劉彩霞，黃廷磊

(1.桂林電子科技大學(xué)計算機科學(xué)與工程學(xué)院，廣西桂林541004;2.桂林旅游高等專科學(xué)校現(xiàn)代教育技術(shù)中心，廣西桂林541006)

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

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

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

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

1.1 DV-Hop算法簡介

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

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

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

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

1.2 已有改進算法

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

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

2 蟲洞攻擊簡介

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

3 本文改進算法

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

3.1 算法改進點

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

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

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

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

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

3.2 算法具體描述

該算法具體過程描述為:

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

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

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

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

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

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

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

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

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

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

圖1 算法流程圖

3.3 算法分析

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

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

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

總之，在受到蟲洞攻擊時，該算法與文獻［12］比，在網(wǎng)絡(luò)拓撲結(jié)構(gòu)不規(guī)則的情況下，也可以有效地提高定位精度，實現(xiàn)在蟲洞攻擊下的安全定位。

4 仿真驗證

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

4.1 驗證1

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

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

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

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

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

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

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

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

4.2 驗證2

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

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

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

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

5 總結(jié)

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

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

［2］彭剛，曹大元，孫利民.無線傳感器網(wǎng)絡(luò)節(jié)點定位機制的研究［J］.計算機工程與應(yīng)用，2004.34:27-29.

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

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

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

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

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

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

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

［10］周啟明，何勇.DV-Hop中蟲洞攻擊的仿真及其抵抗方法［J］.計算機工程與應(yīng)用，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.