1、第 39 卷增刊電 子 科 技 大 學 學 報Vol.39 Suppl.2010年4月Journal of University of Electronic Science and Technology of ChinaApr. 2010基于SRP算法的安全AODVjr協議梁滋璐，夏侯士戟，陳東義 (電子科技大學移動計算研究中心 成都 610054)【摘要】無限傳感器網絡由大量具有微處理能力的傳感器節點組成，對物理環境參數進行各種監控。路由是無限傳感網 絡中的一個重要問題, 路由協議用于實現各種路由功能。AODVjr協議是應用最為廣泛的無限傳感器網絡路由協議。作為AODV 協議的簡化，AODV

2、jr協議省略了AODV協議中的各項優化措施，因此在節能性方面優于AODV協議。但是AODVjr協議沒有 在路由過程中采取安全措施，因此不能對路徑信息和傳送的數據提供安全保障。該文將SRP安全算法應用于AODVjr協議，提 出了能夠保障路徑信息安全的SAODVjr協議，并給出了協議安全性的理論證明。關 鍵 詞 AODVjr協議; 路由協議; 安全性; 無線傳感器網絡中圖分類號 TP368文獻標識碼 SRP Based Secured AODVjr RoutingProtocol for Wireless Sensor NetworkLIANG Zi-lu, XIAHOU Shi-ji, and

3、CHEN Dong-yi(Mobile Computing Center, University of Electronic Science and Technology of China Chengdu 610054)AbstractA wireless sensor network (WSN) is a group of spatially distributed sensor nodes that cooperatively monitor the physical or environmental conditions. Routing is an important issue in

4、 WSN and routing protocol is responsible for the routing function. AODVjr routing protocol, a simplified version of the widely used Ad hoc on-demand distance vector (AODV) routing protocol, removes the optimization strategies from the original AODV routing protocol such as HELLO message mechanism an

5、d route error message broadcasting mechanism; while inherits only the dynamic characteristic from AODV routing protocol. Due to this simplification, AODVjr outperforms AODV routing protocol in energy consumption and thereby is widely used in various WSNs.Key wordsAODVjr;routing protocol;security;wir

6、eless sensor network無線傳感器網絡由大量具有微處理能力的傳感器節點組成，涉及傳感器技術、嵌入式技術、分布 式信息處理技術和無線通信技術。傳感器節點采用 電池供電，要求一節普通的五號電池能夠支持數個 月甚至一年以上。因此，無線傳感器網絡路由需要 將節能作為重要的設計指標，以延長網絡的生命期。 值得注意的是，在無線傳感器網絡中，路由協議不 僅要考慮降低單個節點的能耗，更要關心整個網絡 的能量消耗問題。無線自組網按需平面距離矢量協議AODV1是 一個被廣泛采用的傳統無線自組網路由協議。如果 將其直接應用于無線傳感器網絡，由于該協議本身 所具有的復雜性，將不能滿足無線傳感器網絡低功

7、 耗路由的要求。AODVjr協議2在考慮了無線節點的有限移動性之后，以最大限度降低節點功耗為目的，對AODV協議進行了簡化。AODVjr協議僅保留了 AODV協議按需路由的動態特性，而將HELLO消息、 路由錯誤信息、問詢序列號等AODV協議為了適應 節點移動性提出的優化措施統統省略，對AODV協 議進行了最大限度的簡化。受益于這樣的簡化， AODVjr協議在能耗方面極大地優于AODV協議，因 此AODVjr協議被廣泛應用于各種無線傳感器網絡。AODVjr協議最大的問題是沒有考慮路由的安 全性，不僅數據在傳輸過程中極有可能被篡改或故 意丟棄，路徑信息本身也有可能被更改。這必然對 網絡的健壯性產

8、生不利影響。SRP安全算法是一種 端到端的安全機制，它僅在源節點和目的節點處關 注安全性，能夠有效地節約網絡資源，并且不會在收稿日期： 2009 - 11 - 15基金項目：中加政府間科技合作基金(2009DFA12100)作者簡介：梁滋璐(1988 - )，女，碩士生，主要從事無線自組織網絡路由協議方面的研究.中間節點處增加額外開銷。本文用SRP安全算法對 AODVjr協議進行安全化，以達到保障路徑安全性的 目的。若將待傳輸數據捎帶到路由信息中，則可以 保障所傳輸數據的安全性。單純對傳輸數據本身安 全性的保障可以通過采用相關的加密算法實現，不 在本文的討論范圍之內。1AODV協議及AODVj

9、r協議無線自組網按需平面距離矢量協議AODV是一 種按需路由的動態協議。與用路由表保存網絡路由 信息的靜態協議不同，它不需要周期性地廣播信息 更新路由表。當源節點需要向目的節點傳送數據時， 它才廣播一個路由請求(RREQ)啟動一個路經尋找 過程。因為AODV協議避免了發送周期性的路由更 新消息，所以可以降低網絡的開銷，節約通信帶寬； 同時，由于不需要采用路由表存儲路由信息，AODV 協議可以為無線節點節約寶貴的內存資源。AODV 協議的 特 點是引 入 了數據 包 序列號 (sequence number)和HELLO消息(HELLO message)兩種機制。 前者保證網絡即使處于修復破損鏈

10、路狀態也不會出 現路由環路；后者則保證節點能夠及時知曉鏈路的 連接狀況。當網絡規模增加時，AODV協議也能夠 保證令人滿意的網絡性能。AODVjr協議是對AODV協議的簡化版本，其編 程與調試時間不到AODV協議的一半，資源消耗少， 實現起來相對容易得多，但性能卻與AODV協議相 差無幾。所以無線傳感器網絡多采用AODVjr路由協 議，在最大限度保證協議性能的前提下達到節約能 源的目的。為了維持路徑的可用性，路徑的生命期只有在 收到數據包時才進行更新，而發送數據包不進行路 徑更新。當路徑破損時，源節點等待一段時間收不 到來自目的節點的消息時，源節點會停止從目的節 點接收消息，而開始一次新的路由

11、請求。AODVjr 的工作原理如圖1所示，通過采用這種端到端的通信 策略，HELLO消息機制和路由錯誤報告機制完全可 以省略，網絡的開銷因此而大大降低。RREQ RREQ RREQSM1M2DRREP RREP RREP圖1 AODVjr協議工作原理2SRP安全算法及其改進AODVjr協議的控制包內不含易變域，使保持其 安全化變得相對容易。可以考慮采用一種與ARIN3相似的安全算法。ARIN算法采用由一個可靠的第三 方提供加密證來保證路由的安全性，整個網絡中所 有的有效節點都應該知曉該證書供應方的公匙。證 書供應方通過帶寬外的渠道與每個節點交換鑰匙。 每個節點在被證書供應方認證之后可以獲得一個

12、證 書。各個節點都有整個網絡所有其他節點的公匙， 中間節點就能夠驗證每個轉發的路由包的真實性。 但是，公匙加密機制會增加中間節點的開銷，隨著 網絡范圍的加大，這種算法被認為是不現實的。其 次，節點的IP地址并沒有得到保護，這是由AODVjr 協議本身的性質所決定的，所以將證書與IP地址關 聯起來也是不合理的。本文采用SRP 算法4 增強 AODVjr協議的安全性。SRP算法是一種端到端的安全算法機制，即僅 在源節點和目的節點處關注安全性，中間節點則不 予以考慮，這與ARIN算法非常不同。SRP算法有如 下假設：(1) 通信信道為對等的雙向信道。(2) 源節點和目的節點之間存在一個安全聯系 (S

13、A)。通過事先知曉的通信末端節點的公匙就可以 實現這種信任關系。(3) 兩個節 點可以通 過橢圓曲 線 Diffie- Hellman5算法協商出一個共享的密匙，然后用SA與 證實參與交換的節點確實是可以信賴的。(4) 存在一對共享密匙KS,D 控制數據朝兩個方 向流動，從而保證SA的雙向性。(5) 數據鏈路層提供了可靠的雙向傳輸。(6) 有媒體訪問層地址到IP地址的一對一映射。 (7) 每次傳輸都會被所有的鄰節點正常接收到。 當源節點S發出一個路由請求消息RREQ時，會給該路由請求消息一個問詢序列號(query sequence number) 和 一個隨機 問詢標志 (random que

14、ry identifier)，用來標識該路由請求的標志。然后以源 節點IP地址、目的節點IP地址、問詢序列號、隨機 問詢標志和共享密匙KS,D作為輸入計算消息識別碼 MAC(message authentication code)。中間節點Mi (i=1,2,)將自己的IP地址附加到 RREQ包中，并對RREQ進行中繼，中間節點可以在 鏈路破損時作出反饋，在某些情況下，它們還能提 供路由響應，但是考慮到AODVjr協議禁止中間節點 對路由請求作出響應，本文也將禁止SRP算法的該 項功能。通常目的節點會多次接收到來自不同中間節點 的同一路由請求。這時，SRP規定目的節點保留最近收到的該路由請求，

15、而將先前接收到的丟棄掉。 但是在AODVjr中，根據“最快即最好”原則，目的 節點只會對第一個收到的RREQ作出響應。這樣可以 有效地縮短路由發現時間，并且節約能源和內存。 當路由請求到達目的節點D時，目的節點構造出路 由響應消息RREP，并以路由請求消息為輸入計算出 MAC，然后逆著路由請求消息來的路徑將路由響應 傳輸給源節點S。源節點會檢驗該路由響應的有效 性，如果是有效的路由響應，則認為可以通過該路 徑向節點D傳輸數據。在SRP算法中，路由響應可以 通過多條路徑傳回源節點，但是考慮到AODVjr協議 中路由響應只能以單播(unicast)的方式傳回源節點， 為了配合AODVjr協議的運行

16、原理，本文對SRP協議 進行了一定改動。既然目的節點只響應最先收到的 RREQ，那么RREP就逆該RREQ來的路徑傳回源節 點S。3安全化的AODVjr協議SAODVjr協議3.1基本假設AODVjr協議在AODV協議基礎上進行了大量 刪減，將HELLO消息、數據包序列號、路徑長度、 路由錯誤報告等統統省略，從而極大地節省了網絡 資源。在沒有考慮安全因素的前提下，AODVjr可以 表現得與AODV相差無幾。但在考慮安全因素時， AODVjr協議由于過于簡化，反而不利于安全機制的 運行，并且可能導致網絡中出現路由環路。基于以 上考慮，本文在AODVjr協議中引入問詢標志QID， 源節點同一次發出

17、的所有問詢將獲得相同的標志， 以避免中間節點將同一問詢轉發多次，或目的節點 對同一問詢作出多次響應。同時，由于SRP與AODV 在路由機制上略有差異，本文對SRP算法也進行了 一些適用于AODVjr協議的改良，這在前一部分中已 經提到。綜上所述，本文將SAODVjr協議的基本假設總 結如下：(1) 通信信道為對等的雙向信道，源節點和目的 節點之間存在一個安全聯系(SA)和一對共享的鑰匙 KS,D控制數據朝兩個方向流動，從而保證SA的雙向 性。(2) 在AODVjr協議基礎上，引入問詢標志QID參數。(3) 目的節點只響應最先收到的路由請求，對于 之后收到的同一請求不予響應。路由響應以單播的方式

18、逆路由請求的路徑傳回源節點。(4) 僅目的節點響應路由請求，中間節點不得響 應路由請求。(5) 數據鏈路層提供了可靠的雙向傳輸，每一次 傳輸都會被所有的鄰節點正常接收到。(6) 有媒體訪問層地址到IP地址的一對一映射。3.2路由請求RREQ源節點在每一次發起RREQ時激發一個32 bit的 隨機問詢標志QID。中間節點通過該標志來識別路由 請求。本文采用一個安全偽隨機數產生器6來產生 QID，該偽隨機數產生器的輸出與真正的隨機數在統 計學意義上并沒有差別。一個計算能力有限的壞節 點是沒有能力預見其輸出的。MAC域長96 bit。以目的節點地址(dest)、源節 點地址(scr)和共享的鑰匙KS

19、,D作為單向散列函數(如 SHA-1或MD57)的輸入，通過計算其輸出，可以獲 得相應的MAC碼：S ® MAC:Hdest,scr,KS,D(1) 當源節點需要與另一節點進行通信而又沒有通 往該節點的路徑信息時，源節點便通過向鄰節點廣播一個路由請求消息RREQ發起一個路徑尋找過程：S ® brdcast:dest,scr,QID,MAC(2)路由請求RREQ的格式如圖2所示。類型DG保留字 目的節點IP地址 源節點IP地址 中間節點IP地址 問詢標識QIDSRP消息識別碼MAC圖2 SAODVjr的RREQ包格式其中類型取值為1，表示該包為路由請求消息； D的值設為1，表

20、示中間節點不得響應該RREQ；G 的值也設為1，表示通信信道為雙向；保留字默認為0；中間節點IP地址域用于存放該RREQ消息到達目 的節點所經過路徑上所有中間節點的IP地址。3.2RREQ的中繼中間節點對RREQ進行中繼。假設中間節點Mi 從鄰節點處接收到RREQ，Mi首先將QID提取出來， 如果該QID與節點問詢表(query table)的某個入口相 符合，則舍棄接收到的RREQ；否則，M1繼續提取 出源節點S和目的節點D的地址，與QID一起在問詢表 中創建一個入口。然后將自己的IP地址加入到RREQ 的中間節點IP地址域中，并將該RREQ廣播出去：Mi ® brdcast:de

21、str,scr,QID,MAC, (addrM1,addrM2,addrMi-1,addrMi) (i=1,2,)(3)路徑上的每個節點都重復這樣的工作，檢查收 到的RREQ是否已經被處理。若沒有，則提取出目的 節點IP地址、源節點IP地址和問詢標志QID在問詢表 中創建一個新的入口。將自己的IP地址附加到RREQ 中的相關域，然后將該RREQ 廣播出去，直到該 RREQ到達目的節點為止。中間節點還將檢測從鄰節點接收問詢的頻率， 并根據這個頻率給鄰節點劃分優先級。通常最高優 先級會分配給頻率最低的節點，反之亦然。壞節點 的鄰節點會檢測到極高的問詢接收頻率，如果是這 樣，鄰節點們會更新它們相應的

22、優先級。低優先級 的問詢得不到響應，就等于已經被丟棄。這樣，壞 節點就達不到消耗網絡資源、降低網絡性能的目的。3.4路由響應RREP當目的節點D接收到RREQ時，會首先檢驗該 RREQ是否來自于一個與之存在SA關系的節點。然 后，D提取出該RREQ的QID，以判斷是否已經接收 過與該RREQ相同的請求。若已經接收過，則丟棄該 包不作響應；否則，提取出目的節點IP地址、源節 點IP地址和問詢標志QID為單向散列函數的輸入，如 果輸出與該RREQ中的消息識別碼一致，則認為該 RREQ是有效的，其真實性也得到證明。在證實該RREQ的有效性之后，目的節點D開始 構造相應的路由響應RREP。D首先將RR

23、EQ中的目 的節點地址、源節點地址、中間節點IP地址和問詢 標志QID復制到相應區域，然后以目的節點地址、源 節點地址、中間節點IP地址和共享密匙KS,D作為單向 散列函數的輸入計算消息識別碼MAC。該MAC碼可 以向源節點S證明目的節點D確實接收到了其發出 的路由請求：D ® MAC:Hdest,scr, (addrM1,addrM2,addrMi-1,addrMi),KS,D(4) 路由響應RREP的格式如圖3所示。類型A節點數保留字目的節點IP地址源節點IP地址中間節點IP地址問詢標識QIDSRP消息識別碼MAC圖3 SAODVjr的RREP包格式其中類型取值為2，表示該包為路

24、由響應；A取 值為0，表示不需要向目的節點確認RREP的接收；目的節點將RREP逆著該RREQ來的路徑傳輸回 源節點。3.5檢驗RREP的有效性當接收到來自目的節點D的路由響應時，源節 點S首先檢查RREP中源節點地址、目的節點地址和 問詢標志QID，如果與當前最迫切的問詢不一致，則 將該RREP丟棄；否則，源節點提取出目的節點地址、 源節點地址、中間節點IP地址與KS,D一起作為單向散 列函數的輸入計算消息識別碼MAC ，若結果與 RREP中的MAC碼相符，則S認為路由請求確實完好 無損地到達了目的節點D。而且，路由響應能夠沿 著該路徑被源節點S 成功接收，說明路徑信息在 RREQ傳輸的過程

25、中沒有被破壞，該連接信息是真實 可信的。4協議的正確性論證為了論證協議的正確性，本文用文獻8中的方 法對協議的安全性進行了驗證。假設X和Y是公式，P和Q是原語，K是共享密匙，C是一個陳述。遵循文獻9中規定的符號體系：l P < X：P被告知X。l XÎ P：P擁有或者有能力擁有X。l P|X：P說了X。l P| º P ¬¾K ® Q：P相信或有資格相信P和Q可 以通過共享密鑰K進行通信，且這個K是好的，即不 會被P和Q不信任的原語知道。l P| º Ä (P)：P相信它能確認一個消息不是源 自它自己。l P|

26、86; C：P相信或有資格相信陳述C成立。l (X, Y)：兩個公式的聯合。是一個帶有聯合性 和交換性的集合。l *X：公式的“不源于此”性質。如果P被告 知X，則P能夠辨別出自己之前沒有說過X。l H(X)：X的單向散列函數值。l 分隔兩個陳述或陳述的聯合的水平線表示線上面的陳述能夠推出線下面的陳述。如 P < (X ,Y ) 表P < X示，由P被告知(X, Y)可以推出P被告知X。將協議抽象成路由請求RREQ和路由響應RREP在一個公共信道上的傳播，如圖4所示。路徑上一系 列的中間節點都有被攻擊的可能。QS,D, HQS,D,KS,D節點數表示路徑上所有中間節點的數量：SD

27、® unicast:dest,scr, (addrM1,addrM2,addrMi-1,addrMi),QID,MAC(5)DRS,D,route,HQS,D,route,KS,D圖4 抽象化的SAODVjr協議QS,D和RS,D分別代表路由請求RREQ和路由響應RREP；H代表單向散列函數，H表示請求消息識S < HRS,D,KS,D ，并且 (RS,D,KS,D) Î D ，S| º S ¬¾KS ,D¾® D別碼MAC的過程。與QS,D有關的域包括問詢標志QID<(8)S(Q,H (Q, K), S |&#

28、186; ¬¾KS ,D¾® DS , DS , DS , D。S |º D | R,S| º D | HQ, K以及源節點和目的節點的地址。下面對協議的安全性進行論證：S,DID(1) KÎ S，S| º S ¬¾K S ,D¾® D，Q Î S源節點S擁有共享密匙KS,D，且相信該密匙可以 用于自己和目的節點D 相互證明身份。源節點為RREQ分配一個獨特的問詢標志QID用于識別該問詢。S,DID(2) KÎ D，D| º S ¬&#

29、190;KS ,D¾® D，D < Q ，D| º S|QID。 目的節點D同樣擁有共享密匙KS,D，并相信自己和源節點S可以使用該密匙進行通信。D會被告知該RREQ的QID，并且相信源節點說了QID。此外，S與 D都相信它們能夠分別識別路由請求QS,D和路由響 應RS,D。(3) S| º Ä (RS,D，HRS,D,KS,D)，D| º Ä (QS,D，HQS,D,KS,D)。源節點S相信它能確認偽造的RS,D 和MAC碼不 是源于自己；同理，目的節點D相信它能確認偽造 的QS,D和MAC碼不是源于自己。S , D

30、S , DS , D 據此，源節點S相信整個路由響應來自于目的節 點D，并且已經建立起通往D的路徑。假設沒有串通 起來的壞節點，路由響應只可能逆著路由請求到達 的路徑抵達源節點。同時，既然路由響應能夠逆該 路徑到達源節點，也就說明路由響應的內容在其構 造之前沒有被更改過。因此，路由響應順利到達源 節點 S 說明 相應的連接信息是正確的，即證明 SAODVjr協議能夠保障路徑的安全性。5結論本文在AODVjr路由協議基礎上提出了一種基 于SRP 安全算法的能夠保障路徑安全性的路由協 議。理論證明其能夠達到保證路徑安全的目的。但 該協議并不能保證傳輸數據的安全性。此外，該協 議也沒有考慮能耗和網絡

31、開銷。因此，對該協議的 優化可以從以上兩個方面入手。總的來說，SAODVjr 協議能夠為整個無線傳感器網絡提供安全的路由。(4)D < *(QS , D ,H (QS , D , KS , D )D < (QS , D ,H (QS , D , KS , D )，以及參考文獻D < (QS , D ,H (QS , D , KS , D ) 。(QS , D ,H (QS , D , KS , D ) Î D根據“不源于此”性質，當D收到一個包的時 候，它會辨別自己是否之前已經傳播過該包。1 CHARLES E P, ELIZABETH M B. Ad hoc on

32、-demand distance vector (AODV) routingS. IETF RFC 3561.2 IAN D C, LUKE K B. AODVjr, AODV simplifiedJ.Mobile Computing and Communications Review, 2002, 6(3):100-101.(5)(QS , D ,H (QS , D , KS , D ) Î D。(QS , D Î D,H (QS , D , KS , D ) Î D, QID Î D3 KIMAYA S, BRIGET D, BRIAN N L, e

33、t al. A secure routing protocol for Ad hoc networkC/Proceedings of the10th IEEE International Conference on Network Protocols.同樣，可以推出目的節點D擁有QS,D剩下的域中的內容。 從步驟(1)(5)可以得出如下結論：S,D S,DS,D S,DD < HQ,K，(Q,K)Î D，D| º S ¬¾K S ,D¾® DS.l: IEEE, 2002.4 PAPADIMITRATOS P, HAAS Z J

34、. Secure routing for mobile Ad hoc networkC/Proceedings of the SCS CommunicationNetworksandDistributedSystemsModeling and Simulation Conference (CNDS 2002). SanD < (Q,H (Q, K),D|º S ¬¾KS ,D¾® DAntonio, TX: s.n., 2002.(6)S , DS , DS , D D| º S|QS , D , D| º S|HQS

35、 , D , KS , D 。5 DIFFIE W, HELLMAN M E. New directions incryptographyJ. IEEE Transactions on Information Theory,證實了路由請求和消息識別碼均來自源節點。而且，之前就假設兩個原語不會泄露共享秘匙，所 以源節點不會泄露秘匙。1976, 22(6): 644-654.6 MENEZES A, VAN OORSCHOT P, VANSTONE S.Handbook of applied cryptographyM. S.l.: CRC Press,2001.(7)(QS , D ,H (RS

36、 , D , KS , D ) Î S(RS , D Î S , H (QS , D , KS , D ) Î S， 以 及7 RIVEST R. The MD5 message-digest algorithmS. RFC1321, 1992.QID ,route Î S 。 RID Î S 根據“不源于此”性質，可知：8 BURROWS M, ABADI M, NEEDHAM R. A logic of authenticationC/Proceedingsofthe12thACM Symposium on Operating System Prin