基于混合蛙跳的無線傳感器網(wǎng)絡定位方法

江宇波，趙攀，邱玲

（四川理工學院計算機學院，四川自貢643000）

基于混合蛙跳的無線傳感器網(wǎng)絡定位方法

江宇波，趙攀，邱玲

（四川理工學院計算機學院，四川自貢643000）

為了解決無線傳感器網(wǎng)絡未知節(jié)點的定位問題，提出了一種新的三維空間定位方法。首先給出了未知節(jié)點位置的計算方法和誤差評價模型，并利用混合蛙跳算法建立了評價模型的求解算法SFLL。最后，利用仿真實驗，對比了與其它算法之間的性能狀況，結(jié)果表明SFLL具有較好的適應性。

無線傳感器網(wǎng)絡；定位；最小二乘法；混合蛙跳

引言

隨著無線傳感器網(wǎng)絡（Wireless Sensor Network，WSN）的發(fā)展和物聯(lián)網(wǎng)技術的興起，對未知節(jié)點的定位逐漸成為了研究的熱點和重點［1-2］。目前，定位算法可以分為距離和非距離兩種方法。距離定位算法根據(jù)未知節(jié)點與錨節(jié)點的距離，并結(jié)合三邊或者多邊角方法來確定未知節(jié)點位置，主要有RSSI算法［3］、TOA算法［4］等。而基于非距離定位算法則根據(jù)未知節(jié)點與錨節(jié)點之間的鄰接關系來定位，典型代表有質(zhì)心算法［5］、MDS－MAP算法［6］等。最近，基于距離的定位算法又有了更新的發(fā)展，如最小二乘定位算法［7］，采用負梯度搜索等優(yōu)化算法進行定位，不僅所需錨節(jié)點比例較少，而且定位精度更高。

在上述工作的基礎上，本文提出了一種新的三維空間的定位算法和誤差評價模型。該模型利用混合蛙跳算法對評價函數(shù)進行求解，同時通過數(shù)學仿真對比研究了該算法與RSSI（Received Signal Strength Indicator）算法、TOA（Time Of Arrival）算法之間的性能狀況，以此驗證該模型的有效性。

1 節(jié)點定位方法

假設某無線傳感器網(wǎng)絡中存在N個節(jié)點，其中M個為錨節(jié)點，坐標信息通過GPS定位系統(tǒng)確定，如圖1所示，其中M代表錨節(jié)點，N代表未知節(jié)點。由于受到能量、成本等因素限制，只有少量節(jié)點可以成為錨節(jié)點，其余節(jié)點需要通過錨節(jié)點進行定位。距離定位算法［8-9］利用三邊法或最大似然估計法，并結(jié)合信號強度來獲取未知節(jié)點與錨節(jié)點之間的距離，但此方法只適用于錨節(jié)點個數(shù)大于3的情況。因此，本文基于三維空間提出了一種新的無線傳感器網(wǎng)絡節(jié)點定位算法，其思路是：首先根據(jù)能量和傳輸距離將網(wǎng)絡節(jié)點劃分成多個簇，其次根據(jù)每個簇內(nèi)的錨節(jié)點對未知節(jié)點進行定位。

在初始情況下，令所有節(jié)點功能相同、能量有限、通信功率可調(diào)。首先將節(jié)點劃分成簇，簇內(nèi)節(jié)點之間均采用直接通信方式，而簇間則可以選擇直接或間接等方式通信，以達到能耗最低和效率最高的目的。根據(jù)LEACH協(xié)議，需要在各簇中產(chǎn)生簇首節(jié)點。對于各節(jié)點隨機生成（0，1）之間的常數(shù)ε及閾值J，如果ε＜J，則將當前節(jié)點加入候選簇首集合并向周圍節(jié)點進行廣播。如果在相鄰區(qū)域內(nèi)存在多個候選簇首節(jié)點，那么比較當前這些節(jié)點的剩余能量，剩余能量大者作為簇首節(jié)點，其余為普通節(jié)點。這里，閾值J定義為：

其中，p為簇首節(jié)點占總節(jié)點的比例，E0為節(jié)點i的初始能量，λ為距離比例，dm為最大閾值，φ為常系數(shù)（0＜φ＜1），Ee為發(fā)送或接收1比特信息時所消耗的能量，η為在單位距離內(nèi)的信道上傳輸1比特信息時所消耗的能量，d為節(jié)點之間相距距離。

此時，按照產(chǎn)生的簇首節(jié)點集合，以各簇首節(jié)點為中心、R為半徑的球體來劃分簇結(jié)構(gòu)。如果某節(jié)點位于多個球體交界處，那么以距某簇首節(jié)點距離最短作為劃分標準，如圖1中虛線代表簇邊界。

假設簇內(nèi)數(shù)據(jù)轉(zhuǎn)發(fā)只需1跳，而轉(zhuǎn)發(fā)到相鄰簇則需要2跳。由各個簇內(nèi)錨節(jié)點的分布狀況，定位未知節(jié)點位置可分為以下幾種情況：

（1）簇內(nèi)存在2個以上錨節(jié)點

此時，可以通過最小二乘法進行求解。假設未知節(jié)點N的坐標為（x，y，z），錨節(jié)點Mi（i＝1，2，…，k，k≥3）的坐標為（xi，yi，zi），那么未知節(jié)點Node與錨節(jié)Mi之間的測量距離ri滿足：

由于存在多于3個已知錨節(jié)點信息，對上述方程進行求解可得到如下形式：

（2）簇內(nèi)存在2個錨節(jié)點

假設這2個錨節(jié)點坐標分別為M1（x1，y1，z1）和M2（x2，y2，z2），根據(jù)公式（2）計算它與未知節(jié)點之間的測量距離r1和r2。同時分別以這兩個錨節(jié)點為中心、r1和r2為半徑的作出兩球區(qū)域，在連接球心的軸線上，取其中心點位置為新增臨時錨節(jié)點M3（x3，y3，z3），當兩球體相交時，其坐標為：

當兩球體不相交時：根據(jù)錨節(jié)點M1（x1，y1，z1）、M2（x2，y2，z2）和M3（x3，y3，z3）信息，利用標準最小二乘法可獲得未知節(jié)點坐標信息。

（3）簇內(nèi)存在2個以下錨節(jié)點

此時由于錨節(jié)點距離未知節(jié)點較遠，只能利用上述2個錨節(jié)點定位方法進行計算，其定位誤差將增大。

2 算法描述

對于上述方法，其關鍵在于求解測量距離ri。但是由于GPS定位誤差以及計算結(jié)果的近似處理，未知節(jié)點位置會存在一定偏差。假設位置節(jié)點與錨節(jié)點之間實際距離為di，誤差為εi，那么滿足越小代表定位精度越高，當εi→0時，定位算法獲得最優(yōu)解。因此，本文首先建立目標函數(shù)：

其約束條件為：

由此，本文結(jié)合混合蛙跳算法對上述方法進行求解?；旌贤芴惴ㄊ且环N群體智能的生物進化算法［10-11］，它模擬了青蛙群體尋找食物時按族群分類進行信息交換的過程，算法將群體分割為多個族群，在族群內(nèi)部和簇群之間進行更新操作。各族群內(nèi)部搜索和全局信息交換一直持續(xù)交替進行到滿足收斂條件或達到最大迭代次數(shù)為止。本文結(jié)合混合蛙跳算法給出目標函數(shù)的求解算法（Shuffled Frog Leaping－based Localization algorithm，SFLL），其步驟如下：

（1）定義混合蛙跳算法的適應度函數(shù)來衡量當前解的優(yōu)劣：

（2）初始化，確定t＝0時WSN的各項參數(shù)。并令青蛙個體初始數(shù)目為a，將目標函數(shù)F視作青蛙個體，測量距離ri視作表示青蛙個體移動步長，最大迭代次數(shù)為MAXT；

（3）隨機產(chǎn)生初始種群，計算個體適應度。然后將個體按照適應度值大小進行降序排列，并按以下原則分配到s個族群中：第1個個體放入第1個族群，第2個個體放入第2個族群，…，第s個個體放入第s個族群，第s＋1個個體放入第1個族群，這樣一直循環(huán)，直至所有個體分配完畢；

（4）在每一個族群中，適應度最優(yōu)解和最差解是以其適應函數(shù)值的最大和最小值來確定的，記為Fopt（s）和Fwst（s），并將所有族群Fopt（s）的最大值作為種群的全局最優(yōu)解Fopt；

（5）在每個族群內(nèi)部進行如式的內(nèi)部搜索：

其中，a為（0，1）之間的系數(shù)，rnewi表示青蛙個體更新之后的移動步長。如果Fwst（s）發(fā)生改變，則使用新的Fwst（s），否則將Fopt（s）換成Fopt來重新執(zhí)行內(nèi)部搜索；如果仍沒有改變，則隨機產(chǎn)生（Fwst（s），F(xiàn)opt（s））之間的任意數(shù)來替換Fwst（s）；

（6）當所有族群內(nèi)部更新完成后，令t＝t＋1并跳轉(zhuǎn)到步驟（3），重新劃分族群和執(zhí)行更新操作，直到達到最大迭代次數(shù)MAXT；

（7）輸出當前最優(yōu)解，即為預測誤差極小值；

（8）算法結(jié)束。

3 仿真實驗

對于本文提出的SFLL算法，利用NS2和MATLAB進行仿真實驗來驗證其有效性。這里基于NS2建立如圖1所示的仿真拓撲結(jié)構(gòu)，設置三維空間大小為100 m×100m×100m，節(jié)點數(shù)目100個，并劃分為15個柵格，測距半徑為10 m。同時令青蛙個體初始數(shù)目為100個，共有15個族群，最大迭代次數(shù)為200。這里將本文提出的SFLL算法與傳統(tǒng)的RSSI（Received Signal Strength Indicator）算法、TOA（Time Of Arrival）算法進行對比。

首先研究平均定位誤差與錨節(jié)點通信半徑之間的關系。圖2給出了這三種算法對應的平均定位誤差與錨節(jié)點通信半徑之間的關系。由圖2可以看出，隨著錨節(jié)點通信半徑的增加，平均定位誤差逐漸減低，直至平穩(wěn)。這與通常理解是一致的，若錨節(jié)點通信半徑可以增大到整個區(qū)域空間，那么該區(qū)域內(nèi)將不存在盲區(qū)，那么平均定位誤差趨于0。而當達到相同平均定位誤差時，SFLL算法所需的錨節(jié)點通信半徑更小。

其次，對比分析錨節(jié)點數(shù)量對平均定位誤差的影響情況（圖3）。令ρ表示錨節(jié)點數(shù)量與總節(jié)點數(shù)量的比值，從圖3可以看出，當ρ增加時平均定位誤差呈現(xiàn)遞減趨勢，這與通常的理解一致。加大錨節(jié)點在空間區(qū)域中的密度，使得網(wǎng)絡中的盲點區(qū)域減少，可以獲得更大的定位精度，但是此時將會加大系統(tǒng)開銷成本。所以在實際應用中，應綜合各種因素來考慮錨節(jié)點密度。并且從圖3中可以看出，在相同密度下，SFLL算法計算得到的平均定位誤差最小，而TOA算法精度最差，說明SFLL算法具有一定的精度優(yōu)勢。

最后，深入分析影響SFLL算法的關鍵因素。圖4給出了不同青蛙簇群數(shù)量s下平均定位誤差的變化趨勢。在仿真初始階段，簇群數(shù)越大對應的平均定位誤差越小，而在仿真后期情況發(fā)生突變，簇群數(shù)越大對應的平均定位誤差越大。這是因為初始階段青蛙個體性能普遍較低，此時簇群數(shù)越大即意味著簇內(nèi)個體越小，個體性能更新速度將越快；而在仿真后期，隨著整體性能的提供啊，此時簇群數(shù)越小可以有效擴大個體尋優(yōu)的目標，避免陷入局部最優(yōu)。

4 結(jié)束語

為了有效解決無線傳感器網(wǎng)絡中未知節(jié)點定位精度的問題，本文結(jié)合最小二乘法建立了三維空間的定位算法SFLL。首先將WSN節(jié)點劃分成簇，并根據(jù)簇內(nèi)錨節(jié)點數(shù)量給出了未知節(jié)點坐標的具體計算方法和誤差評價模型，同時利用混合蛙跳算法對評價模型進行求解。最后通過進行數(shù)學仿真，深入研究了該算法與其他算法之間的性能差異，結(jié)果表明SFLL具有較好的適應性。

［1］Wang W,Srinivasan V,Wang B,et al.Coverage for target localization in w ireless sensor neworks［J］.IEEE Transactions on W ireless Communications,2008,7（2）：667-676.

［2］馮晨.無線傳感器網(wǎng)絡定位精度優(yōu)化方法研究［D］.南京：南京郵電大學,2013.

［3］詹杰,劉宏立,劉述鋼,等.基于RSSI的動態(tài)權(quán)重定位算法研究［J］.電子學報,2011,39（1）：82-88.

［4］孟令軍,王宏濤,夏善紅.WSN節(jié)點聲測距TOA值頻域估計方法［J］.電子與信息學報,2010,32（4）：993-997.

［5］宮娜娜,王緩緩.無線傳感器網(wǎng)絡質(zhì)心算法的最佳通信半徑［J］.計算機仿真,2013,30（5）：203-207.

［6］馬震,劉云,沈波.分布式無線傳感器網(wǎng)絡定位算法MDS-MAP（D）［J］.通信學報,2008,29（6）：57-62.

［7］匡興紅,邵惠鶴.基于傳感器網(wǎng)絡的氣體源定位方法研究［J］.系統(tǒng)仿真學報,2007,19（7）：1464-1467.

［8］丁衛(wèi)平,王建東,管致錦.基于量子蛙跳協(xié)同進化的粗糙屬性快速約簡［J］.電子學報,2011,39（11）：2597-2603.

［9］楊維劍,王梅英.無線網(wǎng)絡傳感器中超低功耗節(jié)點能源技術研究［J］.四川理工學院學報：自然科學版, 2010,23（1）：44-47.

［10］葛宇,王學平,梁靜.基于蛙跳算法的DV-Hop定位改進［J］.計算機應用,2011,31（4）：922-924.

［11］葛宇,梁靜,許波,等.基于蛙跳算法的無線傳感器網(wǎng)絡節(jié)點定位［J］.計算機工程與應用,2012,48（20）：126-130.

Node Localization Method ofW ireless Sensor Network Based on Shuffled Frog Leaping

JIANG Yubo，ZHAO Pan，QIU Ling
（School of Computer Science，Sichuan University of Science＆Engineering，Zigong 643000，China）

In order tomitigate the node localization accuracy in wireless sensor network，a new three-dimensional localization method is proposed.At first，the calculationmethod and error evaluationmodel of unknown node is presented.Then，an evaluation algorithm SFLL is proposed by shuffled frog leaping.At last，amathematic simulation is conducted.Compared to the performances of other algorithms，the results show that SFLL has better adaptability.

wireless sensor network；localization；Least Squares；Shuffled Frog Leaping

TP393

A

1673-1549（2014）04-0034-04

10.11863／j.suse.2014.04.09

2014-05-05

四川省教育廳重點項目（13ZA0118）；人工智能四川省重點實驗室開放基金項目（2012RYY02）；四川理工學院培育項目（2012PY13）；企業(yè)信息化與物聯(lián)網(wǎng)檢測技術四川省高校重點實驗室項目（2013WYJ01）

江宇波（1982-），男，四川自貢人，助理實驗師，碩士，主要從事計算機網(wǎng)絡通信方面的研究，（E-mail）598256382＠qq.com