節點分區與平均跳數加權的三維DV-Hop定位算法

張伯泉，王瑞成

廣東工業大學 計算機學院，廣州 510006

1 引言

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

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

2 三維DV-Hop定位算法

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

（1）計算節點間最小跳數。即確定錨節點與在通信范圍內的未知節點間最小跳距，即兩個節點間的距離小于通信。

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

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

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

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

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

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

圖1 無線傳感器網絡節點

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

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

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

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

（3）以最大的兩個維度方差為根據對無線傳感器網絡進行區域劃分區域劃分為正方形，區域的個數：

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

（4）以經典DV-Hop算法中的方法計算各分區后錨節點間的跳數及每個錨節點的平均跳距，錨節點間的平均跳距表達式如下：

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

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

其中hopsize1到hopsizeN為節點分區后計算得出的區域平均跳距，n1到nN為每個分區后區域內的節點個數，Nodes為實驗節點總數。

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

4 算法仿真及結果分析

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

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

圖2 無線傳感器網絡節點三維隨機布局

網絡平均定位誤差計算公式（12）如下：

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

4.1 錨節點數對定位誤差的影響實驗

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

圖3 錨節點數目與定位誤差的關系

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

圖4節點總數為100，通信半徑為40 m。錨節點從10到40過程中，錨節點個數與定位誤差的關系。

圖4 錨節點個數與定位誤差的關系

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

圖5節點總數為100，通信半徑為40 m。錨節點從比例保持30%時，節點個數與定位誤差的關系。

圖5 節點個數與定位誤差的關系

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

4.2 算法綜合性能比較分析

4.2.1 時間復雜度

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

4.2.2 空間復雜度

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

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

5 結論

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

[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]戴晨沖，宋來亮，晁代宏.基于四節點RSSI的三維空間定位算法[J].計算機測量與控制，2016，24（1）：229-232.

[6]陳慶章，毛科技，何文秀，等.基于共面度和分層結構的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].無線通信技術，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]李琳，趙可，林志貴，等.基于加權的三維DV-Hop定位算法[J].控制工程，2015，22（4）：761-764.

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

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

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

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

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