邱奉美，李懷忠，2

(1.溫州大學物理與電子信息工程學院，浙江 溫州 325035;2.埃迪斯科文大學計算機與安全科學學院，澳大利亞 柏斯6050)

1 概述

無線傳感器網(wǎng)絡(Wireless Sensor Network，WSN)是由部署在監(jiān)測區(qū)域內(nèi)的大量廉價微型傳感器節(jié)點，通過無線通信方式形成的一個多跳的自組織的網(wǎng)絡系統(tǒng)，其目的是協(xié)作地感知、采集和處理網(wǎng)絡覆蓋區(qū)域中被感知對象的信息，并發(fā)送給觀察者［1］。WSN 被廣泛應用于諸多領(lǐng)域，已成為計算機和通信領(lǐng)域的研究熱點。

基于WSN 的大量應用都離不開節(jié)點位置信息。節(jié)點定位技術(shù)屬于WSN 應用支撐技術(shù)，在WSN 體系中占有重要地位［2］。無線傳感器節(jié)點通常隨機布放在不同的環(huán)境中執(zhí)行各種監(jiān)測任務，以自組織的方式互相協(xié)調(diào)工作。隨機布放的傳感器節(jié)點無法事先預知自身位置，傳感器節(jié)點必須能在布放后實時進行定位。對大多數(shù)的應用，不知道節(jié)點位置而感知的數(shù)據(jù)是沒有意義的。WSN 中的節(jié)點自定位問題已成為一個重要的研究方向。網(wǎng)絡節(jié)點定位必須滿足低能耗、低成本、低復雜性和高精度的定位性能［3］。

近幾年中國學者在非測距定位領(lǐng)域取得了國際領(lǐng)先成果，例如，劉云浩教授領(lǐng)導的科研團隊開展了基于非測距的無線網(wǎng)絡定位理論與方法研究，率先實現(xiàn)了基于無線射頻識別技術(shù)的非測距定位系統(tǒng)LANDMARC，突破了無線多跳網(wǎng)絡下的非測距定位算法各向異性的瓶頸，在煤礦安全監(jiān)測、海洋環(huán)境監(jiān)測、森林碳匯和城市碳排放與空氣質(zhì)量監(jiān)測等應用中進行了實驗驗證，并在綠野千傳和CitySee 系統(tǒng)中進行了成功的大規(guī)模應用實踐［4］。

目前，應用較廣且研究較熱的WSN 自定位算法分為2 類:基于測距定位算法與無需測距定位算法［5］?；跍y距的定位算法需要外在硬件設備的支持，利用節(jié)點間信號強度或者角度信息，計算未知節(jié)點坐標;無需測距定位算法，較基于測距定位算法實現(xiàn)簡單，無需外在硬件設備，只需通過錨節(jié)點信息及整個網(wǎng)絡連通度來估計未知節(jié)點的坐標。因此，這類定位算法日趨受到關(guān)注。典型無需測距定位算法包括質(zhì)心算法、Amorphous 算法、APIT 算法以及DVHop 算法［6］等。其中，DV-Hop 算法是無需測距定位算法中應用最廣泛的算法之一。

本文首先簡單介紹傳統(tǒng)DV-Hop 算法基本思想，討論傳統(tǒng)算法存在的不足和相關(guān)改進方案，針對已有改進算法仍存在的不足提出一種改進算法，并以平均定位誤差和覆蓋率作為定位性能的主要評價標準，分別對錨節(jié)點比例、節(jié)點個數(shù)以及通信半徑等3個因素對平均定位誤差的影響進行仿真，同時在不同錨節(jié)點比例時對覆蓋率的影響進行仿真，并將本文的改進算法與傳統(tǒng)DV-Hop 算法及其他改進算法進行比較。

2 DV-Hop 算法

2.1 DV-Hop 算法簡介

DV-Hop 算法是利用距離矢量路由和GPS 定位原理的分布式定位算法APS(Ad hoc Positioning System)中的一種。圖1 是9 個節(jié)點小型網(wǎng)絡，其中，L1，L2，L3 為錨節(jié)點，D 為未知節(jié)點，以此網(wǎng)絡為例闡述DV-Hop 算法。

算法定位過程分為3 個階段:

(1)計算未知節(jié)點與每個錨節(jié)點的最小跳數(shù)。

錨節(jié)點向鄰居節(jié)點廣播含錨節(jié)點編號IDi，坐標(xi，yi)以及跳數(shù)字段di(初始化為0)的數(shù)據(jù)包。接收節(jié)點記錄到各錨節(jié)點的最小跳數(shù)，忽略同一錨節(jié)點的較大跳數(shù)的數(shù)據(jù)包。將跳數(shù)加1 后轉(zhuǎn)發(fā)給鄰居節(jié)點。所有節(jié)點就能夠記錄到各錨節(jié)點的最小跳數(shù)。如圖1 所示，D 到L1，L2，L3 的最小跳數(shù)分別為2，3，3，錨節(jié)點Ll，L2，L3 彼此間的跳數(shù)分別為2，5，6。

圖1 小型網(wǎng)絡結(jié)構(gòu)

(2)計算未知節(jié)點和錨節(jié)點的實際跳段距離。

各錨節(jié)點根據(jù)一階段中記錄的其他錨節(jié)點的位置和跳數(shù)信息，利用式(1)估算自身的跳段距離。

其中，(xi，yi)和(xj，yj)是錨節(jié)點i，j 的坐標;hj是錨節(jié)點i 與j(j≠i)之間的跳段數(shù)。

錨節(jié)點間距由歐氏距離公式計算，如圖1 所示分別為40 m，75 m 和100 m。由式(1)得錨節(jié)點L1，L2，L3 的跳段距離分別為:HopSize1=(40+75)/(2 +5)=16.43 m，HopSize2=(100 +40)/(6 +2)=17.5 m，HopSize3=(100 +75)/(6 +5)=15.91 m。然后，錨節(jié)點將計算的跳段距離用帶生存期字段的分組廣播至網(wǎng)絡中，未知節(jié)點僅記錄最近錨節(jié)點廣播的跳段距離，并轉(zhuǎn)發(fā)給鄰居節(jié)點。未知節(jié)點到各錨節(jié)點的距離由式(2)計算可得:

以圖1 為例，錨節(jié)點L1，L2，L3 向整個網(wǎng)絡廣播它們計算所得的跳段距離，未知節(jié)點D 即可收到它們的廣播。未知節(jié)點D 距L1 的跳數(shù)最少，因此，它最先接收到L1 的跳段距離將其作為平均跳距，并忽略其他跳段距離。由式(2)可得:節(jié)點D 到L1，L2，L3 的距離分別為2×16.43 m，3×16.43 m，3×16.43 m。

(3)三邊測量法或極大似然估計法計算自身位置。

未知節(jié)點利用二階段中記錄的到各錨節(jié)點的距離，利用三邊測量法或極大似然估計法計算自身坐標。極大似然估計法介紹如下:已知n 個錨節(jié)點坐標為(xi，yi)，其中，i=1，2，…，n，錨節(jié)點到未知節(jié)點(x，y)距離分別d1，d2，…，dn，則得式(3):

第1 個方程依次減去最后一個方程得到式(4):

向量表示為AX=B，其中:

由式(5)標準最小均方差估計法可得D 的坐標為:

2.2 DV-Hop 算法存在問題及相關(guān)解決方案

針對DV-Hop 算法，國內(nèi)外研究者提出了很多算法改進，文獻［7-8］的算法在未知節(jié)點到錨節(jié)點的路徑中，考慮相鄰3 個節(jié)點組成的夾角對距離的影響，根據(jù)鄰近節(jié)點重疊度計算夾角。引入網(wǎng)絡平均連通度計算節(jié)點間跳距，從而更精確地計算距離。在文獻［9］的改進算法中，錨節(jié)點通過實際距離和估計距離的誤差來修正平均跳距，采用新的二維雙曲線定位算法計算節(jié)點坐標。文獻［10］提出基于加權(quán)處理的平均跳距估計算法，根據(jù)距離未知節(jié)點的跳數(shù)和環(huán)境影響因素進行加權(quán)。文獻［11］的改進算法通過共線性檢查證明錨節(jié)點的有效性，分別用最小均方誤差準則、歸一化加權(quán)和總體最小二乘法進行定位，然后升級已定位未知節(jié)點為錨節(jié)點定位其他未知節(jié)點。文獻［12］針對存在障礙物情況，引入信任度概念，提出一種基于信任度的改進算法，通過對信任度值的判斷篩選合適的平均跳距值。以上改進算法在一定程度上提高了定位精度和覆蓋率，但仍存在以下不足:

(1)平均跳距的估算很大程度決定了DV-Hop定位算法的定位誤差。目前平均跳距是接收最近錨節(jié)點廣播的平均每跳校正值。這樣所得的平均跳距的估算值很粗糙，有待改進以獲得更準確的估計值。

(2)算法對錨節(jié)點密度有一定的要求，當錨節(jié)點相對稀疏時就需要對算法進行改進，使之能適用于節(jié)點稀疏場景的相關(guān)應用。

(3)DV-Hop 定位算法對跳數(shù)具有一定的依賴，節(jié)點間最小跳數(shù)的計算對定位精度有很大的影響，當跳數(shù)為1 時，存在一跳定位誤差問題，如果將未知節(jié)點和僅一跳間隔范圍的錨節(jié)點之間的距離，簡單地等同平均跳距值，將導致多個未知節(jié)點的定位重合或者定位誤差增大。

(4)網(wǎng)絡中存在障礙物時，對最短路徑選擇造成影響，使得跳段距離估算誤差較大。

本文針對DV-Hop 節(jié)點定位算法三階段和平均跳距估計誤差問題，從以下3 個方面進行改進:

(1)對算法第2 階段中所得平均跳距進行加權(quán)處理，得到一個與實際更為接近的平均跳距。

(2)對最后定位出的未知節(jié)點坐標進行修正。

(3)升級已定位未知節(jié)點為錨節(jié)點定位其他未知節(jié)點。相當于增加錨節(jié)點密度，從而提高定位覆蓋率。

3 本文改進算法

3.1 加權(quán)平均跳距

在傳統(tǒng)的DV-Hop 算法中，算法主要誤差來源于:用跳段數(shù)與未知節(jié)點接收離其最近的一個錨節(jié)點廣播的平均跳距的乘積，即由式(2)計算未知節(jié)點與錨節(jié)點之間的距離。當平均跳距的估計值與實際值偏差較大時，計算所得的未知節(jié)點估計距離與實際距離之間的誤差會增大。平均跳距誤差分析如圖2所示。其中，實線表示節(jié)點可以直接通信;虛線表示節(jié)點不能直接通信，需要中間節(jié)點的過度。

圖2 平均跳距誤差分析示意圖

由2.1 節(jié)中式(2)計算出未知節(jié)點D 到L1，L2和L3 的距離為2 ×16.43=32.86 m，3 ×16.43=49.29 m，3 ×16.43=49.29 m，如圖2 中虛線所示，顯然虛線距離(即真實距離)與計算所得距離有一定的偏差，因此，本文采用基于未知節(jié)點到錨節(jié)點跳數(shù)的加權(quán)來計算平均跳距，即通過式(6)求平均跳距:

其中，ni是未知節(jié)點到錨節(jié)點的跳數(shù);Hopsizei是傳統(tǒng)DV-Hop 算法中各錨節(jié)點計算所得跳段距離。

3.2 未知節(jié)點位置坐標修正

在傳統(tǒng)的DV-Hop 算法定位出未知節(jié)點位置坐標的基礎上，本文改進算法以最近錨節(jié)點坐標作為參照對原算法定位出的未知節(jié)點坐標進行修正，其修正方法如下:設定位出未知節(jié)點的坐標為(xj，yj)，最近錨節(jié)點坐標，在DV-Hop 算法定位機制中，未知節(jié)點僅接收距其最近錨節(jié)點轉(zhuǎn)發(fā)的平均跳距，所以，在修正策略中，以最近錨節(jié)點位置作為參照，引入一個與跳數(shù)相關(guān)的動態(tài)權(quán)值α，若未知節(jié)點估計坐標偏離最近錨節(jié)點，通過權(quán)值修正策略將坐標修正為相對更接近錨節(jié)點的位置。具體修正策略如下:當時，修正坐標為((1+α)xj，yj);當時，修正坐標為((1 -α)xj，yj);當時，修正坐標為(xj，(1 +α)yj);當時，修正坐標為(xj，(1 -α)yj)。

其中，ni是未知節(jié)點到錨節(jié)點的跳數(shù)這樣獲得的修正未知節(jié)點坐標更接近實際坐標。

如圖3 所示，當估計位置為E1(x1，y1)時，其在最近錨節(jié)點的正右方，故位置修正為((1 -α)x1，y1);當估計位置為E2(x2，y2)時，其在最近錨節(jié)點的左上方，故位置修正為((1 +α)x2，(1 -α)y2);當估計位置為E3(x3，y3)時，其在最近錨節(jié)點的左下方，故位置修正為((1 +α)x3，(1 +α)y3);當估計位置為E4(x4，y4)時，其在最近錨節(jié)點的右下方，故位置修正為((1 -α)x4，(1 +α)y4)。

圖3 位置修正策略示意圖

3.3 改進算法實現(xiàn)步驟

在本文改進算法的運算過程中，針對傳統(tǒng)DVHop 算法平均跳距估算比較粗糙，引入基于未知節(jié)點到錨節(jié)點跳段數(shù)的加權(quán)平均跳距，加權(quán)平均跳距的估算方法參照3.1 節(jié);同時采用最小二乘法來計算未知節(jié)點的位置坐標;最后，由于未知節(jié)點接收離其最近的錨節(jié)點轉(zhuǎn)發(fā)的平均跳距，本文引入坐標修正策略，參照3.2 節(jié)。這樣獲得的修正未知節(jié)點的坐標更接近實際坐標。本文改進算法實現(xiàn)步驟如下:

(1)網(wǎng)絡初始化。

本文算法相關(guān)主要參數(shù)變量如下:

anchors_n:網(wǎng)絡錨節(jié)點的個數(shù);

nodes_n:網(wǎng)絡節(jié)點的個數(shù);

square_L:方形監(jiān)測區(qū)域邊長;

comm_r:節(jié)點間通信距離;

all_nodes.true=unifrnd(0，square_L，nodes_n，2):所有節(jié)點真實坐標矩陣，包括橫縱坐標，與square_L 和nodes_n 有關(guān);

all_nodes.estimated:所有錨節(jié)點估計坐標矩陣(考慮到GPS 誤差)，包括橫縱坐標;

hopsize(1:all_nodes.anchors_n):每個錨節(jié)點的跳段距離;

Hopsize:式(6)所求得平均跳距;

alpha:位置修正策略引入的動態(tài)權(quán)值α。

(2)錨節(jié)點廣播包含節(jié)點ID、自身位置信息、跳數(shù)信息的數(shù)據(jù)包，跳數(shù)初始化為0。

(3)未知節(jié)點和其他錨節(jié)點接收錨節(jié)點的數(shù)據(jù)包，各節(jié)點計算最小跳數(shù)。

未知節(jié)點和其他錨節(jié)點接收錨節(jié)點的數(shù)據(jù)包，待廣播結(jié)束后，判斷未知節(jié)點是否收到3 個或3 個以上錨節(jié)點信息，是則錨節(jié)點開始計算與其他錨節(jié)點的距離，否則未知節(jié)點不能定位。

(4)每個錨節(jié)點估計校正值:根據(jù)式(1)計算每個錨節(jié)點估計校正值HopSizei。

(5)錨節(jié)點根據(jù)式(6)計算其平均跳距并全網(wǎng)廣播。

(6)未知節(jié)點根據(jù)最小二乘法定位出其位置坐標。

(7)對定位出的未知節(jié)點位置坐標進行修正。

參照3.2 節(jié)的修正策略根據(jù)未知節(jié)點與距其最近錨節(jié)點的坐標位置關(guān)系進行位置修正，并將修正后的坐標作為未知節(jié)點最終定位的坐標，整個定位過程結(jié)束。本文算法流程如圖4 所示。

圖4 本文改進算法流程

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

為驗證本文改進算法性能，用Matlab7.11.0 軟件對改進算法進行仿真，本文將基于100 次仿真統(tǒng)計結(jié)果的平均定位誤差和覆蓋率作為評價指標，并與傳統(tǒng)DV-Hop 算法及文獻［10］和文獻［11］提出的2 種改進算法進行比較。

仿真網(wǎng)絡環(huán)境如下:傳感器節(jié)點隨機分布在100 m× 100 m 的正方形區(qū)域內(nèi)，設所有節(jié)點的通信半徑均為R，分別在不同錨節(jié)點比例、不同節(jié)點個數(shù)和不同通信半徑等3 個因素下對傳統(tǒng)算法、文獻［10］改進算法和本文改進算法的定位誤差進行研究。在保持節(jié)點個數(shù)不變，錨節(jié)點個數(shù)不同時，R 為15 m 和25 m 2 種情況下，對傳統(tǒng)算法、文獻［11］改進算法和本文改進算法的覆蓋率進行研究。對在WSN 中，定義平均定位誤差為估計位置到真實位置的歐式距離與通信半徑的比值，如式(8)所示:

定位覆蓋率定義為:可定位節(jié)點數(shù)/未知節(jié)點總數(shù)。

圖5 給出了總節(jié)點數(shù)200 個，通信半徑為15 m 情況下節(jié)點平均定位誤差與錨節(jié)點比例的關(guān)系曲線。由仿真結(jié)果可知，3 種算法的平均定位誤差均隨總節(jié)點數(shù)量的增加而減小，并逐漸趨于穩(wěn)定。本文算法較DV-Hop 算法，平均定位誤差整體平均降低12.55%，較文獻［10］的改進算法整體平均降低了3.42%。

圖5 平均定位誤差與與錨節(jié)點比例的關(guān)系

圖6 給出了錨節(jié)點比例為10%，通信半徑為15 m情況下節(jié)點平均定位誤差與總節(jié)點個數(shù)的關(guān)系曲線。

圖6 平均定位誤差與節(jié)點個數(shù)的關(guān)系

由仿真結(jié)果可知，3 種算法的平均定位誤差隨總節(jié)點數(shù)量的增加而減小，并逐漸趨于穩(wěn)定。本文算法較DV-Hop算法，定位誤差整體平均降低15.38%，較文獻［10］改進算法的整體平均降低3.78%。

圖7 給出錨節(jié)點比例為15%，即30 個錨節(jié)點、節(jié)點個數(shù)為200 時節(jié)點平均定位誤差與通信半徑的關(guān)系曲線。由仿真結(jié)果可知，3 種定位算法的平均定位誤差隨節(jié)點通信半徑的增加而減小，這是由于增加通信半徑相當于增大網(wǎng)絡的連通度，節(jié)點之間相互通信的機會增加，有效地減小了定位誤差。由圖7可知隨著節(jié)點通信半徑的增加，3 種定位算法的定位誤差都在不斷下降。在相同的通信半徑情況下，本文算法較DV-Hop 算法，平均定位誤差整體平均降低10.26%，較文獻［10］改進算法整體平均降低約2.0%。

圖7 平均定位誤差與通信半徑的關(guān)系

圖8 和圖9 給出通信半徑R 為15 m 和25 m 2 種情況，節(jié)點個數(shù)為200 時，錨節(jié)點個數(shù)在5～40內(nèi)變化，節(jié)點覆蓋率與錨節(jié)點個數(shù)的關(guān)系曲線。由仿真結(jié)果可知，3 種算法隨著錨節(jié)點個數(shù)增加，覆蓋率都有提高。且在相同的錨節(jié)點數(shù)的情況下，本文的改進算法較傳統(tǒng)的DV-Hop 算法及文獻［11］改進算法覆蓋率更高。這是由于本文改進算法以代替未知節(jié)點接收的最近錨節(jié)點廣播的平均跳距HopSize，將全網(wǎng)廣播，這樣未接收3 個錨節(jié)點信息的未知節(jié)點也能接收到再由式(2)計算未知節(jié)點到錨節(jié)點的距離，同時升級已定位未知節(jié)點為錨節(jié)點定位其他未知節(jié)點，從而提高覆蓋率。本文改進算法中R=15 m 時，本文算法較DVHop 算法，隨錨節(jié)點個數(shù)變化覆蓋率整體平均提高12.75%，較文獻［11］算法整體平均提高1.25%;R=25 m時，本文算法較DV-Hop 算法，覆蓋率隨錨節(jié)點個數(shù)變化整體平均提高8.63%，較文獻［11］算法整體平均提高1.38%。

圖8 覆蓋率與錨節(jié)點個數(shù)的關(guān)系(R=15 m)

圖9 覆蓋率與錨節(jié)點個數(shù)的關(guān)系(R=25 m)

5 結(jié)束語

本文算法并沒有改變傳統(tǒng)DV-Hop 算法的基本定位過程，無需額外的硬件支持，在確保平均跳距估計誤差較小的同時，不增加網(wǎng)絡通信開銷，且對定位出的未知節(jié)點坐標進行動態(tài)加權(quán)修正，在控制計算量的同時，大幅提高了節(jié)點的定位精度和覆蓋率。仿真結(jié)果表明，該算法的定位精度和覆蓋率均優(yōu)于傳統(tǒng)DV-Hop 算法和文獻［10 -11］改進算法。發(fā)現(xiàn)當存在有障礙物時，障礙物將影響未知節(jié)點與錨節(jié)點之間的最短路徑，形成彎曲路徑，從而給平均跳距的估算帶來誤差，影響定位精度。因此，對有障礙物以及稀疏節(jié)點場景下DV-Hop 定位算法改進將成為今后主要的研究方向。

［1］Akyildiz I F，Su W，Sankarasubramaniam Y，et al.A Survey on Sensor Networks［J］.IEEE Communications Magazine，2002，40(7):102-114.

［2］Qi Hairong，Kuruganti P T，Xu Yingyue.The Development of Localized Algorithms in Wireless Sensor Networks［J］.Sensors，2002，2(7):286-293.

［3］Liu Yunhao，Yang Zheng，Wang Xiaoping，et al.Location，Localization，and Localizability［J］.Journal of Computer Science and Technology，2010，25(2):274-297.

［4］GreenOrbs ［EB/OL］.［2013-09-30］.http://www.greenorbs.org.

［5］Perkins C，Royer E.Ad Hoc on Demand Distance Vector Routing［J］.Mobile System and Applications，1999，24(3):59-81.

［6］Niculescu D，Nath B.DV Based Positioning in Ad-hoc Networks［J］.Journal of Telecommunication Systems，2003，22(4):267-280.

［7］王 穎，石昊旸.改進的無線傳感器網(wǎng)絡DV-Hop 定位算法［J］.計算機工程，2012，38(7):66-69.

［8］張曉龍，解慧英，趙小建.無線傳感器網(wǎng)絡中一種改進的DV-Hop 定位算法［J］.計算機應用，2007，27(11):2672-2674.

［9］石為人，賈傳江.一種改進的無線傳感器網(wǎng)絡DV-Hop定位算法［J］.傳感技術(shù)學報，2011，24(1):83-87.

［10］馮 江，朱 強，吳春春.改進的DV-Hop 定位算法研究［J］.計算機工程，2012，38(19):74-77，81.

［11］張 靜，曹 敦.DV-Hop 算法定位誤差和覆蓋率的改進［J］.計算機應用，2011，31(7):1944-1947.

［12］史庭俊，桑 霞，徐力杰，等.一種基于信任度的DVHop 改進定位算法［J］.微電子學與計算機，2008，25(10):101-102.