基于蜜源定位模型的無線傳感器三維定位算法

摘 要：根據德國動物學家弗里希對蜜蜂舞蹈行為的研究成果，提出了基于蜜蜂舞蹈的蜜源定位模型。無線傳感器網絡作為一種全新的信息獲取和處理技術，在許多領域均有著重大的應用價值和科研價值。而節點定位信息在無線傳感器網絡的應用中起著關鍵作用。針對目前有關二維平面節點定位算法難以推廣到三維空間的現狀，提出了無線傳感器網絡節點三維定位算法。仿真表明，該算法能有效地對三維空間中的傳感器節點進行定位，是一種可選的定位方案。

關鍵詞：蜜源； 蜜蜂舞蹈； 無線傳感器網絡； 三維節點定位

中圖分類號：TP393 文獻標志碼：A 文章編號：1001-3695(2008)08-2512-02

Three dimensional localization algorithm based on nectar source

localization model in wireless sensor network

ZHENG Shi-jue，LI Kai，ZHENG Zhen-hua，SU Ying

（Dept. of Computer Science， Huazhong Normal University， Wuhan 430079， China）

Abstract:According to German zoologist Frisch’s research on honeybee’s dance behavior， brought forward nectar source localization model based on honeybee dance. As a kind of brand-new information acquisition and the processing technology， the wireless sensor network had great significance in application and scientific research in many fields. But the node localization information played a key role in the application of wireless sensor network. In view of the present situation that the two-dimensional plane node localization algorithm was difficult to be practiced in the three-dimensional space， proposed three dimensio-nal localization algorithm in the wireless sensor network. Simulations indicate that the algorithm can carry out localization on sensor node in the three-dimensional space effectively and turns to be one kind of localization methods which can be applicable.

Key words:nectar source; honeybee dance; wireless sensor network; three dimensional localization

蜜蜂是群居性的昆蟲。根據德國著名生物學家弗里希對蜜蜂舞蹈行為的科學研究和實驗，以舞蹈來表示蜜源的方向和距離，蜜蜂在直線爬行擺動腹部時，用頭的朝向與重力線所成的角度表示蜜源位置與太陽所成的角度，而太陽在不同時刻的位置是不斷發生變化的^[1]。1973年，憑借對蜜蜂舞蹈的研究，弗里希榮獲諾貝爾獎。

無線傳感器網絡是由大量傳感器節點通過無線通信技術自組織構成的網絡，在環境監測和保護、醫療護理、 軍事領域以及其他一些危險的工業環境如井礦、核電廠等領域，無線傳感器網絡均有廣泛應用^[2]。在傳感器網絡中，位置信息對傳感器網絡的監測活動至關重要，因此，節點的準確定位在傳感器網絡的應用中起關鍵作用。在實際應用中，如智能塵埃網絡，使各節點懸浮在大氣中來探測空間不同位置的氣壓和溫度；海洋監測中，在海平面下不同深度放置節點進行水溫、洋流及生物活動探測等，都需要對節點進行三維定位。而前人關于無線傳感器網絡節點定位的研究基本上停留在二維平面定位算法的研究和分析上^[3，4]，因此，傳感器節點三維定位問題迫切需要得到解決。文獻[5]提出了一種基于球殼交集的APIS算法。本文從弗里希對蜜蜂舞蹈的研究出發，提出了蜜源定位模型，并將此思想應用到無線傳感器網絡節點定位中，最終提出了一種無線傳感器網絡節點三維定位算法(NSLM)。

1 蜜源方向定位模型

以蜂巢為原點的三維坐標空間中，如圖1所示。其中：（a）為示意圖；（b）為坐標圖。太陽在xoz平面內，用s表示;蜜源在xoy平面內，用b表示;在x軸上取一點p，設os與x軸所成角為α；ob與軸所成角為θ；os與ob所成角即蜜源與太陽所成的角為β，則

cos α cos θ=cos β (1)

θ即為蜜源的方向。太陽在不同時刻的位置是不斷發生變化的，為討論方便起見，假設太陽剛升起時為凌晨4時，落下為下午16時，所以α=π/12（t-4）（4≤t≤16）。由此可得蜜源的方向：

θ=arccos（cos β/（cos π/12）（t-4） ））（t≠10）

π/2 （t=10）(2)

2 NSLM算法

2.1 NSLM算法的原理

在三維坐標空間中取三個錨節點，平移坐標系，使其中一個錨節點與新坐標系的原點重合，以三個錨節點所組成的三角形為底，以待定位節點為頂點構造一個三棱錐。根據由信號強度測距法計算出的待定位節點到各錨節點的距離信息以及余弦定理求得相關角的角度，再利用蜜蜂蜜源定位思想求出待定位節點的相對位置，最后結合錨節點的坐標信息求出待定位節點在三維空間中的坐標。

2.2 NSLM算法的步驟

a）待定位節點通過監聽錨節點的廣播信息，得到它們在三維空間位置中的坐標信息，并監聽錨節點的第二次廣播信息，得到各錨節點的信號在自己所在位置的信號強度，再利用信號傳播模型^[6，7]，將傳播損耗轉換為錨節點到待定位節點的距離

d=PtGtGrλ2/[（4π）2Pr（d）L](3)

其中：Pt為發射機功率；Pr（d）是在距離d處的接收功率；Gt、Gr分別是發射天線和接收天線的增益；d是距離，單位為m；L為與傳播無關的系統損耗因子；λ是波長，單位為m。設監聽到的錨節點個數為n，從中隨機選三個點組成一個集合，組成互不相同的C3n個集合，分別計算Z值的方差，選取方差最小的集合，則該集合的三個點被選定。

b）如圖2所示，A、B、C三點即為選擇的三個錨節點，P為待定位節點，A、B、C在原坐標系中的坐標分別為（xA，yA，zA）、（xB，yB，zB）、（xC，yC，zC）。其中，xi，yi，zi＞0(i=A，B，C)。對原坐標系實行平移變換得新坐標系XYZ，使A點與新坐標系XYZ的原點重合，則A、B、C均在或者近似在新坐標系中XYZ平面上。圖2中，｜AP｜、｜BP｜及｜CP｜均已由式(3)求得。其中：A、B、C三個錨節點之間的兩兩距離可由坐標信息計算得到，進一步由余弦定理可求得∠BAP、∠CAP、∠BAC。

c）過P點在平面ABC上做垂線，垂足為Q，則平面PAQ⊥ABC，由蜜源的方向模型，即式(1)知

cos∠PAQ cos∠CAQ=cos∠CAP (4)

cos∠PAQ cos∠BAQ=cos∠BAP (5)

兩式相除，得cos∠CAQ/cos∠BAQ=cos CAP/cos BAP，而∠BAC=∠BAQ+∠CAQ。∠BAC可由b）求得，∠BAP、∠CAP可由b）求得。由式(4)可求得∠CAQ，再由式(4)可求得∠PAQ＝arccos （cos CAP/cos CAQ），即AP與平面ABC所成角為arccos （cos CAP/cos CAQ），｜AQ｜=｜AP｜cos PAQ。

d）AC與x軸所成角為arctan (yC-yA)/(xC-xA)，所以AQ與x軸所成角為arctan((yC-yA)/(xC-xA))+∠CAQ，從而P坐標由以下三式給出：

xP=xA+｜AQ｜cos（arctan(yC-yA)/(xC-xA))+∠CAQ）（6）

yP=yA+｜AQ｜sin（arctan(yC-yA)/(xC-xA))+∠CAQ）（7）

zP=zA+｜AP｜cos∠PAQ(8)

e）由于測距誤差以及定位計算中帶來的計算誤差都有可能引入定位誤差，需要對位置坐標進一步的修正。采用下列修正量對估計的位置坐標進行修正：

Δi=j∈Teij（dij-dij） fij (9)

其中：dij為待定位節點到步驟a）中所選擇錨節點的距離，即dij=｜pi-pj｜，pi、pj為節點i、 j的位置坐標，dij為測算距離；eij為方向單位矢量，eij=（pi-pj）/dij； fij為錨節點數量占總節點數量的百分比，取值為(0 ，1)；集合T為a）選擇的所有錨節點的集合。

節點位置坐標為pi=pi+Δi，循環執行上述位置調整過程。當Δi小于某一小量時，則停止坐標調整，并認為節點位置坐標已接近真實位置值。

2.3 仿真

為了考察算法性能，使用NS2網絡仿真軟件進行性能仿真。無線傳感器網絡節點分布在500×500×100，節點位置隨機生成并服從平均分布。測距誤差則服從正態分布，如20%的測距誤差表示測距誤差服從N（0，20%）。

不斷增加錨節點的數量，算法的平均定位誤差也不斷下降，當測距誤差在15%的情況下，比較兩種算法的平均定位誤差及定位覆蓋率，如圖3、4所示。

從圖中可以看出， APIS算法的定位覆蓋率受錨節點數量變化的影響很大，而NSLM算法的定位覆蓋率始終保持很高。盡管有時測距誤差會很大從而影響定位誤差，但是， 隨著錨節點數量的增加， NSLM算法的平均定位誤差均小于APIS算法。

3 結束語

目前，有關無線傳感器網絡的三維定位研究還處于起步階段，NSLM算法能保證絕大部分未知節點被定位，特別是在沒有障礙物的空間中，有比較好的定位精度，能有效地實現三維空間環境中的傳感器節點定位，是一種可選的三維定位方案，并且隨著硬件技術的進步，將更加適合傳感器網絡小型化、低成本化的需求。

參考文獻:

[1]FRISCH V.The dance language and orientation of bees[M].New York:Harvard University Press， 1967.

[2]CALLAWAY E H. Wireless sensor networks: architectures and protocols [M].Boca Raton :CRC Press，2004:1-40.

[3]SAHINOGLU Z. Hybrid TOA/RSS and TDOA/RSS location estimation schemes for short-range wireless networks [J].Bechtel Telecommunication Technical Journal， 2004，2(2):77-84.

[4]王建剛. 無線傳感器網絡分布式節點定位算法研究[D].西安：西北工業大學，2006.

[5]呂良彬，曹陽，高洵，等.基于球殼交集的傳感器網絡三維定位算法[J].北京郵電大學學報， 2006，29(5): 48-51.

[6]BULUSU N， HEIDEMANN J ， ESTRIN D.GPS-less low cost outdoor localization for very small devices[J].IEEE Personal Communications Magazine， 2000，7(5):28-34.

[7]AKYILDIZ L F ， SU Y ， SANKARASUBRAMANIAM Y ，et al .A survey on sensor networks[J].IEEE Communication Magazine，2002，40(8):102-114.