趙建平,馬淑麗,劉鳳霞,厲成遠(yuǎn)
(曲阜師范大學(xué)物理工程學(xué)院,山東 曲阜 273165)
無線傳感器網(wǎng)絡(luò)由微型傳感器節(jié)點(diǎn)和控制系統(tǒng)、無線通信系統(tǒng)等組成,一般應(yīng)用在軍事、環(huán)境檢測[1]、森林防火、海洋等人不能夠長時間滯留的環(huán)境中,所以微型傳感器未知節(jié)點(diǎn)一般是從飛機(jī)上拋散,服從隨機(jī)分布。而錨節(jié)點(diǎn)的部署是已知的。未知節(jié)點(diǎn)位置信息的獲取對無線傳感器網(wǎng)絡(luò)的信息跟蹤等服務(wù)功能起著關(guān)鍵作用。節(jié)點(diǎn)定位的理論研究中,研究者一般采用節(jié)點(diǎn)隨機(jī)均勻分布方式仿真?,F(xiàn)有的節(jié)點(diǎn)定位算法主要分為:基于測距的定位算法和無需測距的定位算法,以及兩者的結(jié)合等?;跍y距的節(jié)點(diǎn)定位算法定位精度高但是需要復(fù)雜的硬件設(shè)備等,成本高,而無需測距的節(jié)點(diǎn)定位算法簡單成本低,但是定位精度不高,往往滿足不了一些高定位精度要求的應(yīng)用。本文考慮提高無需測距算法的定位精度,提出一種新的錨節(jié)點(diǎn)人工部署方式,并分別在二維、三維空間仿真分析對DV-Hop算法節(jié)點(diǎn)定位精度的影響。
DV-Hop定位算法是一種無需測距的節(jié)點(diǎn)定位算法,由美國羅格斯大學(xué)Dragos Niculescu等人提出[2]。
無線傳感器網(wǎng)絡(luò)是同構(gòu)的網(wǎng)絡(luò)[3]。每個節(jié)點(diǎn)的通信半徑等是相同的,節(jié)點(diǎn)間的通信是雙向的,采用自由空間電波傳播模型,輻射范圍是以自身為原點(diǎn)的圓(二維)或球(三維)。每個節(jié)點(diǎn)有自己的ID號。錨節(jié)點(diǎn)的位置是已知的,定位開始先將自己的位置信息與初始跳數(shù)值信息等以泛洪方式廣播至整個網(wǎng)絡(luò),每被轉(zhuǎn)發(fā)一次跳數(shù)值加一。根據(jù)錨節(jié)點(diǎn)間的實(shí)際距離除以節(jié)點(diǎn)間的跳數(shù)估算各自的平均每一跳距離并作為校正值廣播。未知節(jié)點(diǎn)定位時只將離自己最近的錨節(jié)點(diǎn)的校正值作為自己與其他錨節(jié)點(diǎn)的平均每跳距離。當(dāng)知道至少三個(二維)或者四個(三維)錨節(jié)點(diǎn)與未知節(jié)點(diǎn)的估算距離時,就可以用三邊測量法或極大似然估計(jì)法等進(jìn)行未知節(jié)點(diǎn)位置估算。最終得到未知節(jié)點(diǎn)坐標(biāo)信息。
以三維空間節(jié)點(diǎn)定位為例,如圖1所示[3]。
圖1 極大似然估計(jì)法示意
已知1、2、3 等 n 個錨節(jié)點(diǎn)坐分別標(biāo)為(x1,y1,z1)、(x2,y2,z2)、(x3,y3,z3)、…、(xn,yn,zn),未知節(jié)點(diǎn)到錨節(jié)點(diǎn)距離分別為d1、d2、d3、…、dn,根據(jù)以下式子,最終估算出未知節(jié)點(diǎn)坐標(biāo)(x,y,z):
將式(1)前(n-1)個方程分別減去最后一個方
現(xiàn)在許多研究者從改進(jìn)二維空間節(jié)點(diǎn)定位算法方面提高DV-Hop算法節(jié)點(diǎn)定位精度。如文獻(xiàn)[4]在二維區(qū)域提出改進(jìn)的DV-Hop算法,通過小波神經(jīng)網(wǎng)絡(luò)算法修正平均每一跳距離值,提高了節(jié)點(diǎn)定位精度。而在無線傳感器網(wǎng)絡(luò)的實(shí)際應(yīng)用中三維節(jié)點(diǎn)定位應(yīng)用更多。文獻(xiàn)[1]在三維無線傳感器網(wǎng)絡(luò)空間以DV-Hop算法為基礎(chǔ)建立空間向量模型,提高了定位精度。
從錨節(jié)點(diǎn)部署策略方面考慮提高定位精度的文獻(xiàn)較少。許多文獻(xiàn)如文獻(xiàn)[4]采用未知節(jié)點(diǎn)與錨節(jié)點(diǎn)隨機(jī)分布的仿真環(huán)境。文獻(xiàn)[5]研究了圓形區(qū)域內(nèi)節(jié)點(diǎn)分布均勻性對定位精度的影響,并在其提出的圓形均勻分布領(lǐng)域內(nèi)用三種無需測距的算法仿真。文獻(xiàn)[6]指出基于無需測距的DV-Hop定位算法的定位精度受限于網(wǎng)絡(luò)中節(jié)點(diǎn)分布的均勻性。文獻(xiàn)[7-8]各提出了一種均勻二維錨節(jié)點(diǎn)分布方式:利用歐式范數(shù),根據(jù)式(5)推導(dǎo)出相對定位誤差最小時(推導(dǎo)過程見文獻(xiàn)[8]),其錨節(jié)點(diǎn)分布滿足下式:
式中,(xm,ym)為中心錨節(jié)點(diǎn)坐標(biāo),(xi,yi)為其他錨節(jié)點(diǎn)坐標(biāo),即一個錨節(jié)點(diǎn)分布在圓形區(qū)域中心,其他錨節(jié)點(diǎn)對稱分布在區(qū)域周邊。
本文提出一種新的二維、三維錨節(jié)點(diǎn)分布方式,分別將所有錨節(jié)點(diǎn)固定在正方形內(nèi)切圓、立方體內(nèi)切球的中心,經(jīng)研究發(fā)現(xiàn)能大大提高節(jié)點(diǎn)定位精度。
絕對誤差,即節(jié)點(diǎn)的定位誤差,指未知節(jié)點(diǎn)i的定位坐標(biāo)(xi,yi)與實(shí)際坐標(biāo)(x0i,y0i)的距離,如下式:
定位精度,指網(wǎng)絡(luò)中全部節(jié)點(diǎn)(N個)的平均定位誤差與節(jié)點(diǎn)通信半徑R的比率,值越小定位精度越高,如下式:
網(wǎng)絡(luò)連通度C,反應(yīng)網(wǎng)絡(luò)中節(jié)點(diǎn)的通信密度,由網(wǎng)絡(luò)區(qū)域的邊長L、節(jié)點(diǎn)通信半徑R、節(jié)點(diǎn)總數(shù)N決定。二維網(wǎng)絡(luò)連通度、三維網(wǎng)絡(luò)連通度計(jì)算式子分別如式(9)、式(10)所示:
文獻(xiàn)[5]根據(jù)節(jié)點(diǎn)的通信輻射范圍是以自身為原點(diǎn)的圓(二維),將未知節(jié)點(diǎn)規(guī)定為圓心位置,錨節(jié)點(diǎn)在扇形區(qū)域內(nèi)均勻分布,并用3種無需測距的定位算法驗(yàn)證能提高定位精度。本文規(guī)定錨節(jié)點(diǎn)為圓心位置,其他未知節(jié)點(diǎn)在扇形區(qū)域內(nèi)隨機(jī)均勻分布。
首先將無線傳感器網(wǎng)絡(luò)監(jiān)控區(qū)域劃分為n2(4、9、16、25、36、49 等)個相同的小正方形幾何區(qū)域,在每個小正方形區(qū)域的內(nèi)切圓中心位置放置1個錨節(jié)點(diǎn)。未知節(jié)點(diǎn)在網(wǎng)絡(luò)監(jiān)控區(qū)域內(nèi)隨機(jī)均勻分布。
設(shè)定仿真環(huán)境在二維空間邊長為100 m的正方形。二維錨節(jié)點(diǎn)分布方式如圖2所示。
圖2 本文二維錨節(jié)點(diǎn)分布 n=2、3、4、5、6、7
將三維空間劃分為n3(8、27、64等)個相同小立方體空間,在每個空間的內(nèi)切球中心位置放置1個錨節(jié)點(diǎn),其他未知節(jié)點(diǎn)采用隨機(jī)均勻分布方式。
設(shè)定仿真環(huán)境在三維空間邊長為100 m的正方體。三維錨節(jié)點(diǎn)分布方式與文獻(xiàn)[1]隨機(jī)分布方式如圖3所示。
圖3 本文三維錨節(jié)點(diǎn)分布與隨機(jī)分布n=2、3、4
文獻(xiàn)[5]給出的錨節(jié)點(diǎn)最直觀的均勻分布模型為:在邊長為M m的正方形中分布m個錨節(jié)點(diǎn),錨節(jié)點(diǎn)間是等間距的,相距 M/(m0.5-1)m。文獻(xiàn)[7]提出1個錨節(jié)點(diǎn)分布在區(qū)域中心其他錨節(jié)點(diǎn)橫縱坐標(biāo)呈等差數(shù)列分布在區(qū)域的邊上。文獻(xiàn)[8]提出1個錨節(jié)點(diǎn)在區(qū)域中心,其他錨節(jié)點(diǎn)分布在以區(qū)域中心為圓心以區(qū)域邊長的一半為半徑的圓上。文獻(xiàn)[4]的節(jié)點(diǎn)分布方式是將節(jié)點(diǎn)全部隨機(jī)分布。
將仿真環(huán)境設(shè)定在邊長100 m正方形區(qū)域內(nèi),分別按本文、文獻(xiàn)[5]、文獻(xiàn)[4]的錨節(jié)點(diǎn)分布方式布置36個錨節(jié)點(diǎn),其他64個未知節(jié)點(diǎn)隨機(jī)分布。將上述3種節(jié)點(diǎn)分布方式對比,如圖4所示。
圖4 3種二維節(jié)點(diǎn)分布方式m=36
通信半徑取21 m,在3種節(jié)點(diǎn)分布方式下做DV-Hop算法的定位。3種節(jié)點(diǎn)分布方式中未知節(jié)點(diǎn)位置分布相同,并從1到64編號。每個節(jié)點(diǎn)定位誤差如圖5所示。
圖5 三種分布方式節(jié)點(diǎn)定位誤差R=21
由于節(jié)點(diǎn)分布的隨機(jī)性,將程序運(yùn)行1000次取平均值,得出錨節(jié)點(diǎn)覆蓋率36%,網(wǎng)絡(luò)連通度為13.85時,本文提出的節(jié)點(diǎn)分布方式定位精度比文獻(xiàn)[5]、文獻(xiàn)[4]分布方式分別提高4%、9.6%。
分別按本文、文獻(xiàn)[7-8]節(jié)點(diǎn)分布方式布置9個錨節(jié)點(diǎn),其他91個未知節(jié)點(diǎn)隨機(jī)分布。如圖6所示。
圖6 三種二維節(jié)點(diǎn)分布方式m=9
做DV-Hop算法的定位誤差對比,如圖7所示。
圖7 三種分布方式節(jié)點(diǎn)定位誤差R=21
將程序運(yùn)行1000次取平均值,得出錨節(jié)點(diǎn)覆蓋率9%,網(wǎng)絡(luò)連通度為13.85時,本文提出的節(jié)點(diǎn)分布方式定位精度比文獻(xiàn)[7-8]分布方式分別提高6.1%、1.3%。
錨節(jié)點(diǎn)為9時,節(jié)點(diǎn)通信半徑分別取19、22、25、28、31、34、37、40、43、46、49 m。用 DV -Hop 算法對本文與文獻(xiàn)[4]兩種環(huán)境中不同通信半徑下節(jié)點(diǎn)定位精度。程序運(yùn)行1000次取平均值,如圖8所示。
圖8 兩種分布不同通信半徑定位精度m=9
錨節(jié)點(diǎn)覆蓋率為9%時,本文分布方式在通信半徑為22 m、28 m時定位精度分別比文獻(xiàn)[4]提高約23%、12%,通信半徑為37 m時定位精度最高達(dá)到24.99%,比文獻(xiàn)[4]提高約10.2%。
錨節(jié)點(diǎn)為16個時,將程序運(yùn)行1000次取平均值,如圖9所示。
圖9 兩種分布不同通信半徑定位精度m=16
錨節(jié)點(diǎn)覆蓋率為16%時,本文分布方式在通信半徑在28 m時定位精度最高達(dá)到23.8%,比文獻(xiàn)[4]分布方式定位精度提高約7.4%。
無線傳感器網(wǎng)絡(luò)中節(jié)點(diǎn)通信半徑越低節(jié)點(diǎn)能量消耗越小[9],本文節(jié)點(diǎn)分布方式能在二維區(qū)域錨節(jié)點(diǎn)覆蓋率9%時通信半徑22、28、37 m時和錨節(jié)點(diǎn)覆蓋率為16%時通信半徑在19、22、28、31 m時定位精度比文獻(xiàn)[4]節(jié)點(diǎn)分布下定位精度明顯要高,所以本文節(jié)點(diǎn)分布方式在選擇合適的錨節(jié)點(diǎn)覆蓋率時選擇較低的通信半徑能降低節(jié)點(diǎn)能量消耗,延長網(wǎng)絡(luò)生命周期。
通信半徑為28 m時,錨節(jié)點(diǎn)覆蓋率分別取4%、9%、16%、25%、36%、49%,比較不同錨節(jié)點(diǎn)覆蓋率下本文與文獻(xiàn)[4]節(jié)點(diǎn)分布方式對DV-Hop算法定位精度的影響,將程序運(yùn)行1000次取平均值,如圖10所示。
圖10 兩種分布不同錨節(jié)點(diǎn)覆蓋率定位精度R=28
通信半徑為28 m時,本文節(jié)點(diǎn)分布方式在錨節(jié)點(diǎn)覆蓋率36%以下時定位精度比文獻(xiàn)[4]分布方式明顯要高。錨節(jié)點(diǎn)覆蓋率4%時,本文節(jié)點(diǎn)分布方式比文獻(xiàn)[4]分布方式定位精度提高27.8%。錨節(jié)點(diǎn)覆蓋率16%時定位精度最高達(dá)到26.7%,比文獻(xiàn)[4]節(jié)點(diǎn)分布方式定位精度提高約7%。
通信半徑為37 m時,將程序仿真運(yùn)行5000次取平均值,如圖11所示。
圖11 兩種分布不同錨節(jié)點(diǎn)覆蓋率定位精度R=37
通信半徑為37 m時,在不同錨節(jié)點(diǎn)覆蓋率下本文節(jié)點(diǎn)分布方式比文獻(xiàn)[4]分布方式定位精度高。隨著錨節(jié)點(diǎn)覆蓋率增大兩種分布方式下的定位精度都提高,且逐漸逼近,節(jié)點(diǎn)覆蓋率在9%、16%時本文節(jié)點(diǎn)分布方式定位精度分別達(dá)到26.9%、27.4%,比文獻(xiàn)[4]分布方式下定位精度分別提高約8%、3.2%。
由于錨節(jié)點(diǎn)微型傳感器自帶導(dǎo)航裝置成本比普通節(jié)點(diǎn)高[10],本文節(jié)點(diǎn)分布方式在通信半徑為28 m、37 m二維區(qū)域低錨節(jié)點(diǎn)覆蓋率時能明顯提高節(jié)點(diǎn)定位精度,所以本文分布方式在合適的通信半徑下選擇較低的錨節(jié)點(diǎn)覆蓋率能降低無線傳感器網(wǎng)絡(luò)的成本。
經(jīng)實(shí)驗(yàn)發(fā)現(xiàn),通信半徑越大、錨節(jié)點(diǎn)覆蓋率越高節(jié)點(diǎn)定位精度總體趨勢越好。錨節(jié)點(diǎn)覆蓋率取4%、9%、16%、25%、36%、49%,節(jié)點(diǎn)通信半徑取21、24、27、30、33、36、39、42、45、48 m。求兩種分布方式下DV-Hop定位精度之差,運(yùn)行1000次,如表1所示(加號表示提高定位精度,負(fù)號表示降低定位精度)。
表1 文獻(xiàn)[4]分布不同錨節(jié)點(diǎn)覆蓋率不同通信半徑下與本文分布定位精度差值
如表1所示,本文節(jié)點(diǎn)分布方式在較低的錨節(jié)點(diǎn)覆蓋率與較低的通信半徑下比文獻(xiàn)[4]節(jié)點(diǎn)分布方式定位精度高。說明本文節(jié)點(diǎn)分布方式在提高節(jié)點(diǎn)定位精度同時能降低無線傳感器網(wǎng)絡(luò)成本和延長網(wǎng)絡(luò)生命周期。
(1)錨節(jié)點(diǎn)27個時不同通信半徑下不同未知節(jié)點(diǎn)個數(shù)對比
在三維空間,錨節(jié)點(diǎn)個數(shù)取27個,邊長為100 m的正方體內(nèi),未知節(jié)點(diǎn)個數(shù)取 100、200、300、400、500,通信半徑取 30、32、34、36、38、40、42、44、46、48 m,分別按本文錨節(jié)點(diǎn)分布方式和文獻(xiàn)[1]錨節(jié)點(diǎn)分布方式布置錨節(jié)點(diǎn),其他未知節(jié)點(diǎn)分布采用隨機(jī)分布方式且相同。在不同通信半徑、不同未知節(jié)點(diǎn)個數(shù)下對兩種節(jié)點(diǎn)分布方式做三維DV-Hop算法定位精度對比。仿真3000次,取平均值,如圖14和圖15所示。
圖14 兩種分布不同通信半徑下不同未知節(jié)點(diǎn)數(shù)m=27
從圖14中看出本文節(jié)點(diǎn)分布方式定位精度比文獻(xiàn)[1]分布方式高。隨著通信半徑增大,兩種方式定位精度在相同未知節(jié)點(diǎn)個數(shù)下總體趨勢提高。通信半徑小于等于38 m時未知節(jié)點(diǎn)個數(shù)多的定位精度占優(yōu)勢,隨著通信半徑增大,未知節(jié)點(diǎn)個數(shù)少的定位精度占優(yōu)勢,在40 m時500個未知節(jié)點(diǎn)的定位精度與100、200的定位精度明顯拉大。
圖15 兩種分布不同未知節(jié)點(diǎn)數(shù)下不同通信半徑m=27
從圖15中看出隨著未知節(jié)點(diǎn)個數(shù)的增多,兩種方式下定位精度都逐漸提高并趨于平緩,且在相同的通信半徑和相同的未知節(jié)點(diǎn)個數(shù)下本文提出的節(jié)點(diǎn)分布方式比文獻(xiàn)[1]分布方式定位精度都要高。
在通信半徑較小、未知節(jié)點(diǎn)個數(shù)較少時,本文節(jié)點(diǎn)分布方式比文獻(xiàn)[1]節(jié)點(diǎn)分布方式能提高節(jié)點(diǎn)定位精度(如表2所示)。證明在三維空間錨節(jié)點(diǎn)數(shù)為27時,本文節(jié)點(diǎn)分布方式能提高定位精度的同時降低網(wǎng)絡(luò)成本和延長網(wǎng)絡(luò)生命周期。
表2 文獻(xiàn)[1]分布不同未知節(jié)點(diǎn)個數(shù)不同通信半徑下與本文分布定位精度差值(m=27)
(2)錨節(jié)點(diǎn)64個時不同通信半徑、不同未知節(jié)點(diǎn)個數(shù)定位精度對比
錨節(jié)點(diǎn)個數(shù)64時,未知節(jié)點(diǎn)個數(shù)取100、200、300、400、500、600、800、1000,通信半徑 28、30、32、34、36、38、40、42、44、46 m。求兩種分布方式下DV-Hop定位精度之差,仿真3000次,如表3所示。
表3 文獻(xiàn)[1]分布不同未知節(jié)點(diǎn)個數(shù)不同通信半徑下與本文分布定位精度差值(m=64)
由表3可知,本文節(jié)點(diǎn)分布方式能在較低的未知節(jié)點(diǎn)個數(shù)和較小的通信半徑下提高定位精度,說明錨節(jié)點(diǎn)數(shù)為64時,本文節(jié)點(diǎn)分布方式在三維空間也能降低網(wǎng)絡(luò)成本和延長網(wǎng)絡(luò)生命周期。
本文首先將提出的一種錨節(jié)點(diǎn)人工部署方式與其他文獻(xiàn)錨節(jié)點(diǎn)人工部署方式對比,仿真證明有一定的優(yōu)勢,然后分別在二維、三維空間下比較不同的錨節(jié)點(diǎn)覆蓋率、不同的通信半徑、不同未知節(jié)點(diǎn)數(shù)等仿真新的錨節(jié)點(diǎn)分布方式對DV-Hop算法的定位精度影響規(guī)律。MATLAB仿真結(jié)果表明本文的節(jié)點(diǎn)分布方式在節(jié)點(diǎn)數(shù)低、通信半徑較小時能有效提高節(jié)點(diǎn)定位精度。新的錨節(jié)點(diǎn)分布方式能降低網(wǎng)絡(luò)成本和節(jié)點(diǎn)能量消耗,適用于一定的無線傳感器網(wǎng)絡(luò)應(yīng)用中,缺點(diǎn)是增加了人力負(fù)擔(dān)。下一步用基于無需測距的質(zhì)心定位算法驗(yàn)證本文提出的節(jié)點(diǎn)分布方式。
[1]YAN Zang,SUN Bai- xiang,GUO Wei,LI Ming.Research on Node Localization for Wireless Sensor Networks[C]//Electric Engineering and Computer(MEC),2013 IEEE International Conference on Mechatronic Sciences.IEEE,2013:3665 -3668.
[2]陳敏,王擘,李軍華.無線傳感器網(wǎng)絡(luò)原理與實(shí)踐[M].北京:化學(xué)工業(yè)出版社,2011.CHEN Min,WANG Bo,LI Jun-h(huán)ua.Wireless Sensor Network Theory and Practice[M].Beijing:Chemical Industry Press,2011.
[3]姚向華,楊新宇,易勁剛等.無線傳感器網(wǎng)絡(luò)原理與應(yīng)用[M].北京:高等教育出版社,2012.YAO Xiang-h(huán)ua,YANG Xin-yu,YI Jin-gang,et al.Wireless Sensor Network Principle and Application[M].Beijing:Higher Education Press,2012.
[4]HU Juan,JIANG Min-lan.An Improved Node Localization Algorithm in Wireless Sensor Network[C]//Workshop on Advanced Research and Technology in Industry Application(WARTIA),IEEE ,2014:398-401.
[5]宮娜娜,武海艷.傳感器網(wǎng)絡(luò)節(jié)點(diǎn)分布均勻性與定位性能的關(guān)系[J].電子測量技術(shù),2014,37(12):80-85.GONG Na-na,WU Hai-yan.The Relationship Between the Sensor Network Node Distribution Uniformity and Positioning Performance[J].Electronic Measurement Technology,2014,37(12):80-85.
[7]黃炎炎,陳向東,倪進(jìn)權(quán)等.改進(jìn)的DV-HOP無線傳感器網(wǎng)絡(luò)定位算法[J].通信技術(shù),2014,47(07):765-769.HUANG Yan-yan,CHEN Xiang-dong,NI Jin-quan,et al.An Improved DV -Hop Localization Algorithm for Wireless Sensor Networks[J].Communications Technology,2014,47(07):765-769.
[8]ZHENG You-si,WAN Lei,SUN Zhi,MEI Shun-liang.A Long Range DV -Hop Localization Algorithm with Placement Strategy in Wireless Sensor Networks[C]//Wireless Communications,Networking and Mobile Computing,2008.WiCOM'08.4th International Conference on.[s.l.]:IEEE,2008:1 -5.
[9]劉方愛,張春花,吳楠.WSN中基于能量和距離的自適應(yīng)分層路由算法[J].計(jì)算機(jī)應(yīng)用研究,2014,31(11):3434-3437.LIU Fang-ai,ZHANG Chun-h(huán)ua,WU Nan.Adaptive Hierarchical Routing Algorithm for WSN based on Energy and Distance[J].Application Research of Computers ,2014,31(11):3434 -3437.
[10]姚英彪,姜男瀾.無線傳感器網(wǎng)絡(luò)定位的分布式求精算法[J].通信學(xué)報(bào),2015,36(01):1-10.YAO Ying-biao,JIANG Nan-lan.Distributed Refinement Algorithm for WSN Localization[J].Journal on Communications,2015,36(01):1 -10.