A Localization Algorithm for Wireless Sensor Networks with Asymmetric Links*

ZHANG Yaming，SHI Haoshan*，LIU Yan，CHENG Wei

(1.School of Electronics and Information，Northwestern Polytechnical University，Xi’an 710072，China; 2.National Key Lab.of Antennas and Microwave Technology，Xidian University，Xi’an 710071，China)

A Localization Algorithm for Wireless Sensor Networks with Asymmetric Links*

ZHANG Yaming1，SHI Haoshan1*，LIU Yan2，CHENG Wei1

(1.School of Electronics and Information，Northwestern Polytechnical University，Xi’an 710072，China; 2.National Key Lab.of Antennas and Microwave Technology，Xidian University，Xi’an 710071，China)

For conquering the problem of poor locating performance by using DV-Hop algorithm in the complex environment with asymmetric links.Several approaches were put forwarded in this paper.Firstly，a neighbor nodes mining method is used for ensure the accurate identification of adjacent nodes.Secondly，the minimum hop-count mechanism is used for calculate the real hop count between nodes.Thirdly，a new method of computing average hop-size is adopted to reduce its error.And then，a novel method of solving a system of equations is presented to estimation the initial location of unknown node.Finally，a coordinate calibration technology is used to further improve the positioning accuracy.Simulation results show that，the improved algorithm can effectively avoid the influence of asymmetric links，significantly improve the positioning accuracy and reduce the cost of network.

wireless sensor networks(WSNs);localization;DV-Hop algorithm;asymmetric links

隨著無線傳感器網(wǎng)絡(luò)應用的日趨復雜和多樣化，作為其關(guān)鍵技術(shù)的節(jié)點定位技術(shù)得到了國內(nèi)外學者的持續(xù)關(guān)注和研究。按照是否需要測量節(jié)點間距離，現(xiàn)有定位算法可分為基于測距的(Range-Based)定位和無需測距的(Range-Free)定位兩類［1］。Rangebased定位首先使用測距技術(shù)獲得節(jié)點間距離或角度信息，然后使用三邊測量法、三角測量法或極大似然估計法計算未知節(jié)點坐標。這種定位機制雖然定位精度較高但通常需要配備額外的特殊硬件設(shè)備，會造成較大的成本和能耗負擔。Range-free定位不需要測量節(jié)點間距離或方位，僅依靠相鄰節(jié)點間的連通關(guān)系或利用節(jié)點間的估計距離計算節(jié)點位置。如今，隨著Range-Free定位算法在成本控制等方面優(yōu)勢的進一步體現(xiàn)，它已經(jīng)被視為一種高性價比的、簡單易行且定位精度可接受的定位方式而倍受重視。DV-hop算法［2］作為無需測距定位算法的典型代表，是目前應用最廣泛的定位算法之一，有著極其重要的研究價值。隨著無線傳感器網(wǎng)絡(luò)研究和應用的進一步深入，針對DV-Hop算法的改進研究倍受重視。然而多數(shù)文獻［3-10］局限于對個別問題的研究改進，缺乏對整個網(wǎng)絡(luò)系統(tǒng)的全面考慮，更很少考慮真實環(huán)境，特別是復雜環(huán)境中存在的大量不對稱鏈路對DV-Hop算法的影響。文獻［11］通過對由26個節(jié)點組成的無線傳感器網(wǎng)絡(luò)進行鏈路質(zhì)量測量，驗證了無線傳感器網(wǎng)絡(luò)中的通信鏈路存在不對稱性。文獻［12］對無線傳感器網(wǎng)絡(luò)中鏈路存在不規(guī)則性進行了更深入的分析，發(fā)現(xiàn)導致鏈路不規(guī)則的原因有兩大類，即傳輸介質(zhì)(如介質(zhì)類型、噪聲和溫度、障礙物等)和設(shè)備(如天線類型和增益、發(fā)射功率、接收機門限值等)。文獻［13］通過對密集傳感器網(wǎng)絡(luò)的研究表明，數(shù)據(jù)報文接收率在真實環(huán)境中會隨時間和空間因素變化，大約有5%到15%的鏈路是不對稱鏈路，且環(huán)境約復雜不對稱鏈路比例越高。這種不對稱鏈路會嚴重影響DV-Hop定位算法中平均跳距和節(jié)點間距離的估算，進而影響到算法的定位精度。

鑒于以上研究和分析，本文提出了一種可用于復雜環(huán)境的改進的DV-Hop定位算法。該算法首先采用鄰居挖掘機制確保相鄰節(jié)點之間能準確識別，然后利用最小跳數(shù)方法更準確的計算未知節(jié)點到每個信標節(jié)點的最小跳數(shù);接著采用改進的平均跳距計算方法減小平均跳距誤差;然后采用一種新的方程組求解方法完成節(jié)點初步定位;最后使用一種簡單的坐標校準技術(shù)，進一步提高定位精度。

1 DV-Hop算法原理

DV-Hop算法［2］是由美國路特葛斯大學Niculescu等人提出的類似于傳統(tǒng)網(wǎng)絡(luò)中距離向量路由機制的一種免測距無線傳感器網(wǎng)絡(luò)定位算法。其過程可分3個階段，簡單描述如下:

第1階段通過典型的距離矢量交換協(xié)議使每個節(jié)點獲取到每個錨節(jié)點的最小跳數(shù)。

第2階段計算未知節(jié)點與錨節(jié)點之間的距離。在此階段，每個錨節(jié)點根據(jù)第1階段中記錄的其它錨節(jié)點的位置信息和相距跳數(shù)，利用式(1)估算出平均跳距HopSize。然后，將該平均跳距作為校正值通過帶有生存期字段的分組廣播至網(wǎng)絡(luò)中，未知節(jié)點僅存儲接收到的第1個校正值，并轉(zhuǎn)發(fā)給鄰居節(jié)點，忽略所有后收到的校正值。未知節(jié)點接收到平均跳距后乘以其到錨節(jié)點的最小跳數(shù)，即可得到其與相應錨節(jié)點之間的估計距離(利用跳段距離代替直線距離)。

式中，(xi，yi)表示錨節(jié)點i的坐標;(xj，yj)表示錨節(jié)點j的坐標;hij表示錨節(jié)點i，j之間的最小跳數(shù)。

第3階段利用三邊定位法或極大似然估計法計算自身位置。

2 不對稱鏈路對DV-Hop算法影響

本文以圖1所示網(wǎng)絡(luò)拓撲結(jié)構(gòu)為例分析不對稱鏈路對DV-Hop算法的影響。在圖1所示網(wǎng)絡(luò)中，部分節(jié)點間的通信鏈路是不對稱鏈路，即因為設(shè)備或介質(zhì)等因素影響，某些相鄰節(jié)點間只能單向通信。例如10號節(jié)點能夠直接接收到08號節(jié)點的數(shù)據(jù)報文，而08號節(jié)點因為不對稱鏈路影響并不能直接接收到10號節(jié)點的數(shù)據(jù)報文。節(jié)點間的這種不對稱鏈路導致DV-Hop第1階段中計算的節(jié)點間跳數(shù)各不相同，從而使各錨節(jié)點計算的平均跳距存在較大誤差，最終影響到整個算法的定位精度。

圖1 包含不對稱鏈路的無線傳感器網(wǎng)絡(luò)示意圖

例如，13號錨節(jié)點利用式(1)計算的平均跳距為:

其中，h13，05(表示05號節(jié)點到13號節(jié)點的跳數(shù))等于8(跳數(shù)路徑為:05-06-07-02-08-10-11-14-13)，h13，19(表示19號節(jié)點到13號節(jié)點的跳數(shù))等于6(跳數(shù)路徑為:19-17-16-15-11-14-13)。

隨著DV-Hop算法執(zhí)行，08號節(jié)點計算自身到13號錨節(jié)點的跳數(shù)是5(最小跳數(shù)路徑為:13-14-11-10-09-08)。因此，當08號節(jié)點接收到Hop-Size13，它計算得到自己距離13號錨節(jié)點的距離是5 ×HopSize13。然而，HopSize13是基于h13，05計算得到，根據(jù)h13，05可知08號節(jié)點到13號錨節(jié)點的跳數(shù)應該是4;也就是說，如果使用HopSize13作為校正值，08號節(jié)點到13號錨節(jié)點的距離應該是4×Hop-Size13;相同的情況在計算15號節(jié)點到19號錨節(jié)點和05號錨節(jié)點時也會出現(xiàn)，從而導致最終的三邊定位出現(xiàn)較大誤差。

由上述分析可知，若可以使得節(jié)點間的跳數(shù)計算結(jié)果與理想網(wǎng)絡(luò)(無不對稱鏈路)中相同，則必然可以減少這種不可預見誤差，提高算法實際定位精度。

3 DV-Hop算法改進

結(jié)合上述分析，本文采用以下措施改進DV-Hop算法:①使用鄰居節(jié)點挖掘措施NNM(Neighbor Nodes Mining)完成鄰居節(jié)點間的準確識別;②使用最小跳數(shù)方法MHC(The Minimum Hop-Count)計算節(jié)點間的真實跳數(shù);③采用改進的平均跳距計算方法減小測距誤差;④采用一種新的方程組求解方法完成節(jié)點初步定位;⑤最后使用一種簡單的坐標校準技術(shù)，進一步提高定位精度。

3.1 NNM方法

在無線傳感器網(wǎng)絡(luò)中，每個節(jié)點都會有一個鄰居表NT(Neighbor Table)，理論上每個節(jié)點都應該可以直接與其鄰居表中的所有節(jié)點進行通信。但是因為不對稱鏈路的存在，節(jié)點發(fā)送出的消息可能不會被鄰居表中的鄰居節(jié)點直接接收。為盡量消除不對稱鏈路對算法的影響，本文在此提出NNM方法:定義MiningMsg消息，該消息由SrcId、SrcNT、FwdId、Ttl共4個字段組成。其中SrcId表示發(fā)出信息的源節(jié)點號;SrcNT表示源節(jié)點的鄰居表;FwdId表示最近一次轉(zhuǎn)發(fā)過該信息的節(jié)點號;Ttl表示該消息的生存期。每個節(jié)點在約定時間段內(nèi)周期性發(fā)送MiningMsg消息。對于收到該消息的節(jié)點(假設(shè)其節(jié)點號為IDtest，鄰居表為NTtest)，將采用如下方法完成其鄰居節(jié)點挖掘:

以圖1所示無線傳感器網(wǎng)絡(luò)為例，節(jié)點08屬于節(jié)點10的鄰居表，而節(jié)點10并不屬于節(jié)點08的鄰居表。通過NNM方法，節(jié)點08可以接收到節(jié)點10的MiningMsg信息(傳播路徑為10-09-08)，并發(fā)現(xiàn)它屬于節(jié)點10的鄰居表，因此將節(jié)點10添加至自己的鄰居表。至此，節(jié)點08和節(jié)點10完成相互之間的準確識別。

3.2 MHC方法

雖然NNM方法能夠確保節(jié)點本身與其鄰居表中的節(jié)點互相識別為鄰居節(jié)點，但鏈路的不對稱性是實際存在的，它會影響廣播消息在網(wǎng)絡(luò)中的傳播，繼而影響到節(jié)點間真實跳數(shù)的準確計算。為此，在完成鄰居節(jié)點挖掘之后，為DV-Hop算法第1階段的錨節(jié)點廣播消息中添加Route［N］字段，即新的廣播消息組成為{ID，xi，yi，HopCount，Route［N］}。其中Route［N］字段的每個Route元素包含{FwdId; Hops}兩個變量，F(xiàn)wdId表示轉(zhuǎn)發(fā)過該消息的節(jié)點ID，Hops表示節(jié)點FwdId與最初發(fā)出該廣播消息的錨節(jié)點之間的最小跳數(shù)。

當一個節(jié)點(假設(shè)其節(jié)點號為IDtest)接收到該條廣播消息，將按照下列方法完成它與相應錨節(jié)點之間的跳數(shù)計算:①HopCount字段值加1;②在Route［N］中挑出FwdId屬于IDtest節(jié)點的鄰居表且Hops最小的Route元素;③對于步驟②中選擇的Route元素，若其Hops+1＜HopCount，則更新Hop-Count為Hops+1，然后將Route［N］中該Route元素之后的所有元素消除;④IDtest節(jié)點將HopCount作為其與錨節(jié)點之間的跳數(shù)，并將對應信息添加至該廣播消息的Route［N］尾部;⑤轉(zhuǎn)發(fā)更新后的廣播消息。

上述方法中Route［N］字段的N取值范圍推薦為2～5。在步驟④中，若Route［N］已滿，則先將各元素依次前移覆蓋，再將空出的第N個元素由當前節(jié)點更新。

仍然以圖1為例，節(jié)點08會接收到錨節(jié)點13發(fā)出的廣播消息，其中HopCount項為5(路徑為13 -14-11-10-09-08)。節(jié)點08在該消息中發(fā)現(xiàn):Route［3］.FwdId=10，Route［4］.FwdId=09均屬于其鄰居表中的節(jié)點，且Route［3］.Hops=3最小。所以，廣播消息中的HopCount項更新為3+1 =4，同時把節(jié)點09對應的元素Route［4］內(nèi)容從Route［N］中清除，并由節(jié)點15填充(即Route［4］. FwdId=08，Route［4］.Hops=4)后再次轉(zhuǎn)發(fā)。通過這種方法，節(jié)點13和節(jié)點08計算的兩者間的跳數(shù)就是相等的。

NNM和MHC方法以通信成本為代價確保了相鄰節(jié)點間的準確識別，并使的節(jié)點間計算的跳數(shù)與理想環(huán)境相同，減少了跳段距離估算時的不可預見誤差。

3.3 平均跳距修正

即使不考慮鏈路對稱性問題，采用“跳段距離代替直線距離”這種做法也使DV-Hop定位算法在隨機分布網(wǎng)絡(luò)中可能產(chǎn)生較大的測距誤差。本文在文獻［3-9］的基礎(chǔ)上對平均跳距計算進行如下改進。

3.3.1 錨節(jié)點平均跳距修正

在DV-Hop定位算法的第1階段，基于無偏估計準則，錨節(jié)點i使用它自己算出的平均跳距值HopSizei乘以相應跳數(shù)以估計其到其它各錨節(jié)點的距離時，產(chǎn)生的平均誤差如下式所示:

式中，N表示錨節(jié)點個數(shù);εij表示錨節(jié)點i、j之間使用平均跳距與跳數(shù)乘積代替實際距離所引起的誤差;(xi，yi)和(xj，yj)分別表示錨節(jié)點i和j的坐標; HopSizei表示錨節(jié)點i計算的平均跳距值;hij表示錨節(jié)點i、j之間的最小跳數(shù)。

對(3)而言，準確的HopSizei會使平均誤差達到最小。根據(jù)最小均方誤差準則，令:

3.3.2 未知節(jié)點平均跳距修正

在傳統(tǒng)DV-Hop定位算法中，未知節(jié)點僅記錄最先收到的那個錨節(jié)點的平均跳距，并以此作為未知節(jié)點自身的平均跳距來估計它到各錨節(jié)點的估計，而參考全網(wǎng)所有錨節(jié)點的平均跳距信息計算未知節(jié)點的平均跳距這種極端的計算策略會極大增加網(wǎng)絡(luò)通信成本。為了降低通信成本的同時減小平均跳距誤差，在此提出一種基于局部錨節(jié)點的加權(quán)平均策略:即未知節(jié)點利用它能接收到的錨節(jié)點平均跳距信息計算其自身平均跳距，公式如(6)所示。而這些錨節(jié)點平均跳距信息由各錨節(jié)點通過帶有較小生存期字段的分組廣播至網(wǎng)絡(luò)，控制在局部范圍內(nèi)傳播，這也正是基本DV-Hop算法中校正值的擴散方式。

式中:hui是未知節(jié)點U和錨節(jié)點i之間的最小跳數(shù); n是未知節(jié)點收到的錨節(jié)點平均跳距信息個數(shù); HopSizei表示錨節(jié)點i計算的平均跳距值。

未知節(jié)點以此平均跳距乘以相應跳數(shù)計算它到各錨節(jié)點距離。

3.4 改進的方程組求解方法

傳統(tǒng)DV-Hop算法的第3階段是利用極大似然估計法計算節(jié)點位置。為了減少測距誤差對定位算法的影響，本文采用一種改進的方程組求解方法。

假設(shè)(x，y)是未知節(jié)點u的坐標，(xi，yi)是第i (i=1，…，n)個錨節(jié)點的坐標，di是未知節(jié)點u到錨節(jié)點i的估計距離，則通過式(8)可獲得未知節(jié)點u的位置估計。

式中di是帶有一定測量誤差的估計距離。傳統(tǒng)DV-Hop算法中先對(7)兩邊平方后再去求解(x，y)，使得包含在di中的測距誤差被迅速放大。在此，為了降低估計距離di中的固有誤差影響，我們對(7)使用一種新的解法。

首先用方程組中的前n-1個方程分別和最后一個方程相減，則可得到如下方程組:

令k=x2+y2，Ai=x2i+y2i，將方程組(8)兩邊平方后化簡可得，

上式可用矩陣形式表示為QZ=H，其中

為了進一步提高定位精度，在此使用加權(quán)最小二乘方法對QZ=H求解，可得

其中，

wu，i表示參考錨節(jié)點i相對于未知節(jié)點的權(quán)重，其取值為1/hui。

3.5 節(jié)點坐標校正

由上述內(nèi)容可以看到，通過(11)可得未知節(jié)點的初步估計坐標(x，y)以及k的值。由于di存在測距誤差，所以估計坐標(x，y)通常不滿足方程組(9)的k= x2+y2。如圖2所示，如果k＜x2+y2，則對于未知節(jié)點的一個更優(yōu)的位置估計可能在B處;如果k＞x2+y2，對于未知節(jié)點的一個更優(yōu)的位置估計可能在C處。

圖2 未知節(jié)點的位置估計

所以，借助k的值可對節(jié)點坐標進行進一步校正，具體方式如下:

從(9)可知，k的表達式包含x和y。為了方便討論，使用x'和y'分別代替k中的x和y，即k= (x')2+(y')2。令未知節(jié)點U的初步估計坐標為(x″，y″)，則有x'=t×x″，y'=t×y″。其中t是參數(shù)。因x″、y″和k的值已知，所以由k=(x')2+(y')2=(t ×x″)2+(t×y″)2即可得出t的值。

最后，使用下式修正節(jié)點坐標。

對于上式，由x'=t×x″，y'=t×y″可得

例如，假設(shè)未知節(jié)點U通過式(11)計算得到其初步估計坐標為(4，3)，k為36。則由坐標校正過程可知:x″=4，y″=3;x'=4t，y'=3t。又因k=(x')2+(y')2=36，所以t=6/5。將x″，y″和t的值帶入式(14)，可得校正后的未知節(jié)點坐標估計:x=4.4，y=3.3。

4 仿真實驗及性能分析

為了驗證本文算法的性能，采用NS2進行仿真，并將其定位效果與基本DV-Hop算法［2］和同樣針對不對稱鏈路情況下的DV-Hop改進算法［10］相比較。所有節(jié)點坐標在網(wǎng)絡(luò)區(qū)域(100 m×100 m)內(nèi)隨機生成，仿真過程中會考慮錨節(jié)點密度、網(wǎng)絡(luò)規(guī)模等不同因素對定位誤差的影響。因為本文算法試圖克服復雜網(wǎng)絡(luò)環(huán)境下存在的不對稱鏈路對定位算法的影響，所以仿真實驗會通過修改測試tcl腳本參數(shù)使網(wǎng)絡(luò)中含有一定量的不對稱鏈路。實驗評價指標為平均定位誤差，其中定位誤差是定位算法輸出的估計坐標與實際坐標之間的距離與節(jié)點通信半徑之比;平均定位誤差則是實驗重復執(zhí)行50次后得到的全網(wǎng)所有未知節(jié)點的定位誤差平均值。

4.1 不同錨節(jié)點比例時的定位性能

因為錨節(jié)點的費用比普通節(jié)點高兩個數(shù)量級，所以錨節(jié)點密度將直接關(guān)系到整個網(wǎng)絡(luò)成本高低。圖3顯示了在不同錨節(jié)點密度時本文算法與其它兩種定位算法的定位性能比較(節(jié)點總數(shù)為300，節(jié)點通信距離為15 m)。

圖3 錨節(jié)點比例變化時的定位性能比較

由圖3可以看到，當節(jié)點總數(shù)保持不變，而錨節(jié)點密度逐漸增大的情況下，各算法的平均定位誤差都逐漸減小。這是因為錨節(jié)點密度增大使得網(wǎng)絡(luò)中錨節(jié)點個數(shù)增多，未知節(jié)點可以獲得更多的高精度位置參考信息，它到各錨節(jié)點的距離估計更加接近實際距離。其中本文定位算法定位效果最好，其定位誤差比基本DV-Hop算法平均減小約16%，比文獻［10］中的改進算法平均減小約12%。這主要得益于本文算法所采取的鄰居節(jié)點挖掘機制和最小跳數(shù)計算方法能有效抑制或避免不對稱鏈路的影響，而平均跳距修正、新的方程組求解方法和最后的坐標校正技術(shù)更是進一步提高了節(jié)點定位精度。從圖3還可以看到，本文算法只需較少量的錨節(jié)點即可得到一個較好的定位效果，比其它兩種算法更能有效減少錨節(jié)點需求，降低網(wǎng)絡(luò)成本。

4.2 不同節(jié)點規(guī)模時的定位性能

圖4顯示了在不同節(jié)點規(guī)模時3種算法的定位效果(錨節(jié)點比例為10%，節(jié)點通信半徑為15m)。由圖4可見，各算法的平均定位誤差均隨著節(jié)點總數(shù)的提高而逐漸降低。其中本文定位算法定位效果仍然最好，其定位誤差比基本的DV-Hop算法平均減小約15%，比文獻［10］的算法平均減小約12%。從圖4還可以看到，網(wǎng)絡(luò)越是稀疏，本文算法的定位效果越突出，比如當網(wǎng)絡(luò)中的節(jié)點總數(shù)為200時，本文算法與其它兩種算法相比，其定位誤差分別降低了16%和15%。這同樣得益于本文算法的鄰居節(jié)點挖掘機制、最小跳數(shù)計算方法及后期的改進和坐標校正?？梢?，在相同的監(jiān)測區(qū)域和錨節(jié)點比例下，本文算法對傳感器節(jié)點的需求更少，更節(jié)約網(wǎng)絡(luò)成本。

圖4 節(jié)點總數(shù)變化時的定位性能比較

4.3 不同網(wǎng)絡(luò)連通度時的定位性能

網(wǎng)絡(luò)連通度體現(xiàn)了網(wǎng)絡(luò)中單個節(jié)點通信范圍內(nèi)的平均節(jié)點數(shù)目。為降低網(wǎng)絡(luò)成本，在保證定位性能的前提下，網(wǎng)絡(luò)連通度應越小越好。圖5給出了不同網(wǎng)絡(luò)連通度時3種算法的定位效果。

圖5 網(wǎng)絡(luò)連通度變化時的定位性能比較

由圖5可見，隨著網(wǎng)絡(luò)連通度增大，各算法的平均誤差均逐漸減小。在相同的網(wǎng)絡(luò)連通度下，本文算法的定位效果最好。其定位誤差比基本DV-Hop算法平均降低約15%，比文獻［10］的改進算法平均降低約12%。定位誤差的降低再次驗證了本文鄰居節(jié)點挖掘機制、最小跳數(shù)計算方法及坐標校正等改進措施的有效性。從圖5還可以看到，只需要較小的網(wǎng)絡(luò)連通度，本文算法即可達到較好的定位效果。這進一步體現(xiàn)了本文算法在節(jié)約網(wǎng)絡(luò)成本方面的優(yōu)勢。

5 通信成本及計算時間

定位算法的通信成本通常由定位過程中傳輸?shù)南⒎纸M個數(shù)表示。與傳統(tǒng)DV-Hop算法相比，本文算法的鄰居挖掘機制和最小跳數(shù)計算方法都是以通信成本為代價換取定位精度的提升，對此，我們認為這是值得的，特別是當網(wǎng)絡(luò)環(huán)境復雜導致有大量不對稱鏈路存在時，本文算法的優(yōu)勢將更加明顯。

另外，本文算法的鄰居挖掘機制、最小跳數(shù)計算方法和后期的坐標校正將會增加節(jié)點的定位計算時間。圖6顯示了上述3種定位算法在不同網(wǎng)絡(luò)規(guī)模時的定位時間比較?？梢钥吹?，本文算法與文獻［10］所述算法需要的定位時間接近，比傳統(tǒng)DVHop算法增加了約0.12 s，對此，我們認為定位時間和上文所述通信成本的增加都是必要的，這些付出將會帶來復雜環(huán)境下算法定位精度的大幅度提升。

圖6 節(jié)點總數(shù)變化時的定位時間比較

6 結(jié)束語

節(jié)點定位是無線傳感器網(wǎng)絡(luò)的關(guān)鍵技術(shù)。現(xiàn)有

DV-Hop算法很容易受不對稱鏈路的影響而產(chǎn)生較大的定位誤差。本文為此提出一種改進算法。新算法首先使用鄰居節(jié)點挖掘措施和最小跳數(shù)計算方法確保相鄰節(jié)點的準確識別以及節(jié)點間的跳數(shù)的準確計算;接著使用改進的平均跳距計算方法減小平均跳距誤差;然后采用一種新的方程組求解方法完成節(jié)點初步定位;最后使用一種坐標校正技術(shù)進一步提高定位精度。仿真結(jié)果顯示，本文算法以適當?shù)耐ㄐ懦杀竞陀嬎汩_銷為代價，在明顯提高定位精度的同時有效降低了網(wǎng)絡(luò)成本，能適應于多種應用環(huán)境。

［1］Boukerche A，Oliveira H A B F，Nakamura E F，et al.Localization Systems for Wireless Sensor Networks［J］.IEEE Wireless Communications，2007，14(6):6-12.

［2］Niculescu D，Nath B.Ad Hoc Positioning System(APS)［C］// Proceeding of the 2001 IEEE Global Telecommunications Conf，San Antonio:IEEE Communications Society，2001:2926-2931.

［3］林金朝，陳曉冰，劉海波.基于平均跳距修正的無線傳感器網(wǎng)絡(luò)節(jié)點迭代定位算法［J］.通信學報，2009，30(10):107-113.

［4］江禹生，馮硯毫.一種新的DV-Hop定位算法［J］.傳感技術(shù)學報，2010，23(12):1815-1819.

［5］Qian Q，Shen X，Chen H.An Improved Node Localization Algorithm Based on DV-Hop for Wireless Sensor Networks［J］.Computer Science and Information Systems，2011，8(4):953-972.

［6］張震，閆連山，劉江濤，等.基于DV-hop的無線傳感器網(wǎng)絡(luò)定位算法研究［J］.傳感技術(shù)學報，2011，24(10):1469-1472.

［7］Kumar S，Lobiyal D K.An Advanced DV-Hop Localization Algorithm for Wireless Sensor Networks［J］.Wireless Personal Communications，2013，71(2):1365-1385.

［8］石為人，賈傳江，梁煥煥.一種改進的無線傳感器網(wǎng)絡(luò)DV-Hop定位算法［J］.傳感技術(shù)學報，2011，24(1):83-87.

［9］Chen X，Zhang B.Improved DV-Hop Node Localization Algorithm in Wireless Sensor Networks［J］.International Journal of Distributed Sensor Networks，2012，2012:1-7.

［10］Zhao H G，Shi H S，Zhao Y H.Range-Free Localization Algorithm in Wireless Sensor Networks with Asymmetric Links［J］.Applied Mechanics and Materials，2014，446:1591-1595.

［11］Zhao J，Govindan R，Estrin D.Computing Aggregates for Monitoring Wireless Sensor Networks［C］//Proceedings of the First IEEE International Workshop on Sensor Network Protocols and Applications，2003:139-148.

［12］Zhou G，He T，Krishnamurthy S，et al.Impact of Radio Irregularity on Wireless Sensor Networks［C］//Proceedings of the 2nd International Conference on Mobile Systems，Applications，and Services，New York: ACM，2004:125-138.

［13］Zhao J，Govindan R.Understanding Packet Delivery Performance in Dense Wireless Sensor Networks［C］//Proceedings of the 1st International Conference on Embedded Networked Sensor Systems，New York:ACM，2003:1-13.

張亞明(1980-)，男，漢族，博士生，研究方向為無線傳感器網(wǎng)絡(luò)，zhangym333@ 163.com;

史浩山(1946-)，男，漢族，西北工業(yè)大學教授、博士生導師，研究方向為無線通信、計算機通信網(wǎng)絡(luò)、無線傳感器網(wǎng)絡(luò)，shilaoshi@nwpu.edu.cn。

不對稱鏈路環(huán)境下的WSN節(jié)點定位算法*

張亞明1，史浩山1*，劉燕2，程偉1
(1.西北工業(yè)大學電子信息學院，西安710072;2.西安電子科技大學天線與微波技術(shù)重點實驗室，西安710071)

針對無需測距定位算法DV-Hop在含有不對稱鏈路的復雜環(huán)境中存在較大定位誤差的問題，從5個方面對其進行了改進:首先采用鄰居節(jié)點挖掘措施確保相鄰節(jié)點的準確識別;接著使用最小跳數(shù)方法計算未知節(jié)點到錨節(jié)點之間的真實跳數(shù);然后使用改進的平均跳距計算方法減小平均跳距誤差;其次采用一種新的方程組求解方法完成節(jié)點初步定位;最后采用一種校正技術(shù)對初步估計坐標進行校準。仿真結(jié)果表明，改進算法以適當增加通信成本和計算開銷為代價，有效避免了不對稱鏈路的影響，在明顯提高定位精度的同時降低了網(wǎng)絡(luò)成本。

無線傳感器網(wǎng)絡(luò);定位;DV-Hop算法;不對稱鏈路

TP393

A

1004－1699(2014)03－0320－07

2014-01-07修改日期:2014-03-11

C:6150P;7230

10.3969/j.issn.1004－1699.2014.03.009

項目來源:國家自然科學基金項目(61301092，61202314);陜西省自然科學基金項目(2012JQ8005)