周永塔
(广东南华工商职业学院 教育技术与信息中心,广东 广州 510507)
随着社会的发展、无线技术的进步,加上人们想要摆脱有线网路的束缚,进行不受时空限制的自由通信,使得无线网络及其相关技术得到了飞速发展。互联网已发展为有线网络和无线网络组成的综合网络。根据无线网络的结构可以将其划分为两类:有固定基础设施的无线网络和无固定基础设施的无线网络[1]。有固定基础设施的无线网络包含大量移动节点(如移动终端)和少量固定节点(如基站),移动节点依靠通信范围内的固定节点进行相互之间的通信[2]。此类网络可以有效地利用现成的固定基础设施(如基站),在固定设施的覆盖范围内进行通信,但其有效通信也仅仅局限于固定设施的覆盖范围以内[3]。有固定基础设施的无线网络的典型代表有无线蜂窝网和无线局域网等。但面对某些特殊的应用场景,有固定基础设施的无线网络将不能胜任[4]。相比传统有线网络和有固定基础设施的无线网络,Ad Hoc网络以其无中心、自组织、动态拓扑、有限带宽、有限能量等特点,使其在许多环境的通信应用中有独特的优势[5]。例如,在军事、应急领域,Ad Hoc网络能满足高灵活性、高抗毁性、高可靠性、高可扩展性等要求;在个人通信领域,Ad Hoc可以实现如手机、Pad、电脑等个人移动通信设备间的通信;在商业应用流域,Ad Hoc网络可以构建家庭网络、移动计算以及移动办公等[6]。因此Ad Hoc网络具有广阔的应用前景。
由于Ad Hoc网络体系结构和其自身特点,使得Ad Hoc网络中的多播比有线网络中的多播要更加复杂。多播路由协议有两种典型的分类方法,第一种方法是按照按需路由和表驱动路由分类;另一种是根据多播数的构造方式将Ad Hoc网络多播路由协议分为四类[7]:基于树的多播路由协议、基于网的多播路由协议、无状态的多播路由协议和混合多播路由协议。表1为几种常见Ad Hoc网络多播路由协议的比较[8-9]。
表1 Ad Hoc网络多播路由协议比较
Ad Hoc网络中多播路由协议的主要思想是用最小的冗余找到多播成员间的通信路径,上述各种协议使用不同的方法来试图达到这个目标。
Ad Hoc网络具有其固有的特点:网络节点的移动性造成网络拓扑结构动态变化、节点终端设备的个体差异以及节点间的无线链路环境受限等,因此Ad Hoc网络中的路由变得复杂且网络的维护开销也较大。为提高Ad Hoc网络的路由综合性能,本文提出了基于链路稳定性的Ad Hoc网络多播路由:将经典的MAODV协议改进为基于链路稳定性的MAODV(Stability based MAODV,SMAODV)协议,SMAODV中提出了“HELLO响应机制”和“主动链路切换机制”,HELLO响应机制用于收集测算链路稳定性和主动链路切换所需的相关数据。
由于链路的稳定性需要收集节点间的传输时延和节点的移动速度等信息,因此将MAODV原有报文均添加了节点的移动速度字段,将RREP报文还添加了链路稳定性向量,将邻居表和多播路由表进行了扩展,添加了HR报文。SMAODV主要包含以下六种报文:RREQ、RREP、MACT、GRPH、HELLO和HR[10]。以下是相关的六个基本定义。
定义1节点间的传输时延td(transmission delay):节点A和节点B通信,A在t1s时刻给B发送信息,B在t1r时刻收到,并在t2s时刻给A发送信息,A在t2r时刻收到信息,则:
(1)
定义2节点间的传输时延差值Δtd:两次相邻的传输时延的差值,该值可能为负:
Δtd=tdnew-tdold
(2)
其中,tdnew表示最新计算出的传输时延,tdold表示前一次的传输时延。
定义3节点的移动速度ms(move speed):在节点发送信息时的移动速度。
定义4节点的移动速度差值Δms:某节点收到另一节点两次相邻的移动速度的差值,该值可能为负:
Δms=msnew-msold
(3)
其中,msnew表示最新收到的节点移动速度,msold表示前一次收到的节点移动速度。
定义5节点间的稳定性向量nv(nodes vector):该向量是一个四元组(td,Δtds,ms,Δmss),用于测算节点间的稳定性,是后续链路稳定性的基础。其中Δtds表示节点间的传输时延差值Δtd的符号位,Δmss表示节点的移动速度差值Δms的符号位。
定义6链路稳定性向量lv(link vector):该向量是一个四元组(TD,ΔTDS,MS,ΔMSS),用于测算链路的稳定性。
为了获得用于测算链路稳定性的链路稳定性向量,首先需要获得节点间的稳定性向量,本文通过“HELLO响应机制”来测算节点间的稳定性。节点定期广播HELLO消息,该HELLO消息中附带自己的移动速度ms和发送该消息的时间t1s。收到HELLO消息的节点则响应HR消息,该HR消息中附带自己的移动速度ms、收到的HELLO消息中的t1s、接收到该HELLO消息的时间t1r和发送HR消息的时间t2s。接收到HR消息的节点,则根据接收到HR消息时间t2s和HR消息中附带的t1s、t1r和t2s来计算自己与响应节点间传输时延td,随后更新邻居表。节点更新邻居表时将邻居传输时延和节点的移动速度设为测算出的td和HR消息中附带的ms,如果节点间是首次进行HELLO响应机制,则将Δtds和Δmss均设为0;否则根据定义5,如果测算出的td小于邻居表中已有的传输时延则将Δtds设为-1,大于则设为1,Δmss同理。通过HELLO响应机制就完成了节点间的稳定性向量的测算。
此外,本文将控制消息均加入了移动速度,所以在收到控制消息时都类似于“HELLO响应机制”一样更新邻居表中的ms和Δmss。后文介绍多播树的构建和维护时就不再介绍邻居表的维护。
非多播树成员想要加入多播组,首先在多播路由表(Multicast Route Table,MRT)中创建表项表明自己是组成员,然后广播RREQ-J消息;多播树成员想要加入多播树,只需要将MRT中自己的身份改为多播组成员。节点通过组头表(Group Leader Table,GLT)检测组头可达性。在RREQ-J的传播过程中节点在单播路由表(Unicast Route Table,URT)中建立至请求的源节点的反向路由。多播树成员具有相同或者更大的序列号的节点,收到RREQ-J则单播回复RREP-J。当节点收到RREP-J时将发送该RREP-J消息的节点在邻居表(Neighbor Talbe,NT)中对应的td、Δtds、ms和Δmss取出,分别累加进RREP-J消息的TD、ΔTDS、MS和ΔMSS,然后继续进行转发。RREP-J沿RREQ-J传播建立的反向路由发送到请求的源节点,RREP-J传播过程中节点在MRT中建立至多播树的正向路由。当请求的源节点在请求等待时间RREP_WAIT _TIME内,如果是首次收到RREP-J消息,则将其存入缓存Cache中;否则将收到的RREP-J与Cache中的对比,如果拥有更新的序列号或者序列号相同但跳数更小或者序列号和跳数均相同但稳定性更好,则用新收到的RREP-J替换Cache中原有的。等待RREP_WAIT _TIME后向Cache中的RREP-J选择的上游节点单播MACT-J消息进行路由激活。每个收到MACT-J的节点在自己的MRT中将该MACT-J的发送节点标明为新的下一跳。如果收到MACT-J的节点是多播树成员节点则加入完成,否则继续向上游转发MACT-J。
如果请求的源节点在等待RREQ_RETRIES后仍未收到任何RREP-J,则意味着网络中无该多播树或网络被分割,则该节点作为组头开始维护多播组序列号和多播树。图1描述了MAODV的路由过程。
图1 MAODV路由过程
由于节点的移动性可能会造成断路,而断路的修复过程将给网络带来较大开销,从而降低MAODV的整体性能。本文在测算节点间的稳定性的基础上,提出了主动链路切换机制,进一步提高SMAODV的整体性能。
如图2所示过程,多播组成员节点2即将离开多播树成员节点A的信号覆盖范围,进入多播树成员节点B的信号范围。当多播组成员节点2离开多播树成员节点A的信号范围后将会发起链路修复过程,经过修复过程多播组成员节点2又会嫁接成为多播树成员节点B的下游节点。然而如果此过程可以提前预见并作出相应的处理便能有效减少链路断开的情况,从而降低链路修复过程造成的开销、降低丢包率等。通过对控制包报文和邻居表的扩展便能提前发现并主动作出处理。主动链路切换机制主要分为三个步骤:危险节点(可能因移动性造成断路的节点)发现、危险节点监控和链路切换。
图2 主动链路切换
(1)危险节点发现。当多播树成员节点在自己的邻居表中存在非多播表中的上游和下游的节点,且邻居表中自己的上游节点的Δtds为1,非上游和下游多播树成员节点的Δtds为-1,则自己成为危险节点,进入危险节点监控。
(4)
图3 节点移动时间测算
(3)链路切换。链路切换包括嫁接和剪枝过程。进入链路切换的危险节点首先进行嫁接,从邻居表中选择非自己的上游和下游节点中Δtds为-1且td最小的多播树成员节点,向其单播RREQ-J消息,收到RREQ-J的节点单播响应RREP-J消息。危险节点收到RREP-J响应后,向原上游节点单播MACT-P消息开始剪枝,将MRT中自己的上游节点改为发送RREP-J的多播树成员节点并向其单播MACT-J消息进行链路激活。
本文采用NS2_2.30对MAODV和SMAODV进行仿真实验,并用以下3个典型的衡量路由协议的技术指标作为考察指标。
(1)数据包转发率(Packet Delivery Ratio)。在多播环境下,计算网络中的数据包在目标节点接收与应收个数,不仅反映数据传送的可靠性能,也反映路由在失效下的稳定性、高效性和持续性。
(2)数据包平均端到端时延(Average End-to-End Delay of Packets)。计算数据包在源节点与目标节点之间的传送时间,通过其可以反映网络拥塞等因素。
(3)路由开销(Routing Overhead)。通过其可以反映在路由出现异常情况下控制包数与数据包数之间负载情况。
SMAODV协议中的相关参数设定如表2所示。
表2 SMAODV参数
本文仿真实验中移动节点的速度采用0 m/s,5 m/s,10 m/s,20 m/s和混合速度五种。其中前四种均可以使用NS2提供的拓扑场景生成工具setdest来随机生成无线网的节点运动场景;但setdest不能满足生成混合速度无线节点运动场景的需求,所以需要手动编写脚本。TCL脚本代码省略,setdest使用命令格式如下:
setdest -v <1> -n
or
setdest -v <1> -n
仿真就数据包转发率、数据包平均端到端时延和路由开销对比说明MAODV和SMAODV运行性能。
(1)多播组成员数对性能的影响。将多播数据发送源节点数设为1,将节点的移动速度设为5。测试结果如表3所示。
表3 不同多播成员数对性能影响测试结果
SMAODV采用基于链路稳定性的路由选择方法以及主动链路切换策略等,减少了控制消息的发送以及断路发生的情况,路径优于MAODV仅根据跳数选择的路径,在数据包平均端到端时延体现出较高的性能。
(2)多播数据发送源节点数对性能的影响。将多播组成员数设为10,将节点的移动速度设为5,测试结果如表4所示。
数据包转发率随着多播数据发送源节点数的增加而降低,同样SMAODV在数据包转发率上体现出高于MAODV的性能。
通过上述两组实验可以得出结论:SMAODV在数据包转发率和数据包平均端到端时延上都优于MAODV,在路由开销上略低于MAODV,所以SMAODV在综合性能上优于MAODV。
表4 多播数据发送源节点数对性能影响测试结果
本文对MAODV协议进行改进,提出了基于链路稳定性的Ad Hoc网络多播路由协议SMAODV。该协议主要包括路由构建和维护过程、主动链路切换策略、HELLO响应机制。通过大量的实验进一步验证了SMAODV协议的综合性能,说明本文提出的基于链路稳定性的Ad Hoc网络多播路由协议具有正确性、可行性和优越性。