張伯泉，王瑞成

廣東工業(yè)大學(xué) 計(jì)算機(jī)學(xué)院，廣州 510006

1 引言

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

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

2 三維DV-Hop定位算法

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

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

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

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

（3）利用三邊測(cè)量法或極大似然法計(jì)算未知節(jié)點(diǎn)的坐標(biāo)。

3 改進(jìn)的三維DV-Hop定位算法

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

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

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

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

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

（1）計(jì)算錨節(jié)點(diǎn)坐標(biāo)的幾何中心：

（2）計(jì)算錨節(jié)點(diǎn)三維坐標(biāo)中每一維度的方差：

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

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

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

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

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

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

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

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

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

圖2為三維節(jié)點(diǎn)隨機(jī)分布圖，其中紅色節(jié)點(diǎn)為錨節(jié)點(diǎn)，藍(lán)色節(jié)點(diǎn)為未知節(jié)點(diǎn)。

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

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

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

4.1 錨節(jié)點(diǎn)數(shù)對(duì)定位誤差的影響實(shí)驗(yàn)

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

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

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

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

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

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

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

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

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

4.2 算法綜合性能比較分析

4.2.1 時(shí)間復(fù)雜度

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

4.2.2 空間復(fù)雜度

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

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

5 結(jié)論

基于區(qū)域劃分的加權(quán)三維定位算法，利用節(jié)點(diǎn)分區(qū)減小了因區(qū)域過(guò)大造成節(jié)點(diǎn)跳數(shù)偏大的偶然性誤差，同時(shí)節(jié)約了節(jié)點(diǎn)的能源消耗，然后通過(guò)節(jié)點(diǎn)跳距加權(quán)的方式，考慮了因節(jié)點(diǎn)跳數(shù)不同時(shí)，節(jié)點(diǎn)在定位過(guò)程中占的比重是不同的，因?yàn)樵诶碚撋?，?dāng)節(jié)點(diǎn)間的跳數(shù)都為1時(shí)，定位精度最高。通過(guò)理論分析和實(shí)驗(yàn)仿真證明，在錨節(jié)點(diǎn)比例較小時(shí)和節(jié)點(diǎn)通信距離較小時(shí)，節(jié)點(diǎn)平均定位誤差明顯好于其他三維定位算法，同時(shí)隨著錨節(jié)點(diǎn)數(shù)增加和通信距離增大時(shí)，本文算法的定位誤差率也稍微好于3DPH-DVHop算法和3D-DW-DVHop算法，在室外的三維定位中更具有實(shí)際應(yīng)用效果。不足之處在于分區(qū)的節(jié)點(diǎn)跳數(shù)只是基于局部最優(yōu)的節(jié)點(diǎn)定位算法，不是基于全局最優(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]戴晨沖，宋來(lái)亮，晁代宏.基于四節(jié)點(diǎn)RSSI的三維空間定位算法[J].計(jì)算機(jī)測(cè)量與控制，2016，24（1）：229-232.

[6]陳慶章，毛科技，何文秀，等.基于共面度和分層結(jié)構(gòu)的WSN三維定位算法[J].電子測(cè)量與儀器學(xué)報(bào)，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].無(wú)線通信技術(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ú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位算法[J].計(jì)算機(jī)工程與應(yīng)用，2016，52（10）：104-107.

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

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

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

[15]劉少?gòu)?qiáng)，龐新苗，樊曉平，等.一種有效提高節(jié)點(diǎn)定位精度的改進(jìn) DV-HOP算法[J].傳感技術(shù)學(xué)報(bào)，2010，23（8）：1179-1183.