無線傳感器網絡節點定位與漂移檢測

畢 燁，陳麗娜，苗春雨

1(吉林師范大學 分院 現代教育技術中心，吉林 四平 136000) 2(浙江師范大學 數理與信息工程學院，浙江 金華 310023) 3(浙江師范大學 網絡空間安全一流學科，浙江 金華 310023)

1 引 言

無線傳感器網絡是物聯網的一個重要組成部分，利用大量微型傳感器節點通過無線通信方式構成一個自組織的多跳網絡，部署在需要監測的區域內[1]，目的是協作地感知、采集和處理網絡覆蓋區域內待測對象的信息并發送給觀察者，無線傳感器網絡還廣泛用于土木工程和可持續能源系統中[2,3].

在實際應用中，根據無線傳感器網絡中是否需要配備自身位置已知的信標節點，可以將定位算法分成基于信標節點的定位算法[4,5]，和無信標節點的定位算法[6,7]兩類.通常基于信標節點的定位算法在絕對精度和相對精度上都有更好的表現，因此在對節點位置精確度要求較高的應用場合中通常使用基于信標節點的定位算法.不考慮使用動態位置進行定位的無線傳感器網絡[8,9]，在傳統的靜態無線傳感器網絡中，我們假定所有節點都是靜止不動的，然而實際應用中節點的位置并不像理想情況下那樣永遠保持不變[10].對于一般的傳感器網絡節點，按照一定的周期對其進行重新定位就可以校正由漂移引起的定位偏差.為了降低成本，在大量應用中采用對信標節點人為預設位置信息的辦法，這種情況下如果信標節點產生了漂移，重新定位過程反而會使位置偏差擴散.就算信標節點安裝了GPS模塊，也可能因為信標的漂移導致某個區域內定位覆蓋率降低，普通節點無法完成重定位過程.因此，解決信標節點漂移情況下的無線傳感器網絡節點定位問題，具有極大的理論價值和應用價值.

關于WSN節點可信定位問題的研究方面，Kuo等人提出了信標移動檢測算法(Beacon Movement Detection，BMD)[11]，主要用來識別網絡中的部分位置發生被動改變的信標節點.其思路為，在網絡中設置一個BMD引擎來收集全網絡的RSSI(Received Signal Strength Indication)信息并進行處理，在一定容錯范圍內能夠判斷出信標節點是否發生移動.這種集中式的算法通信量較大且需要具有較強計算能力的Sink節點或后臺計算機，不適用于大規模WSN網絡.也有采用隱藏的位置校驗節點對信標進行位置驗證的方法[12]，但同樣屬于集中式的可信定位算法，且需要額外的可信節點，對實際應用場景有特殊的要求.Yang Z等人[13，14]運用剛性理論排除定位參考位置中的異常值，以此來提供可信的定位結果，但一方面剛性理論本身要求測距值精度很高，另一方面運算量較大.Yawen Wei等人[15]根據鄰居節點間的相互觀測信息建立了位置驗證概率模型，并取得較好的效果.但未對后續的節點重定位過程進行探討.文獻[16]運用分布式的基于RSSI變化的鄰居節點評分機制，來識別位置被動改變的信標節點.但不能運用于信標節點被誘捕的情況.文獻[17]同樣是分布式的節點定位及位置驗證算法，雖然分布式算法在計算量方面占優勢，但精確度和算法收斂速度往往不理想.

本文將能夠完成節點一次性定位的兩類多維定標算法進行結合，將精確性和魯棒性進行優勢互補，提出一種能夠將節點定位、位置驗證和節點重定位進行融合的RI-MDS(RSSI-based Multi-Dimensional Scaling)算法以解決WSN節點漂移場景中的定位問題.

2 問題建模

2.1 問題描述

定義1.節點漂移，在某些應用場景中，網絡部署并完成節點定位后，節點自身位置可能發生被動的改變，這種現象叫做節點漂移.

2.2 問題建模

在一個2維的WSN中，共有N個傳感器節點，組成adhoc網絡.其中m個信標節點A={ai：i=1，…，m}，n個普通節點S={si：i=1，…，n}，m+n=N，m<

(1)

因此，目標問題為

3 RI-MDS定位過程

3.1 算法基本思想

測距MDS以測距值為算法輸入，能夠一次性完成節點定位，但由于測距誤差的存在，導致定位精度不高；而非測距的MDS算法利用節點間相異性信息和節點間距離需滿足單調性關系的特點進行反復迭代計算，對測距誤差有較高的容忍程度，但定位精度受初始化位置的影響較大.由測距MDS算法產生初始坐標矩陣，由非測距MDS的迭代計算進行位置求精，符合集中式一次性節點定位算法的需求.網絡部署并完成首次節點定位后，每個時間周期T內執行一次，每次執行過程中均將本次定位過程中由非測距MDS產生的相對坐標與首次產生的相對初始坐標進行比較，過濾產生了漂移的信標節點.

3.2 算法定位流程

在無線傳感器網絡中，普通節點借助信標位置信息，通過調用特定的定位算法得到自身的估計位置，估計位置與其實際位置有一定偏差，這個偏差稱之為定位誤差；完成網絡部署后，每個時間周期T內均有若干節點發生位置漂移(所有節點短時內的不停移動屬移動定位問題，不予考慮).在一定區域內部署N個節點，其中信標節點m個，其余N-m個為普通節點；網絡中所有節點通信半徑為R，假設任意兩節點在通信半徑范圍內可以進行通信，互為鄰居節點.假設節點在初始化定位時，信標節點的位置信息是可信的.

測距過程采用經典的無線傳播模型[18]如公式(2)所示：

(2)

其中d表示兩節點間的距離，d0為參考距離(通常取1米)，n為信道衰減指數，一般取2～4，P(d0)是兩節點間距離為d0時接收節點的接收信號強度，P(d)為兩節點間距離為d時接收節點的接收信號強度，Xσ為高斯白噪聲，一般使用均值為0，方差為σ的高斯隨機函數產生.RI-MDS的算法輸入為各節點測量到的RSSI向量；算法輸出即所有節點在絕對坐標系中的位置坐標信息.

算法框架步驟：

Step1.傳感器節點收集t次鄰居節點的RSSI信息，構成RSSI向量，發送至Sink節點.

Step2.Sink節點根據各節點的RSSI向量計算平均RSSI，并按公式(2)進行測距，利用節點間的測距值構建節點相異性矩陣[pij] .

Step4.采用非測量多維定標技術，計算每個節點的相對位置坐標Xr；

Step5.選擇若干個節點(二維不少于3個且不共線，三維不少于4個且不共面)并給定其在絕對坐標系中的坐標值，并以此為信息利用仿射變換(Affine Transform)方法將所有節點的相對位置坐標 轉換為絕對位置坐標.

算法框架的step 4是整個算法的核心，采用了非測量多維定標技術利用相異性矩陣信息對節點坐標位置進行反復的迭代計算，以使脅強系數滿足一定值.

(3)

其中，θ是坐標軸繞原點逆時針轉動的角度，bx和by是坐標軸原點分別在X軸和Y軸上移動的距離.

將已知兩坐標系位置坐標值的m個點的坐標信息依次代入公式(3)，得到如下方程組：

(4)

和

(5)

對式(4)和(5)應用極大似然估計法(MLE，Maximum Likelihood Estimation)法來獲得最小均方差(MMSE，Minimum Mean Square Error)意義上的估計值以得到最終的轉換函數參數λsinθ、λcosθ、bx和by，并得到最終的轉換線性方程如下：

(6)

依次對網絡中所有未獲得絕對坐標值的n-m個節點應用式(6)求解絕對坐標值.

4 漂移檢測與重定位

圖1 漂移節點檢測流程圖Fig.1 Flow chart of drifted node detection

5 性能驗證

5.1 仿真環境

評價定位算法性能好壞最常用的兩個指標是平均定位誤差(ALE，Average Localization Error)和平均定位誤差率(LER，Localization Error Ratio)，平均定位誤差和平均定位誤差率的計算公式分別如式(7)和式(8)所示：

(7)

(8)

仿真實驗的設計主要分為兩個部分：

1)與文獻[19]中對經典MDS-MAP定位算法的改進算法進行比較：比較兩算法在隨機分布情況下，不同平均連通度條件下的定位誤差率，矩形區域邊長為1000單位，節點數量均為200，用于從相對坐標系向全局坐標系轉換用的節點數量為4個，通過調整各個分布條件下節點的通信半徑以調整平均連通度指標，并以該指標為坐標軸橫軸，定位誤差率為坐標軸縱軸進行性能比較.

上述仿真實驗的結果均是取50次運行的平均值.

5.2 實驗結果與討論

第一個仿真實驗的結果分別如圖2所示，可以看到不管在隨機分布場景中，本文所提出的RI-MDS相對定位算法在各種網絡平均連通度條件下平均定位誤差率均低于IMDS定位算法5到10個百分點.此外，IMDS定位算法在網絡平均連通度提高至大約16時，其平均定位誤差率的下降趨勢出現了明顯的減緩，并在一定范圍內出現反復波動的情況，而本文所提出的RI-MDS相對算法的平均定位誤差率則繼續隨著網絡平均連通度的提高而下降.

圖2 節點隨機部署情況下的性能比較Fig.2 Performance evaluation in random deployment

通過對算法原理的初步分析可以推測，由于IMDS定位算法采用節點間測量出的距離值作為節點間相異性關系的數據基礎，且僅使用了基于測距的MDS技術進行節點位置的計算，導致網絡連通度達到一定程度后，引入的冗余位置關系引起更多的位置沖突，抵消了精確度上的提升.而RI-MDS算法除了直接使用平均RSSI測距值作為算法的輸入數據，使得初始位置相對較準，還利用基于非測距的MDS技術進行多次迭代和取平均值的方式消除了新增加的冗余性引入的關系沖突，因此算法的定位精度相對IMDS算法在同等情況下還可以繼續提高.

圖3 不同網絡連通度情況下RI-MDS算法的性能Fig.3 Performance in various network connections

如圖3所示，當可用信標數量超過5個的時候，無論網絡連通度升高多少，RI-MDS算法的定位精度均改善有限；同時，當網絡連通度大于10時，無論信標節點增加多少，算法的定位精度都比較穩定.因此，可以說RI-MDS算法能夠適應于信標節點密度較低的場景，只要網絡連通度有一定的保障，而實際應用場景中，由于節點的通信半徑往往在60米以上，隨機撒播的網絡節點密度較高，上述情況通常是可以得到滿足的.而圖4則說明當存在較大的測距誤差情況下，RI-MDS的定位誤差仍能滿足小于40%通信半徑的可用性條件，只要網絡的連通度大于10.進一步說明了算法的實用性.下面對算法在節點漂移檢測方面的性能.

首先對漂移檢測閾值λ的取值進行實驗，范圍在[0.1r，0.4r]以步長0.05r變化，實驗中20個信標均發生漂移.仿真結果如圖5所示，隨著測距誤差的增大，漂移信標節點的檢測成功率下降；測距誤差固定的情況下，隨著λ值的增大，檢測成功率和誤檢率均下降(因實驗場景中共20個信標，5%的比率代表1個信標被檢測成功或誤檢)，由于測距誤差的存在，導致每次測距的方差均有小幅變化，從本質上導致了算法很難準確檢測出位置產生了輕微漂移的節點，而這些節點中的信標節點位置的改變對重定位結果的影響也很有限，綜合來看在λ取值0.3r的時候，檢測成功率在90%以上，而衰檢測率小于10%.因此，在后續實驗中固定λ的值為0.3r.

圖4 不同測距誤差&網絡連通度的性能比較Fig.4 Performance comparison in various range errors and network connections

圖5 檢測率與檢測閾值的關系Fig.5 Detection ratio VS.threshold

接下來通過與文獻[11]提出的其于RSS值的BMD(beacon movement detection)算法進行比較，分析RI-MDS的節點漂移檢測性能隨網絡中節點密度和漂移信標的比例變化情況下的不同表現.實驗中將測距誤差固定在0.2r，所有20個信標節點均發生漂移.

圖6 節點漂移檢測性能與網絡節點密度的關系Fig.6 Detection ratio VS.density of sensor node

實驗結果如圖6所示，隨著節點數的增加(網絡節點密度升高)，兩種算法的檢測成功率均有提高，但RI-MDS的檢測成功率高于BMD算法；而誤檢測率方面，BMD算法隨著網絡節點數量增多，反而出現上升的情況，性能表現也不如RI-MDS.這是因為，RI-MDS是能過測距值迭代計算進行節點定位，在定位過程中消除了測距誤差產生的數據沖突，既漂移檢測的情能與定位精度緊密相關；而BMD算法在存在較大測距誤差的情況下，采集的數據之間可能相互沖突，反而產生誤檢的情況.在下一個實驗中，將產生位置漂移的信標節點數量在[5，20]范圍間變化，步長為5.實驗結果如圖7所示，由于節信標節點數量較少，因此在實驗結果上直接以檢測出(誤檢測)節點數量為單位，測距誤差仍設置為0.2r，網絡中共部署了400個節點.結果與我們預想的基本一致，兩種算法的檢測成功率比較穩定，但由于迭代計算的原因，RI-MDS的性能表現均高于BMD算法.

圖7 檢測性能與漂移信標節點比例變化的關系Fig.7 Detection ratio VS.the amount of drift anchors

最后，通過實驗評估在所有20個信標均發生了位置漂移后，在將相對坐標系轉換為絕對坐標系的過程中，引入5個未發生漂移的普通信節作為臨時信標，RI-MDS的算法定位性能表現，網絡平均連通度設置為10，測距誤差范圍在[0.05r，0.2r]變化，步長0.05r.

圖8 重定位誤差Fig.8 Error of re-localization

結果如圖8所示，因RI-MDS對誤差的容忍度較好，定位精度滿足了可用性要求.

6 結論與展望

本文提出一種融合節點定位、位置驗證和重定位一體的算法RI-MDS，有效的解決了存在節點漂移場景下的WSN節點定位問題，RI-MDS算法很好的整合兩類MDS算法的優勢，在節點定位、位置驗證和重定位方法表現出較好的性能.未來工作將集中在移動節點的位置驗證算法研究方面.

[1] Shi H，Wang W，Kwok N M，et al.Game theory for wireless sensor networks：a survey[J].Sensors，2012，12(7)：9055-9097.

[2] Jang W S，Lee D E，Choi J H.Ad-hoc performance of wireless sensor network for large scale civil and construction engineering applications[J].Automation in Construction，2012，26(10)：32-45.

[3] Hackmann G，Sun F，Castaneda N，et al.A holistic approach to decentralized structural damage localization using wireless sensor networks[J].Computer Communications，2012，36(1)：29-41.

[4] Shen X S，Lu M.A framework for indoor construction resources tracking by applying wireless sensor networks[J].Canadian Journal of Civil Engineering，2012，39(9)：1083-1088.

[5] Gholami M，Cai N，Bemnan R W.An artificial neural network approach to the problem of wireless sensors network localization[J].Robotics and Computer-Integrated Manufacturing，2012，29(1)：96-109.

[6] Min H F，Yei L W.Investigating target detection and localization in wireless sensor network[J].Procedia Engineering,2012,41:75-81.

[7] Jarray F.A lagrangean-based heuristics for the target covering problem in wireless sensor network[J].Applied Mathematical Modelling，2013，37(10-11)：6780-6785.

[8] Chang C T，Chang C Y，Lin C Y.Anchor-guiding mechanism for beacon-assisted localization in wireless sensor networks[J].IEEE Sensors Journal，2012，12(5)：1098-1111.

[9] Bao H，Zhang B X，Li C.Mobile anchor assisted particle swarm optimization (PSO) based localization algorithms for wireless sensor networks[J].Wireless Communications & Mobile Computing，2012，12(15)：1313-1325.

[10] Wang J，Ghosh R K，Das S K.A survey on sensor localization[J].Journal of Control Theory and Applications，2010，8(1)：2-11.

[11] Kuo S P，Kuo H J，Tseng Y C.The beacon movement detection problem in wireless sensor networks for localization applications[J].IEEE Transactions on Mobile Computing，2009，8(10)：1326-1338.

[12] Zeng Y，Cao J，Hong J，et al.Secure localization and location verification in wireless sensor networks：a survey[J].Journal of Supercomputing，2013，64(3)：685-701.

[13] Yang Z，Jian L，Wu C，et al.Beyond triangle inequality：sifting noisy and outlier distance measurements for localization[J].ACM Transactions on Sensor Networks (TOSN)，2013，9(2)：1-20.

[14] Yang Z，Wu C，Chen T，et al.Detecting outlier measurements based on graph rigidity for wireless sensor network localization[J].Vehicular Technology，IEEE Transactions on，2013，62(1)：374-383.

[15] Wei Y，Guan Y.Lightweight location verification algorithms for wireless sensor networks[J].Parallel and Distributed Systems，IEEE Transactions on，2013，24(5)：938-950.

[16] He Wen-xiu，Xia Ming，Zhao Xiao-min，et al.Research on localization algorithm with beacon movement in wireless sensor network[J].Journal of Chinese Computer Systems，2011，32(11)：2259-2262.

[17] Miao C，Dai G，Ying K，et al.Collaborative localization and location verification in WSNs[J].Sensors，2015，15(5)：10631-10649.

[18] Jin R，Che Z，Xu H，et al.An RSSI-based localization algorithm for outliers suppression in wireless sensor networks[J].Wireless Networks，2015，21(8)：2561-2569.

[19] Stojkoska B R，Kirandziska V.Improved MDS-based algorithm for nodes localization in wireless sensor networks[C].Eurocon.IEEE，2013：608-613.

附中文參考文獻：

[16] 何文秀，夏 明，趙小敏，等.WSN中信標節點移動情況下的定位方法研究[J].小型微型計算機系統，2011，32(11)：2259-2262.