協作式無線傳感器網絡節點定位算法的研究
2009-01-01 00:00:00陳衛東李娜
計算機應用研究 2009年2期
（燕山大學 信息科學與技術學院， 河北 秦皇島 066004）
摘 要：提出了一種在三個錨節點的條件下基于到達角的測距方法，利用節點之間的幾何關系實現傳感器網絡中未知節點的定位。通過仿真驗證該方法能夠對未知節點進行有效的定位；同時，該方法僅依賴到達角信息來確定節點的位置，從而降低了處理的復雜度、節省了節點的能量、提高了節點的壽命。
關鍵詞：傳感節點定位；錨節點；到達角
中圖分類號：TP393.04 文獻標志碼：A
文章編號：10013695(2009)02053202
Collaborative localization technology in wireless sensor network
CHEN Weidong，LI Na
（College of Information Science Engineering， Yanshan University， Qinhuangdao 066004， China）Abstract:This paper proposed a algorithm for unknown nodes under three anchor node’s condition in wireless sensor networks based on AOA( angle of arrival) method and the geometrical relations among sensor nodes. The simulation proves the effective localization of the unknown node. Meanwhile， this method is only reply on the information of AOA to determine the location of nodes，thereby， reduces processing complexity while saving the energy of nodes which extends life expectancy of nodes.
Key words:sensor node localization; anchor node; AOA(angle of arrival)
無線傳感器網絡(wireless sensor networks，WSN)是由大量分布式傳感節點組成的面向任務的網絡，它綜合了微機電、傳感器、嵌入式計算、現代網絡及無線通信、分布式信息處理等多種領域技術，能夠協作地實時監測、感知和采集網絡分布區域內的各種環境或監測對象的信息，在環境監測、軍事偵察、生物醫療等方面具有廣泛的應用前景。但是對于大多數應用來說，不知道傳感器位置而感知的數據是沒有意義的，因此，傳感器節點的位置信息作為無線傳感器網絡的關鍵技術，對基于地理位置的網絡協議本身研究和無線傳感器網絡的基本應用都有重要的意義。
1 相關研究
無線傳感器網絡的定位是指自組織的網絡通過特定的方法提供節點的位置信息。當前無線傳感器網絡節點定位問題的研究一般基于以下前提：網絡中存在少量位置已知的節點，稱為錨節點或是信標節點(beacon node)，其坐標可以通過攜帶GPS定位設備或者其他手段在定位未知節點前獲得自身的位置信息。除錨節點以外的其他節點稱為未知節點(unknown node)，錨節點是網絡中未知節點的定位參考點。一般來說，錨節點被部署在指定區域中可以通過兩種方式：一種是確定放置，即通過操縱機器人或是人工安裝等方式將節點放置在預定的確定位置上；另外一種就是隨機拋撒，即通過炮彈彈射或飛機拋撒等方式將節點隨機地散布在監測區域內。
目前，無線傳感器網絡自定位算法主要分為兩類:基于測距的算法(rangebased)和非基于測距的算法(rangefree)。基于測距的方法是指未知節點首先測量出自己到多個錨節點的距離或角度信息，然后利用錨節點和未知節點之間的幾何關系，再根據三邊測量法、三角測量、最大似然估計等定位算法計算出自己的位置。常用的測距方法有TOA(time of arrival)[1]、TDOA(time difference of arrival)[2]、AOA[3]和RSSI(received signal strength indicator)算法[4]。非基于測距的算法與基于測距的算法的最大不同在于，未知節點并不是通過各種測量方法測量出自己與錨節點之間的距離或角度信息，而是利用節點間的估計距離、網絡連通性等信息估算出自己與錨節點間的距離。計算節點位置主要有APIT(approximate pointintriangulation test)算法[1]、質心算法[5]、DVHop算法[6]等。以上兩種定位技術各有優缺點，基于測距的定位技術精度最高，但對硬件要求也最高；基于非測距的定位技術精度較高。
2 定位算法的介紹
本文提出了一種在三個錨節點的條件下基于到達角的測距方法。這種算法需要未知節點確定與三個錨節點之間的夾角，因此需要節點具有接收天線或是陣列天線；除此之外還需要知道兩個錨節點之間的距離。它可通過兩點間距離公式得到：
d=(xi-xj)2+（yi-yj）2； i，j=1，2，…（1）
2.1 錨節點部署模型的建立
假設未知節點任意部署在監測區域中，每個節點都裝配有全方向的接收天線，并且節點間能夠雙向通信[7]。錨節點的部署方式采用確定放置方式，因此錨節點的坐標是已知的。為分析簡單起見，本文僅考慮二維情況，三維情況依此類推。
在二維平面中假設錨節點A1，A2，A3的坐標分別為（x1，y1），（x2，y2），（x3，y3），此坐標是已知的；用（x，y）表示未知節點U的坐標。部署錨節點的約束條件是三個錨節點中兩兩構成的三條直線中存在任意兩條直線是互相垂直的，所以對于錨節點的部署就有一定的要求。本文按照圖1的方式對錨節點進行部署[8]，但是部署點的坐標并不是已知的，也就是說錨節點的坐標是部署完畢后通過一些技術手段得到的，而且錨節點的部署距離也不要求必須等距。
a)將區域用互相垂直的直線分割，兩條直線的交點即為部署點。部署點的位置是預先確定的，其坐標存儲在每個傳感器的內存里。
b)將N個錨節點按部署點進行部署，令(xi，yi)表示第i個錨節點的坐標。
2.2 算法的描述
假設錨節點A1，A2，A3與未知節點間的到達角分別為α1、α2、α3，則根據到達角可以計算出β、γ。在上述模型中任意地選擇三個錨節點來計算未知節點的坐標。首先利用式（1）可計算出A1與A2、A3的距離d12，d13分別為
d12=(x2-x1)2+(y2-y1)2（2）
d13=(x3-x1)2+(y3-y1)2（3）
由于未知節點是隨機部署在區域中，錨節點與未知節點的位置關系就存在兩種可能：錨節點與未知節點共線和錨節點與未知節點不共線。首先考慮未知節點與錨節點共線的情況，此時又有兩種可能存在，如圖2所示。
a）U在直線A1A2上，則根據直角三角形的三角函數關系可得未知節點U的坐標x、y分別為
x=x1+d13cot β， y=y1=y2
b）U在直線A1A3上，則根據直角三角形的三角函數關系可得未知節點U的坐標x，y分別為
x=x1=x2， y=y1-d13cot γ
從圖2中不難發現，只要未知節點在由兩個錨節點構成的直線上，不論是沿哪個方向移動的都可以利用上述公式來確定未知節點的位置。
其次，考慮錨節點與未知節點不共線的情況，如圖3所示。此時假設節點的天線方向是豎直的，從圖中可看出
β=α3-α1， γ=α1+α2（4）
在△A1A3U和△A1A2U中，根據正弦定理分別有A1U/sin(π-β-δ)=d13/sin β，即有
A1U=d13sin(β+δ)/sin β（5）
A1U/sin(π-r-∠UA1A2)=d12/sin γ（6）
由前面的模型已知A1A2⊥A1A3， 所以有
∠UA1A2=π/2-δ（7）
將式（6）帶入式（5）可得到
A1U=d12cos(γ-δ)/sin γ（8）
由式（5）和（8）相等有
A1U=d13sin(β+δ)/sin β=d12cos(γ-δ)/sin γ（9）
將式（9）變形得到
d13sin γ/（d12sin β）=cos(γ-δ)/sin (β+δ)（10）
由式（10）解得tan δ=（cos γ-N sin β）/（N cos β-sin γ），即δ=arcta ((cos γ-N sin β)/(N cos β-sin γ))。其中
N=d13 sin γ/（d12sin β）（11）
綜上可以得到未知節點的坐標：
x=x1+A1U sinδ(12)
y=y1-A1U cosδ (13)
從錨節點與未知節點不共線的情況中可以看出，當 δ等于90°或0°時就是錨節點與未知節點共線的情況。并且將δ等于90°或0°時代入式（12）和（13）中，經過化簡便得到共線時未知節點U的坐標公式。因此，無論錨節點與未知節點共線與否都可以應用式（12）和（13）定位未知節點。
3 仿真結果
在現有對無線傳感器網絡的研究手段（實驗手段、數學建模和仿真手段）中，仿真手段具有高效性和低成本的特點，本文主要通過MATLAB仿真實驗來分析驗證本文所提出的方法。本文仿真數據是50次獨立仿真的結果。
在規則的二維平面上160個未知節點隨機分布在50 m×50 m的區域中。圖4給出了該區域內的節點真實位置分布與通過本算法后估計出的位置分布。其中圓圈所在處表示節點的真實位置，星號表示通過本算法后該節點的估計位置。
下面驗證不同參數時的定位誤差。無線傳感器網絡模型的主要參數如下：網絡規模為100個節點，其中有3個錨節點；節點分布在50 m×50 m的區域中，節點位置隨機生成并且服從均勻分布；到達角的誤差服從正態分布。采用文獻[9]的研究成果，如10%的到達角誤差表示為到達角誤差服從N（0，10%）。平均定位誤差定義如下：
[error]=Ni=1(xi-i)2+(yi-i)2/N
其中：(i，i)為節點i的位置坐標估計值；(xi，yi)為節點i的真實坐標值。仿真結果如圖5、6所示。
由圖5可知，到達角的誤差越大，定位誤差也越大；由圖6可以看出，定位誤差隨著節點數目的增加而增加，并且當節點數目到達80以后，定位誤差趨于穩定。
4 結束語
定位技術是無線傳感器網絡的一項關鍵技術，節點的定位信息是無線傳感器網絡基本的要求，定位的準確性直接關系到傳感器節點采集數據的有效性。本文介紹了無線傳感器網絡一種基于測距的協作式定位算法。該算法利用節點間的幾何關系實現定位，其僅依賴于到達角信息，降低了處理的復雜度，節省了節點的能量，更適合目前以低成本為目標、以單片機為核心的無線傳感器網絡。仿真實驗顯示：本文的方法能夠對未知節點進行有效的定位，并且定位精度較高。
參考文獻：
［1］HARTER A，HOPPER A，STEGGLES P.The anatomy of a context-aware application[J].Wireless Network，2002，8(23):187197.
[2]GIROD L，ESTRIN D.Robust range estimation using acoustic and multimodal sensing[C]//Proc ofIEEE International Conference on Intelligent Robots and Systems.2001:13121320.
[3]NICULESCU D，NAT H B.Ad hoc positioning system (APS) using AOA[C]//Proc of the 22nd Annual Joint Conference on IEEE Computer and Communications Societies.2003:17341743.
[4]GIROD L，BYCHOVSKIY V，ELSON J.Locating tiny sensors in time and space:a case study[C]//Proc of IEEE International Conference on Computer Design.2002:214219.
[5]BULUSU N，HEIDEMANN J，ESTRIN D.GPSless low cost outdoor localization for very small devices[J].IEEE Personal Communications Magazine，2000，7(5):2834.
[6]NICOLESCU D，NATH B.DV based positioning in Ad hoc networks[J].Journal of Telecommunication Systems，2003，22(1/4): 267280.
[7]FANG Lei，DU Wenliang，NING Peng.A beaconless location disco-very scheme for wireless sensor networks[C ]//Proc of the 24th Ann-ual Joint Conference IEEE Computer and Communications Societies.New York:Springer Publishing Computer，2005:161171.
[8]NASIPURI A，LI Kai.A directionality based location discovery scheme for wireless sensor networks[C]//Proc of the 1st ACM International Wireless Sensor Network and Applications.New York:ACM Press，2002:105111.
[9]WHITEHOUSE K，CULLER D.Calibration as parameter estimation in sensor network[C]//Proc of the 1st ACM International Wireless Sensor Network and Applications.New York:ACM Press，2002：5967.
