改進(jìn)的抵制蟲洞攻擊的DV-Hop算法

樂小意，何涇沙

（北京工業(yè)大學(xué) 北京 100024）

近年來，無線傳感器網(wǎng)絡(luò)引起學(xué)術(shù)界和工業(yè)界的廣泛關(guān)注，在傳感器節(jié)點(diǎn)的定位算法中，分為基于距離 （Rangebased）和距離無關(guān)（Range-free）的兩種類型的定位算法，在距離無關(guān)的算法中，DV-Hop定位算法是一個(gè)基于跳數(shù)來實(shí)現(xiàn)定位的算法，由于其良好的精度，對硬件要求低等特點(diǎn)，使其成為一個(gè)優(yōu)秀的算法，在現(xiàn)實(shí)生活中得到了廣泛的應(yīng)用。

文中主要是提出了一種WARSL定位機(jī)制，提高了傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位的準(zhǔn)確性。

1 DV-Hop的基本原理

DV-Hop定位算法是Drago Niculescu等人根據(jù)距離矢量路由原理提出的一系列分布式定位算法APS（Ad Hoc position System）中的一種，采用加權(quán)方法、求精算法來提高DV-Hop算法的性能。

DV-Hop算法[1]的定位過程主要分為3個(gè)階段。第一階段，計(jì)算未知位置節(jié)點(diǎn)與信標(biāo)節(jié)點(diǎn)的最小跳數(shù)。信標(biāo)節(jié)點(diǎn)向鄰近的節(jié)點(diǎn)廣播自己的信息，節(jié)點(diǎn)接收到相鄰節(jié)點(diǎn)廣播的信息，將跳數(shù)值加1后轉(zhuǎn)發(fā)；第二階段，估算每跳的平均距離。信標(biāo)節(jié)點(diǎn)在獲得其他信標(biāo)節(jié)點(diǎn)的信息之后，通過獲得信息中的跳數(shù)，使用公式（1）計(jì)算出其平均每跳的距離。然后將其作為一個(gè)校正值廣播至網(wǎng)絡(luò)中。校正值公式為：

其中（xi-xj），（yi-yj）是信標(biāo)節(jié)點(diǎn) i，j的坐標(biāo)，hj是信標(biāo)節(jié)點(diǎn)i與j之間的最小跳數(shù)。當(dāng)接收到校正值后，節(jié)點(diǎn)根據(jù)自身與信標(biāo)節(jié)點(diǎn)之間的跳數(shù)值來計(jì)算信標(biāo)節(jié)點(diǎn)之間的距離。第三階段，未知節(jié)點(diǎn)根據(jù)自身與3個(gè)或多個(gè)信標(biāo)節(jié)點(diǎn)的距離，使用三邊測量或極大似然法來計(jì)算自己的位置。

蟲洞攻擊，一般需要兩個(gè)節(jié)點(diǎn)才能完成，是一種主要針對網(wǎng)絡(luò)中帶防御性路由協(xié)議的嚴(yán)重攻擊。它在兩個(gè)串謀惡意節(jié)點(diǎn)間建立一條私有通道，攻擊者在網(wǎng)絡(luò)中的一個(gè)位置上記錄數(shù)據(jù)包或位置信息，通過此私有通道將竊取的信息傳遞到網(wǎng)絡(luò)的另外一個(gè)位置。

在DV-Hop定位算法中，蟲洞攻擊會(huì)對DV-Hop定位過程產(chǎn)生嚴(yán)重的影響。如圖1所示，A1和A2節(jié)點(diǎn)相互協(xié)作在網(wǎng)絡(luò)中發(fā)起蟲洞攻擊。當(dāng)B1進(jìn)行泛洪時(shí)，他的廣播信號(hào)會(huì)通過蟲洞鏈路A1轉(zhuǎn)發(fā)到A2，并進(jìn)一步轉(zhuǎn)發(fā)給S7，最終到達(dá)B2。因此，B2獲得與 B1之間的最小跳數(shù)為 3（B1－＞S6－＞S7－＞B2），而在真實(shí)的情況下，B2與 B1之間最小跳數(shù)為 6（B1－＞S1－＞S2－＞S3－＞S4－＞S5－＞B2）。 所以，當(dāng) B2在估算平均每跳距離的時(shí)，其得到的結(jié)果會(huì)比實(shí)際值偏大。另外，未知節(jié)點(diǎn)進(jìn)行定位時(shí)，首先需要估算其與各個(gè)信標(biāo)節(jié)點(diǎn)之間的跳數(shù)，然而，S6通過蟲洞鏈路直接可以傳遞信息到S7，接著到達(dá)B2。S6與B2之間的最小跳數(shù)為 2（S6－＞S7－＞B2），而實(shí)際兩者之間的最小跳數(shù)為 7（S6－＞B1－＞S1－＞S2－＞S3－＞S4－＞S5－＞B2）。 因此 S6估算的其與 B2之間的距離會(huì)偏小。

圖1 蟲洞攻擊對于DV－Hop定位過程的影響Fig.1 Wormhole attack for DV－Hop positioning process

在無線傳感器節(jié)點(diǎn)的定位中，隨著對于無線傳感器網(wǎng)絡(luò)研究的不斷深入，學(xué)術(shù)界也提出了各種各樣的解決方法，主要還是從以下3個(gè)途徑進(jìn)行考慮：①通過增加硬件設(shè)備或完善算法本身等手段來加強(qiáng)定位方法的強(qiáng)壯性；②利用信息加密或者身份認(rèn)證保證節(jié)點(diǎn)的信息傳遞的安全性和可靠性；③引入一些安全模型機(jī)制，檢測和排除一些惡意的攻擊節(jié)點(diǎn)。

2 WARSL定位機(jī)制

在安全的無線傳感器網(wǎng)絡(luò)中，只有信標(biāo)節(jié)點(diǎn)和普通節(jié)點(diǎn)兩種類型的節(jié)點(diǎn)，信標(biāo)節(jié)點(diǎn)攜帶GPS（Global Position System）定位組件等手段獲得自身的位置信息，發(fā)送包含位置參照信息的信標(biāo)報(bào)文，供其他的節(jié)點(diǎn)使用；而普通節(jié)點(diǎn)自身沒有GPS定位信息，只能通過信標(biāo)節(jié)點(diǎn)的位置信息通過定位算法。

在無線傳感器網(wǎng)絡(luò)中，根據(jù)蟲洞攻擊所處的情況不同，蟲洞攻擊的分布主要有以下3種情況[2]：①信標(biāo)節(jié)點(diǎn)與信標(biāo)節(jié)點(diǎn)之間；②信標(biāo)節(jié)點(diǎn)與普通節(jié)點(diǎn)之間；③普通節(jié)點(diǎn)與普通節(jié)點(diǎn)之間。通過分析，第二種情況和第三種情況可以采用相同的方式進(jìn)行處理，因而在本文中，主要對于信標(biāo)節(jié)點(diǎn)和信標(biāo)節(jié)點(diǎn)，信標(biāo)節(jié)點(diǎn)和普通節(jié)點(diǎn)的蟲洞攻擊進(jìn)行討論。

蟲洞攻擊在如下的環(huán)境中討論，所有的信標(biāo)節(jié)點(diǎn)和普通節(jié)點(diǎn)都是可信的，不會(huì)被惡意節(jié)點(diǎn)捕獲。WARSL的定位機(jī)制是通過檢測傳感器節(jié)點(diǎn)的跳數(shù)值是否符合三角形法則或者最低跳數(shù)值法則來檢測傳感器網(wǎng)絡(luò)中是否存在蟲洞攻擊，在有攻擊的局部網(wǎng)絡(luò)中，矯正不合理的跳數(shù)值。定位機(jī)制的運(yùn)用在信標(biāo)節(jié)點(diǎn)之間和信標(biāo)節(jié)點(diǎn)與普通節(jié)點(diǎn)之間的原理不一樣，下面將會(huì)對其做詳細(xì)的解釋。首先我將引入以下幾個(gè)參數(shù)以便之后的說明。

d（A，B）:節(jié)點(diǎn) A 和節(jié)點(diǎn) B之間的距離；

r:傳感器節(jié)點(diǎn)信息傳播的半徑；

Hopleast（A，B）:節(jié)點(diǎn) A 和節(jié)點(diǎn) B之間的最小跳數(shù)值

Hop（A，B）：節(jié)點(diǎn) A和節(jié)點(diǎn) B之間的跳數(shù)值

Hopopt（A，B）節(jié)點(diǎn)A和節(jié)點(diǎn) B之間的最優(yōu)值

如圖2所示，在安全的傳感器網(wǎng)絡(luò)中，所有的傳感器節(jié)點(diǎn)在一條直線節(jié)點(diǎn)之間的跳數(shù)值是最小。任何一對鄰居節(jié)點(diǎn)的距離等于節(jié)點(diǎn)傳播的半徑[3]。兩個(gè)節(jié)點(diǎn)間的最小跳數(shù)值按照公式（1）計(jì)算。

圖2 節(jié)點(diǎn)間最小跳數(shù)值Fig.2 Minimum hop count between nodes

規(guī)則1蟲洞攻擊在信標(biāo)節(jié)點(diǎn)與信標(biāo)節(jié)點(diǎn)之間

如圖3所示，A1和A2是兩個(gè)惡意節(jié)點(diǎn)，A1和A2之間形成一條蟲洞鏈路，B1和B2是兩個(gè)信標(biāo)節(jié)點(diǎn)。在正常情況下，B1和B2之間的跳數(shù)值為7，在有蟲洞攻擊的情況下，B1和B2之間的跳數(shù)值為3。由于信標(biāo)節(jié)點(diǎn)可以計(jì)算出自己的位置，因而如果 Hop（B1，B2）＜Hopleast（B1，B2），則說明信標(biāo)節(jié)點(diǎn) B1和信標(biāo)節(jié)點(diǎn)B2之間存在著蟲洞攻擊。則用最優(yōu)值來替換階段出來的值。 Hop（B1，B2）=Hopopt（A，B）。 在這種情況下，Hopopt（A，B）的值根據(jù)公式（2）來計(jì)算。 例如，假如 Hop（B1，B2）=3，Hopleast（B1，B2）=5，Hopopt（A，B）=6，由于 3＜5，則 Hop（B1，B2）=6。

規(guī)則2蟲洞攻擊在信標(biāo)節(jié)點(diǎn)與普通節(jié)點(diǎn)之間

如圖4所示，A1和A2是兩個(gè)惡意節(jié)點(diǎn)，A1和A2之間形成一條蟲洞鏈路，B1和B2是兩個(gè)信標(biāo)節(jié)點(diǎn)，S1是需要定位的普通節(jié)點(diǎn)。在正常情況下，S1在定位過程中，獲取B1廣播過來的位置信息，計(jì)算出其與B1之間的跳數(shù)值為5；在蟲洞攻擊的情況下，S1與B1之間的跳數(shù)值為3。在這種情況下，如果要檢測出是否存在蟲洞攻擊，需要借助另外一個(gè)信標(biāo)節(jié)點(diǎn)，如圖中的信標(biāo)節(jié)點(diǎn)B2，而且B2和S1之間沒有蟲洞攻擊，d（B1，S1）和 d（S1，B2）和 d（B1，B2）之間構(gòu)成一個(gè)三角形，要滿足三角形三邊的規(guī)則。即

如果不同時(shí)滿足上面的關(guān)系式，則說明這條鏈路中存在著蟲洞攻擊。 在這種情況下，Hopopt（B1，S1）的值根據(jù)公式（3）來計(jì)算，Hop（B1，S1）=Hopopt（B1，S1）。 例如：Hop（B1，B2）=2，Hop（B2，S1）=5，Hop（B1，S1）=3。 則 Hop（B1，S1）=Hopopt（B1，S1）=10。

圖4 蟲洞攻擊在信標(biāo)節(jié)點(diǎn)和普通節(jié)點(diǎn)之間Fig.4 Wormhole attack between beacon node and common node

因而，如果將WARSL定位機(jī)制應(yīng)用于DV-Hop定位算法中，其步驟如下[4]：

1）信標(biāo)節(jié)點(diǎn)將自己的位置信息以分組的形式廣播出去，信息的格式為 {idi，（xi，yi），Hopi}， 其中 idi表示信標(biāo)節(jié)點(diǎn)的編號(hào)，（xi，yi）表示信標(biāo)節(jié)點(diǎn)的坐標(biāo)值， Hopi表示跳數(shù)值，初始值為0。

2）節(jié)點(diǎn)獲得信標(biāo)節(jié)點(diǎn)廣播的信息，首先判斷是否來自于一個(gè)信標(biāo)節(jié)點(diǎn)，如果來自于同一個(gè)信標(biāo)節(jié)點(diǎn)，則與已經(jīng)保存的跳數(shù)值進(jìn)行比較，保存最小的跳數(shù)值；如果不是來自與同一個(gè)信標(biāo)節(jié)點(diǎn)，則保存跳數(shù)值。

3）如果該節(jié)點(diǎn)是信標(biāo)節(jié)點(diǎn)，那么根據(jù)規(guī)則1，兩個(gè)信標(biāo)節(jié)點(diǎn)的之間的跳數(shù)值是否小于信標(biāo)節(jié)點(diǎn)之間的最小值，如果信標(biāo)節(jié)點(diǎn)之間的跳數(shù)值小于最小值，那么這兩個(gè)信標(biāo)之間存在著蟲洞攻擊，使用公式（2）替換測量信標(biāo)節(jié)點(diǎn)的跳數(shù)值；反之，信標(biāo)節(jié)點(diǎn)之間的跳數(shù)值是可信的。如果該節(jié)點(diǎn)是普通節(jié)點(diǎn)，那么根據(jù)規(guī)則2，判斷節(jié)點(diǎn)間是否滿足三角形法則，如果不滿足的情況下，則說明信標(biāo)節(jié)點(diǎn)與普通節(jié)點(diǎn)之間存在著蟲洞攻擊，使用公式（3）替換測量出來的跳數(shù)值。反之，信標(biāo)節(jié)點(diǎn)與普通節(jié)點(diǎn)之間的跳數(shù)值是可信的。

4）節(jié)點(diǎn)保存可信的信標(biāo)節(jié)點(diǎn)的跳數(shù)值，并將跳數(shù)值加1廣播出去。

5）當(dāng)泛洪過程結(jié)束后，每個(gè)信標(biāo)節(jié)點(diǎn)根據(jù)公式（1）來計(jì)算自己的平均每跳距離。

6）每個(gè)信標(biāo)將自己的平均每跳距離的消息廣播到網(wǎng)絡(luò)中，消息的格式{idi，Hopdi}，idi表示信標(biāo)節(jié)點(diǎn)的編號(hào)，Hopdi表示信標(biāo)節(jié)點(diǎn)的平均每跳距離。

7）未知節(jié)點(diǎn)接收到平均每跳距離后，根據(jù)自己數(shù)據(jù)表里記錄的信標(biāo)節(jié)點(diǎn)的跳數(shù)，找到一個(gè)離自身最近的信標(biāo)節(jié)點(diǎn)，將該信標(biāo)節(jié)點(diǎn)的平均每跳距離作為整個(gè)傳感器網(wǎng)絡(luò)的平均每跳距離。根據(jù)d=Hop×Hopd，計(jì)算未知節(jié)點(diǎn)與每個(gè)信標(biāo)節(jié)點(diǎn)的距離。

8）當(dāng)未知節(jié)點(diǎn)得到3個(gè)或者3個(gè)以上不同信標(biāo)的距離后，可以使用三邊測量法或極大似然估計(jì)法計(jì)算自己的位置。

為了更好的說明整個(gè)算法的流程，圖5給出了算法的流程圖。

圖5 WARSL算法流程圖Fig.5 Flowchart of algorithm WARSL

3 實(shí)驗(yàn)結(jié)果

對于定位算法而言，衡量其性能的指標(biāo)主要包括定位誤差、平均定位誤差、定位精度、計(jì)算量、通信量等[5]，本實(shí)驗(yàn)的主要的目的是驗(yàn)證在蟲洞攻擊存在的情況WARSL定位算法能夠提高定位的準(zhǔn)確性，因而在本實(shí)驗(yàn)中采用平均定位誤差來衡量WARSL定位算法的性能。平均定位誤差的計(jì)算方法如下：

式中：（xi，yi）表示未知節(jié)點(diǎn)i的定位坐標(biāo)；（x′i，y′i）表示未知節(jié)點(diǎn)i的真實(shí)坐標(biāo)，N表示未知節(jié)點(diǎn)的個(gè)數(shù)。

實(shí)驗(yàn)環(huán)境假設(shè)[6]：100個(gè)節(jié)點(diǎn)隨機(jī)的部署在300 m×400 m的方形區(qū)域中，節(jié)點(diǎn)的通信半徑為30 m，蟲洞鏈路數(shù)為10。平均定位誤差隨著網(wǎng)絡(luò)中信標(biāo)節(jié)點(diǎn)的比例關(guān)系如圖6所示。

圖6 平均定位誤差隨著信標(biāo)節(jié)點(diǎn)的比例的變化Fig.6 Average position error with the change of the proportion of beacon nodes

從圖6可以看出，當(dāng)信標(biāo)節(jié)點(diǎn)數(shù)量的在網(wǎng)絡(luò)所占的比例較小時(shí)，在有蟲洞攻擊的環(huán)境下，WARSL定位算法能夠較大的提高節(jié)點(diǎn)定位的準(zhǔn)確度，當(dāng)信標(biāo)節(jié)點(diǎn)的數(shù)量比例達(dá)到20%之后，WARSL定位算法與DV-HOP定位算法的定位的準(zhǔn)確度相差不大。但是整體而言，WARSL定位算法還是更加可靠。

4 結(jié)束語

文中針對DV-Hop定位算法，引入了一種新的檢測機(jī)制，此機(jī)制通過一些檢驗(yàn)規(guī)則能夠很好的檢測蟲洞攻擊，從而增強(qiáng)了定位結(jié)果的準(zhǔn)確性。本方法不需要借助昂貴的硬件輔助，僅通過簡單的計(jì)算來抵制蟲洞攻擊。

[1]周明偉，劉淵.WSNs中 DV-hop定位算法的安全增強(qiáng)研究[J].計(jì)算機(jī)工程與應(yīng)用.

ZHOU Ming-wei，LIU Yuan.The security enhanced research of DV-hop localization algorithm in WSNs[J].Computer engineering and applications.

[2]Yanchao Niu，D.G.S.G.， A Robust Localization in Wireless Sensor Networks against Wormhole Attack [J].Journal of networks，2012（1）:187-194.

[3]Honglong Chen，W.L.A.Z.， Conflicting-Set-Based Wormhole Attack Resistant Localization inWireless Sensor Networks[J].Ubiquitous Intelligence and Computing-6th International Conference，2009：296-309.

[4]Khan Z A，M.H.I.， Wormhole Attack A new detection technique[C]//2012 International Conference on Emerging Technologies，2012：276-281.

[5]Nabila Labraoui，M.G.A.M.， Secure DV-Hop localization scheme against wormhole in wireless sensor networks[J].EuropeanTransactionsonTelecommunications，2011：303-316.

[6]劉彩霞，黃廷磊.WSN中抵御蟲洞攻擊的改進(jìn)的DV-Hop算法研究[J].傳感技術(shù)學(xué)報(bào)，2011（10）:1473-1478.

LIU Cai-xi，HUANG Ting-lei， A improvemented against wormhole attacks in WSNs[J].Journal of sensing technology，2011（10）:1473-1478.