無線網絡的移動節點定位方法研究

孫苑瑩

(長春理工大學 電子信息工程學院， 吉林 長春　130022)

?

無線網絡的移動節點定位方法研究

孫苑瑩

(長春理工大學 電子信息工程學院， 吉林 長春130022)

摘要：到達時間差算法(TDOA)是通過測量移動節點接收兩個已知節點發射信號的時間差值估算距離，但移動節點需在通信范圍內；DV-hop根據節點之間跳數測距,但估算誤差較大。將兩種方法相結合，在不增加網絡硬件的條件下，提高了定位精度。

關鍵詞：無線傳感器網絡； 移動節點； 定位

0引言

無線傳感器節點一般是由傳感、數據處理、電池等模塊組成的，并通過自組織的方式工作，它們將信息通過采集、提取、傳輸到電腦，操作者可以通過電腦獲定位信息，隨機分布的傳感器節點構成了無線傳感器網絡系統。在無線傳感器網絡中，已知位置坐標的節點叫做錨節點，不確定位置坐標的節點叫未知節點[1]。

在無線傳感器網絡中，獲取未知固定節點位置坐標信息通過無線傳感器網絡本身是可以完成的，但若是節點的位置坐標是移動不定的，若通過給移動節點裝上 GPS而定位其坐標，經濟上就會出現困難，所以就需要對移動節點的定位方法進行進一步深入研究。

無線傳感器網絡定位方法依據是否需要測距主要分兩種:一種是測距定位,首先測量已知節點到未知節點的距離，再根據測量的距離進行定位；另一種是非測距的定位計算。文中采用的是測距定位計算其位置坐標。

1基于測距算法

1.1　RSSI測距算法

已知移動節點的發射功率，當已知節點接收到移動節點發射出來的功率時，接收到的功率在傳播時一定會有損耗，該算法利用消耗功率值來計算已知節點到未知節點的距離。

優點：不需要額外的成本，比較容易實現測距算法。

缺點：如果需要精確的距離信息時，就得需要較多的已知節點，并且在傳播過程中，若不是在直線傳播等因素的情況下，會造成結果的不準確[2]。

1.2　AOA測距算法

節點上配置天線，通過天線已知節點獲取與未知節點的角度，從而計算出已知節點到未知節點的距離。

優點：需要的已知節點數目少并且定位的精度比較高。

缺點：配置上天線后，對于節點電量損耗比較大，與普通節點相比成本也提高了。

1.3　到達時間差法

到達時間差法的基本內容：測量不同的已知節點接到同一移動節點信號的時間差，通過時間差來建立雙曲線方程，從而計算已知節點到未知節點的距離。當進行空間定位的時候，已知節點的數目要大于3個。

優點：算法簡單而且易行性強，精度比RSSI測距算法還要高且應用廣泛。

缺點：在計算信號時間差的時候，已知節點接收移動節點的信號時，容易受到其它信號的影響，導致有一定的誤差。

1.4　DV-hop 算法

DV-hop 算法分為3步：

1)計算出已知節點間的平均跳數和每跳的平均距離；

2)測量出已知節點到移動節點的跳數;

3)用跳數乘以每跳平均距離就是已知節點到未知節點的距離。

優點：測量已知節點到移動節點間的距離不受外界因素的影響。

缺點：測量精度低，計算量多。

2定位算法

2.1　質心算法

已知節點向周圍未知節點發射信號，信號的信息是已知節點的位置，當未知節點接收到的信號超過一個之前設置好的數量之后，那么未知節點就位于這些已知節點組成圖形的質心上。

優點：算法比較簡單，容易實現。

缺點：這是一種估計的算法，故精度不是很高，它的精度和已知節點的密度成正比。

2.2　凸規劃定位(Convex Position Estimation)算法

將已知節點到未知節點的通信視為一種幾何約束，把整個無線傳感器網絡看作一個凸集，將無線傳感器網絡移動節點的定位問題轉化為凸集優化問題。

優點：算法簡單，容易執行。

缺點：節點的估算會因為已知節點必須分布位置而做偏移[3]。

2.3　三邊測量法

已知3個不同的已知節點到同一移動節點的距離，那么移動節點一定在以已知節點為圓心到未知節點距離為半徑的3個圓的交點上。

優點：方法原理簡單而且使用起來也很容易。

缺點：有可能由于誤差原因，移動節點不在3個圓的交點上，這種情況就使得該算法無法估計出移動節點的位置。

3算法的建立

定位算法的好壞可以由多方面決定，例如是否節能、精度高低、定位范圍廣度等，文中的主要思想就是不增加組件的前提下提高算法的精度。由上文分析可知，到達時間差法定位算法雖然定位誤差小，但是定位時有一定的局限性，一旦已知節點無法接到移動節點信號時，就無法進行定位；而DV-hop 算法雖然定位誤差大，但對移動節點的位置沒有限制要求。故文中結合兩種算法的優缺點[4]，用到達時間差法定位算法彌補DV-hop 算法定位精度低的缺點，用DV-hop 算法彌補到達時間差法的定位位置限制的缺點，得到移動節點的距離后，用三邊測量法對移動節點進行位置定位。

算法的流程如圖1所示。

圖1　流程圖

其中N表示移動節點接收到已知節點信息的個數。

算法分為3個步驟：

1)到達時間差法測得已知節點到移動節點的距離。

首先，已知節點發送信號，當移動節點處在多于兩個已知節點的通信射程范圍時，就直接用到達時間差法算得距離，具體算法如下：移動節點到任意兩個已知節點的距離差為固定值d時，移動節點一定位于以兩個已知節點為焦點的雙曲線上，用兩雙曲線組成的方程解出的交點坐標即為移動節點的位置坐標[5]，此算法原理圖如圖2所示。

圖2　TDOA定位算法幾何原理圖

用到達時間差法測距之后，用三邊定位法計算移動節點的位置坐標。如果當移動節點所處的通信范圍內，少于3個已知節點對其進行測距，則用步驟2)DV-hop 來測距。

2)DV-hop 算法測得已知節點到移動節點的距離。

經過步驟1)，可以完成已知節點通信范圍內的移動節點測距，如測得三邊定位所需邊中的一些長度，其余邊的長度需要用 DV-hop算法來計算。

DV-hop算法如下[6]:

第1部分：計算得出移動節點與已知節點之間的跳數最小值。相鄰已知節點接收到各個已知節點的跳數信息，比較接收送來的跳數信息后，留下小的數據，舍棄大的跳數數據，并將此跳數數據發給其相鄰已知節點，以此方法計算已知節點最小跳數值。

第2部分：獲取移動節點與已知節點間實際距離。根據第1部分得出的最小跳數，可得出每跳實際距離[7]:

(1)

式中：(xj,yj)，(xi,yi)----已知節點j和i的位置坐標；

hj----已知j最小跳數。

此時，網絡中的移動節點分兩類:

第1類：移動節點在一些已知節點的通信范圍內，即移動節點可以通過到達時間差法測距，這時可以忽略已知節點向移動節點發送有關跳數數據，但移動節點如果接收到其它已知節點發送來的跳數信息，則這些移動節點的測距問題要靠DV-hop算法來計算；

第2類：移動節點不在已知節點的通信范圍內，就可以直接用DV-hop定位算法計算。

3)三邊定位方法估算移動節點位置坐標[8]。

通過上面兩步，移動節點測得了到達已知節點的3個以上的距離。分別通過到達時間差法和DV-hop 算法測得，這時即可利用三邊定位算法計算出移動節點的位置坐標。

三邊法的幾何原理如圖3所示。

圖3　三邊測量法

如果未知節點M到已知節點A，B，C的距離分別為d1，d2，d3，那么M一定位于以A，B，C為圓心，d1，d2，d3為半徑的3個圓的交點上。由此可計算出移動節點M的位置坐標。

4結語

論述了無線傳感器網絡中對移動節點的定位方法，提出了基于無線傳感器網絡的移動節點定位研究的新方法。此方法理論上簡單明了，結合了到達時間差法和DV-hop 算法的優缺點計算距離，并用三邊定位方法估算位置，不僅節約了無線傳感器網絡定位的時間，而且提高了無線傳感器網絡定位的精度，簡單易行。

參考文獻：

[1]Langendoen K, Reijers N. Distributed localization in wireless sensor networks: A quantitative comparison The Int'1 Journal of Computer and Telecommunications Networking[J]. Electronic Industry Press,2003，43(4)：499-518.

[2]王雪,錢志鴻,胡正超,等.基于二叉樹的RFID防碰撞算法的研究[J].通信學報,2010,31(6):49-57.

[3]Yi Shang, Wheeler Ruml, Ying Zhang. Localization from mere connectivity[C]//MobiHoc ’03, Annapolis. Maryland, USA:[s.n.],2003：201-212.

[4]Shih E. Physical layer driven algorithm and protocol design for energy-efficient Wireless sensor networks[C]//Proceedings of the Senventh Annual International Conference on Mobile Computing and Networks (MobiCOM 01). Rome Italy:[s.n.],2001：272-286.

[5]錢志鴻,王義君.物聯網技術與應用研究[J].電子學報,2012,40(5):1023-1029.

[6]余光偉.自主移動機器人路徑規劃方法研究[D]:[碩士學位論文].長春：長春工業大學電氣與電子工程學院,2010:3-4.

[7]崔莉,鞠海玲,苗勇,等.無線傳感器網絡研究進展[J].計算機研究與發展,2005,42(1)：163-174.

[8]王楠.移動無線傳感器網絡定位問題的研究[J].遼寧工程技術大學學報，2010(1):14-16.

Mobile node localization in a Wireless Sensor Network

SUN Yuan-ying

(College of Electronics and Information Engineering, Changchun University of Science and Technology, Changchun 130022， China)

Abstract：Time Difference of Arrival (TDOA) algorithm is used to estimate the distance with the time difference of transmitting signals between the two receiving nodes but the nodes should be in the range of communication, while the DV-hop algorithm is applied to predict the distance according to the numbers of hop but with more error. We combine the two to obtain the high position accuracy under the same hardware environment.

Key words：Wireless Sensor Network (WSN); mobile node; positioning.

作者簡介：孫苑瑩(1990-)，女，漢族，吉林梅河口人，長春理工大學碩士研究生，主要從事無線傳感器網絡定位問題研究,E-mail:540929616@qq.com.

收稿日期：2014-06-08

中圖分類號：TP 732

文獻標志碼：A

文章編號：1674-1374(2015)01-0057-04

DOI:10.15923/j.cnki.cn22-1382/t.2015.1.12