王利凱，羅 沛

(西安電子科技大學電子工程學院，陜西西安 710071)

WSN中免測距距離估計算法的實現(xiàn)與比較

王利凱，羅 沛

(西安電子科技大學電子工程學院，陜西西安 710071)

在無線傳感器網絡中，節(jié)點定位技術是保證其他應用有效的基本功能，而定位過程可分為距離估計和位置計算兩個階段。文中就距離估計階段介紹了Sum－Dist、DV－Hop以及Euclidean算法，并在Matlab中仿真實現(xiàn)，最后分析比較其結果表明，各算法在響應的環(huán)境中具有良好的表現(xiàn)，和一定的提升空間。

無線傳感器網絡;距離估計;Sum－Dist;DV－Hop;Euclidean

無線傳感器網絡(Wireless Sensor Networks，WSN)的出現(xiàn)對于許多應用領域都具有重要意義，因此，其吸引了越來越多的研究者［1］。近年來，微電子、無線通信和計算等技術的進步推動了傳感器的快速發(fā)展，使得已經在體積和短距離通信方面有優(yōu)勢的傳感器又向低成本、低功耗和多功能方面發(fā)展并逐漸成熟，并引起國際學術界和工業(yè)界的重視，被認為是對21世紀產生巨大影響力的技術之一［2－7］。

無線傳感器節(jié)點在部署時往往是不可控制的，如在大型無線傳感器網絡中，節(jié)點通常被撒播在廣泛的區(qū)域之中，而其中大部分節(jié)點的位置不能事先確定。然而，無線傳感器網絡中，節(jié)點的位置信息對傳感器網絡的監(jiān)測活動尤為重要，沒有位置信息的監(jiān)測消息是毫無意義的［8］。對于一些突發(fā)事件，事件監(jiān)測到之后所關心的一個重要問題就是事件發(fā)生的位置信息。如需要告知火災的發(fā)生地點、戰(zhàn)場上車輛運動的區(qū)域、天然氣管道泄漏的具體地點等;又如在環(huán)境監(jiān)測應用中，需要獲取采集信息所對應的物理位置。

因此，節(jié)點的定位問題已成為無線傳感器網絡的一個重要研究方向。傳感器節(jié)點的自身定位是一種通過估計距鄰居節(jié)點的距離或鄰居數(shù)目，并利用節(jié)點間的信息交換來確定各節(jié)點自身位置的機制。無線傳感器網絡中，根據(jù)定位過程中是否實際測量節(jié)點間的距離，把定位機制分為:基于測距的(Range－based)定位和距離無關的(Range－free)定位方法。

由于無線傳感網絡不同于傳統(tǒng)網絡，其能源有限，節(jié)點的通信能力、計算能力相對較弱，而節(jié)點數(shù)量較多，導致其定位算法必須考慮能源有效性、生命周期、通信延遲、感知精度、可擴展性、魯棒性等指標。而Range－free算法則僅利用節(jié)點間距離的關聯(lián)關系來計算目標節(jié)點位置。定位精度較Range－based算法稍差，但由于其降低了對節(jié)點硬件的要求，相對更適于無線傳感器網絡中的定位。典型算法有:DV－Hop、Sum－Dist、Euclidean等。這些定位算法都需要經過如圖1所示的定位過程:

1 免測距距離估計算法

1.1 Sum－Dist算法

Sum－Dist［9］算法是距離估計算法中較簡單的方法，其主要思想是將網絡泛洪過程中的每跳距離相加，以此作為兩個節(jié)點間的距離。從錨節(jié)點開始，該錨節(jié)點會廣播一條包含自身標志、位置信息、并將路徑長度置為0的消息。每個接收該消息的節(jié)點都會將測量距離加到路徑長度上，并在泛洪限制許可的情況下，將該消息再次在網絡中廣播。如果關于同一個錨節(jié)點的消息兩次或多次廣播至未知節(jié)點，即僅在當前路徑長度小于以前路徑長度時，才允許繼續(xù)廣播。這樣，最終結果就是每個節(jié)點都儲存了每個錨節(jié)點的位置以及到達該錨節(jié)點跳數(shù)最少的距離。

圖1 節(jié)點定位過程

圖2是一個簡單的Sum－Dist算法模型，節(jié)點A到錨節(jié)點1只有一條路徑，且僅有一跳，距離為5;到錨節(jié)點2也只有一條路徑，距離為5+6+6=17;到錨節(jié)點3有兩條路徑:A－D－3以及A－D－E－3，需選擇跳數(shù)最少的路徑，即A－D－3，距離為7+7=14。

圖2 Sum－Dist算法模型

1.2 DV－Hop算法

DV－Hop［10］定位算法測距過程分為兩個階段:

第一階段 首先計算待定位節(jié)點與錨節(jié)點的最小跳數(shù)。為獲得節(jié)點間的跳數(shù)，錨節(jié)點向所有鄰居節(jié)點廣播一個包含其自身標志、位置信息、跳數(shù)被置為0的消息。當未知節(jié)點接收到該消息時，將跳數(shù)加1，并在泛洪限制許可的情況下，將消息繼續(xù)向它的鄰居節(jié)點轉發(fā)，此過程一直持續(xù)下去，直至網絡中每個節(jié)點都獲得每個錨節(jié)點的位置信息和相應的跳數(shù)值。為了保證能得到最小跳數(shù)，未知節(jié)點收到消息時，會查看是否已經收到過關于該錨節(jié)點的消息，若已經存在，則比較當前跳數(shù)是否比之前收到的小，若不是則丟棄該消息，這樣就能保證得到的跳數(shù)最小跳數(shù)。

第二階段 計算未知節(jié)點與錨節(jié)點的實際跳距。每個錨節(jié)點根據(jù)第一階段中得到的其它錨節(jié)點的位置信息和相距跳數(shù)，利用式(1)估算平均跳距

DV－Hop算法能夠計算出離錨節(jié)點很遠未知節(jié)點的位置。而且其不需要額外信息，但是其誤差與其路徑的彎曲程度成正比。由于一個未知節(jié)點只能通過一條路徑得到跳數(shù)，所以它需要通過每跳平均距離來計算自身的位置，這樣導致計算出位置的誤差量大。假設一個DV－Hop模型如圖3所示。

圖3 DV－Hop算法模型

其中，A1，A2，A3是錨節(jié)點;A 是一個未知節(jié)點，A1，A2，A3之間的距離已知，分別為30，30和40。A點到A1點為8，跳數(shù)為1;根據(jù)最小跳數(shù)原則，A點到A2，A3的跳數(shù)分別為3和2。

首先，錨節(jié)點廣播包括位置信息、自身標志及開始跳數(shù)為0的消息，當消息廣播至另一個節(jié)點，跳數(shù)根據(jù)最小跳數(shù)的原則變化，最終，每個節(jié)點都可得到離錨節(jié)點的最小跳數(shù)，而錨節(jié)點得到與其他錨節(jié)點的最小跳數(shù)后便可以計算平均跳距。在圖3中，A1、A2、A3的平均跳距如下

在計算出平均跳距后，錨節(jié)點將在網絡中廣播該信息，未知節(jié)點將平均跳距與最小跳數(shù)的乘積作為與錨節(jié)點的間距。即，A1、A2、A3將廣播 8.6、7.8、7.8 的3個平均跳距。如，A收到A1、A2、A3這3點廣播的跳距后，即能計算A到各錨節(jié)點的距離AA1=8.6;AA2=7.8×3=23.4;AA3=7.8×2=15.6。

1.3 Euclidean算法

如果網絡的拓撲結構不規(guī)則，DV－Hop算法的測距誤差會較大。針對這些問題，Niculescu和Nath提出了另一種方法，即為Euclidean［11］。該方法依靠錨節(jié)點周圍節(jié)點的幾何關系進行計算，若一個節(jié)點的兩個鄰居節(jié)點已知各自到錨節(jié)點的距離等于彼此之間的距離，這時，即可計算該節(jié)點到錨節(jié)點的距離了。

如圖4是一個Euclidean算法的模型。

圖4 Euclidean算法模型

在圖4中，A有兩個鄰節(jié)點B、C，已知B、C與錨節(jié)點ANC的距離分別是a和b，結合已知的節(jié)點間距c、d、e，Euclidean算法得到兩個解:r1和r2。為確定哪個解為正解，可采用鄰居節(jié)點投票的方法:若存在第3個鄰居節(jié)點D，與B或C相連，且已知它到錨節(jié)點的距離。這時，可用D替換C或B，再重新計算A的位置，得到另一對解，正解必然在這兩對解中，如此，用簡單的選擇法便可得到正解。當然，若是有更多的鄰居節(jié)點參與計算，最終結果會更精確。

2 仿真實現(xiàn)與結果分析

默認環(huán)境如下:在100個單位的正方形場景中，有300個節(jié)點，通信距離設為15，錨節(jié)點比例設為5%，通信誤差是通信距離的10%，以下從不同參數(shù)進行仿真比較。

圖5 不同通信誤差下各算法的測距方差

圖5是不同通信誤差下，DV－Hop、Sum－Dist、Euclidean算法執(zhí)行距離估計得到的標準方差，圖6和圖7則分別是在不同的通信距離、錨節(jié)點比例下所得到的方差。(1)Sum－Dist是3種方法中通信量最少、計算量最小的測距算法。但在通信誤差＜10%時，其測距結果仍是理想的。實際上，有兩個完全不同的趨勢影響著Sum－Dist的測距精度。其一，如果完全沒有通信誤差，多條路徑上的距離總和大于實際距離，這樣就導致估計值過大;其二，由于Sum－Dist算法尋找的是最短路徑，所以當存在通信誤差時，其所選的路徑就會比實際距離小。因為有這兩個影響，通信距離的小誤差反而提高了Sum－Dist的測距精度。最初，由于路徑存在彎曲，導致距離估計值過大，但在最短路徑的影響下，通信距離誤差的增大反而使距離估計值更小。

當通信距離增大時，更多的節(jié)點可以直接通信，這樣就可以得到更多的直線路徑，并為最短路徑提供了更多選擇。所以，對于Sum－Dist算法來說，提高測距精度并不一定要增加錨節(jié)點比例。

(2)DV－Hop算法是相對較穩(wěn)定、可預測的算法，由于并不需要實際測量距離，所以它對誤差源并不敏感。DV－Hop算法的路徑是跳數(shù)最少的路徑，所以其平均跳距接近通信距離。然而，從錨節(jié)點到未知節(jié)點路徑上的最后一跳往往比通信距離短，這也會導致對錨節(jié)點和未知節(jié)點間距的少許高估。在短路徑的情況下，高估的情況更為明顯，正因如此，通信距離越大，錨節(jié)點比例越高，跳數(shù)越少，而其測距誤差反而越大。

(3)Euclidean算法在精確測量錨節(jié)點和未知節(jié)點距離方面明顯有效，但僅在沒有通信距離誤差和高連通的網絡中。而這些條件一旦放松，Euclidean算法的性能會急速下降。Euclidean算法在一般情況下對距離的估計均過低，這是由于在選擇時，被迫在兩個相隔較遠的位置間選擇。而大部分情況下，最短距離是不正確的。圖4所示，較短距離r2落在錨節(jié)點的通信范圍內。如果r2是正確距離，那么該未知節(jié)點應該能夠與錨節(jié)點直接通信，避免選擇的需要。未知節(jié)點距錨節(jié)點有多跳距離時也同樣存在上述情況。因此，在通信距離誤差較小的情況下，相對于高估距離，未知節(jié)點更可能會低估其與錨節(jié)點的距離。

如圖7所示，Euclidean算法對于錨節(jié)點比例并不敏感?？s小通信距離的主要影響是Euclidean算法無法廣播其錨節(jié)點間距。在之前描述Euclidean算法的選擇方法中，需要至少3個已經與錨節(jié)點之間僅有一跳，且已經得到距離估計值的鄰居節(jié)點。在低連通的網絡中，僅有少量鏈路連接的兩部分往往共享一些錨節(jié)點，這也導致在定位階段只能計算更少的一些節(jié)點位置。

3 結束語

文中實現(xiàn)無線傳感器網絡中3種免測距距離估計算法:Sum－Dist、DV－Hop和 Euclidean，在無線傳感器網絡中，由于節(jié)點的通信距離有限，為能夠與更遠的節(jié)點進行通信，節(jié)點間采用多跳的方式進行數(shù)據(jù)傳遞，這種方式提高了整個網絡的通信能力，也為免測距算法帶來了執(zhí)行的可能性，實驗結果表明，免測距算法更適合應用于能源攜帶有限、通信能力弱、計算能力弱的無線傳感器網絡網絡中。

［1］MAO G，F(xiàn)IDAN B，ANDERSON B.Wireless sensor network localization techniques ［J］.Computer Networks，2007，51(10):2529－2553.

［2］AKYILDIZ I，SU W，SANKARA Y，et al.A survey on sensor networks ［J］.IEEE Communications Magazine，2002，40(8):102－114.

［3］TILAK S，ABU G N B，HEINZELMAN W.A taxonomy of wireless micro － sensor network models［J］.Mobile Computing and Communications Review，2002，6(2):1 －8.

［4］CULLAR D，ESTRIN D，STRVASTAVA M.Overview of sensor network［J］.Computer，2004，37(8):41 －49.

［5］王福豹，史龍，任豐原.無線傳感器網絡中的自身定位系統(tǒng)和算法［J］.軟件學報，2005，16(5):857 －868.

［6］李建中，高宏.無線傳感器網絡的研究進展［J］.計算機研究與發(fā)展，2008，45(1):1 －15.

［7］孫利民，李建中，陳渝，等.無線傳感器網絡［M］.北京:清華大學出版社，2005.

［8］ASIS N，LI K.A directionality based location discovery scheme for wireless sensor networks［C］.Shoul:WSNA'02，2002:105－111.

［9］SAVARESE C，LANGENDOEN K，RABAEY J.Robust positioning algorithms for distributed ad－h(huán)oc wireless sensor networks［C］.Monterey，CA:USENIX Technical Annual Conference，2002:317 －328.

［10］SAVVIDES A，PARK H，SRIVASTAVA M.The bits and flops of the N－h(huán)op multilateration primitive for node localization problems［C］.Atlanta，GA:First ACM International Workshop on Wireless Sensor Networks and Application(WSNA)，2002:112 －121.

［11］NICULESCU D，NATH B.Ad － hoc positioning system(APS)using AoA.［C］.In GlobeCom IEEE Computer and Communications Scotland，2001.

Implementation and Comparison of the Range-free Localization Algorithm in Wireless Networks

WANG Likai，LUO Pei
(School of Electronic Engineering，Xidian University，Xi'an 710071，China)

In the WSN，the node location technology is a basic function to guarantee the effectiveness of other application，and the positioning process can be divided into two stages:distance estimation and position calculation.This paper introduces three algorithms of distance estimation:Sum-Dist，DV-Hop，and Euclidean，and simulates them in Matlab.The result shows that in the response of the environment all the algorithms perform well and can be further improved.

wireless sensor network;distance estimation;sum-dist;DV-Hop;euclidean

TN92

A

1007－7820(2012)06－056－04

2012-01-03

中央高?；究蒲袠I(yè)務費專項資金資助項目(K50510020034)

王利凱(1988—)，男，碩士研究生。研究方向:無線傳感器網絡。羅沛(1987—)，女，碩士研究生。研究方向:計算機網絡。