一种多传感器网络的路由空洞解决策略

一种多传感器网络的路由空洞解决策略

0基于局部转发策略的节点自身改进无线通信网络是一个由大量传感器节点组成的多段自组织网络系统。它在军事研究、环境评估和灾难救援等领域具有广阔的应用前景。贪婪地理路由协议是无线传感器网络路由协议中的重要一类,它利用节点的地理位置信息作为路由依据,使用贪婪转发策略进行数据包传递。当网络节点密度较低或出现不可抗拒的地理因素(大的障碍物、池塘等)时,贪婪转发策略找不到合适的下一跳节点,便出现了路由空洞,有些文献称之为局部最优化现象。GPSR协议中,采用基于右手法则的边界转发配合贪婪转发,以达到整个路由算法收敛的目的。本文对GPSR协议中的边界转发进行改进,将右手法则与左手法则相结合,提出了一种数据包的分区边界转发策略。该策略能够以较小的控制开销代价,提高了数据包投递成功率,减少路由跳数,并提高了贪婪地理路由协议的实时性。1路由控制算法路由空洞是贪婪地理路由协议中必须面对和解决的问题,除了增大节点发射功率、补充移动节点、丢弃分组等简单的解决策略外,国内外学者也相继提出了一些空洞处理算法。当遇到路由空洞时,GRA启动路由发现机制搜索从空洞节点到目的节点的路由,一旦收到路由回复消息,即在路由表中保存该路由条目。当路由空洞在数据转发中出现过早时,该方法就衍变成与AODV、DSR类似的基于链路状态的表驱动路由协议。此外,路由发现机制是通过向全网泛洪探测分组来实现的,控制开销较大。反馈避免算法(如SPEED)利用先前探测分组或数据分组的传输遇到空洞的先验知识,帮助后续数据分组避绕路由空洞,以此提高路由空洞处理效率,降低数据传输时延。该类算法的控制过程繁琐,时空复杂度高,对单个节点的处理能力要求较高。路标引导算法在数据分组发送之前,通过探测分组来获得路由空洞的信息,并提取一些地理路标指引数据分组在传输过程中避开空洞。因为要记录从源节点到目的节点的经历节点,当网络规模较大,算法的存储和控制开销将急剧增大。2b边界转发aGPSR协议使用边界转发策略处理路由空洞问题,其过程为:a)对节点的邻居表进行图的平面化处理(去除交叉边);b)从贪婪失败节点开始,利用右手法则依次计算下一跳节点,直至数据包到达目的节点或返回贪婪转发模式;c)在边界转发过程中,判断是否发生循环遍历,以此决定是否将数据包丢弃;判断即将遍历的边与目标节点和贪婪失败节点的连线是否相交,以此决定是否进行转发平面的切换。本文对该转发过程进行改进,将左手法则和右手法则结合使用,根据下一跳节点的位置对数据包进行分区转发,以此来减少路由跳数,缩短转发路径。2.1改进的分区边界转发过程如图1所示,x为贪婪失败节点,D为目的节点;连接x、D作虚连接xD¯¯¯¯¯xD¯,将原平面化图划分为两部分。定义沿向量xD方向,左侧区域为右手法则区,右侧区域为左手法则区。对原边界转发协议中的步骤b)改进如下:a)以x节点为起点、xD¯¯¯¯¯xD¯为起始边,使用右手法则计算下一跳节点(也可选择使用左手法则)。b)若下一跳节点位于右手(左手)法则区,则使用右手(左手)法则进行边界转发。c)若在进入右手(左手)法则区后没有找到可达路径,数据包会在右手(左手)法则的作用下返回x节点,此时在x节点处再使用左手(右手)法则,进入左手(右手)法则区寻找路由途径。d)在分区边界转发过程中,比较当前节点和贪婪失败节点距离目标节点的远近,若当前节点更近,则返回贪婪转发模式。由此,改进后的分区边界转发过程如图2所示。图中e0为数据包遍历到当前平面记录的第一条边;Lf为数据包进入当前平面时与xD¯¯¯¯¯xD¯的交点。2.2分区转发策略下面给出一个运用分区边界转发策略而避免绕远的实例。数据包在x节点贪婪转发失败,转换为边界转发模式。明显地,数据包由a点直接转发至e点,转发路径最短,传输时延最小。但图3中使用的原边界转发策略只依赖右手法则,所以从x节点开始,数据包的转发路径为(x→a→b→c→d→e→f→g→D),大大绕远。图4使用分区边界转发策略,首先在x节点使用右手法则计算下一跳节点,发现下一跳节点位于左手法则区,故由x节点开始使用左手法则进行转发。最后,数据包沿(x→a→e→f→g→D)最优路径转发至目的节点,有效解决了绕远问题。2.3算法的特点1互补点对于原接面质图的影响该策略只在区域划分时增加了一条虚连接(xD¯¯¯¯¯)(xD¯),将原平面化图划分为两个互补的子集,既不会造成连接边的遗失,也不会破坏图的连通性;另外,左、右手法则分别在两个互补子集区域内使用,可以保证对全图的完全遍历,即如果存在可达路径,使用该策略一定可以找到。2包气成分配路径通过图3和4实例对比可以看出,在原边界转发策略下,数据包的转发路径为(x→a→b→c→d→e→f→g→D);而使用分区边界转发策略后,转发路径为(x→a→e→f→g→D),有效缩短了路由长度。3节点计算复杂度对比与反馈避免、路标指引等其他解决空洞问题的复杂方法相比,该方法只在原边界转发协议的基础上稍加改进,将左手法则与右手法则进行了有效结合,几乎没有增加节点计算的复杂度,可谓简洁、轻巧。3模拟与结果分析3.1网络信标验证本文采用OPNETModeler14.5网络仿真器对原GPSR协议和改进后路由协议进行建模仿真。网络模型由50个节点组成,每个节点的通信范围为250m,均在范围为1500m×300m的矩形区域内移动。移动节点采用randomwaypoint模型,移动速度在0～20m/s内随机选择,暂停时间分别设为0,30,60,120s。在900s的仿真时间中,全网所有节点以1个/s的恒定速率广播8Byte大小的信标;随机选取30个节点作为CBR源节点,以4个/s的恒定速率发送64Byte大小的数据包。为比较改进前后转发策略的性能,选取以下三个评价路由协议的关键指标进行数据收集和结果分析:a)控制开销。仿真时间内,网络中所有节点广播信标的总量。b)数据包投递成功率。成功接收的数据包总数占总发送数据包数的百分比。c)路由长度。投递成功的数据包从源节点到达目的节点所经过的节点个数,即跳数。3.2模拟结果1改进的协议从图5中可以看出,由于节点的信标周期固定,信标传输量与节点移动性无关。与原GPSR协议相比,改进后的协议同样采用了周期性发送信标的方法维护节点的邻居表,且信标周期相同,所以两者的全网信标传输量,即控制开销相同。不同于DSDV等表驱动协议要进行信标的全网广播,在GPSR协议中,各个节点只需要周期性地向周围节点发送生命周期为1的信标来维护本节点的一跳邻居表,所以控制开销小。2改进的分区转发策略从图6中可以看出,当网络的移动性较弱(暂停时间为60s和120s)时,两种策略下的数据包投递成功率相差无几;而当网络的移动性较强(暂停时间为0和30s)时,改进后的协议略占优势。这是由于分区转发策略缩短了边界模式下的转发路径,故缩短了数据包投递时间;在移动性强的网络中,投递时间越短,网络的拓扑结构变化越小,数据包投递成功率自然越高。3消除了原协议的边界转发策略从图7中可以看出,两种策略下的数据包平均跳数均随着暂停时间的增加而减少。这是由于随着网络移动性的降低,网络拓扑结构稳定性增加、转发路径选择准确率提高带来的效果。从图中还可看出,与原协议相比,改进后的协议无论在网络移动性强还是弱的情况下,数据包的平均跳数均有所减少。这是由于分区边界转发策略有效解决了原协议中存在的绕远问题,缩短了路由长度。与此同时,路由协议的实时性也随之提高。4改进的分区转发策略GPSR是一种经典的贪婪地理路由协议,采用基于右手法则的边界转发策略处理路