張伯泉,王瑞成
廣東工業(yè)大學(xué) 計(jì)算機(jī)學(xué)院,廣州 510006
隨著無(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ò)定位誤差。
三維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)。
經(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)的距離極大似然法公式如下:
采用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ù)。
圖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.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ù)雜度與其他算法基本一致。
基于區(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.