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