一种最小能量动态源路由实现

　　移动Ad hoc网络MANET（Mobile Ad hoc Networks）是由一组具有路由功能的移动节点自组织成的无线多跳系统。MANET为Mobile Ad hoc network的简称，Ad hoc网络是一种自组织网络，分为固定节点和移动节点两种。MANET特指节点具有移动性的Ad hoc网络。比如有N个笔记本电脑通过802.11的Ad hoc模式自己组网形成一个网络，如果笔记本的使用者如果不移动的话，网络的拓扑就不会改变，路由等也就是固定的。但是如果每个出租车上都配置一个无线网卡，全部出租车组成一个网络，则拓扑是不断变化的，路由等也变的复杂。 MANET研究已经有很多年的历史，详情见参考资料。目前的研究热点集中在MAC层和路由层，路由又偏重于借助其它手段，如GPS等定位方法的路由。传统的MANET路由协议包括表驱动协议和按需驱动协议。表驱动协议如DSDV等，按需驱动为AODV,DSR等。借助于GPS信息的路由协议如GPS-DSR等。

　　传统路由协议都使用一组度量指标来寻找维护路径，常用的度量指标是少跳数。然而这个指标没有考虑节点和网络的耗能和寿命问题，可能导致节点能源的浪费和过度使用等问题，终使得节点和网络的寿命严重下降。

　　动态源路由（DSR）[1]协议在转发数据时，使用少跳数的路径进行数据转发。在发射器以固定能量水平发送的Ad hoc网络中，DSR协议并没有考虑路径的剩余能量。由于DSR协议始终选择少跳数的路径进行数据转发，因此在少跳数路径上的节点被过度使用的可能性很大。节点的过度使用极易使节点死亡造成网络发生分割，缩短网络的使用寿命。

　　本文针对DSR协议和MEDSR协议在节能策略方面存在的缺陷，以减少节点的过度使用和延长网络生存时间为设计目标，以MEDSR路由协议为基础，提出了一种基于能量感知的能量动态源路由协议。引入能量感知策略就是使路径的剩余能量成为主要的度量指标来选取路径。

　　1 相关算法

　　链路功率路由协议（MLRP）算法旨在寻找一条低功率的路由，其中每个节点都能根据自己要进行通信的邻近节点自适应地调整发射功率。在此算法中，路由寻找的发起者决定转发RREQ请求的中间节点的统一发射功率，当路由建立尝试失败时，能相应地减小此功率值。因此，此路由进程主要考虑化每个参与节点消耗的能量，以及减小所选路径消耗的能量。电池开销路由（MBCR）[3]算法中定义了节点电池开销函数，从而计算出包含n个节点的路径m的总电池开销，而剩余电池能量的路径即是拥有电池开销的那条路径。

　　2 能量动态源路由（MEDSR）

　　2.1 能量路由协议的背景

　　传统的路由协议都是采用固定的发射功率进行数据包的转发，由于节点发射功率的大小直接影响到邻近节点的通信，发射功率太小虽然可以相对减少能量消耗，路由协议通过在路由器之间共享路由信息来支持可路由协议。路由信息在相邻路由器之间传递，确保所有路由器知道到其它路由器的路径。总之，路由协议创建了路由表，描述了网络拓扑结构；路由协议与路由器协同工作，执行路由选择和数据包转发功能。路由协议主要运行于路由器上，路由协议是用来确定到达路径的，它包括RIP,IGRP,EIGRP,OSPF.起到一个地图导航，负责找路的作用。它工作在网络层。

　　发射功率水平过高或者过低都会严重影响网络的连通性，在保证节点通信成功的情况下，采用发射功率水平不仅可以保证网络的连通性，而且还减少节点的能量消耗。

　　2.2 能量动态源路由简介（MEDSR）

　　MEDSR协议是在DSR协议的基础上，采用可调整的发射功率，并且在DSR协议的路由发现过程当中改进而得来的。

　　MEDSR协议的路由发现过程当中包含两个机制：

　　（1）多功率水平路由发现机制

　　源节点首先使用低功率水平发送RREQ,RREQ中包含功率水平信息。如果使用低功率水平发送失败，则选择高功率水平发送。下一跳节点也选择可调整的功率水平将RREQ转发，并且将自己的功率水平信息加到RREQ中。此过程一直操作下去，直到RREQ到达目标节点。

　　（2）逐段功率水平调整机制

　　图1（a）中节点C接收到目标节点D发送过来的RREP,测量节点C接收到的能量水平Precv.因为RREP中包含目的节点的发送功率水平信息Pt.节点C计算到达目标节点D所需少的传送能量：Pmin=Pt-Precv,然后节点C将所需的少传送能量存储在自己的能量表中。

　　3 协议描述

　　3.1 能量感知

　　3.1.1 路由请求包（RREQ）的结构

　　为了实现MEDSR协议中功率调整，需要在RREQ中增添功率值列表字段Power list,如表1所示。

　　3.1.2 路由回复包（RREP）的结构

　　路径的剩余能量是指该路径中的节点剩余能量的值。

　　能量感知的目的就是在返回的众多路径中选择剩余能量的路径。

　　按需路由协议并不像表驱动路由协议那样预先知道网络全局的拓扑信息，按需路由协议是根据发送数据分组的需要按需进行路由发现过程，所以MEDSR协议中路径的剩余能量只能通过路由发现过程动态地获得。如表2所示。

　　3.1.3 节点本地cache表的结构

　　为了满足能量感知的目标，需要在MEDSR协议的基础上，对网络节点的cache表中再增加剩余能量值字段Residual energy和临时剩余能量字段Temporary energy,以及发射功率值字段Power level,如表3所示。

　　Residual energy字段记录节点当前的剩余能量值，Temporary energy字段记录Residual energy字段与Power level字段的差值，用于和RREP中的Path energy字段比较，Power level字段记录经调整的发射功率值。

　　采用Temporary energy字段是因为MEDSR协议的发射功率是可调整的，即不同路径上节点的发射功率大小不同，如果此时简单地使用Residual energy值作为比较对象，有可能使Residual energy的节点由于Power level过大而造成节点能量的过快消耗。

　　3.1.4 能量感知过程说明

　　变量说明：R代表cache中的Residual energy字段记录的值；P代表cache中的Power level字段记录的值；T代表cache中的Temporary energy字段记录的值（用于和RREP中的E比较）；E代表RREP的Path energy字段记录的值。

　　（1）节点剩余能量的计算过程

　　每个节点都保存着自己剩余能量的数值R,同时，保存着临时的发射功率水平数值P（P是MEDSR协议经过能量水平调整而暂时存储在本地cache表当中的）。每转发一个数据包，节点就进行操作：R:=R-P.

　　（2）路径剩余能量的计算过程

　　在MEDSR协议路由应答过程中，目的节点的下一跳邻居节点进行能量水平调整以及相应的临时剩余能量T计算。首先进行计算T:=R-P,然后将自己的T赋值到RREP中的Path energy字段。当RREP到达目的节点的次下一跳邻居节点时，该节点也进行能量水平调整和临时剩余能量T计算，然后将自己的T值和RREP中的E值进行比较：如果T<E,则E:=T;如果T>=E,则E不做任何改变。

　　当源节点接收到经过多个RREP后，比较它们当中的E值，源节点首先选择E的的路径进行数据包的转发，即选择剩余能量的路径进行数据转发。

　　3.1.5 能量感知形式化说明

　　图2（a）和图2（b）分别用无向图和有向图表示同一个网络[5].图2（a）中节点旁边的数字代表节点的剩余能量R,节点之间的数字代表经过调整发射能量水平数值P.图2（b）中节点旁边的数字代表节点的剩余能量R,节点之间的数字代表临时剩余能量T.

　　如图2（b），节点d和节点b进行通信，d、b之间有两条路径，分别是d-a-b和d-c-b,路径d-a-b的剩余能量E是60;路径d-c-b的剩余能量E是55,所以节点d和节点b进行通信时，会优先选择剩余能量值较大的d-a-b路径。再如，节点a和节点c进行通信，a、c之间有两条路径，分别是a-b-c和a-d-c,路径a-b-c的剩余能量E是35;路径a-d-c的剩余能量E是55,所以节点a和节点c进行通信时，会优先选择剩余能量值较大的a-d-c路径。路由算法，可以根据多个特性来加以区分，算法设计者的特定目标影响了该路由协议的操作；具体来说存在着多种路由算法，每种算法对网络和路由器资源的影响都不同；由于路由算法使用多种metric,从而影响到路径的计算。

　　3.2 路由算法

　　3.2.1 路由请求

　　（1）源节点S在本地路由缓存中检查是否存在到达目的节点D的路由。如果存在，则转（2），否则开始路由请求过程：节点选择可调整的功率水平转发RREQ.首先，源节点S使用低功率水平发送路由请求数据包RREQ,如果发送成功，则将功率水平信息存放到RREQ发射功率值列表字段Power list中；否则，选择高功率水平发送路由请求数据包RREQ,如果发射成功，进行如上述功率水平信息同样的操作，并转（3）。

　　（2）使用该路由发送数据分组。

　　（3）下一跳邻居节点接收到RREQ后，首先检查路由请求表中是否有对应的表项，如果有，直接丢弃该RREQ;否则，检查路由请求分组的路由记录是否已含有该节点，如果有，丢弃该分组。然后，如果路由请求分组的目的节点为节点本身，即将自己的地址信息加到RREQ中，并将功率水平信息加到RREQ中发射功率值列表字段Power list中，该节点同时反向转发RREP,RREP中保存RREQ中功率水平信息。

　　（4）次下一跳邻居节点接收到RREQ后，重复操作。

　　（5）所有中间节点按照步骤（3）操作，直到所有RREQ到达目的节点D.

　　3.2.2 路由应答

　　（1）目的节点D将自己的地址信息和功率水平信息加到RREP中，并反向转发RREP,并转（2），同时进行路径剩余能量的计算。

　　（2）下一跳邻居节点接收到RREP后，首先根据MEDSR协议中的功率水平调整机制进行功率的调整，并将计算得到的Pmin存放到本地cache中的Power level字段。然后进行临时剩余能量的计算T:=R-P,将自己的T赋值到RREP中的Path energy字段。

　　（3）次下一跳邻居节点接收到RREP后，首先根据MEDSR协议中的功率水平调整机制进行功率的调整，并将计算得到的Pmin存放到本地cache中的Power level字段。然后进行临时剩余能量的计算T:=R-P,将自己的T值和RREP中的E值进行比较：

　　（4）所有中间节点按照步骤（3）操作后，向下一邻居节点继续转发RREP,直到RREP到达源节点S.

　　（5）源节点S选取Path energy值的RREP提供的路由信息进行数据分组的转发。

　　3.3 路由过程

　　3.3.1 路由请求过程

　　（1）从如图3可以看到源节点S在路由缓存中并没有发现到达目的节点D的缓存路由。源节点S开始路由请求过程：节点S使用可调整的功率水平发送路由请求数据包RREQ,将功率水平信息存放到RREQ功率值列表字段Power list中，并转发RREQ.图3中（S,B）的功率水平值为20,（S,E）的功率水平值为15.

　　（2）下一跳邻居节点B和E接收到RREQ后，首先，节点B和E检查路由请求表并没有发现对应的表项；同时检查路由请求分组的路由记录也没有发现含有该节点，则不丢弃RREQ.然后，节点B和E检查路由请求分组的目的节点不是节点B和E本身，同时将自己的地址信息加到RREQ中，该节点同样选择可调整的功率水平转发RREQ,将自己的功率水平信息加到RREQ功率值列表字段中，并转发RREQ.图3中（E,F）的功率水平值为15,（B,C）的功率水平值为20.

　　（3）次下一跳邻居节点F和C接收到RREQ后，首先，节点F和C检查路由请求表并没有发现对应的表项；同时检查路由请求分组的路由记录也没有发现含有该节点，则不丢弃RREQ.然后，节点F和C检查路由请求分组的目的节点不是节点F和C本身，同时将自己的地址信息加到RREQ中，该节点同样选择可调整的功率水平转发RREQ,将自己的功率水平信息加到RREQ功率值列表字段中，并转发RREQ.图3中（F,G）的功率水平值为15.

　　但是，次下一跳邻居节点H接收到节点B和E转发过来的RREQ,如图3中节点H先接收到节点B转发过来的RREQ,并且不丢弃，节点H检查路由请求分组的目的节点不是节点H本身，同时将自己的地址信息加到RREQ中，该节点同样选择可调整的功率水平转发RREQ,将自己的功率水平信息加到RREQ功率值列表字段中，并转发该RREQ.此后，节点H接收节点E转发过来的RREQ,发现路由请求表中有对应的表项，丢弃掉该RREQ.

　　（4）同理，中间节点C接收到节点B和H转发过来的RREQ,图3中节点C先接收到节点B转发过来的RREQ,并且不丢弃，节点C检查路由请求分组的目的节点不是节点C本身，同时将自己的地址信息加到RREQ中，该节点同样选择可调整的功率水平转发RREQ,将自己的功率水平信息加到RREQ功率值列表字段中，并转发该RREQ.此后，节点C接收节点H转发过来的RREQ,发现路由请求表中有对应的表项，丢弃掉该RREQ.图3中（C,D）的功率水平值为15.

　　（5），直到所有RREQ到达目的节点D.如图3中（S,E,F,G）和（S,B,C）到达目的节点D.

　　3.3.2 路由应答过程

　　（1）目的节点D将自己的功率水平信息加到RREP中，并反向转发RREP,如图4所示。

　　（2）下一跳邻居节点C和G接收到RREP后，首先根据MEDSR协议中的功率水平调整机制进行功率的调整，并将计算Pmin存放到cache中的Power level字段。图4中C和G的Pmin都是15.然后进行临时剩余能量的计算 T:=R-P, C的剩余能量R是85,因此，C的T值为70.同理，G的T值为75,然后将自己的T赋值到RREP中的Path energy字段。（S,B,C,D）中，M:=70;（S,E,F,G,D）中，M:=75.继续转发RREP.

　　（3）次下一跳节点B和F接收到RREP后，首先根据MEDSR协议中的功率水平调整机制进行功率的调整，并将计算Pmin存放到cache中的Power level字段。如图4,B和F的Pmin都是15.然后进行临时剩余能量的计算T:=R-P,B的剩余能量R是70,因此B的T值为55.同理，F的T值为65,然后将自己的T值和RREP中的M值进行比较：

　　（S,B,C,D）中，55<70则E:=55;

　　（S,E,F,G,D）中，65<75则E:=65.

　　（4）所有中间节点进行临时剩余能量计算以及路径剩余能量计算操作后，向下一节点继续转发RREP,直到RREP到达源节点S.

　　（5）源节点S选取Path energy的RREP提供的路由信息进行数据分组的转发。

　　（S,B,C,D）中，E=55;

　　（S,E,F,G,D）中，E=65.

　　所以源节点S选取（S,E,F,G,D）进行数据分组的转发，并不是选择跳数较少的（S,B,C,D）进行数据分组的转发。

　　本文针对MEDSR协议中存在的问题对路由发现过程进行改进，加入能量感知策略，能量感知可使数据流平均地分布在网络的各个节点中，减少网络节点的过度使用，使网络分割的可能性减小，延长网络的使用寿命。