江宇波，趙攀，邱玲

（四川理工學(xué)院計(jì)算機(jī)學(xué)院，四川自貢643000）

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

江宇波，趙攀，邱玲

（四川理工學(xué)院計(jì)算機(jī)學(xué)院，四川自貢643000）

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

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

引言

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

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

1 節(jié)點(diǎn)定位方法

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

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

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

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

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

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

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

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

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

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

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

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

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

2 算法描述

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

其約束條件為：

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

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

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

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

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

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

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

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

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

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

3 仿真實(shí)驗(yàn)

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

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

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

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

4 結(jié)束語(yǔ)

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

［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)絡(luò)定位精度優(yōu)化方法研究［D］.南京：南京郵電大學(xué),2013.

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

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

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

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

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

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

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

［10］葛宇,王學(xué)平,梁靜.基于蛙跳算法的DV-Hop定位改進(jìn)［J］.計(jì)算機(jī)應(yīng)用,2011,31（4）：922-924.

［11］葛宇,梁靜,許波,等.基于蛙跳算法的無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位［J］.計(jì)算機(jī)工程與應(yīng)用,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

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

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