無線傳感器網絡中Dv－hop算法的研究及改進

王麗俠

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

1 Dv－hop算法簡介

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

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

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

2 對Dv－hop的分析和問題的提出

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

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

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

3 逐級分區和加權定位算法

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

3.1 參考節點信標的逐級分區洪泛

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

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

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

分區算法分為4個步驟：

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

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

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

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

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

3.2 基于權重的校正值計算和傳播

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

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

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

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

3.3 參考節點的選取

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

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

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

4.1 定位精度

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

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

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

4.2 通信量

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

圖3 不同參考節點比例下的通信量

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

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

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

圖4 不同節點總數下的通信量（15%Anchor）

圖5 “C”形網絡的定位精度

5 仿真總結

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

［1］ 張品，孫巖．一種新的無線傳感器網絡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］ 石為人，賈傳江，梁煥煥．一種改進的無線傳感器網絡DV－Hop定位算法［J］．傳感技術學報，2011，24（1）：83－87．

［4］ 戴瑩，王建平，張崇巍．無線傳感器網絡節點定位算法的研 究 與 改 進 ［J］．傳 感 技 術 學 報，2010，23（4）：567－570．

［5］ 衛開夏，田金鵬，王克謙．無線傳感器網絡DV－Hop定位 改 進 算 法 ［J］．傳 感 技 術 學 報，2010，23（12）：1820－1824．