無線傳感器網(wǎng)絡(luò)中Dv－h(huán)op算法的研究及改進

王麗俠

（唐山學院 信息工程系，河北 唐山063000）

1 Dv－h(huán)op算法簡介

傳感器網(wǎng)絡(luò)中的數(shù)據(jù)采用多跳路由的方式傳送，每一個節(jié)點只與其鄰居進行通信，通過這種方式，有限的參考節(jié)點能夠被更多的未知節(jié)點利用，從而降低對參考節(jié)點的依賴。Dv－h(huán)op利用了距離矢量原理，屬于無需測距的分布式定位算法［1］。

在Dv－h(huán)op算法中，要實現(xiàn)最后的定位計算，每個未知節(jié)點需要先獲得兩個基本信息：①不少于3個參考節(jié)點的坐標；②到這些參考節(jié)點的距離。Dv－h(huán)op算法會將未知節(jié)點到參考節(jié)點之間的距離用網(wǎng)絡(luò)平均每跳距離和兩者之間最短路徑的跳數(shù)乘積表示，因此實際用于度量距離和參與計算的最重要的值就是跳數(shù)。在原始的Dv－h(huán)op算法中，除了孤島節(jié)點外（連通度為0的節(jié)點），其余節(jié)點幾乎都能夠獲得網(wǎng)絡(luò)中每一個參考節(jié)點的信息。利用這大量的冗余信息，絕大部分節(jié)點都能實現(xiàn)有效的定位，這也是Dv－h(huán)op與其他算法相比的最大優(yōu)勢。

Dv－h(huán)op算法運行過程如文獻［2］中所述：首先，參考節(jié)點通過距離矢量協(xié)議，向網(wǎng)絡(luò)中廣播其坐標和跳數(shù)信息；然后，參考節(jié)點估計出所有節(jié)點間單跳的平均距離，任何一個參考節(jié)點均可向整個網(wǎng)絡(luò)廣播此距離，將其作為整個網(wǎng)絡(luò)的修正值；最后，未知節(jié)點就可以利用事先獲得的參考節(jié)點的坐標和修正值，通過三邊計算等方式完成自身的定位工作。

2 對Dv－h(huán)op的分析和問題的提出

Dv－h(huán)op是目前最典型的多跳定位機制，它充分利用了有限的參考節(jié)點信息，避免了測距誤差的引入，簡單可行，具有很高的實用性，但是相應(yīng)的，該算法也有不少亟待改進的地方（如文獻［3］中所述）。筆者從參考節(jié)點對精度的影響以及通信量兩個方面，對Dv－h(huán)op算法的缺陷進行分析。該算法具體存在以下兩個問題。

（1）在計算校正值的階段，距離過遠的參考節(jié)點和較近的參考節(jié)點所帶來的誤差影響是有所不同的，尤其是在具有一定各向異性特點的拓撲中尤為明顯，而Dv－h(huán)op對全網(wǎng)的所有參考節(jié)點都配以相同的權(quán)重，這往往會使得到的校值偏小，從而影響最后的坐標計算。

（2）原算法中采用了全網(wǎng)洪泛的方式來確保每個節(jié)點都能收到所有參考節(jié)點的信標，這樣雖然可以使未知節(jié)點獲得足夠多的參考節(jié)點信息，但是不受控洪泛的方式對傳感器網(wǎng)絡(luò)來說代價過于昂貴，對于參考節(jié)點數(shù)接近1 000的大規(guī)模網(wǎng)絡(luò)，通信過程會帶來巨大的能耗，使用Dv－h(huán)op算法不可行，這也將這種算法的應(yīng)用范圍限制在了中小型的網(wǎng)絡(luò)。如何在保證未知節(jié)點能獲得足夠的參考節(jié)點信息的前提下降低通信量成了改進這種定位算法的最關(guān)鍵問題。

3 逐級分區(qū)和加權(quán)定位算法

下面將針對Dv－h(huán)op算法存在的兩個問題，提出一種新的定位算法，引入逐級分區(qū)概念和加權(quán)計算，與文獻［4］思路類似，首先通過對網(wǎng)絡(luò)中的所有參考節(jié)點進行分級，按逐漸縮小本地范圍的方式進行信標洪泛，以達到既能使節(jié)點獲得足夠參考節(jié)點信標，又能極大降低網(wǎng)絡(luò)通信量的目的；其次在校正值的計算和傳播階段，通過對不同參考節(jié)點加權(quán)并合理選擇參考節(jié)點進行坐標計算，來減小最終的定位誤差。

3.1 參考節(jié)點信標的逐級分區(qū)洪泛

逐級分區(qū)主要是對參考節(jié)點進行分級，并通過各級分別洪泛來限制洪泛的范圍，因此，改進后的算法可適用于大規(guī)模的傳感器網(wǎng)絡(luò)。算法開始運行之前，所有參考節(jié)點b和未知節(jié)點u隨機分布，參考節(jié)點事先劃分為幾個級別，劃分的值與參考節(jié)點的ID沒有關(guān)聯(lián)，采取隨機劃分或指定。

算法的實現(xiàn)采用一個通用的信息包結(jié)構(gòu)：UNI＿MESSAGE，在所有節(jié)點通信中都發(fā)送這樣的數(shù)據(jù)包，包含發(fā)送節(jié)點的ID號、級別、坐標、校正值（hopsize）和跳數(shù)；消息以結(jié)構(gòu)體實現(xiàn)，以omnet的消息類進行封裝，字段定義如圖1所示。

圖1 消息體UNI＿MESSAGE字段定義

分區(qū)算法分為4個步驟：

（1）首先，第一級的節(jié)點向鄰居廣播自己的信標。和在Dv－h(huán)op算法中一樣，這個過程通過距離矢量的方式進行洪泛，所有節(jié)點記錄下收到的信標中的坐標位置、ID號、Hops字段值，然后將Hops加1轉(zhuǎn)發(fā)給自己的鄰居節(jié)點。

（2）收到了第一級參考節(jié)點的信標后，未知節(jié)點記錄下數(shù)據(jù)包中的ID號和坐標；同時，收到信標的每一個節(jié)點包括其他參考節(jié)點，都計算出一個自己所屬的區(qū)域，這個區(qū)域的序號即是它所收到的信標中跳數(shù)值（Hops字段）最小的那個參考節(jié)點的ID號，如果有兩個或兩個以上信標中的跳數(shù)值相同，則取最先收到的一個。這樣形成的結(jié)果就是，第一級的參考節(jié)點在它的附近一定范圍內(nèi)，劃分出了一個以自己的ID號為序號的“虛擬”本地區(qū)域，這幾個區(qū)域也是對全局的一個完整劃分。

（3）從第二級的參考節(jié)點開始，均設(shè)置計時器，以收到上一級的信標起開始計時，當計時器溢出后，即認為上級節(jié)點的洪泛已經(jīng)結(jié)束，然后開始自己的洪泛。第二級開始的參考節(jié)點在發(fā)送信標前，先根據(jù)前面收到的所有參考節(jié)點的信息（坐標值、跳數(shù)）計算校正值（與原算法不同，新校正值的計算方式在3.2節(jié)闡述），然后將計算出的校正值置入 UNI＿MESSAGE的hopsize字段，以“捎帶”的方式與它的信標一起發(fā)送出去。與前一級參考節(jié)點不同，后一級參考節(jié)點信標的洪泛范圍將被限制在它當時所處的區(qū)域內(nèi)部，這也是算法能保證通信量大幅降低的關(guān)鍵。

對于來自同一區(qū)域的信標，判斷是否需要更新自己當前所處區(qū)域的依據(jù)是：如果當前保存的Region＿hop值大于新參考節(jié)點到自己的跳數(shù)，就執(zhí)行更新，然后將Region更新為新收到的參考節(jié)點ID。這樣，新的參考節(jié)點就在它原來所屬區(qū)域里面劃分出了一個子區(qū)域。這個過程重復(fù)執(zhí)行，直到各級的洪泛全部完成。最后的結(jié)果是，如果網(wǎng)絡(luò)中分布了n個參考節(jié)點，網(wǎng)絡(luò)將被劃分為n個子區(qū)域，每個區(qū)域逐漸縮小，并且以一個相應(yīng)的參考節(jié)點為中心。

（4）洪泛全部結(jié)束后，參考節(jié)點已經(jīng)將信標和校正值廣播到了網(wǎng)絡(luò)中，未知節(jié)點在一段時間沒有收到信標后，計時溢出，并開始坐標計算：首先將收到的校正值進行計算，得到最終的校正值，并選取參考節(jié)點，通過公式dn≈hopsizen×Hn將跳數(shù)距離轉(zhuǎn)換為估計距離，然后采用三邊計算或最大似然估計法求得坐標值。

3.2 基于權(quán)重的校正值計算和傳播

在校正值的計算過程中應(yīng)該考慮到參考節(jié)點的距離遠近問題，對于過遠的節(jié)點，在校正值的計算中要進行修正，配以較小的權(quán)重加以限制，使跳距過遠的參考節(jié)點對校正值的影響迅速減小。

在3.1節(jié)分區(qū)算法步驟（3）中所述，從第二級的參考節(jié)點開始計算校正值，并且以“捎帶”的方式將校正值隨信標一起發(fā)送。假設(shè)第i個參考節(jié)點計時溢出后（Time＿up函數(shù)返回true）在其參考節(jié)點鏈表anchor＿list中有j個上級節(jié)點的信標，相應(yīng)的跳數(shù)值分別為 Hij，相應(yīng)坐標表示為（Xj，Yj），校正值hopsizei的計算公式為：

Hin為參考節(jié)點n到i的跳數(shù)。通過這種改進的校正值計算方式，可以提供更符合實際的校正值，從而提高最終的節(jié)點定位精度。

在新算法中，參考節(jié)點的信標和校正值是放在同一個數(shù)據(jù)包UNI＿MESSAGE里一起洪泛到網(wǎng)絡(luò)中的，所以不存在第二次通信開銷的問題，另外，當未知節(jié)點收到第一個校正值時，發(fā)出這個值的參考節(jié)點必然與它處于同一個子區(qū)域內(nèi)（即一級節(jié)點劃分的區(qū)域），后續(xù)節(jié)點也是如此，而且會逐漸靠近收到該值的未知節(jié)點，所以此算法可以確保校正值均來自未知節(jié)點附近。在本算法中，未知節(jié)點會接收到多個來自附近的校正值，最后通過取平均的方式進行處理，以充分利用這些冗余信息：hopsize＝，hopsize即未知節(jié)點用來估算到參考節(jié)點距離的校正值，n為節(jié)點最終收到的校正值數(shù)目。通過將校正值取平均，避免了因某個參考節(jié)點的值出現(xiàn)嚴重失真帶來的影響。

3.3 參考節(jié)點的選取

新算法中，在坐標值計算方面，采取不同的策略：洪泛完成之后，節(jié)點首先在一級參考節(jié)點當中排除自己所屬區(qū)域以外的其他幾個節(jié)點，利用所有剩下的節(jié)點信標計算其坐標值；如果剩下的信標總數(shù)小于等于3，再在排除的參考節(jié)點中依照跳數(shù)值，按從小到大的順序選擇其他參考節(jié)點，直到信標數(shù)大于3為止。這樣做可以保證定位計算只基于本地網(wǎng)絡(luò)拓撲，目的同樣是避免網(wǎng)絡(luò)的非均勻性對坐標計算帶來的影響，而且一級節(jié)點數(shù)目越多，用于坐標計算的參考節(jié)點離得越近，網(wǎng)絡(luò)的不均勻性帶來的影響也就越小。

4 定位算法的仿真驗證與分析

分區(qū)加權(quán)算法主要針對定位精度和通信開銷問題進行了改進。下面在OMNet＋＋和Matlab組成的環(huán)境下，對算法的相對定位誤差、通信量，以及在各向異性拓撲下的性能進行對比仿真。

4.1 定位精度

為了檢驗算法的定位精度，采用隨機分布的網(wǎng)絡(luò)拓撲進行仿真，參考節(jié)點的分級均采用3.1中的劃分方式，一級節(jié)點都為4個。下面各圖中每一個數(shù)據(jù)點是在相同參數(shù)下5次仿真的平均值。

圖2為Dv－h(huán)op算法和改進算法的定位誤差曲線，參考節(jié)點的比例從5%到30%。從圖中可以看到，在參考節(jié)點僅為5%時，改進算法的定位精度不如Dv－h(huán)op算法，平均相對誤差達到了140%以上；參考節(jié)點多于10%時，改進算法的誤差明顯小于Dv－h(huán)op算法，且相對誤差隨參考節(jié)點增加而下降的趨勢略快于Dv－h(huán)op算法；在參考節(jié)點取15%時，其誤差平均值為47．9%。圖2表明，根據(jù)參考節(jié)點的跳數(shù)遠近決定其權(quán)重的大小來計算校正值的方式，明顯改善了節(jié)點定位的精度。

圖2 不同參考節(jié)點比例下的定位精度比較

4.2 通信量

對分區(qū)加權(quán)算法通信開銷的仿真分兩步，首先要驗證通信量與參考節(jié)點的關(guān)系。圖3中上面為Dv－h(huán)op的通信量曲線，虛線為其理論值；下面為分區(qū)加權(quán)算法通信量，虛線是其理論值。由仿真可見，Dv－h(huán)op中總節(jié)點數(shù)不變，參考節(jié)點從5%到30%變化時，通信量呈線性增加，增幅較大。

圖3 不同參考節(jié)點比例下的通信量

圖4為不同節(jié)點總數(shù)時的通信量曲線，參考節(jié)點比例固定為15%，節(jié)點每增加100，分布區(qū)域相應(yīng)增加100，其他參數(shù)與前面相同，仿真次數(shù)均為1次。對于Dv－h(huán)op算法，其理論通信量計算為pn2＋n，p為參考節(jié)點比例。從仿真結(jié)果可以看到，其實際的通信量基本呈指數(shù)級增加；而分區(qū)加權(quán)算法中，通信量與理論值相近，呈對數(shù)特性，增加非常緩慢，在網(wǎng)絡(luò)達到1 000個節(jié)點時，發(fā)送包數(shù)仍然小于10 000，而Dvhop算法的相應(yīng)值卻是它的14倍。

4.3 各向異性拓撲下的對比仿真

由于分區(qū)加權(quán)方式的采用，算法對網(wǎng)絡(luò)拓撲的依賴性比Dv－h(huán)op算法要小?，F(xiàn)對一個“C”形的網(wǎng)絡(luò)進行仿真，其代表了各向異性網(wǎng)絡(luò)拓撲。圖5為對網(wǎng)絡(luò)取不同的參考節(jié)點比例時，分別運行Dv－h(huán)op算法和分區(qū)加權(quán)算法得到的定位精度曲線圖。最上面為Dv－h(huán)op算法的誤差曲線，其相對誤差都在110%以上，平均誤差值為138．6%，并且沒有隨參考節(jié)點增加而降低?？梢奃v－h(huán)op算法的確僅適用于各向同性網(wǎng)絡(luò)拓撲［5］，在“C”形網(wǎng)絡(luò)結(jié)構(gòu)中，拓撲呈明顯的各向異性，“空洞”效應(yīng)在這里非常明顯。中間的曲線為分區(qū)加權(quán)算法，一級節(jié)點數(shù)目為4時的結(jié)果，在所有參考節(jié)點比例下，定位精度都有明顯的提高。最下邊一條曲線為一級節(jié)點數(shù)目為6時的結(jié)果，即按照6，6，12，24…的方式劃分，可以看到，在這種情況下，當參考節(jié)點比例增加到20%時，定位精度有非常明顯的提高，其相對誤差降低到了53．2%，與Dv－h(huán)op算法在各向同性網(wǎng)絡(luò)中的性能相近。但圖中曲線也同時表明，要在這種完全各向異性的拓撲中取得較高的定位精度，需要更高的參考節(jié)點比例。

圖4 不同節(jié)點總數(shù)下的通信量（15%Anchor）

圖5 “C”形網(wǎng)絡(luò)的定位精度

5 仿真總結(jié)

以上的仿真實驗表明，在節(jié)點隨機分布的網(wǎng)絡(luò)中，分區(qū)加權(quán)算法的定位精度優(yōu)于Dv－h(huán)op算法，更關(guān)鍵的是，它極大地降低了定位過程中的通信開銷，因此從這個方面講，它能夠應(yīng)用于節(jié)點數(shù)目較多的大規(guī)模傳感器網(wǎng)絡(luò)，是對Dv－h(huán)op算法的有效擴展。另外，在各向異性網(wǎng)絡(luò)中，分區(qū)加權(quán)算法的定位精度與Dv－h(huán)op算法相比有非常明顯的提高，在仿真中采用的“C”形網(wǎng)絡(luò)，當參考節(jié)點數(shù)目達到20%以上時，其定位相對誤差降低到了53．2%。

［1］ 張品，孫巖．一種新的無線傳感器網(wǎng)絡(luò)DV－Hop算法［J］．電子器件，2010，33（1）：117－120．

［2］ Niculescu D，Nath B．DV based positioning in Ad Hoc networks［J］．Telecommunication Systems，2003，22（1－4）：267－280．

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

［4］ 戴瑩，王建平，張崇?。疅o線傳感器網(wǎng)絡(luò)節(jié)點定位算法的研 究 與 改 進 ［J］．傳 感 技 術(shù) 學 報，2010，23（4）：567－570．

［5］ 衛(wèi)開夏，田金鵬，王克謙．無線傳感器網(wǎng)絡(luò)DV－Hop定位 改 進 算 法 ［J］．傳 感 技 術(shù) 學 報，2010，23（12）：1820－1824．