陶志勇,魏強(qiáng),劉影
遼寧工程技術(shù)大學(xué)電子與信息工程學(xué)院,遼寧葫蘆島 125105
多功率錨節(jié)點(diǎn)輔助的DV-Hop定位算法
陶志勇,魏強(qiáng),劉影
遼寧工程技術(shù)大學(xué)電子與信息工程學(xué)院,遼寧葫蘆島 125105
在無線傳感器網(wǎng)絡(luò)中,DV-Hop定位算法在計(jì)算未知節(jié)點(diǎn)到錨節(jié)點(diǎn)的距離以及通信半徑之內(nèi)相鄰節(jié)點(diǎn)跳距時(shí)存在較大誤差,提出了一種錨節(jié)點(diǎn)輔助的分布式定位算法。此算法不需要任何測距技術(shù)支持。它是利用錨節(jié)點(diǎn)的功率控制,即以不同的發(fā)射功率發(fā)射信標(biāo)信號,接收到信標(biāo)信號的未知節(jié)點(diǎn)將這些信標(biāo)信息記錄。此外還考慮了用全網(wǎng)錨節(jié)點(diǎn)來修正單獨(dú)錨節(jié)點(diǎn)的平均每跳距離,用極大似然法計(jì)算節(jié)點(diǎn)坐標(biāo)。Matlab仿真實(shí)驗(yàn)結(jié)果表明,在相同網(wǎng)絡(luò)環(huán)境下,該算法能有效減小距離計(jì)算帶來的定位誤差,可適合實(shí)際定位情況且具有較高的定位精度。
無線傳感器網(wǎng)絡(luò);節(jié)點(diǎn)定位;錨節(jié)點(diǎn);平均每跳距離;極大似然法;距離向量算法
無線傳感器網(wǎng)絡(luò)(Wireless Sensor Network,WSN),是由大量智能傳感器節(jié)點(diǎn)構(gòu)成,通過無線通信方式構(gòu)成的一個(gè)多跳的網(wǎng)絡(luò)系統(tǒng),具有環(huán)境適應(yīng)性、自組織和低成本的特點(diǎn)。在很多領(lǐng)域已經(jīng)實(shí)施應(yīng)用,例如目標(biāo)跟蹤、環(huán)境監(jiān)測、戰(zhàn)場偵察、生物醫(yī)療、搶險(xiǎn)救災(zāi)以及工業(yè)監(jiān)控等領(lǐng)域,WSN具有廣闊的應(yīng)用前景[1-2]。
無線傳感器網(wǎng)絡(luò)定位分為自定位和對外定位兩種,其中無線傳感器網(wǎng)絡(luò)中定位技術(shù)是最關(guān)鍵的技術(shù)之一。無線傳感器網(wǎng)絡(luò)自定位是通過少數(shù)已知位置的節(jié)點(diǎn)來確定大多數(shù)未知節(jié)點(diǎn)的位置。傳感器網(wǎng)絡(luò)的定位算法一般有以下特點(diǎn):自組織性、節(jié)點(diǎn)數(shù)量龐大、動態(tài)性、容錯(cuò)性好、高可靠性、能采用分布式計(jì)算的機(jī)制、遵守能量高效利用的原則。
根據(jù)定位機(jī)制,可將現(xiàn)有的無線傳感器網(wǎng)絡(luò)自定位算法分兩類:一是基于測距技術(shù)的定位算法Range-Based,例如RSSI(Received Signal Strength Indicator)[3]、TOA(Time of Arrival)、TDOA(Time Difference on Arrival)、AOA(Angel of Arrival);二是基于無需測距的定位算法Range-Free,如DV-Hop(Distance Vector-Hop)算法[4]、凸規(guī)劃算法、MDS-MAP算法、質(zhì)心算法等。
基于測距的定位機(jī)制由于實(shí)際測量節(jié)點(diǎn)間的距離或角度或時(shí)間,因此節(jié)點(diǎn)需要安裝特殊的硬件設(shè)備。通常定位精度相對比較高,但對節(jié)點(diǎn)的硬件要求也較高,實(shí)現(xiàn)起來較復(fù)雜,定位過程中消耗的能量也比較多,而且這些測量信息極易受衰弱、干擾等影響。無需測距定位算法不需要測量節(jié)點(diǎn)間的距離或角度,對硬件要求也簡單,實(shí)現(xiàn)也方便,適用于部分不需要高精度的場合。因?yàn)楣暮统杀镜囊蛩?,所以基于無需測距定位算法受到了廣泛關(guān)注。
DV-Hop算法是目前研究和應(yīng)用最為廣泛的基于無需測距的定位算法,并且對硬件要求較低,實(shí)現(xiàn)簡單。但在計(jì)算未知節(jié)點(diǎn)和錨節(jié)點(diǎn)間的距離時(shí)估算較粗糙、誤差較大。當(dāng)節(jié)點(diǎn)間跳數(shù)為1跳時(shí),不管兩節(jié)點(diǎn)之間距離到底多遠(yuǎn)或多近,DV-Hop定位算法計(jì)算出的距離是一樣的,這就會對定位造成誤差。當(dāng)節(jié)點(diǎn)跳數(shù)大于1跳時(shí),大部分節(jié)點(diǎn)之間是成折線的不是直線的,算法是用折線距離代替節(jié)點(diǎn)之間的實(shí)際距離因此也會帶來誤差。如果跳數(shù)越多,未知節(jié)點(diǎn)與錨節(jié)點(diǎn)之間路徑偏離兩點(diǎn)直線連線的可能性越大,計(jì)算出的未知節(jié)點(diǎn)與錨節(jié)點(diǎn)估計(jì)距離與真實(shí)距離誤差越大。現(xiàn)階段,對DV-Hop算法的改進(jìn)方法主要有:(1)與其他的定位算法相結(jié)合[5];(2)修正未知節(jié)點(diǎn)與錨節(jié)點(diǎn)間的距離[6];(3)改進(jìn)最后一步的定位計(jì)算方法[7],而對DV-Hop算法本身的參數(shù)優(yōu)化研究較少,定位精度不是很高,適用于定位精度要求比較低的環(huán)境中。本文對參數(shù)進(jìn)行了詳細(xì)的分析并且提出了一種新的利用錨節(jié)點(diǎn)功率控制計(jì)算節(jié)點(diǎn)間距離,結(jié)果表明可以有效地提高DV-Hop算法的定位精度。
DV-Hop算法的基本思想[8-11]:用網(wǎng)絡(luò)中節(jié)點(diǎn)之間的平均每跳距離和節(jié)點(diǎn)間的跳數(shù)乘積表示待定位節(jié)點(diǎn)間距離,然后采用三邊定位法獲取節(jié)點(diǎn)的位置信息。
DV-Hop算法步驟[12-14]:
第1步:計(jì)算最小跳數(shù)。
第2步:計(jì)算各節(jié)點(diǎn)間的實(shí)際跳數(shù)距離。第i個(gè)錨節(jié)點(diǎn)的平均每跳距離為:
式中(xi,yi)、(xj,yj)為錨節(jié)點(diǎn)i、j坐標(biāo),hij為錨節(jié)點(diǎn)i、j之間的最小跳數(shù)。
第3步:定位未知節(jié)點(diǎn)位置。將估算的平均每跳距離作為一個(gè)校正值廣播至網(wǎng)絡(luò)中,待定位的節(jié)點(diǎn)接收到校正值后,根據(jù)跳數(shù)信息計(jì)算與參考節(jié)點(diǎn)間的距離。利用三邊測量法或極大似然估計(jì)法計(jì)算出未知節(jié)點(diǎn)的位置。
3.1 多功率錨節(jié)點(diǎn)分布模型
當(dāng)未知節(jié)點(diǎn)與錨節(jié)點(diǎn)間的跳數(shù)為1跳時(shí),計(jì)算出的估計(jì)距離是一個(gè)定值。例如,節(jié)點(diǎn)隨機(jī)分布在網(wǎng)絡(luò)環(huán)境中,節(jié)點(diǎn)的通信半徑R為30 m,根據(jù)DV-Hop算法計(jì)算得到的平均每跳距離為21 m,假設(shè)1跳之內(nèi)有兩個(gè)未知節(jié)點(diǎn)a、b,它們到錨節(jié)點(diǎn)的實(shí)際距離為3 m、15 m。根據(jù)算法得出未知節(jié)點(diǎn)到錨節(jié)點(diǎn)的估計(jì)距離均為21 m,則用估計(jì)距離21 m代替實(shí)際距離3 m和15 m會有很大的誤差。如果能獲得未知節(jié)點(diǎn)到錨節(jié)點(diǎn)相對更準(zhǔn)確的距離無疑能提高未知節(jié)點(diǎn)的定位精度,因此本文依據(jù)與錨節(jié)點(diǎn)進(jìn)行通信時(shí),控制錨節(jié)點(diǎn)的發(fā)射功率來調(diào)節(jié)信號傳輸最大半徑,假如,錨節(jié)點(diǎn)有N個(gè)級別的發(fā)射功率,其對應(yīng)的信號傳輸最大半徑分別為Ri,i=1,2,…,N。這樣就可以控制錨節(jié)點(diǎn)傳輸不同長度的半徑。本文采用錨節(jié)點(diǎn)有3級發(fā)射功率,如圖1所示,對應(yīng)半徑就有三種R1、R2、R3,在這里R1取R/3,R2為2R1,R3為R。特殊說明,錨節(jié)點(diǎn)有三個(gè)通信半徑,未知節(jié)點(diǎn)只有一個(gè)通信半徑R。
圖1 錨節(jié)點(diǎn)3級發(fā)射功率節(jié)點(diǎn)分布示意圖
錨節(jié)點(diǎn)以通信半徑R(即R3)向網(wǎng)絡(luò)中廣播位置信息數(shù)據(jù)包,以得到所有節(jié)點(diǎn)到各個(gè)錨節(jié)點(diǎn)的最小跳數(shù)并記錄。其次,錨節(jié)點(diǎn)分別再以R1、R2通信半徑向全網(wǎng)廣播,并統(tǒng)計(jì)在通信半徑R1范圍內(nèi)的未知節(jié)點(diǎn)和在通信半徑R1、R2之間的未知節(jié)點(diǎn)。這樣未知節(jié)點(diǎn)到錨節(jié)點(diǎn)的距離分為四種情況。第一種情況是統(tǒng)計(jì)R1范圍內(nèi)未知節(jié)點(diǎn)到錨節(jié)點(diǎn)的距離為1/3×HopSizei;第二種情況是未知節(jié)點(diǎn)在R1~R2范圍內(nèi),計(jì)算估計(jì)距離為2/3×HopSizei;第三種情況是未知節(jié)點(diǎn)在R2~R范圍內(nèi),計(jì)算到錨節(jié)點(diǎn)的距離是HopSizei;第四種情況就是當(dāng)跳數(shù)大于1跳時(shí),計(jì)算估計(jì)距離為di。四種情況具體如下式(R=3R1=1.5R2):
這樣在上面的例子中,未知節(jié)點(diǎn)a在R1=10范圍之內(nèi),所以就用7 m取代原來的21 m,節(jié)點(diǎn)b在通信半徑R1~R2所以就用14 m取代原來的21 m,雖然與實(shí)際距離還有誤差,但總比原來的21 m來估計(jì)距離無疑提高了不少。使離未知節(jié)點(diǎn)1跳的錨節(jié)點(diǎn)的估計(jì)距離更接近實(shí)際距離,這樣就能達(dá)到提高定位精度的目的。
3.2 距離校正值修正
在經(jīng)典的DV-Hop算法中計(jì)算每個(gè)錨節(jié)點(diǎn)的平均每跳距離時(shí),如果算出的平均每跳距離誤差大會造成DV-Hop算法一系列誤差,最終定位肯定不準(zhǔn)確。算法中計(jì)算平均每跳距離是等于錨節(jié)點(diǎn)間距離之和除以錨節(jié)點(diǎn)間跳數(shù)之和。但是求未知節(jié)點(diǎn)到各個(gè)錨節(jié)點(diǎn)的距離只需最先到達(dá)的錨節(jié)點(diǎn)平均每跳距離,而未考慮其他節(jié)點(diǎn)的影響。本文改進(jìn)的算法在計(jì)算錨節(jié)點(diǎn)的平均每跳距離時(shí)不僅考慮最先接收到的平均每跳距離,同時(shí)也要考慮網(wǎng)絡(luò)環(huán)境中其他錨節(jié)點(diǎn)的平均每跳距離。
根據(jù)經(jīng)典DV-Hop算法求出各個(gè)錨節(jié)點(diǎn)的平均每跳距離,綜合考慮所有節(jié)點(diǎn)對定位精度的影響。把所有錨節(jié)點(diǎn)的平均每跳距離求均值定義為全網(wǎng)平均每跳距離。
Hdave為全網(wǎng)平均每跳距離;Hdi為第i個(gè)錨節(jié)點(diǎn)的平均每跳距離;n為錨節(jié)點(diǎn)的個(gè)數(shù)。
在此基礎(chǔ)上,對Hdave和Hdi求均值得到修正后的錨節(jié)點(diǎn)平均每跳距離Hi,這樣就充分地把所有錨節(jié)點(diǎn)分布考慮在內(nèi),進(jìn)而達(dá)到減小誤差的效果。
利用反饋的思路來驗(yàn)證求得的平均每跳距離是否誤差較大,從而更進(jìn)一步改進(jìn)平均每跳距離。用已經(jīng)求得的平均每跳距離計(jì)算各個(gè)錨節(jié)點(diǎn)之間的距離——平均每跳距離乘以跳數(shù)即得錨節(jié)點(diǎn)之間的距離。錨節(jié)點(diǎn)是位置已知的節(jié)點(diǎn),各個(gè)錨節(jié)點(diǎn)之間的真實(shí)距離可以得知,比較用平均每跳距離乘以跳數(shù)求得的估計(jì)距離和真實(shí)實(shí)際距離兩者之間的差距,并計(jì)算誤差。計(jì)算平均每跳距離誤差為:
dij為錨節(jié)點(diǎn)i,j之間的真實(shí)距離,dˉi是錨節(jié)點(diǎn)i到錨節(jié)點(diǎn)j之間的估計(jì)距離,hij為兩錨節(jié)點(diǎn)間的跳數(shù),n則為錨節(jié)點(diǎn)的總數(shù)。
將得到的錨節(jié)點(diǎn)平均每跳距離誤差來修正錨節(jié)點(diǎn)平均每跳距離Hi,可得出修正后的每個(gè)錨節(jié)點(diǎn)的平均每跳距離。
最后在利用極大似然估計(jì)法定位時(shí)當(dāng)選擇所有錨節(jié)點(diǎn)作為未知節(jié)點(diǎn)的參考錨節(jié)點(diǎn),其平均定位誤差并不會達(dá)到最小誤差的結(jié)果,而是選擇其中離未知節(jié)點(diǎn)較近的一部分錨節(jié)點(diǎn)作為參考節(jié)點(diǎn)會有更好的效果,這時(shí)得到的估計(jì)距離是最接近實(shí)際距離的。本文改進(jìn)的算法定位精度相對提高,為了更直觀,表1列出了本文算法與幾種改進(jìn)算法的部分?jǐn)?shù)據(jù)比較。
表1 不同算法的部分?jǐn)?shù)據(jù)比較m
為了驗(yàn)證改進(jìn)后算法的性能,利用Matlab對本文改進(jìn)的算法與其他算法進(jìn)行仿真對比,對比其定位精度。在100 m×100 m的無線傳感器網(wǎng)絡(luò)環(huán)境中,且仿真結(jié)果數(shù)據(jù)均取自30次仿真的平均值。分別對算法中未知節(jié)點(diǎn)數(shù)目、錨節(jié)點(diǎn)所占比例、節(jié)點(diǎn)通信半徑三個(gè)參數(shù)變化時(shí),定位誤差是如何變化的進(jìn)行仿真分析。為了便于比較,使用統(tǒng)一的評價(jià)標(biāo)準(zhǔn)為平均定位誤差,并對其做通信半徑歸一化處理。其定義式為:
(1)未知節(jié)點(diǎn)數(shù)目對定位誤差的影響
仿真環(huán)境為錨節(jié)點(diǎn)數(shù)目20,節(jié)點(diǎn)通信半徑為30 m,通過改變未知節(jié)點(diǎn)數(shù)量,觀察對定位算法誤差的影響。
由圖2可知,隨著未知節(jié)點(diǎn)個(gè)數(shù)的不斷增加,各種算法的平均定位誤差均大幅度下降,改進(jìn)的算法要比其他算法下降幅度大。未知節(jié)點(diǎn)到達(dá)120之后,誤差下降的幅度逐漸趨于平緩、穩(wěn)定。因?yàn)殡S著未知節(jié)點(diǎn)數(shù)的增加,節(jié)點(diǎn)之間聯(lián)系更加緊密,加強(qiáng)了網(wǎng)絡(luò)的連通性。
圖2 未知節(jié)點(diǎn)與定位誤差關(guān)系
(2)錨節(jié)點(diǎn)比例對定位誤差的影響
節(jié)點(diǎn)總數(shù)200,節(jié)點(diǎn)通信半徑R分別為30 m、20 m、15 m三種情況下,觀察錨節(jié)點(diǎn)比例對平均定位誤差的影響。
圖3是當(dāng)節(jié)點(diǎn)通信半徑為30 m時(shí),錨節(jié)點(diǎn)數(shù)量的增加與平均定位誤差的關(guān)系圖。從圖中可以明顯看出,隨著錨節(jié)點(diǎn)個(gè)數(shù)的不斷增加,定位誤差均呈現(xiàn)降低的趨勢。但是,當(dāng)錨節(jié)點(diǎn)的數(shù)量相同時(shí),本文提出的算法下降速度要快于其他算法。
圖3 錨節(jié)點(diǎn)與平均定位誤差關(guān)系圖(R=30)
圖4和圖5是當(dāng)節(jié)點(diǎn)通信半徑為20 m和15 m時(shí),錨節(jié)點(diǎn)數(shù)量的增加與算法平均定位誤差的關(guān)系圖。均是隨著錨節(jié)點(diǎn)數(shù)量的增加,所有算法平均定位誤差迅速下降,下降到一定程度趨于平緩,改進(jìn)的算法要比其他算法下降得快。
圖4 錨節(jié)點(diǎn)與平均定位誤差關(guān)系圖(R=20)
圖5 錨節(jié)點(diǎn)與平均定位誤差關(guān)系圖(R=15)
(3)不同通信半徑下,本文算法平均定位誤差關(guān)系
圖6是在不同的通信半徑下,改進(jìn)算法的誤差隨錨節(jié)點(diǎn)的變化情況。隨著節(jié)點(diǎn)通信半徑的增加,錨節(jié)點(diǎn)的增加平均定位誤差均明顯下降,且通信半徑為30 m時(shí),算法性能最好,定位誤差最低。
圖6 不同通信半徑下,本文算法平均定位誤差關(guān)系圖
本文對DV-Hop無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位算法進(jìn)行了研究,首先簡單介紹了原始DV-Hop算法流程,并簡要分析了算法的不足。提出了一種多功率錨節(jié)點(diǎn)輔助定位方法,使用不同發(fā)射功率來控制錨節(jié)點(diǎn)傳輸不同的通信半徑,保證了1跳之內(nèi)節(jié)點(diǎn)間距離更加精確,進(jìn)一步為校正值選取提供了可靠的數(shù)據(jù),并且對DV-Hop算法本身的參數(shù)進(jìn)行優(yōu)化,最后對改進(jìn)算法進(jìn)行仿真。仿真結(jié)果顯示,本文提出的算法其性能更好,有效地提高了算法的定位精度,網(wǎng)絡(luò)節(jié)點(diǎn)覆蓋率,算法的適應(yīng)性更強(qiáng)。
[1]趙靈鍇,洪志全.基于無線傳感器網(wǎng)絡(luò)的DV-Hop定位算法的改進(jìn)[J].計(jì)算機(jī)應(yīng)用,2011,31(5):1189-1192.
[2]Qiu R C,Zhang Changchun,Hu Zhen,et al.Towards a largescale cognitive radio network tested spectrum sensing system architecture and distributed sensing[J].Journal of Communications,2012,7(7):552-566.
[3]Chen Xiaoyan,Pei Yanli.The application of QGA in sensor optimization design[C]//Proc of the 6th International Conference on Distributed Computing and Applications for Business,Engineering and Sciences,Wuhan,China,2007:14-17.
[4]Shihong Duan,Yadong Wan,Zhiqiang Guo,et al.RAAH:Reliability Aware Adaptive Hopping scheme on timevarying channel model in WSN[J].JCIT,2013,8(1):16-25.
[5]胡斌,立方敏.基于RSSI量化模型的定位算法研究[J].武漢理工大學(xué)學(xué)報(bào),2009,31(23):92-95.
[6]劉少飛,趙清華,王華奎.基于平均跳距估計(jì)和位置修正的DV-Hop定位算法[J].傳感技術(shù)學(xué)報(bào),2009,22(8):1154-1158.
[7]王書鋒,侯義斌,黃樟欽.無線感知網(wǎng)絡(luò)最小二乘法定位算法的誤差分析與優(yōu)化[J].系統(tǒng)仿真學(xué)報(bào),2009,21(19):6211-6215.
[8]Qiu Lele,Hu Yanjun,Wang Yi,et al.A novel multimedia transmissionmethodbasedonquantizedcompressive sensing for Wireless Sensor Network[J].IJACT,2013,5(1):496-504.
[9]Zhao Chanchan,Hai Xiaowei,Jiang Xiaohua,et al.Coal mine environment monitoring with Wireless Sensor Networks[J].IJACT,2013,5(1):505-514.
[10]He T,Huang C,Blum B M,et al.Range-free localization schemes for large scale sensor networks[C]//Proceedings of the 9th Annual International Conference on Mobile Computing and Networking.San Diego:ACM Press,2003: 81-95.
[11]張震,閆連山,劉江濤,等.基于DV-Hop的無線傳感器網(wǎng)絡(luò)定位算法研究[J].傳感技術(shù)學(xué)報(bào),2011,24(10):1469-1472.
[12]王麗俠.無線傳感器網(wǎng)絡(luò)中DV-Hop算法的研究及改進(jìn)[J].唐山學(xué)院學(xué)報(bào),2013,26(3):75-78.
[13]王穎,石昊旸.改進(jìn)的無線傳感器網(wǎng)絡(luò)DV-Hop定位算法[J].計(jì)算機(jī)工程,2012,38(7):66-69.
[14]Wang Guo,Juan Wei.Optimization research of the DVHop localization algorithm[J].TELKOMNIKA Indonesian Journal of Electrical Engineering,2014,12(4):2735-2742.
[15]顧亦然,蔣璐璐.無線傳感器網(wǎng)絡(luò)定位算法研究[D].南京:南京郵電大學(xué),2012:23-30.
TAO Zhiyong,WEI Qiang,LIU Ying
School of Electronic and Information Engineering,Liaoning Technical University,Huludao,Liaoning 125105,China
In wireless sensor networks,aiming at the default that DV-Hop localization algorithm has large errors in the calculation of the distance of unknown node to an anchor node and the jump distance of the adjacent nodes in the communication radius,this paper presents an auxiliary anchor node distributed localization algorithm.This algorithm does not require any ranging technical support.It uses the power control of the anchor nodes by sending the beacon signals with different transmit powers,and the unknown nodes which receive the beacon signals will record the beacon information.It uses whole network anchors to fix separate anchor nodes on per hop distance,and then calculates the coordinates of nodes with great natural method.The Matlab simulation results show that in the same network environment,this algorithm can effectively reduce positioning errors caused by distance calculation and is suitable for the actual situation with high accuracy.
Wireless Sensor Networks(WSN);node location;anchor;average hop distance;maximum likelihood method; Distance Vector(DV)-Hop algorithm
A
TP393
10.3778/j.issn.1002-8331.1403-0101
TAO Zhiyong,WEI Qiang,LIU Ying.Improved DV-Hop localization algorithm based on more power auxiliary anchor nodes.Computer Engineering and Applications,2014,50(21):121-124.
遼寧工程技術(shù)大學(xué)研究生學(xué)院第五屆科研立項(xiàng)(No.5A2014029-01)。
陶志勇(1978—),男,博士研究生,副教授,主要研究方向:無線傳感器網(wǎng)絡(luò)、多媒體通信;魏強(qiáng)(1988—),男,通訊作者,碩士研究生,主要研究方向:無線傳感器網(wǎng)絡(luò);劉影(1983—),女,博士研究生,主要研究方向:無線傳感器網(wǎng)絡(luò)。E-mail:1102773015@qq.com
2014-03-11
2014-04-26
1002-8331(2014)21-0121-04
CNKI出版日期:2014-07-02,http://www.cnki.net/kcms/doi/10.3778/j.issn.1002-8331.1403-0101.html