劉 洋,高美鳳
(江南大學 物聯(lián)網(wǎng)工程學院 輕工過程先進控制教育部重點實驗室,江蘇 無錫 214122)
在現(xiàn)有比較典型的基于非測距的定位算法[1]中,加權質(zhì)心定位(weighted centroid localization,WCL)算法[2,3]易于實現(xiàn),且計算較為簡單,但缺陷是:為了達到較高的定位精度,往往需要在網(wǎng)絡內(nèi)布設大量的錨節(jié)點,造成硬件成本增加,限制了算法的應用。文獻[4]提出了在加權因子中引入修正系數(shù)來提高定位精度。文獻[5]根據(jù)節(jié)點間的不同距離,采用不同的權重系數(shù),進一步提高了定位精度。文獻[6]提出了對加權質(zhì)心定位算法的接收信號強度指示(received signal strength indication,RSSI)距離值進行差分修正,從消除RSSI誤差角度來減小累積誤差。以上算法需要網(wǎng)絡內(nèi)部署較多數(shù)量的錨節(jié)點,導致了硬件成本增大。文獻[7]利用少量真實錨節(jié)點的定位信息構造出虛擬靜態(tài)錨節(jié)點參與定位,再結合加權質(zhì)心定位算法對未知節(jié)點進行估計。文獻[8]利用單個錨節(jié)點沿DOUBLE-SCAN路線飛行移動并與鄰居節(jié)點進行通信,未知節(jié)點根據(jù)一定的篩選機制并結合簡化的加權質(zhì)心定位算法估計未知節(jié)點坐標。算法雖減少了硬件成本投入,但邊界未知節(jié)點的共線問題未得到很好解決,導致節(jié)點的定位精度偏低。
針對以上問題,本文采用單個移動錨節(jié)點以既定路線遍歷整個無線傳感器網(wǎng)絡的監(jiān)測區(qū)域,在降低投入成本的情況下,對加權質(zhì)心定位算法提出了相應的改進方案,設計了WCL-TRH(WCL-triangle RSSI hop)定位算法,并通過Matlab仿真實驗對比分析了WCL-TRH,WCL,RR-WCL(WCL algorithm based on RSSI ratio)3種算法。
采用單個移動錨節(jié)點,根據(jù)折線方式[9]移動路線的思想,設計了移動路徑,如圖1所示(“·”表示移動錨節(jié)點停留位置,即虛擬錨節(jié)點;“→”表示其移動方向和路徑)。這種移動方式可以達到網(wǎng)絡區(qū)域的盡可能覆蓋,保證了網(wǎng)絡中的未知節(jié)點可以接收到足夠的移動錨節(jié)點位置信息。同時這種三角式移動廣播方式,能夠盡量保證網(wǎng)絡內(nèi)的未知節(jié)點處于至少3個移動位置所構成的多邊形范圍內(nèi)部,有效地避免了邊界節(jié)點共線問題,實現(xiàn)了更好的定位效果。
圖1 移動錨節(jié)點路徑規(guī)劃
移動錨節(jié)點在移動過程中以時間間隔T或拐角處向未知節(jié)點廣播當前位置,動態(tài)地與周圍鄰居未知節(jié)點建立連接關系,繼續(xù)移動,直到遍歷整個網(wǎng)絡。
加權質(zhì)心定位算法的計算公式為
(1)
式中 (xi,yi)為第i個錨節(jié)點的坐標;(x,y)為未知節(jié)點M的坐標;N為未知節(jié)點的鄰居錨節(jié)點個數(shù);wi為第i個錨節(jié)點所對應的權值系數(shù)
(2)
式中di為未知節(jié)點M與第i個錨節(jié)點之間的距離,可通過式(3)無線信號傳播衰減模型[10]求得
(3)
式中RSSI(d)為距離發(fā)射點d處的接收信號強度值;RSSI(d0)為距離d0處的接收信號強度值;λ為路徑衰減因子,易受環(huán)境影響,一般取值范圍在2~4之間;d為未知節(jié)點到錨節(jié)點間的距離,一般情況下取d0=1 m;ζo為正態(tài)隨機變量,標準差為σ。
為抑制環(huán)境對于RSSI值的差異影響[11],文獻[12]提出了RR-WCL算法,采用信號強度比值作為加權值,但僅采用信號強度比值作為權值,并未充分體現(xiàn)出不同位置處虛擬錨節(jié)點對質(zhì)心位置的影響,定位效果不佳。
本文所提出的WCL-TRH算法在采用信號強度比值作為加權值的同時,根據(jù)網(wǎng)絡中每個未知節(jié)點與鄰居虛擬錨節(jié)點之間的最小跳數(shù)信息,對自身位置進行修正。若只采用最小跳數(shù)的倒數(shù)作為修正因子,雖然平均相對定位誤差會降低1 %左右,但也會帶來中心化效應,即定位結果不同程度地偏向于鄰居虛擬錨節(jié)點位置的平均值。由于在小型網(wǎng)絡區(qū)域,節(jié)點的最小跳數(shù)信息差別很小,所以,只采用跳數(shù)的倒數(shù)作為修正因子,降低定位誤差效果不是很明顯。為了擴大最小跳數(shù)對節(jié)點間實際位置的影響程度,結合指數(shù)函數(shù)y=ex,進行修正,擴大最小跳數(shù)的差異影響。
定義Rij為未知節(jié)點M分別從虛擬錨節(jié)點Bj,Bi接收到信號強度比值
(4)
根據(jù)個體差異修正后的權值系數(shù)為
(5)
式中hi為未知節(jié)點M到虛擬錨節(jié)點i的最小跳數(shù)。
由WCL-TRH算法所求得的未知節(jié)點坐標為
(6)
式中
(7)
WCL-TRH算法步驟如下:
1)所有傳感器節(jié)點隨機分布在監(jiān)測區(qū)域后,采用一個移動錨節(jié)點按照規(guī)定的路線移動。在移動的過程中,移動錨節(jié)點在每個三角形路徑的拐點處停留時間T,感知周圍鄰近的未知節(jié)點并廣播數(shù)據(jù)包Message_Loca。數(shù)據(jù)包需包含有自身移動位置坐標(xi,yi)、標號IDi、間隔跳數(shù)值Hops(始化為零)以及信息源標記(source=-1表示由移動錨節(jié)點發(fā)送的信息,source=0表示由未知節(jié)點發(fā)送的信息)
Message_Loca(IDi,(xi,yi),Hops,source)
2)未知節(jié)點根據(jù)接收的移動錨節(jié)點Message_Loca信息,首先測量獲取該信息的接收功率ri,然后記錄與移動位置i的間隔跳數(shù)值Hopsi=Hops+1。如果接收的信息源標記source=-1,一定是未知節(jié)點第一次接收到的信息,無需比較,只需將跳數(shù)加一并將信息源標記改為source=0,然后進行廣播;如果未知節(jié)點接收到的廣播信息是從其他未知節(jié)點轉(zhuǎn)發(fā),那么首先判斷是否第一次接收到位置標記i的信息包,若是,則記錄標號i,并將跳數(shù)進行加一處理;否則,比較曾記錄的跳數(shù)值,保留較小跳數(shù)值對應的標號信息,處理后繼續(xù)廣播。
3)若移動錨節(jié)點在停留當前位置j時,接收到來自未知節(jié)點發(fā)送的數(shù)據(jù)包時,如果是第一次接收到標號為i的信息時,記錄并處理標號為i的跳數(shù)值,同時記錄位置i,j的連通關系;如果不是第一次接收到該標號信息,則與原記錄值進行比較,保留較小跳數(shù)的信息。
4)移動錨節(jié)點沿既定路線移動結束后,監(jiān)測區(qū)域內(nèi)的未知節(jié)點根據(jù)記錄的信號強度值、最小跳數(shù)及相關虛擬錨節(jié)點的位置坐標,進行定位。若接收的虛擬錨節(jié)點數(shù)至少3個,則直接利用式(6)計算未知節(jié)點的估計坐標;若接收到的虛擬錨節(jié)點數(shù)為1或2個,則利用式(8)估算未知節(jié)點坐標
(8)
式中RSSIi為未知節(jié)點接收到的移動錨節(jié)點位于位置i處所接收到的信號強度;(xi,yi)為移動錨節(jié)點處于該位置下的坐標。
利用MATLAB對算法進行仿真實驗以驗證改進算法WCL-TRH的性能。假設在100 m×100 m的正方形區(qū)域內(nèi),隨機布設200個未知節(jié)點,節(jié)點通信半徑為10 m的圓形區(qū)域。
平均相對定位誤差為
(9)
式中m,n分別為虛擬錨節(jié)點和節(jié)點數(shù)量,rest為未知節(jié)點的估計位置,rreal為未知節(jié)點的實際位置,R為節(jié)點的通信半徑。當未知節(jié)點從50增加到300個,比較WCL,RR-WCL和WCL-TRH 3種算法的相對平均定位誤差,如圖2所示。
圖2 相對平均定位誤差
可以發(fā)現(xiàn):WCL的相對平均定位誤差在19.86 %~26.06 %波動;而RR-WCL和WCL-TRH的平均相對定位誤差分別在12.25 %~13.11 %,4.77 %~6.11 %波動,且隨未知節(jié)點數(shù)的增加,相對平均定位誤差總體變化趨勢較為平緩,即未知節(jié)點數(shù)量對RR-WCL和WCL-TRH算法基本無影響;WCL-TRH的定位精度較WCL算法提高了15.09 %~19.95 %,較RR-WCL算法提高了7.00 %~7.48 %。
圖3 節(jié)點相對平均定位誤差標準差
可以看出:WCL,RR-WCL和WCL-TRH算法的標準差整體隨未知節(jié)點數(shù)的增大先減小后趨于穩(wěn)定;WCL-TRH算法的定位誤差標準差明顯低于WCL算法和RR-WCL算法的定位誤差標準差,說明WCL-TRH的穩(wěn)定性要優(yōu)于WCL算法和RR-WCL算法。
在相同的仿真環(huán)境下,改變移動錨節(jié)點的廣播間距,從圖4中可以發(fā)現(xiàn),節(jié)點的相對平均定位誤差隨廣播間距增大而增大。這是由于在網(wǎng)絡區(qū)域內(nèi),移動錨節(jié)點的廣播間距代表了虛擬錨節(jié)點的數(shù)量,廣播間距越小,虛擬錨節(jié)點的數(shù)量越多,定位精度越高;反之則定位精度越低。另外,通過改變移動錨節(jié)點的通信半徑大小,可以發(fā)現(xiàn)當移動錨節(jié)點的廣播間距與其通信半徑相同時,網(wǎng)絡內(nèi)未知節(jié)點的相對平均定位誤差最小。因此,在考慮實際應用成本以及定位精度的情況下,選擇移動錨節(jié)點廣播間距與其通信半徑相當時定位效果最好。
圖4 移動錨節(jié)點廣播間距對相對平均定位誤差影響
相同的仿真環(huán)境下,改變節(jié)點的通信半徑后,節(jié)點的相對平均定位誤差如圖5所示。
圖5 通信半徑對相對平均定位誤差影響
可以看出:當移動錨節(jié)點廣播位置不變時,隨著節(jié)點的通信半徑增加,節(jié)點的相對平均定位誤差逐漸減小。這是由于在一定范圍內(nèi),節(jié)點通信半徑的增大會提高網(wǎng)絡的連通度,使得未知節(jié)點可以接收的移動錨節(jié)點數(shù)據(jù)包數(shù)量增多,其位置也可以越來越趨近于鄰居移動錨節(jié)點位置所構成的多邊形中心,從而使得未知節(jié)點的相對平均定位誤差有所提高。
在不增加硬件資源的前提下,提出了WCL-TRH算法。采用了單個移動錨節(jié)點以既定的合理路徑遍歷整個定位區(qū)域,采用了一種改進的加權系數(shù)計算方法對未知節(jié)點進行定位。在充分考慮了鄰居虛擬錨節(jié)點位置對未知節(jié)點的影響情況下,利用未知節(jié)點的接收信號強度比值以及鄰居虛擬錨節(jié)點間的最小跳數(shù)等信息對未知節(jié)點的位置進行估計。仿真實驗表明:WCL-TRH算法可以得到較小的定位誤差和較高的穩(wěn)定性,且節(jié)約了硬件成本。接下來的工作是移動錨節(jié)點根據(jù)網(wǎng)絡內(nèi)節(jié)點的不同分布情況采用動態(tài)路徑的移動方式對未知節(jié)點進行定位。
[1] 彭 宇,王 丹.無線傳感器網(wǎng)絡定位技術綜述[J].電子測量與儀器學報,2011,25(5):389-399.
[2] Blumenthal J,Grossmann R,Golatowski F,et al. Weighted centroid localization in ZigBee-based sensor networks[C]∥IEEE International Symposium on Intelligent Signal Processing,Spain:IEEE Instrumentation and Measurement Society,2007:1-6.
[3] 王 宇.基于灰度質(zhì)心法的雷達干擾源定位方法研究[J].自動化技術與應用,2016,35(2):63-66.
[4] 張先超,劉興長,張春園.基于次錨節(jié)點的無線傳感器網(wǎng)絡改進加權質(zhì)心定位算法[J].傳感器與微系統(tǒng),2015,34(2):143-146.
[5] Zhao Jijun,Zhao Qingwei,Li Zhihua,et al.An improved weighted centroid localization algorithm based on difference of estimated distances for wireless sensor networks[J].Telecommunication System,2013,5(1):25-31.
[6] 花 超,吉小軍,蔡 萍,等.基于RSSI差分修正的加權質(zhì)心定位算法[J].傳感器與微系統(tǒng),2012,31(5):139-141.
[7] 于海存,石為人,冉啟可,等.基于虛擬靜態(tài)錨節(jié)點的加權質(zhì)心定位算法[J].傳感技術學報,2013,26(9):1276-1283.
[8] 鮑金鳳,游曉鵬.WSNs中移動信標輔助的加權質(zhì)心定位算法[J].計算機技術與發(fā)展,2013,23(10):27-30.
[9] 李瑞雪,房至一,儀婷婷.基于可規(guī)律性移動錨節(jié)點和接收信號強度指示器的改進DV-Hop定位算法及其性能分析[J].吉林大學學報:工學版,2011,41(2):435-441.
[10] Alippi C,Vanini G.Wirsless sensor networks and radio localization:A metrological analysis of the MICA2 received signal strength indicator[C]∥Proceedings of the 29th Annual IEEE International Conference on Local Computer Networks,USA:IEEE Computer Society,2004:572-582.
[11] Rabaey J M,Ammer M J,Silva J L D,et al.Picorodio supports Ad Hoc ultra-low power wireless networking[J].Computer,2000,33(7):42-48.
[12] 楊新宇,孔慶茹,戴湘軍.一種改進的加權質(zhì)心定位算法[J].西安交通大學學報,2010,44(8):1-4.
[13] Rezazadeh J,Moradi M,Ismail A S,et al.Impact of static trajectories on localization in wireless sensor networks[J].Wireless Networks,2015(3):809-827.