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

　　節點(diǎn)定位是實(shí)現傳感器網(wǎng)絡(luò )應用的前提，控制節點(diǎn)定位誤差成為保證網(wǎng)絡(luò )正常運行的關(guān)鍵。采用基于測距的定位算法，可以達到良好的精度，但需要測量裝置，不適合能量受限的無(wú)線(xiàn)傳感器網(wǎng)絡(luò )。本文分析了常用的非測距定位算法，并在此基礎上提出了一種改進(jìn)的基于序列的非測距定位算法，以提高無(wú)線(xiàn)傳感器網(wǎng)絡(luò )定位算法的性能。

　　引言

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

　　目前基于非測距的算法有DVHop（Distance VectorHop）算法［2］、Centroid算法［3］、APIT算法［4］、SBL（SequenceBased Localization）算法［5］。SBL算法是一種利用接收信號強度RSSI來(lái)采集信標節點(diǎn)序列，通過(guò)區域劃分實(shí)現節點(diǎn)定位的非測距定位算法。該算法對比RSSI信號的強弱獲得待定位節點(diǎn)與不同信標節點(diǎn)之間距離的相對大小，具有復雜度低、定位精度高、健壯性強的特點(diǎn)。但是SBL算法不能充分利用一跳范圍以外的信標節點(diǎn)和未知節點(diǎn)的信息等，本文通過(guò)分析一跳范圍以外的節點(diǎn)信息，在相同條件下提高了算法的定位精度，仿真實(shí)驗表明 ASBL（Advanced SequenceBased Localization）算法相對于SBL算法在性能上有大幅的提升。

　　1 模型化

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

　　圖1 區域劃分和求簽名序列

　　兩個(gè)序列之間的匹配相似度采用斯皮爾曼相關(guān)系數［6］（Spearman‘s Rank Order Correlation Coefficient）和肯德?tīng)柕燃壪嚓P(guān)系數［6］（Kendall’s Tau）來(lái)衡量。給定兩個(gè)序列U={ui}和V={vi}，1≤ i≤n，其中n表示信標節點(diǎn)的個(gè)數，ui和vi表示序列中的信標節點(diǎn)的位置。用ρ表示斯皮爾曼相關(guān)系數，用τ表示肯德?tīng)柕燃壪嚓P(guān)系數，則有：

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

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

　　圖2 匹配探測序列完成定位

　　2 ASBL算法

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

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

　　圖3 不同跳數的信標節點(diǎn)之間的中垂線(xiàn)

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

　　圖4 不同跳數的信標節點(diǎn)對定位的幫助

　　3 仿真驗證

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

　　表1 仿真平臺默認參數信息

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

　　本組仿真中，將節點(diǎn)隨機部署，信標節點(diǎn)密度設為10%，節點(diǎn)數量在100～500之間變化，節點(diǎn)通信半徑覆蓋不規則度為0，其余參數保持不變。通過(guò)圖5可以看出，隨著(zhù)節點(diǎn)密度的增大，各算法定位精度都有所提升，當節點(diǎn)達到400個(gè)時(shí)，各算法性能趨于穩定。因為能夠使用一跳范圍外的信標節點(diǎn)和未知節點(diǎn)協(xié)助定位，ASBL算法定位精度比DV-Hop算法提高25%左右，比APIT算法提高15%左右，比SBL算法提高12%。

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

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

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

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

　　結語(yǔ)

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