WSNs中DV-hop定位算法的安全增強研究

周明偉，劉淵

江南大學數字媒體學院，江蘇無錫214122

1 引言

傳感器的感知功能以及節點間的通訊能力，為無線傳感器網絡提供了廣闊的應用前景。作為一種無處不在的感知技術，無線傳感器網絡廣泛應用于軍事、環境監測和預報、智能家居、健康護理、建筑物狀態監控、復雜機械監控、城市交通、空間探索以及機場、大型工業園區的安全監測等領域。隨著無線傳感器網絡的深入研究和廣泛應用，無線傳感器網絡將逐漸深入到人類生活的各個領域。無線傳感器網絡采集的數據往往需要與其位置信息相結合才有意義，因此，確定事件發生的位置或獲取信息的節點位置是無線傳感器網絡最基本的功能之一，對無線傳感器網絡應用的有效性是至關重要的，當一個傳感器節點檢測到一個緊急事件時，它的位置信息應該快速并準確地被識別，不知道傳感器位置的遙感數據是沒有意義的[1]。一個直接的解決辦法是為每一個傳感器節點配置一個GPS接收器。這樣就可以準確提供它們的位置信息，然而為每個節點都配備GPS定位組件將消耗大量的成本，不符合最小化成本的目的。因此只能為一小部分節點配備GPS組件，這些配備GPS的節點稱為信標節點或錨節點，未知位置的節點稱為未知節點或待定位節點，待定位節點可以利用附近的多個錨節點的位置信息來估計自身的位置。

WSNs中節點定位技術越來越受到研究者的關注，并且提出了許多基于測距和基于非測距的方案。基于測距的技術需要測量相鄰節點間的絕對距離或方位來計算未知節點的位置，包括信號強度測距法（Received Signal Strength Indicator，RSSI）[2]，到達時間差（Time Difference On A rrival，TDOA）測距法[3]，到達時間（Time Of A rrival，TOA）定位法[4]和到達角（Angle Of A rrival，AOA）[5]定位算法等。基于非測距的定位技術利用節點間的估計距離計算節點位置，包括質心（centroid algorithm）定位算法，凸規劃（convex optim ization）定位算法，以三角形內的點近似定位（APIT）算法[6]，基于距離矢量計算跳數（DV-Hop）定位算法[7]等。但提出的這些定位算法僅能夠在環境較穩定，未受到攻擊者破壞的理想環境中進行，但由于位置信息是無線傳感器網絡服務的重要部分，設計一個具有抵御攻擊的安全定位方案尤為重要。然而，任何一種安全措施都需要消耗一定的資源包括節點自身的計算和能源開銷以及網絡通信開銷等，因此，對于一個具體的定位系統，還要考慮系統的應用背景、攻擊模型、安全需求和資源條件等多種因素進行折中，以確定其防御策略[8]。

考慮到傳感器節點自身條件的限制，本文在非測距的DV-Hop定位算法的基礎上，增加了一些安全機制。DV-Hop定位算法是一種典型的利用跳數來定位未知節點的非測距方法，對節點的硬件要求低，實現簡單。同時，本文選取蟲洞攻擊作為抵御目標，因為蟲洞攻擊不需要損壞任何節點也不需要破譯密鑰便可以實施攻擊，因此，僅通過密鑰管理技術來抵御蟲洞攻擊是不夠的。

本文研究的安全方案是在對節點進行定位前，利用簡單的三角不等式規則對信標節點的合法性進行檢測，然后在DV-Hop定位算法的第一步進行改進，利用鄰節點間的RTT屬性值增加檢測蟲洞攻擊的模塊，若檢測出蟲洞攻擊，則通過調整通信節點間的跳數來抵御蟲洞攻擊。最后，仿真實驗證明了該方案對惡意信標節點、蟲洞攻擊的檢測以及抵御的有效性。

2 DV-hop定位方案

2.1 DV-hop定位算法

距離向量算法（DV-hop）使用平均每跳距離計算實際距離，對節點的硬件要求較低，實現簡單，它的定位過程如下：

（1）計算未知節點與每個信標節點的最小跳數

信標節點向鄰居節點廣播自身位置信息的分組，其中包含跳數字段，初始化為0，接收節點記錄到每個信標節點的最小跳數，忽略來自同一個信標節點的較大跳數的分組，然后將跳數值加1，并轉發給鄰節點，通過這個方法，網絡中的所有節點能夠記錄到每個信標節點的最小跳數。

（2）計算未知節點與信標節點的實際跳段距離

每個信標節點根據第一階段中記錄的其他信標節點位置信息和相距跳數，利用公式（1）估算平均每跳的實際距離：

其中(xi，yi)，(xj，yj)是信標節點i，j的坐標，hj是信標節點i與j之間的跳段數。

然后信標節點將計算的每跳平均距離用帶有生存期字段的分組廣播到網絡中，未知節點僅記錄接收到的第一個平均每跳距離，并轉發給鄰居節點，這個策略確保了絕大多數節點從最近的信標節點接收每跳平均距離值。未知節點接收到平均距離后，根據記錄的跳數，計算到每個信標節點的距離。

（3）利用三邊測量法或者極大似然估計法計算自身位置

未知節點利用第二階段中記錄的到各個信標節點的跳段距離，用三邊測量法或極大似然估計法計算自身坐標。極大似然估計法在無線傳感器網絡定位計算中被廣泛使用。假設與未知節點D(x，y)能夠直接通信的信標節點有N個且坐標分別為(x1，y1)，(x2，y2)，…，(xn，yn)，并且假設通過測距技術已知它們到節點D的距離分別為d1，d2，…，dn，則存在如下關系：

由第一個方程開始逐一減去最后一個方程，則得到：

將式（3）表示為：

最后，使用標準的最小均方差估計法即可以估算得到未知節點D的坐標：

2.2 DV-hop定位算法的蟲洞脆弱性分析

蟲洞攻擊是通過兩個串謀惡意節點n1、n2建立起一條高質量高帶寬的私有通道，攻擊者在網絡中的節點n1位置上記錄數據分組或位置信息，通過此私有通道將竊取的信息傳遞到網絡的另一個位置節點n2處。由于蟲洞攻擊采用高質量高帶寬的私有通道，所以通過私有通道傳遞的數據分組比通過正常多跳路徑傳遞的數據分組要早到目標節點。在這種情況下，即使網絡通訊間存在信任和身份認證，攻擊者無密鑰仍能夠進行攻擊。蟲洞攻擊對DV-hop定位算法的影響主要表現在兩方面：

（1）引起定位誤差

蟲洞攻擊可以極大惡化DV-hop的定位過程，在DV-hop定位算法的第一階段，蟲洞攻擊使得信標節點間的跳數異常，這直接影響了算法第二部計算平均跳段的過程，最終導致整個定位系統失效。如圖1所示，在惡意節點A1和A2之間存在一條蟲洞鏈，A1接收來自于節點B1的信息，然后將信息通過隧道轉發給A2，A2將信息重放給B2，正常情況下，信標節點B1和B2之間有5跳，但在存在蟲洞鏈的情況下，跳數變為2跳，導致B2對平均每跳的距離作出錯誤的估算。同樣，位于B2附近的節點也將會得到一個較小的距離B1的跳數，這樣使用三邊測量法或者最大似然估計法計算坐標的時候將會得到一個具有較大誤差的位置估計結果。

圖1 蟲洞攻擊對系統的影響

（2）能量消耗

在存在蟲洞攻擊的情況下，節點不得不傳送更多的重傳信息，這樣消耗了更多的能量，這對于一個資源有限的網絡來說是致命的。

總之，蟲洞攻擊因其實現簡單，對基于非測距的定位系統破壞性極大，因此，本文以蟲洞攻擊作為研究對象。

3 系統模型

本文提出的安全定位方案，主要由三部分構成，如圖2所示。系統首先檢測并移除非法或惡意的信標節點，待確定了信標節點的合法性之后，檢測網絡中是否存在蟲洞攻擊，然后根據得到的信息采取不同的定位方案。

圖2 安全定位系統模型

3.1 檢測并移除非法信標節點

由于無線傳感器網絡中未知節點是根據信標節點發送的位置信息來完成自身的定位過程，故信標節點的有效性直接關系到定位結果的有效性。若信標節點被惡意節點破壞或者是由惡意節點偽造的節點，那么所有的基于信標節點的定位系統都將失效。因此，本文研究的安全方案在定位之前添加了檢測并移除非法信標節點的模塊。考慮到傳感器節點的自身資源的有限性，該模塊使用了一個簡單的規則——三角不等式規則來檢測信標節點的合法性。

設N為待檢測節點，B1和B2是一對待檢測的信標節點，這三個節點構成了一個三角形ΔNB1B2，根據三角不等式規則，第三邊必小于另兩邊之和并且大于另兩邊之差。即在ΔNB1B2中有：為B1與B2之間的距離，d1、d2為檢測節點N分別到B1、B2節點的距離，利用接收到的信標信號，通過物理方法可以得到。若檢測節點N發現d12不滿足其中的任一條件則將認為B1、B2為惡意節點。然后檢測節點N將檢測結果發送給基站，基站將建立一個表格用于保存每個信標節點的ID以及被標記為惡意節點的次數統計。當某個節點被標記的次數超過閾值t時，則確認該節點為惡意節點將其從網絡中移除。

在該方案中采用了一個簡單的投票機制，假設網絡中共有n個信標節點，每兩個節點組成一個待檢測對。當檢測節點檢測到信標節點為惡意節點時則投一票，最后將每個信標節點的票數累加。可知，一個信標節點獲得最多票數為n-1，最少為0，即n-1代表著最不可信節點，而0代表著最可信節點。閾值t取為最大值與最小值的平均值，即

3.2 抵御蟲洞攻擊模型

在確定了信標節點的合法性后，接下來對網絡中存在的非法節點進行檢測。本文以蟲洞攻擊為研究目標，因其容易實現并且對定位方案具有很大影響，對定位系統是一個很大的挑戰。同樣考慮到傳感器節點自身的有限資源，本文提出的安全方案是在DV-hop定位方案的第一階段進行改進，利用節點間完成一次通信的時間RTT（Round Trip Time）[9]來檢測網絡中存在的蟲洞鏈，若發現異常，則通過修改節點間跳數來降低蟲洞攻擊對定位系統的影響。抵御蟲洞攻擊算法流程圖如圖3所示。

3.2.1 RTT分析

圖3 算法流程圖

RTT是指數據包從一個節點，經過無線網絡傳遞到另一節點的往返時間，RTT可由接收消息時間Rrec減去消息發送時間Rsend求得，即RTT=Rrec-Rsend。假設節點s1與鄰居節點s2進行通信，在正常情況下，節點s1與節點s2的RTT值為2p。如果s1與s2之間建立的直接連接是由蟲洞攻擊形成的，那么往返時間RTTwormhole=2(p+w+p)=2(2p+w)。其中w為數據包在蟲洞鏈形成的隧道中傳遞時消耗的時間，因此，可以認為存在蟲洞鏈時，節點間的RTT至少是正常鏈接情況下的2倍，雖然RTT值不僅受到惡意節點存在的影響，還和網絡的可用帶寬、瓶頸帶寬、是否擁塞等有關，但是理論上在同等狀況下的網絡環境中以上關系是不會發生改變的，即在w遠小于p的情況下仍然成立。

3.2.2 抵御蟲洞攻擊算法的具體描述

（1）信標節點Sn發送包含自身位置信息的分組，其中包含跳數字段，初始化為0，同時記錄發送時間Rsend。

（2）接收到信息的鄰居節點發送應答消息給節點Sn，Sn接收應答消息并記錄接收時間Rrec。計算Sn與每個鄰節點的RTT=Rrec-Rsend，并對所有RTT求和得RTTtotal。

（3）計算節點Sn與所有鄰節點Si完成一次通信的平均時間avgRTT=RTTtotal/i。

（4）比較每個RTT(sn，si)是否大于k×avgRTT，其中，n是節點具有的鄰節點總數，m為存在的蟲洞鏈的最多數量。若大于，則認為Sn與Si之間的鏈路為蟲洞鏈路，則執行步驟（5）；若不大于，執行步驟（6）。

（5）修改Sn與Si之間的跳數統計，具體方法將在下文中介紹。

（6）判斷網絡泛洪是否結束，如果結束則進行DV-hop算法的其他階段，否則返回步驟（1）繼續尋找下一跳的鄰節點。

本方案可以很大程度地降低蟲洞鏈對定位系統的影響，這將在后文實驗部分給予證明。

3.2.3 修改受蟲洞鏈影響的跳數

當檢測到有蟲洞攻擊時，跳數信息必須進行處理，這樣才可以避免蟲洞攻擊所造成的巨大影響，如果重新設置的跳數信息仍然不合理，會造成定位誤差的擴大。如何設置跳數信息是個具有挑戰性的問題。本文利用文獻[10]的方法，只不過在取整過程中，本文采用向上取整的方法，由于能夠相互通信的節點必定在通信半徑的范圍之內，不能夠相互通信的節點只能夠通過第三方進行中轉。對兩信標節點之間的距離與通信半徑的商采用向上取整的方式來確定兩點之間的最小跳數更加合理，即當≤3時，跳數hop為：

3.3 算法分析

為了能夠抵御蟲洞攻擊實現安全定位，本方案使用了兩個簡單的算法，首先檢測并移除非法的信標節點，因為未知節點的定位與信標節點發送的位置信息緊密相關。檢測非法信標節點時，使用一個特定的檢測節點N，利用三角不等式規則對信標節點的合法性進行判斷，這個待檢測節點N要確保其合法性，實際環境中可以采用一個特制的節點，由于三角不等式規則不需要復雜計算并且此過程并未增加過多的硬件要求，只需要一個性能良好的節點來完成。因此，該方案不會增加傳感器網絡的負擔。

待確定了信標節點的合法性后，在信標節點向網絡中發送包含自身位置信息的過程中，通過計算與鄰節點之間的RTT值來判斷通信節點間是否存在蟲洞鏈，對RTT值的計算不需要很大的存儲空間，因此該過程不會消耗過多的資源。在檢測到蟲洞鏈時，通過修改節點之間的跳數來最小化蟲洞攻擊對定位系統的影響，該過程只有在檢測到蟲洞鏈存在時才會執行，否則按原始算法進行處理。因此，該方法充分考慮到節點資源的有限性，并且沒有增加任何的硬件成本。

4 仿真結果分析

4.1 惡意信標節點的檢測

本節驗證基于三角不等式規則檢測惡意信標節點的有效性。設無線傳感器網絡布局在500m×500m的區域內，如圖4所示，網絡中設置一個檢測節點N，節點間通訊半徑為r，以檢測節點N為圓心(x0=y0=0)，半徑為l的圓內設置n個信標節點，保證節點之間都可以相互通信。假設惡意信標節點謊報的位置與真實位置偏移距離為a，為了保證實驗效果，實驗中假設偏移方向為水平方向，即Δx=a，Δy=0。實驗中設置n=11，c分別取值2、5、8，閾值t=5，a∈(0.1r，2r)，r=50m，用C程序來進行實驗，所有信標節點到檢測節點N的真實距離通過公式計算得到。實驗結果如圖5所示。

圖4 網絡中節點布局

圖5 偏移量a與系統識別惡意節點的關系

（1）由圖5可知，當惡意節點的偏移距離a較小時，該方案不能夠準確地將所有惡意信標節點識別出來，當偏移距離a≥r時該方案才能發揮理想作用，將大部分惡意節點準確識別出，這說明惡意節點偏移量的大小對該方案的有效性有直接的影響。但在接下來的實驗將證明若偏移量a較小時，其對定位系統的定位精度影響是很微弱的，即攻擊者若想對定位系統造成較大的影響必須將偏移量a設置得足夠大。但在a值較大的情況下，本方案可以將大部分惡意節點識別出。因為實際環境中，存在即使信標節點偏離實際位置很遠，也可能滿足三角不等式規則的情況，這會對識別結果造成一定的影響，如何避免此影響的研究將是今后的工作。

（2）該網絡環境中設置了11個信標節點，當惡意節點的數目較少時，即小于n/2時，系統不會發生誤報的現象，但惡意節點的數量超過節點總數的一半后，如c=8時，系統會將良性信標節點誤報為惡意節點，即該方案對惡意節點的數量有一定的要求，若系統中存在過多的惡意節點，則會使系統失效，引起誤報的情況。

4.2 偏移量大小對定位效果的影響

網絡布局如圖6所示，在200m×200m的區域中，布置10個節點，通訊半徑為50m，其中B1、B2、B3為信標節點，且B3為惡意信標節點，選定節點N為待定位節點，已知B1到B3之間的距離為B1B3=125，B1B2=111.8，B2B3=125，B1與B3通信需要的最小跳數是3，B1與B2的為4，B3與B2的為4。因為待定位節點通信只需要1跳，根據DV-hop算法可知，節點N接收從B3獲得的矯正值，而丟棄從B1、B2獲得的。矯正值為(125+125)/(3+4)=35.71，因此它與3個信標節點之間的距離分別為NB1=3×35.71，NB2=3×35.71，NB3=1×35.71，使用三邊測量法可以得到未知節點的位置信息，惡意節點會對矯正值產生影響，導致整個定位過程出現誤差。本實驗使用C程序來實現，實驗結果如表1所示，其中定位誤差為誤差與通信半徑之比。

圖6 無線傳感器網絡布局

由表1可以看出，當偏移量a值較小時，其引起的定位誤差在可以接受的范圍內，僅為通信半徑的0～30%之間。而當a值較大時，如1r附近，其引起的誤差較大，對定位精度有著較大的影響。因此，得出結論，攻擊者若企圖破壞定位系統，a值必須足夠大。

4.3 抵御蟲洞攻擊的有效性

本部分實驗在Linux環境下，使用NS2模擬網絡環境，然后對生成的trace文件進行分析，驗證該方案檢測以及抵御蟲洞攻擊的有效性。蟲洞攻擊由兩個具有遠大于正常節點的通信半徑的特殊節點來模擬，并在兩個惡意節點間用一條有線鏈路表示蟲洞鏈。無線傳感器網絡布置在一個500m×500m的區域中，均勻分布100個傳感器節點，其中包括信標節點和普通節點，節點的通信半徑設置為50m。

表1 偏移量對定位精度的影響

在不存在蟲洞攻擊的情況下，隨著信標節點的增長，定位精度的變化如圖7所示。隨著信標節點的增加，定位誤差逐漸下降，當信標節點達到一定數量后，定位精度趨于平緩。

根據圖7，選取15個信標節點來實驗隨著蟲洞鏈的增加，DV-hop基本算法與使用本文提出的安全定位方案的定位誤差之間的對比。假設每個蟲洞鏈都可以成功截獲數據包，并通過隧道傳遞給蟲洞鏈另一端的惡意節點。實驗過程中選定一個待定位節點作為實驗對象，并人工設定蟲洞鏈的位置，以便對定位結果造成直接影響，實驗結果如圖8所示。

圖8 定位誤差隨著蟲洞鏈數變化的情況

從圖8可以看出，隨著蟲洞鏈數量的增長，由常規定位算法計算出未知節點的定位誤差增長很快，在蟲洞鏈數量為2時，定位誤差超過了通信半徑的一半以上，定位結果已經接近無效。由此可見，蟲洞攻擊對系統的定位效果有極大的影響，但本文提出的方案可以有效地減弱蟲洞攻擊對定位系統的影響。隨蟲洞鏈數量的增長，本文提出的安全定位方案的定位誤差并未呈現急劇增長的局面，而是很好地控制了誤差的增長，使得定位誤差仍然在可以接受的范圍內。

文獻[11]中提出了一種通過檢測兩個節點之間的跳數是否受到了攻擊的算法DWDV（Defined Wormhole attack in DV-hop），具體的方法是首先檢測節點間跳數是否小于最小跳數hopleast，如果小于，則表明該跳數是不合理的，那么就用最優化跳數hopopt替換受到攻擊的跳數，hopopt是同網絡區域相關的。將本文提出的算法與該算法進行對比，結果如圖9所示。

圖9 與文獻[11]中算法效果對比圖

從圖9中可以看出，在蟲洞鏈數量較少的時候，文獻[11]中的算法同樣發揮出較好的效果，但隨著蟲洞鏈比重的增加到4個以上的時候，定位誤差會急劇上升，而本文提出的算法仍然能夠保持較好的定位效果。

5 總結

本文分析了常用于無線傳感器網絡節點定位的算法，其中大部分算法在理想的環境中不存在惡意攻擊的情況下發揮了良好的定位性能，但隨著技術不斷更新，社會復雜化的加劇，顯然已有的算法不能發揮其應有的價值，尤其是在對安全性要求較高的環境如戰場中，在敵人采用惡意節點攻擊的情況下，如何能夠及時識別惡意節點并采取相應措施，顯得尤為重要。因此，研究了一種安全的定位方案，由于蟲洞攻擊的特殊性，本文用其作為抵御對象，同時考慮到節點自身資源的限制，本文在實現簡單，對硬件要求低的基于非測距的定位算法DV-hop的基礎上增加了安全模塊，并在運行定位模塊之前增加檢測并移除惡意信標節點的過程。理論分析及仿真實驗證明，提出的安全定位方案不需要借助昂貴的硬件輔助，實現簡單，在檢測惡意信標節點以及抵御蟲洞攻擊上具有良好的效果。本文研究對象限制在靜態傳感器節點上，下一步的重點是研究能夠適用于大規模隨機性布置節點的動態網絡節點定位的安全方案。

[1]Rabaey J M，Ammer M J，da Silva J L，et al.PicoRadio supports ad hoc ultra-low power w ireless networking[J].Computer，2002，33（7）：42-48.

[2]Girod L，Bychovskiy V，Elson J，et al.Locating tiny sensors in time and space：a case study[C]//Proceedings of the 2002 IEEE International Conference on Computer Design：VLSI in Computers and Processors，Freiburg，2002：214-219.

[3]Girod L，Estrin D.Robust range estimation using acoustic and multi modal sensing[C]//Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems，Maui，2001：1312-1320.

[4]Harter A，Hopper A，Steggles P，et al.The anatom y of a context-aware application[C]//Proceedings of the 5th Annual ACM/IEEE International Conference on Mobile Computing and Networking，Seattle.[S.l.]：ACM Press，1999：59-68.

[5]Nicolescu D，Nath B.Ad-hoc positioning system using AoA[C]//Proceedings of IEEE International Conference on Computer Communications，San Francisco，2003.

[6]He T，Huang C，Blum B M，et al.Range free location schemes for large scale sensor networks[C]//Proceedings of ACM International Symposium on Mobile Ad-hoc Networking&Computing，Maryland，2003.

[7]Niculescu D，Nath B.DV based positioning in Ad hoc networks[J].Journal of Telecommunication Systems，2003，22（1/4）：267-280.

[8]Labraoui N，Gueroui M，A liouat M，et al.Data aggregation security challenge in Wireless Sensor Networks：a survey[C]//Proceedings of the 5th IEEE International Symposium on Wireless Pervasive Computing（ISWPC），2010：325-330.

[9]Labraoui N，Gueroui M.Secure range-free localization scheme in Wireless Sensor Networks[C]//Proceedings of the 10th International Symposium on Programming and Systems（ISPS），2011：1-8.

[10]Liu Caixia，Huang Yanlei.Research on improved DV-hop algorithm against wormhole attacks in WSN[J].Chinese Journal of Sensors and Actuators，2011，24（10）.

[11]Zhu Bin，Liao Junguo，Zhang Huifu.Defending wormhole attack in ASP DV-Hop[C]//Proceedings of the 3rd International Conference on Communications and Networking，2008.