摘  要： 在MCL算法的基礎(chǔ)上，結(jié)合改進(jìn)的基于多維定標(biāo)MDS（Multidimensional Scaling）的定位算法引進(jìn)新的濾波條件，提出了一種移動(dòng)節(jié)點(diǎn)定位算法。該算法通過在循環(huán)濾波部分引入新的限定條件，可以保留更靠近真實(shí)距離的預(yù)測(cè)樣本，減小定位誤差。仿真實(shí)驗(yàn)表明，該算法具有更好的定位精度。
關(guān)鍵詞： 無線傳感器網(wǎng)絡(luò)；移動(dòng)節(jié)點(diǎn)；定位算法；蒙特卡羅;多維定標(biāo)

    無線傳感器網(wǎng)絡(luò)WSN(Wireless Sensor Networks)綜合了無線通信技術(shù)、傳感器技術(shù)、嵌入式計(jì)算技術(shù)和分布式信息處理技術(shù)，已經(jīng)成為當(dāng)前國際上備受關(guān)注的、多學(xué)科高度交叉、知識(shí)高度集成的前沿研究領(lǐng)域[1]。通過部署大量傳感器節(jié)點(diǎn)至目標(biāo)區(qū)域，WSN將改變?nèi)藗兣c客觀世界的交互方式，其在環(huán)境監(jiān)測(cè)方面的應(yīng)用尤其具有廣泛前景[2]。
    鑒于WSN的應(yīng)用背景，定位技術(shù)成為實(shí)現(xiàn)其功能的關(guān)鍵技術(shù)之一，如何使定位指標(biāo)達(dá)到最優(yōu)始終是WSN定位算法的研究目標(biāo)。
    近年來，對(duì)WSN定位問題有了許多新穎的思想和解決方案，但多是針對(duì)解決固定節(jié)點(diǎn)的定位問題。若將這些算法應(yīng)用于移動(dòng)節(jié)點(diǎn)的定位，雖然也可以通過每隔一段時(shí)間的更新來進(jìn)行定位，但節(jié)點(diǎn)的移動(dòng)性會(huì)導(dǎo)致算法的定位精度降低。雖然移動(dòng)性給節(jié)點(diǎn)定位帶來了困難，但也可以利用其來提高定位精度。參考文獻(xiàn)[3]提出了一種基于MCL（Monte Carlo Localization）的移動(dòng)節(jié)點(diǎn)定位算法，其核心思想是在貝葉斯濾波位置估計(jì)基礎(chǔ)上，用若干個(gè)帶權(quán)重的采樣點(diǎn)來描述移動(dòng)節(jié)點(diǎn)在布置區(qū)域的可能位置分布。
    多維定標(biāo)技術(shù)MDS（Multidimensional Scaling）是一種運(yùn)用于心理學(xué)領(lǐng)域的技術(shù)，后由Shang等人引入WSN定位技術(shù)中[4]?；贛DS技術(shù)的定位算法在不需要知道節(jié)點(diǎn)間測(cè)量距離的情況下，可以充分利用節(jié)點(diǎn)間連通性信息，在即使沒有錨節(jié)點(diǎn)的情況下也可以得到節(jié)點(diǎn)的相對(duì)位置坐標(biāo)。
    本文提出一種MDS-MCL定位算法，通過結(jié)合MCL和MDS-RC[5]兩種方法，得到一種新的移動(dòng)節(jié)點(diǎn)定位算法。通過將MDS-RC定位算法引入MCL算法，在定位過程中利用MDS-RC定位算法給出的定位位置作為新的限定條件進(jìn)行濾波，保留更接近節(jié)點(diǎn)真實(shí)位置的預(yù)測(cè)樣本，提高節(jié)點(diǎn)定位精度。
1 MDS-MCL定位算法
    本文提出的MDS-MCL算法，主要是通過在過濾階段利用MDS-RC算法給出的定位結(jié)果作為新的限定條件，濾除預(yù)測(cè)樣本，以達(dá)到提高精度的目的。
1.1 引入新的濾波條件
    MDS-RC定位算法是一種應(yīng)用在大規(guī)模固定節(jié)點(diǎn)定位問題中的算法，通過對(duì)節(jié)點(diǎn)間最小路徑賦予權(quán)值的方法來提高算法的整體定位精度。在大規(guī)模的網(wǎng)絡(luò)中使用時(shí)，該算法的整體定位效果較好，但不排除出現(xiàn)個(gè)別節(jié)點(diǎn)誤差較大的情況。在大規(guī)模網(wǎng)絡(luò)中，由于整體定位精度較高，所以即使個(gè)別節(jié)點(diǎn)的定位誤差較大，也不會(huì)影響算法整體的定位效果。但將這種算法應(yīng)用于單一節(jié)點(diǎn)的定位時(shí)，這種偶然出現(xiàn)的較大誤差對(duì)于最終定位結(jié)果的影響較大，必須進(jìn)行處理。
    在MDS-MCL定位算法中，會(huì)對(duì)MDS-RC得到的定位結(jié)果進(jìn)行判斷，根據(jù)不同的情況采取不同的濾波方式，從而避免偶然出現(xiàn)的大誤差對(duì)最終結(jié)果造成影響。算法的具體流程如圖1所示。

    算法的初始化主要是進(jìn)行循環(huán)次數(shù)k和預(yù)測(cè)樣本總數(shù)N的設(shè)定。
    如圖1所示，在每一時(shí)刻的定位過程中，首先根據(jù)周圍一跳范圍內(nèi)的信標(biāo)節(jié)點(diǎn)信息，根據(jù)MDS-RC算法，得到初步定位位置ot。然后根據(jù)ot是否在最大移動(dòng)速度范圍內(nèi)對(duì)預(yù)測(cè)樣本進(jìn)行處理。

    過濾階段的詳細(xì)處理方法如下：
    第一種情況：如果算法的定位位置ot在最大移動(dòng)速度范圍內(nèi)，則根據(jù)ot進(jìn)行濾波。在生成的N個(gè)預(yù)測(cè)位置中，計(jì)算其與ot的距離，將這些距離與前一次保留的預(yù)測(cè)樣本進(jìn)行比較，保留N個(gè)與ot最近的樣本，然后進(jìn)行下一次循環(huán)。
    第二種情況：如果算法的定位位置ot在最大移動(dòng)速度范圍外，用另一種方法對(duì)位置進(jìn)行修正。在使用MDS-RC算法進(jìn)行定位時(shí)，會(huì)利用到周圍一跳范圍內(nèi)的信標(biāo)節(jié)點(diǎn)。對(duì)預(yù)測(cè)樣本中的每一個(gè)位置，統(tǒng)計(jì)在其通信范圍的本次定位中利用到的信標(biāo)節(jié)點(diǎn)數(shù)，然后與前一次保留的預(yù)測(cè)樣本進(jìn)行比較，保留N個(gè)信標(biāo)節(jié)點(diǎn)數(shù)最多的樣本，然后進(jìn)入下一次循環(huán)。
    通過結(jié)合MDS-RC與MCL方法對(duì)移動(dòng)節(jié)點(diǎn)進(jìn)行定位，可以避免單一方法中偶然出現(xiàn)的較大誤差。
    另外，MDS-MCL算法與MCL算法另一點(diǎn)不同的是，在每一次濾波中保留N個(gè)最符合要求的預(yù)測(cè)樣本，而不是嚴(yán)格刪除所有不符合要求樣本。通過這一點(diǎn)修改，可以保證算法在規(guī)定次數(shù)的循環(huán)內(nèi)得到足夠數(shù)量的預(yù)測(cè)樣本，從而將算法的計(jì)算時(shí)間控制在一定范圍內(nèi)。
1.2 參數(shù)與算法表現(xiàn)的關(guān)系
    在MDS-MCL算法中，有兩個(gè)初始參數(shù)：循環(huán)次數(shù)和預(yù)測(cè)樣本數(shù)。為了使算法的性能達(dá)到最優(yōu)，下面通過仿真實(shí)驗(yàn)考察這兩個(gè)參數(shù)對(duì)定位誤差和計(jì)算時(shí)間的影響。
    

    在移動(dòng)節(jié)點(diǎn)的定位中，必須要考慮實(shí)時(shí)性因素，圖4給出了在循環(huán)次數(shù)、樣本數(shù)不同時(shí)定位時(shí)間的變化。由仿真結(jié)果看出，當(dāng)循環(huán)次數(shù)為3和5時(shí)，算法的計(jì)算時(shí)間較短，且隨樣本數(shù)的增長變化較為平緩，當(dāng)循環(huán)次數(shù)為10時(shí)，計(jì)算時(shí)間略長，且隨樣本數(shù)變化的較為劇烈。
    綜上所述，為了兼顧定位精度和計(jì)算時(shí)間兩方面的考慮，在參數(shù)的選擇中，可將樣本數(shù)選為50，循環(huán)次數(shù)選為5。
2 算法仿真實(shí)驗(yàn)及結(jié)果
    在本文中，通過MATLAB7.0軟件進(jìn)行仿真實(shí)驗(yàn)，節(jié)點(diǎn)被隨機(jī)部署在范圍為100×100網(wǎng)絡(luò)中，信標(biāo)節(jié)點(diǎn)的位置固定，均勻分布在整個(gè)網(wǎng)絡(luò)中。節(jié)點(diǎn)的通信半徑設(shè)為20。在仿真試驗(yàn)中，通過改變部署的節(jié)點(diǎn)總數(shù)來改變節(jié)點(diǎn)連通度（平均每個(gè)節(jié)點(diǎn)具有的鄰居節(jié)點(diǎn)數(shù)）。
    本文中，移動(dòng)節(jié)點(diǎn)定位誤差定義如下
  
    為了說明MDS-MCL算法的性能，將其與MCL定位算法進(jìn)行比較。
    圖5為移動(dòng)速度不同時(shí)，各連通度下兩種算法的定位誤差。

    由圖中可以看到，MDS-MCL算法相對(duì)普通的MCL定位算法，具有更好的定位精度。且在各連通度下，節(jié)點(diǎn)的定位誤差基本穩(wěn)定，基本保持在10%左右，比MCL算法有了2%左右的提高。
    圖6(a)和圖6(b)給出了在最大移動(dòng)速度為連通度為15時(shí)，MCL算法和MDS-MCL算法的定位效果圖?？梢钥闯觯?jīng)過改進(jìn)后的定位算法對(duì)移動(dòng)節(jié)點(diǎn)的運(yùn)動(dòng)軌跡擬合更好。
    在基于MCL方法的基礎(chǔ)上，本文結(jié)合MDS-RC方法對(duì)移動(dòng)節(jié)點(diǎn)定位算法進(jìn)行了改進(jìn)。通過仿真可以驗(yàn)證，即使在不需測(cè)距的情況下，移動(dòng)節(jié)點(diǎn)也可以得到較好的定位效果。通過將MCL算法和MDS-MCL算法進(jìn)行比較，可以驗(yàn)證改進(jìn)算法的定位誤差大體均在15%以下，且相對(duì)前者有2%左右的降低。另外，通過對(duì)算法計(jì)算時(shí)間的考察，可以驗(yàn)證改進(jìn)算法的計(jì)算時(shí)間較短，可以滿足實(shí)際應(yīng)用的要求。
參考文獻(xiàn)
[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.