一种基于新的能量消耗模型的路由协议

《一种基于新的能量消耗模型的路由协议》由会员分享，可在线阅读，更多相关《一种基于新的能量消耗模型的路由协议（8页珍藏版）》请在金锄头文库上搜索。

1、http:/ - 1 -一种基于新的能量消耗模型的路由协议一种基于新的能量消耗模型的路由协议1 王博，李腊元，许重球 武汉理工大学计算机科学与技术学院，武汉（430063） E-mail: 摘摘 要：要：移动 Ad Hoc 网络是由一组无线移动主机组成的一个没有任何建立好的基础设施或 集中管理设备的临时网络。网络拓扑易变、带宽、能源有限是移动 Ad Hoc 网络的主要特点。 本文在介绍了一种新的能量消耗模型的基础上，提出了一种路由算法，由于该算法是一个 NP 难题，因此给出了一个近似算法，并在经典的路由协议 AODV 进行了实现与仿真实验。 实验结果表明新的协议EA_AODV在总能量消耗和网

2、络生存时间方面表现出了很好的性能。 关键词：关键词：能量模型；EA_AODV；近似算法；NP 难题 0. 引言引言 移动Ad Hoc 网络是由一组自主的无线节点或终端相互形成的，独立于固定的基础设施、采用分布式管理的多跳网络，是一种自创造、自组织和自管理的网络。而该网络的拓扑结构动态变化，无线链路带宽有限，以及节点各自的能量有限等特点导致Ad hoc网络的路由协议是当前研究的热点之一1。 Ad hoc网络节点能量受限的路由协议的研究是当前研究的热点，IETF的MANET小组提出的几种经典的路由协议， 都是最短路由， 即最小跳数路由， 没有考虑能量因素。 但是Ad hoc网络中的节点大部分是便携

3、式设备， 由尺寸受限的电池供电， 整个网络是一个能量受限系统，如何节省节点的能量，尽可能延长网络的可操控时间逐渐成为衡量路由协议性能的重要指标。特别是在紧急营救、军事行动、商务会议等情况下显得尤其重要。从能量的角度来看，最短路由并不一定是最佳的路由。相反，用一些短跳来代替相对较长的跳，可能是更好的节能选择2。 目前，Ad hoc中的节能路由算法主要有两个思路：第一个是使发送每个数据包耗费的能量最小3,4；第二个就是尽可能的延长网络的存活时间5,6。第一个思路的路由算法通过发现最小发射功率的路由，使发送每个数据包所耗费的能量最小，达到节省能量的目的。但是它还是保留了原先路由算法中的一个问题，就是

4、在选定了一条路由后，会一直用下去，直到数据发完或是拓扑变化触动路由更新，这样，同最小跳数路由协议一样，容易使某些关键节点因为过度使用而能量耗尽， 导致网络过早分裂。 第二个思路的路由算法就是针对这个问题提出的，通过保护剩余能量小的节点来达到推迟网络分裂，延长网络存活时间的目的。 由于这两个思路都考虑的比较片面， 本文的改进想法是综合这两个思路， 结合网络生存时间和节点的能量消耗两个目标条件， 并提出一种新的能量模型， 来保证各个节点的能量消耗均衡和延长网络的生存时间8。 1. 新的能量模型新的能量模型 利用图论的相关理论，Ad hoc 网络可以使用有向图 G=(V，E) 来描述，其中 V 是节

5、点的集合，E 是节点之间可以直接通信(在彼此的通信范围内)的链路集合，|V|=N，|E|=M。在传统的通信网络中，节点 u 和 v 的边(u，v)可以用跳数、链路容量和当前负荷来表示。但在这里表示能量消耗水平。 1本课题得到国家自然基金项目资助（批准号:60672137,90304018）的资助。 http:/ - 2 -vun vu vuSdP, ,|=)()()(, uEKduPuvu =根据信号传输模型，接收信号的功率可以用nd来表示，d 表示两个相互通信节点之间的传输距离。 通常当 n=2 表示两节点之间传输距离较近， n=4 表示传输距离较远。 在文献32中，给出了一个计算传输功率的

6、公式如下： 其 中是正数，vuS,为当前链路(u，v)之间的信道和干扰情况，vud,为 u 和 v 之间的距离，n 也取 2 或 4。 在本模型中，简化相关参数，得到如下的公式： vuvuKdP,= 其中 K 为正数，仍取 2 或 4，vud,意义如上。 定义一个有向图 Gs=(V，Es) 是 G 的一个子集。用)(vPt表示节点 v 在 t 时刻的剩余能量，为了简化方便，省略参数 t，用)(vP来表示。设节点 v 的初始能量为 E(v)。当一个节点jv在iv的传输范围之内，并且iv用)(ivP向jv发送数据包时，在 Gs图中jv和iv就有一条边直接相连。很明显，MEs|，EEs。 用)(uP

7、表示节点 u 在 t 时刻的剩余能量， 由于 v 是 u 直接相邻的节点， u 节点的剩余能量的比例(能量消耗速率)为： 在 Gs有向图中， 设 P 为有向链路(v0， v1)， (v1, v2), . . . , (vl1， vl) 连接的其中一条路径，v0 为源节点，vl为目的节点。 因此，要得到一条从 v0 到 vl的最优路由要满足以下两个条件： (1) 使得 P 路径上的传输能量消耗最少，即如下公式： (2) 确保 P 路径中的各个节点如 vi的能量消耗速率最小的最大化，即先保证各个节点的有最长的生存时间，再使得网络的生存时间最长。 ivMINMAX )(PVvi 2. 基于该能量模型

8、的路由算法基于该能量模型的路由算法 根据上节的能量模型， 我们所要求的最优的路由必须既要满足一条路径上的传输能量消耗最少，又要满足该路径上的任何节点的生存时间最长。从分析可以看出：该问题是个 NP难题，得到最优的结果是不可能的。因此我们构造近似的路由算法来确保得到一个次优解。 2.1 近似算法思想近似算法思想 在有向图Gs中，每一条边（链路）(vi, vi+1)的权重设为双重权重，表示为： )()()(,(1,1, ivvi vvvEKdvPuKdiiii +=其中第一项权重表示为节点的传输能量消耗，第二项权重表示为对应节点的生存时间。)()(10,1=+=lia vviikdMINPWhtt

9、p:/ - 3 -考虑到保证网络中各个节点的能量消耗均匀， 我们对各条路径上的能量消耗总和设置一个下限L ，为大于1的正数，L为一条路径上的最少跳数，上限为 Fv()，表示为从源节点到目的节点V的最高能量消耗。此外，设置一个，使得各个节点的能量消耗速率都不小于，0 FE但由于3 . 0，路由请求包 RREQ 只能发给 A 节点； 第二步：同样的方法，SAB 的能量消耗为 FB = FA+3=8，同时也满足 3 . 0； 第三步：B 的邻居节点是 C 和 F，SABC 的能量消耗 Fc= FB +4=12 ，而 FF= FB +3=11，同时到 C 和 F 节点都满足3 . 0，因此 RREQ

10、分别发送给 F 和 C； 第四步：F 和 C，D，E 直接相连，由于 F 到 E，C 的) do 2_levelMinlevelMax+;If FIND(Gs, , ) Then Min_level ; Else Max_level ; Endif Endwhile 图3 Find_Approximation_Path的伪代码形式 3. 近似算法的复杂性分析近似算法的复杂性分析 3.1 算法的正确性分析算法的正确性分析 在本文节的前面我们分析， 要同时满足两个目标条件得出一条最优的路由， 这显然是一个NP难题。因此我们就用一个近似的模型和算法得到一个可行解。设传输能量消耗最少的最优解为*P，最

11、快节点的能量的消耗速率则为*。 在Find_Approximation_Path(Gs，)函数，可以看出： Max_levelMin_levelMax_level Min_level，同时由于，* Max_level 和 Min_level Max_level，因此我们可以得出结论：*- Max_level-，所以我们肯定可以得到一个可行的解。 3.2 算法的时间复杂性分析算法的时间复杂性分析 整个的算法过程包括FIND(Gs， )和Find_Approximation_Path(Gs, )两个函数。而FIND(Gs, , ) 函数的机制类似于经典的最短路径算法Dijkstra s算法，它的时

12、间复杂 性为O(m+nlogn)。 在Find_Approximation_Path(Gs, )函数中，每次执行While循环，同时调用了FIND (Gs, ,)函数，因此，Find_Approximation_Path(Gs, )的时间复杂性就是两部分的积，即)_1log(nlogn)O(mlevelMinlevelMax+。 4. 仿真模型的建立仿真模型的建立 文中以NS27作为实验的仿真平台，在AODV9的基础上进行修改得出协议NA_AODV，比较它们两个在能耗、网络存活时间两个方面的相对性能。实验所需的网络拓扑由NS2的setdest工具生成，节点的运行速率和初始位置均随机设置，在整个

13、仿真时间内模拟出各节点的随机运行场景。整个实验场景的区域为500m500m，仿真时间为900s，节点运行的最大速率为15m/s。仿真场景的节点个数为25，初始能量分别为10，20，30，40个能量单位，停留时间为0，20，120，600，900。实验一共生成15种随机拓扑，每种情况对应5种，最后的数据为5种拓扑所产生数据的平均值。节点间的数据流由cbrgen工具随机设置，分别随机产生http:/ - 6 -20个发送者对20个接收者的udp流，每个CBR包的大小为512个字节，每秒发送4个包，带宽为2M，节点的发射半径为250m。实验中所用到的其他参数配置如下：信道和无线模型为two-ray

14、ground reflection model，MAC层使用IEEE 802.11的DCF(Distributed Coordination Function)。 5. 协议性能分析协议性能分析 图 4 到图 7 分别显示了在不同初始能量和停留时间下， 两种协议关于能量总消耗和网络生存时间的情况。 对这两个性能比较参数做如下说明： (1) 能量消耗：所有节点从 0s 到 900s 仿真的时间内的能量消耗之和。 (2) 网络生存时间：当网络中第一个节点发生死亡的时间或存活时间。 图 4 初始能量和总能量消耗 图 5 停留时间和总能量消耗 图 6 初始能量和网络生存时间 http:/ - 7 -图

15、 7 停留时间和网络生存时间 从图 4 可以看出，EA_AODV 协议的能量消耗稍微小些。因为该协议在找一条合适的路由时，考虑了各个节点能量的消耗量，同时也考虑了能量消耗速率，使得在满足以上两个因素的情况下，来减少总的能量消耗。图 5 显示了节点在不同停留时间的情况下，EA_AODV协议的能耗也教少， 这主要是由于停留时间的增加以及节能的策略的加入， 从而减少了节点能量的过快的消耗。图 6 反映了在 EA_AODV 协议在不同的初始能量下，网络的生存时间较长，由于我们在算法和模型中，在保证每个节点的最小能量消耗速率的前提下，尽量避免能量消耗过快的节点，从而提高了网络的生存时间。这个效果从图 7 也得到了表现。因此，从不同初始能量和停留时间两个方面来看，EA_AODV 协议都比 AODV 性能上有了明显的提高。但是，本文的改进只是建立在四个可能发生路由断裂的情况之上，因此发现其他可能出现的情况，快速建立备选路由和进行其他方面性能对比也是我们今后研究是另一个方向。 6. 结论结论 基于 Ad hoc 网络能量受限的路由算法的研究是一个热点，本文结合当前的研究背景，综合考虑了衡量节点能量消耗情况的两个方面， 即保证路径上的总能耗最小， 同时防止各个节点的能量消耗过快， 来满足各个节点是生存时间较