陶琳， 楊俊成， 楊新鋒

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

基于幾何學的無線傳感器網(wǎng)絡(luò)節(jié)點定位算法研究

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

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

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

無線傳感器網(wǎng)絡(luò)； 節(jié)點定位； 幾何學； 斜率

0 引言

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

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

1 WSN定位技術(shù)的研究現(xiàn)狀

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

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

2 幾何學定位算法描述

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

2.1 模型建立

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

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

(a)

(b)

(c)

2.2 錨節(jié)點最優(yōu)組合選擇

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

算法的具體步驟如下：

步驟1：網(wǎng)絡(luò)初始化

步驟2：計算網(wǎng)絡(luò)中所有錨節(jié)點的平均每跳距離值，并進行廣播

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

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

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

圖3 幾何學算法流程

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

2.3 位置估計

最后，根據(jù)最小二乘法估計出未知節(jié)點A的位置。以L1作為參考節(jié)點，分別從其它四個錨節(jié)點中選出兩個節(jié)點構(gòu)成最小二乘定位，求出未知節(jié)點A的坐標，一共有6種組合，求出未知節(jié)點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)網(wǎng)絡(luò)場景設(shè)置

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

(2)仿真結(jié)果與分析

隨著錨節(jié)點數(shù)量的增加，本文的幾何學定位算法定位誤差逐漸下降。圖4為網(wǎng)絡(luò)的拓撲結(jié)構(gòu)圖，如圖4所示。

圖4 網(wǎng)絡(luò)節(jié)點分布圖

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

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

如圖5所示:

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

如圖7所示。

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

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

(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 總結(jié)

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

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

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

[3] 劉剛, 周興社, 谷建華等. 自組織、自適應(yīng)無線傳感器網(wǎng)絡(luò)理論研究[J]. 計算機應(yīng)用研究, 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] 劉影, 錢志鴻, 劉月一, 張旭. 基于幾何學的無線傳感器網(wǎng)絡(luò)定位算法[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

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

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

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

TP393

A

2016.05.10)