结合拥塞控制和能量均衡策略DSR路由协议
邬春学，宋兰中，王佳炳
上海理工大学光电信息与计算机工程学院，上海200093）
摘 要：为了改善Ad Hoc网中拥塞状况，提高网络生存时间，通过分析DSR协议，利用对节点拥塞和能量状态的划分，提出了一种结合拥塞控制和能量均衡的CE-DSR路由协议。NS-?,进行仿真表明，新策略不但减轻了网络的拥堵程度，而且延长了整个网络的生存时间。改进后的CE-DSR路由协议性能明显优于传统的DSR路由协议性能。最后给出了改进后的CE-DSR协议在移动自组网络控制系统中的应用效果。
关键词：Ad Hoc网络；DSR路由协议：拥塞控制；能量均衡
中图分类号：TP 393 文献标识码：A
l 引 言
Ad Hoc网络是由一组带有无线收发装置的移动终端组成的一个多跳的临时性自治系统，网络中的移动终端具有路由和报文转发功能，可以通过无线连接构成任意的网络拓扑。它的特点是：独立组网、无中心、自组织、多跳路由，动态拓扑等。上述特点使得自组织网成为无线网络和移动计算领域最集中研究的热点。
从Ad Hoc冈络的定义可知，他与传统的网络不同，传统的路由协议不适用于Ad Hoc网。由于Ad Hoc网中带宽和节点能量有限，在链路上的拥塞和网络生存时间短是网络性能下降的主要原因。目前的Ad Hoc路由协议都不是很****，设计出符合Ad Hoc网的路由协议是很多研究者的孜孜追求。然而，一般对路由协议的改进只是针对某一个方面，比如只改进拥塞方面，或者只改进能量均嘶方面。本文将结合拥塞控制和能量均衡技术来改 进传统的DSR路由协议使其拥有广泛的应用前景。
2传统DSR协议分析
DSR协议是一种按需动态源路由协议，可找到从源节点到目的节点的多条路径。DSR协议主要由路由发现和路由维护2部分组成，本文着重点在路由发现，下面只介绍路由发现具体实现过程。
1)路由发现路由实现过程，如图l所示。
图1路由实现过程
当源节点S要向目的节点D发送数据时，先产生路由请求分组RREQ，格式如下：
当一个节点收到RREQ消息时，按以下步骤处理：
Step 1 查看RREQ消息中的(源节点地址，RREQ ID)是否在自己的新近请求记录中，若在，则丢弃RREQ，否则将此请求加入新近路由记录中。
Step 2查看自己的地址是否在RREQ消息的路由记录中，若在，丢弃RREQ，否则处理Step 3。
Step 3查看目的节点地址是否与自己的地址匹配，若匹配，则向源节点回应路由应答( RREP)消息，否则处理Step 4。
Step 4将自己添加到路由记录中，继续广播RREQ消息。这样，由源节点发出的RREQ消息在网络中转发，直到到达目的节点或知道该怎么到达目的节点的中间节点。目的节点或中间节点沿路由记录中记录的路由反转后的路由将RREP消息发送给源节点（这里假设链路为双向链路）。这样就建立了多条从源节点到目的节点的路径。例如，在图l中，在源节点S和目的节点D之间会建立路径S—A-C—F-D和S-A-C-E-D。
2) DSR协议缺点DSR协议没有考虑链路的拥塞狄况和节点的能量状况。例如：当节点E处于拥塞状态或能量不足时，而F节点拥塞较轻和能量充足，就不应该再让E节点参与转发路由请求报文( RREQ)，否则，整个网络有可能出现拥塞状态或网络生存时间短。
3DSR协议改进
从传统的DSR协议可以看出，它的路由过程是不考虑当前节点的拥塞状况和能量状况，从而很容易导致整个网络的拥塞和减少网络生存时间，因此，本文从此点出发优化DSR协议。
为了让路由协议对状态不同的节点做出不同的响应，需要对网络中的节点状态进行划分。
1)节点状态划分
①网络节点拥塞级别的划分将节点的拥塞级别划分为3个级别：c-normal，congestion，c-daner。划分依据为：节点的缓存队列长度。当节点均缓存队列较少，处于较为空闲的状态，节点能够承受更多的数据任务，此时节点划分为c-normal,当节点其缓存队列中的数据较多，但是拥塞状态不是很严重的节点，这些节点可以继续发送数据，但它们已经不是****状态，此时节点划分为congesion；当节点其缓存队列已经很多，节点可能已经处于拥塞状态，已经不应继续增加在该节点上的数据转发，此时节点划分为c -danger。
②网络节点能墨级别的划分将节点的能量状态也分为3个等级：e-normai，warning，e-danger。划分依据为：节点的剩余能量。当节点能量充足或比较充足，此时节点能量划分为e-normal；当节点还有能量，但是能量状态已经不是****状态了，应该防止节点过多的参与路由，但是当节点是路由路径必须经过的节点时仍然可以作为路由路径经过，此时节点量划分为warning；当节点自身能量已经不足，已经不应该参与任何路由，此时节点能量划分为e-danger。
2)算法描述在路由发现的过程中，当网络中的节点收到路由请求报文后根据节点自身的状态决定下一步动作，算法如下：
最后当源节点在一段时间后仍没有发现有效的路由，就重新发起一次路由发现过程，第二次路由发现过程将不再对节点的拥塞状态及能量进行区分，以保证路由的正常建立。这个过程主要是针对网络较稳定的情况制定的，如果网络中大多数节点已经处于能量不足的状态时就不适合采用上述过程。
上述过程的流程图，如图2所示。
通过上述改进，在节点处于拥塞或能量状态不佳的情况下延迟节点转发路由请求报文，这样可以让不在拥塞状态并且节点能量状态良好的节点优先形成路由链路，从而避免了通过状态不佳的节点形成路由，当节点已经拥塞或者能量已经不足时节点直接丢弃路由请求报文，这样节点就无法参与到路由链路的建立，结合这两方面的改进该技术既阻止了在拥塞状态和能量不足节点上建立路由，有效地减少了为了建立多条路由所产生的路由请求报文的广播风暴以及为了维护多条路由所需的网络消耗，同时又在节点拥塞、能量情况与路由其他代价之间进行了比较，获取了****的路由链路。
在图1中，可以知道在路由发现中没有考虑拥塞状况和节点的能量状况，而在改进的CE-DSR中却考虑到了这两点，如图3所示。
下面以图3举例说明：
假设图3中节点B拥塞状态c-danger状态（图中月黑竖影标记），C拥塞状态处于congestion状态（图中用黑横影标记），E能量状态处于warning状态（图中用灰斜影标记）。
分析图3的路由发现过程：当源节点S要向目的节点D发送数据时，先产生路由请求分组RREQ。
①节点A，B收到RREQ后分析自己的拥塞状况和能量状况，由于节点A能量状态处于c-normal，能量状态处于e-normal，节点B拥塞状态处于c-danger，所以节点A直接转发路由请求分组RREQ，而节点B丢弃路由请求分组RREQ。
②当节点C收到来自节点A的RREQ，先检查自己的状态，发现自己拥塞状态处于congestion时，节点C先延迟一个delaytime后（在此之间链路好的路径可以先建立起一条路由路径）它将继续转发RREQ。
③节点B，E，F收到C转发的RREQ，检查自己的状态，由于B节点能量状态处于e-danger所以拒绝转发RREQ；节点E能量状态处于e-warning，所以它延迟一个delaytime转发RREQ，在此之间节点F已经转发RREQ，一条好的链路的路由已经形成，而经过E点的路由路径只作为备选。
④节点F转发RREQ，节点D收到后回应RREQ -条妤的链路的路由S-A-C-F-D****形成，而由于E节点的一个delaytime延迟，使得不是****的路径S-A-C-E-D最后形成：
由图3的路由发现过程可以知道，这种结合拥塞控制和能量均衡的路由策略不但减少了拥塞的发生，而且延长了整个网络的生存时间，提高了整个网络的综合性能。
3)性能分析假设每个节点将路由请求报文传送到下一节点时间为t，那么从源节点到目标节点整个延时：
式中，a=0，1，2，当节点正常发送时a=0，当节点发生一次延迟转发时a=l，节点发生2次延迟转发时n =2。
由此可见，DeLay_of_route和经过的节点跳数n，每个节点转发报文所用时间t及节点状态有关。当网络中节点的拥塞及能量状况良好时a等于0，这时的Delay_of_route与只与t有关，这与普通DSR路由协议相同。
当路由距离最短的路径中有节点拥塞时，n可能不为0，等于0时说明路由协议通过其他未拥塞节点达到目标节点。这时因为绕行了稍远的路径，路由时间Delay_oj route可能会比未改进的路由协议有所增加，路由过程中的网络延时会增加，但是白于路由过程只有一次，而如果网络出现拥塞，拥塞将持续整个数据传输过程，所以通过这种改进还是能够减少网络中端到端的延时的。而不等于O时说明节点无法通过其他路径达到目标节点，De-lay_ojrouie也会变大，虽然这时的端到端延时将会比未改进时有所增加，但是这是以路由延迟为代价改善网络中的拥塞状况，当网络处于较稳定状态时不会出现大面积的拥塞节点，这种情况发生的概率是较小的，总之改进后网络的端到端延时还是会有所降低的。
在路由距离最短路径中存在能量不足节点的情况时，这种方式的改进会导致整个端到端延时的增加，但这是为了换取网络中的节点能量更加均衡的使用。在网络中节点既处于拥塞状态，能量状态又不佳的情况与只发生一种不佳状态时是一样的。
改进后的CE-DSR路由协议，在路由发现过程中可能会比原DSR路由协议的路由延时有所增加，但是这些延时能够使整个数据发送过程中拥塞状态和网络能量状态有所改善，因此还是值得的。
4仿真
1)仿真环境与方法本次仿真主要是在改变30个节点暂停时间情况下研究了改进前后的DSR协议的包成功发送率，平均端到端时延和网络生存时间性能。使用的模拟实验环境是NS-2模拟器，仿真环境：数据包512字节；节点传输范围250 m；初始能量100 J；模拟时间900 8；节点数30；连接数12；Mac层协议802. 11协议；初始节点队列长度50；节点队列类型CMUPriQueue；信道传输速率2 Mbp。
仿真过程如下：
由于数据量大，仿真时间长，为保住数据准确，本文采用了编写shell批处理文件程序，只需运行一个命令，数据就可以自动输出到指定位置。仿真结果图中的每个数据点代表在完全相同的通信模型、但是随机产生的不同移动方案下仿真10次得到的仿真结果平均值。
对每个路由协议使用完全相同的移动试验方案和通信试验方案。
2)仿真结果与分析
①包成功发送率在开始的一分钟时间里，由于使用两种协议的节点能量充足，没有网络拥塞，所以包成功发送率基本相同，如图4所示。
随着时间的淌耗，DSR协议和CE-DSR协议的数据传送成功率都在下降，但是在l—8 min时，DSR协议的包成功发送率明显比CE-DSR协议的包成功发送率下降的快，虽然在第8到第10 min之间DSR协议的包成功发送率稍微有点上升，但包成功发送率总趋势还是小于CE-DSR协议。因为CE-DSR采取了拥塞控制和能量均衡机制，使得节点存活时间要比原先长，对比它的端到端时延代价较小使得发送数据包的成功率比改进前有所增加。第10 min以后不管是使用DSR协议还是使用CE-DSR协议的网络包成功发送率都在减少中趋于平缓。
②网络生存时间DSR和CE-DSR的网络生存时间，如图5所示。
当网络拓扑变换越慢，2种协议的网络生存时间越长。在节点停留时间为O~10 s，由于使用2种协议的节点能量都充足，所以他们的网络生存时间差别不大。但是，当节点停留时间10 s后，使用DSR协议的网络生存时间明显短于使用CE-DSR协议的网络生存时间，因为CE-DSR协议采用了能量均衡策略，使得节点不会过早的死亡，所以网络生存时间有了朗显的提高。对比之下，DSR协议的网络生存时间明显不如CE-DSR协议的网络生存时间。在节点停留大于10 s之后，使用CE-DSR协议的网络生存时间增加趋势明显比使用DSR协议的要快的多。
③平均端到端时延，如图6所示。
节点停留时间在0—80 s时，使用DSR协议的网络平均端到端时延比使用CE-DSR协议的要短，但到节点停留时间在80 s之后，改进后的CE-DSR协议端到端延时明显比DSR协议的端到端延时小。这与理论分析是相互符合的。在使用CE-DSR路由协议的网络中，虽然一方面改进后的路由协议在进行路由的过程中可能因为节点的拥塞情况和能量级别而发生延迟转发甚至不转发，导致整个端到端延迟的增加，但是另一方面它有效地改善了网络的拥塞情况，减少了端到端的延时。而延迟转发或不转发路由请求报文只会对在路由过程中造成一次性的端到端延迟，而拥塞的链路将会造成整个数据传输过裎的延迟。综合这些方面，在仿真过程中，网络的整体端到端延时还是有减少。由图6可知，随着节点停留时间的增加，平均时延不会一直减少，而是趋于平稳。
从以上仿真结果可以看出，改进后的CE-DSR协议不仅提高了整个网络生存周期中节点成功接收数据包的总数，延长了整个网络的生存周期，而且在一定程度E也减少了网络的端到端延时，总体上提高了网络性能：
5 CE-DSR在移动自组NCS中的应用
移动自组NCS具有安装便捷、使用灵活移动、易于扩展等优点，具有广泛的应用前景。
路由协议在通讯网络中的好坏很大程度上影响移动自组NCS网络性能。CF-DSR协议使拥塞得到控制和改善，能延长网络生存时间，该方法应用在移动自组NCS中，网络通信性能可以得到明显改善，典型的网络控制系统信息流程结构图，如图7所示。
(2)式中，τ为整个系统延时；τs为系统延时中的固定部分，主要由数据预处理时间、数据后处理时间和节点发送数据包时间组成；τv为系统延时中的变化部分，主要由数据包等待发送时间和数据包在节点之间传递时间组成.
从仿真图4~图6结果综合可知，由于网络状态良好，τv得到改善，从而整个系统延时τ减少，提高了整个移动自组NCS网络性能。有效的路由协议可以减少可变延时τv。
由于采用了CE-DSR协议，达到了拥塞控制和能量均衡目的，使时延、丢包率减少，并延长了网络生存时间。因此，CE-DSR协议在移动自组Ncs的应用具有受控性好，可靠性高，连通性强。
6结语
改进后的CE-DSR路由协议可以通过对DSR路由协议简单修改得到，膻朋广泛，实用性强。虽然在路由发现过程中可能会比原DSR路由协议的路由延时有所增加，但是这此延时能够使整个数据发送过程中拥塞状态和网络能量状态有所改善，因此还是值得的。由于DSR路由协议是多路径路由，所以下一步工作主要集中在怎样在路由协议中添加动态的路由状态的侦测，发现并采用多条路由状态较佳的路径提高网络性能。
|
