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

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

關(guān)鍵詞：蜜源； 蜜蜂舞蹈； 無(wú)線傳感器網(wǎng)絡(luò)； 三維節(jié)點(diǎn)定位

中圖分類號(hào)：TP393 文獻(xiàn)標(biāo)志碼：A 文章編號(hào)：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

蜜蜂是群居性的昆蟲。根據(jù)德國(guó)著名生物學(xué)家弗里希對(duì)蜜蜂舞蹈行為的科學(xué)研究和實(shí)驗(yàn)，以舞蹈來(lái)表示蜜源的方向和距離，蜜蜂在直線爬行擺動(dòng)腹部時(shí)，用頭的朝向與重力線所成的角度表示蜜源位置與太陽(yáng)所成的角度，而太陽(yáng)在不同時(shí)刻的位置是不斷發(fā)生變化的^[1]。1973年，憑借對(duì)蜜蜂舞蹈的研究，弗里希榮獲諾貝爾獎(jiǎng)。

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

1 蜜源方向定位模型

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

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

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

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

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

2 NSLM算法

2.1 NSLM算法的原理

在三維坐標(biāo)空間中取三個(gè)錨節(jié)點(diǎn)，平移坐標(biāo)系，使其中一個(gè)錨節(jié)點(diǎn)與新坐標(biāo)系的原點(diǎn)重合，以三個(gè)錨節(jié)點(diǎn)所組成的三角形為底，以待定位節(jié)點(diǎn)為頂點(diǎn)構(gòu)造一個(gè)三棱錐。根據(jù)由信號(hào)強(qiáng)度測(cè)距法計(jì)算出的待定位節(jié)點(diǎn)到各錨節(jié)點(diǎn)的距離信息以及余弦定理求得相關(guān)角的角度，再利用蜜蜂蜜源定位思想求出待定位節(jié)點(diǎn)的相對(duì)位置，最后結(jié)合錨節(jié)點(diǎn)的坐標(biāo)信息求出待定位節(jié)點(diǎn)在三維空間中的坐標(biāo)。

2.2 NSLM算法的步驟

a）待定位節(jié)點(diǎn)通過監(jiān)聽錨節(jié)點(diǎn)的廣播信息，得到它們?cè)谌S空間位置中的坐標(biāo)信息，并監(jiān)聽錨節(jié)點(diǎn)的第二次廣播信息，得到各錨節(jié)點(diǎn)的信號(hào)在自己所在位置的信號(hào)強(qiáng)度，再利用信號(hào)傳播模型^[6，7]，將傳播損耗轉(zhuǎn)換為錨節(jié)點(diǎn)到待定位節(jié)點(diǎn)的距離

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

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

b）如圖2所示，A、B、C三點(diǎn)即為選擇的三個(gè)錨節(jié)點(diǎn)，P為待定位節(jié)點(diǎn)，A、B、C在原坐標(biāo)系中的坐標(biāo)分別為（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)。對(duì)原坐標(biāo)系實(shí)行平移變換得新坐標(biāo)系XYZ，使A點(diǎn)與新坐標(biāo)系XYZ的原點(diǎn)重合，則A、B、C均在或者近似在新坐標(biāo)系中XYZ平面上。圖2中，｜AP｜、｜BP｜及｜CP｜均已由式(3)求得。其中：A、B、C三個(gè)錨節(jié)點(diǎn)之間的兩兩距離可由坐標(biāo)信息計(jì)算得到，進(jìn)一步由余弦定理可求得∠BAP、∠CAP、∠BAC。

c）過P點(diǎn)在平面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坐標(biāo)由以下三式給出：

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）由于測(cè)距誤差以及定位計(jì)算中帶來(lái)的計(jì)算誤差都有可能引入定位誤差，需要對(duì)位置坐標(biāo)進(jìn)一步的修正。采用下列修正量對(duì)估計(jì)的位置坐標(biāo)進(jìn)行修正：

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

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

節(jié)點(diǎn)位置坐標(biāo)為pi=pi+Δi，循環(huán)執(zhí)行上述位置調(diào)整過程。當(dāng)Δi小于某一小量時(shí)，則停止坐標(biāo)調(diào)整，并認(rèn)為節(jié)點(diǎn)位置坐標(biāo)已接近真實(shí)位置值。

2.3 仿真

為了考察算法性能，使用NS2網(wǎng)絡(luò)仿真軟件進(jìn)行性能仿真。無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)分布在500×500×100，節(jié)點(diǎn)位置隨機(jī)生成并服從平均分布。測(cè)距誤差則服從正態(tài)分布，如20%的測(cè)距誤差表示測(cè)距誤差服從N（0，20%）。

不斷增加錨節(jié)點(diǎn)的數(shù)量，算法的平均定位誤差也不斷下降，當(dāng)測(cè)距誤差在15%的情況下，比較兩種算法的平均定位誤差及定位覆蓋率，如圖3、4所示。

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

3 結(jié)束語(yǔ)

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

參考文獻(xiàn):

[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]王建剛. 無(wú)線傳感器網(wǎng)絡(luò)分布式節(jié)點(diǎn)定位算法研究[D].西安：西北工業(yè)大學(xué)，2006.

[5]呂良彬，曹陽(yáng)，高洵，等.基于球殼交集的傳感器網(wǎng)絡(luò)三維定位算法[J].北京郵電大學(xué)學(xué)報(bào)， 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.