WSN中抵御蟲洞攻擊的改進的DV-Hop算法研究

劉彩霞，黃廷磊

(1.桂林電子科技大學計算機科學與工程學院，廣西桂林541004;2.桂林旅游高等?？茖W?，F代教育技術中心，廣西桂林541006)

位置信息對傳感器網絡的監測活動非常重要，沒有位置的監測消息毫無意義，事件發生的位置和獲取到信息的節點的位置是傳感器節點監測消息中所包含的重要信息。如何確定無線傳感器網絡中節點的位置信息稱為“節點定位”成為了必須解決的關鍵問題之一。所謂節點定位，就是根據少數已知位置的節點，按照某種定位機制確定自身的位置的過程。

根據定位機制，可將現有的無線傳感器網絡自身定位算法分為Range-based和Range-free兩類。前者需要通過測量節點間點到點的距離或角度等信息;后者無須距離和角度信息，僅根據網絡連通性等信息實現節點的定位。

DV-Hop算法是目前應用最廣泛的非基于測距的定位算法之一，針對DV-Hop算法的改進算法已有很多，本文針對DV-Hop算法通信量大，且在惡劣環境下容易受到蟲洞攻擊影響，使定位精度大幅下降的情況，提出了一種改進的DV-Hop算法，通過合理地限制跳數，有效地減少了通信量;通過增加蟲洞檢測以及處理過程有效地減小了蟲洞攻擊的影響;通過蟲洞鏈路位置確定以及受到攻擊的節點對數量多少的檢測，來選擇性地對節點進行重定位過程，從而有效解決了大量蟲洞攻擊的影響。仿真驗證表明，本文提出的定位方法，在同等條件下，明顯減少了通信量，并在受到蟲洞攻擊時利用簡單而有效的方法降低了定位誤差，提高了定位精度。

1 DV-Hop及其已有改進算法

1.1 DV-Hop算法簡介

DV-Hop算法是由美國的Niculescu等人提出的分布式定位系統中的一種算法?？煞譃槿缦虏襟E:

(1)錨節點先通過距離矢量路由廣播自身信息，網絡中所有節點記錄下錨節點坐標及相應最小跳數，并和鄰居節點交換信息。

(2)錨節點接收到來自其它所有錨節點的信息后，估算平均每跳距離。然后，每個錨節點廣播自己的平均每跳距離，未知節點只接收離自己最近的錨節點的信息。

(3)當未知節點得到到3個及以上不同錨節點的距離后，運用三邊測量法或極大似然估計法計算自己的位置。

1.2 已有改進算法

DV-Hop算法被提出后，對其改進算法已有很多［1-12］，其中，比較典型的文獻［2］中，定位節點對接收到的多個信標節點的平均每跳距離進行算術平均處理;文獻［3］根據定位節點記錄的距離多個信標節點的跳數信息，對各信標節點的平均每跳距離值賦予了不同的權值;文獻［4］也是采用加權平均思想，調整加權平均系數，修正全網平均每跳距離;文獻［5］則是通過計算每個信標節點的平均每跳距離誤差，從而計算出全網平均每跳距離誤差，用來修正全網平均每跳距離。即已有成果大都是以增加節點的計算量或者通信量為代價來提高定位精度，文獻［9］則是在減小通信量的基礎上提高了定位精度。文獻［9］對DV-Hop定位算法的改進是為了避免在網絡拓撲結構不規則時，實際每跳距離的誤差會隨著跳數的增加而變大，估算的每跳距離也會與實際偏差越來越大。因此，文中算法限定了最大跳數 T，其中為正方形網絡區域的邊長，R為節點通信半徑，P為錨節點的比例，A為每個未知節點定位需要的平均錨節點數，S為網絡中節點總數，令未知節點接收跳數T范圍內的包含校正值的錨節點信息，從而限制了未知節點的通信范圍，減少了通信量。文獻［9］中的算法與DV-驗是否存在蟲洞攻擊，當時存在蟲洞攻擊，錨節點間用hop=1+來代替的跳數，其中R是Hop算法相比，減少了通信量，并提高了節點的定位精度，但是降低了網絡的覆蓋率。

上面文獻中對DV-Hop算法的改進都是在安全環境下提出的，當網絡環境不安全時，僅通過上面那些方法是無法保證定位性能的。由于DV-Hop算法依靠距離矢量交換估計距離，最容易受到蟲洞攻擊的影響，文獻［10］中提出了一種抵抗蟲洞攻擊的方法，通過檢測兩個節點間的距離是否大于其最大通信半徑來檢節點的最大通信半徑，(xi，yi)和(xj，yj)為兩個錨節點的坐標;相似地，文獻［12］中，作者提出了一種通過檢測兩個節點之間的跳數是否受到攻擊的算法DWDV(Defend Wormhole Attack in DV-Hop)，具體方法是檢測跳數是否小于最小跳數hopleast，如果跳數小于hopleast，則跳數是不合理的，則用最優化跳數hopopt替換受到攻擊的跳數，hopopt是同網絡區域相關的;文獻［11］提出一種基于標簽(Label-based DV-Hop)的DV-Hop安全定位算法，通過特定的策略將錨節點和未知節點加上不同的標簽，從而將受到攻擊的路由信息丟棄，但是尋找受到攻擊的路由信息的過程比較復雜;Lazos等分別提出了 SeRLoc協議［13］、ROPE 協議［14］和 HiRLoc 協議［15］，雖然都一定程度上提高了定位精度，但是增加了大量的硬件成本、計算開銷和通信開銷，不適用于大規模的無線傳感器網絡應用。

2 蟲洞攻擊簡介

蟲洞攻擊，是一種合謀攻擊，攻擊者可以建立一條不在彼此的通信范圍內的鏈路，主要針對網絡中帶防御性的路由協議進行嚴重攻擊。它在兩個合謀惡意節點間建立一條延遲很小的隧道，即所謂的蟲洞，攻擊者在隧道一端把收到的包發送到隧道另一端，在隧道的另一端進行回放攻擊。由于合謀的惡意節點通過一個私有的網絡連接，而不是通過正常網絡連接，所有又稱這種攻擊為隧道攻擊。這種攻擊能破壞路由競爭條件，使遭受攻擊的節點收到一個錯誤的信息報，而丟棄了正確的包。另外，蟲洞攻擊還能導致路由拓撲混亂，通過蟲洞轉發包，可以使兩個遠距離的節點認為是相鄰的。從而，使定位精度大為降低，給傳感器節點的定位過程帶來嚴重的影響。

3 本文改進算法

目前，對于DV-Hop算法在惡劣環境下的研究相對較少，而且已有的改進算法的性能還是不夠理想，因此還需要進一步的研究。為了綜合考慮算法性能，本文參考文獻［9-10，12］提出一種新的基于DV-Hop的改進算法。

3.1 算法改進點

(1)為了減少通信量，對跳數T作了限制，此處參考文獻［14］中的設置方法其中，假設網絡區域為正方形，L是其邊長，r為節點通信半徑，P為錨節點的比例，S為網絡中節點總數，A為每個未知節點定位需要的平均錨節點數。

(2)當檢測到有蟲洞攻擊時，跳數信息必須進行處理，這樣才可以避免蟲洞攻擊所造成的巨大影響，如果重新設置的跳數信息仍然不合理，也會造成定位誤差的擴大，如何設置跳數信息是個具有挑戰性的問題。

考慮到隨著節點間跳數的增加，節點間實際距離與估計距離存在的誤差越大，我們對跳數進行了特殊處理，當時，hop=，否則當＞3時，估計跳數不再是簡單地對其進行取整，而是要加即 hop=，但 hop的最大值限制為T。

(3)對于存在蟲洞攻擊的情況下，為了確認蟲洞鏈路的具體位置，我們又增加了一個信息廣播過程，即在未知節點定位后將其位置信息廣播向鄰居節點，鄰居節點接收到該信息之后，取出信息中包含的位置，通過判斷是否大于r來檢測兩個節點之間是否存在蟲洞鏈路，若存在，則標記該未知節點的id，并發反饋信息給該未知節點，同時發報警信號到網絡控制器。

(4)在網絡受到一定量的蟲洞攻擊時，我們選擇性地增加了重定位過程，此時，系統控制器會根據接到的報警信號多少來決定是否需要重定位，若開始重定位，未知節點在執行定位過程時，不再需要進行安全檢測，每個節點會查詢首次定位時標記出的蟲洞鏈路的位置，從而繞開它。

3.2 算法具體描述

該算法具體過程描述為:

(1)每個錨節點將其位置信息以數據分組的形式在網絡中廣播出去，分組的格式為{idi，xi，yi，hopi}，其中包含了該錨節點的id號、位置信息(xi，yi)以及跳數信息hopi，hopi初始值為0。

(2)接收到此分組的每個鄰居節點將hopi改為hopi+1，如果此時 hopi＞T，則放棄該信息;否則執行(3)。

(4)當節點接收到一個idi號相同的數據分組時，便與自己數據表中相同idi號信息的hopi比較。若新的跳數小于數據表中已存在的跳數，則轉向(3)，否則否則丟棄該數據分組，也不再進行轉發。

(5)當泛洪過程結束后，每個錨節點計算自己的平均每跳距離。錨節點i可利用式(2)計算平均每跳距離:

(6)每個錨節點將自己計算的平均每跳距離以數據分組的形式廣播至網絡中，分組的格式為{idi，Ci，hopsi}，其中包含了該錨節點的idi號、平均每跳距離Ci以及被傳播的次數hopsi。接收到此分組的鄰居節點先判斷hopsi是否大于或者等于T，如果是，則丟棄該分組;否則如果該節點是錨節點，則放棄該信息分組，如果不是則將hopsi加1并將該分組信息以{idi，Ci，hopsi}的形式存儲到自己的數據表中，然后繼續向新的鄰居節點廣播。當遇到idi號重復的數據分組時便丟棄。

(7)未知節點接收到平均每跳距離后，根據自己數據表中記錄的跳數，按照Di=Ci*hopi來計算上一 個 矯 正 值 到每個錨節點的距離。

(8)未知節點得到3個或3個以上到不同錨節點的距離后，運用三邊測量法或極大似然估計法計算自己的位置。

(9)首次定位結束后，計算出自己位置的未知節點，將自己的位置以數據分組的形式廣播至網絡中，分組的格式為{idi，xi，yi}。接收到此分組的鄰居節點如果位置已知，則計算 L=是否大于 R，若是，則將 idi作一標記并單獨保存下來，同時發出報警信號。

(10)未知節點廣播完之后，網絡總控制器根據接到報警信號的次數決定是否需要重新定位，若需要則啟動重新定位程序。由于假定蟲洞鏈路形成后不再改變位置，因而重定位過程中不需要再次進行安全檢測，但是在信息分組泛洪過程中，接收信息的節點要檢測信息是否來自首次定位時標記過的節點，若是，則直接放棄該消息，若不是，則將信息分組保存并在T跳范圍內繼續傳播。

余下其他步驟與首次定位相同。為便于閱讀，圖1給出了算法流程圖。

圖1 算法流程圖

3.3 算法分析

為了抵御蟲洞攻擊，本算法增加了蟲洞檢測過程，因而需要判斷兩個錨節點間距離是否合理，但由于錨節點的比例較小，因而這個過程計算量增加也較少;未知節點定位后廣播自己的位置，周圍節點需要通過計算來確定自己與該未知節點間是否存在蟲洞鏈路，這也需要增加計算量，這個增加量與未知節點數量成線性關系;最后一部分是，當網絡中受到蟲洞攻擊的節點對數量較多時，需要進行重新定位，從而導致計算量的增加。但在網絡受到較少蟲洞攻擊或沒有攻擊時，該算法計算量的增加還是比較少的。

該算法在發現有蟲洞攻擊時，不是簡單地通過取整來替代錨節點間的跳數而是通過一個公式，針對不同值進行不同的處理，可以較好地避免因網絡拓撲不規則造成的距離誤差;未知節點利用有限跳數范圍內的錨節點作為參考節點，也有效緩解了網絡拓撲結構不規則時累積跳距誤差的影響，從而提高了定位精度。另外，該算法在抵御蟲洞攻擊時，僅僅通過簡單的計算過程，沒有增加任何的硬件成本，且在受到較多蟲洞攻擊時，可以通過重定位過程實現更準確的定位。

該算法增加了蟲洞鏈路位置確認過程，在消息傳播時可以繞開蟲洞鏈路，從而為準確定位提供了保證，同時，在自定位結束后，節點傳送所獲得的信息時，也可以繞開蟲洞鏈路，因此，該方法不僅能實現安全定位，而且在定位結束后的應用中也可以抵御蟲洞攻擊，起到了雙重保護作用。

總之，在受到蟲洞攻擊時，該算法與文獻［12］比，在網絡拓撲結構不規則的情況下，也可以有效地提高定位精度，實現在蟲洞攻擊下的安全定位。

4 仿真驗證

對于定位算法而言，衡量其性能的指標也不外乎定位誤差、平均定位誤差、定位精度、計算量、通信量等，本實驗仿真的主要目的是驗證在蟲洞攻擊存在時，提出算法對定位誤差的控制效果，并驗證算法通信量的大小，因而仿真環境仍然選擇MATLAB R2007a，實驗時，隨機產生規定數目的點作為傳感器節點的位置，錨節點則從產生的點中按規定比例取前面的點，然后通過判斷節點間的距離是否大于節點的通信半徑來確定節點間是否可以通信;蟲洞鏈路仍然通過隨機選擇兩個規定好距離的點來模擬，蟲洞攻擊則通過判斷傳感器節點與攻擊者之間的距離是否小于攻擊者的通信半徑來確定，若小于，則表示傳感器節點受到蟲洞攻擊。

4.1 驗證1

本算法中設置了非線性的跳數替換公式，為了驗證該公式的設置對定位誤差的改進效果，我們用文獻［12］中算法與本算法進行比較，每種算法仿真隨機運行100次取平均值。

為了使算法適合大型網絡使用，我們設仿真環境的主要參數為:500個節點隨機部署在300 m×300 m的方形區域中，錨節點比例從5%到50%，節點通信半徑R分別取20 m和40 m，蟲洞鏈路的長度分別設為50 m，蟲洞鏈路數從5到50遞增。

在蟲洞鏈路數為10，通信半徑為R=20時，平均定位誤差都隨著錨節點比例的變化曲線分別如圖2所示。

圖2 平均定位誤差隨錨節點比例的變化曲線

分析上圖，我們可以得出結論:平均定位誤差隨著錨節點比例升高而不斷下降，當錨節點的比例超過30%時，定位誤差的下降速度越來越緩慢，漸漸趨于平穩，但本算法表現出來的性能更好。

在通信半徑為R=20 m，錨節點比例為20%，其中假設在蟲洞鏈路數為20時，系統需要進行重定位，平均定位誤差都隨著蟲洞鏈路數的變化曲線如下圖3所示。

圖3 平均定位誤差隨著蟲洞鏈路數的變化情況

從圖3我們可以看出，在通信半徑和錨節點比例不變的情況下，文獻［12］中算法的平均定位誤差會隨著蟲洞鏈路數量增加不斷升高，當蟲洞鏈路數是50時，其平均定位誤差接近節點通信半徑的2倍，而使用本算法，平均定位誤差則不會猛增，因此本算法可以更好地抵御蟲洞攻擊。

4.2 驗證2

在仿真實驗中，若我們假設在蟲洞鏈路數超過20時，系統就需要重定位，則會造成通信量的增加，下面將本算法與DV-Hop算法進行比較，每種算法仿真隨機運行100次取平均值。

我們設仿真環境的主要參數為:500個節點隨機部署在300 m×300 m的方形區域中，錨節點比例為20%，節點通信半徑R取20 m，蟲洞鏈路的長度設為50 m，蟲洞鏈路數從5到50遞增;算法中設置的最大跳數限制T，由其公式計算出T＞1.465 8，實驗中我們取T=3。仿真結果如圖4所示。

圖4 通信量隨蟲洞鏈路數的變化情況

我們按節點廣播信息來計通信量，節點每廣播一次，通信量就增加1，從圖4可以看出，在錨節點比例和節點通信半徑一定的情況下，隨著蟲洞鏈路數量的增加，DV-Hop算法需要的通信量不斷減少;本算法的通信量則在重定位前后分別處于平穩狀態，但在重定位后通信量會增加約1倍，卻仍然比DV-Hop算法小很多;當錨節點比例或節點通信半徑增大時，T會相應地減小，從而本算法的通信量也會隨之略有減少。

5 總結

本文對DV-Hop算法進行了多方面改進，理論分析及仿真實驗表明，本章算法不需要借助昂貴的硬件輔助，僅通過簡單的計算來抵御蟲洞攻擊，不僅實現容易，而且算法性能較好，因而適合用于大規模的網絡應用中。下一步我們將研究該算法在三維環境下無線傳感器網絡的定位應用。

［1］馬祖長，孫怡寧.無線傳感器網絡節點的定位算法［J］.計算機工程，2004，30(7):13-14，48.

［2］彭剛，曹大元，孫利民.無線傳感器網絡節點定位機制的研究［J］.計算機工程與應用，2004.34:27-29.

［3］戴瑩，王建平，張崇巍.無線傳感器網絡節點定位算法的研究與改進［J］.傳感技術學報，2010，23(4):567-570.

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

［5］林金朝，劉海波，李國軍，等.無線傳感器網絡中DV-Hop節點定位改進算法研究［J］.計算機應用研究，2009，26(4):1272-1276.

［6］廖先林，耿娜，石凱，等.無線傳感器網絡節點自身定位算法［J］.東北大學學報:自然科學版，2007，28(6):801-804.

［7］趙清華，劉少飛，張朝霞，等.一種無需測距節點定位算法的分析和改進［J］.傳感技術學報，2010，23(1):122-127.

［8］張佳，吳延海，石峰，等.基于DV-HOP的無線傳感器網絡定位算法［J］.計算機應用，2010，30(2):323-326.

［9］侯阿臨，桃敏，沈楊，等.基于DV-Hop的免測距WSN定位算法研究［J］.長春工業大學學報(自然科學版)，2009，30(6):674-678.

［10］周啟明，何勇.DV-Hop中蟲洞攻擊的仿真及其抵抗方法［J］.計算機工程與應用，2010，46(14):88-90.

［11］Wu Junfeng，Chen Honglong，Lou Wei，et al.Label-Based DV-Hop Localization Against Wormhole Attacks in Wireless Sensor Networks［C］//2010 Fifth International Conference on Networking，Architecture，and Storage，2010，7.

［12］Zhu Bin，Liao Junguo，Zhang Huifu.Defending Wormhole Attack in APS DV-Jop［C］//2008 Third International Conference on Communications and Networking in China，(Chinaeom2008，Aeeessionurnber:090111839491).

［13］Lazos L，Poovendran R，Capkun S.ROPE:Robust Position Estimation in Wireless Sensor Networks［C］//Proc.of IEEE IPSN，2005.

［14］Lazos L，Poovendran R.SeRLoc:Robust Localization for Wireless Sensor Networks［J］.ACM Transactions on Sensor Networks，2005，1(1):73-100.

［15］Lazos L，Poovendran R.HiRLoc:High-Resolution Robust Localization for Wireless Sensor Networks［J］.IEEE Journal on Selected Areas in Communications，2006，24(2):233-246.

［16］Hu Y C，Perrig A，Johnson D B.Wormhole Attacks in Wireless Networks［J］.IEEE Journal on Selected Areas in Communications，2006，24(2):370-380.