一種優(yōu)化的移動無線傳感器網(wǎng)絡(luò)三維定位算法研究

王照宇

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

【關(guān)鍵詞】無線通信技術(shù) 定位 三維空間 無線傳感器網(wǎng)絡(luò)

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 引言

隨著無線通信和硬件技術(shù)的發(fā)展，無線傳感器網(wǎng)絡(luò)在現(xiàn)實中的應(yīng)用范圍越來越廣。在環(huán)境監(jiān)測、礦井安全、農(nóng)業(yè)生產(chǎn)、疾病監(jiān)護、車輛交通等許多領(lǐng)域都能找到它的身影[1-2]。在一些應(yīng)用中，節(jié)點是大量隨機部署在監(jiān)測區(qū)域內(nèi)并實時移動的，節(jié)點的地理位置信息無法獲得，然而許多時候只有明確了傳感器節(jié)點自身的位置，才能為用戶提供有用的監(jiān)測數(shù)據(jù)，為路由和拓?fù)浣Y(jié)構(gòu)的規(guī)劃提供依據(jù)，節(jié)點的位置信息是許多研究的基礎(chǔ)[3]。

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

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

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

2 蒙特卡羅定位算法

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

3 優(yōu)化的移動無線傳感器網(wǎng)絡(luò)三維定位

算法

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

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

3.1 初始定位區(qū)域的確定

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

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

3.2 定位區(qū)域的篩選及確定

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

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

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

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

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

4 仿真結(jié)果和分析

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

在仿真模型中假設(shè)節(jié)點部署區(qū)域為100 m×100 m

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

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

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

5 結(jié)束語

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

參考文獻：

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

[2] 周正. 無線傳感器網(wǎng)絡(luò)的節(jié)點自定位技術(shù)[J]. 中興通訊技術(shù)， 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] 宋琛，羅娟. 無線傳感器網(wǎng)絡(luò)移動節(jié)點的定位算法[J]. 計算機工程， 2008，34（20）： 107-108.

[7] 黃梅根，常新峰. 一種基于蒙特卡羅法的無線傳感器網(wǎng)絡(luò)移動節(jié)點定位算法研究[J]. 傳感技術(shù)學(xué)報， 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] 朱紅霞，陳曙. 一種新的基于非測距的無線傳感器網(wǎng)絡(luò)三維定位算法[J]. 傳感技術(shù)學(xué)報， 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.