王照宇

【摘 要】在許多應(yīng)用中，無線傳感器網(wǎng)絡(luò)中節(jié)點(diǎn)的位置信息往往決定著網(wǎng)絡(luò)的功能和性能。為了解決移動無線傳感器網(wǎng)絡(luò)三維定位問題，提出了一種優(yōu)化的移動無線傳感器網(wǎng)絡(luò)定位算法。該算法在三維空間中利用在監(jiān)測區(qū)域內(nèi)隨機(jī)分布的固定錨節(jié)點(diǎn)，移動未知節(jié)點(diǎn)通過判斷是否是第一次收到或第一次沒有收到錨節(jié)點(diǎn)的位置信息，同時結(jié)合前一定位時刻移動未知節(jié)點(diǎn)的位置及距移動未知節(jié)點(diǎn)一跳和兩跳的固定錨節(jié)點(diǎn)的位置，縮小移動未知節(jié)點(diǎn)可能所在的區(qū)域范圍，進(jìn)而減小節(jié)點(diǎn)的定位誤差。通過計算機(jī)仿真發(fā)現(xiàn)與擴(kuò)展到三維空間的蒙特卡洛（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)護(hù)、車輛交通等許多領(lǐng)域都能找到它的身影[1-2]。在一些應(yīng)用中，節(jié)點(diǎn)是大量隨機(jī)部署在監(jiān)測區(qū)域內(nèi)并實時移動的，節(jié)點(diǎn)的地理位置信息無法獲得，然而許多時候只有明確了傳感器節(jié)點(diǎn)自身的位置，才能為用戶提供有用的監(jiān)測數(shù)據(jù)，為路由和拓?fù)浣Y(jié)構(gòu)的規(guī)劃提供依據(jù)，節(jié)點(diǎn)的位置信息是許多研究的基礎(chǔ)[3]。

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

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

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

2 蒙特卡羅定位算法

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

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

算法

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

5 結(jié)束語

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

參考文獻(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é)點(diǎn)自定位技術(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é)點(diǎn)的定位算法[J]. 計算機(jī)工程， 2008，34（20）： 107-108.

[7] 黃梅根，常新峰. 一種基于蒙特卡羅法的無線傳感器網(wǎng)絡(luò)移動節(jié)點(diǎn)定位算法研究[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.