基于加權(quán)質(zhì)心和ＤＶ－Ｈｏｐ混合算法ＷＳＮ定位方法研究

摘 要：為了提高無線傳感器網(wǎng)絡(luò)中節(jié)點定位的精確度，分析了DV-Hop（distance vector—hop，距離向量-跳段）定位算法和質(zhì)心算法的優(yōu)缺點，提出基于加權(quán)質(zhì)心和DV-Hop混合算法，并用MATLAB進(jìn)行了仿真實驗。實驗結(jié)果表明，在基準(zhǔn)節(jié)點密度相同的條件下，混合算法的定位精度比DV-Hop平均提高了20%，比質(zhì)心算法平均提高了15%。該混合算法在提高無線傳感器節(jié)點精確度上是有效的。

關(guān)鍵詞：無線傳感器網(wǎng)絡(luò); 節(jié)點定位算法; 精確度; 距離向量-跳段; 加權(quán)質(zhì)心算法; 混合算法

中圖分類號：TP393文獻(xiàn)標(biāo)志碼：A

文章編號：1001-3695(2009)06-2248-03

doi:10.3969/j.issn.1001-3695.2009.06.075

Research of location based on mixed algorithm of weightedcentroid and DV-Hop in WSN

BAI Jin-jinga， YAN Xin-pinga， ZHANG Cun-baoa， ZHOU Xin-conga， ZHOU Xian-jub

(a.Intelligent Transport System Center， b.School of Computer Science Technology， Wuhan University of Technology， Wuhan 430063， China )

Abstract:

The node positioning technology is very important in the research of wireless sensor networks， so how to improve the positioning precision is the objective. The paper analysed the advantages and disadvantages of the distance vector-hop(DV-Hop) and the centroid algorithm， then put forward an algorithm that mixed the weighted centroid and the DV-Hop.Simulated the mixed algorithm in MATLAB. The experimental results show that the accuracy of the mixed algorithm is higher 20% than the DV-Hop and 15% than the centroid in the same experiment environment.

Key words：wireless sensor networks(WSN); node positioning algorithm; accuracy; DV-Hop; weighted centroid algorithm; mixed algorithm

無線傳感器網(wǎng)絡(luò)中，節(jié)點位置信息至關(guān)重要。定位信息常用來報告事件發(fā)生地點，進(jìn)行目標(biāo)跟蹤，實時監(jiān)視目標(biāo)的行動路線、交通監(jiān)控和環(huán)境檢測等^[1]。

無線傳感器網(wǎng)絡(luò)定位算法可分為基于距離的定位和距離無關(guān)的定位。目前基于距離的定位方法有基于TOA(time of arrival，到達(dá)時間)的定位、基于TDOA(time difference of arrival，到達(dá)時間差)的定位、基于AOA(angle of arrival，到達(dá)角度)的定位和基于RSSI(received signal strength indicator，接收信號強(qiáng)度)定位等。距離無關(guān)的定位算法有質(zhì)心算法^[2]、DV-Hop算法^[3，4]、Amorphous算法^[5]、APIT算法^[6]、MDS-MAP^[7]等。其中，基于TOA的方法定位精度高，但要求節(jié)點間保持精確的時間同步，對傳感器節(jié)點的硬件和功耗要求較高；TDOA方法具有較高的精度，但對于攜帶有限能量的無線傳感器，它的成本和能耗仍然過大；AOA方法可以確定全面的位置信息，但它的硬件尺寸和功耗使得它不適合大規(guī)模無線傳感器網(wǎng)絡(luò)；RSSI技術(shù)近年來研究較多，但它在實驗環(huán)境中表現(xiàn)良好，而在現(xiàn)實環(huán)境中，諸多變化因素使得它很難用于實際應(yīng)用。在距離無關(guān)的算法中，質(zhì)心算法完全基于網(wǎng)絡(luò)的連通性，無須基準(zhǔn)節(jié)點和未知節(jié)點之間的協(xié)調(diào)，實現(xiàn)簡單；DV-Hop算法對硬件的要求低，實現(xiàn)簡單，但存在一定的誤差；Amorphous算法將節(jié)點的通信半徑作為平均每跳段距離，定位誤差較大；APIT算法在無線信號傳播模式不規(guī)則和節(jié)點隨機(jī)部署的情況下精度較高，但對網(wǎng)絡(luò)的連通性有較高的要求。

總體上，基于距離的定位機(jī)制定位需要測量節(jié)點間的實際距離或方位，精度相對較高，但對硬件要求較高，定位過程中消耗能量較大；同時，在測距過程中使用聲波、超聲波、無線電波信號易受溫度、濕度、障礙物等環(huán)境因素的影響。距離無關(guān)的定位無須測量節(jié)點間的實際距離或方位，降低了對硬件的要求，使得它適合大規(guī)模網(wǎng)絡(luò)，而且受環(huán)境的影響較小；在精度上雖然不如基于距離的定位方法，但它能夠滿足大多數(shù)的傳感器應(yīng)用要求。因此，本文使用距離無關(guān)定位算法。通過將質(zhì)心算法進(jìn)行加權(quán)處理，并與DV-Hop算法混合使用。該算法不需要額外的硬件，適合較大規(guī)模的傳感器網(wǎng)絡(luò)。與APIT算法相比，它實現(xiàn)簡單；與質(zhì)心算法相比，消除了干擾點，有更高的精確度；與DV-Hop算法相比，它降低了跳段距離代替直線距離帶來的影響。

1 DV-Hop算法和質(zhì)心算法簡介

美國Rutgers大學(xué)的Niculescu^[3]利用距離向量路由和GPS定位的原理提出了一系列分布式定位算法APS（Ad hoc positioning system），共有六種，DV-Hop是其中的一種算法^[3]。DV-Hop即距離向量—跳段，在距離向量定位機(jī)制中，未知節(jié)點首先計算與基準(zhǔn)節(jié)點的最小跳數(shù)，然后估算平均每跳的距離，用最小跳數(shù)乘平均跳數(shù)距離得到未知節(jié)點與基準(zhǔn)節(jié)點估計距離^[8]。

幾何圖形的中心稱為質(zhì)心，多邊形質(zhì)心的計算方法為計算各個頂點的坐標(biāo)平均值。在無線傳感器網(wǎng)絡(luò)中，基準(zhǔn)節(jié)點周期性地向鄰近節(jié)點廣播分組，該分組包含了基準(zhǔn)節(jié)點的標(biāo)志號和坐標(biāo)。未知節(jié)點接收到來自基準(zhǔn)節(jié)點的分組數(shù)超過設(shè)定的值m或者定時器定時結(jié)束時，利用收到的分組計算自身的坐標(biāo)。發(fā)送分組的基準(zhǔn)節(jié)點構(gòu)成了多邊形的頂點，多邊形的質(zhì)心近似為未知節(jié)點坐標(biāo)。如圖1所示，A、B、C、D、E、F、G為基準(zhǔn)節(jié)點，坐標(biāo)分別為(XA，YA)、(XB，YB)(XC，YC)(XD，YD)、(XE，YE)(XF，YF)、(XG，YG)，H為未知節(jié)點，假設(shè)其坐標(biāo)為(X，Y)，使用質(zhì)心算法計算點H的近似坐標(biāo)為

(X，Y)=[(XA+XB+XC+XD+XE+XF+XG)/7，(YA+YB+YC+YD+YE+YF+YF)/7](1)

2 加權(quán)質(zhì)心和DV-Hop混合算法

質(zhì)心算法中，網(wǎng)絡(luò)連通的情況下，算法的精度受到兩個因素的制約，即基準(zhǔn)節(jié)點的密度以及基準(zhǔn)節(jié)點分布的均勻度。在某個區(qū)域內(nèi)，基準(zhǔn)節(jié)點密度越高、分布越均勻，則質(zhì)心算法定位精度越高。DV-Hop算法使用跳段距離代替直線距離，因此未知節(jié)點與基準(zhǔn)節(jié)點之間的跳段路徑和直線路徑的擬合度越高，精度越高，而與跳段路徑之外的節(jié)點的稀密程度無關(guān)。因此，DV-Hop算法對基準(zhǔn)節(jié)點密度的要求較低。

利用質(zhì)心算法對基準(zhǔn)節(jié)點密度要求較高而DV-Hop算法對基準(zhǔn)節(jié)點密度要求較低的特性，可以使用DV-Hop算法獲得未知節(jié)點的大致位置，使用質(zhì)心算法估計未知節(jié)點的位置區(qū)域，將通過不同方法獲得的位置進(jìn)行比較并進(jìn)行處理，可以獲得未知節(jié)點更準(zhǔn)確的位置。

如果使用普通的質(zhì)心算法，根據(jù)未知節(jié)點周圍的基準(zhǔn)節(jié)點的坐標(biāo)直接計算未知節(jié)點的坐標(biāo)，會帶入基準(zhǔn)節(jié)點中的一些奇異點。如圖1所示，其中E點就是奇異點，直接使用質(zhì)心算法將不可避免地擴(kuò)大誤差。因此，有必要對奇異點進(jìn)行處理，減小奇異點對定位的影響。本文采用對未知節(jié)點周圍的基準(zhǔn)節(jié)點賦予不同的權(quán)值的方法來處理，對定位影響大的基準(zhǔn)節(jié)點賦予較大的權(quán)值，對定位影響小的基準(zhǔn)節(jié)點賦予較小的權(quán)值，這就是本文提出的加權(quán)質(zhì)心算法。

加權(quán)質(zhì)心算法需要先獲得一個質(zhì)心區(qū)域，獲得質(zhì)心區(qū)域的過程如下：根據(jù)質(zhì)心算法的步驟，在定時內(nèi)基準(zhǔn)節(jié)點發(fā)送分組完成后，未知節(jié)點將獲得附近的N個基準(zhǔn)節(jié)點的位置信息。在N個基準(zhǔn)節(jié)點中選取N-1個，分N-1次構(gòu)建N-1個N-1邊形；每構(gòu)建一個N-1邊形，就使用質(zhì)心算法計算獲得一個質(zhì)心；經(jīng)過N-1次構(gòu)建之后，獲得N-1個質(zhì)心，形成一個質(zhì)心區(qū)域。

獲得質(zhì)心區(qū)域后，需要對該區(qū)域的質(zhì)心進(jìn)行篩選。篩選的依據(jù)是上述N-1個質(zhì)心的權(quán)值的大小。質(zhì)心i(1≤i≤N-1)的權(quán)值Ki與該質(zhì)心到根據(jù)DV-Hop算法計算獲得的未知節(jié)點坐標(biāo)的距離Ri有關(guān)，計算公式如式（2）所示。其中ai為調(diào)和系數(shù)，作用是使∑n-1i=1Ki=1。

Ki=ai/R2i（2）

如圖2所示的傳感器網(wǎng)絡(luò)，A~I為基準(zhǔn)節(jié)點，其坐標(biāo)已知；P、L、T、V為未知節(jié)點，區(qū)域Q((X1，Y1)…(XN-1，YN-1))為N-1邊形的質(zhì)心區(qū)域，需要計算未知節(jié)點P的坐標(biāo)(x，y)。

首先，A~I先定時發(fā)送分組，其他基準(zhǔn)節(jié)點和未知節(jié)點都將收到分組。定時結(jié)束后，先利用DV-Hop算法來計算未知節(jié)點的大致位置。這里選用A、B、C三個基準(zhǔn)節(jié)點來計算每跳距離HopDistance，P到 A、B、C的距離分別為2×HopDistance、2×HopDistance、2×HopDistance，再利用三邊測量法和A、B、C的坐標(biāo)就可計算出P的估算位置P1。分別計算八邊形ABCDEDFGH、…、IABCDEFG的質(zhì)心，獲得質(zhì)心區(qū)域Q，利用式（2）計算獲得各質(zhì)心的權(quán)值。最后利用權(quán)值對各個質(zhì)心坐標(biāo)進(jìn)行一次加權(quán)計算獲得最終位置。

根據(jù)上述過程，假定有N個基準(zhǔn)節(jié)點，未知節(jié)點位P，給出混合算法的描述如下：

a）基準(zhǔn)節(jié)點發(fā)送分組。

b）分組發(fā)送結(jié)束，使用DV-Hop算法獲得P的近似坐標(biāo)P1(Xp1，Yp1)。

c)P構(gòu)造N-1個N-1邊形，分別計算N-1個多邊形的質(zhì)心，得Q((X1，Y1)…(XN-1，YN-1))。

d)分別計算各個質(zhì)心到P1的距離。

D1=(X1-Xp1)2+(Y1，…，Yp1)2 …

DN-1=(XN-1-Xp1)2+(YN-1，…，Yp1)2

e)根據(jù)D1…DN-1分別對各個質(zhì)心賦予權(quán)值b1…bi，bj…bN-1 。

(b1+…+bi+bj+…+bN-1=1， if Di>Djthenbi

f)x= b1X1+…+ bi Xi+ bjXj+…+ bN-1 XN-1

 y= b1Y1+…+ biYi+ bjYj+…+ bN-1YN-1

得到未知節(jié)點P更精確的坐標(biāo)（x，y）。

3 實驗

在無線傳感器網(wǎng)絡(luò)中，評價定位算法常用的指標(biāo)有定位精度、規(guī)模、能耗等指標(biāo)^[9]。在距離無關(guān)定位算法中，各算法的能耗和適用的規(guī)模指標(biāo)比較接近，最能體現(xiàn)算法優(yōu)劣的指標(biāo)是算法的精度。為了檢驗混合算法的精度指標(biāo)，在眾多仿真平臺中^[10]，本文采用MATLAB 7.0對該算法進(jìn)行仿真，并對仿真結(jié)果進(jìn)行比較分析。

本實驗分為兩類，一類為基準(zhǔn)節(jié)點數(shù)目固定，驗證未知節(jié)點數(shù)目的變化對未知節(jié)點定位精度的影響；另一類為位置節(jié)點數(shù)目固定，驗證基準(zhǔn)節(jié)點數(shù)目固定對未知節(jié)點定位精度的影響。每一類實驗分兩個步驟：a）在仿真環(huán)境中分別運行質(zhì)心算法、DV-Hop算法、混合算法的仿真程序，獲得未知節(jié)點坐標(biāo)；b)進(jìn)行多次重復(fù)實驗，并在MATLAB中統(tǒng)計分析。

在100×100m2的范圍內(nèi)隨機(jī)分布M個節(jié)點，里面設(shè)置N個基準(zhǔn)節(jié)點（N

3.1 基準(zhǔn)節(jié)點數(shù)量確定，未知節(jié)點數(shù)量變化的定位仿真

在實驗區(qū)域內(nèi)部署50個基準(zhǔn)節(jié)點，未知節(jié)點的數(shù)目從10增加到100，每次增加10個未知節(jié)點，新增的未知節(jié)點隨機(jī)分布。分別運行定位程序計算未知節(jié)點的坐標(biāo)，在相應(yīng)的未知節(jié)點數(shù)目下，重復(fù)進(jìn)行多次定位，獲得各次定位的誤差；在MATLAB中對多次定位誤差進(jìn)行統(tǒng)計，分別比較DV-Hop算法、質(zhì)心算法和混合算法的定位平均誤差；然后改變節(jié)點的通信半徑r的值，比較其他條件相同、通信半徑不同的情況下，這幾種算法的定位平均相對誤差。

實驗結(jié)果如圖3~5所示，在基準(zhǔn)節(jié)點固定的條件下，混合算法的定位精度比DV-Hop算法有了平均20%的提高，與質(zhì)心算法相比定位精度平均有15%的提高。



3.2 未知節(jié)點數(shù)目確定，基準(zhǔn)節(jié)點數(shù)量變化的定位仿真

在實驗區(qū)域內(nèi)部署400個未知節(jié)點，基準(zhǔn)節(jié)點的數(shù)目從5增加到45，每次增加5個基準(zhǔn)節(jié)點，每次新增的基準(zhǔn)節(jié)點隨機(jī)分布。在不同的基準(zhǔn)節(jié)點數(shù)目下，運行定位程序，計算未知節(jié)點的坐標(biāo)，重復(fù)進(jìn)行多次定位，獲得各次定位的誤差；對多次定位誤差進(jìn)行統(tǒng)計，比較DV-Hop算法、質(zhì)心算法和混合算法的定位平均相對誤差，然后改變節(jié)點的通信半徑r的值，比較其他條件相同、通信半徑不同的情況下，這幾種算法的定位平均誤差。

實驗結(jié)果如圖6~8所示。在未知節(jié)點數(shù)目固定的條件下，混合算法比DV-Hop算法的精度平均提高了15%，與質(zhì)心算法相比平均提高了10%。

4 結(jié)束語

本文在加權(quán)質(zhì)心算法和DV-Hop算法的基礎(chǔ)上，提出了一種改進(jìn)的混合定位算法，并使用MATLAB軟件對該算法進(jìn)行仿真實驗分析。結(jié)果表明，在基準(zhǔn)節(jié)點數(shù)目固定而未知節(jié)點數(shù)目可變的條件下，該混合算法的定位精度比DV-Hop算法平均提高了20%，比質(zhì)心算法平均提高了15% ；在未知節(jié)點數(shù)目固定而基準(zhǔn)節(jié)點數(shù)目可變的條件下，該混合算法的定位精度比DV-Hop算法平均提高了15%，比質(zhì)心算法平均提高了10%。因此，本文算法在定位精度上具有較高的性能。另外，由于本文的研究基于理想的信號傳播模型，仿真結(jié)果并不能體現(xiàn)真實場景下的定位效果，今后還要研究在真實場景中的應(yīng)用問題。

參考文獻(xiàn):

[1]SOHRABY K， MINOLI D， ZNATI T. Wireless sensor networks[M].New Jersey: Wiley， 2007.

[2]BULUSU N， HEIDEMANN J， ESTRIN D. GPS-less low cost outdoor localization for very small devices[J]. IEEE Personal Communications Magazine， 2000， 7(5): 28-34.

[3]NICULESCU D S. Forwarding and positioning problems in Ad hoc networks[M]. New Jersey: State University of New Jersey，2004:29-33.

[4]劉克中，王殊，胡富平，等. 無線傳感器網(wǎng)絡(luò)中一種改進(jìn)DV-Hop節(jié)點定位方法[J]. 信息與控制，2006，35(6):787-792 .

[5]NAGPAL R. Organizing a global coordinate system from local information on an amporphous computer[C]//Information Pressing in Sensor Networks. Berlin:Springer， 2003:333-348.

[6]HE Tian， HUANG C， BLUM B M， et al. Range-free localization schemes for large scale sensor networks[C]//Proc of the 9th Annual International Conference on Mobile Computing and Networking. New York: ACM Press， 2003:81-95.

[7]SHANG Yi， RUML W， ZHANG Ying. Localization from mere connectivity[C]//Proc of ACM International Symposium on Mobile Ad hoc Networking and Computing. New York:ACM Press，2003:201-212.

[8]孫利民，李建中，陳渝，等．無線傳感器網(wǎng)絡(luò)［M］．北京：清華大學(xué)出版社，2005.

[9]王福豹， 史龍，任豐原．無線傳感器網(wǎng)絡(luò)中的自身定位系統(tǒng)和算法[J]．軟件學(xué)報， 2005，16(5):1148-1157.

[10]操敏，李文鋒，袁兵. 基于OMNeT++的LEACH協(xié)議的仿真研究[J]. 交通與計算機(jī)，2007，25(1):125-128.