降低Ad hoc網絡信息泄露的路由算法

2016-01-08 05:39:47劉玉軍,汪明輝,蔡猛等

計算機工程與科學 2015年6期

降低Adhoc網絡信息泄露的路由算法*

劉玉軍，汪明輝，蔡猛，陳坤

(裝甲兵工程學院信息工程系，北京 100072)

摘要：分析了Ad-hoc網絡信息傳輸過程中信息泄露的途徑和原因，提出了Ad-hoc網絡信息泄露模型，設計了一種降低信息泄露的路由算法RARIL。該算法在加權圖模型的基礎上，加入節點位置信息和身份認證，減少組外節點和組內非信任節點竊聽信息，優先信任節點轉發信息，降低信息泄露概率。通過計算非信任節點信息泄露概率，選擇信息泄露概率最小的節點作為轉發節點，組建可控轉發節點集合，保證集合中轉發節點的信息泄露概率最小。最后，根據算法設計約束條件，以算法性能的主要影響因素設定算法評估指標，通過仿真比較路由算法在降低信息泄露方面的優越性。

關鍵詞：信息泄露；加權圖；位置路由；身份認證；非信任節點

中圖分類號：TN918.91 文獻標志碼：A

doi:10.3969/j.issn.1007-130X.2015.06.009

收稿日期：*2014-05-19;修回日期：2014-09-26

基金項目：軍內科研計劃資助項目

作者簡介:

通信地址：100072 北京市豐臺區杜家坎21號裝甲兵工程學院信息工程系

Address:Department of Information Engineering,Academy of Armored Force Engineering,21 Dujiakan,Fengtai District,Beijing 100072,P.R.China

AroutingalgorithmforinformationleakagereductioninAd-hocnetworks

LIUYu-jun,WANGMing-hui,CAIMeng,CHENKun

(DepartmentofInformationEngineering,AcademyofArmoredForceEngineering,Beijing100072,China)

Abstract:We analyze the approaches and causes of information leakage during information transmission in Ad-hoc networks, design an Ad-hoc network model based on the leaked information, and propose a routing algorithm for information leakage reduction. Based on the weighted graph model, we add the node location information and authentication in order to reduce information eavesdropping by external users and un-trusted users within the group, and to make the information forwarding of trusted users the priority, thus reducing the probability of information leakage. After calculating the leakage probability of the un-trusted nodes, we select the node with minimum probability of information leakage as the forwarding node, and we build a controllable forwarding node set to ensure the minimum probability of information leakage. Finally, according to the constraints of algorithm design, we take the main factors that impact the algorithm performance as the performance evaluation indicators, and the simulation results prove the superiority of the proposed route algorithm in information leakage.

Keywords:informationleakage;weightedgraph;locationrouting;authentication;un-trusteduser

1引言

目前，對Ad-hoc網絡[1]路由協議進行的研究主要集中在提高傳輸性能等方面，如FSR對指定搜索取值范圍外的節點使用不同頻率進行搜索，R-DSDV引入了擁塞控制以減小路由開銷，LANMAR通過添加路標以減少跳數，這些研究[2,3]的主要思路在于共享節點移動信息和網絡流量信息以降低能耗，或是提高網絡遭受惡意攻擊時的健壯性[4]。但是，對Ad-hoc網絡路由安全方面的研究還比較欠缺，尤其是沒有考慮到非目標節點轉發信息帶來的安全性問題。雖然，Ad-hoc網絡節點可以采用加密手段來保護無線信息傳輸，但信息泄露并不能完全避免，信息被竊聽的概率甚至還比較高[5]，因此，需要換個角度研究Ad-hoc網絡路由安全性問題。本文重點研究如何降低被竊聽數據概率，但針對無線電信號直接監聽破譯的情形不在本文研究范疇內。

為了研究降低Ad-hoc網絡信息泄露的路由算法RARIL(RoutingAlgorithmforReducingInformationLeakageinAd-hocNetwork)，本文引入了可信多播TGM(TrustedGroupMulticast)和可信單播CU(ConfidentialUnicast)兩種加權圖模型，并將網絡節點分為四類：單播和多播節點、組內和組外節點、目標和非目標節點、信任和非信任節點。在多播組內的節點稱為組內節點，在多播組外的節點稱為組外節點。目標節點即是指信宿節點，非目標節點指信宿節點外的其它所有節點。信任節點是指網絡內通過安全認證的節點，非信任節點是指網絡內未通過安全認證的節點。根據節點位置信息和身份認證，避開非信任節點轉發信息，達到降低無線網絡信息傳輸泄漏的目的。最后，通過與傳統BFS算法進行比較，表明本算法降低了信息泄露的可能性，提高了信息傳輸的安全性，并且減少了信息傳輸跳數，減少了數據傳輸延遲。

2Ad-hoc網絡信息泄露模型

Ad-hoc網絡在傳輸信息過程中往往要借助多個節點轉發，網絡拓撲結構隨時可能變化，因此選擇轉發節點成為一個難題。Ad-hoc網絡中存在非信任節點和組外節點，若是選擇此兩種節點作為轉發節點，就增大了網絡泄露信息的可能性。因此，可以通過盡可能地選擇信任節點轉發信息，控制和減少使用非信任節點，才能降低信息泄露的概率。

2.1信息泄露與節點屬性

可能泄露信息的節點主要包括組內非信任節點和組外節點。信息泄露途徑主要有三個：(1)信息在組內節點之間轉發時，不判別非信任節點，導致信息經由非信任節點轉發，造成信息泄露；(2)組內節點在轉發信息時，由于缺乏組內其它節點的位置信息，不能分辨組外節點，為了選擇較短路徑，借助了組外節點轉發信息，導致信息泄露；(3)節點不能分辨非信任節點和組外節點，信息傳遞過程中，經過組內非信任節點和組外節點，造成信息泄露。可見，信息泄露的原因在于轉發節點不區分組內非信任節點和組外非信任節點，信息經過此類節點轉發極易造成信息泄露。因此，需要引入節點認證和位置信息來減少此類節點的使用，達到降低信息泄露概率的目的。

節點進行身份認證的情況主要有兩種：第一種情況，路由選擇時，節點選擇下一轉發節點，需要對下一轉發節點進行身份認證，若是通過身份認證，則選其作為轉發節點，否則尋找其它轉發節點；第二種情況，當組外其它節點需要加入組時，需要進行身份認證，通過認證的節點可以加入，未通過身份認證的節點則被拒絕，有效地防止了組外節點作為轉發節點參與信息傳輸。

為了提高數據分組投遞成功率，路由時加入節點位置信息，一方面有利于最佳路徑的選擇，另一方面有利于替換非信任節點時根據位置信息在鄰居節點中就近選擇新的節點。節點的物理位置信息需要通過GPS或者其他定位技術獲取[6]，也有學者提出不使用坐標位置信息，而使用節點之間的相對位置關系[7]。該算法基于上述節點物理位置信息或者節點相對位置關系進行本地計算，每個節點的路由選擇根據數據包中包含的目的節點位置和轉發節點的鄰居節點位置加以決定。本文目的是研究減少信息泄露問題，直接使用節點位置信息，但是位置信息的獲取不在本文的研究范圍內。

2.2路由算法設計約束條件

路由算法設計目標是讓信息以盡可能小的延遲安全交付。最理想的情形是最短路徑完全由可信任節點組成；第二種情形是完全由可信任節點組成的傳輸路徑，但不是最佳路徑；第三種情形是信息傳輸用最短路徑，但為了實現最短路徑，采用非信任節點參與轉發。第一、二種情形都是比較理想的狀態。現實中，由于信息通達的要求，不得不使用非信任節點轉發出現的情形難以避免。因此，為了減少節點信息泄露的概率，必須計算參與路由轉發節點的泄露概率，如果泄露概率高，則需另外選擇轉發節點，再重新尋找傳輸路徑并計算其泄露概率，實現在最短路徑和最安全路徑之間的折衷。

路由算法引入節點位置信息和身份認證兩種約束進行路徑選擇。利用位置信息發現最短路徑，減小路由開銷；利用身份認證判斷非信任節點，使信息被非信任節點和組外節點竊聽到的概率降到最低，從而及時地將信息傳遞到目的節點。

2.3降低信息泄露的圖模型

為了探究各類信息傳輸節點之間的關系和泄露途徑，通過引入圖模型的方法對信息泄露進行分析。圖模型的符號定義見表1。

Table 1　 Definition of symbols in model figures

假設加權圖[8]為G(V，E)：V、E是基本元素，V代表點的集合，即節點集合；E代表鏈路集合，如果兩個節點之間能相互通信，那么兩者之間存在一條鏈路。定義wi,j為鏈路ei,j的權重，ei,j可以是有向或無向，若鏈路ei,j不存在，則認為wi,j=0。

(1)

路由算法設計約束條件可表示如下：

(1)VD∈GR，且min(D(v0，VD))。目標節點屬于可能獲取信息的集合，即目標節點可以接收到信息，且從v0到VD中節點的最大跳躍距離最小；

按照以上約束條件構造的圖模型[9]，如圖1所示。可以得出非信任節點VA與v0、VD、VO、VR無交集，即盡可能地減少信息轉發范圍內的非信任節點數。VA與GR有交集，說明信息在信源與信宿之間傳遞的過程中，仍然存在中繼節點VR將信息泄露給組外節點VO或者非信任節點VA，即仍存在非信任節點竊聽節點信息的可能性。

Figure 1　Model figure of information leakage 圖1　信息泄露圖模型

在圖1所示的信息泄露模型中，信源v0往目的節點VD傳遞信息的路徑有兩條，第一條路徑是信息直接由v0傳遞給VD，中間不存在轉發節點VR轉發信息，因此，不存在信息泄露；第二條路徑是信息首先由v0經過轉發節點VR傳遞給組外節點VO，以VO為中繼再把信息通過VR傳遞給目的節點VD，由于信息經由轉發節點傳遞，期間可能發生信息泄露。信息泄露有兩種可能，第一種是信息由信源v0經過轉發節點VR直接被非信任節點VA獲取，另一種是信息通過轉發節點轉發給組外節點VO的過程中，非信任節點VA通過VO間接獲取信息。

通過加權圖模型可以看出信息泄露的途徑，根據加權圖模型加入節點位置信息，節點根據位置信息選擇信息傳輸路徑，盡量避開組內和組外的非信任節點，使用通過身份認證的節點作為轉發節點VR，提高網絡協議的安全性，降低信息泄露的概率。

3Ad-hoc網絡降低信息泄露路由算法RARIL

在設計減少Ad-hoc網絡信息泄漏路由算法時，為了比較清楚地區分非信任節點、組外節點、目的節點和其他轉發節點的關系，可以假設把非信任節點集合、組外節點集合、目的節點集合單獨列出，通過其他轉發節點和三個集合的連線表示相互之間的關系。按照此方法建立的最優化圖模型如圖2所示。圖2中集合S是從圖1中取出的非信任節點集合、組外節點集合目的節點集后的部分。VA和VS、VO和VS、VD和VS中兩個節點連線都是E中的邊。

Figure 2　Model figure of optimization 圖2　最優化圖模型

Table 2　Definition of symbols in routing algorithm

加入位置信息后，節點通過獲取其它節點位置信息，形成組內節點的拓撲結構，根據網絡拓撲信息找到信息傳遞的最短路徑。為了增加信息傳遞的安全性，通過身份認證[10]判斷轉發節點是否可靠，根據反饋信息決定路由轉發節點。由此可以選擇組內信任節點有選擇地轉發信息，降低信息泄露的概率。

為了降低信息泄露的概率，需要根據轉發路徑最短、是否通過身份認證和信息泄露概率最小三個原則選擇轉發節點，算法分為五個步驟：

步驟1按照最短路徑的目標進行路由選擇，記錄路由跳數，把選擇好的轉發節點添加到VRi(i為尋路次數，即路徑條數，初值為1)中；

(3)

(4)

步驟3設定泄露概率判決門限α。對于步驟2發現的非信任節點和組外節點，如果該節點泄露概率小于α，則可以使用該節點參與轉發，繼續執行步驟2，直到計算和比較完VR中所有非信任節點和組外節點的泄露概率；如果泄露概率大于α，則需在鄰居節點中就近選擇轉發節點替換該節點。

步驟4i自增1，令VRi等于VR(i-1)，將該泄露概率較大的非信任節點(或組外節點)從VRi中移除，以非信任節點(或組外節點)在轉發路徑的上一節點為起點，重新根據位置信息就近選擇轉發節點并添加到VRi，記錄路由跳數，判斷是否存在非信任節點(或組外節點)，即重新從步驟2開始執行。

步驟5對比重新計算得出的不同轉發路徑，以路由跳數和信息泄露概率之和最小，確定安全有效傳輸路徑。

最終得到網絡傳輸延遲和信息泄露概率最小的轉發路徑，這是最短路徑和最安全路徑之間的折衷。

4路由算法評估

4.1算法性能評估

為了驗證路由效果，根據算法設計約束條件，以影響算法性能的主要因素為依據設定路由算法評估指標，對算法進行評估。影響算法性能的主要因素包括信源到信宿的最大跳數、非信任節點竊聽信息概率和組外轉發節點的數量。以此三項因素作為評估指標，對算法的影響如下：

(1)D(v0, VD)，v0和VD中目標節點之間參與信息轉發的節點數量是度量路由性能的一項標準。一方面，通過在算法中加入節點位置信息，節點根據位置信息進行尋路，理論上可以減少路由跳數；另一方面，降低信息泄露概率不能以延長信息傳輸路徑為代價，且轉發節點數量越少，非信任節點出現的可能性越低。

(3)|VO∩VR|，信息通過組外節點進行傳輸時，組外轉發節點轉發信息是造成信息泄露的又一主要原因。因此，可以作為路由算法性能評估的另一指標。

4.2算法仿真分析

根據算法性能評估要求，對改進的RARIL算法進行仿真，并與BFS算法[12,13]進行比較。

Figure 3　Simulation of the nodes deployment 圖3　節點部署仿真圖

仿真對比分析結果分別如表3、表4和表5所示。

Table 3　Comparison among max-hop simulation results

表3所示為BFS算法和RARIL算法信息傳輸最大跳數仿真結果，BFS算法最大跳數為8，RARIL算法最大跳數為7。可以看出，改進的算法縮短了分組轉發路徑。

Table 4　Simulation result comparision of the

表4所示為BFS算法和RARIL算法中非信任節點傳遞信息造成的信息泄露概率。可以看出，RARIL算法的泄露概率低于BFS算法的信息泄露概率，算法在降低非信任節點信息泄露方面有提高。

Table 5　Simulation result comparison

表5顯示的是BFS算法和RARIL算法中，組內非信任節點數和組外轉發信息節點總的節點數。可以看出，BFS算法可能造成信息泄露的節點數高于RARIL算法，RARIL算法在減少組內非信任節點和組外轉發節點方面有明顯提高。

5結束語

本文分析了Ad-hoc網絡轉發信息過程中造成信息泄露的原因，探討了算法設計約束條件，構造了一種涵蓋可信單播和可信多播模型的加權圖模型，根據圖模型分析了信息泄露的途徑。為了控制和減少信息泄露途徑，本文設計了基于位置信息的路由選擇算法RARIL，通過加入位置信息，提高路由轉發效率，同時減少組外節點對信息的竊聽可能性；通過對節點進行身份認證，減小了非信任節點對信息的竊聽概率。最后，通過與傳統的BFS算法仿真比較，驗證了RARIL算法在降低信息泄露概率的同時并沒有過多增加網絡延遲，而是在兩者取折衷值，在路由安全方面更具優勢。

參考文獻:

[1]Chen Lin-xing, Zeng Xi, Cao Yi. Mobile Ad hoc network[M]. Beijing:Electronic Industry Press,2012.(in Chinese)

[2]Pham V, Larsen E, Ovsthus K, et al． Rerouting time and queuing in pro-active Ad Hoc networks[C]//Proc of IEEE International Performance on Computing and Communications, 2007:160-169.

[3]Liang B, Haas Z J. Hybrid routing in ad hoc networks with a dynamic virtual backbone[J]. IEEE Transactions on Wireless Communications, 2006,5(6):1392-1405.

[4]Singh A, Vaisla K S. A mechanism for detecting wormhole attacks on wireless ad hoc network[J]. International Journal of Computer and Network Security, 2009,2(9):27-31.

[5]Cui Yong-gang, Liu Yu-jun. Public verifiable short key of encryption scheme[J]. Journal on Communications, 2010,31(3):44-50.(in Chinese)

[6]Mauve M, Widmer J, Hartenstein H. A survey on position based routing in mobile ad hoc networks[J] . IEEE Network, 2001,15(6):30-39.

[7]Rao A, Ratnasamy S, Papadimitriou C, et al. Geographic routing without location information[C]//Proc of MobiCom’03, 2003:1.

[8]Zhang Ji-zan,Li Hong-bo,Wang Feng.Ad Hoc network routing policies of weighted reliable[J]. Computer Engineering and Applications, 2007,43(35):140-145.(in Chinese)

[9]Cheng Wei, Wu Deng-yuan, Cheng Xiu-zhen. Routing for information leakage reduction in multi-channel multi-hop Ad-hoc social networks[C]//Proc of WASA’12, 2012:31-42.

[10]Guo Ping. Wireless network authentication architecture and related technology research[D]. Nanjing:Nanjing University of Science and Technology, 2012.(in Chinese)

[11]Shen Chang-xing. Mobile Ad Hoc network routing protocol based location[D]. Beijing:Beijing University of Posts and Telecommunications, 2006.(in Chinese)

[12]Yang Ai-min. Parallel breadth-first search algorithm[D]. Xi’an:Xidian University, 2012.(in Chinese)

[13]Qiang Yan, Lu Jun-zuo, Liu Tao, et al. HBase based par-

allel BFS method[J]. Computer Science, 2013,40(3):234-237.(in Chinese)

參考文獻：附中文

[1]陳林星,曾曦,曹毅.移動Ad hoc網絡[M].北京：電子工業出版社，2012.

[5]崔永剛,劉玉軍.可公開驗證的短密鑰公鑰加密方案[J]. 通信學報, 2010,31(3):44-50.

[8]張吉贊, 李洪波, 王峰. Ad Hoc 網絡的加權可靠路由策略[J]. 計算機工程與應用, 2007, 43(35):140-145.

[10]郭萍. 無線網絡認證體系結構及相關技術研究[D]. 南京：南京理工大學, 2012.

[11]沈長星. 基于地理位置的移動 Ad Hoc 網絡路由協議研究[D]. 北京:北京郵電大學, 2006.

[12]楊愛民. 并行廣度優先搜索算法研究[D].西安：西安電子科技大學,2012.

[13]強彥, 盧軍佐, 劉濤, 等. 基于HBase的并行BFS方法[J]. 計算機科學, 2013,40(3):234-237.