一種優化的移動無線傳感器網絡三維定位算法研究

王照宇

【摘 要】在許多應用中，無線傳感器網絡中節點的位置信息往往決定著網絡的功能和性能。為了解決移動無線傳感器網絡三維定位問題，提出了一種優化的移動無線傳感器網絡定位算法。該算法在三維空間中利用在監測區域內隨機分布的固定錨節點，移動未知節點通過判斷是否是第一次收到或第一次沒有收到錨節點的位置信息，同時結合前一定位時刻移動未知節點的位置及距移動未知節點一跳和兩跳的固定錨節點的位置，縮小移動未知節點可能所在的區域范圍，進而減小節點的定位誤差。通過計算機仿真發現與擴展到三維空間的蒙特卡洛（MCL）定位算法相比，本算法具有較高的定位精度。

【關鍵詞】無線通信技術 定位 三維空間 無線傳感器網絡

Research on an Optimized Three-Dimensional Localization Algorithm in

Mobile Wireless Sensor Network

[Abstract] In many applications， the function and performance of wireless sensor network （WSN） depend on the location information of sensor nodes. In order to deal with the three-dimensional localization in WSN， an optimized localization algorithm for WSN was proposed in this paper. In the proposed algorithm， fixed anchor nodes are deployed randomly in the monitoring zone of the three-dimensional space. The mobile sensor node judges whether it is the first time that it receives or not receives the position information from anchor nodes. It also utilizes the position of itself in the previous localization time and the position information of anchor nodes that one hop and two hops apart from itself to reduce the location error. Simulation results show that， compared with the three-dimensional Monte Carlo localization （MCL） localization algorithm， the proposed localization algorithm has higher localization accuracy.

[Key words]wireless communication localization three-dimensional space WSN

1 引言

隨著無線通信和硬件技術的發展，無線傳感器網絡在現實中的應用范圍越來越廣。在環境監測、礦井安全、農業生產、疾病監護、車輛交通等許多領域都能找到它的身影[1-2]。在一些應用中，節點是大量隨機部署在監測區域內并實時移動的，節點的地理位置信息無法獲得，然而許多時候只有明確了傳感器節點自身的位置，才能為用戶提供有用的監測數據，為路由和拓撲結構的規劃提供依據，節點的位置信息是許多研究的基礎[3]。

早期的無線傳感器網絡定位算法主要針對二維平面空間的靜態網絡，節點位置固定不變，節點坐標也只有X和Y兩個維度，沒有考慮到節點的移動性和三維空間的情況。然而在許多傳感器應用領域，例如野生動物追蹤、洋流監測、車載網等，傳感器節點的位置是隨時間變化的，對節點位置的測量也要提供三維坐標。因此對移動傳感器網絡三維定位算法的研究非常重要[4-5]。

在移動傳感器網絡中比較常見的定位方法是為一部分固定節點裝配GPS全球定位系統，稱之為固定錨節點，其余的移動未知節點利用這些錨節點的位置信息來估算自身的位置。例如，有文獻提出在監測區域內隨機部署一定數量的固定錨節點，基于蒙特卡羅算法，移動節點首先根據上一時刻的位置對當前自身的位置進行預測，估算移動節點可能所在的位置區域當作樣本，然后利用距該移動節點一跳和兩跳范圍內的固定錨節點的位置信息對樣本進行過濾，篩選出滿足錨節點限定條件的樣本值，再進行交叉操作和變異操作，對采樣進行優化，最后對篩選出的樣本坐標取平均，記作移動節點當前的位置坐標[6]。還有文獻提出移動節點根據自身的移動速度，生成相對距離約束，然后利用偵聽到的固定錨節點的位置信息和信息傳輸范圍來估算移動節點的位置，避免了蒙特卡羅算法中反復采樣的問題[7]。

在現有的移動傳感器網絡定位技術中，移動節點的采樣區域較大，節點的定位精度較低，并且主要針對二維平面空間，因此本文綜合考慮這些問題，提出了一種優化的移動傳感器網絡三維定位算法。本算法把傳統的移動傳感器網絡定位算法擴展到了三維空間中，利用移動未知節點是否是第一次收到和第一次沒有收到固定錨節點的位置信息，并綜合兩跳錨節點的位置信息，提高移動未知節點的定位精度。經過仿真發現與擴展到三維空間的蒙特卡羅定位算法相比，本算法可以有效提高移動未知節點的三維空間定位精度。

2 蒙特卡羅定位算法

蒙特卡羅定位算法在定位初始化階段，系統首先從網絡區域內隨機選擇N個樣本點形成初始的樣本集合L0={l10，l20，…，lN0}，然后重復預測階段和過濾階段實現移動未知節點的定位。在預測階段，移動未知節點根據節點的最大移動速度預測節點的位置，假設移動未知節點自身的實時移動速度未知，節點最大移動速率不超過Vmax。設在t-1時刻節點的位置是，則在t時刻節點的位置位于以為圓心，Vmax為半徑的圓內。其中Vmax越大，則采樣區域就越大，節點可能所在的位置區域也隨之增大。該算法通過在圓內反復采樣，便可由t-1時刻的樣本集合Lt-1得到t時刻的樣本集合Lt。在過濾階段，該算法利用距移動未知節點一跳和兩跳的固定錨節點的位置信息把不符合條件的樣本過濾掉。假設R是節點的通信半徑，則移動未知節點的樣本值位于距一跳錨節點距離為R的圓內，位于距兩跳錨節點距離為R和2R的圓環內。當過濾階段結束后，由于移動未知節點的一部分定位樣本被過濾掉，采集到的樣本數可能小于系統閾值，該算法將重復預測和過濾過程，直到移動未知節點采集到足夠的樣本值，最后計算這些樣本坐標的平均值作為移動未知節點當前的位置坐標[8]。

3 優化的移動無線傳感器網絡三維定位

算法

在傳統的基于蒙特卡羅算法的移動傳感器網絡節點定位中，移動未知節點可能所在的位置區域較大，節點的定位精度較低，并且目前的算法都是針對二維平面區域，在三維空間中無法應用。本文所提出的一種優化的移動傳感器網絡三維定位算法充分利用移動未知節點是否是第一次收到和第一次沒有收到固定錨節點的位置信息，滿足高精度定位的要求。

在該算法中無線傳感器網絡由在監測區域內部署的固定錨節點和移動未知節點組成。固定錨節點存儲有自身及一跳范圍內的鄰居錨節點的位置信息，其余的移動未知節點在網絡內隨機移動，固定錨節點在每個定位時刻廣播其存儲的錨節點位置信息。當移動未知節點進入到某個固定錨節點的通信區域內時，則認為移動未知節點可以接收到該錨節點廣播的位置信息，移動未知節點基于此信息來計算自身的實時坐標。

3.1 初始定位區域的確定

當固定錨節點在監測區域內部署完畢后，移動未知節點開始在網絡內自由移動，移動速度不固定。假設所有節點的通信距離為R，移動未知節點最大移動速度為Vmax，系統間隔時間T對移動未知節點進行一次定位，則移動未知節點在每個定位間隔內最大的移動距離為Smax=T*Vmax。為了保證本算法的有效性，需要限定系統的定位間隔，使Smax

假設移動未知節點在上一定位時刻的位置為M，因為在每個定位間隔內移動未知節點最大移動距離為Smax，則在當前定位時刻，移動未知節點N位于以點M為球心，以Smax為半徑的球內，如圖1所示：

3.2 定位區域的篩選及確定

固定錨節點在每個定位時刻廣播其自身的位置信息及距該錨節點一跳范圍內的鄰居錨節點的位置信息和節點ID號。移動未知節點在收到固定錨節點廣播的信息后，記錄該固定錨節點和其鄰居錨節點的信息，這些錨節點都是該移動未知節點的一跳或兩跳錨節點。如果某錨節點僅是移動未知節點的兩跳錨節點，則把該錨節點記為兩跳錨節點，否則記為一跳錨節點。然后移動未知節點判斷當前收到的一跳錨節點ID號與前一定位時刻收到的一跳錨節點ID號是否存在不相同的ID號。如果存在不同的ID號，則把當前定位時刻新偵聽到的一跳錨節點記作第一次偵聽到的一跳錨節點，前一定位時刻偵聽到而在當前定位時刻沒有偵聽到的一跳錨節點記作第一次沒有偵聽到的一跳錨節點。

在當前定位時刻，如果移動未知節點不是第一次收到或第一次沒有收到某一跳錨節點廣播的信息，則移動未知節點N位于以該一跳錨節點A為球心，R為半徑的球內。同時移動未知節點N還位于以距其兩跳距離的固定錨節點B為球心，半徑為R和2R的球殼內，如圖2所示：

如果移動未知節點在當前定位時刻第一次偵聽到某一跳錨節點廣播的信息，則移動未知節點距該一跳錨節點最近的距離為R-Smax（上一定位時刻移動未知節點剛好位于該錨節點的通信區域外），最遠的距離為R（當前定位時刻移動未知節點剛好位于該錨節點的通信區域內），移動未知節點N位于以該固定錨節點C為球心，半徑為R-Smax和R的球殼內。如果移動未知節點在當前定位時刻第一次沒有偵聽到某一跳錨節點廣播的信息，則移動未知節點距該固定錨節點最近的距離為R（當前定位時刻移動未知節點剛好位于該錨節點通信區域外），最遠的距離為R+Smax（上一定位時刻移動未知節點剛好位于該錨節點的通信區域內），移動未知節點N位于以該固定錨節點D為球心，半徑為R和R+Smax的球殼內，如圖3所示。

移動未知節點在綜合考慮以上限定因素后，取這些限定區域的交集區域作為移動未知節點可能所在的區域范圍，采用網格掃描法[9]計算該交集區域中心的坐標，記作當前定位時刻移動未知節點的位置坐標。

如果上一定位時刻移動未知節點的定位誤差較大，則在當前定位時刻移動未知節點基于偵聽到的固定錨節點的限定區域和基于上一定位時刻位置的限定區域可能沒有交集，無法計算移動未知節點的位置坐標。因此當以上限定區域沒有交集區域時，則首先利用距移動未知節點一跳和兩跳的固定錨節點的坐標計算移動未知節點可能所在的區域范圍，然后計算該區域中心的坐標作為移動未知節點當前定位時刻的位置坐標。如果移動未知節點在當前定位時刻沒有偵聽到固定錨節點，則把移動未知節點上一定位時刻的位置坐標記作當前定位時刻的位置坐標。

4 仿真結果和分析

因為MCL定位算法是一種二維空間定位算法，而本文提出的一種優化的移動傳感器網絡三維定位算法針對三維空間，所以本文將MCL定位算法擴展到三維空間中，增加定位維度，通過改變不同的系統參數，在移動未知節點定位精度方面和本算法進行對比。

在仿真模型中假設節點部署區域為100 m×100 m

×100 m，固定錨節點和移動未知節點的通信半徑均為R，固定錨節點個數為m個，移動未知節點個數為n個，則固定錨節點密度為Ad=m/（n+m），所有節點隨機部署在網絡區域內。移動未知節點采用隨機步行移動模型[10]，在網絡區域內隨機移動，在兩個定位時刻之間，移動未知節點的移動速度在[0， Vmax]范圍內隨機變化，移動方向隨機選擇，在每個定位間隔內的最大移動距離小于R。在仿真結果分析中為了方便起見，將Smax和平均定位誤差均用R表示，例如當節點通信半徑R=30 m，Smax=9 m時，則將Smax用0.3R表示。仿真中的移動未知節點的定位誤差為所有移動未知節點定位誤差的平均值。

當改變移動未知節點的最大移動距離時，取所有節點的總數為300個，固定錨節點密度為10%，本算法和擴展MCL定位算法的移動未知節點平均定位誤差如圖4所示。從圖4可以看出當最大移動距離為0.7R時，擴展MCL定位算法的平均定位誤差為0.529R，本算法的平均定位誤差為0.496R，比擴展MCL定位算法減少了6.37%。

當改變固定錨節點密度時，取所有節點的總數為300個，移動未知節點在每個定位間隔內最大移動距離為0.4R，本算法和擴展MCL定位算法的移動未知節點平均定位誤差如圖5所示。從圖5可以看出當固定錨節點數量較少時，在本算法中每個定位時刻第一次收到和第一次沒有收到的固定錨節點數量很小，定位誤差和擴展MCL定位算法相比優勢不明顯。隨著固定錨節點數量的增加，本算法的定位誤差明顯減小，當固定錨節點密度為20%時，本算法的定位誤差為0.171R，比擴展MCL定位算法減少了11.6%。

5 結束語

本文針對移動傳感器網絡MCL定位算法中節點定位精度較低和定位范圍為二維空間的問題，提出了一種優化的移動傳感器網絡三維定位算法，引入了移動未知節點對第一次收到和第一次沒有收到固定一跳錨節點信息的判斷，減小了未知節點的所在區域范圍。在與擴展MCL定位算法的仿真結果對比中，本文提出的定位算法在定位精度方面要優于擴展MCL定位算法，尤其當移動未知節點在每個定位間隔內的最大移動距離較小時，定位精度的優勢體現的更為明顯。

參考文獻：

[1] Akyildiz I F， Su W， Sankarasubramaniam Y. A Survey on Sensor Networks[J]. IEEE Communications Magazine， 2002，40（8）： 535-539.

[2] 周正. 無線傳感器網絡的節點自定位技術[J]. 中興通訊技術， 2005，11（4）： 51-56.

[3] V Potdar， A Sharif， E Chang. Wireless Sensor Networks： A Survey[A]. International Conference on Advanced Information Networking and Applications Workshops[C]. 2009： 393-422.

[4] P Amitangshu. Localization Algorithms in Wireless Sensor Networks Current Approaches and Future Challenges[J]. Network Protocols and Algorithms， 2010（1）： 45-74.

[5] C H Ou， K F Su. Sensor Position Determination with Flying Anchors in Three-Dimensional Wireless Sensor Networks[J]. IEEE Transactions on Mobile Computing， 2008（9）： 1084-1097.

[6] 宋琛，羅娟. 無線傳感器網絡移動節點的定位算法[J]. 計算機工程， 2008，34（20）： 107-108.

[7] 黃梅根，常新峰. 一種基于蒙特卡羅法的無線傳感器網絡移動節點定位算法研究[J]. 傳感技術學報， 2010，23（4）： 562-566.

[8] Hu L， Evans D. Localization for Mobile Sensor Networks[A]. In Proceedings of the10th Annual International Conference on Mobile Computing and Networking[C]. 2004： 45-47.

[9] 朱紅霞，陳曙. 一種新的基于非測距的無線傳感器網絡三維定位算法[J]. 傳感技術學報， 2009，22（11）： 1655-1660.

[10] Davies V A， Vanessa C， Davies A. Evaluating Mobility Models within an Ad Hoc Network[D]. Colorado School of Mines， 2000.