一種改進(jìn)的無線傳感器網(wǎng)絡(luò)非測(cè)距定位算法

付松濤，楊愛玲，高鎮(zhèn)，郭振乾

（1.中國(guó)人民解放軍61655部隊(duì)；2.中國(guó)人民解放軍61936部隊(duì)；3.四川大學(xué)）

引 言

無線傳感器網(wǎng)絡(luò)具有部署靈活、便于信息獲取和傳輸?shù)忍卣鱗1]，得到大量應(yīng)用。由于無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)一般采用低功耗設(shè)置以解決長(zhǎng)時(shí)工作狀態(tài)下能量補(bǔ)給困難的問題，其節(jié)點(diǎn)定位技術(shù)不同于全球衛(wèi)星定位系統(tǒng)（Global Positioning System，GPS）定位技術(shù)。如果采用基于測(cè)距的定位算法，可以達(dá)到良好的精度，但要求額外的物理測(cè)量設(shè)備，硬件成本和功耗偏高，不適合于大規(guī)模無線傳感器網(wǎng)絡(luò)?；诜菧y(cè)距的定位算法，由于不需要測(cè)量傳感器節(jié)點(diǎn)之間的物理距離或角度，在實(shí)際中具有更佳的實(shí)用性，因此成為研究熱點(diǎn)。

目前基于非測(cè)距的算法有DV-Hop（Distance Vector-Hop）算法[2]、Centroid 算法[3]、APIT 算法[4]、SBL（Sequence-Based Localization）算法[5]。SBL算法是一種利用接收信號(hào)強(qiáng)度RSSI來采集信標(biāo)節(jié)點(diǎn)序列，通過區(qū)域劃分實(shí)現(xiàn)節(jié)點(diǎn)定位的非測(cè)距定位算法。該算法對(duì)比RSSI信號(hào)的強(qiáng)弱獲得待定位節(jié)點(diǎn)與不同信標(biāo)節(jié)點(diǎn)之間距離的相對(duì)大小，具有復(fù)雜度低、定位精度高、健壯性強(qiáng)的特點(diǎn)。但是SBL算法不能充分利用一跳范圍以外的信標(biāo)節(jié)點(diǎn)和未知節(jié)點(diǎn)的信息等，本文通過分析一跳范圍以外的節(jié)點(diǎn)信息，在相同條件下提高了算法的定位精度，仿真實(shí)驗(yàn)表明ASBL（Advanced Sequence-Based Localization）算法相對(duì)于SBL算法在性能上有大幅的提升。

1 模型化

在無線傳感器網(wǎng)絡(luò)中，節(jié)點(diǎn)分為兩類：信標(biāo)節(jié)點(diǎn)和未知節(jié)點(diǎn)。信標(biāo)節(jié)點(diǎn)所占比例較小，可以獲知自身的精確位置，未知節(jié)點(diǎn)利用信標(biāo)節(jié)點(diǎn)的位置信息通過某種算法來確定自身位置。如圖1所示，區(qū)域中有A、B、C三個(gè)信標(biāo)節(jié)點(diǎn)，在A和C中垂線的上側(cè)區(qū)域中任意一點(diǎn)與A、C的距離關(guān)系為DA＜DC，同理在中垂線下側(cè)區(qū)域有DC＜DA。不同的中垂線相互交叉把網(wǎng)絡(luò)所在區(qū)域分割成更小的獨(dú)立區(qū)域，每個(gè)獨(dú)立區(qū)域到信標(biāo)節(jié)點(diǎn)的距離排序是唯一的，這個(gè)排序序列稱為該獨(dú)立區(qū)域的簽名序列。如果一個(gè)待定位節(jié)點(diǎn)在DB＜ DA∩DB＜ DC∩DA＜ DC區(qū)域中通過RSSI測(cè)量各個(gè)信標(biāo)節(jié)點(diǎn)的信號(hào)強(qiáng)度，那么得到的信號(hào)強(qiáng)度應(yīng)該是SB＞SA＞SC，待定位節(jié)點(diǎn)認(rèn)為自己測(cè)得的定位序列為B-A-C。

圖1 區(qū)域劃分和求簽名序列

兩個(gè)序列之間的匹配相似度采用斯皮爾曼相關(guān)系數(shù)[6]（Spearman＇s Rank Order Correlation Coefficient）和肯德爾等級(jí)相關(guān)系數(shù)[6]（Kendall＇s Tau）來衡量。給定兩個(gè)序列 U＝｛ui｝和 V＝｛vi｝，1≤i≤n，其中n表示信標(biāo)節(jié)點(diǎn)的個(gè)數(shù)，ui和vi表示序列中的信標(biāo)節(jié)點(diǎn)的位置。用ρ表示斯皮爾曼相關(guān)系數(shù)，用τ表示肯德爾等級(jí)相關(guān)系數(shù)，則有：

其中，nc表示兩個(gè)序列中先后順序一致的節(jié)點(diǎn)對(duì)的數(shù)目，nd表示兩個(gè)序列中先后順序不一致的節(jié)點(diǎn)對(duì)的數(shù)目，ntu和ntv分別表示兩個(gè)序列的內(nèi)部關(guān)系數(shù)。

ρ和τ的值都介于-1和1之間。兩個(gè)完全相同序列的ρ和τ的值為1，完全不相關(guān)的兩個(gè)序列的ρ和τ的值為0，兩條相逆的序列的ρ和τ的值為-1。SBL算法取ρ和τ值最大的序列作為匹配序列。如圖2所示，待定位節(jié)點(diǎn)通過式（1）的匹配算法與“簽名序列表”中的序列進(jìn)行匹配，可以得出自己所在的區(qū)域，以該區(qū)域的質(zhì)心作為自己的坐標(biāo)。

圖2 匹配探測(cè)序列完成定位

2 ASBL算法

ASBL算法的待定位節(jié)點(diǎn)只能接收到通信半徑范圍內(nèi)的信標(biāo)節(jié)點(diǎn)的RSSI值，無法充分利用通信半徑外的信標(biāo)節(jié)點(diǎn)信息來定位。當(dāng)網(wǎng)絡(luò)中信標(biāo)節(jié)點(diǎn)增多時(shí)，理論上被分割區(qū)域并沒有發(fā)揮作用。

如圖3所示，S表示待定位節(jié)點(diǎn)，最中心的虛線范圍表示S經(jīng)過RSSI序列進(jìn)行初步定位之后可能的待定位區(qū)域。A表示在S通信范圍內(nèi)的信標(biāo)節(jié)點(diǎn)，B表示2跳范圍的信標(biāo)節(jié)點(diǎn)，C和D表示三跳范圍的信標(biāo)節(jié)點(diǎn)。分別做AB、AC和AD之間的平分線，AB和AC之間的平分線穿越S的待定位區(qū)域，能夠縮小待定位區(qū)域的面積，當(dāng)信標(biāo)節(jié)點(diǎn)D位于三跳范圍邊緣時(shí)，AD之間的平分線剛好與待定位區(qū)域的邊緣相切，未能穿越待定位區(qū)域。因此，在均勻分布的網(wǎng)絡(luò)中，距離待定位節(jié)點(diǎn)跳數(shù)越小的信標(biāo)節(jié)點(diǎn)對(duì)于待定位節(jié)點(diǎn)的定位幫助越大，隨著跳數(shù)的增加，三跳范圍以外的的信標(biāo)節(jié)點(diǎn)不能對(duì)待定位節(jié)點(diǎn)的定位提供有用的位置信息。在實(shí)際中，待定位節(jié)點(diǎn)發(fā)出的定位詢問信息的跳數(shù)上限設(shè)置為6即可，既能最大化地利用多跳信標(biāo)節(jié)點(diǎn)的位置信息，又不會(huì)消耗過多的能量用于通信。

圖3 不同跳數(shù)的信標(biāo)節(jié)點(diǎn)之間的中垂線

如圖4所示，一跳的信標(biāo)節(jié)點(diǎn)能給待定位節(jié)點(diǎn)提供大致的待定位區(qū)域，二跳信標(biāo)節(jié)點(diǎn)一般情況下能將待定位區(qū)域的面積縮小75%左右，三跳及三跳以外的信標(biāo)節(jié)點(diǎn)能在二跳的基礎(chǔ)上繼續(xù)將待定位區(qū)域面積縮小20%左右。

圖4 不同跳數(shù)的信標(biāo)節(jié)點(diǎn)對(duì)定位的幫助

3 仿真驗(yàn)證

本文使用Java語言開發(fā)了一個(gè)仿真平臺(tái)，分析檢驗(yàn)ASBL算法的各種性能指標(biāo)。設(shè)置傳感器節(jié)點(diǎn)隨機(jī)部署在200 m×200 m的區(qū)域內(nèi)，節(jié)點(diǎn)的通信半徑默認(rèn)為30 m，表1中的數(shù)據(jù)是仿真平臺(tái)的各項(xiàng)參數(shù)信息。

表1 仿真平臺(tái)默認(rèn)參數(shù)信息

3.1 節(jié)點(diǎn)密度對(duì)定位精度的影響

本組仿真中，將節(jié)點(diǎn)隨機(jī)部署，信標(biāo)節(jié)點(diǎn)密度設(shè)為10%，節(jié)點(diǎn)數(shù)量在100～500之間變化，節(jié)點(diǎn)通信半徑覆蓋不規(guī)則度為0，其余參數(shù)保持不變。通過圖5可以看出，隨著節(jié)點(diǎn)密度的增大，各算法定位精度都有所提升，當(dāng)節(jié)點(diǎn)達(dá)到400個(gè)時(shí)，各算法性能趨于穩(wěn)定。因?yàn)槟軌蚴褂靡惶秶獾男艠?biāo)節(jié)點(diǎn)和未知節(jié)點(diǎn)協(xié)助定位，ASBL算法定位精度比DV-Hop算法提高25%左右，比APIT算法提高15%左右，比SBL算法提高12%。

圖5 節(jié)點(diǎn)密度對(duì)定位精度的影響

3.2 節(jié)點(diǎn)通信半徑對(duì)定位精度的影響

設(shè)置節(jié)點(diǎn)總數(shù)為300個(gè)，信標(biāo)節(jié)點(diǎn)密度為10%，節(jié)點(diǎn)通信半徑從10～50 m遞增，其余參數(shù)按照默認(rèn)設(shè)置，重復(fù)10次仿真。由圖6可以看出，通信半徑為10 m時(shí)，ASBL算法的定位精度要比SBL算法高75%，這是因?yàn)锳SBL能充分利用一跳范圍外的信標(biāo)節(jié)點(diǎn)。通信半徑為50 m時(shí)，ASBL算法的定位精度比SBL算法僅高1.4%，這是因?yàn)楫?dāng)節(jié)點(diǎn)通信半徑增加時(shí)，原來位于一跳范圍外的信標(biāo)節(jié)點(diǎn)此時(shí)會(huì)位于一跳范圍內(nèi)。

圖6 節(jié)點(diǎn)通信半徑對(duì)定位精度的影響

結(jié) 語

非測(cè)距的定位技術(shù)以所需傳感器節(jié)點(diǎn)能量少、硬件簡(jiǎn)單，成為目前無線傳感器網(wǎng)絡(luò)定位技術(shù)的主要研究方向。本文提出了ASBL算法，針對(duì)SBL算法作了改進(jìn)，以提高算法良好的適應(yīng)性和健壯性。恰當(dāng)?shù)亩ㄎ凰惴ㄊ菬o線傳感器網(wǎng)絡(luò)正常工作的基礎(chǔ)，針對(duì)非測(cè)距定位算法的研究將會(huì)朝著降低能量消耗和提高定位精度的方向發(fā)展，從而極大地提高網(wǎng)絡(luò)的生存能力和工作效率。

[1]Bin Duan，Guojing Li，Chaowu Qiu，et al.Fault location and self-healing of distribution network based on function block and wireless sensor[J].Innovative Smart Grid Technologies（ISGT），2012（1）：16-20.

[2]Ying Zhou，Baojian Gao，Tianzhang Xing，et al.Improvement on Localization Error and Adaptability in DV-Hop Algorithm[C]//6th China Conference，CWSN 2012：725-733.

[3]Bulusu N，Heidemann J，Estrin D.GPS-less low cost outdoor localization for very small devices[J].IEEE Personal Communications，2008，7（5）：28-34.

[4]He T，Huang C，Blum B M，et al.Range-free localization schemes for large scale sensor networks[C]//Proc 9th Annual Int＇1 Conf on Mobile Computing and Networking（Mobi-Com），San Diego，CA，2003：81-85.

[5]Krishnamachari，Bhaskar.Sequence-Based Localization in Wireless Sensor Networks[J].Mobile Computing，IEEE Transactions，2008（7）：81-94.

[6]W H Press，B P Flannerly，S A Teukolsky，et al.Vetterling：The Art of Scientific Computing[M].Second edition.England：Cambridge UnivPress，1992.