趙亞濤，王玉寶

(燕山大學(xué)信息科學(xué)與工程學(xué)院，河北秦皇島066004)

0 引言

無(wú)線傳感器網(wǎng)絡(luò)(wireless sensor network，WSNs)越來(lái)越受到關(guān)注。定位技術(shù)是其關(guān)鍵技術(shù)之一，近年來(lái)，研究者們提出了很多只需用很少錨節(jié)點(diǎn)來(lái)協(xié)助計(jì)算未知節(jié)點(diǎn)絕對(duì)坐標(biāo)的定位算法［1］。這些算法主要分為:基于測(cè)距的和無(wú)需測(cè)距的。其中，基于測(cè)距的算法主要由到達(dá)時(shí)間差［2］(time difference of arrival，TDoA)，到達(dá)角度［3］(angle of arrival，AoA)，接收信號(hào)強(qiáng)度指示［4］(received signal strength indicator，RSSI)和到達(dá)時(shí)間(time of arrival，ToA)等來(lái)獲得距離或角度信息，進(jìn)而定位;而無(wú)需測(cè)距的算法，只需要獲得網(wǎng)絡(luò)連通性等少量信息就可實(shí)現(xiàn)定位，且不需要節(jié)點(diǎn)額外的硬件開(kāi)銷。因此倍受關(guān)注，如，MDS-MAP算法［5］，凸規(guī)劃算法［6］，質(zhì)心算法，DV-Hop 算法［7］及其改進(jìn)算法［8～10］等。本文基于DV-Hop算法的原理，利用加權(quán)思想處理錨節(jié)點(diǎn)的平均跳距，提出了一種無(wú)線傳感器網(wǎng)絡(luò)非均勻分布節(jié)點(diǎn)定位算法——W-DV-Hop(weighted-DV-Hop)算法。

1 計(jì)算節(jié)點(diǎn)位置的基本方法

傳感器節(jié)點(diǎn)定位的過(guò)程中，未知節(jié)點(diǎn)獲得錨節(jié)點(diǎn)的距離后，通常用三邊測(cè)量法(Trilateration)來(lái)計(jì)算自己的位置，如圖1所示。

圖1 三邊測(cè)量法Fig 1 Trilateration

已知 A，B，C 3 個(gè)錨節(jié)點(diǎn)的坐標(biāo)分別為(xa，ya)，(xb，yb)，(xc，yc)，以及它們到未知節(jié)點(diǎn) D的距離分別為da，db，dc，假設(shè)D的坐標(biāo)為(x，y)。那么，存在下列公式

由此可得到未知節(jié)點(diǎn)D的坐標(biāo)為

2 W-DV-hop算法

本算法的定位過(guò)程分為3個(gè)階段:第一階段，根據(jù)距離矢量協(xié)議使網(wǎng)絡(luò)中所有節(jié)點(diǎn)獲得各個(gè)錨節(jié)點(diǎn)的最小跳數(shù)信息;接著，錨節(jié)點(diǎn)利用公式(3)計(jì)算各自平均跳距［7］(Hop-Sizei)，由式(4)得到網(wǎng)絡(luò)平均跳距HopSize;然后，作為校正值廣播到網(wǎng)絡(luò)，即有

其中，HopSizei表示第i個(gè)錨節(jié)點(diǎn)的平均跳距值，dij表示錨節(jié)點(diǎn)i，j之間的歐氏距離為(xi，yi)，(xj，yj)表示錨節(jié)點(diǎn) i和錨節(jié)點(diǎn) j的坐標(biāo)，hij表示錨節(jié)點(diǎn)i與j(j≠i)之間的跳數(shù)，N表示網(wǎng)絡(luò)中節(jié)點(diǎn)總個(gè)數(shù)，M表示錨節(jié)點(diǎn)的個(gè)數(shù)，ai表示到第i個(gè)錨節(jié)點(diǎn)有最少跳數(shù)的未知節(jié)點(diǎn)的個(gè)數(shù)，wi表示HopSizei的權(quán)重，即錨節(jié)點(diǎn)i的加權(quán)值等于到第i個(gè)錨節(jié)點(diǎn)有最少跳數(shù)的未知節(jié)點(diǎn)的個(gè)數(shù)除以未知節(jié)點(diǎn)的總個(gè)數(shù)。這樣做一個(gè)歸一化的處理，使用統(tǒng)一標(biāo)準(zhǔn)對(duì)錨節(jié)點(diǎn)的平均跳距進(jìn)行處理，并保證各個(gè)平均跳距的權(quán)值之和為1。同時(shí)，通過(guò)對(duì)平均跳距賦以不同的權(quán)值，區(qū)分了不同錨節(jié)點(diǎn)的平均跳距對(duì)網(wǎng)絡(luò)平均跳距的影響程度。

第二階段，未知節(jié)點(diǎn)利用網(wǎng)絡(luò)平均跳距和到錨節(jié)點(diǎn)的跳數(shù)信息計(jì)算到錨節(jié)點(diǎn)的距離(稱為跳段距離)，如公式(5)所示

其中，hlk表示未知節(jié)點(diǎn)l到錨節(jié)點(diǎn)k的最小跳數(shù)。

當(dāng)未知節(jié)點(diǎn)獲得3個(gè)或更多錨節(jié)點(diǎn)的信息后，則在第3階段進(jìn)行自身定位。

若網(wǎng)絡(luò)中有計(jì)算能力很強(qiáng)的節(jié)點(diǎn)，則可以由其收集錨節(jié)點(diǎn)的平均跳距并計(jì)算網(wǎng)絡(luò)平均跳距，然后廣播到網(wǎng)絡(luò);還可以由錨節(jié)點(diǎn)記錄彼此的平均跳距來(lái)各自計(jì)算得到網(wǎng)絡(luò)平均跳距。然后，將該值作為校正值廣播到網(wǎng)絡(luò)，由于錨節(jié)點(diǎn)廣播的校正值是相同的，可以根據(jù)一定的轉(zhuǎn)發(fā)策略廣播到網(wǎng)絡(luò)，以達(dá)到減少能量消耗的目的。具體的轉(zhuǎn)發(fā)機(jī)制［11］包括:基于概率轉(zhuǎn)發(fā)、基于計(jì)數(shù)器轉(zhuǎn)發(fā)、基于距離轉(zhuǎn)發(fā)、基于位置轉(zhuǎn)發(fā)……，本文采用基于計(jì)數(shù)器轉(zhuǎn)發(fā)。

3 非均勻分布網(wǎng)絡(luò)模型

當(dāng)無(wú)線傳感器網(wǎng)絡(luò)應(yīng)用于河流、建筑物的環(huán)境監(jiān)測(cè)、智能家居時(shí)，難免出現(xiàn)節(jié)點(diǎn)的非均勻布置。圖2即為一常見(jiàn)的非均勻分布C型網(wǎng)絡(luò)。

圖2 C型網(wǎng)絡(luò)模型Fig 2 C type network model

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

為了驗(yàn)證算法的性能，在計(jì)算機(jī)上利用Matlab7進(jìn)行仿真并與DV-Hop算法進(jìn)行了比較，實(shí)驗(yàn)設(shè)置各個(gè)節(jié)點(diǎn)有相同的通信半徑R。

4.1 平均定位誤差

性能評(píng)價(jià)采用平均誤差函數(shù)

其中，(xi，yi)表示未知節(jié)點(diǎn) i的實(shí)際坐標(biāo)，(x'i，y'i)表示未知節(jié)點(diǎn)i的估計(jì)坐標(biāo)。平均誤差越小，則定位精度越高;反之，越低。

在實(shí)驗(yàn)過(guò)程中，網(wǎng)絡(luò)節(jié)點(diǎn)隨機(jī)分布，生成如圖2 C型網(wǎng)絡(luò)和圖3所示的網(wǎng)格分布網(wǎng)絡(luò)。本文算法在圖3所示網(wǎng)絡(luò)模型下進(jìn)行仿真。

圖3描述了另一常見(jiàn)的非均勻分布網(wǎng)絡(luò)模型，橫軸和縱軸分別表示節(jié)點(diǎn)的橫縱坐標(biāo)值，其中錨節(jié)點(diǎn)和未知節(jié)點(diǎn)隨機(jī)產(chǎn)生，且考慮定位因素從布置3個(gè)錨節(jié)點(diǎn)(星型節(jié)點(diǎn))開(kāi)始進(jìn)行性能仿真。

圖3 網(wǎng)格分布網(wǎng)絡(luò)Fig 3 Grid distribution network

圖4描述了圖3所示網(wǎng)絡(luò)的節(jié)點(diǎn)平均定位誤差和錨節(jié)點(diǎn)個(gè)數(shù)的關(guān)系曲線，錨節(jié)點(diǎn)個(gè)數(shù)依次為3，4，5，6，7，8。由圖示曲線描述:隨著錨節(jié)點(diǎn)個(gè)數(shù)的增加，2種算法的平均定位誤差總體呈現(xiàn)降低趨勢(shì)，由于網(wǎng)絡(luò)節(jié)點(diǎn)布置的隨機(jī)性曲線產(chǎn)生波動(dòng)?？闯霎?dāng)錨節(jié)點(diǎn)個(gè)數(shù)為3時(shí)，新算法平均定位誤差值比DV-Hop算法降低最多為29%左右，主要原因是錨節(jié)點(diǎn)的個(gè)數(shù)較少時(shí)，在非均勻分布網(wǎng)絡(luò)錨節(jié)點(diǎn)的平均跳距不能很好地接近網(wǎng)絡(luò)每跳距離，而影響定位精度，由于新算法采用的網(wǎng)絡(luò)平均跳距能體現(xiàn)大多數(shù)節(jié)點(diǎn)所適合采用的網(wǎng)絡(luò)每跳距離，能從總體上降低節(jié)點(diǎn)的平均誤差，且可以在滿足需要的同時(shí)降低網(wǎng)絡(luò)成本。

需要說(shuō)明的是，網(wǎng)絡(luò)中節(jié)點(diǎn)的平均定位誤差不總是隨著錨節(jié)點(diǎn)個(gè)數(shù)的增加而降低，這是因?yàn)槠骄`差是所有未知節(jié)點(diǎn)誤差的和除以未知節(jié)點(diǎn)個(gè)數(shù)，當(dāng)網(wǎng)絡(luò)中節(jié)點(diǎn)總數(shù)一定而錨節(jié)點(diǎn)的個(gè)數(shù)增加時(shí)，相應(yīng)的未知節(jié)點(diǎn)的數(shù)目將會(huì)減少，即公式(6)中的分母變小，這將使平均誤差值具有不確定性。

圖5曲線的橫縱坐標(biāo)分別表示圖3所示網(wǎng)絡(luò)節(jié)點(diǎn)的通信半徑和平均誤差，由曲線描述看出:新算法相比原算法定位誤差最好時(shí)要低28%左右，當(dāng)R≥60 m時(shí)，2種算法的平均誤差值趨于一致，這主要是由網(wǎng)格之間的間距決定的，但相對(duì)DV-Hop算法，新算法在R從剛好滿足節(jié)點(diǎn)通信的大小增大到R為60m的階段平均定位誤差要比DV-Hop算法低很多。

圖4 不同錨節(jié)點(diǎn)的平均定位誤差Fig 4 Average localization error of different anchor nodes’number

圖5 平均定位誤差與半徑R的關(guān)系Fig 5 Relation between average localization error and R

4.2 能耗分析

網(wǎng)絡(luò)能耗主要包括通信開(kāi)銷和計(jì)算開(kāi)銷。假設(shè)網(wǎng)絡(luò)總節(jié)點(diǎn)個(gè)數(shù)為N;錨節(jié)點(diǎn)個(gè)數(shù)為M;計(jì)數(shù)器門限為L(zhǎng)(N·L≥M)，分析可知，當(dāng)L取值較小時(shí)，出現(xiàn)部分未知節(jié)點(diǎn)不能定位;當(dāng)取值較大時(shí)，錨節(jié)點(diǎn)的覆蓋會(huì)出現(xiàn)重疊，造成能量的浪費(fèi)。對(duì)于L的取值可以根據(jù)實(shí)際取值，為滿足網(wǎng)絡(luò)的整體要求要適當(dāng)偏大，當(dāng)節(jié)點(diǎn)接收的計(jì)數(shù)信息大于L時(shí)，不再轉(zhuǎn)發(fā)網(wǎng)絡(luò)平均跳距。對(duì)于DV-Hop算法采用兩次泛洪，則通信開(kāi)銷為2MN;新算法采用基于門限轉(zhuǎn)發(fā)則通信開(kāi)銷為MN+N/M。新算法需要得到網(wǎng)絡(luò)平均跳距，則相對(duì)DVHop算法增加的計(jì)算開(kāi)銷為2M+1(M次除法，M次乘法和一次加法)，可得2種算法的能耗差值?

進(jìn)一步化簡(jiǎn)得到

在實(shí)際應(yīng)用中，錨節(jié)點(diǎn)的比例很小，式(8)肯定會(huì)大于0，由此可知新算法的能耗較低。

由圖6可以看出:當(dāng)滿足定位的最低要求時(shí)，本文算法的數(shù)據(jù)包個(gè)數(shù)大約為DV-Hop算法的1/3，當(dāng)錨節(jié)點(diǎn)個(gè)數(shù)增加時(shí)，DV-Hop算法用于定位的數(shù)據(jù)包數(shù)目急劇增加，而本文算法變化不十分明顯。且新算法的計(jì)算開(kāi)銷只是在錨節(jié)點(diǎn)(或參與計(jì)算網(wǎng)絡(luò)平均跳距)的能耗加大時(shí)對(duì)于占總節(jié)點(diǎn)大比例的未知節(jié)點(diǎn)能耗會(huì)相對(duì)DV-Hop算法減少很多，能很好地延長(zhǎng)節(jié)點(diǎn)壽命。

圖6 網(wǎng)絡(luò)能耗Fig 6 Energy consumption of network

5 結(jié)論

本文提出一種無(wú)線傳感器網(wǎng)絡(luò)非均勻分布的節(jié)點(diǎn)定位算法——W-DV-Hop算法。該算法不需要節(jié)點(diǎn)的額外配置，網(wǎng)絡(luò)成本低，主要采用加權(quán)處理錨節(jié)點(diǎn)的平均跳距作為網(wǎng)絡(luò)平均跳距HopSize，使未知節(jié)點(diǎn)到錨節(jié)點(diǎn)的跳段距離更接近實(shí)際距離。仿真結(jié)果表明:同等條件下，新算法比DVHop算法定位精度要高，并且能量消耗降低，能有效延長(zhǎng)節(jié)點(diǎn)的壽命。

［1］王福豹，史 龍，任豐原.無(wú)線傳感器網(wǎng)絡(luò)中的自身定位系統(tǒng)和算法［J］.軟件學(xué)報(bào)，2005，16(5):857－868.

［2］陳鴻龍，李鴻斌，王 智.基于TDoA測(cè)距的傳感器網(wǎng)絡(luò)安全定位研究［J］.通信學(xué)報(bào)，2008，29(8):11－21.

［3］Niculescu D，Nath B.Ad Hoc positioning system(APS)using AoA［C］∥Proc of IEEE the InfoCom，San Francisco，CA，USA，2003:1734－1743.

［4］趙 昭，陳小惠.無(wú)線傳感器網(wǎng)絡(luò)中基于RSSI的改進(jìn)定位算法［J］.傳感技術(shù)學(xué)報(bào)，2009，22(3):391－394.

［5］Shang Y，Ruml W.Improved MDS-based localization［C］∥Proc of the IEEE Infocom，Hong Kong，2004:2640－2651.

［6］Doherty L，Pister K，Ghaoui L.Convex position estimation in wireless sensor networks［C］∥Proc.of the IEEE Infocom，Anchorage，AK，USA，2001:1655－1663.

［7］Niculescu D，Nath B.Ad Hoc positioning system(APS)［J］.IEEE Globe Com，2001(5):2926－2931.

［8］嵇瑋瑋，劉 中.DV Hop定位算法在隨機(jī)傳感器網(wǎng)絡(luò)中的應(yīng)用研究［J］.電子與信息學(xué)報(bào)，2008，30(4):970－974.

［9］付 華，胡 冰.一種無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位算法的改進(jìn)［J］.傳感器與微系統(tǒng)，2009，28(3):27－29.

［10］彭 剛，曹元人，孫利民.無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位機(jī)制的研究［J］.計(jì)算機(jī)工程與應(yīng)用，2004，40(35):27－29.

［11］Ni SY，Tseng Y C，Chen Y S，et al.The broadcast storm problem in a mobile Ad Hoc Network［C］∥Proceedings of Mobicom’99 5th Annual ACM/IEEE International Conference on Mobile Computing and Networking，1999:51－162.