無線傳感器網絡WSN(Wireless Sensor Networks)綜合了無線通信技術,、傳感器技術、嵌入式計算技術和分布式信息處理技術,，已經成為當前國際上備受關注的,、多學科高度交叉、知識高度集成的前沿研究領域[1],。通過部署大量傳感器節(jié)點至目標區(qū)域,，WSN將改變人們與客觀世界的交互方式，其在環(huán)境監(jiān)測方面的應用尤其具有廣泛前景[2],。
鑒于WSN的應用背景,，定位技術成為實現(xiàn)其功能的關鍵技術之一，如何使定位指標達到最優(yōu)始終是WSN定位算法的研究目標,。
近年來,，對WSN定位問題有了許多新穎的思想和解決方案，但多是針對解決固定節(jié)點的定位問題,。若將這些算法應用于移動節(jié)點的定位,，雖然也可以通過每隔一段時間的更新來進行定位，但節(jié)點的移動性會導致算法的定位精度降低,。雖然移動性給節(jié)點定位帶來了困難,，但也可以利用其來提高定位精度。參考文獻[3]提出了一種基于MCL（Monte Carlo Localization）的移動節(jié)點定位算法,，其核心思想是在貝葉斯濾波位置估計基礎上,，用若干個帶權重的采樣點來描述移動節(jié)點在布置區(qū)域的可能位置分布。
多維定標技術MDS（Multidimensional Scaling）是一種運用于心理學領域的技術,，后由Shang等人引入WSN定位技術中[4],。基于MDS技術的定位算法在不需要知道節(jié)點間測量距離的情況下,，可以充分利用節(jié)點間連通性信息,，在即使沒有錨節(jié)點的情況下也可以得到節(jié)點的相對位置坐標。
本文提出一種MDS-MCL定位算法,，通過結合MCL和MDS-RC[5]兩種方法,，得到一種新的移動節(jié)點定位算法。通過將MDS-RC定位算法引入MCL算法,，在定位過程中利用MDS-RC定位算法給出的定位位置作為新的限定條件進行濾波,，保留更接近節(jié)點真實位置的預測樣本，提高節(jié)點定位精度,。
1 MDS-MCL定位算法
本文提出的MDS-MCL算法,，主要是通過在過濾階段利用MDS-RC算法給出的定位結果作為新的限定條件，濾除預測樣本,，以達到提高精度的目的,。
1.1 引入新的濾波條件
MDS-RC定位算法是一種應用在大規(guī)模固定節(jié)點定位問題中的算法,，通過對節(jié)點間最小路徑賦予權值的方法來提高算法的整體定位精度。在大規(guī)模的網絡中使用時,，該算法的整體定位效果較好,，但不排除出現(xiàn)個別節(jié)點誤差較大的情況。在大規(guī)模網絡中,，由于整體定位精度較高,，所以即使個別節(jié)點的定位誤差較大，也不會影響算法整體的定位效果,。但將這種算法應用于單一節(jié)點的定位時,，這種偶然出現(xiàn)的較大誤差對于最終定位結果的影響較大，必須進行處理,。
在MDS-MCL定位算法中,，會對MDS-RC得到的定位結果進行判斷，根據不同的情況采取不同的濾波方式,，從而避免偶然出現(xiàn)的大誤差對最終結果造成影響,。算法的具體流程如圖1所示。
算法的初始化主要是進行循環(huán)次數(shù)k和預測樣本總數(shù)N的設定,。
如圖1所示,，在每一時刻的定位過程中，首先根據周圍一跳范圍內的信標節(jié)點信息,，根據MDS-RC算法,，得到初步定位位置ot。然后根據ot是否在最大移動速度范圍內對預測樣本進行處理,。
過濾階段的詳細處理方法如下：
第一種情況：如果算法的定位位置ot在最大移動速度范圍內,，則根據ot進行濾波。在生成的N個預測位置中,，計算其與ot的距離,，將這些距離與前一次保留的預測樣本進行比較，保留N個與ot最近的樣本,，然后進行下一次循環(huán),。
第二種情況：如果算法的定位位置ot在最大移動速度范圍外，用另一種方法對位置進行修正,。在使用MDS-RC算法進行定位時,，會利用到周圍一跳范圍內的信標節(jié)點。對預測樣本中的每一個位置,，統(tǒng)計在其通信范圍的本次定位中利用到的信標節(jié)點數(shù),，然后與前一次保留的預測樣本進行比較，保留N個信標節(jié)點數(shù)最多的樣本，然后進入下一次循環(huán),。
通過結合MDS-RC與MCL方法對移動節(jié)點進行定位,，可以避免單一方法中偶然出現(xiàn)的較大誤差。
另外,，MDS-MCL算法與MCL算法另一點不同的是，在每一次濾波中保留N個最符合要求的預測樣本,，而不是嚴格刪除所有不符合要求樣本,。通過這一點修改，可以保證算法在規(guī)定次數(shù)的循環(huán)內得到足夠數(shù)量的預測樣本,，從而將算法的計算時間控制在一定范圍內,。
1.2 參數(shù)與算法表現(xiàn)的關系
在MDS-MCL算法中，有兩個初始參數(shù)：循環(huán)次數(shù)和預測樣本數(shù),。為了使算法的性能達到最優(yōu),，下面通過仿真實驗考察這兩個參數(shù)對定位誤差和計算時間的影響。
在移動節(jié)點的定位中,，必須要考慮實時性因素,，圖4給出了在循環(huán)次數(shù)、樣本數(shù)不同時定位時間的變化,。由仿真結果看出,，當循環(huán)次數(shù)為3和5時，算法的計算時間較短,，且隨樣本數(shù)的增長變化較為平緩,，當循環(huán)次數(shù)為10時，計算時間略長,，且隨樣本數(shù)變化的較為劇烈,。
綜上所述，為了兼顧定位精度和計算時間兩方面的考慮,，在參數(shù)的選擇中,，可將樣本數(shù)選為50，循環(huán)次數(shù)選為5,。
2 算法仿真實驗及結果
在本文中,，通過MATLAB7.0軟件進行仿真實驗，節(jié)點被隨機部署在范圍為100×100網絡中,，信標節(jié)點的位置固定,，均勻分布在整個網絡中。節(jié)點的通信半徑設為20,。在仿真試驗中,，通過改變部署的節(jié)點總數(shù)來改變節(jié)點連通度（平均每個節(jié)點具有的鄰居節(jié)點數(shù)）。
本文中，移動節(jié)點定位誤差定義如下
為了說明MDS-MCL算法的性能,，將其與MCL定位算法進行比較,。
圖5為移動速度不同時，各連通度下兩種算法的定位誤差,。
由圖中可以看到,，MDS-MCL算法相對普通的MCL定位算法，具有更好的定位精度,。且在各連通度下,，節(jié)點的定位誤差基本穩(wěn)定，基本保持在10%左右,，比MCL算法有了2%左右的提高,。
圖6(a)和圖6(b)給出了在最大移動速度為
連通度為15時，MCL算法和MDS-MCL算法的定位效果圖,?？梢钥闯觯涍^改進后的定位算法對移動節(jié)點的運動軌跡擬合更好,。
在基于MCL方法的基礎上,，本文結合MDS-RC方法對移動節(jié)點定位算法進行了改進。通過仿真可以驗證,，即使在不需測距的情況下,，移動節(jié)點也可以得到較好的定位效果。通過將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 10th Annual 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 4th ACM 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.