基于改進(jìn)DV-Hop算法的無(wú)線傳感器網(wǎng)絡(luò)定位研究*

李 鵬

(長(zhǎng)江大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院，湖北 荊州 434023)

0 引 言

無(wú)線傳感器網(wǎng)絡(luò)是由部署在監(jiān)測(cè)區(qū)域內(nèi)大量的具有計(jì)算和通信能力的微型傳感器節(jié)點(diǎn)組成，通過(guò)無(wú)線通信的方式形成一個(gè)多跳的自組織的網(wǎng)絡(luò)系統(tǒng)[1]，其作用是利用傳感器來(lái)監(jiān)測(cè)、收集、處理信息數(shù)據(jù)，傳感器的無(wú)線收發(fā)裝置將數(shù)據(jù)通過(guò)無(wú)線通信傳輸。傳感器節(jié)點(diǎn)的定位是無(wú)線傳感器網(wǎng)絡(luò)的基本功能。根據(jù)是否需要測(cè)量實(shí)際節(jié)點(diǎn)間的距離，把無(wú)線傳感器網(wǎng)絡(luò)定位算法分為兩類：基于距離的定位算法(Range-based)和距離無(wú)關(guān)的定位算法(Range-free)[2]?；诰嚯x的定位算法共同特點(diǎn)是需要測(cè)量相鄰節(jié)點(diǎn)間的絕對(duì)距離或方位，并通過(guò)測(cè)量的絕對(duì)距離和方位來(lái)計(jì)算未知節(jié)點(diǎn)的位置；距離無(wú)關(guān)的定位算法則不需要測(cè)量節(jié)點(diǎn)間的絕對(duì)距離或方位，而是要得到節(jié)點(diǎn)間的估計(jì)距離，然后利用估計(jì)距離計(jì)算節(jié)點(diǎn)位置。

距離無(wú)關(guān)的定位算法通常有DV-Hop算法、質(zhì)心算法、APIT算法等經(jīng)典算法[3]。其中DV-Hop算法使用每跳平均距離乘以跳段數(shù)來(lái)計(jì)算節(jié)點(diǎn)間距離，對(duì)網(wǎng)絡(luò)節(jié)點(diǎn)的硬件設(shè)備要求低，部署簡(jiǎn)單，實(shí)現(xiàn)起來(lái)比較簡(jiǎn)易，缺點(diǎn)是節(jié)點(diǎn)間的跳段距離是估算出來(lái)的，用節(jié)點(diǎn)間的跳段距離代替節(jié)點(diǎn)間的實(shí)際直線距離是不精確的，存在誤差[4]。在分析了傳統(tǒng)DV-Hop算法特點(diǎn)的基礎(chǔ)上，提出了一種改進(jìn)的DV-Hop算法，主要思想是利用粒子群優(yōu)化算法對(duì)DV-Hop算法中的每跳平均距離誤差函數(shù)進(jìn)行優(yōu)化，從而精確了節(jié)點(diǎn)間的跳段距離，達(dá)到了對(duì)DV-Hop算法校正的目的，通過(guò)三邊測(cè)量法計(jì)算出的未知節(jié)點(diǎn)的位置更精確。

1 無(wú)線傳感器網(wǎng)絡(luò)定位技術(shù)

1.1 定位技術(shù)基本概念

在傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位中，節(jié)點(diǎn)分為信標(biāo)節(jié)點(diǎn)和未知節(jié)點(diǎn)，信標(biāo)節(jié)點(diǎn)是未知節(jié)點(diǎn)的參考點(diǎn)，信標(biāo)節(jié)點(diǎn)數(shù)量比未知節(jié)點(diǎn)要少，信標(biāo)節(jié)點(diǎn)可通過(guò)GPS定位裝置來(lái)確定自己的準(zhǔn)確位置，而未知節(jié)點(diǎn)通過(guò)和鄰近的信標(biāo)節(jié)點(diǎn)或者是已經(jīng)確定位置的未知節(jié)點(diǎn)進(jìn)行通信，來(lái)確定自己的位置。

1.2 測(cè)量節(jié)點(diǎn)位置基本方法

圖1 三邊測(cè)量法圖示

計(jì)算節(jié)點(diǎn)位置的方法有三邊測(cè)量法、三角測(cè)量法、極大似然估計(jì)法。在此主要介紹三邊測(cè)量法[5]，三邊測(cè)量法是未知節(jié)點(diǎn)接收到3個(gè)以上信標(biāo)節(jié)點(diǎn)的位置信息后(以3個(gè)信標(biāo)節(jié)點(diǎn)為例)，就可以得到未知節(jié)點(diǎn)到3個(gè)信標(biāo)節(jié)點(diǎn)的距離，然后可以算出未知節(jié)點(diǎn)的坐標(biāo)，三邊測(cè)量法圖示如圖1所示。假設(shè)已知3個(gè)信標(biāo)節(jié)點(diǎn)A、B、C的坐標(biāo)分別為(xA，yA)、(xB，yB)、(xC，yC)，未知節(jié)點(diǎn)的坐標(biāo)為(x，y)，未知節(jié)點(diǎn)到3個(gè)信標(biāo)節(jié)點(diǎn)的距離分別為dA，dB，dC，則：

(1)

通過(guò)式(1)可得到未知節(jié)點(diǎn)D的坐標(biāo)為

(2)

1.3 定位性能評(píng)價(jià)標(biāo)準(zhǔn)

無(wú)線傳感器網(wǎng)絡(luò)定位系統(tǒng)算法很多，常用的衡量定位能力的標(biāo)準(zhǔn)有定位精度，定位精度是指定位系統(tǒng)提供的位置信息的精確程度，是評(píng)價(jià)定位能力的最關(guān)鍵的標(biāo)準(zhǔn)，精度越高，技術(shù)要求也越高。除此之外，還有覆蓋范圍、信標(biāo)節(jié)點(diǎn)密度、節(jié)點(diǎn)密度、容錯(cuò)性和魯棒性以及功耗等。

2 定位算法分析

2.1 基于距離的定位算法

基于距離的定位機(jī)制(Range-based)分為3個(gè)階段：第1階段為測(cè)距階段；第2階段為定位階段；第3階段是修正階段，對(duì)第2階段計(jì)算得到的未知節(jié)點(diǎn)的坐標(biāo)精確化，減少誤差?；诰嚯x的定位算法通常有：基于接收信號(hào)強(qiáng)度指示算法RSSI、到達(dá)時(shí)間方法TOA、到達(dá)時(shí)間差方法TDOA、到達(dá)角度方法AOA等。

2.2 距離無(wú)關(guān)的定位算法

基于距離的定位算法可以精確定位未知節(jié)點(diǎn)的坐標(biāo)，但是對(duì)無(wú)線傳感器節(jié)點(diǎn)的硬件要求很高，導(dǎo)致無(wú)線傳感器節(jié)點(diǎn)的硬件開(kāi)銷大、能耗高，因此人們提出了距離無(wú)關(guān)的定位技術(shù)。距離無(wú)關(guān)的定位技術(shù)不需要測(cè)量節(jié)點(diǎn)間的絕對(duì)距離或角度信息，只需網(wǎng)絡(luò)連通性等約束來(lái)實(shí)現(xiàn)節(jié)點(diǎn)的定位，降低了無(wú)線傳感器節(jié)點(diǎn)的硬件開(kāi)銷，但定位誤差會(huì)相應(yīng)的增加。距離無(wú)關(guān)的定位算法通常有質(zhì)心算法、DV-Hop算法、APIT算法等經(jīng)典算法，在此主要介紹DV-Hop算法。DV-Hop算法(距離向量-跳段)[6]定位過(guò)程如下：

首先，計(jì)算未知節(jié)點(diǎn)與每個(gè)信標(biāo)節(jié)點(diǎn)之間的最小跳段數(shù)量，網(wǎng)絡(luò)中信標(biāo)節(jié)點(diǎn)通過(guò)距離矢量交換協(xié)議發(fā)送一個(gè)廣播分組，將該信標(biāo)節(jié)點(diǎn)的位置信息和跳數(shù)廣播到整個(gè)網(wǎng)絡(luò)，廣播分組包括該信標(biāo)節(jié)點(diǎn)號(hào)、坐標(biāo)位置(xi，yi)，以及跳數(shù)，跳數(shù)初始化為0。當(dāng)節(jié)點(diǎn)接收到該信標(biāo)節(jié)點(diǎn)的廣播分組后對(duì)比自己的數(shù)據(jù)表的跳數(shù)和該分組的跳數(shù)，如果該分組跳數(shù)小于本節(jié)點(diǎn)數(shù)據(jù)表內(nèi)的跳數(shù)，則用分組的跳數(shù)代替節(jié)點(diǎn)的跳數(shù)，將跳數(shù)加1，并且廣播該分組，如果該分組的跳數(shù)大于本節(jié)點(diǎn)數(shù)據(jù)表內(nèi)的跳數(shù)，則丟棄該分組，而且不廣播該分組。這樣，所有的未知節(jié)點(diǎn)都能獲得與所有信標(biāo)節(jié)點(diǎn)之間的最小跳數(shù)。

然后，計(jì)算未知節(jié)點(diǎn)與信標(biāo)節(jié)點(diǎn)的距離。每個(gè)信標(biāo)節(jié)點(diǎn)根據(jù)記錄的其他信標(biāo)節(jié)點(diǎn)的位置信息和跳數(shù)，利用式(3)估算出每跳平均距離

(3)

其中，(xi，yi)，(xj，yj)是信標(biāo)節(jié)點(diǎn)i，j的坐標(biāo)，hj是信標(biāo)節(jié)點(diǎn)i與j(j≠i)之間的跳數(shù)。然后信標(biāo)節(jié)點(diǎn)將計(jì)算的每跳平均距離廣播到網(wǎng)絡(luò)中，未知節(jié)點(diǎn)記錄接收到的第一個(gè)每跳平均距離，并將分組轉(zhuǎn)發(fā)給鄰居節(jié)點(diǎn)，未知節(jié)點(diǎn)接收到每跳平均距離HopSizei后，根據(jù)記錄的自己與信標(biāo)節(jié)點(diǎn)之間的跳數(shù)h，通過(guò)HopSizei×h計(jì)算未知節(jié)點(diǎn)到每個(gè)信標(biāo)節(jié)點(diǎn)的跳段距離。

最后，利用三邊測(cè)量法或極大似然估計(jì)法計(jì)算未知節(jié)點(diǎn)自身位置。未知節(jié)點(diǎn)與各信標(biāo)節(jié)點(diǎn)之間的跳段距離可以計(jì)算出，再利用三邊測(cè)量法或極大似然估計(jì)法計(jì)算節(jié)點(diǎn)自身位置坐標(biāo)。

DV-Hop算法中每跳平均距離是估算出來(lái)的，節(jié)點(diǎn)間的跳段距離通過(guò)每跳平均距離計(jì)算得到，所以用節(jié)點(diǎn)間的跳段距離代替節(jié)點(diǎn)間的實(shí)際直線距離是不精確的，存在誤差。在近期一些相關(guān)研究中，研究者對(duì)DV-Hop算法提出了改進(jìn)，提高了定位精度。本文提出通過(guò)粒子群優(yōu)化算法優(yōu)化每跳平均距離誤差函數(shù)，使得未知節(jié)點(diǎn)與信標(biāo)節(jié)點(diǎn)之間的跳段距離更加精確，通過(guò)三邊測(cè)量法計(jì)算得到的未知節(jié)點(diǎn)的位置也更精確，定位效果良好。

3 粒子群優(yōu)化算法改進(jìn)DV-Hop算法

粒子群優(yōu)化(Particle Swarm Optimization， PSO)算法是模擬鳥(niǎo)類捕食行為的群體智能算法，由美國(guó)電氣工程師Eberhart和社會(huì)心理學(xué)家Kennedy于1995年提出[7]。粒子群優(yōu)化算法是一種全局優(yōu)化算法，源于對(duì)鳥(niǎo)群群體運(yùn)動(dòng)行為的研究。PSO算法容易實(shí)現(xiàn)，要調(diào)整的參數(shù)少，廣泛應(yīng)用于各種領(lǐng)域。

3.1 粒子群優(yōu)化算法

粒子群優(yōu)化算法的數(shù)學(xué)描述[8]：粒子群算法中每個(gè)個(gè)體就是一個(gè)“粒子”，代表一個(gè)潛在的解，在一個(gè)D維目標(biāo)搜索空間中，每個(gè)粒子是空間內(nèi)的一個(gè)點(diǎn)，設(shè)有n個(gè)代表潛在的解的粒子組成一個(gè)群，粒子i(i=1，2，…，n)的D維位置矢量zi=(zi1，zi2，…，ziD)，zi的適應(yīng)值用來(lái)衡量粒子位置的優(yōu)劣，zi當(dāng)前的適應(yīng)值由預(yù)先設(shè)定的適應(yīng)值函數(shù)計(jì)算得到，粒子的飛行速度vi=(vi1，vi2，…，viD)，即粒子的移動(dòng)距離，記pi為粒子迄今為止搜索到的最優(yōu)位置，pi=(pi1，pi2，…，piD)，記pg為整個(gè)粒子群迄今為止搜索到的最優(yōu)位置，pg=(pg1，pg2，…，pgD)。每次迭代中，粒子根據(jù)以下式子更新速度和位置：

(4)

(5)

其中，i=1，2，…，n；d=1，2，…，D，k是迭代次數(shù)，r1和r2是[0，1]之間的隨機(jī)數(shù)，用來(lái)保持群體的多樣性，c1和c2是學(xué)習(xí)因子，粒子通過(guò)不斷學(xué)習(xí)，最后找出pg就是全局最優(yōu)解。

3.2 粒子群算法改進(jìn)DV-Hop算法過(guò)程

DV-Hop算法通過(guò)每跳平均距離乘以未知節(jié)點(diǎn)與信標(biāo)節(jié)點(diǎn)間的跳數(shù)來(lái)計(jì)算未知節(jié)點(diǎn)到信標(biāo)節(jié)點(diǎn)的距離，這個(gè)距離與實(shí)際直線距離是有誤差的，通過(guò)三邊測(cè)量法得到的坐標(biāo)也是有誤差的，通過(guò)粒子群優(yōu)化算法校正DV-Hop算法中估算得到的每跳平均距離，從而使得未知節(jié)點(diǎn)到信標(biāo)節(jié)點(diǎn)間的跳段距離更加精確，然后利用三邊測(cè)量法得到未知節(jié)點(diǎn)的坐標(biāo)，DV-Hop算法改進(jìn)過(guò)程如下：

(1) 通過(guò)信息廣播過(guò)程計(jì)算未知節(jié)點(diǎn)與每個(gè)信標(biāo)節(jié)點(diǎn)之間的最小跳數(shù)h；

(2) 通過(guò)粒子群優(yōu)化算法優(yōu)化每跳平均距離誤差函數(shù)，得到優(yōu)化后的每跳平均距離，計(jì)算出未知節(jié)點(diǎn)與信標(biāo)節(jié)點(diǎn)的跳段距離d。首先利用式(3)得到已知信標(biāo)節(jié)點(diǎn)間每跳平均距離HopSizei，設(shè)未知節(jié)點(diǎn)與信標(biāo)節(jié)點(diǎn)間實(shí)際每跳平均距離為HopSizer，則誤差函數(shù)δ=|HopSizer-HopSizei|，利用粒子群優(yōu)化算法對(duì)誤差函數(shù)進(jìn)行優(yōu)化，利用式(4)和式(5)更新粒子的位置和速度，設(shè)置適當(dāng)?shù)倪m應(yīng)值，達(dá)到迭代的次數(shù)停止運(yùn)算，找出最優(yōu)解，得到校正后的每跳平均距離HopSizea，然后通過(guò)HopSizea×h得到未知節(jié)點(diǎn)與信標(biāo)節(jié)點(diǎn)間的跳段距離d；

(3) 通過(guò)第二步得到了經(jīng)過(guò)粒子群優(yōu)化算法校正的跳段距離d，利用三邊測(cè)量法計(jì)算未知節(jié)點(diǎn)自身的位置。

4 仿真實(shí)驗(yàn)

本文使用Matlab進(jìn)行仿真實(shí)驗(yàn)，設(shè)置100 m×100 m的二維仿真環(huán)境，采用隨機(jī)分布信標(biāo)節(jié)點(diǎn)和未知節(jié)點(diǎn)的方式，分成固定信標(biāo)節(jié)點(diǎn)數(shù)量、改變節(jié)點(diǎn)總數(shù)和固定節(jié)點(diǎn)總數(shù)、改變信標(biāo)節(jié)點(diǎn)數(shù)量以及改變節(jié)點(diǎn)通信半徑等3種情況進(jìn)行仿真實(shí)驗(yàn)，通過(guò)仿真實(shí)驗(yàn)分析定位誤差的多少來(lái)對(duì)比本算法與傳統(tǒng)DV-Hop定位算法。

圖2 不同節(jié)點(diǎn)數(shù)的定位誤差曲線

圖3 不同信標(biāo)節(jié)點(diǎn)數(shù)的定位誤差曲線

圖4 不同節(jié)點(diǎn)通信半徑的定位誤差曲線

(1) 100 m×100 m區(qū)域內(nèi)，設(shè)置30個(gè)信標(biāo)節(jié)點(diǎn)，節(jié)點(diǎn)總數(shù)分別為50、100、150、200、250、300、350時(shí)仿真情況如圖2所示，定位誤差隨著節(jié)點(diǎn)數(shù)的增大而下降，通過(guò)粒子群優(yōu)化算法改進(jìn)的DV-Hop定位算法的定位誤差率比傳統(tǒng)DV-Hop定位算法的低。

(2) 100 m×100 m區(qū)域內(nèi)，設(shè)置節(jié)點(diǎn)總數(shù)300個(gè)，信標(biāo)節(jié)點(diǎn)數(shù)量為10、15、20、25、30、35時(shí)仿真情況如圖3所示，定位誤差隨著信標(biāo)節(jié)點(diǎn)數(shù)的增大而下降，通過(guò)粒子群優(yōu)化算法改進(jìn)的DV-Hop定位算法的定位誤差率比傳統(tǒng)DV-Hop定位算法的低。

(3) 100 m×100 m區(qū)域內(nèi)，設(shè)置節(jié)點(diǎn)總數(shù)300個(gè)，信標(biāo)節(jié)點(diǎn)占10%，節(jié)點(diǎn)通信半徑R從10 m到30 m遞增，節(jié)點(diǎn)通信半徑與平均定位誤差的關(guān)系如圖4所示，從圖4中可以看出，本文的改進(jìn)DV-Hop算法優(yōu)越于傳統(tǒng)的DV-Hop算法，當(dāng)節(jié)點(diǎn)的通信半徑達(dá)到30 m時(shí)，平均定位誤差下降到20%左右。

5 結(jié)束語(yǔ)

DV-Hop算法不需要測(cè)量節(jié)點(diǎn)間的絕對(duì)距離和方位，節(jié)點(diǎn)的硬件要求低，開(kāi)銷小，適合大規(guī)模布置，受環(huán)境因素影響小，適合復(fù)雜的監(jiān)測(cè)環(huán)境，但是DV-Hop算法定位精度較差，本文采用粒子群優(yōu)化算法對(duì)DV-Hop算法進(jìn)行了改進(jìn)，實(shí)驗(yàn)表明，提高了定位精度。

參考文獻(xiàn)：

[1] 張俊霞， 汪煬， 李善亮. 基于無(wú)線傳感器網(wǎng)絡(luò)的定位系統(tǒng)設(shè)計(jì)[J]. 計(jì)算機(jī)工程與應(yīng)用， 2008， 44(17)：67-70

[2] 白鳳娥， 姜曉榮， 牟匯慧. 無(wú)線傳感器網(wǎng)絡(luò)DV-Hop定位算法的研究[J]. 計(jì)算機(jī)與數(shù)字工程， 2010， 38(3)：34-36

[3] 王汝傳， 孫力娟. 無(wú)線傳感器網(wǎng)絡(luò)技術(shù)及其應(yīng)用[M]. 北京：人民郵電出版社， 2011：74-76

[4] 孫利民， 李建中， 陳渝，等. 無(wú)線傳感器網(wǎng)絡(luò)[M]. 北京：清華大學(xué)出版社， 2005：140-142

[5] 彭力. 無(wú)線傳感器網(wǎng)絡(luò)技術(shù)[M]. 北京：冶金工業(yè)出版社， 2011：73-75

[6] 趙靈鍇， 洪志全. 基于無(wú)線傳感器網(wǎng)絡(luò)的DV-Hop定位算法的改進(jìn)[J]. 計(jì)算機(jī)應(yīng)用， 2011， 31(5)：1189-1192

[7] KENNEDY J， EBERHART R. Particle swarm optimization[C]. Proceedings of the IEEE International Conference on Neural Networks， 1995：1942-1948

[8] 陳星舟， 廖明宏， 林建華. 基于粒子群優(yōu)化的無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位改進(jìn)[J]. 計(jì)算機(jī)應(yīng)用， 2010， 30(7)：1736-1738

[9] 毛會(huì)瓊， 陳世海， 范建國(guó)， 等. 基于無(wú)線傳感器網(wǎng)絡(luò)的環(huán)境監(jiān)測(cè)系統(tǒng)的設(shè)計(jì)[J]. 工礦自動(dòng)化， 2009(8)：119-121

[10] 王曉樂(lè)， 徐家品. 基于粒子群優(yōu)化算法的WSNs節(jié)點(diǎn)定位研究[J]. 計(jì)算機(jī)應(yīng)用， 2009， 29(02)：494-495