基于阈值判断的动态源路由协议算法优化设计*

朱清超，陈 靖，龚水清，龙建辉，高培勇

（空军工程大学信息与导航学院，西安 710077）

基于阈值判断的动态源路由协议算法优化设计*

朱清超＊＊，陈 靖，龚水清，龙建辉，高培勇

（空军工程大学信息与导航学院，西安 710077）

针对移动自组织网动态源路由协议（DSR）中旧路径中断至新路径建立期间存在的丢包和端到端时延问题，设计了一种基于阈值判断的路由发现和维护算法，以优化路由协议性能。该方法首先定义节点电池能量和节点接收信号能量双阈值等级，分别用于衡量节点和既存链路状态;然后修改路由发现和路由维护算法，使动态源路由具备阈值判断功能。分别对增强型动态源路由协议（EDSR）包传递率和端到端时延等性能随节点数目和移动速度等参数的变化规律进行了软件仿真。实验结果表明，节点数目超过150或者速度小于10 m/s时，EDSR端到端时延和包传递率优于DSR，其他性能基本相当，因此EDSR协议性能得到明显改善，为低速大规模移动自组网路由协议提供了重要参考。

移动自组织网;增强型DSR;优化设计;阈值判断

1 引言

移动自组织网（MANET）是具有高度动态拓扑结构、节点任意移动、无基础设施的自治网络，网络节点既是终端，也是路由器，节点的移动性导致拓扑结构动态变化，增加了路由协议设计的复杂度，因而路由协议模型的设计成为MANET研究的重点和难点。针对该问题，已经形成的路由协议高达10～20［1－4］种。根据路由发现机制的不同，分为先验式和按需式两种。前者节点周期执行路由发现过程，更新路由表信息，维持网络拓扑结构，路由建立时延较低，但节点能量消耗较大，降低了以电池供电的节点生存时间，从而减少MANET网络的生命周期。而后者当存在数据发送且本地节点没有源路由时才执行路由发现，降低路由发现开销，克服先验式路由协议的不足，成为MANET协议研究的热点。

动态源路由协议（DSR）［5－7］是常用的按需式路由协议，采用源路由技术，将源节点到目的节点的路径存储在每个数据包包头中，因而当发送数据时，路由建立更加简单、高效，该过程分为路由发现和路由维护两个阶段。路由发现过程仅当源节点存在数据发送且没有到目的节点的源路由时执行，所得新路径存储到路由缓存。路由维护主要用于检测拓扑结构的变化，确保数据包能够按既定链路传输数据。当发送数据时，源路由中每个节点必须检测下一跳节点是否中断。当链路中断时，该节点将向源节点发送路由错误信息。源节点尝试从路由缓存中寻找其他源路由，或者执行路由发现过程。

定义旧路由失效时刻与新路由建立时刻相隔时间为时间间隔，则DSR的缺点是时间间隔依赖于路由缓存中的备份路径。如果缓存中存在备份路径，时间间隔与路径在缓存中的位置和备份路径的刷新时间有关;如果不存在，则时间间隔与路由缓存的数量和路由发现算法有关，在此期间所有数据包将丢失，从而增加网络丢包率和时延。

针对该问题，本文提出一种双等级阈值判断方法，当节点能量降低到低阈值等级之前执行路由发现算法，从而防止DSR时间间隔内数据包的丢失，提升网络丢包率和时延等性能指标。论文安排如下:第二部分提出增强型DSR路由协议，介绍新协议的路由发现和路由维护机制;第三部分对该路由协议的性能进行仿真，并对结果进行理论分析;第四部分进行总结。

2 算法设计

时间间隔内数据包的丢失是由于源路由的连通性遭受破坏造成的，直接原因包括以下两点:一是由于MANET节点的移动性，接收信号和链路状态动态变化，增加了链路中断的概率，DSR路由协议源节点启动重传机制，更多的数据包进入网络，无疑增加网络丢包率和端到端时延;二是节点采用电池供电，网络生存周期与电池容量息息相关，数据传输导致节点能量不断下降，使得部分节点低于规定的发射功率阈值，成为无效节点，无法对接收的数据包进行转发，DSR源节点直到发送失败后才进行源路由的切换或执行路由发现，因而增加了数据传输时延，降低信道利用率。结合以上分析，针对DSR丢包率和时延，通过对节点电池能量和接收信号功率进行定量判断，设计增强型DSR路由协议，改进路由发现和路由维护算法，提高网络整体性能。

2.1 增强型DSR基本概念及原理

由于DSR节点在发送和接收均存在能量限制，因而设计两种阈值:节点电池能量（B_POW.TH1和B_POW.TH2）和节点接收信号（RF.TH1和RF.TH2），其中TH2＞TH1。节点电池能量主要用于检测节点自身能量是否符合发射要求，如不符，则从网络退出，并广播该信息。接收信号功率主要解决由于节点的移动性，造成链路质量较差，信号接收能量过低，无法实现数据包的正确接收问题。增强型DSR分为链路中断检查和阈值级别改变，链路中断检查可以降低节点移动性的影响，阈值级别改变可以缓解电池能量和移动性对网络性能的影响。

（1）链路中断检查

为避免链路中断，对备份路由进行检查，若所有备份路径超时，则尝试路由发现过程，否则每个中间节点均对自身电池能量和接收信号进行检查，当任何节点电池能量或接收功率低于TH2时，定义为中断路径，向源节点S发送消息。源节点以该消息为基础，开始检查路由缓存中所有备份路由，并将中断路径的备份路由删除。如果源节点路由缓存为空，执行路由发现过程。当低于TH1时，源节点检查路由缓存，如果存在其他源路由，则以此为主路径进行数据传输，否则对数据包进行缓存，直到发现新的路由为止。

（2）阈值级别改变

源路由中节点周期性检查电池能量和接收信号功率，当任何节点的阈值级别提高时，节点向源节点发送一个通知信号，源节点同时刷新所有备份源路由，从路由缓存中删除与条件不符的路由。当路由缓存为空时，源节点执行路由发现过程查询新路由。同理可知，当阈值级别降低时，源节点也刷新备份路由。路由缓存中的源路由按照查找顺序均可作为主路由。当路由缓存为空时，源节点对数据包进行存储直到发现新的路由。该协议的优点是当路由缓存中至少存在一条路由时，时间间隔降低为0，而且当不存在新的路由时，其时间间隔也比DSR较低。由于数据丢包率与时间间隔相关，因而增强DSR在丢包率方面高于DSR。

增强DSR是以DSR为基础设计并进行改善的。对于DSR［8］，在路由发现期间，可以获得多条源路由，性能较好的路由作为主路由并发送数据，如跳数最少的路径等，所有其他路由均作为备份路由存储在路由缓存中，如图1所示。随着时间的推移，备份路由将超时，从路由缓存中清空。对于该机制，增强型DSR不对其进行修改。

图1 DSR备份路径更新示意图Fig.1 Sketch map of DSR routes update

从图1（b）可知，节点N4与N5之间链路失效时，源节点路由缓存中删除与N4相关的源路由，从而保持路由缓存处于最新状态。

2.2 增强型DSR路由发现算法

当源节点S向目的节点D发送数据但路由不存在时，源节点向其邻节点发送RREQ数据包，过程与DSR相同，其根本变化是增加阈值级别TH2的判断，具体包括对RREQ和RREP包的操作，如图2所示。

图2 增强型DSR路由发现算法Fig.2 Routing discovery algorithm of enhanced DSR

从图中不难看出，剩余能量和接收信号能量均高于TH2的节点作为源节点到目的节点的中间节点，从而确保数据包发送过程中的所有节点具有足够的处理能量而不至于过早失败。而且通过检测接收信号的能量，保证邻节点物理位置上相差不大。因此随着节点的移动性，路由不会马上中断，提高了路由的可靠性。由于源节点收到多个RREP包，因而其路由缓存中存储多条路径。路径最短的路由将作为主路由进行数据发送，其他路径以跳数递增规律存储在路由缓存中，作为备份路径使用。

2.3 增强型DSR路由维护算法

如前所述，增强型DSR中提出两种能量阈值，即电池剩余能量和接收信号能量。通过检测电池剩余能量，源节点检查所有的备份路由并从路由缓存中删除失效路由。如果路由缓存为空时，源节点执行路由发现过程。在主路由失效后，如果路由缓存中存在备份路由，源节点以此为主路由。如果没有任何备份路由，源节点将数据包缓存直到发现新路由。当节点的剩余能量或接收能量低于阈值TH2时，可视为脆弱节点。基于以上概念，路由维护执行过程包括以下几步。

第一步:脆弱节点向源节点发送通知信息

情况1:当节点检测链路中断原因为电池能量低于B_POWER.TH2时，节点向源节点发送标准格式通知包，该通知包包含目的节点D和源节点S。

情况2:当节点逐渐移出邻节点范围时，两节点均通过接收信号强度与RF.TH2比较，当前者不大于后者时，可检测链路变化。

第二步:源节点开始刷新备份路由

情况1:源节点接收到脆弱节点发送的通知包后，通过路由缓存中的备份路径广播控制包C1，用于回应S－D的节点对。若目的节点D通过备份路由R接收到该控制包C1，通过R向S发送另一控制包C2。源节点S仅维持正常接收C2的路径，从而实现备份路径的刷新。如果S没有接收任何C2控制包，则备份路径均已超时，此时S执行路由发现。

情况2:执行过程与情况1相同。

第三步:检查备份路由的状态

情况1:当发现电池剩余能量或接收信号能量低于TH1时，微弱节点W再次发送通知信息公布节点电池能量或接收信号强度的临界值。该通知信息包含目的节点D和源节点S。当源节点收到该信息时，检测路由缓存，选择最优路径作为回应目的节点的主路径。

情况2:若所有路由超时，当发现电池或接收信号能量低于TH1时，微弱节点W发送与情况1相同的通知信息。收到该信息后，由于源节点S处于路由发现过程，因而缓存所有到达数据包，回应源SD节点对。当发现新路由后，源节点通过该路径开始发送所有缓存数据包。

3 仿真测试及分析

假定源节点路由缓存中备份路由按照跳数的升序排列，利用NS2进行仿真，根据RFC 4728文档既定标准，仿真参数设置如表1所示。

表1 仿真参数设置Table 1 Set of simulation parameters

对数据利用MATLAB进行处理，结果如图3和图4所示。

图3 DSR和EDSR性能与节点数目关系Fig.3 Performance of DSR and EDSR vs.number of network nodes

图4 DSR和EDSR性能与节点移动速度关系Fig.4 Performance of DSR and EDSR vs.velocity of network nodes

从图3中可以看出，在端到端时延方面，当节点数目较小时，DSR比较稳定且低于EDSR，但随着节点数目增多，DSR增长速率明显加快，当节点数目达到150之后，DSR呈现线性增长，而EDSR相对比较平稳。包传递率方面，两者都呈现上升、平稳、下降的规律，但EDSR投递率略高于DSR。从图4中可以看出，端到端时延方面，当节点移动速度不大于10时，DSR与EDSR性能相当，但速度增加时，EDSR增加比DSR较快，可能原因为节点速度增加，节点接收的功率很快达到阈值下限TH1，因而该备份路径删除，在发现新备份路径之前，节点位置已经发生改变，接收的信号功率降低，如此往复，增加了端到端时延，而DSR路由缓存中仍存在原有备份路径。包投递率方面，当节点速度小于10时，EDSR明显高于DSR，但随着速度的增加，两者相差不大。由以上结果不难看出，EDSR对于网络规模的适应性高于DSR，而对于移动速度的适应性与DSR相当。

4 结论

DSR路由协议以其简单、高效的优点成为MANET按需路由协议研究的重点，但该协议存在缺点，即在新路由与源路由的时间间隔内，发送数据包全部丢失，从而增加了丢包率和端到端时延。针对该问题，提出电池能量和接收信号能量双阈值判断规则，对DSR路由发现和路由维护进行改进，设计了增强型动态源路由协议。经仿真验证，该协议随着网络规模的增加，包传递率和时延均得到改善;随速度的变化趋势与DSR相当，主要由于在仿真过程中节点能量的消耗是以线性关系降低的，与实际节点能量消耗存在差距。如何设定节点能量的递减规律，降低该参数对仿真性能的影响是今后研究的重要课题。

［1］Vijayavani G R，Prema G.Performance comparison of MANET routing protocols with mobility model derived based on realistic mobility pattern of mobile nodes［C］//Proceedings of 2012 IEEE International Conference on Advanced Communication Control and Computing Technologies.Ramanathapuram:IEEE，2012:32 －36.

［2］Sadeghi M，Yahya S.Analysis of wormhole attack on MANETs using different MANET routing protocols［C］//Proceedings of 2012 Fourth International Conference on Ubiquitous and Future Networks.Phuket:IEEE，2012:301－305.

［3］Hiranandani D，Obraczka K，Garcia－ Luna－ Aceves J J.MANET protocol simulations considered harm ful:the case for benchmarking［J］.IEEE Wireless Communications，2013，20（4）:82 －90.

［4］Saeed N H，Abbod M F，Al－ Raweshidy H S.MANET routing protocols taxonomy［C］//Proceedings of 2012 International Conference on Future Communication Networks.Baghdad:IEEE，2012:123 －128.

［5］Baisakh，Patel N R，Kumar S.Energy conscious DSR in MANET［C］//Proceedings of 2012 2nd IEEE International Conference on Parallel Distributed and Grid Computing.Solan:IEEE，2012:784 －789.

［6］Tamilarasi M，Shyam V R，Haputhanthri U M，et al.Scalability improved DSR protocol for MANETs［C］//Proceedings of 2007 International Conference on Computational Intelligence and Multimedia Applications.Sivakasi:IEEE，2007:283 －287.

［7］Tamilarasi M，Chandramathi S，Palanivelu T G.Overhead reduction and energy management in DSR for MANETs［C］//Proceedings of 3rd International Conference on Communication Systems Software and Middleware and Workshops.Bangalore:IEEE，2008:762 －766.

［8］Amjad K，Stocker A J.Impact of node density and mobility on the performance of AODV and DSR in MANETS［C］//Proceedings of 2010 7th International Symposium on Communication Systems Networks and Digital Signal Processing.Newcastle Upon Tyne:IEEE，2010:61 －65.

Optim ized Design of Dynam ic Source Routing Algorithm Based on Threshold Judgment

ZHU Qing － chao，CHEN Jing，GONG Shui－ qing，LONG Jian － hui，GAO Pei－ yong
（School of Information and Navigation，Air Force Engineering University，Xi'an 710077，China）

A novel route discovery and maintenance algorithm is proposed for solving the packet lost rate and end－to－end delay problem of Dynamic Source Routing（DSR）during the interval between the old source route and new source route in Mobile Ad Hoc Network（MANET），which is aimed to optimize the performance of route protocol.The proposed algorithm first defines two concepts，battery power and

signal power，both of which are used to measure the statement of any node and link respectively.Then route discovery and maintenance algorithm are modified to make the DSR possess the function of threshold judgment.Finally the relation between performance of packet deliver fraction and end－to－end delay of enhanced DSR（EDSR）and the number of nodes and mobile velocity is simulated by network software.The simulation results show that packet deliver fraction and end－to－end delay of EDSR is better than that of DSR when the number of nodes is higher than 150 or velocity of node is lower than 10 m/s.What's more，the performance of EDSR is equal to that of DSR in other region.For the reasons above，compared with DSR，the performance of proposed EDSR protocol is better obviously.It provides an important reference for low －speed of large－scale MANET routing protocol.

MANET;enhanced dynamic source routing protocol;optimized design;threshold judgment

The National Natural Science Foundation of China（No.61172083）

＊＊

sxsxaswyqwjgcxy@126.com Corresponding author:sxsxaswyqwjgcxy@126.com

TP393

A

1001－893X（2014）05－0644－06

10.3969/j.issn.1001 －893x.2014.05.022

朱清超，陈靖，龚水清，等.基于阈值判断的动态源路由协议算法优化设计［J］.电讯技术，2014，54（5）:644－649.［ZHU Qing－chao，CHEN Jing，GONG Shui－ qing，et al.Optimized Design of Dynamic Source Routing Algorithm Based on Threshold Judgment［J］.Telecommunication Engineering，2014，54（5）:644 －649.］

2013－11－15;

2014－02－21 Received date:2013－11－15;Revised date:2014－02－21

国家自然科学基金资助项目（61172083）

朱清超（1987—），男，山东济宁人，2012年获硕士学位，现为博士研究生，主要研究方向为通信与信息系统;

ZHU Qing－chao was born in Jining，Shandong Province，in 1987.He received the M.S.degree in 2012.He is currently working toward the Ph.D.degree.His research concerns com-munication and information system.

Email:sxsxaswyqwjgcxy@126.com

陈 靖（1963—），女，陕西西安人，2005年获博士学位，主要研究方向为自组织网络、网格计算等;

CHEN Jing was born in Xi'an，Shaanxi Province，in 1963.She received the Ph.D.degree in 2005.Her research interestsinclude Ad Hoc network，grid computing and so on.

龚水清（1987—），男，湖南长沙人，2013年获硕士学位，现为博士研究生，主要研究方向为组网技术;

GONG Shui－ qing was born in Changsha，Hunan Province，in 1987.He received the M.S.degree in 2013.He is currently working toward the Ph.D.degree.His research concerns network technology.

龙建辉（1990—），男，湖南长沙人，2012年获学士学位，现为硕士研究生，主要研究方向为通信与信息系统;

LONG Jian － hui was born in Changsha，Hunan Province，in 1990.He received the B.S.degree in 2012.He is now a graduate student.His research concerns communication and information system.

高培勇（1989—），男，河南郑州人，2012年获学士学位，现为硕士研究生，主要研究方向为通信与信息系统。

GAO Pei－ yong was born in Zhengzhou，Henan Province，in 1989.He received the B.S.degree in 2012.He is now a graduate student.His research direction is communication and information system.