無線傳感器網絡中基于相鄰節點協作的惡意節點溯源定位算法

張迪

（赤峰學院物理與智能制造工程學院，內蒙古 赤峰 024000）

無線傳感器網絡是一種由基站（sink）及大量的傳感器節點組成的分布式網絡，多部署在無人值守的環境中，因此極易受到物理破壞及人為的攻擊。與傳統網絡相比，傳感器網絡節點結構較為簡單且容易被敵方俘獲，可以通過被捕獲節點發動如泛洪攻擊等方式的惡意攻擊，使得網絡資源快速耗盡。因此，設計一種高效的惡意節點溯源定位算法，成為當前無線傳感器網絡研究熱點之一。

Savage[1]等人最早提出具體的標記算法方案。Ye[2]等人提出了一種基于概率包標記的節點溯源方案(Probabilistic Nested Marking,PNM)，該方案中，傳感器網絡節點對接收到的數據包作概率性標記，隨著被標記的次數增加，致使數據包的首部變大，因此需要占用大量的傳感器存儲資源。Yang[3]等人提出一種基本標記方法(Basic Probabilistic Packet Marking,BPPM)，該方法是對PNM方法的改進，節點概率性標記數據包包頭的標記區域限定為四個，為了能夠重構溯源路徑，在單個數據包標記信息有限的情況下，只能收集更多的數據包，該方法雖然標記過程簡單、復雜度低，但算法收斂性差，溯源定位效率較低。此外，上述方法在網絡拓撲發生變化，如因能量均衡改變簇頭節點或惡意節點主動更改路由時，則需要重新定位惡意節點并重新收集更多數量的數據包，使得對惡意節點的溯源定位效率大大降低，變得更加困難[4]。

為解決上述問題，本文提出了一種基于相鄰節點協作的惡意節點溯源定位算法。本算法基于數據包日志，在通信過程中，收發節點及其相鄰節點將建立數據包日志并記錄數據包內的特征參數。當惡意節點發動攻擊時，sink節點通過收集途中各節點及其相鄰節點數據日志中的特征參數重構數據包傳輸路徑，進而定位至攻擊節點。與傳統的BPPM算法作對比分析，結果表明本算法對惡意節點具有更高的溯源定位效率且能夠適應無線傳感器網絡動態路由變化等特點。

1 基于相鄰節點協作的惡意節點溯源定位算法

1.1 系統模型與假設

假設一個傳感器網絡由基站（sink節點）及若干傳感器節點構成，基站與外網相連，安全可靠且資源不受限制[5]。傳感器節點隨機部署，網絡拓撲呈樹狀結構且可以動態變化，當傳感器節點感知到某事件發生時，將通過簇頭節點收集感知信息（如事件的位置信息等），簇頭節點將周圍若干節點發送過來的感知信息進行數據融合處理，再將數據融合后的數據包發送給下一跳節點，經過若干節點轉發后，最終達到基站。與目前許多安全問題研究假設相同，假設傳感器節點抗俘獲能力較弱，攻擊者可以通過被捕獲傳感器節點獲取節點內所有的信息。本算法借鑒了與LEAP[6]協議類似的多重密鑰機制，以適應節點間、簇間、節點與基站之間多種通信形式的安全需要。

1.2 符號

文中涉及的符號含義如下：

IDA：傳感器節點A的標識符，即節點的MAC地址；

KA：個體密鑰，節點A的個體密鑰，該密鑰與基站共享；

KAn：廣播認證密鑰，節點A的單項秘鑰鏈中用于廣播認證的第n個秘鑰；

(Data)K：用秘鑰K來加密數據Data；

MAC{Data}K：數據Data使用秘鑰K計算出來的消息認證碼；

NA：節點A的相鄰節點列表。

1.3 算法描述

下面將對初始化階段及惡意節點溯源定位算法進行描述。

（1）網絡部署及初始化階段。本階段主要完成節點部署、節點發現、建立路由以及秘鑰分配等任務，假設在網絡部署及初始化階段內，系統不會受到攻擊。在節點部署前，在每一個節點（以節點A為例）內預置一個唯一的節點標識符IDA和一個與基站共享的通信秘鑰KA。當節點部署完成后，借鑒μTESLA[7]協議生成應對一跳范圍相鄰節點廣播通信認證的單向秘鑰鏈（KA1,KA2,KA3,……,KAn），然后廣播節點標識符IDA、廣播通信認證秘鑰KA1等信息來發現并建立節點之間的鄰居關系，相鄰節點P收到節點A的廣播信息后將IDA寫入其鄰居節點列表NP中，隨后節點之間完成其他秘鑰的分配工作。

（2）感知信息階段。本階段傳感器節點主要依據基站下達任務感知部署環境相關信息，每一個節點需要在緩沖區內建立數據包日志，用來記錄接收到的有關感知信息的數據包的相關參數，數據包格式如圖1所示。

圖1 感知信息數據包格式

其中IDstr表示發起數據包的源節點ID；IDlast表示上一跳轉發數據包節點的ID；IDend表示數據包目的節點的ID；Seq表示數據包源節點設置的序列號，其值沒隨節點轉發而不斷增大；Klast-i表示上一跳轉發數據包IDlast節點的單向秘鑰鏈驗證秘鑰；IDnext表示轉發數據包的下一跳節點ID；Data表示感知信息數據；MAC表示數據包經過秘鑰計算出來的消息認證碼。例如假設在部署區域內發生某一事件，該區域簇頭節點在匯聚來自周圍節點的感知信息后，通過數據融合處理后生成感知信息數據包M，經過節點A并以廣播形式發送給下一跳節點B，數據包M的格式如下：

接收節點在收到感知信息數據包后，先利用單向鏈秘鑰KAi驗證數據包的合法性，若驗證數據包為合法數據包，則接收節點根據數據包內的相關信息，在緩沖區內建立數據包日志，日志信息將以結構體數組node[i]的形式按照FIFO方式記錄并儲存，其日志格式如下：

struct LogF{IDstr;Seq;sum;IDlast;IDnext}node[i];

其中Seq和sum分別表示在一個網絡拓撲更新周期內節點發送感知信息數據包的序列號及發送數據包的條目數；若數據包核驗為非法數據包，則直接丟棄該數據包。

（3）數據包的轉發及日志信息的建立與更新。驗證數據包M合法后，接收節點需要判斷自己是否需要轉發該數據包，檢查數據包頭中的IDnext是否與接收節點ID一致，如果一致則該節點需要將該數據包進行轉發并記錄數據包日志；若檢查數據包頭中的IDnext與接收節點ID不一致，則接收節點需要查找其相鄰節點列表，檢查接收節點是否同時是數據包M中上一跳節點IDlast和下一跳節點IDnext共同鄰居節點，如果是共同鄰居節點，則需要記錄該路徑數據包日志，否則丟棄該數據包。算法描述如下：

1）假設節點B收到上一跳節點A發出的感知信息數據包M，若有IDnext==IDB，則執行數據轉發過程如下：

步驟1：建立或更新數據包日志。節點B檢查緩沖區中的數據包日志。若存在數組元素B[i]滿足傳輸轉發路徑一致的日志信息：

即節點B的日志信息與數據包M的源節點、序列號、上一跳轉發節點ID、接收節點（下一跳節點）ID均一致，則執行B[i].sum=B[i].sum+1，將該記錄的sum域的數值增加1后替換保存；否則，將建立新的傳輸轉發路徑日志記錄B[i]={IDS;Seq;1;IDA;IDB}，保存在數據包日志緩沖區中。

步驟2：轉發數據包至下一跳節點。節點B查找路由表，查找下一跳路由節點C的ID，然后替換數據包M中的單向鏈秘鑰Klast-i、上一跳節點IDlast和下一跳節點IDnest， 即Klast-i=KBi；IDlast=IDB；IDnext=IDC；然后將數據包發送給下一跳節點C。

2）假設節點B收到上一跳節點A發出感知信息數據包M，若有M.IDnext==IDC，即該數據包M的下一跳節點為C，則節點B查找其相鄰節點列表NB，若有：IDB?NA∩NC，則丟棄該數據包，若有：IDB∈NA∩NC，即節點B為節點A和C的共同相鄰節點，則執行數據監聽過程如下：

建立或更新數據包日志。節點B檢查緩沖區中的數據包日志。若存在數組元素B[i]滿足傳輸轉發路徑一致的日志信息：

即節點B的日志信息與數據包M的源節點、序列號、上一跳轉發節點ID、接收節點（下一跳節點）ID均一致，則執行B[i].sum=B[i].sum+1，將該記錄的sum域的數值增加1后替換保存；否則，將建立新的傳輸轉發路徑日志記錄B[i]={IDS;Seq;1;IDA;IDB}，保存在數據包日志緩沖區中。

（4）惡意節點的溯源定位。當系統發現不合法數據包或者檢測到有惡意節點正在發動攻擊時[8,9]，sink節點會啟動針對的惡意節點溯源定位程序，具體過程描述如下：

步驟1：當sink節點檢測到非法數據包后，sink節點將向上一跳節點H1發送節點溯源請求信息Q，如圖2所示。請求信息包含非法數據包中的IDstr和Seq兩個域的數據，節點H1收到該請求信息后，將該請求信息Q廣播給鄰居節點N1、N2……Ni，節點N1收到廣播信息Q后，將檢查其數據包日志，如果無該傳輸路徑的日志，則無須回復任何信息；如果有日志記錄：

圖2 利用相鄰節點信息溯源惡意節點過程

則N1[i].IDlast節點（假設為IDH2節點）就是節點H1的上一跳節點，則節點N1將生成ACK回答信息發送給節點H1，ACKN1的格式如下：

節點H1收到相鄰節點N1發送過來的ACK回答信息后，通過節點N1的單向鏈密鑰KN1i驗證ACK的合法性，若通過驗證，則保存該ACK，否則丟棄。當節點H1收到其他相鄰節點Ni發送回來的ACK消息后，檢查這些ACK消息中節點H1的上一跳節點是否相同，結合自身相鄰節點列表，選取上一跳節點結果相同的ACK，回復給sink節點，回復sink節點的數據包格式如下：

步驟2：節點N1將sink節點的溯源請求信息Q繼續發送給上一跳節點N2，N2收到信息Q之后重復步驟1中節點N1的過程。這樣按照上述步驟逐跳節點溯源后，sink節點將會收到上游節點發送回來的ACK信息，然后利用與節點的共享密鑰驗證其是否合法并提取上兩跳節點的ID值，當從sink收到自源節點IDstr至sink節點路徑的所有節點的ACK回復信息后，由于溯源路徑上的每個節點均包含兩跳節點的ID信息，所有sink節點可通過這些ACK信息中構造出來的路徑信息，溯源到惡意節點。

2 安全性及效率分析

2.1 安全分析

當惡意節點發動虛假數據注入攻擊時，本算法采用相鄰節點協作的形式，由sink節點發起惡意節點溯源，通過逐跳查詢的方式，查找上游節點的數據日志，由于途中轉發節點及相鄰節點已經將數據包的參數記錄在數據包日志中，所以，無論網絡路由是否發生變化，均可以實現路由重構和對惡意節點的溯源定位。

對于單獨的惡意節點發起的虛假數據注入攻擊，sink節點可以依據上游節點的ACK信息重構路徑，進而溯源到惡意節點。惡意節點也不能隨意丟棄溯源請求信息或拒絕回復sink節點的溯源請求信息，這種情況惡意節點將直接被sink節點視為非法節點。

對于途中節點或鄰居節點配合遠程惡意節點發起攻擊。當途中節點或相鄰節點中被敵人捕獲，配合遠端的惡意節點發動攻擊時，如果某途中節點為惡意節點，由于難以提供多個相鄰節點ACK信息，因此很難偽造出合法的干擾信息來回復sink節點，一旦無法核驗，惡意行為將被檢出；另一種情況是某節點的相鄰節點中惡意節點的數量可能超過合法節點的數量，這樣將偽造虛假的ACK消息，但是在路徑重構過程中，很難偽造連續的多個合法的ACK來干擾sink節點重構路徑，因此這種情況下很容易識別到遠程的惡意節點。

2.2 通信開銷

假設自源節點到sink節點之間的節點數目為x，每一跳節點之間的共同相鄰節點平均數量為y。在溯源定位過程中，路徑中的每個節點需要廣播溯源請求信息Q至上一跳節點和相鄰節點，相鄰節點發送一個查詢數據包日志并反饋ACK信息。這樣途中節點的通信開銷x+x*y+x=(y+2)*x；接著途中節點再將反饋的ACK信息匯總后逐跳轉發反饋給sink節點，其通信開銷為1+2+…+x=0.5*x*(1+x)。以BPPM算法為例，該算法在跳數<10、概率標記0.1、節點轉發次數20的時候能夠獲得最高的溯源定位效率，sink節點大約需要接受400-600個數據包。本算法假設跳數為x=10，通信節點之間的平均相鄰節點數量為y=5個，則sink節點需要接收0.5*10*(1+10)=55個數據包，所有節點發送的總的數據包個數為10*（5+2）=70，效率明顯優于BPPM算法。

2.3 適用性分析

這里需要討論兩個通信節點距離與其共同相鄰節點個數之間的關系，顯然通信節點的間隔越近，兩節點天線覆蓋范圍重疊面積越大，當節點間通信距離增長至最大通信距離時，兩節點天線覆蓋范圍的重疊區域將減少到最小，總的重疊面積約為節點通信總面積的39%。假設節點均勻分布，當兩節點天線覆蓋范圍重疊面積最小時，其共同的相鄰節點也應最少。因此，如果一跳節點相鄰節點的平均個數為15時，其公共鄰居節點的平均數量最少為6個。因此，與BPPM算法相比，本算法不受網絡的規模限制，更適用于稠密、大型的傳感器網絡以及遠距離惡意節點的溯源定位。

3 結論

本文提出了一種基于相鄰節點協作的無線傳感器網絡惡意節點溯源定位算法。本算法通過收集上游各節點及其相鄰節點數據日志中的特征參數重構數據包傳輸路徑，實現對惡意節點的溯源定位。與傳統的BPPM算法作對比分析，結果表明，本算法可以在面對單個或多個惡意節點協同攻擊時實現對惡意節點的溯源定位，可適應大型且節點稠密的無線傳感器網絡以及路由動態變化的特點，溯源過程中可大幅度地減少數據包的傳輸數量，進一步降低了節點頻繁的信息交換所帶來的通信開銷。