基于幾何學的無線傳感器網絡節點定位算法研究

陶琳， 楊俊成， 楊新鋒

(1.河南工業職業技術學院 電子信息工程系， 南陽 473003 2.南陽理工學院 計算機與信息工程學院， 南陽 473003)

基于幾何學的無線傳感器網絡節點定位算法研究

陶琳1， 楊俊成1， 楊新鋒2

(1.河南工業職業技術學院 電子信息工程系， 南陽 473003 2.南陽理工學院 計算機與信息工程學院， 南陽 473003)

將幾何學中的斜率概念引入到無線傳感器網絡定位算法中，提出了一種分析錨節點之間位置關系的方法，并給出了一種基于幾何學的定位方案。在二維平面上定位一個目標節點需要3個位置已知的錨節點，這3個錨節點的選取是非常重要的，如果未知節點所選取的錨節點位置不合理將無法定位出節點的位置，因此，節點在定位前根據提出的方案選出最優的錨節點組合，然后再進行定位，可以提高定位的準確性。為定位算法中錨節點的選取提供可靠依據，從而達到了提高定位精度和定位覆蓋率的效果。

無線傳感器網絡； 節點定位； 幾何學； 斜率

0 引言

無線傳感器網絡WSN(wireless sensor network)是一種由許多微型傳感器節點組成的自組織網絡，這些傳感器節點集成數據采集、數據處理和無線通信等功能，且它們具備制作成本低、功耗低、體積微小等特點，WSN已經成為一種新型的信息獲取和處理技術[1]。傳感器節點采集監測區域內的感知信息，通過中間節點進行一系列處理，并以多跳的方式傳輸給匯聚節點實現網絡自動監測；同時匯聚節點也可以向網絡中的傳感器節點傳輸控制指令來執行特殊任務。無線傳感器網絡改變了人類與自然界的交互方式，擴大了人類認知世界的能力[2]。美國商業周刊將無線傳感器網絡譽為21世紀最具有影響力的21項技術和改變世界的十大技術之一[3]。

無線傳感器網絡中每個傳感器節點搜集到監測的數據之后，通過無線通信的方式發送給匯聚節點，最終傳輸給管理者。在處理數據的過程中，最重要的是我們要知道數據的來源，是哪個位置的傳感器發來的數據，從而為用戶提供最有意義的數據[4]。傳感器節點可以配備GPS定位系統來獲得自身的絕對位置，但是受體積、價格和能耗的影響[5],每個節點都使用GPS系統并不適合于無線傳感器網絡[6]。在本文中，網絡中僅僅設置少量位置已知的節點，記為錨節點，其它節點是通過這些已知節點的位置信息，基于一些定位算法來獲得自身位置坐標，所以開發簡單和準確的定位算法是研究者的追求目標。

1 WSN定位技術的研究現狀

為了估計出未知節點的位置，錨節點與未知節點需要通過無線通信的方式彼此交互信息。由此產生兩種定位技術[7]：一種是基于測距的定位技術，利用硬件設備，例如超聲波、無線電和天線陣列等獲得節點之間的信號強度、到達時間以及到達角度，利用這些參數計算出未知節點到達錨節點的真實距離，從而估計未知節點的位置，是一種高精度的定位方法[8]；另一種是非測距的定位技術，利用網絡中的錨節點信息和網絡的連通度，間接得到錨節點與未知節點的距離，這種方法不需要測得節點間的真實距離，是一種粗粒度定位的方法。通過以上兩種方法得到了錨節點到未知節點的距離之后，采用位置計算的數學方法計算出節點的位置。

基于測距的定位算法的是依據錨節點到目標節點的距離或者角度進行定位。目前，具有代表性的定位算法有基于到達角度(Angle of Arrival, AOA)、基于到達時間(Time of Arrival, TOA)、基于到達時間差(Time difference of Arrival, TDOA)和基于信號接收強度指示(Received Signal Strength Indicator, RSSI)的定位方法。非測距定位算法是一種粗粒度定位估計方法，對于無線傳感器網絡某些應用也是可以滿足的，是一種追求低成本的定位技術，因此，這種方法也備受關注。目前，典型的非測距定位算法包括APS(DV-Hop、DV-distance、Euclidean)、APIT、Centroid、Amorphous等，在這些方法的基礎上，廣大學者針對非測距定位算法提出了新的定位方法。

2 幾何學定位算法描述

為更好地利用錨節點的信息，本文提出一種基于幾何學的定位算法。首先，我們使用幾何學中的斜率方法，即用斜率來判斷錨節點之間的分布關系。其次，又分析了當錨節點個數為3個和大于3個的時候，分別采用的不同方法來求解未知節點的位置。

2.1 模型建立

無線傳感器網絡定位的數學模型描述如下：假設設置m個傳感器節點(錨節點)，并且每個節點都知道自己的位置，二維空間坐標αk∈R2，k=1,2,…,m。n個傳感器節點(非錨節點)xj∈R2，j=1,2,…,n，這些節點稱為未知節點。在一個二維空間中，要想實現一個目標的定位，最少需要3點才能夠確定目標的位置。在二維平面中，兩個節點在平面的分布關系可以用斜率值表示，判斷任意一點與其它兩個點連線角度關系用斜率差表示，如圖1所示(如圖1(a)所示)。

3個黑色節點1、2、3為錨節點，空心u為未知節點，3個錨節點可以很容易求出未知節點u的位置。圖1(b)中錨節點4、5、6在同一條直線上，那從幾何角度考慮，這種分布的點是無法解出未知點u。圖1(c)中錨節點7、8、9雖然不是在一條直線上，但是趨近于直線，如果測距存在誤差，可能造成無法解出未知節點u。因此，本文提出一種方法來選取一種相對最優的錨節點組合。

(a)

(b)

(c)

2.2 錨節點最優組合選擇

在無線傳感器網絡中，DV-Hop屬于非測距的定位算法，不需要借助外在的硬件設備測量錨節點到未知節點的真實距離，從而減少了節點的成本開銷和能量消耗，此算法簡單、覆蓋度高和可行性好，所以這種定位算法被很多學者所青睞，在應用中是最有潛力的一種定位算法。但由于DV-Hop算法在錨節點位置選擇上不一定是最優的，會造成未知節點無法定位，尤其是未知節點接收到超過3個錨節點時，如果3個錨節點在一條直線節點將無法求解，嚴重影響網絡的整體定位精度。然而平面幾何學中的斜率方法可以判斷錨節點之間的位置關系，從而選取最優的錨節點序列，能夠更精確的確定未知節點的位置。同時分析了待定位節點的鄰居錨節點數量對定位精度的影響。

算法的具體步驟如下：

步驟1：網絡初始化

步驟2：計算網絡中所有錨節點的平均每跳距離值，并進行廣播

步驟3：未知節點對錨節點的選取。當網絡中的未知節點接收到錨節點平均每跳校正值時，判斷錨節點的個數，判斷的具體過程描述如下：(1)當錨節點數目小于3時，無法執行最小二乘定位；(2)當錨節點等于3時，判斷3點是否接近共線，如圖4.3所示，首先計算直線L1L2的斜率為K1，再計算直線L2L5，的斜率K2，當K2-K1的值越接近0的時候，3點越接近共線，利用這3個點計算未知節點的位置就不準確了，重新選擇錨節點；(3)當錨節點大于3時，首先選取最先接收到錨節點的信息作為參考節點，在從其余的錨節點中選取兩個錨節點進行定位，進行多次求出未知節點的位置，再把求出的位置求均值。如圖2所示。

如果待定位節點同時收到錨節點L1，L2，L3，L4，L5發送的信息包時，待定位節點將最先接收到L1的消息，把L1作為參考節點，分別從其它錨節點中選出兩個錨節點，構成3個錨節點，反回步驟(2)判斷3個錨節點是否共線。

幾何學算法的具體流程，如圖3所示。

圖3 幾何學算法流程

算法的初始化階段和平均每跳距離的求解步驟與DV-Hop算法相同，只有在選擇錨節點定位時本文采取斜率判斷法來獲得最優的錨節點組合，從而實現精準的定位。

2.3 位置估計

最后，根據最小二乘法估計出未知節點A的位置。以L1作為參考節點，分別從其它四個錨節點中選出兩個節點構成最小二乘定位，求出未知節點A的坐標，一共有6種組合，求出未知節點A有6個坐標A1(x1,y1)，A2(x2,y2)，A3(x3,y3)，A4(x4,y4)，A5(x5,y5)，A6(x6,y6)，之后對這六個坐標求平均，得到A(xreal,yreal)。

3 仿真測試

(1)網絡場景設置

使用MATLAB對無線傳感器網絡DV-Hop定位算法以及本文所提出的定位算法進行仿真，研究整個網絡中錨節點之間的位置關系和所選錨節點數量的最優組合對網絡性能的影響。實驗中采用的網絡拓撲結構：錨節點和未知節點都是隨機產生，錨節點分布在網絡中不同的位置。仿真參數設置為：網絡范圍100 m×100，節點數目100個，傳輸距離為10 m、20 m及30 m，錨節點個數為10、15、20、25、30、35、50。

(2)仿真結果與分析

隨著錨節點數量的增加，本文的幾何學定位算法定位誤差逐漸下降。圖4為網絡的拓撲結構圖，如圖4所示。

圖4 網絡節點分布圖

星節點為錨節點，當隨機播撒節點的時候，有些錨節點排列成直線分布，在一條直線上的3個點是無法定位出一個點的位置的，這樣用原始的DV-Hop算法定位，誤差將會很大。

仿真的橫坐標代表錨節點的個數;縱坐標為節點的定位精度，即平均定位誤差與通信半徑的百分比。實驗結果表明，隨著通信半徑的增加，錨節點數目相同的情況下，確實改進了網絡定位精度。

如圖5所示:

圖5(a)、(b)和(c)表示通信半徑R=10、20、30時本文定位算法(Geometric Location)與DV-Hop定位算法誤差的對比。在不同通信半徑下本文算法(Geometric Location)的定位誤差變化，如圖6所示。錨節點大于25時定位誤差明顯下降，如圖6所示。

如圖7所示。

圖7(a)、(b)和(c)表示表示通信半徑R=10、20、30時本文定位算法(geometric location)與DV-Hop定位算法定位率的對比，證明了通信半徑增加，可以提高定位率。在不同的通信半徑下本文定位算法(geometric location)定位率的變化關系，如圖8所示。

隨著錨節點增多本文算法的定位率在逐漸的提升。

(a)通信半徑R=10

(b)通信半徑R=20

(c)通信半徑R=30

圖6 不同通信半徑下Geometric Location的定位誤差對比

(a)通信半徑R=10

(b)通信半徑R=20

(c)通信半徑R=30

圖8 不同通信半徑下Geometric Location的定位率對比

4 總結

在無線傳感器網絡中，無論是基于測距的定位技術還是非測距定位技術錨節點的信息都是一個不可或缺的重要因素。本文將幾何學中的斜率概念引入到了無線傳感器網絡定位算法中，分析錨節點之間的位置關系對定位精度的影響，并給出一種基于此方法的定位方案。當未知節點定位時需對所選擇的錨節點組合進行分析處理，根據斜率判斷錨節點是否趨于一條直線或者未知節點與錨節點是否在一條直線，是則放棄，直到選出最優的錨節點組合；其次分析了待定位節點的鄰居錨節點數量對該定位算法定位精度的影響，提出了基于幾何學中斜率的方法找出錨節點最優組合的選擇策略，在不同的通信半徑下，該策略的定位精度和定位率相比DV-Hop定位算法都有很大的提升。此方法為定位算法中錨節點的選取提供可靠依據，從而達到了提高定位精度和定位覆蓋率的效果。

[1] 鄭增威, 吳朝暉, 金水祥. 無線傳感器網絡及其應用[J]. 計算機科學, 2003, 30(10): 138-140.

[2] 馬祖長, 孫怡寧, 梅濤. 無線傳感器網絡綜述[J]. 通信學報, 2004, 25(4): 114-124.

[3] 劉剛, 周興社, 谷建華等. 自組織、自適應無線傳感器網絡理論研究[J]. 計算機應用研究, 2005, 5: 30-33.

[4] Martusevicius V, Kazanavicius E. Self-localization system for wireless sensor network[J]. Elektronika Ir Elektrothchnika, 2010, 16(10): 17-20.

[5] Guoqiang Mao, Baris Fidan, Brian D.O.Anderson. Wireless sensor network localization techniques[J]. Computer Networks, 2007, 51(10): 2529-2553.

[6] Randolph L Moses, Dushyanth Krishnamurthy, Robert Patterson. A self-localization method for wireless sensor networks[J]. EURASIP Journal on Applied Signal Processing, 2003(4): 348-358.

[7] Chen J C, Hudson R E, Yao K. Maximum-likelihood source localization and unknown sensor location estimation for wideband signals in the near-filed[J]. IEEE Transaction on Signal Processing, 2002, 50(8):1843-1854.

[8] 劉影, 錢志鴻, 劉月一, 張旭. 基于幾何學的無線傳感器網絡定位算法[J]. 光電子·激光期刊, 2010, 10(21):1435-1438.

Research on Wireless Sensor Network Node Localization Algorithm Based on Geometry

Tao Lin1,Yang Juncheng1,Yang Xinfeng2

(1. Department of Electronic Information Engineering,Henan Polytechnic Institute,Nanyang 473004,China;2. School of Computer and Information Engineering,Nanyang Institute of Technology,Nanyang 473004,China)

It was the first time that the gradient concept of geometry was applied to the wireless sensor network localization algorithm. The method for analyzing the position relationship between anchor nodes has been investigated and given by the location of geometric algorithm. In two-dimensional plane, locating a target node requires three anchor nodes which have a significant selected position. If the selected anchor node doesn’t fit, this cannot locate the position of unknown node. Therefore, before localization, the optimum anchor node combination should be selected in accordance with the proposed scheme, and then locating these nodes can improve the accuracy of localization. This method provides reliable basis for the selection of anchor nodes in localization algorithm, and then improves location accuracy and location coverage.

Wireless sensor network; Node localization; Geometry; Gradient

河南省科技攻關重點計劃項目(112102210500)

陶 琳(1979-)，女，河南南陽人，工程碩士，講師，研究方向：計算機應用，南陽 473003 楊俊成(1982-)，男，河南南陽人，碩士，講師，研究方向：人工智能、嵌入式系統，南陽 473003 楊新鋒(1979-)，男，河南南陽人，碩士，副教授，研究方向：圖像處理，南陽 473003

1007-757X(2017)01-0026-04

TP393

A

2016.05.10)