節(jié)點分區(qū)與平均跳數(shù)加權(quán)的三維DV-Hop定位算法

張伯泉，王瑞成

廣東工業(yè)大學 計算機學院，廣州 510006

1 引言

隨著無線通信技術(shù)的快速發(fā)展，無線傳感器網(wǎng)絡(luò)的應(yīng)用越來越廣。在諸多應(yīng)用中需要確定網(wǎng)絡(luò)節(jié)點的位置。因此，無線傳感器網(wǎng)絡(luò)的定位技術(shù)受到廣泛關(guān)注，成為研究熱點。對于平面布局的無線傳感器網(wǎng)絡(luò)定位需要二維定位研究，對于空間布局的無線傳感器網(wǎng)絡(luò)定位需要三維定位研究。相對于二維定位，三維定位技術(shù)應(yīng)用更加廣泛。因此，三維定位方法的研究更加熱門[1-3]。

三維定位算法研究中有基于測距與非測距這兩種定位算法?；跍y距定位算法研究的有RSSI、TOA、TDOA、AOA等[4-6]。但由于功耗、成本等方面原因，非測距定位算法更受關(guān)注。DV-Hop（Distance Vector Hop）是典型的非測距定位算法，但存在定位精度不高的缺陷。文獻[7]提出了坐標四面體質(zhì)心定位算法，但是它沒有考慮未知節(jié)點不在某個四面體內(nèi)的情況。文獻[8]提出了基于平均跳距修正的三維DV-Hop定位算法，但它需要實際距離與估計距離的差值，而差值的準確性有待提高。文獻[9]提出了一種分區(qū)的三維DV-Hop定位改進算法，提高了錨節(jié)點間跳數(shù)準確度，但沒有研究不同跳數(shù)對于定位的影響。文獻[10]提出一種跳數(shù)加權(quán)三維定位改進算法，一定程度上降低了定位的平均誤差。文獻[11]提出了一種基于初始位置投影矯正的三維定位算法，但是在實際情況中山體不能簡單地用某一條拋物面來模擬。文獻[12]提出了一種細化節(jié)點跳數(shù)的多通信半徑加權(quán)的DV-Hop改進算法，但是該算法在傳感器的能源消耗和時間效率上有一定缺陷。文獻[13]提出最小跳數(shù)偏離度的概念，并對未知節(jié)點的定位進行了修正。但是當節(jié)點的布局改變時，算法的因子調(diào)整需要進行試驗后進行調(diào)整，適用性受到限制。本文在前人研究的基礎(chǔ)上提出一種基于分區(qū)與跳數(shù)加權(quán)相結(jié)合的三維定位算法。它對無線傳感器網(wǎng)進行分區(qū)以提高跳數(shù)估計的準確性，又考慮不同跳數(shù)對于定位誤差的影響，對錨節(jié)點跳數(shù)進行加權(quán)處理，能夠有效降低網(wǎng)絡(luò)定位誤差。

2 三維DV-Hop定位算法

三維DV-Hop定位算法是對二維DV-Hop定位算法的擴展，是一種基于距離矢量無需測距定位算法[14-15]。DV-Hop算法的基本思想是將未知節(jié)點到信標節(jié)點之間的距離用平均跳距和兩者之間跳數(shù)的乘積表示，跳數(shù)計算方式是錨節(jié)點通過洪泛的方式向整個網(wǎng)絡(luò)傳播位置信息和跳數(shù)信息，其中信息發(fā)起的錨節(jié)點的跳數(shù)定義為0，當最近的節(jié)點收到此錨節(jié)點發(fā)出的信息時把跳數(shù)加1，并傳給下一個節(jié)點。當一個節(jié)點收到多個跳數(shù)信息時，進行比較，取所有跳數(shù)的最小值。其定位過程如下：

（1）計算節(jié)點間最小跳數(shù)。即確定錨節(jié)點與在通信范圍內(nèi)的未知節(jié)點間最小跳距，即兩個節(jié)點間的距離小于通信。

（2）計算未知節(jié)點與錨節(jié)點間的距離。根據(jù)位置坐標信息和步驟（1）記錄的跳數(shù)，通過式（1）估算平均跳距：

式中(xi,yi,zi)和(xj,yj,zj)為錨節(jié)點i和 j的坐標，hij是錨節(jié)點i到錨節(jié)點 j的跳數(shù)，Hopsizei表示錨節(jié)點i的平均跳距。每個未知節(jié)點利用自己的平均跳距和到各個錨節(jié)點的最小跳數(shù)的乘積，近似得到其與每個錨節(jié)點的距離。

（3）利用三邊測量法或極大似然法計算未知節(jié)點的坐標。

3 改進的三維DV-Hop定位算法

經(jīng)典DV-Hop定位算法既忽略了未知節(jié)點與錨節(jié)點間相同跳數(shù)、不同距離的情況，也沒有考慮多跳情形對平均跳距的影響。節(jié)點間跳距的計算是基于錨節(jié)點通信的直線距離，沒有考慮常見的多跳折線的情況以及相同跳數(shù)時距離不同的情況，如圖1所示。定位誤差將隨著節(jié)點間的跳距的增加而增大。

中國在全面建設(shè)和完善社會主義市場經(jīng)濟的進程中，陌生人間的交往已取代熟人間的交往而成為主導(dǎo)性和常態(tài)化的交往模式，于是在家庭和國家之間形成了一個由陌生人構(gòu)成的龐大復(fù)雜的公共交往空間。相應(yīng)地，家庭和國家對個體或組織的影響力、規(guī)范力都有所削弱，這就決定了傳統(tǒng)的以熟人共同體為背景的修齊治平的道德責任必須突破血緣和地緣的狹隘語境，經(jīng)過思想內(nèi)容的更新和創(chuàng)新才可能對以市場社會為背景的陌生人社會有規(guī)范意義。

圖1 無線傳感器網(wǎng)絡(luò)節(jié)點

圖中，A1、A2、A3為錨節(jié)點，a1、a2、a3、a4為未知節(jié)點。由圖中可知，A1到A2與A2到A3的跳數(shù)都為2，但是實際距離并不相同。

針對這兩種情況本文提出一種3DPHW-DVHop改進定位算法。算法描述如下：

（1）計算錨節(jié)點坐標的幾何中心：

（2）計算錨節(jié)點三維坐標中每一維度的方差：

（3）以最大的兩個維度方差為根據(jù)對無線傳感器網(wǎng)絡(luò)進行區(qū)域劃分區(qū)域劃分為正方形，區(qū)域的個數(shù)：

其中L和W分別為一個特定的目標區(qū)域的長度和寬度，R為傳感器的通信半徑，以R為長的正方形的外接圓直徑為 2R，設(shè)K為劃分系數(shù)，其值取決于錨節(jié)點的實際相對密度。因此，正方形的長度的設(shè)定為 2RK。

（4）以經(jīng)典DV-Hop算法中的方法計算各分區(qū)后錨節(jié)點間的跳數(shù)及每個錨節(jié)點的平均跳距，錨節(jié)點間的平均跳距表達式如下：

（5）基于跳距加權(quán)的未知節(jié)點與錨節(jié)點間的距離計算。定位實踐表明，錨節(jié)點間的跳數(shù)越少，定位誤差越小。因而越小的跳數(shù)對錨節(jié)點間平均跳距影響越大，所以跳距越小賦予的權(quán)值應(yīng)當越大。權(quán)值采用的表達式如下：

（6）由步驟（1）到（5）可計算出劃分區(qū)域后每個分區(qū)內(nèi)的平均節(jié)點跳距，本文算法采用的平均跳距表達式如式（11）所示：

其中hopsize1到hopsizeN為節(jié)點分區(qū)后計算得出的區(qū)域平均跳距，n1到nN為每個分區(qū)后區(qū)域內(nèi)的節(jié)點個數(shù)，Nodes為實驗節(jié)點總數(shù)。

（7）計算未知節(jié)點到錨節(jié)點的距離極大似然法公式如下：

4 算法仿真及結(jié)果分析

采用Matlab對本文算法進行仿真，并與3D-DVHop基本算法、3D-WD-DVHop算法以及3DPH-DVHop算法比較。無線傳感器網(wǎng)絡(luò)的三維布局設(shè)為100 m×100 m×100 m的正立方體，隨機產(chǎn)生100個網(wǎng)絡(luò)節(jié)點。實驗以錨節(jié)點數(shù)和錨節(jié)點通信半徑為變量驗證算法的平均定位誤差。

圖2為三維節(jié)點隨機分布圖，其中紅色節(jié)點為錨節(jié)點，藍色節(jié)點為未知節(jié)點。

圖2 無線傳感器網(wǎng)絡(luò)節(jié)點三維隨機布局

網(wǎng)絡(luò)平均定位誤差計算公式（12）如下：

式中，(xi,yi,zi)為未知節(jié)點 i的實際坐標，(x′i,y′i,z′i)為算法求出的未知節(jié)點的估計坐標，R為錨節(jié)點的通信半徑，N為未知節(jié)點的總數(shù)。

4.1 錨節(jié)點數(shù)對定位誤差的影響實驗

圖3節(jié)點總數(shù)為100，通信半徑為30 m。錨節(jié)點從10增加到40過程中，實驗300次得出平均網(wǎng)絡(luò)定位誤差的影響。圖3即為本文算法3DPHW-DVHop與基于加權(quán)的三維DV-Hop定位算法以及3DPH-DVHop定位算法網(wǎng)絡(luò)平均定位誤差的對比圖。

圖3 錨節(jié)點數(shù)目與定位誤差的關(guān)系

從圖3中可以看出當錨節(jié)點為10時，3DPH-DVHop定位算法相比3D-WD-DVHop定位算法平均定位誤差小4%左右，本文算法3DPHW-DVHop低于3D-WD-DVHop算法5%。說明在錨節(jié)點比例較小時，分區(qū)定位算法優(yōu)勢較為明顯，當錨節(jié)點比例達到20%，3DPH-DVHop算法與3D-WD-DVHop定位算法的平均定位誤差相對持平，而本文算法定位誤差明顯優(yōu)于這兩種算法。這是因為當錨節(jié)點個數(shù)較少時，純粹基于分區(qū)算法忽略了區(qū)域節(jié)點個數(shù)占總節(jié)點數(shù)的比重，因而在計算節(jié)點平均跳距時容易產(chǎn)生偶然性誤差，同時也沒有考慮相同跳數(shù)情況下節(jié)點實際距離不同的情況，而本文算法則綜合考慮了這兩個因素，同時對區(qū)域劃分后求出的平均跳距進行了進一步的加權(quán)求值處理?；诠?jié)點加權(quán)的算法則是因為錨節(jié)點個數(shù)較少，在計算未知節(jié)點與錨節(jié)點的跳數(shù)時，容易產(chǎn)生較大誤差。

圖4節(jié)點總數(shù)為100，通信半徑為40 m。錨節(jié)點從10到40過程中，錨節(jié)點個數(shù)與定位誤差的關(guān)系。

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

圖4所示與圖3相比，當錨節(jié)點為10的時候，本文算法的平均網(wǎng)絡(luò)誤差為45%，低于通行半徑為30 m時10%，當隨著錨節(jié)點數(shù)增加時，誤差率也是隨之減小，當錨節(jié)點增加到40時，網(wǎng)絡(luò)平均定位誤差為27%左右，低于3DPH-DVHop算法與3D-WD-DVHop定位算法3%～4%，而三種算法之間的定位誤差率相對于半徑為30 m，定位誤差相差減小，這是因為通信半徑增加，節(jié)點間的跳數(shù)總和會隨之減小，節(jié)點間的平均跳數(shù)減小，根據(jù)式（12）可知定位誤差也會隨著減小。當錨節(jié)點逐漸增多時，因本文算法相對與分區(qū)算法考慮了每個分區(qū)節(jié)點數(shù)占總節(jié)點數(shù)的比重，并對節(jié)點跳距進行的加權(quán)求值，避免了偶然性誤差，提高了定位的精確度。

圖5節(jié)點總數(shù)為100，通信半徑為40 m。錨節(jié)點從比例保持30%時，節(jié)點個數(shù)與定位誤差的關(guān)系。

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

從圖中可以得出，當錨節(jié)點數(shù)一定時，隨著通信半徑的增加，三種定位算法的網(wǎng)絡(luò)平均誤差逐漸減小，其中本文算法在半徑20 m到35 m時，本文算法的平均定位誤差明顯小于3DPH-DVHop算法和3D-DW-DVHop算法，其中主要原因歸于區(qū)域劃分后，局部節(jié)點間的跳數(shù)計算更加精確，節(jié)點平均跳距再采用跳數(shù)加權(quán)處理和區(qū)域節(jié)點平均跳距值加權(quán)處理后，局部節(jié)點定位的精確度也得到了提升。

4.2 算法綜合性能比較分析

4.2.1 時間復(fù)雜度

由前文算法描述可知，本文算法和3DPH-DVHop算法，在對選取(x,y,z)作為區(qū)域劃分的參考時，分別對每一個維度進行了求方差，時間復(fù)雜度為O(n)；在對節(jié)點坐標進行劃分分區(qū)時要計算節(jié)點所屬的區(qū)域，時間復(fù)雜度也為O(n)，相對于3D-WD-DVHop和普通3DDVHop算法多耗時O(n)，其中n為節(jié)點個數(shù)。接下來在求節(jié)點的權(quán)重時，以及最后的定位過程中時間復(fù)雜度與其他算法基本相同，而綜合整個3D-DVHop定位算法，時間復(fù)雜度為O(n2)。因此，本文算法相對于3DWD-DVHop和普通3D-DVHop算法多消耗的O(n)時間可以忽略不計。

4.2.2 空間復(fù)雜度

基于分區(qū)的3D-DVHop定位算法，在對節(jié)點進行劃分時，需要對每個節(jié)點所屬分區(qū)進行記錄，因而相對于3D-DVHop算法和3D-DW-DVHop算法多占用了O(n)的存儲空間，其中n為實驗中的節(jié)點總數(shù)。

綜上所述，本文算法比其他算法略優(yōu)，一是對區(qū)域節(jié)點進行了權(quán)值處理，二是多占用了O(n)的存儲空間；而時間復(fù)雜度與其他算法基本一致。

5 結(jié)論

基于區(qū)域劃分的加權(quán)三維定位算法，利用節(jié)點分區(qū)減小了因區(qū)域過大造成節(jié)點跳數(shù)偏大的偶然性誤差，同時節(jié)約了節(jié)點的能源消耗，然后通過節(jié)點跳距加權(quán)的方式，考慮了因節(jié)點跳數(shù)不同時，節(jié)點在定位過程中占的比重是不同的，因為在理論上，當節(jié)點間的跳數(shù)都為1時，定位精度最高。通過理論分析和實驗仿真證明，在錨節(jié)點比例較小時和節(jié)點通信距離較小時，節(jié)點平均定位誤差明顯好于其他三維定位算法，同時隨著錨節(jié)點數(shù)增加和通信距離增大時，本文算法的定位誤差率也稍微好于3DPH-DVHop算法和3D-DW-DVHop算法，在室外的三維定位中更具有實際應(yīng)用效果。不足之處在于分區(qū)的節(jié)點跳數(shù)只是基于局部最優(yōu)的節(jié)點定位算法，不是基于全局最優(yōu)的定位算法。

[1]Savvides A，Han C C，Srivastava M B.Dynamic finegrained localization in ad-hoc networks of sensors[C]//Proceeding of the 7th Annual International Conference on Mobile Computing and Networking，Rome，2001：166-179.

[2]Niculescu D，Nath B.Ad hoc positioning systems（APS）using AO-A[C]//Proceeding of the 22nd Annual Joint Conference of the IEEE Computer and Communications，San Francisco，2001：1734-1743.

[3]Wang Jing，Ghosh R K，Sajal K Das.A survey on sensor localization[J].Journal of Control Theory and Applications，2010，27（4）：1345-1352.

[4]Zhang Zhibin，Xu Xiaoling，Yan Lianlong.Underground localization algorithm of wireless sensor network based on Zigbee[J].Journal of China Coal Society，2009，34（1）：125-128.

[5]戴晨沖，宋來亮，晁代宏.基于四節(jié)點RSSI的三維空間定位算法[J].計算機測量與控制，2016，24（1）：229-232.

[6]陳慶章，毛科技，何文秀，等.基于共面度和分層結(jié)構(gòu)的WSN三維定位算法[J].電子測量與儀器學報，2012，26（8）：673-680.

[7]Chen Hongyang，Huang Pei，Martins M.Novel centroid localization algorithm for three dimensionalwireless sensor networks[C]//4th International Conference on Wireless Communications，Networking and Mobile Computing（WiCOM’08），2008：1-4.

[8]基于平均跳距修正的三維DV-Hop定位算法研究[J].無線通信技術(shù)，2013，1：50-53.

[9]Wang Ruijin，Qin Zhiguang，Wang Jahao.A new 3D positioning algorithm using partial hopsize in WSN[C]//International Conference on Communications，2014：91-95.

[10]李琳，趙可，林志貴，等.基于加權(quán)的三維DV-Hop定位算法[J].控制工程，2015，22（4）：761-764.

[11]胡中棟，肖華為.適應(yīng)山頭地形的無線傳感器網(wǎng)絡(luò)節(jié)點定位算法[J].計算機工程與應(yīng)用，2016，52（10）：104-107.

[12]劉士興，黃俊杰，劉宏銀，等.基于多通信半徑的加權(quán)DVHop定位算法[J].傳感技術(shù)學報，2015，28（6）：883-887.

[13]劉玉珍，王兆豐.基于DV-HOP改進的無線網(wǎng)絡(luò)定位算法[J].計算機工程與應(yīng)用，2016，52（4）：79-83.

[14]王新生，趙衍靜，李海濤.基于DV-HOP定位算法的改進研究[J].計算機科學，2011，38（2）：76-78.

[15]劉少強，龐新苗，樊曉平，等.一種有效提高節(jié)點定位精度的改進 DV-HOP算法[J].傳感技術(shù)學報，2010，23（8）：1179-1183.