基于EDV-Hop的免測(cè)距定位算法研究

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

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

基于EDV-Hop的免測(cè)距定位算法研究

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

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

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

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

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

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

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

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

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

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

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

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

2.1 準(zhǔn)備階段

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

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

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

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

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

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

2.2 跳進(jìn)展分析

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

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

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

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

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

只有當(dāng)鄰居節(jié)點(diǎn)比當(dāng)前其他節(jié)點(diǎn)更接近目的節(jié)點(diǎn)D時(shí)，才能作為下一轉(zhuǎn)發(fā)節(jié)點(diǎn)。例如，節(jié)點(diǎn)n3位于節(jié)點(diǎn)S的通信范圍內(nèi)，但它比S更遠(yuǎn)離目的地D，因此不能作為S到D的中間轉(zhuǎn)發(fā)節(jié)點(diǎn)。這就使得本文必須考慮確定任何從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é)利用三邊測(cè)量技術(shù)和第2節(jié)期望跳進(jìn)展分析結(jié)果作為免測(cè)距定位EDV-Hop算法描述的基礎(chǔ)。在描述EDV-Hop算法之前，先介紹相關(guān)符號(hào)所表示的意義。P0表示期望跳進(jìn)展；ni表示節(jié)點(diǎn)ni的編號(hào)；Ai表示錨節(jié)點(diǎn)Ai的編號(hào)；Na表示網(wǎng)絡(luò)中錨節(jié)點(diǎn)的數(shù)目；Γi表示節(jié)點(diǎn)ni的鄰居節(jié)點(diǎn)集合；τi表示節(jié)點(diǎn)ni的鄰居節(jié)點(diǎn)數(shù)目；∑i

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

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

述，具體如下。

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

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

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

4 EDV-Hop算法評(píng)估

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

4.1 評(píng)估度量定義

4.2 仿真實(shí)驗(yàn)

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

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

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

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

5 結(jié)束語(yǔ)

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

無(wú)線傳感器網(wǎng)絡(luò)感知感興趣的數(shù)據(jù)具有重要的意義，節(jié)點(diǎn)物理位置估計(jì)是極其重要的。本文提出基于免測(cè)距的EDV-Hop算法估算節(jié)點(diǎn)位置。根據(jù)精度和有效性的度量，EDV-Hop算法比DV-Hop具有更好的定位性能。并且，在錨節(jié)點(diǎn)稀少的條件下，EDV-Hop算法驗(yàn)證了錨節(jié)點(diǎn)三角部署的網(wǎng)絡(luò)比方形部署的網(wǎng)絡(luò)節(jié)點(diǎn)平均定位誤差減少了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é)點(diǎn)定位算法［J］.計(jì)算機(jī)工程，2010，36（24）：90-91.

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

［12］謝昕，張恒，于忠平，等；基于能量與功率控制的TopDisc拓?fù)渌惴ㄑ芯浚跩］.華東交通大學(xué)學(xué)報(bào)，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

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

湯文亮（1969－），男，副教授，研究方向?yàn)閃SN、信息安全。