降低Ad hoc网络信息泄露的路由算法

2016-01-08刘玉军,汪明辉,蔡猛等

计算机工程与科学 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.