無線傳感器網(wǎng)絡(luò)中基于相鄰節(jié)點協(xié)作的惡意節(jié)點溯源定位算法

張迪

（赤峰學(xué)院物理與智能制造工程學(xué)院，內(nèi)蒙古 赤峰 024000）

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

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

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

1 基于相鄰節(jié)點協(xié)作的惡意節(jié)點溯源定位算法

1.1 系統(tǒng)模型與假設(shè)

假設(shè)一個傳感器網(wǎng)絡(luò)由基站（sink節(jié)點）及若干傳感器節(jié)點構(gòu)成，基站與外網(wǎng)相連，安全可靠且資源不受限制[5]。傳感器節(jié)點隨機部署，網(wǎng)絡(luò)拓?fù)涑蕵錉罱Y(jié)構(gòu)且可以動態(tài)變化，當(dāng)傳感器節(jié)點感知到某事件發(fā)生時，將通過簇頭節(jié)點收集感知信息（如事件的位置信息等），簇頭節(jié)點將周圍若干節(jié)點發(fā)送過來的感知信息進(jìn)行數(shù)據(jù)融合處理，再將數(shù)據(jù)融合后的數(shù)據(jù)包發(fā)送給下一跳節(jié)點，經(jīng)過若干節(jié)點轉(zhuǎn)發(fā)后，最終達(dá)到基站。與目前許多安全問題研究假設(shè)相同，假設(shè)傳感器節(jié)點抗俘獲能力較弱，攻擊者可以通過被捕獲傳感器節(jié)點獲取節(jié)點內(nèi)所有的信息。本算法借鑒了與LEAP[6]協(xié)議類似的多重密鑰機制，以適應(yīng)節(jié)點間、簇間、節(jié)點與基站之間多種通信形式的安全需要。

1.2 符號

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

IDA：傳感器節(jié)點A的標(biāo)識符，即節(jié)點的MAC地址；

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

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

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

MAC{Data}K：數(shù)據(jù)Data使用秘鑰K計算出來的消息認(rèn)證碼；

NA：節(jié)點A的相鄰節(jié)點列表。

1.3 算法描述

下面將對初始化階段及惡意節(jié)點溯源定位算法進(jìn)行描述。

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

（2）感知信息階段。本階段傳感器節(jié)點主要依據(jù)基站下達(dá)任務(wù)感知部署環(huán)境相關(guān)信息，每一個節(jié)點需要在緩沖區(qū)內(nèi)建立數(shù)據(jù)包日志，用來記錄接收到的有關(guān)感知信息的數(shù)據(jù)包的相關(guān)參數(shù)，數(shù)據(jù)包格式如圖1所示。

圖1 感知信息數(shù)據(jù)包格式

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

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

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

其中Seq和sum分別表示在一個網(wǎng)絡(luò)拓?fù)涓轮芷趦?nèi)節(jié)點發(fā)送感知信息數(shù)據(jù)包的序列號及發(fā)送數(shù)據(jù)包的條目數(shù)；若數(shù)據(jù)包核驗為非法數(shù)據(jù)包，則直接丟棄該數(shù)據(jù)包。

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

1）假設(shè)節(jié)點B收到上一跳節(jié)點A發(fā)出的感知信息數(shù)據(jù)包M，若有IDnext==IDB，則執(zhí)行數(shù)據(jù)轉(zhuǎn)發(fā)過程如下：

步驟1：建立或更新數(shù)據(jù)包日志。節(jié)點B檢查緩沖區(qū)中的數(shù)據(jù)包日志。若存在數(shù)組元素B[i]滿足傳輸轉(zhuǎn)發(fā)路徑一致的日志信息：

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

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

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

建立或更新數(shù)據(jù)包日志。節(jié)點B檢查緩沖區(qū)中的數(shù)據(jù)包日志。若存在數(shù)組元素B[i]滿足傳輸轉(zhuǎn)發(fā)路徑一致的日志信息：

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

（4）惡意節(jié)點的溯源定位。當(dāng)系統(tǒng)發(fā)現(xiàn)不合法數(shù)據(jù)包或者檢測到有惡意節(jié)點正在發(fā)動攻擊時[8,9]，sink節(jié)點會啟動針對的惡意節(jié)點溯源定位程序，具體過程描述如下：

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

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

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

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

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

2 安全性及效率分析

2.1 安全分析

當(dāng)惡意節(jié)點發(fā)動虛假數(shù)據(jù)注入攻擊時，本算法采用相鄰節(jié)點協(xié)作的形式，由sink節(jié)點發(fā)起惡意節(jié)點溯源，通過逐跳查詢的方式，查找上游節(jié)點的數(shù)據(jù)日志，由于途中轉(zhuǎn)發(fā)節(jié)點及相鄰節(jié)點已經(jīng)將數(shù)據(jù)包的參數(shù)記錄在數(shù)據(jù)包日志中，所以，無論網(wǎng)絡(luò)路由是否發(fā)生變化，均可以實現(xiàn)路由重構(gòu)和對惡意節(jié)點的溯源定位。

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

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

2.2 通信開銷

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

2.3 適用性分析

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

3 結(jié)論

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