湯文亮，陳 松，周金棟，黃智水

（華東交通大學(xué)軟件學(xué)院，江西南昌 330013）

基于EDV-Hop的免測距定位算法研究

湯文亮，陳 松，周金棟，黃智水

（華東交通大學(xué)軟件學(xué)院，江西南昌 330013）

為了更好地提高無線傳感器網(wǎng)絡(luò)節(jié)點定位精度，降低定位成本，針對APS算法存在的不足，提出一種新的免測距定位算法EDV-Hop，通過限制跳數(shù)實現(xiàn)局部范圍內(nèi)的定位信息提取，同時調(diào)整平均每跳距離，以此提高定位精度。在網(wǎng)絡(luò)隨機(jī)部署和任意節(jié)點密度的條件下估算節(jié)點位置，并從精度和有效性兩個方面進(jìn)行度量。仿真結(jié)果表明，EDV-Hop算法比DV-Hop具有更好的定位性能，它能夠減少節(jié)點間通信量，降低通信成本，提高定位精度。

無線傳感器網(wǎng)絡(luò)；EDV-Hop；免測距定位；定位精度；錨節(jié)點；

目前，免測距定位算法大部分是依賴于自組織定位系統(tǒng)（APS）的思想，并把自組織定位算法作為無線傳感器網(wǎng)絡(luò)免測距定位算法的基準(zhǔn)［1-2］。在APS中，提出一種分布式的、逐跳的定位算法，此類算法能為無線傳感器網(wǎng)絡(luò)中所有節(jié)點提供近似位置信息，并且此類算法被視為距離矢量路由和GPS定位的擴(kuò)展。盡管APS簡單且實用，但是只有當(dāng)網(wǎng)絡(luò)節(jié)點密集部署、均勻分布的條件下才能得到可接受的位置估計信息。如果節(jié)點是隨機(jī)部署且不均勻的分布，則基于APS算法的定位精度急劇惡化?；贏PS定位算法的效率不高，主要有兩種觀點。第一種觀點是錨節(jié)點位置信息廣播和緊隨的估計平均跳距信息廣播分離。第二種觀點是平均跳距來自無線傳感器的整體信息，其中包括非定位信息的引入。如果網(wǎng)絡(luò)不是均勻密集部署，則會產(chǎn)生大于所必需的誤差。

針對APS算法存在的不足，本文提出基于EDV-Hop（expected distance vector-hop）的免測距定位算法，運(yùn)用該算法估計節(jié)點的位置。換言之，在網(wǎng)絡(luò)隨機(jī)部署和任意節(jié)點密度的條件下，運(yùn)用EDV-Hop算法分析跳進(jìn)展，然后估計節(jié)點位置?；卩従庸?jié)點的有效信息，節(jié)點運(yùn)用EDV-Hop定位算法可獨立地確定位置信息。另外，EDV-Hop算法可同步完成廣播錨節(jié)點位置信息及節(jié)點之間相應(yīng)距離信息。

1 EDV-Hop網(wǎng)絡(luò)模型

無線傳感器網(wǎng)絡(luò)的隨機(jī)部署，節(jié)點分布隨機(jī)、節(jié)點密度任意［3-4］。因此，我們不能假定節(jié)點在空間或者形式上分布是規(guī)則的。節(jié)點部署通常是通過低空飛機(jī)撒落或者無人地面車載工具［5-6］。

定義1 假定網(wǎng)絡(luò)中的所有節(jié)點通信能力相同，若節(jié)點ni通信半徑為r0，則其覆蓋面積M(ni,r0)=πr20。顯然，若節(jié)點ni的鄰居節(jié)點nj，則nj的鄰節(jié)點肯定包括ni。

定義2 假定E(C)為位于傳輸覆蓋范圍內(nèi)的平均節(jié)點數(shù)目，并定義EC平均連通度為某節(jié)點的傳輸覆蓋范圍內(nèi)的鄰居節(jié)點平均數(shù)目。因此，E(C)=λπr20，EC=λπr20-1。

定義3 錨節(jié)點Ai(Xi,Yi)通過GPS或人工方式確定其坐標(biāo)。

2 EDV-Hop跳進(jìn)展分析

2.1 準(zhǔn)備階段

在節(jié)點密集部署的無線傳感器網(wǎng)絡(luò)中，任何兩個節(jié)點之間存在最短的多跳路徑，如圖1所示。當(dāng)轉(zhuǎn)發(fā)下一跳時，傳輸數(shù)據(jù)遠(yuǎn)離源節(jié)點，其累積距離通過通信范圍增加而增加。因此，假如所有節(jié)點擁有同樣的傳輸范圍，則任何兩個節(jié)點之間的近似估計距離d為傳輸半徑和它們之間相應(yīng)跳計數(shù)乘積，其表達(dá)式為

式中：h為S節(jié)點和D節(jié)點之間的跳數(shù)。節(jié)點稀疏地部署，如圖2所示。大多數(shù)定位算法更傾向于采用大量不精確的距離預(yù)測，這是因為節(jié)點密度稀疏部署的無線傳感器網(wǎng)絡(luò)不適合在節(jié)點之間直接構(gòu)建最短多跳路徑。在這種情況下，下一轉(zhuǎn)發(fā)節(jié)點的路徑位于傳輸范圍邊界的概率非常低。跳進(jìn)展和傳輸半徑的相應(yīng)差異是可評估的。

圖1 無線傳感器網(wǎng)絡(luò)密集部署Fig.1 Dense deployment of WSN

圖2 無線傳感器網(wǎng)絡(luò)稀疏部署Fig.2 Sparse deployment of WSN

為了避免這個問題，本文利用期望距離矢量跳和跳計數(shù)乘積，提出估計無線傳感器網(wǎng)絡(luò)中任何S和D之間的距離，其表達(dá)式為

式中:h為S節(jié)點和D節(jié)點之間的跳計數(shù)，E(R)是鄰居節(jié)點之間的期望跳進(jìn)展。在隨機(jī)節(jié)點密度和相同的傳輸半徑的無線傳感器網(wǎng)絡(luò)中，為了得到期望跳進(jìn)展，本文引出跳進(jìn)展分析模型。

2.2 跳進(jìn)展分析

在無線傳感器網(wǎng)絡(luò)中，量化路徑距離和網(wǎng)絡(luò)參數(shù)之間的關(guān)系是非常重要的［8-9］。路徑距離定義為源節(jié)點S到目的節(jié)點D之間路徑長度，路徑長度為所有路徑當(dāng)中最短的路徑。源節(jié)點S轉(zhuǎn)發(fā)到目的節(jié)點D跳進(jìn)展的每一跳定義為R，R是隨機(jī)變量。在一維情況下，節(jié)點下一跳通常是線性方向轉(zhuǎn)發(fā)到目的節(jié)點最遠(yuǎn)一跳。然而在二維的情況下，下一跳也許不在目的節(jié)點D與源節(jié)點S的連線上，如圖3所示。

為了便于描述和分析，本節(jié)定義如下參數(shù)：

圖3 跳進(jìn)展分析Fig.3 Hop progress analysis

ri為S節(jié)點到下一潛在轉(zhuǎn)發(fā)節(jié)點ni的跳距，如圖3中的r1和r2，其中：r1=Sn1，r2=Sn2。Ri為S節(jié)點到其下一潛在轉(zhuǎn)發(fā)節(jié)點ni的跳距ri映射到S和D之間連線上，如圖3中的R1和R2。θi為S節(jié)點到其下一潛在轉(zhuǎn)發(fā)節(jié)點ni與SD的夾角，如圖3的θ1和θ2。

圖3清晰地顯示了源節(jié)點S的傳輸范圍，節(jié)點n1比節(jié)點n2緊靠S的傳輸范圍的邊界。然而，相應(yīng)的映射跳距R1小于R2，例如，當(dāng)r2＜r1時，R2＞R1。因此，S與D之間的通信，節(jié)點n2比節(jié)點n1優(yōu)先作為下一轉(zhuǎn)發(fā)節(jié)點。跳距和映射跳距之間的關(guān)系可表示為：Ri=ricosθi。

只有當(dāng)鄰居節(jié)點比當(dāng)前其他節(jié)點更接近目的節(jié)點D時，才能作為下一轉(zhuǎn)發(fā)節(jié)點。例如，節(jié)點n3位于節(jié)點S的通信范圍內(nèi)，但它比S更遠(yuǎn)離目的地D，因此不能作為S到D的中間轉(zhuǎn)發(fā)節(jié)點。這就使得本文必須考慮確定任何從S轉(zhuǎn)發(fā)到D的潛在轉(zhuǎn)發(fā)區(qū)域。

2.3 確定潛在轉(zhuǎn)發(fā)區(qū)域

圖4 潛在轉(zhuǎn)發(fā)區(qū)域確定Fig.4 Determination of potential transferring zone

3 EDV-Hop算法描述

本節(jié)利用三邊測量技術(shù)和第2節(jié)期望跳進(jìn)展分析結(jié)果作為免測距定位EDV-Hop算法描述的基礎(chǔ)。在描述EDV-Hop算法之前，先介紹相關(guān)符號所表示的意義。P0表示期望跳進(jìn)展；ni表示節(jié)點ni的編號；Ai表示錨節(jié)點Ai的編號；Na表示網(wǎng)絡(luò)中錨節(jié)點的數(shù)目；Γi表示節(jié)點ni的鄰居節(jié)點集合；τi表示節(jié)點ni的鄰居節(jié)點數(shù)目；∑i

pc表示到錨節(jié)點Ai的當(dāng)前累積跳進(jìn)展；∑iHC表示到錨節(jié)點Ai的當(dāng)前累積跳計數(shù)；∑i Pr表

示收到到錨節(jié)點Ai的當(dāng)前累積跳進(jìn)展；∑iHr表示收到到錨節(jié)點Ai的當(dāng)前累積跳計數(shù)。EDV-Hop算法描

述，具體如下。

初始化階段：節(jié)點與其相連通的鄰居節(jié)點交換問候數(shù)據(jù)包。鄰居節(jié)點之間數(shù)據(jù)交換僅限于單跳通信，不允許轉(zhuǎn)播問候數(shù)據(jù)包。實際上，節(jié)點會保存Γi和τi的信息，該信息從來自其鄰居節(jié)點的問候數(shù)據(jù)包中獲取。例如，每個問候數(shù)據(jù)包包含發(fā)送節(jié)點nj的ID號，然后任何節(jié)點ni在nj的傳輸范圍內(nèi)能得到問候數(shù)據(jù)包，再后ni檢查是否一個重復(fù)的數(shù)據(jù)包，如果是，則忽略該數(shù)據(jù)包，否則更新本地數(shù)據(jù)庫。

待初始化階段和處理階段順利完成之后，采用三邊測量技術(shù)計算出節(jié)點位置。

值得一提，EDV-Hop算法不同于DV-Hop算法。DV-Hop算法在兩個不同的階段，廣播錨節(jié)點位置坐標(biāo)和鄰居節(jié)點之間的平均跳距，采用超過必需的通信開銷，增加通信時延。EDV-Hop算法廣播錨節(jié)點位置坐標(biāo)的同時估計節(jié)點之間的相應(yīng)跳距，該算法是在一個階段內(nèi)完成。因此，EDV-Hop算法可顯著地降低了網(wǎng)絡(luò)通信和傳輸時延。

4 EDV-Hop算法評估

在網(wǎng)絡(luò)設(shè)置相同的環(huán)境下，根據(jù)已定義好的度量指標(biāo)，對EDV-Hop、DV-Hop算法進(jìn)行比較。并且，仿真驗證EDV-Hop算法采用不同錨節(jié)點部署方式對平均誤差的影響。

4.1 評估度量定義

4.2 仿真實驗

仿真實驗中，假設(shè)200個節(jié)點按2維泊松分布部署在方形區(qū)域內(nèi)，傳輸半徑為10 m，方形區(qū)域A＝50×50 m2。本文通過改變部署節(jié)點數(shù)目，得到不同的節(jié)點密度和連通性。

在無線傳感器網(wǎng)絡(luò)中，這兩種算法采用到錨節(jié)點的距離估計估計節(jié)點的位置。毫無疑問更精確的距離估計得到更好的位置估計。根據(jù)位置估計誤差，圖7顯示位置估計精度。圖5表明EDV-Hop算法在位置估計誤差偏離實際位置r0范圍內(nèi)的節(jié)點比例超過90%。另外，超過70%的節(jié)點估計位置與實際位置的誤差在r02范圍內(nèi)，而DV-Hop只有49%的節(jié)點能實現(xiàn)這樣的功能。因此，EDV-Hop算法比DV-Hop算法具有更好的位置估計性能。

研究錨節(jié)點采用三角或方形部署對EDV-Hop算法的性能影響。在網(wǎng)絡(luò)參數(shù)相同的條件下，采用不同的錨節(jié)點部署方式，分別研究其對平均誤差的影響。改變節(jié)點在感興趣區(qū)域內(nèi)的數(shù)目，數(shù)目變化區(qū)間為100～400。在三角和方形部署的策略下，圖6顯示了平均誤差范圍。顯然，當(dāng)節(jié)點連通性增加，這兩種部署方案的平均定位誤差都減少了。這實際上是因為節(jié)點連通性越高，節(jié)點更能直接或者最短跳距到達(dá)錨節(jié)點，精確位置估計的節(jié)點就更多。另外，仿真結(jié)果表明，在同樣的網(wǎng)絡(luò)設(shè)置以及更少的錨節(jié)點條件下，三角錨節(jié)點部署的平均誤差范圍小于方形錨節(jié)點部署。因此，在無線傳感器網(wǎng)絡(luò)中本文推斷錨節(jié)點的部署對定位系統(tǒng)來說同樣是至關(guān)重要的，仿真結(jié)果表明：錨節(jié)點三角部署的網(wǎng)絡(luò)比方形部署的網(wǎng)絡(luò)定位性能更優(yōu)。

圖5 位置誤差分布Fig.5 Distribution of position errors

5 結(jié)束語

圖6 錨節(jié)點不同部署的平均誤差Fig.6 Average error of anchor nodes in different deployment

無線傳感器網(wǎng)絡(luò)感知感興趣的數(shù)據(jù)具有重要的意義，節(jié)點物理位置估計是極其重要的。本文提出基于免測距的EDV-Hop算法估算節(jié)點位置。根據(jù)精度和有效性的度量，EDV-Hop算法比DV-Hop具有更好的定位性能。并且，在錨節(jié)點稀少的條件下，EDV-Hop算法驗證了錨節(jié)點三角部署的網(wǎng)絡(luò)比方形部署的網(wǎng)絡(luò)節(jié)點平均定位誤差減少了10%左右。

［1］WONG S Y，LIM J G，RAO S，et al.Density-aware Hop-count localization in wireless sensor networks with variable density［C］//Proc.IEEE Wireless Comm.and Networking Conf.（WCNC 05），2005：1848-1853.

［2］XIAO Q J，XIAO B，CAO J N，et al.Multihop range-free localization in anisotropic wireless sensor networks：a pattern-driven scheme［J］.IEEE Transactions on mobile computing，2010，9（11）：1592-1607.

［3］ WANG C，LIU K，XIAO N.A range free localization algorithm based on restricted-area for wireless sensor networks［C］//ICCGI'08，2008：97-101.

［4］SUN YU R，MEI S L.APower-aware and range-free localization algorithm for sensor networks［C］//APCC'06，2006：1-5.

［5］ WANG X.Qos issues and qos constrained design of wireless sensor network［D］.Ph.D dissertation，Univ.of Cincinnati，2006：111.

［6］ WANG L，XIAO Y.A survey of energy-efficient scheduling mechanisms in sensor network［J］.Mobile Network Applications，2006，11（5）：723-740.

［7］WANG Y，WANG X，XIE B，et al.Intrusion detection in homogenous and heterogeneous wireless sensor networks［J］.IEEE Transactions on Mobile Computing，2008，7（6）：698-711.

［8］ NASIPURI A，LI K.A directionality based location discovery scheme for wireless sensor networks［C］//Proc.First ACM Int’l Workshop Wireless Sensor Networks andApplications，2002：105-111.

［9］ CAI SHAOBIN，LI XI，GAO ZHENGUO，et al.Modified improved alternating combination trilateration algorithm with a variable［C］//International Multisymposiums on Computer and Computational Sciences，2008：98-101.

［10］徐小卜，王勇，陶曉玲.基于支持向量機(jī)分類的WSN節(jié)點定位算法［J］.計算機(jī)工程，2010，36（24）：90-91.

［11］湯文亮，黃智水.無約束插值的Monte Carlo無線傳感器網(wǎng)絡(luò)節(jié)點定位方法［J］.傳感器與微系統(tǒng)，2010，29（5）：54-55.

［12］謝昕，張恒，于忠平，等；基于能量與功率控制的TopDisc拓?fù)渌惴ㄑ芯浚跩］.華東交通大學(xué)學(xué)報，2010，27（3）：58-61+87.

AResearch on Range-free LocalizationAlgorithm Based on EDV-Hop

Tang Wenliang，Chen Song，Zhou Jindong，Huang Zhishui
（School of Software，East China Jiaotong University，Nanchang 330013，China）

In order to improve node location accuracy in wireless sensor networks and reduce the cost，the paper puts forward a new Range-free Localization algorithm，EDV-Hop，to overcome the shortcomings of the APS.Local localization information extraction is realized by limiting the hopping number；the location accuracy is improved by adjusting the average distance per hop.In the condition that the nodes in the network are deployed randomly and the density of the nodes is arbitrary，the paper estimates the location of nodes，and measures it from both accuracy and effectiveness.The simulation results show that EDV-Hop algorithm has better positioning performance than DV-Hop，and that it can reduce the traffic among the nodes，reduce the communication cost and improve the location accuracy.

wireless sensor network；EDV-Hop；range-free localization algorithm；location accuracy；anchor node

TP393.3

A

1005-0523（2012）03-0040-06

2012-03-15

國家自然科學(xué)基金項目（61162001；31101081）；江西省科技工業(yè)支撐計劃項目（2010BGA02200）

湯文亮（1969－），男，副教授，研究方向為WSN、信息安全。