趙建平，馬淑麗，劉鳳霞，厲成遠

(曲阜師范大學物理工程學院，山東 曲阜 273165)

0 引言

無線傳感器網絡由微型傳感器節(jié)點和控制系統(tǒng)、無線通信系統(tǒng)等組成，一般應用在軍事、環(huán)境檢測［1］、森林防火、海洋等人不能夠長時間滯留的環(huán)境中，所以微型傳感器未知節(jié)點一般是從飛機上拋散，服從隨機分布。而錨節(jié)點的部署是已知的。未知節(jié)點位置信息的獲取對無線傳感器網絡的信息跟蹤等服務功能起著關鍵作用。節(jié)點定位的理論研究中，研究者一般采用節(jié)點隨機均勻分布方式仿真?，F(xiàn)有的節(jié)點定位算法主要分為:基于測距的定位算法和無需測距的定位算法，以及兩者的結合等?；跍y距的節(jié)點定位算法定位精度高但是需要復雜的硬件設備等，成本高，而無需測距的節(jié)點定位算法簡單成本低，但是定位精度不高，往往滿足不了一些高定位精度要求的應用。本文考慮提高無需測距算法的定位精度，提出一種新的錨節(jié)點人工部署方式，并分別在二維、三維空間仿真分析對DV－Hop算法節(jié)點定位精度的影響。

1 概述

1.1 DV －Hop算法

DV－Hop定位算法是一種無需測距的節(jié)點定位算法，由美國羅格斯大學Dragos Niculescu等人提出［2］。

無線傳感器網絡是同構的網絡［3］。每個節(jié)點的通信半徑等是相同的，節(jié)點間的通信是雙向的，采用自由空間電波傳播模型，輻射范圍是以自身為原點的圓(二維)或球(三維)。每個節(jié)點有自己的ID號。錨節(jié)點的位置是已知的，定位開始先將自己的位置信息與初始跳數(shù)值信息等以泛洪方式廣播至整個網絡，每被轉發(fā)一次跳數(shù)值加一。根據(jù)錨節(jié)點間的實際距離除以節(jié)點間的跳數(shù)估算各自的平均每一跳距離并作為校正值廣播。未知節(jié)點定位時只將離自己最近的錨節(jié)點的校正值作為自己與其他錨節(jié)點的平均每跳距離。當知道至少三個(二維)或者四個(三維)錨節(jié)點與未知節(jié)點的估算距離時，就可以用三邊測量法或極大似然估計法等進行未知節(jié)點位置估算。最終得到未知節(jié)點坐標信息。

1.2 極大似然估計法原理

以三維空間節(jié)點定位為例，如圖1所示［3］。

圖1 極大似然估計法示意

已知1、2、3 等 n 個錨節(jié)點坐分別標為(x1，y1，z1)、(x2，y2，z2)、(x3，y3，z3)、…、(xn，yn，zn)，未知節(jié)點到錨節(jié)點距離分別為d1、d2、d3、…、dn，根據(jù)以下式子，最終估算出未知節(jié)點坐標(x，y，z):

將式(1)前(n－1)個方程分別減去最后一個方

1.3 研究現(xiàn)狀

現(xiàn)在許多研究者從改進二維空間節(jié)點定位算法方面提高DV－Hop算法節(jié)點定位精度。如文獻［4］在二維區(qū)域提出改進的DV－Hop算法，通過小波神經網絡算法修正平均每一跳距離值，提高了節(jié)點定位精度。而在無線傳感器網絡的實際應用中三維節(jié)點定位應用更多。文獻［1］在三維無線傳感器網絡空間以DV－Hop算法為基礎建立空間向量模型，提高了定位精度。

從錨節(jié)點部署策略方面考慮提高定位精度的文獻較少。許多文獻如文獻［4］采用未知節(jié)點與錨節(jié)點隨機分布的仿真環(huán)境。文獻［5］研究了圓形區(qū)域內節(jié)點分布均勻性對定位精度的影響，并在其提出的圓形均勻分布領域內用三種無需測距的算法仿真。文獻［6］指出基于無需測距的DV－Hop定位算法的定位精度受限于網絡中節(jié)點分布的均勻性。文獻［7－8］各提出了一種均勻二維錨節(jié)點分布方式:利用歐式范數(shù)，根據(jù)式(5)推導出相對定位誤差最小時(推導過程見文獻［8］)，其錨節(jié)點分布滿足下式:

式中，(xm，ym)為中心錨節(jié)點坐標，(xi，yi)為其他錨節(jié)點坐標，即一個錨節(jié)點分布在圓形區(qū)域中心，其他錨節(jié)點對稱分布在區(qū)域周邊。

本文提出一種新的二維、三維錨節(jié)點分布方式，分別將所有錨節(jié)點固定在正方形內切圓、立方體內切球的中心，經研究發(fā)現(xiàn)能大大提高節(jié)點定位精度。

1.4 其他

絕對誤差，即節(jié)點的定位誤差，指未知節(jié)點i的定位坐標(xi，yi)與實際坐標(x0i，y0i)的距離，如下式:

定位精度，指網絡中全部節(jié)點(N個)的平均定位誤差與節(jié)點通信半徑R的比率，值越小定位精度越高，如下式:

網絡連通度C，反應網絡中節(jié)點的通信密度，由網絡區(qū)域的邊長L、節(jié)點通信半徑R、節(jié)點總數(shù)N決定。二維網絡連通度、三維網絡連通度計算式子分別如式(9)、式(10)所示:

2 本文提出的錨節(jié)點分布方式

2.1 二維空間

文獻［5］根據(jù)節(jié)點的通信輻射范圍是以自身為原點的圓(二維)，將未知節(jié)點規(guī)定為圓心位置，錨節(jié)點在扇形區(qū)域內均勻分布，并用3種無需測距的定位算法驗證能提高定位精度。本文規(guī)定錨節(jié)點為圓心位置，其他未知節(jié)點在扇形區(qū)域內隨機均勻分布。

首先將無線傳感器網絡監(jiān)控區(qū)域劃分為n2(4、9、16、25、36、49 等)個相同的小正方形幾何區(qū)域，在每個小正方形區(qū)域的內切圓中心位置放置1個錨節(jié)點。未知節(jié)點在網絡監(jiān)控區(qū)域內隨機均勻分布。

設定仿真環(huán)境在二維空間邊長為100 m的正方形。二維錨節(jié)點分布方式如圖2所示。

圖2 本文二維錨節(jié)點分布 n=2、3、4、5、6、7

2.2 三維空間

將三維空間劃分為n3(8、27、64等)個相同小立方體空間，在每個空間的內切球中心位置放置1個錨節(jié)點，其他未知節(jié)點采用隨機均勻分布方式。

設定仿真環(huán)境在三維空間邊長為100 m的正方體。三維錨節(jié)點分布方式與文獻［1］隨機分布方式如圖3所示。

圖3 本文三維錨節(jié)點分布與隨機分布n=2、3、4

3 二維仿真結果分析

3.1 5種錨節(jié)點人工部署方式

文獻［5］給出的錨節(jié)點最直觀的均勻分布模型為:在邊長為M m的正方形中分布m個錨節(jié)點，錨節(jié)點間是等間距的，相距 M/(m0.5－1)m。文獻［7］提出1個錨節(jié)點分布在區(qū)域中心其他錨節(jié)點橫縱坐標呈等差數(shù)列分布在區(qū)域的邊上。文獻［8］提出1個錨節(jié)點在區(qū)域中心，其他錨節(jié)點分布在以區(qū)域中心為圓心以區(qū)域邊長的一半為半徑的圓上。文獻［4］的節(jié)點分布方式是將節(jié)點全部隨機分布。

將仿真環(huán)境設定在邊長100 m正方形區(qū)域內，分別按本文、文獻［5］、文獻［4］的錨節(jié)點分布方式布置36個錨節(jié)點，其他64個未知節(jié)點隨機分布。將上述3種節(jié)點分布方式對比，如圖4所示。

圖4 3種二維節(jié)點分布方式m=36

通信半徑取21 m，在3種節(jié)點分布方式下做DV－Hop算法的定位。3種節(jié)點分布方式中未知節(jié)點位置分布相同，并從1到64編號。每個節(jié)點定位誤差如圖5所示。

圖5 三種分布方式節(jié)點定位誤差R=21

由于節(jié)點分布的隨機性，將程序運行1000次取平均值，得出錨節(jié)點覆蓋率36%，網絡連通度為13.85時，本文提出的節(jié)點分布方式定位精度比文獻［5］、文獻［4］分布方式分別提高4%、9.6%。

分別按本文、文獻［7－8］節(jié)點分布方式布置9個錨節(jié)點，其他91個未知節(jié)點隨機分布。如圖6所示。

圖6 三種二維節(jié)點分布方式m=9

做DV－Hop算法的定位誤差對比，如圖7所示。

圖7 三種分布方式節(jié)點定位誤差R=21

將程序運行1000次取平均值，得出錨節(jié)點覆蓋率9%，網絡連通度為13.85時，本文提出的節(jié)點分布方式定位精度比文獻［7－8］分布方式分別提高6.1%、1.3%。

3.2 錨節(jié)點為9、16時不同通信半徑下對比

錨節(jié)點為9時，節(jié)點通信半徑分別取19、22、25、28、31、34、37、40、43、46、49 m。用 DV －Hop 算法對本文與文獻［4］兩種環(huán)境中不同通信半徑下節(jié)點定位精度。程序運行1000次取平均值，如圖8所示。

圖8 兩種分布不同通信半徑定位精度m=9

錨節(jié)點覆蓋率為9%時，本文分布方式在通信半徑為22 m、28 m時定位精度分別比文獻［4］提高約23%、12%，通信半徑為37 m時定位精度最高達到24.99%，比文獻［4］提高約10.2%。

錨節(jié)點為16個時，將程序運行1000次取平均值，如圖9所示。

圖9 兩種分布不同通信半徑定位精度m=16

錨節(jié)點覆蓋率為16%時，本文分布方式在通信半徑在28 m時定位精度最高達到23.8%，比文獻［4］分布方式定位精度提高約7.4%。

無線傳感器網絡中節(jié)點通信半徑越低節(jié)點能量消耗越?。?］，本文節(jié)點分布方式能在二維區(qū)域錨節(jié)點覆蓋率9%時通信半徑22、28、37 m時和錨節(jié)點覆蓋率為16%時通信半徑在19、22、28、31 m時定位精度比文獻［4］節(jié)點分布下定位精度明顯要高，所以本文節(jié)點分布方式在選擇合適的錨節(jié)點覆蓋率時選擇較低的通信半徑能降低節(jié)點能量消耗，延長網絡生命周期。

3.3 通信半徑為28 m、37 m時不同錨節(jié)點覆蓋率

通信半徑為28 m時，錨節(jié)點覆蓋率分別取4%、9%、16%、25%、36%、49%，比較不同錨節(jié)點覆蓋率下本文與文獻［4］節(jié)點分布方式對DV－Hop算法定位精度的影響，將程序運行1000次取平均值，如圖10所示。

圖10 兩種分布不同錨節(jié)點覆蓋率定位精度R=28

通信半徑為28 m時，本文節(jié)點分布方式在錨節(jié)點覆蓋率36%以下時定位精度比文獻［4］分布方式明顯要高。錨節(jié)點覆蓋率4%時，本文節(jié)點分布方式比文獻［4］分布方式定位精度提高27.8%。錨節(jié)點覆蓋率16%時定位精度最高達到26.7%，比文獻［4］節(jié)點分布方式定位精度提高約7%。

通信半徑為37 m時，將程序仿真運行5000次取平均值，如圖11所示。

圖11 兩種分布不同錨節(jié)點覆蓋率定位精度R=37

通信半徑為37 m時，在不同錨節(jié)點覆蓋率下本文節(jié)點分布方式比文獻［4］分布方式定位精度高。隨著錨節(jié)點覆蓋率增大兩種分布方式下的定位精度都提高，且逐漸逼近，節(jié)點覆蓋率在9%、16%時本文節(jié)點分布方式定位精度分別達到26.9%、27.4%，比文獻［4］分布方式下定位精度分別提高約8%、3.2%。

由于錨節(jié)點微型傳感器自帶導航裝置成本比普通節(jié)點高［10］，本文節(jié)點分布方式在通信半徑為28 m、37 m二維區(qū)域低錨節(jié)點覆蓋率時能明顯提高節(jié)點定位精度，所以本文分布方式在合適的通信半徑下選擇較低的錨節(jié)點覆蓋率能降低無線傳感器網絡的成本。

3.4 不同通信半徑和不同錨節(jié)點個數(shù)對比

經實驗發(fā)現(xiàn)，通信半徑越大、錨節(jié)點覆蓋率越高節(jié)點定位精度總體趨勢越好。錨節(jié)點覆蓋率取4%、9%、16%、25%、36%、49%，節(jié)點通信半徑取21、24、27、30、33、36、39、42、45、48 m。求兩種分布方式下DV－Hop定位精度之差，運行1000次，如表1所示(加號表示提高定位精度，負號表示降低定位精度)。

表1 文獻［4］分布不同錨節(jié)點覆蓋率不同通信半徑下與本文分布定位精度差值

如表1所示，本文節(jié)點分布方式在較低的錨節(jié)點覆蓋率與較低的通信半徑下比文獻［4］節(jié)點分布方式定位精度高。說明本文節(jié)點分布方式在提高節(jié)點定位精度同時能降低無線傳感器網絡成本和延長網絡生命周期。

4 三維仿真結果與分析

(1)錨節(jié)點27個時不同通信半徑下不同未知節(jié)點個數(shù)對比

在三維空間，錨節(jié)點個數(shù)取27個，邊長為100 m的正方體內，未知節(jié)點個數(shù)取 100、200、300、400、500，通信半徑取 30、32、34、36、38、40、42、44、46、48 m，分別按本文錨節(jié)點分布方式和文獻［1］錨節(jié)點分布方式布置錨節(jié)點，其他未知節(jié)點分布采用隨機分布方式且相同。在不同通信半徑、不同未知節(jié)點個數(shù)下對兩種節(jié)點分布方式做三維DV－Hop算法定位精度對比。仿真3000次，取平均值，如圖14和圖15所示。

圖14 兩種分布不同通信半徑下不同未知節(jié)點數(shù)m=27

從圖14中看出本文節(jié)點分布方式定位精度比文獻［1］分布方式高。隨著通信半徑增大，兩種方式定位精度在相同未知節(jié)點個數(shù)下總體趨勢提高。通信半徑小于等于38 m時未知節(jié)點個數(shù)多的定位精度占優(yōu)勢，隨著通信半徑增大，未知節(jié)點個數(shù)少的定位精度占優(yōu)勢，在40 m時500個未知節(jié)點的定位精度與100、200的定位精度明顯拉大。

圖15 兩種分布不同未知節(jié)點數(shù)下不同通信半徑m=27

從圖15中看出隨著未知節(jié)點個數(shù)的增多，兩種方式下定位精度都逐漸提高并趨于平緩，且在相同的通信半徑和相同的未知節(jié)點個數(shù)下本文提出的節(jié)點分布方式比文獻［1］分布方式定位精度都要高。

在通信半徑較小、未知節(jié)點個數(shù)較少時，本文節(jié)點分布方式比文獻［1］節(jié)點分布方式能提高節(jié)點定位精度(如表2所示)。證明在三維空間錨節(jié)點數(shù)為27時，本文節(jié)點分布方式能提高定位精度的同時降低網絡成本和延長網絡生命周期。

表2 文獻［1］分布不同未知節(jié)點個數(shù)不同通信半徑下與本文分布定位精度差值(m=27)

(2)錨節(jié)點64個時不同通信半徑、不同未知節(jié)點個數(shù)定位精度對比

錨節(jié)點個數(shù)64時，未知節(jié)點個數(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 文獻［1］分布不同未知節(jié)點個數(shù)不同通信半徑下與本文分布定位精度差值(m=64)

由表3可知，本文節(jié)點分布方式能在較低的未知節(jié)點個數(shù)和較小的通信半徑下提高定位精度，說明錨節(jié)點數(shù)為64時，本文節(jié)點分布方式在三維空間也能降低網絡成本和延長網絡生命周期。

5 結語

本文首先將提出的一種錨節(jié)點人工部署方式與其他文獻錨節(jié)點人工部署方式對比，仿真證明有一定的優(yōu)勢，然后分別在二維、三維空間下比較不同的錨節(jié)點覆蓋率、不同的通信半徑、不同未知節(jié)點數(shù)等仿真新的錨節(jié)點分布方式對DV－Hop算法的定位精度影響規(guī)律。MATLAB仿真結果表明本文的節(jié)點分布方式在節(jié)點數(shù)低、通信半徑較小時能有效提高節(jié)點定位精度。新的錨節(jié)點分布方式能降低網絡成本和節(jié)點能量消耗，適用于一定的無線傳感器網絡應用中，缺點是增加了人力負擔。下一步用基于無需測距的質心定位算法驗證本文提出的節(jié)點分布方式。

［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］陳敏，王擘，李軍華.無線傳感器網絡原理與實踐［M］.北京:化學工業(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］姚向華，楊新宇，易勁剛等.無線傳感器網絡原理與應用［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］宮娜娜，武海艷.傳感器網絡節(jié)點分布均勻性與定位性能的關系［J］.電子測量技術，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］黃炎炎，陳向東，倪進權等.改進的DV－HOP無線傳感器網絡定位算法［J］.通信技術，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中基于能量和距離的自適應分層路由算法［J］.計算機應用研究，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］姚英彪，姜男瀾.無線傳感器網絡定位的分布式求精算法［J］.通信學報，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.