基于最小连通支配集的CRL分发系统研究*

高申勇 ，张 颖 ，戴国骏

(1.浙江水利水电专科学校计算机与信息工程系 杭州310018；2.杭州电子科技大学计算机学院 杭州 310018）

1 引言

PKI（public key infrastructure，公钥基础设施）是一种普遍适用的网络安全基础设施。目前，PKI通常用来解决有线网络的安全问题，随着无线网络的迅速发展，网络安全成为一个关键问题，它关系到整个网络底层运行的可靠性、正确性以及网络上层应用的保密性、完整性、可认证性和不可否认性。近年来PKI正在被无线网络所采纳，将PKI技术应用于无线网络已经成为发展趋势，且已初步形成无线 PKI标准[1,2]。而证书撤销是PKI中一项关键操作，撤销的证书信息保存于 CRL（certification revocation list，证书撤销列表），如何分发CRL，使得用户能及时获取最新证书撤销信息是PKI应用面临的重要问题之一。

目前CRL分发有基于“推”方式的服务器主动分发和基于“拉”方式的服务器被动分发。“推”方式，即每当CRL文件更新时，CA（certification authority，认证机构）将最新的CRL“推送”给所有相关的用户；采用“拉”方式时，仅当用户的当前CRL文件过期时才主动向CA“拉取”最新的CRL文件。与“拉”方式相比，“推”技术能使CA更及时主动地分发最新CRL，同时较好地避免由于大量用户同时访问服务器造成的负载过重问题，因此“推”方式更适合于能量有限的无线网络。

在无线网络中，实现全网广播分发的最基本的途径是“洪泛”，但通过“洪泛”进行广播容易引起广播风暴，为此通常在广播中寻找最小化参与转发节点数，本文基于最小连通支配集算法分发方法，构造虚拟骨干网络进行广播，一定程度上缓解了广播风暴，避免了大量的传输冲突和碰撞，提高了网络的吞吐量，从而保证网络中的节点及时收到CRL文件。本文的研究结果对无线网络下CRL分发具有一定的理论参考价值和实际应用价值。

2 分发协议设计

本文设计的广播协议属于应用层协议，位于传输层之上，下层协议为其提供服务。协议作如下假定。

·该协议运行于具有全分布式平面结构无线网络内。

·一段时间内，网络都为连通且处于不移动状态，节点采用无向天线。

·无线信道为网络中所有节点共享，MAC协议采用类似IEEE 802.11标准的随机信道访问协议；并且假设通信链路为双向，所有数据分组能按顺序到达目的节点。

协议设计分为两个阶段：广播树构造及沿着广播树传输文件。广播树构造是该协议设计的核心，也是文件传输基础。首先，源节点与相邻节点交换Hello分组，获得2跳网络拓扑信息，利用贪婪集合覆盖算法 （greedy set cover algorithm）[3]，在1跳邻节点集合中，反复地选取那些覆盖最多2跳邻节点数量的节点作为下一步用于转播文件的转播节点，重复该过程，直到所有2跳邻节点都被覆盖，最终由转播节点形成一棵广播树，沿着这个广播树传输文件，将文件广播至所有终端用户。

2.1 数据结构和报文格式

为了实现广播树构造，每个节点都需维护一个重复消息表和一个消息缓存区、节点标识、是否获知1跳邻居标识、转发节点集合以及二步邻接表。具体描述如下。

重复消息表(duplicate_message_table)：记录节点接收到的广播消息内的源节点地址和消息标识；当节点收到广播消息时，首先检查重复消息表。

消息缓存区(message_buffer)：由动态数组组成，临时存放接收到的若干个广播消息。

节点标识(node_identifier)：用来标识节点为转播节点或普通节点，每个节点初始状态赋为普通节点。

是否获知1跳邻节点信息 (get-one-hop)标识：为每个节点分配布尔变量，标识节点是否获得或正在获得其1跳范围内的邻居信息，True表示已获得或正在获得邻居信息，否则为False。

转发节点集合(forward_node_set)：存放转播节点的集合。

二步邻接表(two_hop_adjacency_list)：每个节点维护一个二步邻接表，记录邻居节点信息以及相邻节点的邻居信息。

2.2 广播树构造

广播树构造是整个协议的核心，如何获得2跳邻节点信息是广播构造树的关键步骤，本文参考AODV路由协议[4，5]，采用定时器策略实现节点等待邻居信息，若超过定时器设定的合理等待时间，相邻节点未回复，则认为此节点与它不相邻。根据获得的2跳邻节点信息，每个源节点执行贪婪集合覆盖算法计算1跳邻居中哪些节点为转发节点，所有的转发节点组成了最小连通支配集，也为广播树中的非叶子节点，普通节点构成叶子节点并直接相连于一个非叶子节点。广播树的具体构造过程如下所示。

（1）源节点向其邻居广播 RREQ（user request）分组用于发现广播树路由，分组中跳计数（hop count）初始化为0，启动定时器用来等待收集2跳邻居节点集；定时器开始计时。

（2）当节点接收到RREQ分组，首先检查重复消息表，若为重复消息，不再进行转发，并抛弃该分组；否则，更新重复消息表及RREQ分组，将hop count增加1。

（3）判断 hop count的值，若为 1，设置 get-one-hop 为True，转发更新后的RREQ分组，同时设置合理的时延启动定时器；否则，不再转发RREQ分组，仅回复路由应答分组 RREP（user reply）。

（4）当节点收到 RREP分组，更新 RREP分组，判断hop count值，若为0，提取 RREP信息，将RREP保存到二步邻接表的邻居节点列表内，如果定时器到零，回复RREP，否则，继续等待RREP；若为1，将其保存到二步邻接表中的邻居节点列表及相邻邻居节点列表中。

（5）判断定时器是否到零，为零时，计算转播节点，并向其邻居广播Join分组；否则，继续等待RREP。

（6）当节点收到Join分组后，提取转播列表。若包含该节点，则设置节点为转播节点，并且提取邻居节点信息，将其保存到二步邻接表中的邻居节点列表；否则，抛弃该数据包，设为普通节点。

3 分发系统设计

利用设计分发协议来开发一个CRL文件快速分发系统，实现CRL文件的快速“推送”功能，如图1所示。本系统要求能够实现CRL文件快速地传输到每一个请求的终端。具体功能设计如下。

·生成种子文件功能：对文件进行分块，并且分别对每一块进行散列运算；

·广播树构造功能：按照控制消息构造广播树；

·数据分组广播功能：填充协议头部，构造UDP（user datagram protocol,用户数据报协议）广播分组；

·数据分组转发功能：解析接收到的数据分组的头部，并按照解析的结果和相应的规则转发该数据分组；

·数据分组存储功能：登记每个收到的数据分组，生成块位图和子块位图，同时缓存数据分组，缓冲区满后再将数据转存入磁盘文件。

系统功能模块如图2所示。

4 模拟实现与性能评估

本文采用网络模拟器NS-2作为实验的仿真平台，进行模拟并分析其性能。NS-2支持从数据链路层到应用层的各种网络协议的模拟，如以太网协议、TCP、FTP等，可以用于路由协议、传输协议、多播协议、应用协议等的研究。当前NS-2已被用于移动自组网路由协议性能的评估中[6,7]。模拟网络中共有Node_num个节点，整个实验场景的区域为长为Length、宽为Width的平面区域。具体模拟参数及协议参数如表1所示。

表1 广播协议模拟参数设置

（1）传输成功率

传输成功率定义为实际收到的有效消息个数与应接收的消息个数之比，即DR=RXusr/(TXsrc(Node_num-1))。其中，RXusr是用户实际接收到的非重复的广播消息个数，TXsrc是广播源产生的广播消息总数，Node_num是节点总数。传输成功率反映了广播协议的可靠性或鲁棒性。显然，0≤DR≤1。

（2）传输开销

传输开销为传输一个用户消息时平均每个节点的开销，即 DC=TXall/(TXsrc·Node_num)。其中，TXall是运行过程中所有节点发送的消息总数，包括广播消息和广播协议的控制消息。本文考虑了节点的发送开销，而未计入接收开销。由于发送操作要占用网络带宽，因此在计算传输开销时主要计入节点的发送开销。

（3）传输时间

传输时间为源节点分发一个文件到全网所有用户的传输时间，包括广播树构造时间和文件传输时间。其中模拟实验中文件大小为255 byte。

利用NS-2中的场景生成程序随机产生一个网络，在网络上分别运行模拟程序100次得到统计平均值。令等待2跳邻居节点信息的定时器T的值分别取0.08 s、0.15 s和0.22 s，模拟结果如图3～5所示，网络和协议的其他参数均取缺省值。

由图 3可知，T值设置越长，传输成功率（delivery ratio）越高，主要由于源节点有相对足够的时间等待接收所有的2跳邻节点信息，但却增加了一定的传输开销（delivery cost），如图4所示；另外，T值对网络节点少的传输成功率影响不大，但是随着节数增加，若T值设置较短，会导致源节点可能无法收到离它较远的节点信息，因此传输成功率下降，但因为执行转播操作的时间较短，传输开销较低。

如图5可知，T值对传输时间有影响，一般情况下，T值设置越长，传输时间增加，但是能保证较高的传输成功率而且传输时间也较短，例如，当T=0.22 s时，全网60个节点收到包含255 byte的文件只需6 s。

由以上仿真结果表明，定时器值的设置对传输成功率、传输开销和传输时间这3个主要性能指标有一定的影响。当合理设置定时器等待时间时，不仅能适应节点较多的网络，而且保证较好的传输率、较低的传输开销及较短的传输时间。

5 结束语

无线网络是一种具有重要应用价值的网络，其网络安全仍是一个全新的问题，通过PKI可在一定程度上解决该问题，如何使用户及时获取最新CRL是PKI应用面临的主要问题之一。因此，研究无线网络下CRL分发方法具有一定的理论及应用价值，本文设计了一个基于最小连通支配集算法分发方法的分发协议及CRL分发系统，并利用NS-2对协议进行模拟仿真分析其性能。本文研究的CRL分发系统是一个比较理想的系统，系统假设各节点的数据传输都是可靠的，对于数据分组丢失处理和数据分组重传问题考虑不够，有待进一步研究和完善。

1 ISO/IEC 8802-11.IEEE Standard for Wireless LAN Medium Access Control and Physical Layer Specifications,1999

2 WAP Public Key Infrastructure Specification. Wireless Application Protocol Public Key Infrastructure Definition.http://www.openmobilealliance.org/tech/affiliates/LicenseAgreement.asp?DocName=/wap/wap-217-wpki-20010424-a.pdf,2001

3 Lim H,Kim C.Flooding in wireless ad hoc networks.Computer Communications.2001,24(3-4):353～363

4 王金龙，王呈贵，吴启晖.Ad Hoc移动无线网络.北京：国防工业出版社，2004

5 任智.移动Ad Hoc网络路由算法及协议研究.电子科技大学博士学位论文，2005

6 Das S R,Perkins C E,Royer E M.Performance comparison of two on-demand routing protocols for ad hoc networks.Proceedings of IEEE INFOCOM,Israel,2000

7 Maltz D A,Broch J,Jetcheva J,et al.The Effects of on-demand behaviorin routingprotocolformultihop wirelessad hoc networks.IEEE Journal on Selected Areas in Communications,1999,17(8):1 439～1 453