基于估距方式分類的無線傳感器網(wǎng)絡(luò)定位算法*

黃智勇 張欣

(重慶大學(xué) 通信工程學(xué)院，重慶 400044)

定位技術(shù)是無線傳感器網(wǎng)絡(luò)的應(yīng)用基礎(chǔ)問題之一.在其定位模型中，通常將節(jié)點分為錨點(或稱為信標(biāo)節(jié)點，具有自主定位能力的節(jié)點)和未知節(jié)點(它們通過獲取錨點的相關(guān)信息來確定自己的位置)［1］.現(xiàn)有針對傳感器網(wǎng)絡(luò)的定位算法大致可以分為基于測距的算法和無需測距的算法兩類.由于無需測距的算法僅根據(jù)網(wǎng)絡(luò)連通性就可以實現(xiàn)定位，因此該類算法具有抗干擾能力強、硬件成本低等優(yōu)點，其中距離矢量跳距(DV-Hop)算法是無需測距算法的典型代表［2-3］.

DV-Hop 算法用平均跳距與錨節(jié)點間最小跳數(shù)的乘積來近似表示未知節(jié)點到錨節(jié)點的距離［3］.由于未知節(jié)點受地形、環(huán)境和氣候等因素的影響，故其分布不均勻，導(dǎo)致估距計算存在較大的誤差，使定位精度下降;平均每跳距離存在一定的誤差，當(dāng)未知節(jié)點到錨點間的跳數(shù)較大時，誤差的累計效應(yīng)會使定位精度進一步降低.

為提高DV-Hop 算法的定位精度，文獻［4-5］中使用接收信號強度作為定位的輔助條件，但增加了硬件成本;文獻［6］中提出了針對三邊定位法的錨點篩選依據(jù)，但該方法直接忽略某些不滿足條件的錨點，故不能有效利用這些錨點信息;文獻［7-8］中提出了跳距加權(quán)的方法以提高定位精度;文獻［9-10］從優(yōu)化通信半徑和錨點部署的角度來提高定位精度;文獻［11］中提出了基于最小二乘法的等比例映射的定位方法，通過構(gòu)建虛擬錨點來增加定位精度，但此方法對錨點與未知節(jié)點的分布有一定的要求.根據(jù)文獻［12-13］中對未知節(jié)點進行分類處理的思想和文獻［15-16］中的加權(quán)思想，文中提出了基于估距方式分類的無線傳感器網(wǎng)絡(luò)定位算法.

1 改進的DV-Hop 算法

針對傳統(tǒng)DV-Hop 算法在估算距離時因存在較大誤差而導(dǎo)致定位精度不高的問題，文中做了如下改進:①引入最優(yōu)輔助估距錨點，并將距離估算分為3 類分別計算，以提高估距精度;②在三邊定位法中引入“非線性－跳數(shù)”加權(quán)因子，使用該因子對估計坐標(biāo)進行加權(quán)處理以解決三邊定位法容易產(chǎn)生鏡像坐標(biāo)的問題.

1.1 估距方式的改進

從統(tǒng)計規(guī)律和文獻［12］的論述可知，當(dāng)某個未知節(jié)點處于兩錨點間的最小跳數(shù)路徑上時，使用這兩個錨點間的平均跳數(shù)來計算這個未知節(jié)點到兩個錨點間的估計距離，所得到的結(jié)果更為準(zhǔn)確.因此，文中依據(jù)能否尋找到一個錨點，使得它與待估距錨點間的最小跳數(shù)路徑完全包含或者部分包含當(dāng)前所需估算的距離來對估距方式進行分類，使未知節(jié)點能夠針對當(dāng)前所需估算的距離選擇與之相關(guān)的平均每跳距離，從而減小估距誤差.如圖1 所示，A(i)、A(j)、A(k)為3 個 錨 點，S(p)、S(q)、S(t)、S(l)、S(r)為5 個未知節(jié)點，連接線長度表示實際跳距，p為未知節(jié)點的ID，i 和j 分別為錨點的ID，則可用HNp，i表示未知節(jié)點S(p)到錨點A(i)的最小跳數(shù)，p，i表示S(p)到錨點A(i)的估計距離，HNj，i表示兩錨點A(i)與A(j)間的最小跳數(shù)，di，j表示A(i)與A(j)間的實際距離，并有如下3 種估距方式.

圖1 錨節(jié)點分布示意圖Fig.1 Schematic diagram of distribution of anchor and unknown nodes

(1)類型I.未知節(jié)點S(t)需要估算其與錨點A(i)間的距離.觀察圖1 可以發(fā)現(xiàn)，S(t)在錨點A(i)與A(j)間以及A(i)與A(k)間的最小跳數(shù)路徑上.依據(jù)經(jīng)驗法則、兩錨點間的跳數(shù)越小則兩點間的線性度越好［12］，以及錨點間的已知直線距離及最小跳數(shù)路徑可作為估計距離的相關(guān)約束條件［13］，文中采用如下更能準(zhǔn)確反映S(t)到A(i)的平均每跳距離:

(2)類型II.當(dāng)前需要測量S(r)到A(i)間的距離，但不存在任何一個錨點使得S(r)在A(i)與該錨點間的最小跳數(shù)路徑上，即不滿足估距方式I 的要求.觀察圖1 可知，S(r)到A(i)間的跳數(shù)由兩部分組成，即HNr，i=HNr，j+ HNj，i，若以HSi，j作為平均跳距，則在式(1)等號兩邊同時乘以HSi，j，可得

將di，j=HNj，iHSi，j代入式(2)可得

而兩錨點間的距離di，j可由錨點A(i)與A(j)的坐標(biāo)直接得出，不受A(i)與A(j)間未知節(jié)點的分布的影響.這樣可以極大地減少由平均每跳距離產(chǎn)生的誤差累計效應(yīng).根據(jù)文獻［13］，由于未知節(jié)點S(r)不位于A(i)與A(j)之間的最小跳數(shù)路徑上，故式(3)中的HSi，j無法反映S(r)到A(j)的每跳距離.實際上未知節(jié)點S(r)不位于圖中任何兩錨點間的最小跳數(shù)路徑上，任意兩錨點間的每跳距離與S(r)到A(j)的跳距不相關(guān).為了盡量減小估算距離的均方誤差，文中引入全局每跳距離作為未知節(jié)點S(r)到錨點A(j)的平均每跳距離，即

式中，As為錨點ID 的集合，當(dāng)i=j 時，di，j= 0，HNi，j=0.從文獻［15］的論述及統(tǒng)計學(xué)的角度分析，使用全局每跳距離的好處是:用盡量多的樣本信息去估計未知參數(shù)的平均值，以降低均方誤差.故未知節(jié)點S(r)到錨點A(i)的估計距離可表示為

此時稱A(j)為估算S(r)到A(i)間距離時的類型II最優(yōu)輔助估距錨點.由此可得類型II 估距方式的核心思想:當(dāng)不滿足類型I 的估距條件時，尋找輔助估距錨點，使得該錨點處于未知節(jié)點與待估距錨點間的最小跳數(shù)路徑上，這樣就可以利用該錨點和待估距錨點間的已知直線距離.同樣地，當(dāng)存在多個滿足該條件的錨點時，應(yīng)當(dāng)選擇與未知節(jié)點跳數(shù)最小的錨點作為類型II 的最優(yōu)輔助估距錨點.當(dāng)不存在這樣的錨點時，直接進行類型III 的估距計算.

(3)類型III.如圖1 所示，當(dāng)估算未知節(jié)點S(q)到錨點A(i)間的距離時，q，i均不滿足類型I 與II 的估距條件.實際上未知節(jié)點S(p)、S(l)、S(q)的存在與否對任意錨點的平均跳距均不產(chǎn)生影響.故任意兩錨點間的平均跳距均不能有效表示S(q)到A(i)間的跳距.因此直接使用全局平均每跳距離進行類型III的距離估算，即

可以看出，類型III 的節(jié)點分布是排除類型I、II后其他分布情況的總和，故3 種估距方式對所有可能的分布情況進行了歸納，任意節(jié)點的任意一次估距計算均可歸納為其中的一種.則ID 為x 的未知節(jié)點到ID 為y 的錨點間的估計距離可表示為

結(jié)合式(1)、(4)可求得S(x)到A(y)間的估計距離.需要指出的是:為了實現(xiàn)文中所提出的估距分類方法，每個錨點既要向網(wǎng)絡(luò)中發(fā)送各自的位置坐標(biāo)，又要發(fā)送該錨點到其他錨點的最小跳數(shù)表，故會增加一定的通信開銷.ID 為i 的錨點發(fā)送的跳數(shù)表見表1.

表1 錨點A(i)發(fā)送的跳數(shù)表Table 1 Hop table sended by anchor A(i)

1.2 非線性－跳數(shù)加權(quán)

如圖2 所示，未知節(jié)點S(a)通過式(6)可以分別獲得它到錨點A(p)、A(i)、A(j)間的估算距離，將其與錨點的坐標(biāo)代入三邊定位方程組:

通過極大似然法可以求得基于錨點A(p)、A(i)、A(j)的S(a)的一個估計坐標(biāo)(，).式(7)中的(x1，y1)、(x2，y2)、(x3，y3)分別為3 個錨點的坐標(biāo)，1、2、3分別為未知節(jié)點與3 個錨點的估計距離.重復(fù)上述過程可得到S(a)在不同錨點下的所有估計坐標(biāo).通常將它們的平均值作為最終的估計坐標(biāo).但當(dāng)S(a)選擇圖2 中的錨點A(i)、A(j)、A(k)時，由于它們基本上在同一條直線上，這時通過極大似然法求解，可得到圖2 中S(a)關(guān)于直線L 對稱的S(a')的坐標(biāo)，這會對最終結(jié)果產(chǎn)生較大的影響.為此，文獻［15］中提出了將3 個錨點間的角度作為非線性加權(quán)因素.另一方面，未知節(jié)點到這3 個錨點的跳數(shù)和越大，誤差的累計效應(yīng)越明顯;對比S(a')與S(b')可知，未知節(jié)點到這3 個錨點的跳數(shù)之和在一定程度上能反映鏡像坐標(biāo)間的距離.顯然，鏡像坐標(biāo)間的距離越大，誤差越嚴(yán)重，故未知節(jié)點到3 個錨點間的跳數(shù)之和也可以作為該坐標(biāo)加權(quán)的一個因素.

圖2 鏡像坐標(biāo)示意圖Fig.2 Schematic diagram of mirror coordinate

結(jié)合文獻［15］的非線性加權(quán)，文中提出了“非線性－跳數(shù)”加權(quán)因子.未知節(jié)點μ 由ID 為x1、x2、x3的錨點所估算得到的坐標(biāo)對應(yīng)的權(quán)值可表示為

式中，θ 為由錨點A(a)、A(b)、A(c)組成的三角形的最小內(nèi)角， 表示未知節(jié)點的ID，為未知節(jié)點S()到這3 個錨點的跳數(shù)之和.對于同一個未知節(jié)點，為所有加權(quán)值的總和，將該值作為分母，實際上是進行歸一化處理.這樣可使得所有“非線性－跳數(shù)”加權(quán)因子的總和為1.由前面分析可知，當(dāng)3 個錨點連線近似呈直線時，容易產(chǎn)生鏡像坐標(biāo)，而此時由這3 個錨點組成的三角形的最小內(nèi)角θ 相應(yīng)減小，式(9)中加權(quán)因子的分子(1- cosθ)也減小，故對應(yīng)坐標(biāo)的權(quán)值變小，這樣就能減小鏡像坐標(biāo)對最終估計坐標(biāo)的影響.當(dāng)θ 相同時，依據(jù)文獻［12］，未知節(jié)點到錨點間的跳數(shù)越小，估距精度越準(zhǔn)確，此時對應(yīng)式(9)中的分母越小，相應(yīng)權(quán)值越大，說明未知節(jié)點估計坐標(biāo)的可信度與權(quán)值的變 化 一 致.若表 示 由 錨 點A(i)、A(j)、A(k)估算的坐標(biāo)，則加權(quán)因子w(x，i，j，k)表征了該坐標(biāo)的可信度.最終未知節(jié)點μ 的估計坐標(biāo)可表示為

1.3 算法流程

文中提出的改進DV-Hop 算法流程如圖3 所示.

圖3 改進DV-Hop 算法流程圖Fig.3 Flowchart of modified DV-Hop algorithm

2 仿真實驗分析

為驗證文中算法的定位性能，以Matlab 2010b為仿真平臺進行仿真實驗，并選取邊長為100 m 的二維平面正方形空間作為無線傳感器網(wǎng)絡(luò)的定位區(qū)域，未知節(jié)點完全隨機分布在此區(qū)域中.未知節(jié)點和錨點的總數(shù)N、節(jié)點間的通信半徑R、錨點數(shù)Na等依據(jù)不同的實驗?zāi)康挠胁煌脑O(shè)置.參考文獻［8，13］的計算方法，文中取絕對定位誤差e 和歸一化定位誤差e 的計算公式如下:

式中，M 為實驗次數(shù)，(xi，k，yi，k)和分別為第k 次分布下ID 為i 的節(jié)點的實際坐標(biāo)和最終估計坐標(biāo).

當(dāng)N=150、Na=16、R=15 m 時節(jié)點的實際分布情況如圖4 所示.使用文中算法進行定位計算，結(jié)果如圖5 所示.對比圖4、5 中隨機選取的13 個未知節(jié)點(以▲表示)的位置，可以看出文中算法能夠有效地實現(xiàn)傳感器網(wǎng)絡(luò)的定位.依據(jù)式(10)和(11)計算，得到絕對定位誤差為4.8 m，歸一化定位誤差為0.32.

當(dāng)R=15 m、N=150、K=50 時采用文中算法、文獻［8］算法、DV-Hop 算法［10］及NDV-Hop 算法［6］進行實驗.針對同一次節(jié)點分布情況，選取不同的錨點個數(shù)依次計算4 種算法的歸一化定位誤差.由于錨點分布對定位精度有一定的影響，因此本實驗將錨點的分布分為等間隔理想分布和引入隨機誤差的理想分布.不同錨點數(shù)下4 種算法的歸一化定位誤差如圖6 所示.從圖中可以看出:隨著錨點數(shù)的增加，歸一化定位誤差基本上呈下降趨勢，文中算法的平均定位誤差小于其他3 種算法;優(yōu)化錨點分布可以提高定位精度.

圖6 錨點個數(shù)與歸一化誤差的關(guān)系Fig.6 Relationship between number of anchor and normalization error

當(dāng)N=150、K=20 時不同通信半徑下文中算法的絕對定位誤差如圖7 所示.從圖中可以看出，絕對定位誤差隨通信半徑的增大而上升，通信半徑相同時，錨點數(shù)決定了定位精度.從理論上分析，隨著通信半徑的增大，節(jié)點間的跳數(shù)有所減少，平均每跳距離有所增大，估距的分辨率有所降低，因此定位誤差有所增大，這和實驗結(jié)果一致.但通信半徑不能過小，通信半徑與接收到錨點信息的未知節(jié)點所占比例δ的關(guān)系如圖8 所示.從圖中可以看出，當(dāng)通信半徑小于15 m 時，不能保證所有未知節(jié)點均能收到錨點的廣播信息，這將導(dǎo)致無法定位某些未知節(jié)點.因此，在定位區(qū)域和錨節(jié)點數(shù)一定的條件下，選取通信半徑是一個優(yōu)化問題.對于本實驗的分布模型，R=15 m可以認(rèn)為是一個最優(yōu)解.

當(dāng)R=15 m、N=150、Na=16、K=10 時采用文中算法進行實驗，在定位過程中，3 種估距方式所占的比例分別為29%、37%、34%，估距誤差ed分別為0.18、0.22、0.31，其中ed的計算方法如下:

圖7 通信半徑對文中算法定位誤差的影響Fig.7 Effect of communication radius on location error of the proposed algorithm

圖8 通信半徑與接收到錨點信息的未知節(jié)點數(shù)的關(guān)系Fig.8 Relationship between communication radius and number of unknown nodes received anchor information

3 結(jié)語

通過分析DV-Hop 算法在估距時產(chǎn)生誤差的原因，文中提出了基于估距方式分類的無線傳感器網(wǎng)絡(luò)定位算法，并結(jié)合“非線性－跳數(shù)”加權(quán)因子進一步減小估距誤差，最后通過Matlab 仿真驗證了文中算法的定位性能.隨著錨點數(shù)的增加，定位所需的通信開銷和計算量將大幅增加.如何在保證定位精度的同時減少通信量和計算量，將是今后研究的重點.

［1］Li Shiwei，Yang Guoyan.Introduction to wireless sensor network node location algorithms and multi-path robustness［C］∥Proceedings of the 7th International Conference on Information Technology and Application.Sydney:ICITA，2011:102-104.

［2］Guo Jianquan，Zhao Wei.An anchor free location algorithm for large scale wireless sensor networks［C］∥Proceedings of 2008 IEEE/ASME International Conference on Mechatronics and Embedded Systems and Applications.Beijing:IEEE，2008:7-12.

［3］Kumar Shrawan，Lobiyal D K.An advanced DV-Hop localization algorithm for wireless sensor networks ［J］.Wireless Personal Communications，2013，71(2):1365-1385.

［4］Wu Chengdong，Chen Shifeng，Zhang Yunzhou，et al.A RSSI-based probabilistic distribution localization algorithm for wireless sensor network［C］∥Proceedings of the 6th IEEE Joint International Conference on Information Technology and Artificial Intelligence.Chongqing:IEEE，2011:333-337.

［5］張愛清，葉新榮，胡海峰，等.基于RSSI 每跳分級和跳距修正的DV-HOP 改進算法［J］.儀器儀表學(xué)報，2012，33(11):2552-2559.Zhang Ai-qing，Ye Xin-rong，Hu Hai-feng，et al.Improved DV-HOP positioning algorithm based on one-hop subdivision and average hopping distance modification［J］.Chinese Journal of Scientific Instrument，2012，33 (11):2552-2559.

［6］Liu Jicheng，Wang Wenxiu，Shang Yintong.An improved localization algorithm for wireless sensor network based on DV-Hop［C］∥Proceedings of 2012 International Conference on Measurement，Information and Control.Harbin:IEEE，2012:511-515.

［7］Lu Qingling，Bai Mengliang，Zhang Wei.A new kind of NDV-Hop algorithm in wireless sensor network ［C］∥Proceedings of 2011 International Conference on Network Computing and Information Security.Guilin:IEEE，2011:438-441.

［8］劉峰，張翰，楊驥.一種基于加權(quán)處理的無線傳感器網(wǎng)絡(luò)平均跳距離估計算法［J］.電子與信息學(xué)報，2008，30(5):1222-1225.Liu Feng，Zhang Han，Yang Yi.An average one-hop distance estimation algorithm based on weighted disposal in wireless sensor networks［J］.Journal of Electronics and Information Technology，2008，30(5):1222-1225.

［9］Zheng Yousi，Wan Lei，Sun Zhi.A long range DV-Hop localization algorithm with placement strategy in wireless sensor networks ［C］∥Proceedings of the 4th International Conference on Wireless Communications Networking and Mobile Computing.Avignon:IEEE，2008:4090-4094.

［10］吳玉成，李江雯.基于最優(yōu)節(jié)點通信半徑的改進DVHop 定位算法［J］.華南理工大學(xué)學(xué)報:自然科學(xué)版，2012，40(6):36-42.Wu Yu-cheng，Li Jiang-wen.Improved DV-Hop localization algorithm based on optimal communication radius of nodes［J］.Journal of South China University of Technology:Natural Science Edition，2012，40(6):36-42.

［11］Li Bing，He Yigang，Guo Fengming，et al.A novel localization algorithm based on isomap and partial least squares for wireless sensor networks ［J］.Instrumentation and Measurement，2013，62(2):304-314.

［12］XiaoQingjun，Xiao Bin，Cao Jiannong，et al.Multihop range-free localization in anisotropic wireless sensor networks:a pattern-driven scheme［J］.IEEE Transactions on Mobile Computing，2010，9(11):1592-1607.

［13］朱敏，劉昊霖，張志宏，等.一種基于DV-Hop 改進的無線傳感器網(wǎng)絡(luò)定位算法［J］.四川大學(xué)學(xué)報:工程科學(xué)版，2012，44(1):93-98.Zhu Min，Liu Hao-lin，Zhang Zhi-hong，et al.An improved localization algorithm based on DV-Hop in WSN［J］.Journal of Sichuan University:Engineering Science Edition，2012，44(1):93-98.

［14］Yao Ge，Zhang Jie，Yao Sufen.Research of node location algorithm in wireless sensor network ［J］.Advances in Intelligent and Soft Computing，2011，129(2):309-313.

［15］Xiang Shu，Zhang Yun-zhou，Xia Zhi-jia，et al.An improved DV-Hop localization algorithm using residual weight in wireless sensor network［J］.Journal of Computational Information Systems，2012，8(15):6357-6364.

［16］Tan Lixiong，Luo Fei，Liu Kai.Weighted centroid location algorithm in wireless sensor network［C］∥Proceedings of IET International Communication Conference on Wireless Mobile and Computing.Shanghai:IEEE，2011:414-418.