WSN中基于多功率移动锚节点的智能定位算法

毛永毅, 陈　鹏

(1.西安邮电大学 电子工程学院，陕西 西安 710121；　2.西安邮电大学 通信与信息工程学院, 陕西 西安 710121)

WSN中基于多功率移动锚节点的智能定位算法

毛永毅1, 陈鹏2

(1.西安邮电大学 电子工程学院，陕西 西安 710121；2.西安邮电大学 通信与信息工程学院, 陕西 西安 710121)

摘要:针对无线传感器网络节点定位，提出一种基于多功率移动锚节点的改进鸡群定位算法。移动锚节点按照移动模型遍历定位区域，通过功率控制发射信标信号，未知节点接收到信标信号后，利用测距模型建立距离方程并采用最小二乘法计算节点坐标，再使用鸡群算法对节点坐标进行修正。仿真结果表明，改进鸡群定位算法的定位精度和收敛速度皆有所提高。

关键词:无线传感器网络(WSN)；节点定位；最小二乘；鸡群算法；多功率移动锚节点

无线传感器网络(WirelessSensorNetwork，WSN)[1]是由散布在监测区域的大量传感器通过无线通信方式构成的多跳自组织网络。WSN感知、采集周围信息，并被广泛应用于军事、农业、医疗和交通等领域。

无线传感器网络定位技术可分为两大类[2]：基于测距(range-based)和基于非测距(range-free)。前者测量节点之间的距离或者角度信息，再利用三边或者三角定位来计算未知节点的坐标，常见的方法有TOA、AOA、TDOA和基于RSSI的定位[3-4]；后者不测量节点之间的距离信息，而是利用网络连通性来计算未知节点的坐标。常见的方法有APIT[5]，DV-hop[6-7]、质心算法、Amorphous算法等。

在定位区域引入移动锚节点,可提高定位精度，降低网络成本[8-9]。利用基于凸优化技术(ConvexCenter，CC)的算法[10]，通过移动锚节点靠近并估计目标域的几何质心进行定位，但计算中将非凸规划问题转化为凸规划问题，降低了定位精度。采用基于多功率移动锚节点的自适应权重粒子群算法[11]进行定位，可合理匹配惯性权重，能精确找到最优解，但收敛速度慢。利用鸡群算法(ChickenSwarmOptimization,CSO)能解决无线传感器网络节点定位问题[12]，但需较多迭代次数。

本文利用鸡群算法修正最小二乘法的定位结果，提出LS-CSO(LeastSquare-ChickenSwarmOptimization)定位算法，以达到提高定位精度和收敛速度的目的。

1移动模型和测距模型

1.1移动模型

在基于移动锚节点的WSN定位中，锚节点的移动模型直接影响未知节点的信息接收和定位误差。SCAN模型[13]是一种常用的锚节点移动模型，能够在一定空间内遍历整个定位区域，如图1所示。假设未知节点随机分布在L×L的正方形区域，锚节点从正方形区域的某点出发，沿箭头方向每次移动一个步长s后停止，以一定的时间间隔通过功率控制向周围发射2种功率依次增强的信标信号，信号包含锚节点当前坐标和相应发射功率[11]。信标信号相应发射功率下的最大通信半径为

R={ri:i=1,2且r1

一旦未知节点接收到锚节点的信号，便不再接收锚节点同一位置更高功率的信号。

图1　SCAN移动模型

1.2测距模型

当未知节点接收到信标信号后，按图2所示测距模型[10]将功率信号转化成距离信息。若未知节点接收到锚节点在某位置第i次发射的功率信号，则未知节点到锚节点的距离d≤ri，因信号按照功率依次增强的顺序进行发射，故d>ri-1，由此得未知节点所在位置区间为ri-1

作为未知节点到锚节点的距离，当i=1时，取ri-1=0。如图2，当未知节点接收到锚节点发射的第2级功率信号时，其到锚节点的距离为

图2　测距模型

2LS-CSO算法原理及步骤

锚节点按照SCAN模型遍历定位区域并发射信标信号。未知节点接收信标信号，通过测距模型计算出其到锚节点的距离d，建立距离方程并采用最小二乘法(leastsquare，LS)求解，得到未知节点的粗略定位；利用鸡群算法进一步对粗定位结果进行修正，得到更准确的定位结果。

2.1基于最小二乘法的节点定位

最小二乘法是一种常用的优化方法，通过最小化误差的平方和寻找最优解。利用最小二乘法计算未知节点坐标，可以减少个别测距误差对定位结果的影响。

(1)

对式(1)中的方程组进行变换，从第一个方程开始分别减去最后一个方程，得

(2)

式(2)可写成矩阵形式

AX=b。

其中

(3)

(4)

(5)

使用标准的最小均方差估计法，可以得到未知节点坐标的矩阵表示

X=(ATA)-1ATb。

(6)

2.2基于鸡群算法的节点定位

鸡群算法[12]模拟鸡群内部的觅食活动，将鸡群划分成多个子群，用适应度评价鸡群中个体的优劣，适应度最小的个体为最优个体，各子群以其内部最优个体的位置为方向寻找最优解。

2.2.1适应度函数

适应度表示鸡群个体与未知节点的接近程度，适应度越小表示个体的位置越接近未知节点真实位置。

f(x′,y′)=

(7)

将所有个体依据适应度从小到大按比例确定为公鸡、母鸡和小鸡，按公鸡数量建立子群，并随机建立公鸡、母鸡和小鸡的隶属关系。

2.2.2移动函数

公鸡在较大的范围内搜寻食物，移动函数为[12]

(8)。

式中N是服从均值为0且方差为σ2的高斯分布的随机数，σ2取值为[12]

(9)

式中ε是计算机中最小的常量，用来避免零因子误差,M表示公鸡的数量，fi表示第i只公鸡的适应度，fk(k=1,2,…,M,k≠i)表示随机选出的第k只公鸡的适应度，其值由式(7)决定。

母鸡跟随同子群的公鸡运动，移动函数为[12]

(10)

其中H是在区间[0,1]上服从均匀分布的随机数，n1是和第i只母鸡同子群的公鸡编号，n2是从整个鸡群中随机选出的个体，且必须满足n2的适应度fn2小于第i只母鸡的适应度fi；c1和c2分别为[12]

(11)

c2=exp[fn2-fi]。

(12)

由式(11)和式(12)可知，c1和c2不预先赋值，而是根据个体的适应度动态调整。

小鸡跟随母鸡觅食，移动函数为[12]

(13)

鸡群算法在定位区域进行初始化，利用式(7)计算个体适应度，并确定公鸡、母鸡、小鸡的数量和隶属关系；不同身份分别按照式(8)、(10)、(13)移动；当达到预设迭代次数时，输出鸡群中最优个体的坐标，即为未知节点的定位坐标。

2.2.3定位误差

定位误差是衡量定位算法优劣的重要参数，可表示为[10]

(14)

2.3LS-CSO算法步骤

利用LS-CSO算法进行WSN定位的主要步骤可描述如下。

步骤1锚节点按照SCAN模型遍历定位区域，根据测距模型计算未知节点与锚节点的距离d，列出距离方程，采用最小二乘法求解方程，得到节点的粗略定位结果。

步骤2定义相关参数，初始化鸡群，按照式(7)计算鸡群中每个个体的适应度。

步骤3按照适应度从小到大的顺序，确定公鸡、母鸡、小鸡的数量和隶属关系，将粗定位得到的结果以公鸡身份加入鸡群。

步骤4子群内隶属关系保持不变，不同的身份分别按照式(8)、(10)、(13)迭代G次。

步骤5根据第G次迭代的结果对个体按适应度重新排序，确立新的身份和隶属关系，返回步骤4。

步骤6当达到预设迭代次数时，停止迭代，输出最优个体坐标。

LS-CSO算法流程如图3所示。

图3　LS-CSO算法流程

3仿真与分析

采用Matlab对算法进行仿真对比，选取100个未知节点随机分布在边长L1= 100m的正方形区域，网络中节点利用RM传播模型[14]进行通信，锚节点有2级发射功率，对应的最大通信半径分别为r1=15m，r2=30m，锚节点按照SCAN模型移动，步长s=10m。鸡群数量为40，公鸡的比例为20%，母鸡的比例为60%，其余为小鸡，每迭代G=5次更新身份，预设迭代30次。

对本文算法和CC算法进行500次仿真，记录两种算法定位误差的最大值、最小值、平均值等，如表1所示。图4为其中一次仿真的定位误差，图中“○”表示节点真实位置，“*”表示定位位置，两者连线为定位误差。

表1　两种算法定位误差数据统计

(a) CC算法(e=12.64%)

(b) LS-CSO算法(e=10.57%)

由表1和图4可见，LS-CSO算法的定位误差(8.57%～11.29%)小于CC算法[10]的定位误差(9.76%～13.06%)。CC算法在计算过程中，将非凸规划问题转化为凸规划问题，使计算中出现非最优解，降低了定位精度。LS-CSO算法通过对未知节点的定位结果进行修正计算，取得了较好的定位精度。

仿真分别从未知节点数量、锚节点通信半径和迭代次数3个方面对算法性能进行对比。结果分别如图5、图6和图7所示。

图5　未知节点数量与定位误差的关系

由图5可知，随着未知节点数量的增加，DV-hop算法的定位误差逐渐减小，LS-CSO算法和CC算法的定位误差波动不大，且前者的定位误差小于后者。DV-hop算法需要较好的网络连通度来进行定位，节点越多越密集定位精度就越高，但是定位误差(32.11%～38.59%)仍然较高。CC算法和LS-CSO算法都是基于锚节点信标信号进行定位的，没有节点间的累积误差，未知节点数量上的增加对定位结果几乎没有影响。

图6　锚节点通信半径与定位误差的关系

由图6可知，随着锚节点通信半径增大，两种算法定位误差均增大。通信半径增大导致测距模型的测距误差增大，但是LS-CSO算法的误差和误差增幅均小于CC算法。

图7　收敛情况

图7中，随着迭代次数增加，3种算法定位误差都逐渐减小并趋于平稳。迭代30次时，CSO算法的定位误差为11.21%，基于多功率移动锚节点的自适应权重粒子群算法[11]的定位误差为11.64%，增加迭代次数误差不再显著降低。LS-CSO迭代15次时，定位误差为10.23%，增加迭代次数误差趋于平稳。可见LS-CSO算法能够在迭代次数较少的情况下达到较高的精度(10.23%)，是因为最小二乘法粗定位的结果能够帮助鸡群算法明确搜索方向，利于算法快速收敛。

4结语

基于多功率移动锚节点，给出一种联合最小二乘法和鸡群算法的LS-CSO定位方法。仿真表明，LS-CSO算法相比于原CSO算法具有更快的收敛速度，相比于CC算法和DV-hop算法，具有更小的定位误差，更适用于WSN定位。

参考文献

[1]ZHUC,WUS,HANGJ,etal.Atree-clusterbaseddatagatheringalgorithmforindustrialWSNswithamobilesink[J/OL].AccessIEEE, 2015,3:381-396[2015-09-15].http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=7091856.DOI: 10.1109/ACCESS.2015.2424452.

[2]WEIQR,ZHONGDX,HANJQ.Improvedlocalisationmethodbasedonmulti-hopdistanceunbiasedestimation[J/OL].IETCommunications, 2014,8(16):2797-2804[2015-09-20].http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=6945956.DOI: 10.1049/iet-com.2014.0263.

[3]PARKJW,PARKDH,LEEC.Angleandrangingbasedlocalizationmethodforadhocnetwork[J/OL].JournalofSupercomputing,2013,64(2):507-521[2015-09-26].http://link.springer.com/10.1007/s11227-011-0700-7.

[4]毛晓明，卢光跃，赵国.一种提高无线传感器网络节点定位精度的算法[J/OL].西安邮电学院学报,2012,17(1):42-46[2015-10-04].http://www.cnki.com.cn/Article/CJFDTotal-XAYD201201010.htm.DOI:10.13682/j.issn.2095-6533.2012.01.018.

[5]HET,HUANGC,BLUMBM,etal.Range-freelocalizationschemesforlargescalesensornetworks[C/OL]//ProceedingsoftheAnnualInternationalConferenceonMobileComputingandNetworking.USA:AssociationforComputingMachinery, 2003:81-95[2015-10-06].http://dl.acm.org/citation.cfm?id=938995.DOI:10.1145/938985.938995.

[6]NICOLESCUD,NATHB.Adhocpositioningsystem(APS)usingAoA[C/OL]//INFOCOM2003.Twenty-SecondAnnualJointConferenceoftheIEEEComputerandCommunications.IEEESocieties.IEEE, 2003, 3:1734-1743[2015-10-11].http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=1209196.DOI:10.1109/INFCOM.2003.1209196.

[7]程超, 钱志鸿, 付彩欣, 等. 一种基于误差距离加权与跳段算法选择的遗传优化DV-Hop定位算法[J/OL]. 电子与信息学报, 2015,37(10):2418-2423[2015-10-22].http://dx.doi.org/10.11999/JEIT141205.

[8]SICHITIUML,RAMADURAIV.Localizationofwirelesssensornetworkswithamobilebeacon[C/OL].MobileAd-hocandSensorSystems, 2004IEEEInternationalConferenceon.IEEE,2004:174-183[2015-11-08].http://www.researchgate.net/publication/4123398_Localization_of_wireless_sensor_networks_with_a_mobile_beacon.DOI:10.1109/MAHSS.2004.1392104.

[9]LUOJ,SHUKLAHV,HUBAUXJP.Non-interactivelocationsurveyingforsensornetworkswithmobility-differentiatedTOA[C/OL]//INFOCOM2006. 25thIEEEInternationalConferenceonComputerCommunications.Proceedings.IEEE,2006, 1983(24):1-12[2015-11-13].http://yadda.icm.edu.pl/yadda/element/bwmeta1.element.ieee-000004146843.DOI:10.1109/INFOCOM.2006.190.

[10] 史清江，何晨. 多功率移动锚节点辅助的分布式节点定位方法[J/OL]. 通信学报,2009,30(10):8-13[2015-11-15].http://www.cnki.com.cn/Article/CJFDTotal-TXXB200910004.htm.

[11] 杜杨洋，毛永毅. 基于多功率移动锚节点WSN智能定位算法[J/OL]. 电子技术应用, 2015,41(6):88-90[2015-12-02].http://www.cnki.com.cn/Article/CJFDTotal-DZJY201506027.htm.DOI:10.16157/j.issn.0258-7998.2015.06.024.

[12]MENGXB,LIUY,GAOXZ,etal.Anewbio-inspiredalgorithm:chickenswarmoptimization[M/OL]//Advancesinswarmintelligence.SpringerInternationalPublishing,2014:86-94[2015-12-15].http://dx.doi.org/10.1007/978-3-319-11857-4_10.

[13]KOUTSONIKOLASD,DASSM,HUYC.Pathplanningofmobilelandmarksforlocalizationinwirelesssensornetworks[J/OL].ComputerCommunications,2007,30(13):2577-2592[2015-12-16].http://dx.doi.org/10.1016/j.comcom.2007.05.048.

[14] 梁青，韩昊澎，李卓冉,等.一种无线传感器网络定位算法的改进[J/OL].西安邮电大学学报, 2014,19(3): 11-14[2015-12-23].http://d.wanfangdata.com.cn/Periodical/xaydxyxb201403003.DOI:10.13682/j.issn.2095-6533.2014.03.003.

[责任编辑:陈文学]

WSNIntelligentnodelocalizationalgorithmbasedonmulti-powermobileanchor

MAOYongyi1，CHENPeng2

(1.SchoolofElectronicEngineering,Xi’anUniversityofPostsandTelecommunications,Xi’an710121,China；2.SchoolofCommunicationandInformationEngineering,Xi’anUniversityofPostsandTelecommunications,Xi’an710121,China)

Abstract:An improved chicken swarm optimization localization algorithm based on mobile anchor is established in WSN to enhance the positioning accuracy. A mobile anchor can move in a target area and launch signals by power control based on moving model. The coordinates of unknown nodes are calculated by the least square method according to range equation after receiving signals from a mobile anchor. Then, the optimal solution is estimated iteratively by chicken swarm optimization algorithm. Simulation results indicate that, the improved algorithm is much better than DV-hop and CC methods in both positioning accuracy and convergence rate.

Keywords:wireless sensor network(WSN), node localization, least square, chicken swarm optimization(CSO), multi-power mobile anchor

doi:10.13682/j.issn.2095-6533.2016.03.007

收稿日期：2016-01-20

基金项目：陕西省自然科学基金资助项目(2014JM2-6088)

作者简介：毛永毅(1969-)，男，博士，教授，从事移动台定位、无线传感器网络定位研究。E-mail:maoyongyi@236.net 陈鹏(1989-)，男，硕士研究生，研究方向为移动通信技术及应用。E-mail:chenpengxupt@126.com

中图分类号：TP393

文献标识码：A

文章编号：2095-6533(2016)03-0048-06