基于遗传模拟退火算法的无线传感器网络定位算法

无线传感器网络

第26卷第10期　　　2009年10月　　计算机应用与软件

ComputerApplicationsandSoftwareVol126No.10

Oct.2009

基于遗传模拟退火算法的无线传感器网络定位算法

赵仕俊

1

2

1,2

　孙美玲　唐懿芳

21

(北京科技大学信息工程学院　北京100083)

(中国石油大学计算机与通信工程学院　山东东营257061)

摘　要　　无线传感器网络定位问题本质上是一个基于不同的距离或路径测量方法的优化问题。第一次提出了基于遗传模拟退火

算法的无线传感器网络定位算法GASA2Hop,它是将遗传模拟退火算法作为DV2Hop的后期优化。其中,DV2Hop用来估计未知节点与锚节点的测量距离,GASA用来最小化与DV2Hop相关的适应度函数。仿真结果表明,本算法定位精度高、条件简单,比较适合无线传感器网络的节点定位。

关键词　　无线传感器网络　定位算法　遗传模拟退火算法　算法性能

GASA2BASEDLOCALISATIONALGORITHMRWORKS

1

2

1,2

Yifang

1

(ofUandTechnologyBeijing,Beijing100083,China)

(mEngineering,ChinaUniversityofPetroleum,Dongying257061,Shandong,China)

Abstract　　Inessential,localisationofwirelesssensornetworksisanoptimizationproblemofmeasurementbasedondifferentdistanceorpath.Inthispaper,weproposedalocalisationalgorithmforwirelesssensornetworksbasedonGASA,GASA2Hopforthefirsttime,whichusesGASAasthepost2optimisationofDV2Hop.Init,theDV2Hopisusedtoestimatethemeasuringdistancebetweentheunknownnodesandtheanchornodes,andGASAisusedtominimisethefitnessfunctioncorrelatedtoDV2Hop.OursimulationresultsrevealthattheGASA2Hophashighprecisionandsimplepreconditionandissuitableforthenodesπlocalisationinwirelesssensornetworks.

Keywords　　Wirelesssensornetworks　Localizationalgorithm　Geneticandsimulatedannealing(GASA)　Algorithmperformance

0　引　言

无线传感器网络(WSN)作为上世纪新兴的一种技术,在工农业、城市管理、抢险救灾等许多领域都有重要的科研价值和应用前景。WSN由大量的无线传感器节点组成,每个节点随机布置,因此很难得知其具体位置。虽然运用GPS可以精确得到每个节点的位置,但它高昂的成本和使用环境的限制使它不能广泛应用于WSN。目前,应用定位算法来估算节点位置已经成为一个热点。现有的WSN定位算法是根据少量的位置已知的节点(锚节点)以及它们与其它节点的通信信息来估算整个网络中每个节点的位置。这些算法大部分由两个阶段组成。第一阶段,测量未知节点和锚节点之间的距离或角度,这一阶段称为测距阶段。第二阶段,利用前一阶段的距离或角度测量值得到未知节点的位置,这一阶段称为定位阶段。由于设备的硬件代价和使用限制条件,并且粗精度的定位对于绝大多数应用来说已经足够,许多研究者认为跳段距离是估计未知节点和锚节点距离的一种有效途径。DV2Hop是利用跳段距离的定位算法中最受关注的一个。

定位问题已经被证明是一个NP难解的问题[1],要想在多项式时间内解决这个问题必须使用启发式方法。本文提出使用遗传模拟退火算法作为DV2Hop的后期优化,即使用DV2Hop计

算基于跳段的距离,使用遗传模拟退火算法计算节点的位置。

仿真结果表明,这种新的定位方法比目前提出的其他几个定位算法的性能要好。

1　相关工作

目前许多定位算法相继被提出[2,3]。本文仅详细介绍利用跳段数来计算距离的方法,因为本文的距离估计就是采用该方法。

1.1　DV2Hop的基本机制

DV2Hop

[4-6]

是一种基于跳段的定位算法。它主要由三个

阶段组成。

第一阶段,网络中所有的节点计算其到每一个锚节点的最短路径,该路径是跳段数的形式。具体执行过程如下:每个节点都需要一个表来记录锚节点的信息,该表类似于路由表,我们称之为“锚节点列表”。每个“锚节点列表”的形式为{IDi,xi,yi,hi},其中IDi是锚节点的标识符,xi和yi分别是该锚节点的横坐标和纵坐标,hi是节点到该锚节点的跳数值。开始时,每个

收稿日期:2008-09-12。赵仕俊,副教授,主研领域:无线传感器网络,检测技术与自动化装置。

无线传感器网络

　　190　　　

计算机应用与软件2009年

锚节点都广播一个消息,其中包含它的IDi、(xi,yi)和hi(hi被初始化为0)。一旦接收到此消息,接收节点会检查它的“锚节点列表”中是否含有相同IDi的锚节点信息。如果没有,接收节点就把到该锚节点的跳数值增加1,并将该锚节点的IDi记录到其自身的“锚节点列表”中,然后将此消息广播给它的邻居节点;如果有,则接收节点会将本次接收到的消息中的hi与它“锚节点列表”中的hi进行比较。如果本次消息的跳数值hi小于原来的,则表明了本次的跳数值hi是到那个锚节点的较短跳数值hi,于是该接收节点就更新其“锚节点列表”中的跳数值为此较小者,并将跳数值加1后广播给其邻居节点;若以上两种情况都不是,该消息就被抛弃,既不被更新也不被广播。更新和广播一直继续,直到找到所有的最短路径。

第二阶段:一旦一个锚节点得到了到其他所有锚节点的信息,该锚节点就会计算平均每跳距离Hopsizei,它是该锚节点到所有锚节点的距离之和与所有跳数值之和的比值。锚节点计算出Hopsizei后,会将该值广播给邻居未知节点。Hopsizei被未知节点用来粗略估算到每个锚节点的欧式距离,即将未知节点到每个锚节点的跳数乘以Hopsizei。

每个锚节点计算Hopsizei的公式为:

∑

Hopsizei=

(xi-xj)2+(-)2

i

)

式中,hj是当前位于i(xj,yj)的锚节点之间的跳数值。

由经验可知,一个锚节点在整个定位过程中至少需要计算一次Hopsizei。Hopsizei的更新和广播在文献[7]中被第一次陈述。

第三阶段:在二维空间中,一旦一个未知节点至少知道了它到三个锚节点的估计距离,该未知节点就会执行三边方法来估算自身的位置。每当有了新的信息时,该估计值将会被更新。这些新的信息可以是新的锚节点信息、到锚节点的更短路径、新的Hopsizei等。当不再有更新并且整个网络变得稳定时,定位估计停止,即定位过程完成。

始,但它却容易陷入局部最小解。相反,如果初始温度较高,降温速率较低,SA可以克服局部最小解。但是较高的初始温度和较低的降温速率影响了SA的性能。并且SA的并行性不易实施。本文提出的GASA将全局搜索的GA和局部搜索的SA相结合,是性能更好的优化方法。

一对个体进行交叉和变异操作后会有四个染色体:两个父代个体和两个子代个体。在传统的GA中,父代个体会被它们的子代个体代替。但是在GASA中,组成下一代的两个染色体是从这四个染色体中选择出来的。选择的标准是它们的适应度值。适应度值较高的染色体保留到下一代的概率较大;适应度值较小的个体不一定被抛弃,利用作为局部选择策略的模拟退火算法进行概率性的选择,该概率与当前的控制温度有关。该选择过程涉及四个参数,他们是fbest、fworst、fi和Tt。其中fbest是父代个体中适应度值最好的个体,fworst是父代个体中适应度值最差的个体,fi是子代个体的适应度值,Tt。在每个温度Tt,试验染色体的适应度函数值f(1,2)与fworst进行比较。,i(2)min[1,(fi-wTt]>r

,r0到1。如果染色体i被接受,则。

开始时,GASA的变异概率Pm被设置成 …… 此处隐藏：9097字，全部文档内容请下载后查看。喜欢就下载吧 ……