無線Mesh網絡中基于復權馬爾可夫鏈的安全路由協議

馮媛媛 易 欣 趙 麗

1(四川工程職業技術學院電氣信息工程系 四川 德陽 618000)2(山西大學軟件學院 山西 太原 030013)

0 引 言

機會路由OR(Opportunistic Routing)[1]算法是一組單播或組播的路由算法，它可以確保無線網絡中端到端之間分組路由的可靠性和有效性。與傳統的路由方案如DSV、AODV、OLSR等[2]不同，OR算法在路由過程的每一跳中，僅選擇一個節點作為下一跳的實際轉發器。同時向其傳輸數據包目的地和相鄰節點子集，作為潛在的下一跳轉發器。OR算法中的路由操作分為兩個階段：候選點選擇和候選點協調。其中，候選點選擇方法近年來受到研究者的高度重視。在候選選擇過程中使用不同的度量和參數，例如節點之間的通信鏈路的質量、節點的地理位置以及潛在候選點的可信度等因素。

科研人員對OR中候選節點的選擇和協調方法進行了大量研究[3-4]。例如，極端機會路由(ECOR)[5]是一種基于OR算法的路由算法，這種路由使用預期傳輸計數(ETX)作為候選選擇的度量。簡單機會自適應路由算法(SOAR)[6]同樣使用ETX指標進行候選選擇，源節點和目標節點之間的最短路徑使用ETX度量來計算，然后通過添加接近最短路徑的節點來選擇候選集合。最低成本機會路由(LCOR)[7]是另一種OR算法，這種路由使用預期任意路徑傳輸(EAX)度量來選擇候選節點，該算法能夠通過對網絡拓撲圖進行分析，進而發現最佳候選集合。與LCOR類似，文獻[8]提出一種代表最小傳輸選擇的MTS算法，同樣使用EAX度量來進行候選點的選擇。與這些只考慮候選節點之間鏈路質量的算法不同，有一類算法考慮了節點的地理位置：文獻[9]提出的DPOR算法通過考慮每個候選點到目的地的距離來選擇候選集；在其改進版本DPOR[10]算法中，節點之間的鏈路傳遞概率和距離組合用于定義候選選擇的度量；文獻[11]和DPOR算法類似，也使用鏈路質量和節點的地理位置來精確地選擇其下一跳轉發器。另外，還有一些考慮其他因素的算法。例如，文獻[12]提出了一種傳輸延遲有效的OR算法，提高了能量效率；文獻[13]在路由數據包傳達至目的地的過程中，考慮了服務質量的計算。

目前，大多數研究主要關注可靠性方面，也就是說這些OR算法都遵循一個假設，即網絡中的所有節點都是良性的協作節點。然而，在實際情況下，網絡中可能會出現惡意節點，對無線網絡中的通信性能造成破壞性影響。例如，拒絕服務(DoS)攻擊[4]，其中當惡意節點作為其他節點的下一跳轉發器時，這些節點傾向于丟棄所有收到的分組，并降低網絡性能。

目前，OR算法中惡意節點的影響尚未引起足夠的重視。因此，本文使用復權馬爾可夫鏈構建一種基于OR的無線Mesh網絡的新模型，用于檢測系統中存在的惡意節點，防止其轉發數據包。其主要創新點在于：

(1) 采用了一種最新的馬爾科夫鏈技術，即復權馬爾可夫鏈來進行節點預測；

(2) 通過復權馬爾可夫鏈將機會路由中的惡意攻擊方式進行建模，通過狀態概率的計算來預測惡意節點。

1 路由中的安全問題

除可靠性要求之外，對于安全性的考慮也非常重要。在存在惡意節點的情況下，即使是最可靠的路由算法，在網絡中也不能有效的運行。研究表明，采用密碼方案是針對惡意節點的一種有效防御機制，它可以保證節點之間數據傳輸的安全性和完整性。但是，當涉及到逐跳路由中的節點協作時，就可能引入一系列不當行為。例如，一些惡意節點可能會在網絡中注入虛假信息，或者阻止節點間的協作。

路由攻擊包括黑洞攻擊、灰洞攻擊和蠕蟲攻擊。在黑洞攻擊(即DoS攻擊)中，黑洞節點會傳輸錯誤的路由信息，試圖說服網絡中的其他節點選擇它們作為路由中的下一跳節點，從而試圖吸收盡可能多的數據包，并將它們丟棄。灰洞攻擊是黑洞攻擊的一個特殊變體。灰洞攻擊中，節點傾向于有選擇地丟棄一些接收的數據包并轉發其他數據包。在蠕蟲攻擊中，位于不同地區的兩個惡意節點相互串連，攻擊網絡。一旦惡意節點收到一個數據包，就通過一個私有信道把這個包發送到另一個區域，其他惡意節點將在其他區域重發數據包。

為了防御路由攻擊，科研人員提出了不同的方法。例如，為了識別網絡中不合作的節點，并相應地將其隔離，提出信任和信譽管理協議。文獻[14]和文獻[15]提出了利用無線網絡中節點之間的直接、間接交互構建一些信任和信譽模型。文獻[16]則引入機會網絡的信任計算方法，接收方節點通過發送正反饋消息(PFM)來確認機會網絡中另一個節點的合作性質。

2 復權馬爾可夫鏈

馬爾可夫鏈[17]可以根據事件在以前某個時段的狀態轉移概率為基礎，預測該事件將來的狀態變化概率，它主要包括時間參數集T={0,1,2,…}和狀態參數集E={0,1,2,…}。而在實際應用環境中，常用的是齊次馬爾可夫鏈[18]。假設參數u,k∈T，則：

Pij(u;k)∈E

(1)

式中：Pij(u;k)表示在u時刻，一個隨機事件的狀態i在通過k步狀態轉移計算后變成狀態j的概率，且該事件的狀態i發生在u時刻。

齊次馬爾可夫鏈在使用過程中將各種狀態轉移步長看作是同一個值，并不能得到準確的狀態預測結果。而復權馬爾可夫鏈對各個步長區別對待，引入權重的概念，將各個狀態的預測概率當作權重值，再根據對應的狀態均值，實現數值預測。復權馬爾可夫鏈的具體步驟如下：

(1) 創建對象序列的狀態分級標準，根據聚類法、頻率曲線法等劃分不同的狀態，并確立對象序列的所屬狀態。

(2) 對于指標值序列x1,x2,…,xn，當其狀態由i變為狀態j時，經歷的頻數用fij表示，且i,j∈E。然后計算出各個狀態的轉移規律，從而得出步長的狀態轉移頻數矩陣。

(3) 轉移概率Pij(i,j∈E)可以定義為第i行第j列的元素fij與各行總和的比值，如下式所示：

(2)

式中：m表示指標值序列中可能呈現的狀態數量，m∈E。

(4) 邊際概率P.j可以定義為fij的第j列之和與各行各列的總和的比值，如下式所示：

(3)

統計量X2在序列長度足夠大時可表示為：

(4)

(5) 利用式(5)計算步長的自相關系數：

(5)

(6) 根據式(6)將各步長的自相關系數規范化：

(6)

式中：wk表示規范化后的自相關系數，c表示最大步長。

(8) 利用加權算法求和同一狀態的不同預測概率，可得該狀態的預測概率：

(7)

(8)

3 路由中惡意攻擊的馬爾可夫鏈模型

OR方法中的路由操作可以使用復權馬爾可夫鏈進行精確建模，復權馬爾可夫鏈中的每個狀態都使用一個元組來定義，該元組包含節點標識符和特定節點中發生的重傳次數。文獻[19]提出的模型是評估網狀網絡OR性能的一般模型，但這種模型不適用于包含惡意節點的網絡。在很多情況下，由于硬件或軟件故障等原因，節點并不能像預期的那樣參與路由操作。本文提出了一種修改的OR算法模型，該模型在網絡中含有惡意節點的情況下使用復權馬爾可夫鏈。表1為本文所使用的符號和含義。

假設網絡中存在M個惡意節點，它們都可能執行對應的不合作行為。其中黑洞節點收到數據包后會將其惡意丟棄，但其卻宣稱轉發成功，并向所有其他候選點發送確認消息，指示它已經轉發了分組數據。因此，前一跳和所有其他候選點需要阻止這樣的分組轉發，防止數據包永久丟失。

構建一個N=5、K=3、M=1和C=2的線性拓撲結構。在這個模型中，假設所有節點之間的距離相等，并且一個節點(ID=2)是唯一的惡意黑洞節點，即惡意節點可以收到所有數據包。為此，這樣的節點可以模擬為復權馬爾可夫鏈中的吸收狀態。更具體地說，一旦系統達到吸收狀態，它將保持在該狀態，并不再發生狀態之間的轉換。如圖1所示，由于ID=2的節點會丟棄對象，因此一旦系統達到狀態(2,0)，將不能把分組轉發到目的地，也不會重傳。考慮到這一點，以及M個惡意節點的存在，可以計算系統中的狀態數量S：

S=(N-M-1)×(K+1)+M+2

(9)

吸收狀態的數量將等于M+2，對應于M個惡意節點，以及一個失敗和一個成功狀態。此外，所提出的模型中瞬態的數量為(N-M-1)×(K+1)。一旦復權馬爾可夫鏈中的所有狀態都是已知的，就有可能創建一個包含狀態間轉移概率的隨機矩陣。使用該矩陣，可以提取所需的網絡參數，例如數據包傳輸率、丟包率等。

圖1 存在黑洞節點時的線性拓撲模型

圖2 轉移概率矩陣

當網絡中惡意節點的數量較多，特定節點的所有候選都可能成為惡意節點。在這種情況下，由發送節點發送的所有數據包將被候選節點惡意丟棄，即在復權馬爾可夫鏈中數據包成功到達目標節點的可能性為零，即源節點和目的節點之間不存在路徑。

4 基于馬爾可夫鏈模型的丟包率預測

4.1 計算轉移概率矩陣

(10)

(2)達到與其他候選對象相對應的狀態(除了最高優先級候選節點)：在這種情況下，從狀態(i,j)轉換到狀態(i′,j′)時，i′不是節點i的最高優先級候選。此時狀態的轉換概率可以用下式表示：

(3) 達到重傳或失敗相對應的狀態：如果在傳輸過程中沒有候選點接收到數據包，發送節點傾向于執行重傳，最多發生K次重傳。在這之后，如果沒有候選點接收到數據包，則從網絡中永久丟棄該節點。計算重傳或包傳輸失敗的概率用下式表示：

(12)

4.2 丟包率的計算

通過計算每個與惡意節點相關的從初始狀態到達吸收狀態的概率，然后將它們組合起來得到丟包率。通過丟包率的預測來判別一個節點是否為惡意節點。

顯然，OR算法中的初始狀態與產生數據包的源節點有關。式(13)顯示了OR的初始狀態。從初始狀態V經過h次轉換之后到達任意狀態的概率可以使用ph來表示，初始狀態表示為：

V=[1 0 … 0]

(13)

本文假設網絡中只有一個節點作為源節點，即ID=0節點。這個節點就有必要計算到達與惡意節點相關的每個吸收狀態的概率，矩陣V×Ph中的元素(0，BHi)表示惡意節點BHi接收且丟棄數據包的概率。那么，所有惡意節點丟棄的數據包的總體比率如式(14)所示,其中M是惡意節點的數量。由此可以確定達到成功或失敗狀態的概率，這些值分別代表到達目的地的概率或分組失敗的概率。

(14)

5 仿真分析

利用NS 2.35仿真軟件構建仿真環境，分別將本文提出的模型與經典的三種OR算法(MTS算法[8]、POR算法[9]和DPOR算法[10])進行比較。其中，MTS使用節點之間的鏈路傳遞概率來選擇候選，其證明了可以根據期望的傳輸次數(ETX)選擇最佳的候選集合。POR算法則考慮了候選節點的地理位置，為每個節點選擇候選集合。DPOR中候選點的選擇不僅考慮了它們的位置，還考慮了鏈接的質量。

在仿真過程中引入了黑洞攻擊，一旦惡意節點接收到分組，就會通知所有其他候選點(以及前一跳節點)它已經接收并轉發該分組。其他候選點和前一跳節點會假定該分組已經發送，并且讓這些節點放棄發送或重發分組。

5.1 仿真設置

本文使用陰影衰落傳播模型進行節點之間的無線通信，參數如表2所示。對于單個傳輸的分組，使用下式計算信號接收到的功率：

(15)

式中：d表示傳播距離，Pr(d)表示距離d處的接收功率，用分貝表示，即單位為dBW，Pt表示發射功率，Gt表示發射天線的增益，Gr表示接收天線的增益，λ是信號波長，β是系統損耗，XdB代表均值為零、標準偏差為σdB的高斯隨機變量。當發送一個數據包時，如果接收節點的接收功率大于或等于一個閾值，比如RXThresh，節點可以成功接收數據包。因此，可以使用文獻[10]中的方式計算在距離d處節點x和y之間的傳遞概率，如下式所示：

linkprob(x,y)=Probability(Pr(d)≥10log10(RXThresh))

(16)

表3列出了仿真研究中使用的所有參數。為深入研究各種參數的影響，選擇三個不同的參數進行實驗，包括惡意節點數量、節點密度和最大候選數量。所有參數都設置為默認值，然后每次更改一個參數，計算丟包率、數據包傳輸率和跳數。

表3 仿真參數

5.2 結果分析

5.2.1惡意節點數量對性能的影響

本節介紹惡意節點數量對網絡丟包率和傳輸率性能的影響，其中惡意節點的數量從0變為15。由以下仿真結果可知，惡意節點會對網絡性能參數產生顯著的破壞性影響。

(1) 丟包率。圖3顯示了惡意節點數量對丟包率的影響。丟包率表示為惡意節點丟棄的數據包總數與生成的數據包總數的比例。顯然，隨著惡意節點數量的增加，丟包率也會隨之上升。這是因為當網絡中存在更多的惡意節點時，算法中選擇這些節點作為候選點的概率增加，因此這些惡意節點有更多機會通過捕獲數據分組來攻擊網絡，并相應地丟棄數據包。

在現有的三種算法中，POR算法有最低的丟包率。POR算法的重點是最小化每個數據包的跳數，這么做降低了惡意節點接收數據包的概率。而在MTS算法中，由于整體傳輸數據包較少，惡意節點捕獲數據包的可能性也較小，其丟包率相應較低。而本文提出的算法中丟包率最低，這是因為本文通過復權馬爾可夫鏈來檢測惡意節點，能夠有效避開惡意節點轉發數據，但是當惡意節點數量較多時，會出現不得不通過其轉發數據的情況。

圖3 惡意節點數量對丟包率的影響

(2) 傳輸率。圖4顯示了惡意節點數量對數據包傳輸率的影響。傳輸率是目標節點接收數據包總數與生成的數據包總數的比例。由圖4可知，增加惡意節點的數量將導致所有算法的傳輸率下降，因為惡意節點數量的增加將導致捕獲和丟棄的數據包數量增加，這顯然會導致傳輸率較低。

在現有的三種算法中，POR算法的傳輸率受惡意節點的影響較大，這是因為該算法能夠減少在源和目的地之間接收分組的潛在跳數；MTS算法具有較好的傳輸率性能。本文算法在傳輸率方面同樣獲得了最佳的性能。

圖4 惡意節點數量對數據包傳輸率的影響

5.2.2節點密度對性能的影響

本小節研究節點密度變化對網絡性能的影響。對于這種評估，網絡尺寸將從300×300平方米變為1 000×1 000平方米，而惡意節點的數量都設置為6個節點。

(1) 丟包率。圖5顯示了網絡大小變化對丟包率的影響。通過擴大網絡規模，各種算法的丟包率都是上升到一定水平后開始下降。因為對于較小的網絡，例如300×300平方米，源與目的地之間的路徑更短，分組數據需要較少的跳數就能到達目的地。這降低了惡意節點接收數據包的可能性。相比之下，通過擴大網絡大小，在路由數據包傳遞到目的地的過程中涉及到更多的節點，這為惡意節點捕獲更多的數據包提供了更多的機會。但是，當網絡規模過大時，比如1 000×1 000平方米，節點之間的平均距離也增大，因此，由于無線信道的阻塞，網絡中會有大量的數據包丟失。雖然惡意節點仍然可能被其他節點選為潛在的候選對象，但是只有較少的數據包能夠到達目的地。其中，POR算法性能較好，DPOR算法性能最差，本文算法同樣獲得了最佳性能。

圖5 網絡大小對丟包率的影響

(2) 傳輸率。圖6顯示了網絡大小變化對傳輸率的影響。增加網絡規模時，各種算法的傳輸率都逐漸下降。其原因是惡意節點會捕獲和丟棄一些接收到的數據包，并且隨著網絡規模的擴大，節點之間的距離也越來越大，數據包丟失的可能性也越來越大，因此，更少的數據包將有機會成功傳輸到目的地。其中，MTS算法的數據傳輸性能較佳，DPOR算法的數據傳輸性能最差，POR算法的數據傳輸性能整體優于DPOR算法，這是由于POR算法將嘗試減少源和目的地之間的跳數，這就使得接收到惡意節點的數據包的可能性減小，傳輸比率提高。本文算法獲得了與MTS算法相似的性能。

圖6 網絡大小對數據包傳輸率的影響

5.2.3最大候選節點數量對性能的影響

在這種情況下，候選的最大數目從1個節點變為6個節點，其他參數則設置為其默認值。

(1) 丟包率。圖7顯示了最大候選節點數量對丟包率的影響。當候選點數目超過2個時，DPOR算法的丟包率變化并不明顯，而POR算法的丟包率呈現明顯上升的趨勢，這是因為少數候選點由于傳播模型中的分組丟失和能量損失而導致丟失大量分組。事實上，增加候選集中節點的數量會減少數據包丟失的機會，同時增加選擇更多惡意候選的可能性。當候選點數量從1變化到3時，MTS算法的丟包率呈現略微下降的趨勢，當候選節點數量大于3時，丟包率幾乎不變。與DPOR算法相比，MTS算法中惡意節點可以捕獲更少的數據包。本文算法中，能夠有效識別惡意節點，所以在候選節點數量變化時，丟包率保持在較低的水平。

圖7 最大候選節點數量對丟包率的影響

(2) 傳輸率。圖8為最大候選節點數量對數據包傳輸率的影響。在POR算法中，隨著候選數目的增加，分組丟失的概率減小，而算法嘗試通過選擇離目的地最近的節點來減少跳數。因此，將數據包發送到目的地的可靠性增加，相應的數據包傳輸率也增加。當候選集的最大數目少于3個節點時，POR算法表現出較差的傳輸率。DPOR算法將地理信息與節點之間的鏈路傳遞概率結合起來，具有較好的傳輸率。當候選點數量從1變化到3時，POR和DPOR算法的傳輸率逐漸增加，直到候選點的數量大于3個時，傳輸率趨于穩定。總的來說，MTS算法在傳輸率方面的性能較好。由于本文算法受候選節點數量的影響較小，所以傳輸率也保持在一個較高的水平。

圖8 最大候選節點數量對數據包傳輸率的影響

6 結 語

本文研究了無線網絡中惡意節點對機會路由算法的影響，利用復權馬爾可夫鏈設計并實現了一個新的分析模型來演示惡意節點的存在。另外，為了檢測惡意節點，引入了一種計算丟包率的方法。在設計了機會路由算法后，將黑洞攻擊作為惡意行為的一個例子，設計并實施了一套綜合的性能評估方案，對本文算法和三種經典的機會路由算法進行了仿真分析。結果表明，本文提出的模型能夠有效檢測惡意節點，提高網絡性能。