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

陶琳， 楊俊成， 楊新鋒

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

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

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

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

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

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

0 引言

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

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

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

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

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

2 幾何學(xué)定位算法描述

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

2.1 模型建立

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

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

(a)

(b)

(c)

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

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

算法的具體步驟如下：

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

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

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

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

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

圖3 幾何學(xué)算法流程

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

2.3 位置估計(jì)

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

3 仿真測試

(1)網(wǎng)絡(luò)場景設(shè)置

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

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

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

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

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

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

如圖5所示:

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

如圖7所示。

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

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

(a)通信半徑R=10

(b)通信半徑R=20

(c)通信半徑R=30

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

(a)通信半徑R=10

(b)通信半徑R=20

(c)通信半徑R=30

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

4 總結(jié)

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

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

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

[3] 劉剛, 周興社, 谷建華等. 自組織、自適應(yīng)無線傳感器網(wǎng)絡(luò)理論研究[J]. 計(jì)算機(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] 劉影, 錢志鴻, 劉月一, 張旭. 基于幾何學(xué)的無線傳感器網(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)重點(diǎn)計(jì)劃項(xiàng)目(112102210500)

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

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

TP393

A

2016.05.10)