基于MDS技術與MCL方法的無線傳感器網絡移動節點定位算法*

陳冰潔，黃小平，王 巖

（北京航空航天大學 自動化學院，北京100191）

無線傳感器網絡WSN(Wireless Sensor Networks)綜合了無線通信技術、傳感器技術、嵌入式計算技術和分布式信息處理技術，已經成為當前國際上備受關注的、多學科高度交叉、知識高度集成的前沿研究領域[1]。通過部署大量傳感器節點至目標區域，WSN將改變人們與客觀世界的交互方式，其在環境監測方面的應用尤其具有廣泛前景[2]。

鑒于WSN的應用背景，定位技術成為實現其功能的關鍵技術之一，如何使定位指標達到最優始終是WSN定位算法的研究目標。

近年來，對WSN定位問題有了許多新穎的思想和解決方案，但多是針對解決固定節點的定位問題。若將這些算法應用于移動節點的定位，雖然也可以通過每隔一段時間的更新來進行定位，但節點的移動性會導致算法的定位精度降低。雖然移動性給節點定位帶來了困難，但也可以利用其來提高定位精度。參考文獻[3]提出了一種基于MCL（Monte Carlo Localization）的移動節點定位算法，其核心思想是在貝葉斯濾波位置估計基礎上，用若干個帶權重的采樣點來描述移動節點在布置區域的可能位置分布。

多維定標技術 MDS（Multidimensional Scaling）是一種運用于心理學領域的技術，后由Shang等人引入WSN定位技術中[4]。基于MDS技術的定位算法在不需要知道節點間測量距離的情況下，可以充分利用節點間連通性信息，在即使沒有錨節點的情況下也可以得到節點的相對位置坐標。

本文提出一種MDS-MCL定位算法，通過結合MCL和MDS-RC[5]兩種方法，得到一種新的移動節點定位算法。通過將MDS-RC定位算法引入MCL算法，在定位過程中利用MDS-RC定位算法給出的定位位置作為新的限定條件進行濾波，保留更接近節點真實位置的預測樣本，提高節點定位精度。

1 MDS-MCL定位算法

本文提出的MDS-MCL算法，主要是通過在過濾階段利用MDS-RC算法給出的定位結果作為新的限定條件，濾除預測樣本，以達到提高精度的目的。

1.1 引入新的濾波條件

MDS-RC定位算法是一種應用在大規模固定節點定位問題中的算法，通過對節點間最小路徑賦予權值的方法來提高算法的整體定位精度。在大規模的網絡中使用時，該算法的整體定位效果較好，但不排除出現個別節點誤差較大的情況。在大規模網絡中，由于整體定位精度較高，所以即使個別節點的定位誤差較大，也不會影響算法整體的定位效果。但將這種算法應用于單一節點的定位時，這種偶然出現的較大誤差對于最終定位結果的影響較大，必須進行處理。

在MDS-MCL定位算法中，會對MDS-RC得到的定位結果進行判斷，根據不同的情況采取不同的濾波方式，從而避免偶然出現的大誤差對最終結果造成影響。算法的具體流程如圖1所示。

圖1 MDS-MCL算法主體流程

算法的初始化主要是進行循環次數k和預測樣本總數N的設定。

如圖1所示，在每一時刻的定位過程中，首先根據周圍一跳范圍內的信標節點信息，根據MDS-RC算法，得到初步定位位置ot。然后根據ot是否在最大移動速度范圍內對預測樣本進行處理。

過濾階段的詳細處理方法如下：

第一種情況：如果算法的定位位置ot在最大移動速度范圍內，則根據ot進行濾波。在生成的N個預測位置中，計算其與ot的距離，將這些距離與前一次保留的預測樣本進行比較，保留N個與ot最近的樣本，然后進行下一次循環。

第二種情況：如果算法的定位位置ot在最大移動速度范圍外，用另一種方法對位置進行修正。在使用MDS-RC算法進行定位時，會利用到周圍一跳范圍內的信標節點。對預測樣本中的每一個位置，統計在其通信范圍的本次定位中利用到的信標節點數，然后與前一次保留的預測樣本進行比較，保留N個信標節點數最多的樣本，然后進入下一次循環。

通過結合MDS-RC與MCL方法對移動節點進行定位，可以避免單一方法中偶然出現的較大誤差。

另外，MDS-MCL算法與MCL算法另一點不同的是，在每一次濾波中保留N個最符合要求的預測樣本，而不是嚴格刪除所有不符合要求樣本。通過這一點修改，可以保證算法在規定次數的循環內得到足夠數量的預測樣本，從而將算法的計算時間控制在一定范圍內。

1.2 參數與算法表現的關系

在MDS-MCL算法中，有兩個初始參數：循環次數和預測樣本數。為了使算法的性能達到最優，下面通過仿真實驗考察這兩個參數對定位誤差和計算時間的影響。

在移動節點的定位中，必須要考慮實時性因素，圖4給出了在循環次數、樣本數不同時定位時間的變化。由仿真結果看出，當循環次數為3和5時，算法的計算時間較短，且隨樣本數的增長變化較為平緩，當循環次數為10時，計算時間略長，且隨樣本數變化的較為劇烈。

綜上所述，為了兼顧定位精度和計算時間兩方面的考慮，在參數的選擇中，可將樣本數選為50，循環次數選為5。

2 算法仿真實驗及結果

在本文中，通過MATLAB7.0軟件進行仿真實驗，節點被隨機部署在范圍為100×100網絡中，信標節點的位置固定，均勻分布在整個網絡中。節點的通信半徑設為20。在仿真試驗中，通過改變部署的節點總數來改變節點連通度（平均每個節點具有的鄰居節點數）。

本文中，移動節點定位誤差定義如下

為了說明MDS-MCL算法的性能，將其與MCL定位算法進行比較。

圖5為移動速度不同時，各連通度下兩種算法的定位誤差。

由圖中可以看到，MDS-MCL算法相對普通的MCL定位算法，具有更好的定位精度。且在各連通度下，節點的定位誤差基本穩定，基本保持在10%左右，比MCL算法有了2%左右的提高。

在基于MCL方法的基礎上，本文結合MDS-RC方法對移動節點定位算法進行了改進。通過仿真可以驗證，即使在不需測距的情況下，移動節點也可以得到較好的定位效果。通過將MCL算法和MDS-MCL算法進行比較，可以驗證改進算法的定位誤差大體均在15%以下，且相對前者有2%左右的降低。另外，通過對算法計算時間的考察，可以驗證改進算法的計算時間較短，可以滿足實際應用的要求。

[1]Liu Yongmin,Wu Shuci,Nian Xiaohong.The architecture and characteristics of wireless sensor network[A].In:Proc.of the 2009 Computer Technology and Development(ICCTD’09)Conf.Vol.1[C].Kota Kinabalu,2009：561-565.

[2]Wu Zhengzhong,Liu Zilin,Liu Jun,et al.Wireless sensor networks for living environment monitoring[A].In:Proc.of the 2009 Software Engineering(WCSE’09)Conf.Vol.3[C].Xiamen,2009：22-25.

[3]Hu Lingxuan,DAVID E.Localization for mobile sensor networks[C].In:Proc.Of the 10thAnnual International Conference on Mobile Computing and Networking(MobiCom-2004),2004：45-47.

[4]SHANG Y,RuML W,ZHANG Y.Localization from mere connectivity in sensor networks[C].In：Proc.of the 4thACM Int’l Symp on Mobile Ad Hoc networking^computing,New York:ACM Press,2003：201-212.

[5]Chen Bingjie,Huang Xiaoping,Wang Yan.A localization algorithm in wireless sensor networks based on MDS with RSSI Classified[C].In:Proc of the 5th Hefei International Conference on Computer Science&Education(ICCSE’10),2010：1465-1469.