Ｍ２ＡＳＲ——新型多徑匿名源路由協議

（1.天津大學 a.計算機科學與技術學院; b.電子信息工程學院， 天津 300072; 2.青海師范大學 網絡信息中心，西寧 810008）



摘要：

針對無線Ad hoc網絡通信的安全與效率問題，提出一個高效并有較好匿名能力的多徑匿名源路由協議M2ASR。在DSR協議的基礎上，使用標簽機制，對源路由的工作過程進行了修改，實現了能夠應用于大規模無線網絡的多徑匿名路由；并在協議中首次使用IDA算法，利用Ad hoc網絡的節點轉發和協議本身提供的多徑性質，提高了無線Ad hoc的通信效率；從理論和仿真角度對M2ASR協議的匿名性和使用IDA算法之后所帶來的效率進行了分析和總結。

關鍵詞：多跳移動通信網絡； 多徑； 匿名； 源路由

中圖分類號：TP393.04文獻標志碼：A

文章編號：10013695(2009)03101804



M2ASR: new multipath mutual anonymous source routing protocol



DU Xiujuan1a，2， JIN Zhigang1b



(1.a.School of Computer Science Technology， b.School of Electronics Information Engineering， Tianjin University， Tianjin 300072， China;

2. Network Information Center， Qinghai Normal University， Xining 810008， China)



Abstract:

To solve the security and efficiency issues of mobile Ad hoc networks， this paper presented an efficient multipath mutual anonymous source routing M2ASR which originated from the protocol DSR and provided anonymity by modifying the work flow of routing discovery of protocol DSR and adopting label switches like what used in MPLS， so multipath anonymous routing can be used in largescale wireless networks. Meanwhile， combined with node forwarding and multipath， the algorithm IDA was used in the protocol for the first time so the communication efficiency of Ad hoc networks was greatly enhanced and it is showed by theoretical analysis and simulation.

Key words：Ad hoc; multipath; anonymous; source routing



移動Ad hoc是由帶無線收發裝置的節點組成的多跳移動通信網絡。因為它不依賴于預設的基礎設施且部署迅速，Ad hoc網絡廣泛應用在軍事、災難營救等場合。無線通信中共享信道、高傳輸錯誤率、節點移動性以及有限帶寬等特性給路由協議的設計帶來很大的挑戰。路由協議的設計與實現因此成為該領域的研究熱點。如何設計一個安全、高效的移動Ad hoc路由協議是本文的研究重點。

無線信道的共享及開放特性使得移動Ad hoc網絡很容易遭到外來節點的竊聽。其中每個節點的地位都是平等的，網絡的自組特性決定了該網絡缺乏一個權威的認證機制對每一個節點的身份進行確認，這就使得那些蓄意對網絡進行攻擊的惡意節點有機可乘。Ad hoc網絡中節點的身份、位置、網絡拓撲和移動模式等信息較其他網絡更為敏感。因此，節點匿名的實現成為移動Ad hoc網絡的一個新的研究方向。

關于移動Ad hoc網絡的匿名路由的實現，國內外已經提出了一些研究思想，其中包括ASR[1]、ANODR[2]、MASK[3]路由等，其主要思想是移動Ad hoc網絡的按需路由協議。例如DSR和AODV進行匿名化，當源節點向目的節點發送路由請求RREQ分組以期發現一個或多個到達目的節點的路由時，只有目的節點能夠識別出此RREQ分組是發給它的，而其他節點則只能確定該數據分組不是發送給它們的，不會獲得更多的信息。這些匿名路由協議或對隱私的保護力度不夠，如MASK協議；或由于開銷太大而降低了通信效率，如ASR和ANODR協議。本文設計研究了一個適用于大型網絡、具有較好匿名能力和較高通信效率的多徑匿名源路由協議M2ASR。

1 M2ASR協議的設計

傳統的MANET路由協議分為表驅動和按需路由兩大類，從安全角度考慮，按需路由比表驅動路由更容易實現匿名。目前兩個最流行的按需路由協議，即動態源路由協議DSR[4]和按需距離矢量協議AODV[5]。與AODV相比，DSR協議存在以下優點：

a）DSR協議要比AODV協議簡單。所有與路由相關的信息都被嵌入了數據分組當中，中間節點無須保存與路由相關的信息，因此有利于安全的實現。

b）盡管DSR協議最終只選取一條路徑進行通信，但在路由發現的過程中源節點可能會收到多于一個的RREP分組，即源節點到目的節點的路徑不止一條；而AODV協議則只能發現一條路由，這就使得DSR協議對鏈路失效具有一定的抵抗力，并且DSR協議將選擇路由的權利交給了源節點，從安全和健壯的角度講，這是一個非常好的策略，源節點可以使用不同的度量標準，如節點的能量、處理能力、網絡帶寬、跳數或可靠性等，來選擇指向目的節點的路由。

c）盡管DSR協議由于使用源路由而造成分組數據包較大，但其網絡負載相對AODV協議要小［6］。

由于以上優勢，M2ASR在DSR基礎上進行設計。DSR能夠發現多條路徑，但在執行源路由時只使用其中一條，不能充分利用網絡資源，而且一旦出現網絡擁塞或鏈路失敗則必須重新選擇路徑。而MSR協議以DSR為基礎，充分利用網絡資源，采用多徑路由，同時使用多條互不相關、相互獨立的路徑。因此，在DSR協議的基礎上，M2ASR協議引入了移動Ad hoc網絡下的多徑源路由協議MSR(multipath source routing protocol)的主要思想［7］。

如果在采用多徑路由時，每條路徑上發送不一樣的數據分組，那么盡管帶寬的利用率上去了，可靠性卻沒有增加，而如果每個分組在幾條路徑上都分別傳送一遍，則降低了通信效率。因此，為了能夠充分發揮多路徑的優勢，在M2ASR協議中采用IDA(information dispersal algorithm)對數據分組進行處理，在通信效率和可靠性之間獲得平衡。

IDA算法由Michael O.Rabin提出，將文件信息分解成n個部分，每部分的大小為源文件的m分之一，所有部分加起來的大小只是原來文件大小的（n/m）倍。只要收到其中的m個部分即可對文件重新還原。選取n個向量 ai=(ai1，…，aim)∈Zp，1≤i≤n，使得每一個包含m個不同向量的子集都是線性無關的。文件F被分割成長度為m的序列組，由此 F=(b1，…，bm)，(bm+1，…b2m)，…，令 S1=(b1，…，bm)，依此類推。對于i=1，…，n，Fi=ci1，ci2，…，ciN/m。其中cik=ai×Sk=ai1×b(k-1)m+1+…+aim×bkm。 并且滿足|Fi|=|F|/m。

假如給出文件F的m個數據分片， F1，…，Fm，由此可以進行如下計算來恢復文件F。令A=（aij）1≤i，j≤m為一個 m×m的矩陣，其中的第i行為 ai。表達如下：

A#8226;b1bm=c11c1m

由上式得b1bm=A-1c11c1m

因此，只需要計算矩陣A的逆矩陣一次，就可以一勞永逸，對于文件F中的每一個字符，進行2m模p次運算操作。對于那些能夠滿足m2≤|F|的足夠大的文件來說，即使使用m3次操作來計算矩陣A的逆矩陣，所帶來的開銷也遠小于重組文件F的開銷。

在設計M2ASR協議的過程中，采用MPLS協議的思想對基礎協議DSR進行一定的修改以實現路由的匿名性。當數據包進入網絡時，MPLS協議為該數據包打上一個固定長度的短標簽，該標簽作為轉發索引值對應一個下一跳地址和一個新的標簽，將新標簽替換舊標簽后與數據包一同被轉發給下一跳，這樣當后續節點轉發數據包時，就無須再對數據包的網絡層頭部進行分析了。另外DSR協議所使用的源路由在保存的節點標志數目過多或節點標志長度過大時，會導致數據分組中真正用來加載數據的部分會小得多，因此M2ASR協議將從以上兩方面入手，對DSR協議進行修改。

在移動Ad hoc網絡中，每一個節點所收到的數據分組只能由其無線傳輸范圍之內的鄰居節點轉發給它，如圖1所示。節點A是節點F在路由上的下一個節點，只要節點A收到的數據分組下一跳的標志與節點A相同，數據傳輸就可以進行下去，換句話說，即使節點F收到的數據分組所攜帶的源路由中不包含節點A的標志，但只要節點F確定自己在路由上之后，經過計算或是從記錄中獲取，將下一跳的標志，即節點A的標志放入到源路由列表當中去，節點A就可以像正常的源路由一樣處理，這就提供了一種啟示，即在下一個節點為前一個標志進行編碼。在節點F收到節點A發送的數據分組后，以某種算法將節點A的標志“A”進行編碼，并將這個編碼放入分組中，如圖1中的粗體的“01”，再加上自己的標志“F”，就形成新的分組。當有數據分組返回到F時，節點F在判斷出該分組是發送給自己的之后，再從源路由列表中取出下一跳的編碼，示例中粗體的“01”，經過某種方式的運算，得到了“A”，再將這個“A”放入到列表當中。這樣就可以通過運算方式的選擇來實現縮短標志、擴大路由適用范圍的目的。

2M2ASR協議的路由機制

2.1M2ASR協議的路由請求機制

當某個節點S希望向某個目的節點D發送一個新的數據包時，通常發起節點S會搜索它的路由緩存，尋找一條通往目的節點D的路由，如果沒有找到，那么節點S將會發起一個M2ASR的路由發現過程。

發起節點S以某種方式獲取到目的節點D的公鑰PKD，然后構造并廣播RREQ路由請求分組，中間節點X的鄰居將收到如下格式的來自節點X的RREQ數據分組：

{HEAD，SIDx，hops，(bit_seqS→D)}

其中：HEAD=RREQ，seq，PKD(IDS，SKS(Hask(IDS))，Esession)。HMSG;HMSG=PKD(Hask(PKD(IDS，SKS(Hask(IDS))，Esession)));seq是路由發現的順序號;PKD是節點D的公鑰;IDS為節點S的標志，目的節點通過該標志可獲取S的公鑰;SKS為節點S的私鑰；Esession為發起節點和目的節點此次會話使用的對稱密鑰；SIDX為中間節點X在此次會話中使用的標志，hops記錄經過路由的跳數，為了保證對發起節點S的所有的鄰居節點實現匿名，hops字段將被發起節點S初始化為隨機值；最后一個字段用來保存從節點S到節點D中間經過的所有節點的源路由，由于強匿名原因，該字段也被發起節點隨機初始化成一些數字；HMSG用來提供節點判斷自己是否目的節點以及對前面加密部分的有效性進行驗證。在發送RREQ分組前，節點S會在路由表中保存如表１所示記錄。其中，最后一個字段用來保存到節點D的路由。收到這個路由請求分組的節點X的鄰居節點Y將按圖2所示的流程進行處理。

表１發起節點路由表中RREQ記錄

seqIDDhopsbit_seqS→DSIDSEsession?

2.2M2ASR協議的路由應答機制

當路由請求的目的節點收到一個RREQ分組之后，將根據RREQ分組中的信息，構建并向鄰居節點廣播一個路由應答RREP數據分組。中間節點Y將會收到來自其鄰居節點X的格式如下的路由應答RREP分組：

{HEAD′，SIDY，(bit_seqS→D)，SIDX，(bit_seqD→S)}

其中：HEAD′=RREP，seq，Esession(bit_seqD→S，hops)，HMSG′，HMSG′=Esession(hash(Esession(bit_seqD→S)，hops)))，

這里需要特別說明的是路由回復RREP中的hops，為了能夠保證發起節點S和目的節點相鄰時也能達到相互位置上的強匿名性，以及使得經過的中間節點都不能猜測出距離發起節點有多遠，尤其是發起節點的鄰居節點，在創建路由應答RREP分組時，目的節點也會在從RREQ分組中提取出來的hops字段上加上另外一個隨機數。當然，目的節點D也會將這個隨機數保存起來，在為以后到達的路由請求分組創建路由應答時，將其加在hops字數之上，這樣既使得路由請求的發起節點同其他節點一樣不能猜測出發起節點與目的節點之間的距離，也保證了路由請求的發起節點S能夠在收到多個路由應答分組之后，能夠根據分組中保存的hops字段的值來判斷哪一條路徑更短。如果節點D第一次收到RREQ分組的話，節點D還會在路由表中保存如表2所示的記錄。

表2中間節點路由表中保存的RREQ字段

seqIDShops’bit_seqD→SSIDDEsession?

其中，最后一個字段為用來在以后保存到達節點S的路由。收到節點X轉發的RREP分組的節點處理分組采取的流程略。

2.3M2ASR協議的數據結構

為了進行負載平衡處理，在本文的實驗中，M2ASR在源節點建立一個特殊的表，包含到達目標節點的多個路徑信息[7]，表示如下:

struct mul. dest

{

int index ;

ID Dest ;

float Delay ;

float Weight ;

int seq;

char sessionkey

……

} ;

與MSR中的表結構相比，M2ASR增加了seq和sessionkey。它們分別記錄在路由發現過程中使用的seq序列號以及商定的節點S與節點D的共享對稱密鑰。

3M2ASR協議的匿名性與效率分析

3.1匿名性分析

從對M2ASR協議的描述中可以發現，只有當發起節點和目的節點在獲取對方公鑰時才會使用對方的節點標志，公鑰完成路由請求和路由應答分組中的數據加密，保證只有分組的目的節點才能解開里面的數據。RREQ數據分組中包含的發送節點標志和用發送節點私鑰加密的發送節點簽名用來驗證發送節點，不包含任何與節點身份、位置相關的信息，實現了匿名性要求。而節點的會話標志用來確定這個節點是不是在某條路由上，當該節點收到鄰居發來的數據包時，通過比對數據包中的會話標志字段和該節點與數據包中包含的seq序列號相應的會話標志是否相同，來確定該節點是否在這條路由上。因此，一個節點的會話標志不僅與節點的身份位置等信息無關，而且可以對同一個節點、不同的路由使用不同的標志來加強路由的保密性。使得不在路由上的其他節點很難通過對數據分組的分析來追蹤到數據分組的流向。

為了避免跳數字段暴露節點位置，源、目的節點都對該字段進行了隨機化處理，其他節點無法知道其確切的路徑長度。為了保證發起節點和目的節點對鄰居節點實現匿名，對源路由序列bit_seq進行了特殊處理，隨機初始化成一定的位數，而不是空的源路由序列，即使通信雙方是兩個相鄰節點，也不能相互發現，做到了強位置匿名，保證了各自的鄰居節點無法根據這個路由序列猜測出兩個節點的位置。在M2ASR協議中，源路由序列由會話標志的索引序列替換，該索引只是節點所保存的鄰居節點的會話標志表中的一個本地索引，序列中索引的長度并不固定。路由上的節點依次從路由序列中取出索引值，而其他節點根本不能理解這個索引值序列，因此，M2ASR協議是路由匿名的。表3對匿名路由協議ANODR、ASR和M2ASR所成就的匿名屬性進行了比較。

表3ANODR、ASR和M2ASR匿名屬性比較

內容ANODRASRM2ASR

源、目的節點身份保密X√√

轉發節點身份保密√√√

位置弱保密√√√

位置強保密（外部節點）√√√

位置強保密（內部節點）X√√

路由匿名√√√

節點標志編碼XX√

多徑XX√

3.2協議效率分析

不同的密碼系統引入不同的鏈路和處理開銷，對匿名路由性能產生不同的影響。M2ASR協議在構建RREQ分組時使用目的節點公鑰進行加密，在泛洪RREQ分組時，第一次收到該分組的中間節點使用自己的私鑰對分組中部分數據進行解密，以判斷自己是否是目的節點。考慮到加密與解密次數較多，在協議中選擇加密速度慢、解密速度快的ECAES算法保證解密效率，其他加密采用高效AES/Rijndael對稱加密。中間節點需查找兩次哈希表（SHA1作為哈希函數），而不像ASR等協議那樣每一跳都需要加/解密操作。這三種健壯的密碼系統目前在商業領域應用較為流行。表4為采用Intel Pentium 4的3 GHz(CPU)和1 GB(RAM)的Windows XP操作系統下計算機對三種算法所產生的處理開銷實驗結果。

表4三種密碼系統處理開銷（Intel Pentium 4 3 GHz）

密碼系統加密解密

AES/Rijndael (128 bit key block)32.3 Mbps32.2 Mbps

ECAES1633.17 ms2.25 ms

SHA1161 Mbps hashing

3.3仿真結果

實驗以NS2作為仿真平臺，IEEE802.11 DCF作為MAC層協議，采用tworay ground reflection傳播模型，2 Mbps的信道能力，670 m×670 m的網絡范圍內均勻分布50個節點，節點傳輸范圍為250 m，節點移動采用random way point(RWP)模型，固定CBR模式每秒發送10個包，包大小為512 Byte，源和目的節點對從所有節點中隨機選取，維護5個并發源目的UDP對。

圖3表示基于跳數的路由建立時間的比較。匿名路由建立時，需要每個中間節點花費額外的時間進行加/解密運算，故帶來較大的延時[8，9]。由于ASR和ANODR中每個節點都要產生公／私鑰鍵對每個RREQ分組進行處理，且在試圖解開目的節點陷門時需要嘗試和每個其他節點的共享key，因此M2ASR的路由建立時間低于ASR和ANODR匿名路由，非匿名路由的建立時間最小。圖4表示規格化控制字節的比較。M2ASR采用標簽源路由對路徑上節點的標志進行編碼，大大減少了控制字節。圖5表示UDP吞吐量的比較。由于使用多徑路由，M2ASR成就的UDP吞吐量遠大于ANODR和ASR。但對于TCP連接，因為存在多徑失序問題，吞吐量會嚴重下降，本文未給出具體的仿真結果，有待進一步研究。

4結束語

在多跳環境下的移動自組織網中，路由是其中的關鍵技術，由于無線信道的共享和開放特性，安全的路由設計尤為重要。本文提出了一種新型的多徑匿名源路由協議M2ASR，結合MSR的多徑路由思想執行流量負載均衡，使用IDA算法，充分利用無線網絡資源，對單一路徑失效提供一定的抵抗能力。分析和仿真結果表明，M2ASR協議具有較強的匿名性、快速的路由建立、較少的控制開銷和較高的UDP吞吐量，能夠應用到更大規模的移動Ad hoc網絡當中。

參考文獻：

[1]

ZHU Bo， WAN Zhiguo， KANKANHALLI M S， et al. Anonymous secure routing in mobile Ad hoc networks[C]// Proc of the 29th IEEE International Conference on Local Computer Networks(LCN).[S.l.]:IEEE， 2004:102108.

[2]KONG Jiejun， HONG Xiaoyan. ANODR: anonymous on demand routing with untraceable routes for mobile Ad hoc networks[C]//Proc of the 4th ACM International Symposium on Mobile Ad hoc Networking and Computing (MobiHoc). New York: ACM， 2003:291302.

[3]ZHANG Yanchao， LIU Wei， LOU Wenjing. Anonymous communication in mobile Ad hoc networks [C]//Proc of the 24th International Conference of the IEEE Communications Society(INFOCOM).[S.l.]:IEEE， 2005:19401951.

[4]JOHNSON D B， MALTZ D A， HU Y C， et al. The dynamic source routing protocol(DSR)[S]. [S.l.]:IETF Draft MANET Working Group， 2000.

[5]PERKINS C， BELDINGROYER E， DAS S. RFC 3561， Ad hoc on demand distance vector (AODV) routing[S]. 2003.

[6]LI Layuan， LI Chunlin， YUAN Peiyan. Performance evaluation and simulations of routing protocols in Ad hoc networks[J]. Computer Communications， 2007， 30(8):18901898.

[7]舒炎泰，高德云，王雷.無線Ad hoc網絡中的多徑源路由[J].電子學報，2002，30(2):153156.

[8]LIU Jun， KONG Jiejun， HONG Xiaoyan， et al. Performance evaluation of anonymous routing protocols in MANETs[C]//Proc of IEEE Wireless Communications and Networking Conference. [S.l.]:IEEE， 2006:646651.

[9]MARANDIN D. Improvement of link cache performance in dynamic source routing (DSR) protocol by using active packets[C]//Proc of the 7th International Conference(NEW2AN). Berlin: Springer， 2007:368378.