汪文明，操小偉，劉桂江，施趙媛

(安慶師范學(xué)院 安徽省智能感知與計算重點(diǎn)實(shí)驗(yàn)室，安徽 安慶 246133)

?

無線傳感器網(wǎng)絡(luò)中基于反距離加權(quán)的DV-Hop改進(jìn)算法

汪文明，操小偉，劉桂江，施趙媛

(安慶師范學(xué)院 安徽省智能感知與計算重點(diǎn)實(shí)驗(yàn)室，安徽 安慶 246133)

摘要：通過分析傳統(tǒng)DV-Hop定位算法在對無線傳感器網(wǎng)絡(luò)中節(jié)點(diǎn)分布隨機(jī)性方面的不足，提出了一種改進(jìn)算法。該算法采用最小均方誤差準(zhǔn)則代替方差或偏差，求得平均每跳距離。為了體現(xiàn)各信標(biāo)節(jié)點(diǎn)對未知節(jié)點(diǎn)的影響程度不同，采用反距離加權(quán)法來處理平均每跳距離。實(shí)驗(yàn)結(jié)果表明，在沒有增加原算法復(fù)雜度和成本的前提下，定位精度有了一定提高，該算法是一種簡單實(shí)用的改進(jìn)定位算法。

關(guān)鍵詞：無線傳感器網(wǎng)絡(luò)；DV-Hop；最小均方誤差；反距離

無線傳感器網(wǎng)絡(luò)(Wireless Sensor Networks，WSN)是由大量分布在特定檢測區(qū)域中靜止或移動的傳感器以Ad hoc和多跳方式構(gòu)成的無線網(wǎng)絡(luò)，其目的就是對檢測區(qū)域中相應(yīng)對象進(jìn)行感知、數(shù)據(jù)采集、處理和網(wǎng)絡(luò)傳輸[1-4]，目前，主要應(yīng)用于軍事、環(huán)境檢測及工業(yè)等領(lǐng)域。在無線傳感網(wǎng)絡(luò)中，傳感器節(jié)點(diǎn)的位置信息非常重要，它能實(shí)現(xiàn)對監(jiān)測目標(biāo)的實(shí)時監(jiān)視及信息獲取[5]。在WSN定位機(jī)制中有需要測量各節(jié)點(diǎn)間距離或角度信息的基于測距(Range-Based)定位和無需測距(Range-Free)定位[6]。Range-Based定位算法通過相關(guān)裝置測得節(jié)點(diǎn)間的距離、角度等信息，因此定位精度相對較高，但這也是以增加節(jié)點(diǎn)成本和功耗為代價的；Range-Free定位算法依靠網(wǎng)絡(luò)連通性進(jìn)行定位，其主要有質(zhì)心算法、凸規(guī)劃定位算法、DV-Hop算法和APIT算法等[7]。文章針對DV-Hop算法的局限性提出改進(jìn)，并進(jìn)行仿真實(shí)驗(yàn)。

1DV-Hop定位算法及三邊測量法

DV-Hop[8]最初是由Niculescu等人提出的，它是一個典型的利用多跳信標(biāo)節(jié)點(diǎn)信息策略，主要包括3個階段。以圖1所示的小型傳感網(wǎng)絡(luò)為例，詳細(xì)描述這3個階段，其中，A，B，C為信標(biāo)節(jié)點(diǎn)，其余為未知節(jié)點(diǎn)。

第1階段，各信標(biāo)節(jié)點(diǎn)向周圍節(jié)點(diǎn)廣播包含其自身位置的信息及初始值為0的跳數(shù)值的數(shù)據(jù)包。接收節(jié)點(diǎn)會保留所接受到的數(shù)據(jù)包中與各信標(biāo)節(jié)點(diǎn)的最小跳數(shù)值，并將跳數(shù)值加1后轉(zhuǎn)發(fā)給鄰居節(jié)點(diǎn)。利用這種方法，最終讓所有節(jié)點(diǎn)都能獲得與信標(biāo)節(jié)點(diǎn)間的最小跳數(shù)值。對于圖1網(wǎng)絡(luò)中的節(jié)點(diǎn)R而言，它與信標(biāo)節(jié)點(diǎn)A、B、C間的最小跳數(shù)值分別為4，2，3。

圖1　網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)示意圖

第2階段，在第1階段中各節(jié)點(diǎn)均獲得了與各信標(biāo)節(jié)點(diǎn)的位置信息和跳數(shù)值。利用下式可估算出平均每跳的距離：

計算出各信標(biāo)節(jié)點(diǎn)的平均每跳距離后，通過廣播傳到整個無線傳感網(wǎng)中。但未知節(jié)點(diǎn)只會接收其最近的信標(biāo)節(jié)點(diǎn)的平均每跳距離信息，保存后并會轉(zhuǎn)發(fā)給其鄰居節(jié)點(diǎn)。未知節(jié)點(diǎn)會根據(jù)接收的信息與之前記錄的各節(jié)點(diǎn)的跳數(shù)值，計算得出它到各個信標(biāo)節(jié)點(diǎn)的距離。在圖1中，離未知節(jié)點(diǎn)R最近的信標(biāo)節(jié)點(diǎn)是B，因此，節(jié)點(diǎn)R會最先接收到B發(fā)出的平均每跳距離信息，并保存。據(jù)此，可計算出到信標(biāo)節(jié)點(diǎn)A，B，C的距離：

dA=CB×4，dB=CB×2，dC=CB×3。

第3階段，為了確定未知節(jié)點(diǎn)的位置信息，采用3邊測量[9]定位法計算。在圖1中，假設(shè)未知節(jié)點(diǎn)R的坐標(biāo)為(x,y)，測得與其通信的n個信標(biāo)節(jié)點(diǎn)的坐標(biāo)為(xi,yi)，距離為di(i=1,2,…,n)，則

上式可以轉(zhuǎn)化為AX=b的形式。其中，

用標(biāo)準(zhǔn)的最小二乘法解出位置節(jié)點(diǎn)的坐標(biāo)為

X=(ATA)-1ATb。

2改進(jìn)的DV-Hop算法

2.1最小均方誤差準(zhǔn)則求得平均每跳距離

在傳統(tǒng)的DV-Hop算法中，由公式

求得信標(biāo)節(jié)點(diǎn)的平均每跳距離，其測量誤差均值為零，N為信標(biāo)節(jié)點(diǎn)的個數(shù)。

在一般情況下，誤差都服從高斯分布，這種情況下使用均方誤差比用方差或偏差會更合理，故基于最小均方誤差準(zhǔn)則計算平均每跳距離：

其中，i,j=1,2,…,N。

2.2反距離加權(quán)處理的平均每跳距離計算

在傳統(tǒng)的DV-Hop算法中，整個WSN的平均每跳距離即為未知節(jié)點(diǎn)從其最近信標(biāo)節(jié)點(diǎn)獲取的信息。但這種方法有局限性，不能充分考慮到WSN中節(jié)點(diǎn)分布的隨機(jī)性。如果僅僅利用單個信標(biāo)節(jié)點(diǎn)的平均每跳距離會產(chǎn)生較大偏差，導(dǎo)致未知節(jié)點(diǎn)定位精度的降低；另外，未知節(jié)點(diǎn)周圍不同距離的信標(biāo)節(jié)點(diǎn)對其影響也不同。因此，為了提升定位精度，應(yīng)充分利用網(wǎng)絡(luò)中的信息，并賦予近距離信標(biāo)節(jié)點(diǎn)較大的權(quán)重，故利用反距離加權(quán)處理平均每跳距離，表示為

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

通過MATLAB R2012b平臺對傳統(tǒng)DV-Hop定位算法及改進(jìn)算法進(jìn)行仿真測試，并以平均定位誤差作為評價標(biāo)準(zhǔn)對兩種算法進(jìn)行對比分析。

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

在100 m×100 m的區(qū)域中由rand函數(shù)隨機(jī)產(chǎn)生200個節(jié)點(diǎn)，節(jié)點(diǎn)半徑R分為20 m，25 m，信標(biāo)節(jié)點(diǎn)數(shù)量從5個增長到40個(每次增長5個)，每種狀態(tài)均仿真50次，最終取其平均值。作為評價標(biāo)準(zhǔn)的平均定位誤差定義為所有被成功定位的未知節(jié)點(diǎn)的誤差之和與通信半徑的比值，公式為

3.2結(jié)果分析

從圖2和圖3可以看出，在不同的通信半徑下，改進(jìn)的定位算法與傳統(tǒng)DV-Hop算法相比，定位精度更高。在通信半徑一定的情況下，定位誤差與節(jié)點(diǎn)中信標(biāo)節(jié)點(diǎn)所占比重成反比例關(guān)系，當(dāng)信標(biāo)節(jié)點(diǎn)比重達(dá)到一定值后，定位誤差趨于穩(wěn)定。這是由于節(jié)點(diǎn)總數(shù)不變，在信標(biāo)節(jié)點(diǎn)數(shù)目較低時，未知節(jié)點(diǎn)數(shù)量遠(yuǎn)多于信標(biāo)節(jié)點(diǎn)。在進(jìn)行定位時，每個未知節(jié)點(diǎn)的距離只能通過少量的信標(biāo)節(jié)點(diǎn)來計算獲得，必然會產(chǎn)生計算誤差。另外，信標(biāo)節(jié)點(diǎn)和未知節(jié)點(diǎn)之間的距離較大，跳數(shù)較多也會產(chǎn)生較大的誤差。

圖2 信標(biāo)節(jié)點(diǎn)數(shù)目在通信半徑R=20m時誤差變化圖3 信標(biāo)節(jié)點(diǎn)數(shù)目在通信半徑R=25m時誤差變化

當(dāng)信標(biāo)節(jié)點(diǎn)所占比例相等時，隨著通信半徑的增大，定位誤差也有明顯的降低。

4結(jié)束語

針對WSN中傳感器節(jié)點(diǎn)分布的隨機(jī)性問題，提出了基于反距離加權(quán)的DV-Hop改進(jìn)算法。通過理論分析與實(shí)驗(yàn)仿真可以得出，改進(jìn)的算法與傳統(tǒng)DV-Hop算法相比，在沒有增大原算法復(fù)雜度和成本的前提下，定位性能有較大改善。

參考文獻(xiàn):

[1] 孫利民, 李建中, 陳渝, 等. 無線傳感器網(wǎng)絡(luò)[M]. 北京: 清華大學(xué)出版社, 2005.

[2] 張靜, 曹敦, 傅明, 等.DV-Hop算法定位誤差和覆蓋率的改進(jìn)[J]. 計算機(jī)應(yīng)用, 2011, 31(7): 1944-1947.

[3] 劉鋒, 張翰, 楊驥. 一種基于加權(quán)處理的無線傳感器網(wǎng)絡(luò)平均跳距離估計算法[J]. 電子與信息學(xué)報, 2008, 30(5): 1221-1225.

[4] 王振宇, 江克勤, 方木云, 等.REET無線傳感器網(wǎng)絡(luò)路由協(xié)議[J]. 安慶師范學(xué)院學(xué)報(自然科學(xué)版), 2008, 14(3): 45-47.

[5] 尚志軍, 曾鵬, 于海斌. 無線傳感網(wǎng)絡(luò)節(jié)點(diǎn)定位問題[J].計算機(jī)科學(xué), 2004, 31(10): 35-38.

[6]YangMian,QingQianqing.Researchoncurrentlocalizationtechnologyofsensornetworks[J].MicrocomputerDevelopment, 2005, 15(3): 26-28.

[7] 李云飛, 江明, 婁柯, 等. 無線傳感網(wǎng)絡(luò)中DV-Hop定位算法的改進(jìn)[J]. 計算機(jī)工程與應(yīng)用, 2014, 50(3): 79-81.

[8] 嵇瑋瑋, 劉中.DV-Hop定位算法在隨機(jī)傳感器網(wǎng)絡(luò)中的應(yīng)用研究[J]. 電子與信息學(xué)報, 2008, 30(4): 970-973.

[9]D.Niculescu.PositioninginAdHocsensornetworks[J].IEEENetwork, 2004, 18(4): 24-29.

Study on Improved DV-Hop Algorithm Based on Inverse Distance Weighting Method in Wireless Sensor Networks

WANG Wen-ming, CAO Xiao-wei, LIU Gui-jiang, SHI Zhao-yuan

(The University Key Laboratory of Intelligent Perception and Computing of Anhui Province,Anqing Teachers College, Anqing, Anhui 246133, China)

Abstract:An improved algorithm was proposed by analyzing the deficiencies of traditional DV-Hop algorithm in terms of random distribution， which owns improvements over two aspects. Firstly, instead of variance or deviation, the average one-hop distance is estimated by minimum mean-squared error criterion (MMSE). Secondly, in order to reflect the different effects of each beacon node on unknown nodes, inverse distance weighting method is adopted to deal with the average one-hop distance. Improved algorithm is simulated on MATLAB platform, and the results show that the positioning accuracy is improved on the condition of no increasing complexity and cost. The improved algorithm is a simple and practical algorithm.

Key words:wireless sensor networks, DV-Hop, minimum mean-squared error criterion(MMSE), inverse distance

文章編號：1007-4260(2016)01-0034-03

中圖分類號：TP393

文獻(xiàn)標(biāo)識碼：A

DOI：10.13757/j.cnki.cn34-1150/n.2016.01.010

作者簡介：汪文明，男，安徽懷寧人，碩士，安慶師范學(xué)院計算機(jī)與信息學(xué)院教師，研究方向?yàn)闊o線傳感器網(wǎng)絡(luò)。E-mail: 772067486@qq.com

基金項目：安慶師范學(xué)院青年基金(KJ201406,KJ201303)和“智能感知與計算”安徽省高校科研創(chuàng)新平臺項目。

*收稿日期：2015-07-29

網(wǎng)絡(luò)出版時間：2016-03-15 17:05網(wǎng)絡(luò)出版地址：http://www.cnki.net/kcms/detail/34.1150.N.20160315.1705.010.html