毛永毅, 陳　鵬

(1.西安郵電大學(xué) 電子工程學(xué)院，陜西 西安 710121；　2.西安郵電大學(xué) 通信與信息工程學(xué)院, 陜西 西安 710121)

WSN中基于多功率移動錨節(jié)點的智能定位算法

毛永毅1, 陳鵬2

(1.西安郵電大學(xué) 電子工程學(xué)院，陜西 西安 710121；2.西安郵電大學(xué) 通信與信息工程學(xué)院, 陜西 西安 710121)

摘要:針對無線傳感器網(wǎng)絡(luò)節(jié)點定位，提出一種基于多功率移動錨節(jié)點的改進(jìn)雞群定位算法。移動錨節(jié)點按照移動模型遍歷定位區(qū)域，通過功率控制發(fā)射信標(biāo)信號，未知節(jié)點接收到信標(biāo)信號后，利用測距模型建立距離方程并采用最小二乘法計算節(jié)點坐標(biāo)，再使用雞群算法對節(jié)點坐標(biāo)進(jìn)行修正。仿真結(jié)果表明，改進(jìn)雞群定位算法的定位精度和收斂速度皆有所提高。

關(guān)鍵詞:無線傳感器網(wǎng)絡(luò)(WSN)；節(jié)點定位；最小二乘；雞群算法；多功率移動錨節(jié)點

無線傳感器網(wǎng)絡(luò)(WirelessSensorNetwork，WSN)[1]是由散布在監(jiān)測區(qū)域的大量傳感器通過無線通信方式構(gòu)成的多跳自組織網(wǎng)絡(luò)。WSN感知、采集周圍信息，并被廣泛應(yīng)用于軍事、農(nóng)業(yè)、醫(yī)療和交通等領(lǐng)域。

無線傳感器網(wǎng)絡(luò)定位技術(shù)可分為兩大類[2]：基于測距(range-based)和基于非測距(range-free)。前者測量節(jié)點之間的距離或者角度信息，再利用三邊或者三角定位來計算未知節(jié)點的坐標(biāo)，常見的方法有TOA、AOA、TDOA和基于RSSI的定位[3-4]；后者不測量節(jié)點之間的距離信息，而是利用網(wǎng)絡(luò)連通性來計算未知節(jié)點的坐標(biāo)。常見的方法有APIT[5]，DV-hop[6-7]、質(zhì)心算法、Amorphous算法等。

在定位區(qū)域引入移動錨節(jié)點,可提高定位精度，降低網(wǎng)絡(luò)成本[8-9]。利用基于凸優(yōu)化技術(shù)(ConvexCenter，CC)的算法[10]，通過移動錨節(jié)點靠近并估計目標(biāo)域的幾何質(zhì)心進(jìn)行定位，但計算中將非凸規(guī)劃問題轉(zhuǎn)化為凸規(guī)劃問題，降低了定位精度。采用基于多功率移動錨節(jié)點的自適應(yīng)權(quán)重粒子群算法[11]進(jìn)行定位，可合理匹配慣性權(quán)重，能精確找到最優(yōu)解，但收斂速度慢。利用雞群算法(ChickenSwarmOptimization,CSO)能解決無線傳感器網(wǎng)絡(luò)節(jié)點定位問題[12]，但需較多迭代次數(shù)。

本文利用雞群算法修正最小二乘法的定位結(jié)果，提出LS-CSO(LeastSquare-ChickenSwarmOptimization)定位算法，以達(dá)到提高定位精度和收斂速度的目的。

1移動模型和測距模型

1.1移動模型

在基于移動錨節(jié)點的WSN定位中，錨節(jié)點的移動模型直接影響未知節(jié)點的信息接收和定位誤差。SCAN模型[13]是一種常用的錨節(jié)點移動模型，能夠在一定空間內(nèi)遍歷整個定位區(qū)域，如圖1所示。假設(shè)未知節(jié)點隨機分布在L×L的正方形區(qū)域，錨節(jié)點從正方形區(qū)域的某點出發(fā)，沿箭頭方向每次移動一個步長s后停止，以一定的時間間隔通過功率控制向周圍發(fā)射2種功率依次增強的信標(biāo)信號，信號包含錨節(jié)點當(dāng)前坐標(biāo)和相應(yīng)發(fā)射功率[11]。信標(biāo)信號相應(yīng)發(fā)射功率下的最大通信半徑為

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

一旦未知節(jié)點接收到錨節(jié)點的信號，便不再接收錨節(jié)點同一位置更高功率的信號。

圖1　SCAN移動模型

1.2測距模型

當(dāng)未知節(jié)點接收到信標(biāo)信號后，按圖2所示測距模型[10]將功率信號轉(zhuǎn)化成距離信息。若未知節(jié)點接收到錨節(jié)點在某位置第i次發(fā)射的功率信號，則未知節(jié)點到錨節(jié)點的距離d≤ri，因信號按照功率依次增強的順序進(jìn)行發(fā)射，故d>ri-1，由此得未知節(jié)點所在位置區(qū)間為ri-1

作為未知節(jié)點到錨節(jié)點的距離，當(dāng)i=1時，取ri-1=0。如圖2，當(dāng)未知節(jié)點接收到錨節(jié)點發(fā)射的第2級功率信號時，其到錨節(jié)點的距離為

圖2　測距模型

2LS-CSO算法原理及步驟

錨節(jié)點按照SCAN模型遍歷定位區(qū)域并發(fā)射信標(biāo)信號。未知節(jié)點接收信標(biāo)信號，通過測距模型計算出其到錨節(jié)點的距離d，建立距離方程并采用最小二乘法(leastsquare，LS)求解，得到未知節(jié)點的粗略定位；利用雞群算法進(jìn)一步對粗定位結(jié)果進(jìn)行修正，得到更準(zhǔn)確的定位結(jié)果。

2.1基于最小二乘法的節(jié)點定位

最小二乘法是一種常用的優(yōu)化方法，通過最小化誤差的平方和尋找最優(yōu)解。利用最小二乘法計算未知節(jié)點坐標(biāo)，可以減少個別測距誤差對定位結(jié)果的影響。

(1)

對式(1)中的方程組進(jìn)行變換，從第一個方程開始分別減去最后一個方程，得

(2)

式(2)可寫成矩陣形式

AX=b。

其中

(3)

(4)

(5)

使用標(biāo)準(zhǔn)的最小均方差估計法，可以得到未知節(jié)點坐標(biāo)的矩陣表示

X=(ATA)-1ATb。

(6)

2.2基于雞群算法的節(jié)點定位

雞群算法[12]模擬雞群內(nèi)部的覓食活動，將雞群劃分成多個子群，用適應(yīng)度評價雞群中個體的優(yōu)劣，適應(yīng)度最小的個體為最優(yōu)個體，各子群以其內(nèi)部最優(yōu)個體的位置為方向?qū)ふ易顑?yōu)解。

2.2.1適應(yīng)度函數(shù)

適應(yīng)度表示雞群個體與未知節(jié)點的接近程度，適應(yīng)度越小表示個體的位置越接近未知節(jié)點真實位置。

f(x′,y′)=

(7)

將所有個體依據(jù)適應(yīng)度從小到大按比例確定為公雞、母雞和小雞，按公雞數(shù)量建立子群，并隨機建立公雞、母雞和小雞的隸屬關(guān)系。

2.2.2移動函數(shù)

公雞在較大的范圍內(nèi)搜尋食物，移動函數(shù)為[12]

(8)。

式中N是服從均值為0且方差為σ2的高斯分布的隨機數(shù)，σ2取值為[12]

(9)

式中ε是計算機中最小的常量，用來避免零因子誤差,M表示公雞的數(shù)量，fi表示第i只公雞的適應(yīng)度，fk(k=1,2,…,M,k≠i)表示隨機選出的第k只公雞的適應(yīng)度，其值由式(7)決定。

母雞跟隨同子群的公雞運動，移動函數(shù)為[12]

(10)

其中H是在區(qū)間[0,1]上服從均勻分布的隨機數(shù)，n1是和第i只母雞同子群的公雞編號，n2是從整個雞群中隨機選出的個體，且必須滿足n2的適應(yīng)度fn2小于第i只母雞的適應(yīng)度fi；c1和c2分別為[12]

(11)

c2=exp[fn2-fi]。

(12)

由式(11)和式(12)可知，c1和c2不預(yù)先賦值，而是根據(jù)個體的適應(yīng)度動態(tài)調(diào)整。

小雞跟隨母雞覓食，移動函數(shù)為[12]

(13)

雞群算法在定位區(qū)域進(jìn)行初始化，利用式(7)計算個體適應(yīng)度，并確定公雞、母雞、小雞的數(shù)量和隸屬關(guān)系；不同身份分別按照式(8)、(10)、(13)移動；當(dāng)達(dá)到預(yù)設(shè)迭代次數(shù)時，輸出雞群中最優(yōu)個體的坐標(biāo)，即為未知節(jié)點的定位坐標(biāo)。

2.2.3定位誤差

定位誤差是衡量定位算法優(yōu)劣的重要參數(shù)，可表示為[10]

(14)

2.3LS-CSO算法步驟

利用LS-CSO算法進(jìn)行WSN定位的主要步驟可描述如下。

步驟1錨節(jié)點按照SCAN模型遍歷定位區(qū)域，根據(jù)測距模型計算未知節(jié)點與錨節(jié)點的距離d，列出距離方程，采用最小二乘法求解方程，得到節(jié)點的粗略定位結(jié)果。

步驟2定義相關(guān)參數(shù)，初始化雞群，按照式(7)計算雞群中每個個體的適應(yīng)度。

步驟3按照適應(yīng)度從小到大的順序，確定公雞、母雞、小雞的數(shù)量和隸屬關(guān)系，將粗定位得到的結(jié)果以公雞身份加入雞群。

步驟4子群內(nèi)隸屬關(guān)系保持不變，不同的身份分別按照式(8)、(10)、(13)迭代G次。

步驟5根據(jù)第G次迭代的結(jié)果對個體按適應(yīng)度重新排序，確立新的身份和隸屬關(guān)系，返回步驟4。

步驟6當(dāng)達(dá)到預(yù)設(shè)迭代次數(shù)時，停止迭代，輸出最優(yōu)個體坐標(biāo)。

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

圖3　LS-CSO算法流程

3仿真與分析

采用Matlab對算法進(jìn)行仿真對比，選取100個未知節(jié)點隨機分布在邊長L1= 100m的正方形區(qū)域，網(wǎng)絡(luò)中節(jié)點利用RM傳播模型[14]進(jìn)行通信，錨節(jié)點有2級發(fā)射功率，對應(yīng)的最大通信半徑分別為r1=15m，r2=30m，錨節(jié)點按照SCAN模型移動，步長s=10m。雞群數(shù)量為40，公雞的比例為20%，母雞的比例為60%，其余為小雞，每迭代G=5次更新身份，預(yù)設(shè)迭代30次。

對本文算法和CC算法進(jìn)行500次仿真，記錄兩種算法定位誤差的最大值、最小值、平均值等，如表1所示。圖4為其中一次仿真的定位誤差，圖中“○”表示節(jié)點真實位置，“*”表示定位位置，兩者連線為定位誤差。

表1　兩種算法定位誤差數(shù)據(jù)統(tǒng)計

(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算法在計算過程中，將非凸規(guī)劃問題轉(zhuǎn)化為凸規(guī)劃問題，使計算中出現(xiàn)非最優(yōu)解，降低了定位精度。LS-CSO算法通過對未知節(jié)點的定位結(jié)果進(jìn)行修正計算，取得了較好的定位精度。

仿真分別從未知節(jié)點數(shù)量、錨節(jié)點通信半徑和迭代次數(shù)3個方面對算法性能進(jìn)行對比。結(jié)果分別如圖5、圖6和圖7所示。

圖5　未知節(jié)點數(shù)量與定位誤差的關(guān)系

由圖5可知，隨著未知節(jié)點數(shù)量的增加，DV-hop算法的定位誤差逐漸減小，LS-CSO算法和CC算法的定位誤差波動不大，且前者的定位誤差小于后者。DV-hop算法需要較好的網(wǎng)絡(luò)連通度來進(jìn)行定位，節(jié)點越多越密集定位精度就越高，但是定位誤差(32.11%～38.59%)仍然較高。CC算法和LS-CSO算法都是基于錨節(jié)點信標(biāo)信號進(jìn)行定位的，沒有節(jié)點間的累積誤差，未知節(jié)點數(shù)量上的增加對定位結(jié)果幾乎沒有影響。

圖6　錨節(jié)點通信半徑與定位誤差的關(guān)系

由圖6可知，隨著錨節(jié)點通信半徑增大，兩種算法定位誤差均增大。通信半徑增大導(dǎo)致測距模型的測距誤差增大，但是LS-CSO算法的誤差和誤差增幅均小于CC算法。

圖7　收斂情況

圖7中，隨著迭代次數(shù)增加，3種算法定位誤差都逐漸減小并趨于平穩(wěn)。迭代30次時，CSO算法的定位誤差為11.21%，基于多功率移動錨節(jié)點的自適應(yīng)權(quán)重粒子群算法[11]的定位誤差為11.64%，增加迭代次數(shù)誤差不再顯著降低。LS-CSO迭代15次時，定位誤差為10.23%，增加迭代次數(shù)誤差趨于平穩(wěn)。可見LS-CSO算法能夠在迭代次數(shù)較少的情況下達(dá)到較高的精度(10.23%)，是因為最小二乘法粗定位的結(jié)果能夠幫助雞群算法明確搜索方向，利于算法快速收斂。

4結(jié)語

基于多功率移動錨節(jié)點，給出一種聯(lián)合最小二乘法和雞群算法的LS-CSO定位方法。仿真表明，LS-CSO算法相比于原CSO算法具有更快的收斂速度，相比于CC算法和DV-hop算法，具有更小的定位誤差，更適用于WSN定位。

參考文獻(xiàn)

[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]毛曉明，盧光躍，趙國.一種提高無線傳感器網(wǎng)絡(luò)節(jié)點定位精度的算法[J/OL].西安郵電學(xué)院學(xué)報,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]程超, 錢志鴻, 付彩欣, 等. 一種基于誤差距離加權(quán)與跳段算法選擇的遺傳優(yōu)化DV-Hop定位算法[J/OL]. 電子與信息學(xué)報, 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] 史清江，何晨. 多功率移動錨節(jié)點輔助的分布式節(jié)點定位方法[J/OL]. 通信學(xué)報,2009,30(10):8-13[2015-11-15].http://www.cnki.com.cn/Article/CJFDTotal-TXXB200910004.htm.

[11] 杜楊洋，毛永毅. 基于多功率移動錨節(jié)點WSN智能定位算法[J/OL]. 電子技術(shù)應(yīng)用, 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] 梁青，韓昊澎，李卓冉,等.一種無線傳感器網(wǎng)絡(luò)定位算法的改進(jìn)[J/OL].西安郵電大學(xué)學(xué)報, 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.

[責(zé)任編輯:陳文學(xué)]

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

基金項目：陜西省自然科學(xué)基金資助項目(2014JM2-6088)

作者簡介：毛永毅(1969-)，男，博士，教授，從事移動臺定位、無線傳感器網(wǎng)絡(luò)定位研究。E-mail:maoyongyi@236.net 陳鵬(1989-)，男，碩士研究生，研究方向為移動通信技術(shù)及應(yīng)用。E-mail:chenpengxupt@126.com

中圖分類號：TP393

文獻(xiàn)標(biāo)識碼：A

文章編號：2095-6533(2016)03-0048-06