最小二乘擬合的蒙特卡羅移動定位算法研究

譚志 梁麗文 夏磊

摘 要： 針對傳統蒙特卡羅定位算法由于節點采樣效率低導致的定位精度低、定位不準確的缺陷，提出一種改進的最小二乘擬合蒙特卡羅（LSFMCL）定位算法。該算法利用MBC算法優化采樣空間，并利用最小二乘擬合節點運動軌跡，對節點位置進行預測，進一步得到最優采樣區域，最后提出權值概念并利用預測節點的權值信息計算未知節點的位置。仿真結果表明，與傳統算法相比，優化后的算法提升了節點的采樣率，提高了定位精度，對于移動節點的定位具有更加廣泛的應用前景。

關鍵詞： 蒙特卡羅定位算法； MBC算法； 最小二乘法擬合； 移動節點定位； 運動軌跡； 權值概念

中圖分類號： TN911.1?34； TP212.9 文獻標識碼： A 文章編號： 1004?373X（2018）15?0010?06

Research on least squares fitting Monte Carlo localization algorithm for mobile nodes

TAN Zhi， LIANG Liwen， XIA Lei

（College of Electrical and Information Engineering， Beijing University of Civil Engineering and Architecture， Beijing 100044， China）

Abstract： The traditional Monte Carlo localization algorithm has the defects of low positioning precision and inaccurate positioning due to the low efficiency of node sampling. Therefore， an improved least squares fitting Monte Carlo localization （LSFMCL） algorithm is proposed. The algorithm is adopted to optimize the sampling space by taking advantage of MBC algorithm， fit the node motion trajectory with least square method to predict the location of nodes， and then obtain the optimal sampling area. The weight concept is proposed to calculate the location of the unknown node by using the weight information of the predicted node. The simulation results show that， in comparison with traditional algorithm， the optimized algorithm can improve the sampling rate of the node and positioning accuracy， and has wider application prospect for the localization of the mobile nodes.

Keywords： Monte Carlo location algorithm； MBC algorithm； least square fitting； mobile node localization； motion trajectory； weight concept

0 引 言

無線傳感器網絡技術（Wireless Sensor Networks，WSN）作為21世紀發展的熱點，具有很多別的技術所沒有的優點，如監測范圍廣、運行成本低、網絡自組織性好等。目前，傳感器網絡廣泛地應用在智能家居、建筑防火、環境監測、軍事偵察等領域[1]。

WSN技術的節點定位主要是指已知自身位置的節點通過某種測量方法來定位未知節點位置的方法。因此作為WSN熱門技術之一的節點定位算法有不同的分類標準。根據是否需要測距分為基于測距的定位算法和無需測距的定位算法。典型的基于測距的定位算法包括TOA（Time of Advent）定位算法[2]、TDOA（Time Difference Of Arrival）定位算法[3]、 RSSI（Received Signal Strength Indication）定位算法[4]、AOA（Angle of Arrival）定位算法[5]等，而典型的無需測距的定位算法包括質心算法[6]、DV?Hop 算法[7]、Amorphous 算法[8?9]、APIT 算法[10]等。根據WSN中傳感器節點是否能夠移動，節點的定位算法分為靜態定位（Static Localization）和動態定位（Dynamic Localization）兩種類別。目前對于傳統靜態WSN的定位技術方面已有不少典型的算法，如質心定位算法[11]、凸規劃定位算法[12]、SPA相對定位算法[13]等都是靜態定位算法。但是由于實際應用中，大多數的節點都是運動的，傳統的靜態節點定位不能捕捉到節點的運動，會造成很大的定位誤差。因此，如何定位移動節點成為WSN技術的一個熱點。

MCL（Monte Carlo Localization）[14]定位算法是最早提出定位移動節點的一種算法，也是最典型的一種移動節點定位方法。但是這種算法對采樣數據要求太高，進而提出MBC算法[15]。MBC算法對粒子采樣空間進行了有效優化，但是錨節點較少時，誤差仍然較大。

利用最小二乘擬合的蒙特卡羅移動定位算法不僅通過MCB算法來獲取歷史節點，減少算法初始誤差；同時還能預測移動節點的運動軌跡，降低采樣次數，提高采樣率。

1 蒙特卡羅定位算法

1.1 蒙特卡羅定位算法

蒙特卡羅定位算法是用來表示感知與運動的概率模型的粒子濾波過程，能在復雜網絡定位中較精準定位。定位階段包括預測和濾波。預測階段是根據節點的速度信息和在前一定位時刻的粒子集信息來確定采樣區域，并隨機釆樣得到粒子位置信息[16]。濾波階段通過錨節點信息對預測階段得到的粒子進行篩選，舍棄不滿足條件的粒子，并且記錄能夠符合濾波條件的粒子，然后利用它們的均值來估計節點的位置。如果濾波后的粒子數不能滿足定位所需粒子的數目，就需要執行重采樣與濾波過程，直到得到足夠的粒子數或者釆樣次數到達最大為止[17]。

1.2 蒙特卡羅定位算法內容

MCL算法定位階段包括預測和濾波，節點移動方式按照隨機行走模型（Random Walk Model，RWM）進行，RWM模型是移動WSN最常見的運動模型之一。在RWM模型中，節點速度和位置都是未知的，僅有節點最大運動速率[vmax]已知，并且方向不確定。假設上一時刻的節點粒子集為[lt-1]，則目前時刻的節點可能位置存在于以[lt-1]為圓心，以[vmax]為半徑的圓內。其中目前時刻的粒子集為[lt]。用[d（l1，l2）]表示兩個點[l1]，[l2]之間的歐幾里德距離，且節點速率在[[0，vmax]]之間滿足均勻分布，則狀態轉移概率密度函數[p（ltlt-1）]為：

[p（ltlt-1）=1πv2max，d（ltlt-1）

預測階段得到的集合[R]中的粒子，是從以[lt-1]為圓心，以[vmax]為半徑的圓形區域中隨機選擇出來的。這時的預測結果非常不精確，需要進行濾波。

在濾波階段，可以依據新的觀測信息，濾除掉滿足網絡連通度條件的樣本。文獻[18]給出了粒子濾波條件：

[filter（l）=?s∈S，d（l，s）≤r∧?s∈T，r

式中：r是通信半徑；[s]為錨節點集合。假如得到的位置樣本符合濾波條件，那么狀態轉移概率分布[p（ltlt-1）]函數的值為1，反之為0。

2 MCB定位算法

MCB算法是在 MCL算法基礎上提出的。相對于 MCL，MCB算法采用蒙特卡羅盒子采樣，有效改進了樣本區域。錨盒子采樣區間為：

[xmin=max（xi-di）ymin=max（yi-di） xmax=max（xi+di）ymax=max（yi+di） ] （3）

為了提高采樣區域的利用率，歷史節點的獲取通過由DV?Hop輔助的MCB算法來實現。作為一種非測距定位算法，DV?Hop算法主要根據網絡連通度進行節點間的計算。為了提高蒙特卡羅定位算法精度，采用了DV?Hop測距方法。

2.1 DV?Hop定位算法測距

DV?Hop測距步驟如下：

首先已知位置的錨節點向四周發射信號，使得錨節點的位置可以被周圍節點獲取。周圍節點如果通過1跳能獲取錨節點信息，記跳數為1，并向周圍轉發信息，如果節點通過多次轉發鄰節點信息后，跳數記最小值。

根據錨節點與錨節點的距離和跳數計算出跳距，然后根據未知節點和錨節點的距離及跳距計算出它們的距離[19]。跳距公式為：

[HopSizei=（xi-xj）2+（yi-yj）2hij] （4）

已知[n]個錨節點位置[xi=（xi，yi）（i=1，2，…，n）]，未知節點[x=（x，y）]與參考節點之間距離為[ri（i=1，2，…，n）]，得到：

[（x1-x）2+（y1-y）2（x2-x）2+（y2-y）2? （xn-x）2+（yn-y）2=r21r22?r2n] （5）

變換得到：

[Ax=b] （6）

則[A]與[b]分別為：

[A=2（xn-x1）2（yn-y1）2（xn-x2）2（yn-y2）??2（xn-xn-1）2（yn-yn-1）] （7）

[b=r21-r2n-x21-y21+x2n+y2nr22-r2n-x22-y22+x2n+y2n?r2n-1-r2n-x2n-1-y2n-1+x2n+y2n] （8）

對于計算[（x，y）]的位置，最小二乘算法能夠解決這類問題，使用式（9）進行計算：

[x=（ATA）-1ATb] （9）

2.2 MCB定位算法

通過式（9）計算出[（x，y）]，并進行[di]的計算：

[di=（xi-xj）2+（yi-yj）2] （10）

最后，通過傳統MCB采樣濾波得到節點估值位置。

3 最小二乘法擬合的蒙特卡羅定位算法

3.1 最小二乘擬合的基本原理

最小二乘法又被稱作最小平方法（ Least Square Method），是一種數學優化技術。最小二乘法能夠容易地得到未知數據的值，并能使數據實際值與計算值的差的平方和達到最小。此外最小二乘法用于曲線擬合可以使各種應用更貼合實際[20]。

對于給定的一組數據[（xi，yi）]（i=0，1，2，…，m），要求在函數空間[Φ=spanφ0，φ1，φ2，…，φn]能夠找到一個函數[y=S*（x）]，使誤差平方和最小：

[σ22=i=0mσ2=i=0mS?（xi）-yi2=i=0mS（xi）-yi2] （11）

式中：

[S（x）=a0φ0（x）+a1φ1（x）+…+anφn（x）] （12）

3.2 運動趨勢的預測

假設節點平滑的、連續的運動，通過節點歷史位置信息，利用最小二乘擬合的方法預測節點運動趨勢。LSFMCL（Least Squares Fitting Monte Carlo）定位算法中每個節點都保留著原來前三個時刻位置信息，通過已有歷史位置信息預測移動節點的運動趨勢。當新的位置信息產生后，將前三個時刻最早的位置信息替換掉，以此來不斷更新節點最新的三個歷史位置。假設節點前三個時刻[t1，t2，t3]（其中[t1

[xt=f（t）yt=g（t）] （13）

假設函數偏導數存在，即節點運動是平滑的并且連續的，對式（13）求偏導數，得到節點在t時刻x軸[y]軸方向的預測運動速度：

[vx=df（t）dtt=tn-1vy=dg（t）dtt=tn-1] （14）

由式（14）得到節點在t時刻的運動速度及方向：

[v=v2x+v2yα=arctanvyvx] （15）

根據節點的運動趨勢，在選擇預測的節點位置時首先以式（15）得到的節點運動速度[v]為半徑，以前一時刻的節點位置為圓心，以前一時刻的速度方向順時針和逆時針各展開[α+β]，滿足[α+β<π]，得到一個扇形。然后，隨機抽取位于扇形[N]個點作為預測點，其中越靠近預測的速度矢量，預測精度越高，稱為較優預測點。

3.3 節點位置計算

由圖1可知，在[α]角度附近的預測點的權值要比其他地方的預測點的權值高。預測節點的扇形橫向權值[wi1]的計算如下：

[wi1=1-βα+β] （16）

如果經過濾波后能夠得到符合要求的預測點小于[N]，且扇形的夾角不宜再變大，則此時向扇形速度方向擴展，稱為扇形縱向權值。假設拓展寬度為[γ]，如圖2所示，同時由于[α]較小，所以速度方向拓展部分可以看作是矩形，面積為[S]：

[S=γ2απv180°] （17）

預測節點的縱向權值[wi2]的計算如下：

[wi2=1-v2γ+v] （18）

當得到所有的權值以后，對權值進行歸一化處理，使得所有權值相加其和為1。

[wi=wjj=1Nwj， i=1，2，…，N ] （19）

計算未知節點在t時刻的位置為：

[xt=i=1Nwixiyt=i=1nwiyi ] （20）

4 仿真及結果分析

無線傳感器網絡連通度可以體現網絡魯棒性的好壞，是評估網絡結構的重要指標[21]。假設未知節點估計位置為（[xi]，[yi]），（[Xi]，[Yi]）表示待測節點實際位置，未知節點總數為[un]，定位誤差用[errori]表示。

誤差[errori]計算公式為：

[errori=（Xi-xi）2+（Yi-yi）2] （21）

平均定位誤差[e]計算公式為：

[e=errorun] （22）

假設節點分布在200 m×200 m的區域內，在此區域中均勻分布錨節點，節點移動方式按照RWM模型進行，所有節點的通信半徑為[r=25] m，移動節點最大速度[vmax≤2 m/s]，運動方向未知，采樣的節點數為[N=200]?？紤]到通信半徑對定位誤差的影響，分別取通信半徑為[r=25] m和[r=20] m，在不同的通信半徑下，所有待測節點的誤差圖如圖3所示。節點移動速度影響定位誤差，一般移動速度越大，定位誤差越大。

如圖3所示，當速度不同時，LSFMCL定位算法與MCB算法和傳統算法定位誤差的比較，LSFMCL定位算法明顯優于其他算法，此外當移動節點運動速度小于一定值時誤差隨速度增大有減小趨勢但變化不大，當移動節點速度超過一定值時，定位誤差逐漸增大。同時，對比不同的通信半徑的影響，r=20 m的誤差顯然小于r=25 m時的平均定位誤差。

圖4表現了隨著網絡連通度的提高，無線傳感器網絡定位誤差減小。仿真結果表明，在同樣的網絡連通度下，LSFMCL定位算法優于MCB算法，傳統的MCL算法最差。網絡連通度超過一定值時，定位誤差趨于穩定。

錨節點與定位誤差的關系如圖5所示，錨節點越多，定位誤差越小，定位精度越高，并且當錨節點數達到一定的值后，定位誤差趨于穩定。

如圖6所示，錨節點數對樣本采樣次數的影響很小，因為LSFMCL定位算法對節點運動進行了有效預測，有效地捕捉到節點運動方式，使得采樣次數大幅度減少，提高了運行效率，節省了運行時間。

5 結 語

改進后的算法從傳統定位算法誤差產生的原因出發，利用最小二乘擬合的算法預測節點運動趨勢，確定采樣區間，在一定范圍內提高了預測節點的有效率；并提出權值概念，根據預測節點距離運動方向[α]的遠近確定權值，進而計算出未知節點的位置。從實驗結果得出，傳統的MCL算法誤差太大，MCB定位誤差相比傳統MCL，定位精度和采樣率雖然有很大提高，但是采樣次數仍然很高，利用最小二乘擬合的算法預測節點運動趨勢的LSFMCL定位算法定位精度最高，魯棒性最好，可以被廣泛應用。

參考文獻

[1] DU Xiaoyu， SUN Lijuan， XIAO Fu， et al. Localization algorithm based on minimum condition number for wireless sensor networks [J]. Journal of electronics （China）， 2013， 30（1）： 25?33.

[2] 姜志鵬，陳正宇，劉影，等.TOA定位算法非線性優化問題研究[J].傳感技術學報，2015，28（11）：1716?1719.

JIANG Zhipeng， CHEN Zhengyu， LIU Ying， et al. TOA positioning algorithm nonlinear optimization problem research [J]. Chinese journal of sensors and actuators， 2015， 28（11）： 1716?1719.

[3] 張健，李鷗.改進的無線傳感器網絡TDOA定位算法[J].計算機工程與應用，2010，46（16）：171?120.

ZHANG Jian， LI Ou. Improved wireless sensor network TDOA positioning algorithm [J]. Computer engineering and applications， 2010， 46（16）： 171?120.

[4] 譚志，張卉.無線傳感器網絡RSSI定位算法的研究與改進[J].北京郵電大學學報，2013，36（3）：88?91.

TAN Zhi， ZHANG Hui. Research and improvement of RSSI localization algorithm in wireless sensor networks [J]. Journal of Beijing University of Posts and Telecommunications， 2013， 36（3）： 88?91.

[5] 諸燕平，黃大慶， 李勃.基于AOA的無線傳感器網絡節點定位算法[J].傳感器與微系統，2010，29（1）：98?101.

ZHU Yanping， HUANG Daqing， LI Bo. AOA based wireless sensor network node localization algorithm [J]. Sensor and micro system， 2010， 29（1）： 98?101.

[6] 劉皇保，王濤，彭剛.一種改進的質心定位算法[J].微型機與應用，2013，32（11）：73?75.

LIU Huangbao， WANG Tao， PENG Gang. An improved centroid localization algorithm [J]. Microcomputers and applications， 2013， 32（11）： 73?75.

[7] 衛開夏，田金鵬，王克謙.無線傳感器網絡 DV?Hop定位改進算法[J].傳感技術學報，2010，23（12）：1820?1824.

WEI Kaixia， TIAN Jinpeng， WANG Keqian. Improved DV?Hop localization algorithm for wireless sensor networks [J]. Chinese journal of sensors and actuators， 2010， 23（12）： 1820?1824.

[8] NAGPAL R， SHROBE H， BACHRACH J. Organizing a global coordinate system from local information on an Ad Hoc sensor network [J]. Information processing in sensor networks， 2003， 2634： 333?348.

[9] 安文秀，趙菊敏，李燈熬.基于Amorphous的無線傳感器網絡定位算法研究[J].傳感器與微系統，2013，32（2）：33?35.

AN Wenxiu， ZHAO Jumin， LI Dengao. Research on location algorithm of wireless sensor network based on Amorphous [J]. Sensor and microsystem， 2013， 32（2）： 33?35.

[10] 馮秀芳，崔秀鋒，祈會波.無線傳感器網絡中基于移動錨節點的APIT的改進定位算法[J].傳感技術學報，2011，24（2）：269?274.

FENG Xiufang， CUI Xiufeng， QI Huibo. An improved loca?lization algorithm for APIT based on mobile anchor nodes in wireless sensor networks， Journal of [J]. Chinese journal of sensors and actuators， 2011， 24（2）： 269?274.

[11] 李文辰，張雷.無線傳感器網絡加權質心定位算法研究[J].計算機仿真，2013，30（2）：191?194.

LI Wenchen， ZHANG Lei. Weighted centroid localization algorithm in wireless sensor networks [J]. Computer simulation， 2013， 30（2）： 191?194.

[12] 任克強，莊放望.移動錨節點凸規劃定位算法研究及改進[J].傳感技術學報，2014，27（10）：1406?1411.

REN Keqiang， ZHUANG Fangwang. Research on mobile anchor node convex programming and location algorithm and improvement [J]. Chinese journal of sensors and actuators， 2014， 27（10）： 1406?1411.

[13] 蘇進，萬江文，于寧.無線傳感器網絡相對定位算法研究[J].傳感技術學報，2007，20（12）：2695?2700.

SU Jin， WAN Jiangwen， YU Ning. Relative location algorithm for wireless sensor networks [J]. Chinese journal of sensors and actuators， 2007， 20（12）： 2695?2700.

[14] 梅舉，陳滌，辛玲.基于蒙特卡洛方法的移動傳感網節點定位優化算法[J].傳感技術學報，2013，26（5）：689?694.

MEI Ju， CHEN Di， XIN Ling. Based on Monte Carlo method for mobile sensor network node localization optimization algorithm [J]. Chinese journal of sensors and actuators， 2013， 26（5）： 689?694.

[15] 張銳恒，莊毅，趙振宇，等.基于MCB的傳感網移動目標定位算法[J].計算機科學，2012，39（8）：34?37.

ZHANG Ruiheng， ZHUANG Yi， ZHAO Zhenyu， et al. MBC based sensor network moving target localization algorithm [J]. Computer science， 2012， 39（8）： 34?37.

[16] 陳冰潔，黃小平，王巖.基于MDS技術與MCL方法的無線傳感器網絡移動節點定位算法[J].微型機與應用，2011，30（6）：88?91.

CHEN Bingjie， HUANG Xiaoping， WANG Yan. Wireless sensor network mobile node localization algorithm based on MDS technology and MCL method [J]. Micromachine and application， 2011， 30（6）： 88?91.

[17] 朱海平，于紅丞，鐘小勇，等.動態無線傳感器網絡的改進蒙特卡羅定位算法[J].傳感技術學報，2012，25（9）：1284?1288.

ZHU Haiping， YU Hongcheng， ZHONG Xiaoyong， et al. Improved Monte Carlo localization algorithm for dynamic wireless sensor networks [J]. Chinese journal of sensors and actuators， 2012， 25（9）： 1284?1288.

[18] 周春月，張洪婷.基于測距權重的蒙特卡羅定位改進算法[J].北京交通大學學報，2016，40（5）：63?69.

ZHOU Chunyue， ZHANG Hongting. Improved algorithm of Monte Carlo positioning based on distance weighting [J]. Journal of Beijing Jiaotong University， 2016， 40（5）： 63?69.

[19] 馬曉賢，彭力.一種改進的無線傳感器網絡DV?Hop定位算法[J].計算機工程與應用，2015，51（21）：97?101.

MA Xiaoxian， PENG Li. An improved DV?Hop localization algorithm for wireless sensor networks [J]. Computer engineering and applications， 2015， 51（21）： 97?101.

[20] 袁鑫，吳曉平，王國英.線性最小二乘法的RSSI定位精確計算方法[J].傳感技術學報，2014，27（10）：1412?1417.

YUAN Xin， WU Xiaoping， WANG Guoying. Accurate calculation method of RSSI location for linear least squares method [J]. Chinese journal of sensors and actuators， 2014， 27（10）： 1412?1417.

[21] 張慧敏，柴毅，許磊.無線傳感器網絡加權質心相對定位算法[J].計算機工程與應用，2010，46（28）：22?24.

ZHANG Huimin， CHAI Yi， XU Lei. Weighted centroid relative location algorithm in wireless sensor networks [J]. Computer engineering and applications， 2010， 46（28）： 22?24.