基于改进BERS算法的移动自组织网络能耗及时延优化

宋国平

（吉林广播电视大学远程教育技术中心，吉林 长春 130022）

0 引言

MANET依靠移动节点的合作来动态建立通讯路由［1－3］，因为节点一般是由电池供电的，能源和时效对 MANET 尤为重要［4－5］.

为了节省MANET的能量消耗及降低时延，人们提出了许多路由方案，典型的分层架构是通过聚类结构实现的，例如，文献［6］提出了一种高度聚类启发式算法，基于节点到其他节点的距离计算节点度，该方法存在一个很大的缺点，它没有在任何聚类中限制节点数目的上限，严重影响了聚类的吞吐量和稳定性.文献［7］提出一个最低ID聚类启发式算法，它为每个移动节点安排一个唯一ID，选择最低ID的节点作为聚类头节点，该方法的吞吐量比高度聚类方法好，然而，有较小ID的节点往往反复选为聚类头节点，这可能会很快耗尽电池电量.文献［8］提出了分布式聚类算法和分布式移动自适应聚类算法，也称为节点加权启发式算法，启发式评估每个节点作为聚类头节点的适宜性，并安排对应的节点权重，然而，一个节点必须等到它所有邻居的应答才能确定是聚类头节点还是聚类成员.文献［9］中研究了负载均衡聚类，它相信一个聚类能处理的移动节点数目有个最优值，当聚类太大或太小时将相邻聚类合并在一起或者分离某个聚类.文献［10］提出一种加权聚类启发式算法，合并了聚类的各种指标，如连接到聚类头节点的节点数目、发送功率、移动性和节点电源能量，遗传算法和模拟退火算法已经改进了这个方法.阻塞扩展环搜索（Blocking Expanding Ring Search，BERS）和加强阻塞扩展环搜索（BERS＊）是近期为MANET 开发出的2个路由发现协议［11－12］.相比ERS和BERS，BERS＊在能源时效方面能获得了更好的整体性能.BERS和BERS＊均使用一个追包，在BERS中为STOP，在BERS＊中为END，用于发现路由节点后终止泛洪［13］.为了讨论方便，后续称BERS中的STOP或BERS＊中的END为STOP／END指令.STOP／END指令只能由BERS和BERS＊中的源节点发出，源节点直到第一个路由应答（RREP）到达后才能发出STOP／END指令，即没有因等待RREP所引起的延迟就不能发出STOP／END指令［14］.

基于上述分析，为了更好地降低时延和节省能耗，本文提出了基于路由节点泛洪终止的阻塞扩大环搜索方案，一旦发现路由节点就可以发送STOP／END指令，而不是等待源节点发送STOP／END指令，路由节点也可以参与发送STOP／END指令终止泛洪，仿真实验验证了所提方案的有效性及可靠性.

1 相关工作

1.1 扩展环搜索

ERS是一个寻找源节点和路由节点之间路由的有效方法，路由节点也称作目的端或能提供到目的端路由信息的节点.作为一个受约束的泛洪技术，ERS频繁地用在反应式路由协议中，通常从一个预定义的小搜索区域开始，如果没有发现路由节点ERS在一个每次扩大的搜索区域内从源节点执行新搜索，这个增量式搜索过程一直持续到发现路由节点或达到最大搜索区域.ERS中的泛洪搜索涉及在连续和中继方式下经由中间节点的重播，就像一个逐渐扩展的搜索区域，环到环、从小环到大环.

ERS中的源节点初始化泛洪并控制每个扩展泛洪的搜索区域及最大搜索区域，有2个控制信号用于ERS中有效控制泛洪，RREQ和RREP.为了最小化泛洪，ERS采用生命周期（Time to Live，TTL）机制，TTL序列决定泛洪搜索的顺序，可能会在一个特定的值上加一个增量、固定值1或者2、或随机值.图1显示了泛洪区域集如何受预定义TTL序列值1，2，3，…，n控制.

图1 扩展环搜索

基于TTL的ERS能源效率低下（如图1所示），如果源节点收不到RREP，源节点将会以一个增加的TTL值重播RREQ，每次源节点进行新RREQ的重播都会引入能源浪费.先前的覆盖搜索区域重叠会造成冗余，发现路由节点之前或搜索完整个网络会多次出现这种情况.

1.2 阻塞扩展环搜索（BERS）

BERS可认为是能效ERS，BERS采取了一个策略，即源节点经过重新泛洪的中间节点右侧.BERS的源节点仅发送一次RREQ，中间节点当做一个代理，代表源节点进行重播.为了满足这个策略，BERS要实施一个扩展的2 H个单位等待时间，其中H是跳数.然而源节点仍有义务终止路由发现过程，收到RREP时源节点发送STOP指令去终止泛洪，泛洪持续直到追包，也就是STOP指令，在最后一个泛洪环Hr到达所有结点，在这个环中发现路由节点.

图2显示了BERS如何在从一个环到下一个环传播搜索，在BERS中，源节点首先发送RREQ，等待RREP，如果在第一个环中未发现路由节点，在第一个环中的节点以一个增加了的跳数重播RREQ，这个过程一直持续到源节点接收到RREP，然后源节点广播STOP指令去终止搜索.STOP指令只能由源节点发送，泛洪中涉及的结点将接收STOP指令，RREP可以由任意路由节点发送到源节点.为了在发现路由节点后能有效地终止下一次泛洪，BERS在每一轮泛洪过程中均要求一个扩展的2 H个单位等待时间.

图2 阻塞扩展环搜索

1.3 加强阻塞扩展环搜索（BERS＊）

BERS＊是基于BERS的，旨在减少BERS的延迟，获得能源时效方面最佳的整体性能.

BERS＊的工作方式与BERS相似，除了它在每一轮泛洪过程中减少了一半的等待时间.BERS＊中的中间节点在源节点发送了RREQ后接管后续环搜索上的重播任务，如果这些中间节点不是路由节点，在重播RREQ之前需H个单位等待时间.

相对于BERS中的2 H单位等待时间，BERS＊的整体路由发现过程速度加快近2倍，改进了能源时效方面路由发现的整体性能.如果在Hr环为节点取2 Hr单位时间来接收END泛洪信号，BERS＊中泛洪可能会在Hr＋1环终止，比路由节点发现环多出一个环.

图3所示为BERS＊的工作流程图，从图3中可以看出，在等待和传播RREP和END指令之间由于节点动作同时发生，所以仅需要一个额外环.首先，在并发行动开始之前RREP从路由节点R到源节点S（箭头线）传输花费Hr单位时间；其次，在下一个单位等待时间内，END指令广播到环1，而节点a和b继续泛洪从Hr到Hr＋1（红色箭头线）；此外，在Hr＋1单位等待期间END包花费下一个Hr单位时间追上节点c（在环1从u开始的虚线箭头线）.

图3 加强阻塞扩展环搜索

2 优化方案提出

为了减少了延迟而不增加能耗，提出了加强的BERS（tBERS）和加强的BERS＊（tBRES＊），采用追包的名字，代表tBERS的STOP和tBERS＊的END与tBERS／tBERS＊的STOP／END.tBRES的工作方式与BRES相同，tBRES＊与BRES的工作方式相同，除了tBRES和tBRES＊允许路由节点发送STOP／END指令.通过发送终止指令的路由节点右侧，相比于BERS和BERS＊，tBERS和tBERS＊能分别减少BERS和BERS＊的延迟，减少的延迟量等于Hr，也就是RREP到达源节点的传输时间.

在BERS和BERS＊中仅由源节点发送STOP／END指令终止泛洪，在tBERS和tBERS＊中，一旦接收到RREP，正如BERS和BERS＊，源节点也发送STOP／END指令，然而，这样的目的是终止先前由路由节点发送的STOP／END未覆盖的剩余泛洪，这部分泛洪由环Hr上的那些节点引起，但是由于他们的地理位置不能到达，在RREP单播传送时未从路由节点接收到STOP／END.此外，在tBERS和tBERS＊中，源节点接收到RREP之后不久就已经准备好发送数据包了.

tBERS和tBERS＊都吸取了并发活动的优点，第一类并发活动发生在RREP单播传送和从路由节点多播传送STOP／END之间，尽管由路由节点发送的STOP／END可能追不上环Hr中的所有节点去终止泛洪，但tBERS和tBERS＊中的这个方法旨在停止环Hr中进一步泛洪的一些节点，更早一些执行这个动作，否则会在BERS和BERS＊中执行.第二类并发活动发生在源节点发送数据包和STOP／END指令之间，这允许数据包比在BERS和BERS＊中更早传输.

可以证明tBERS的能耗级别与BERS相同，然而，tBERS＊能节省能源.在BERS＊中，Hr＋1环终止泛洪，超过发现路由节点一个环，相反，tBERS＊中仅有一部分泛洪在这个额外环上终止，而剩余的泛洪较早的在Hr环上终止了，也就是发现路由节点的环.这是因为在环Hr中的一些节点会在它们的Hr单位等待时间内接收到END指令.

图4显示了tBERS＊的一个实例，其中节点d停止泛洪早，尽管它比路由节点R多一跳.这里节点d在环Hr上，但是与路由节点R超过了一跳距离，然而，节点d将从路由节点R接收一个END信号途经节点b和c.相反，如果是在BERS＊中，节点d将在Hr单位等待时间之后多广播一个环，泛洪将不会终止直到环Hr＋1.

图4 tBERS＊示例

节点均匀分布的情况下，在环Hr中约1／3的节点可能在它们的等待时间内接收END消息，如图5所示，其中浅色标记的节点涉及RREPs到达源节点S之前泛洪终止.

上述的均匀分布是tBERS＊的最佳情况，在最差情况下，可能因其地理位置而环Hr中没有非路由节点从路由节点接收到END指令，在这种情况下，tBERS＊的工作方式与BERS＊完全相同，即在第2个Hr周期内接收源节点的END指令.

图5 tBERS＊均匀分布节点

在tBERS或tBERS＊中的路由节点有义务发送RREP和STOP／END指令，有2种方式可以实现同时发送RREP和STOP／END指令，其一是合并RREP和STOP／END到一起，其二是先发送RREP指令，接下来再发送STOP／END指令.注意，RREP以单播方式发送，而STOP／END是广播.作为一个示例，为了在算法中强调本文研究的思想，本文tBERS＊取第2种方法.

2.1 算法

下面仅给出tBERS＊的4个算法，tBERS的算法是类似的.注意算法中使用END指令终止泛洪，算法1是针对源节点，算法2，3和4是针对中间节点和路由节点.

算法1覆盖了路由发现过程中源节点的动作，这包括用第一次发送RREQ（行1）来初始化路由发现过程、处理RREPs中的路由信息（行4，5）.为了避免END指令和数据包之间的冲突，本文为数据包引入一个单位时间的滞后，即调用procedure＿data＿packets（行6）之前等待一个单位时间.

类似的，算法2总结了中间节点的行动，根据接收的3个消息（RREQ，RREP和END）.

算法3和4是2个描述中间节点分别接收到RREQ和END时动作的程序，如果是路由节点，它将初始化并广播END指令（算法3行8）.

算法3中，当识别出路由节点，将以当前跳数发送RREP（即 Hr）到源节点（行5～8），其他中间节点需要等待H 个单位时间（行10），如果没有收到END指令则开启泛洪（行18～19），在等待期间，中间节点需要发送一个END（行12～13，在算法4中调用procedure＿end）或 RREP（行15），因为可能源节点有第2个RREP作为备份.

2.2 能耗和时延计算

本章比较了ERS，BERS，tBERS，BERS＊和tBERS＊的能耗和延迟，结果如表1所示，各个符号说明如表2所示，这里已经消除了量化能耗和发现延迟的数学细节，可以从文献［11－12］中找到为ERS，BERS和BERS＊进行的详细计算，而tBERS和tBERS＊的能耗和延迟计算分别遵循BERS和BERS＊.

表1 各算法的能耗和时延计算

从表1可以看出，tBERS的延迟是Hr＋，tBERS＊的延迟是1＋1.5 Hr＋0.5 H2r，而BERS和tBERS的能耗是相同的，tBRES＊的能耗量低于BERS＊，依赖于节点分布.

表2 术语和符号说明

3 仿真

本文基于上述分析结果执行了一系列的仿真，在IDL6.0系统（研究系统、Boulder、CO、USA）上实现，主要目标是调查新策略应用到BERS和BERS＊的路由发现协议产生的改进，为了得到新方案的性能特征，在如下均匀节点分布下对ERS，BERS，tBERS，BERS＊和tBERS＊进行了一系列的实验.假设共有1000个节点均匀的置于覆盖Hr为10区域的地理区域内，在上述假设的节点分布下，在时效、能效和能源时效方面比较这些协议性能之间的差异.

3.1 时延比较

时效的比较结果见图6.图6a表明了5个方案对Hr的时间延迟，5个方案的延迟随着Hr的增加而增加，然而，tBRES和tBRES＊的延迟比BERS和BERS＊中对应的值小，tBERS＊的时间延迟最小，这表明tBERS＊是5个方案中时间效率最高的方案.

图6b强调了当Hr＝10时5个方案的延迟，从图6b中可以看到，tBERS优于BERS，tBERS＊优于BERS＊，时间效率最高的方案是tBERS＊，然后依次是BERS＊，tBERS和ERS，最后是BERS.当Hr为10时，tBERS＊比BERS＊的时间效率提高约12%.

类似的，当Hr为10时，tBERS比BERS的延迟减少约7.5%.

图6 5个方案的时延比较

3.2 能耗比较

能耗比较的结果见图7.

图7 5个方案的能耗比较

图7a是5个方案对Hr的能耗图，能耗随着Hr的增加而增加，BERS和tBERS产生相同的能耗，这2个方案是能源效率最高的方案，tBERS＊的能耗级别低于BERS＊，相比于BERS＊，当Hr为10时，tBERS＊可节能约6%.

图7b强调了Hr为10时5个方案的能耗，表明BERS和tBERS是能源效率最高的方案，相比于BERS＊，tBERS＊消耗的能源略低.

3.3 成本比较

为了比较各算法的整体性能，本文使用文献［15］提出的产品模型，将全部成本定义为产品的能耗量乘以延迟量，即C＝E＊T，各算法的全部成本比较结果如图8所示，图8a显示了5种方案中每个方案对Hr的能源时效.

图8 5种方案的能源时效

从图8a可以看出，tBERS＊是5个方案中能源时效最高的方案，其次是BERS＊.这意味着本文提出的新策略tBERS和tBERS＊分别改进了现有协议BERS和BERS＊，tBERS的整体成本低于BERS对应的成本.

图8b强调了Hr为10时的成本比较，可以看出，tBERS＊比BERS＊的能源时效提高了近19%.

4 结束语

本文提出了一种基于路由节点泛洪终止的扩展环形搜索改进算法，最初旨在进一步减少2个现存能源或能源时效协议BERS和BERS＊的延迟，对tBERS和tBERS＊的研究结果表明，tBERS和tBERS＊是时间和能源时效更有效的2个路由协议.首先，在tBERS和tBERS＊中通过转换终止从源节点到路由节点的泛洪义务，分别得到了比BERS更高的时效，比BERS＊更高的时间效率和能源效率，这表明在集体环境中重新分布工作负载可能会有潜在的收益.其次，本文研究中的并发对提高时间效率是有用的，而延迟和能耗有权衡的本质，所以并发既能改善时间效率，也能改善能源效率.此外，既考虑时间效率也考虑能源消耗时效是调查整体性能的一个有用度量，单独在时间效率或者能源效率上的结果可能是片面的、不完整的，有时还会产生误导，同时考虑时间和能耗是有益的.

［1］夏辉，贾智平，张志勇.移动Ad Hoc网络中基于链路稳定性预测的组播路由协议［J］.计算机学报，2013，36（5）：926－936.

［2］葛永明，朱艺华，龙胜春，等.IEEE802.11移动自组织网络节点竞争窗口长度的概率分布［J］.电子学报，2010，38（8）：1841－1844.

［3］吴大鹏，武穆清，甄岩.移动自组织网络可用带宽估计方法研究进展［J］.通信学报，2010，31（4）：103－115.

［4］张鹏，崔勇.移动自组织网络路由选择算法研究进展［J］.计算机科学，2010，37（1）：10－21.

［5］牛晓光，崔莉，黄长城.移动自组织网络中基于优化分簇的混合路由协议［J］.通信学报，2010，31（10）：58－67.

［6］王安保，胡小明.基于GPS的启发式Ad hoc路由算法研究［J］.计算机应用研究，2010，27（12）：4708－4710.

［7］BAKER D，EPHREMIDES A.The architectural organization of a mobile radio network via a distributed algorithm ［J］.Communications，IEEE Transactions on，1981，29（11）：1694－1701.

［8］王博，黄传河，杨文忠.TRQ：Ad hoc网络中基于QOS的可信路由算法［J］.小型微型计算机系统，2011，32（7）：1249－1254.

［9］甄岩，武穆清，吴大鹏，等.MANET多路径负载均衡方法［J］.北京邮电大学学报，2010，33（2）：64－68.

［10］霍金海，王钺，徐赞新，等.基于负载和优先级的MANET优化策略［J］.清华大学学报：自然科学版，2012，52（9）：1270－1274.

［11］PHAM D N，NGUYEN N T，DO X B，et al.An expending ring search algorithm for mobile adhoc networks ［C］／／Advanced Technologies for Communications（ATC），Canadian：IEEE，2010：39－44.

［12］PU I M，SHEN Y.Enhanced blocking expanding ring search in mobile ad hoc networks ［C］／／New Technologies，Mobility and Security （NTMS），Candian：IEEE，2009：1－5.

［13］王新颖，吴钊.基于AODV优化的移动自组网路由协议［J］.计算机工程，2009，35（7）：113－115.

［14］JAVAID N，BIBI A，DRIDI K，et al.Modeling and evaluating enhancements in expanding ring search algorithm for wireless reactive protocols［C］／／Electrical＆ Computer Engineering （CCECE），Canadian：IEEE，2012：1－4.

［15］PU I，SHEN Y，KIM J.Measuring energy－time efficiency of protocol performance in mobile ad hoc networks［M］／／Ad－hoc，Mobile and Wireless Networks Berlin：Springer，2008：475－486.