一種改進DV-HOP無線傳感器網絡定位算法

鄔春明，楊　濤，馬冬梅，郭　健，趙宇新

(1.東北電力大學 信息工程學院，吉林 吉林 132012；2.國網吉林供電公司 信息通信分公司，吉林 吉林 132012)

?

一種改進DV-HOP無線傳感器網絡定位算法

鄔春明1，楊濤1，馬冬梅2，郭健2，趙宇新2

(1.東北電力大學 信息工程學院，吉林 吉林 132012；2.國網吉林供電公司 信息通信分公司，吉林 吉林 132012)

針對大型網絡不規則性及翻轉歧義造成距離向量-跳段(DV-HOP) 定位算法性能較差的問題，提出了一種改進的DV-HOP定位算法。針對不規則網絡，提出了一種基于節點密度的誤差修正方法。網絡區域部署節點數量大，節點翻轉歧義誤差不可避免，故提出了一種基于半圓模型的定位誤差修正方法。仿真實驗表明：本文改進算法比現有改進算法的定位精度提高了6%，并且能夠有效地弱化翻轉歧義造成的誤差，因此能夠較好地實現對未知節點的實時精準定位。

距離向量-跳段；節點密度；翻轉歧義；半圓模型；無線傳感器

0　引言

目前，無線傳感器網絡應用于越來越多的領域，而且對監測事物的坐標精度要求越來越高。通常，裝有全球定位系統 (globalpositioningsystem，GPS)裝置的傳感器節點能夠實現較高的定位精度，但其定位成本太高，若能找到一種利用少量裝有GPS裝置的傳感器節點就能實現對未知節點定位的算法，則無線傳感器網絡的節點定位成本將大大降低。因此，無線傳感器網絡定位算法的研究成為科研工作者的關注重點[1-2]。

距離向量-跳段(distancevector-hop,DV-HOP)定位算法通過計算網絡中平均跳距和跳數方式來計算未知節點與錨節點之間的距離，從而利用三邊測距或極大似然法計算未知節點的坐標。影響其定位精度的因素有網絡的不規則、平均跳距值的誤差和節點的翻轉歧義誤差等[3-4]。翻轉歧義誤差的定位算法主要弱化其對算法精度的影響，例如，文獻[5]中IIBM算法(iterativeinflexiblebodymergingalgorithm)、文獻[6]中IP-TNB算法(iterativeprocessingmethodbasedontriangularnodeblocks)和文獻[7]中RAMP算法(refinementalgorithmbasedontheideaofmagneticpole)。IIBM算法提出了一種基于節點塊狀合并的翻轉歧義修正算法，但由于該算法使用了多種節點塊形狀，造成變形，同時其通信開銷也較大。為了解決該問題，文獻[6]提出了IP-TNB算法，該算法主要運用了穩定性更好的三角節點塊和網絡連通度信息對其進行修正，但是該算法容錯性較差，并且對測距誤差敏感。針對不規則網絡造成的定位誤差，文獻[8]提出無線傳感器網絡DV-HOP算法的一種優化方法，該方法利用多個信標節點的平均跳距值的加權處理值替代節點間平均跳距值，再利用交叉粒子群算法對定位結果進行優化，該算法能夠使精度提高，但是計算量較大，且未考慮網絡中存在的節點翻轉歧義問題，故仍存在改進空間。因此，本文針對不規則網絡和翻轉歧義造成的定位誤差，提出了一種適用于農田環境的改進DV-HOP定位算法。

1　基于節點密度的誤差修正方法

由于大型網絡區域的節點是通過飛機隨機部署的，容易形成不規則網絡，區域內的節點密度不同，如圖1所示。圖1中：S1,S2,S3,S4和S5均為錨節點，A為未知節點，各錨節點通過網絡中其他錨節點計算其平均跳距，并將該值廣播至全網，各未知節點保存第1次接收到的平均跳距。節點S1的平均跳距通過與其他4個錨節點之間的歐氏距離和跳數計算而來。顯然，利用保存的平均跳距，節點A到錨節點S2、S3、S4和S5的距離值與真實值之間存在誤差，這將影響節點的定位精度。

圖1　大型網絡區域節點分布圖

針對上述問題，本文提出了基于密度的節點誤差修正方法。先定義幾個符號含義：

HopCounti為未知節點到錨節點的跳數；NodeCount為節點周圍1跳節點的數量；a_ID、s_ID和rec_ID 分別為錨節點、傳感器節點和接收節點的ID號。

假設在某一區域內至少有兩個錨節點,錨節點i廣播一個含有{a_IDi，s_IDi，Pos，HopCounti}的消息，并將s_IDi初始化為a_IDi，HopCounti初始化為0，當一鄰居節點接收到該消息后，a_IDi，s_IDi和Pos保持不變，HopCounti加1，該鄰居節點保留這一新消息，并將s_IDi保存至rec_IDj，同時將s_IDi設置為s_IDj。事實上，每次鄰居節點收到消息后都會檢查rec_IDj是否與之前收到值相同，若不同，則保留，同時NodeCountj加1。按上述方式繼續向全網廣播，最終各錨節點也會檢查rec_IDj與之前保存值s_IDi是否相同，若不同，則NodeCounti加1，則各節點可以統計出周圍節點數量。利用下式可求出各節點周圍節點密度：

(1)

由式(1)可知：n_ratej越小，節點的密度越靠近，若n_ratej<β，則可認為這兩個節點處于同一密度區域內(β為閾值，在本文中設定β為0.15)。但是有一些邊界節點并不符合這一規律，故在本文中，若某一節點不與任何節點處于同一密度區域，則將其視為與其最近的錨節點具有相同的密度區域。在同一密度區域的節點保存該區域內由錨節點廣播的平均跳距hop_len。至此，節點分區完畢，下一步將計算未知節點到各錨節點之間的距離值。

首先，每個錨節點廣播消息至全網，當某一未知節點收到該消息后，檢查HopCounti是否小于之前收到值，若滿足，則HopCounti加1，并向全網繼續廣播，否則丟棄該消息；其次，同時檢查收到的hop_len是否等于之前保存值，若相同，則利用下式計算該未知節點距離目標錨節點的距離值：

new_ddis=hopleni+a_dis,

(2)

其中：new_adis為某一未知節點距目標錨節點的距離值;a_dis為最短路徑中上一中繼節點更新的距離值。若不相同，則利用下式計算該未知節點距離目標錨節點的距離值：

new_adis=hoplenj+a_dis,

(3)

其中：hoplenj為該未知節點保存的平均跳距值。

每個未知節點同時可作為中繼節點轉發消息，其中,未知節點的new_adis保存至a_dis中，并伴隨消息廣播至全網。最終,各未知節點可計算出與各錨節點的距離值，再利用三邊測量法或極大似然法計算未知節點的坐標值。

2　基于半圓模型的弱化節點的翻轉歧義誤差修正方法

圖2　節點分布圖

針對大型無線傳感器網絡產生的翻轉歧義誤差，本文提出了基于半圓模型的弱化節點的翻轉歧義誤差修正方法。節點分布圖見圖2。圖2中：P為未知節點；A、B、C為錨節點。節點P利用三邊測量法計算節點的坐標時，若錨節點A、B、C呈線性關系，則節點P計算出的坐標存在一個鏡像坐標P′，該鏡像坐標繼續參與其他節點定位，則會造成整個算法的定位精度降低，這種誤差被稱為“翻轉歧義誤差”[9]。

該誤差修正方法由兩步組成：節點翻轉歧義誤差檢測和誤差修正。其中，節點翻轉歧義誤差檢測是通過文獻[7]提出的“跳數-距離矛盾”理論來檢測節點是否存在翻轉歧義誤差。“跳數-距離矛盾”理論為：當某一節點與鄰居節點之間的距離大于最大通信半徑或與二跳節點的距離小于最大通信半徑時，則認為其存在“跳數-距離矛盾”。為了具體描述這種矛盾的大小，提出了下面的公式：

(4)

(5)

(6)

若Ei(k)滿足以下條件：

(7)

則該節點存在翻轉歧義誤差，需要對其進行誤差修正；反之，則為有效節點。其中：Wi為節點i周圍1跳節點的數量。

圖3　半圓模型節點分布圖

為了弱化節點翻轉歧義誤差，提出半圓模型方法，該方法通過縮小誤差節點所在的誤差區域面積，同時利用射線法及最小二乘法計算節點的最小誤差坐標。半圓模型節點分布圖如圖3所示。圖3中：節點P存在翻轉歧義誤差；A、B和C為節點P的3個鄰居錨節點；R為最大通信半徑。以A、B、C為圓心，R為半徑，分別作圓，則節點P所在的最大誤差面積為3個圓的相交部分。

若節點C更靠近節點A，則以A為圓心， dac為半徑作圓；反之則以B為圓心， dbc為半徑作圓，誤差節點所在區域圖如圖4所示。首先分析第1種情況，半圓與魚形橢圓的相交，將魚形橢圓分為S1、S2兩部分，則節點P位于S1或S2區域內。若滿足條件RSSIAC>RSSIPC，則位于S1區域內；反之，則位于S2區域內。按照相同的方式，可判斷第2種情況下，節點位于S3或S4區域內。

圖4　誤差節點所在區域圖

圖5　節點P新的所在區域面積圖

假定Mn={M1,M2,…,Mn}為錨節點C周圍的一系列有效節點，分別以這些節點為圓心，dMn,C為半徑作圓，則可得到一系列的半圓SCS(Mn,C)={SCS(M1,C),SCS(M2,C),…,SCS(Mv,C)}。圖5為節點P新的所在區域面積圖。圖5中：SCS(M1,C)為以M1圓心，dM1,C為半徑的半圓，則半圓與S1相交部分為S5，再比較RSSIM1C與RSSIPC的大小，則可判斷節點P所在的區域。

事實上，每次作半圓后判斷RSSIMnC與RSSIPC的大小都可以得到一個新的位置區域面積，最終可以獲得一個誤差節點所在的最小區域面積，如圖6所示。圖6中：Sf為最小區域面積。

圖6　節點P的最小區域面積

假定Uv={U1,U2,…,Uv}為節點P周圍一系列有效節點，以Uv為圓心，dUv,p為半徑作圓，則可得到一系列與Sf的交點。由于最小誤差區域為形狀不規則的區域，本文采用射線法判斷這些節點是否位于最小誤差區域內部。射線法原理如下：

作一系列以交點的縱坐標k的射線，并讓射線穿過Sf，若射線與最小誤差區域的交點個數為奇數時，則該點位于該區域內，反之則不在。射線的可用公式表示如下：

(8)

其中：(xc,yc),(xp,yp)分別為節點C和節點P的坐標。

為了從這些區域內部的交點中選出節點P的最小誤差坐標，首先定義了以下公式：

(9)

其中：W為所有的鄰居節點；dij為節點i與節點j之間的歐氏距離。

利用上述方法即可求出節點P的最小誤差坐標，從而提高定位精度。

3　仿真實驗

為了驗證本文算法的性能，采用MATLAB7.0對其進行仿真，并與經典DV-HOP算法、文獻[8]中的DV-HOP算法和文獻[10]中的DV-HOP算法進行比較分析。

3.1仿真參數設置

在實驗中，為了與大型隨機部署節點的無線傳感器網絡特性相符合，首先，在150 m×150 m正方形區域內按相同某一通信半徑R隨機部署了100個節點，并在不同的通信半徑情況下，通過部署不同的錨節點數量去驗證算法的性能；其次，為了分析節點數量對算法精度的影響，固定最大通信半徑20 m，錨節點數量所占比例為0.15，在該區域內改變節點的數量，分別部署50～300個節點，分析其對節點定位誤差的影響。定義未知節點的平均定位誤差公式為：

(10)

(11)

3.2實驗結果分析

圖7是最大通信半徑分別為20 m和30 m時，節點的歸一化平均定位誤差隨區域內錨節點數量的關系。從圖7可以看出：隨著錨節點數量增多，節點的定位誤差開始下降，并最終趨于穩定。本文算法的性能優于其他3種算法，這是因為本文算法計算的未知節點到錨節點之間的距離值更接近真實值，且本文提出的翻轉歧義修正方法能夠有效地弱化節點翻轉歧義造成的誤差。

固定錨節點數量為15個，并將最大通信半徑從30 m到60 m變化，觀察其對節點定位精度的影響，其結果如圖8所示。由圖8可知:本文算法的性能優于其他3種算法，節點的平均定位誤差下降緩慢并最終趨于穩定，且節點的最大通信半徑為40 m時，這4種算法均能夠獲得一個較好的定位精度。

圖9顯示了節點數量對節點定位精度的影響。由圖9可知:隨著節點數量增加，前3種算法的定位誤差是一個先下降后平穩，然后再上升再平穩的過程，但本文算法的定位誤差則是先下降后逐步平穩，故其性能更優。主要是因為隨著節點數量增多，網絡連通度提高，節點定位精度也隨之提高。此外，網絡中隨著節點數量的增加，發生節點翻轉歧義誤差的概率會增大，而本文算法正好能夠弱化其誤差。

圖7　節點的歸一化平均定位誤差隨區域內錨節點數量的關系

4　結束語

本文針對大型不規則無線傳感器網絡及節點產生的翻轉歧義誤差對定位算法精度的影響，提出了一種改進DV-HOP算法。該算法針對不規則網絡提出了一種基于密度的誤差修正方法來修正未知節點與各錨節點之間的距離值。同時，針對節點存在翻轉歧義誤差，提出了一種基于半圓模型的誤差修正方法。本文算法能夠有效地提高定位精度，其定位性能優于經典DV-HOP定位算法及其改進算法。

[1]BEN S Y,BLAUNSTEIN N.Localization and positioning of any subscriber in indoor environments on the basis of analysis of joint AOA-TOA signal distribution[C]//IEEE APS Topical Conference on Antennas and Propagation in Wireless Communications.2013.

[2]KONE C T,HAFID A,BOUSHABA M.Performance management of IEEE 802.15.4 wireless sensor network for precision agriculture[J].IEEE sensors journal,2015,15(10):5734-5747.

[3]WANG Y,FANG Z Y,CHEN L.A new type of weighted DV-Hop algorithm based on correction factor in WSNs[J].Journal of communications,2014,9(9):699-705.

[4]WANG S Z,LI Y.Node localization algorithm based on RSSI in wireless sensor network[C]//Proceedings of 2012 6th International Conference on Signal Processing and Communication Systems.2012.

[5]XIAO Q J,XIAO B,BU K.Iterative localization of wireless sensor networks:an accurate and robust approach[J].IEEE/ACM transactions on networking,2014,22(2):1-14.

[6]董恩清,劉偉,宋洋.采用三角形節點塊處理無線傳感器網絡節點定位中節點翻轉歧義的迭代方法[J].西安交通大學學報,2015,49(4):1-7.

[7]YAO Y B,JIANG N L.Distributed refinement algorithm for WSN localization[J].Journal on communications,2015,36(1):1-10.

[8]李海龍,李寶華,韓彥春.無線傳感器網絡DV-Hop算法的一種優化方法[J].遼寧工程技術大學學報(自然科學版),2016,35(5):523-528.

[9]LIU W,DONG E Q,SONG Y,et al.An improved flip ambiguity detection algorithm in wireless sensor networks node localization[C]//21st International Conference on Telecommunications(ICT).2014.

[10]鄔春明,張金強,焦龍龍.基于RSSI跳數連續的DV-HOP改進算法[J].重慶郵電大學學報(自然科學版),2015,27(2):184-188.

國家自然科學基金項目(61301257);吉林省科技發展計劃基金項目(20130206050GX)

鄔春明(1966-),男,吉林省吉林市人,教授,碩士,碩士生導師,主要研究方向為無線傳感器網絡節點定位算法.

2016-05-16

1672-6871(2016)06-0055-06

10.15926/j.cnki.issn1672-6871.2016.06.012

TN92

A