Ad Hoc网络中基于能量耗费和阻塞成本路由算法研究①

许 鹏

(合肥职业技术学院,安徽 合肥 230013)

0 引 言

无线Ad hoc网络是一种全部由无线装置构建的，无需任何基础架构，每个节点可随意移动并有发送和接收信息的装置，节点之间的所有通信都是通过相邻节点互相传递、交换信息实现。在无线ad hoc网络中，节点在处理运算、操作系统待机或传送数据时，都会消耗一定的电量，而这些无线装置通常用电池来提供能量，所以减少电源消耗至关重要。传统的路由选择协议(如：AODV、DSR)[1]都是选择最小跳数路径，并未考虑到电源消耗，如果选择的路径中有某个节点电量快要用完，将会造成网络分割，使得数据无法传送到目的节点，同时由于网络拥塞也会对能量消耗产生比较大的影响，因此需要设计一种减少能量消耗和阻塞成本的路由算法来有效延长电池的寿命来提升网络的吞吐量。

1 相关技术

1.1 AODV路由协议

AODV路由协议是反应式路由协议[3]。源节点想传送数据给某个目的节点，若路由表中尚无任何记录时，则启动路由发现程序去查找一条可达路径，并广播RREQ封包给相邻的节点，接收到此封包的节点会去比对其路由表中是否已经存在可达路径，若有，则比较其路由表中的目的端顺序号是否比RREQ中的目的端顺序号的值大，若较大或相等，但跳数较小，则单播一个路由应答封包至反向路径；若较小，必须把RREQ广播给下游的邻近节点。依此类推，直到到达目的节点。

在转送RREQ的过程中，每个节点会自动地设定反向路径。收到RREQ的中间节点会判断是从那一个相邻的节点收到的，并将此相邻节点的IP地址记录到自己的路由表里，并把跳数值加一，接着转送给下一个邻近节点，下一个邻近节点重复同样的步骤。在RREP反向回传到源节点的过程中，此路径上的每个节点都会设定一个转送指针，指向送来RREP的节点，并在路由表中更新此路由的时延。

1.2 PSR路由算法

节省能源路由算法一直是无线ad hoc网络研究的热点，Chai Keong Toh提出最小总传输功率路由(MTPR)[4]，在按需路由协议基础上考虑到电源因素。在传送数据前，计算每个节点的电量消耗，找出耗电量最少的路径来传送数据。缺点是当节点电量相同时，可能因为某个节点传送功率较大，耗电量也较大，将导致路径失效数据无法传送。而最小电池成本路由(MBCR)[5]是计算路径上每一节点所剩余的电量，找出一条总剩余电量最多的路径来传送数据。其缺点是路径中可能存在某些节点的电量不足，导致路径失效数据无法传送。

Singh等提出功率感知源路由(PSR)[6]，该方法与MBCR类似，不同之处在于PSR加入传送一个数据报文所消耗的电量大小、电量之间的比值及权重因子作为计算能量消耗的方式。缺点是将数据报文所消耗的电量大小设为常数，并非与传送功率或节点间距离有关，而且此方法只考虑剩余电量大小，并未考虑造成电量消耗快慢的因素，因此可能会找到剩余电量最大但电量消耗较快的路由。

1.3 Dijkstra 算法

Dijkstra 算法[7]是用来找出从单一节点到所有其他节点的最短路径的方法。首先以来源节点作始发节点，从相连且尚未被选定节点中，选定离来源节点距离最短的节点，并及时更新加入节点到其他节点的距离，通过此方法不断添加新的节点，直到所有的节点都被加入为止，即可求得最短路径。AODV、DSR路由协议在选择路径时也运用Dijkstra算法来求各节点之间的最短路径。

2 路由算法设计

将传统ad hoc网络中的AODV路由协议加入能量花费以及队列长度作为选择路径的依据，设计一种最小能量和阻塞成本路由算法(Minimum Energy and Jam Cost Routing，MEJCR)，利用这种算法可以找到花费能量最少的路由，从而有效延长电池的寿命。

在一般的路由协议中，通常只考虑传送功率Pt对能量成本的影响，但能量成本并非只与传送功率Pt有关，也与电子电路功率Pec有关。取Pec=15mW，则传送功率的大小与距离d有密切关系，如下式所示：

Ebit=Pt×Tbit+Pec×Tbit

(1)

Pt=Pr×dL

(2)

(3)

其中Rs为符率，以baud为单位；Pr为接受功率；L为路径损失指数；Ebit为单位能量消耗，b为每一符号的位数，与所用的调变方法有关。图1为常见的Rs和b所得到的Tbit值：

图1 常见的Tbit值

通过选择Rs和b值可将能量成本最小化，这里取Rs=1Msymbols/sec,b=2bits/symbols，则可将Ebit表示为：

Ebit=(0.5PrdL+7.5)nJ

(4)

路径损失指数L的值通常介于2～5之间，同时考虑到路径拥塞所造成的能量成本提升，需要加入避免拥塞的条件。当d=25m时，Pr=13nW，可以构建以下能量成本模型：

Cjk=

(5)

其中djk代表节点j与节点k之间的距离，Cjk为从节点j到节点k所需花费的能量，Q代表队列的大小，其值通常为0～10之间，Qthreshold为拥塞程度的临界值，、β，y为加权因子。在公式(5)中，前面部分为不考虑拥塞对于能量成本的影响，后面部分则是把队列长度作为拥塞程度的指标，而Qthreshold则作为拥塞严重程度的判别，当目前的队列大于Qthreshold值时，则表示拥塞程度较高，其所得到的能量成本值，相对于队列长度小于Qthreshold值时为大。

路径的能量成本为路径中各连接的能量成本总和，令(j,k)代表连接节点j与k的连接，s与d分别代表来源节点与目的节点，∏(s,d)为s到d之所有路径所成集合，π(s,d)∈∏(s,d)为s到d的一条路径，则π(s,d)的能量成本Cπ(s,d)可表示为：

(6)

最后从中选出一条花费成本为最小的路径R：

(7)

3 路由选择

通常一个ad hoc网络可被表示成一个图形的方式G=(V,E)，V(G)代表节点的集合，E(G)代表所有连接两个节点所形成的链路集合。假设每个节点的最大涵盖范围都相同，当E(G)中存在一条链路(j,k)，则节点j、k必须都在彼此的涵盖范围内。MEJCR构建在AODV路由协议之上，其选择路径时也与AODV路由协议一样运用到Dijkstra 算法来求各节点之间的最短路径。其路由原理为，当来源节点有数据要传给目的节点时，会先查看自己路由表中是否有路径可直接到达目的节点，若有，则利用此路径传送数据；若没有，则利用广播RREQ封包来找寻路径。当中间节点收到此报文时，会依据与前一个节点的距离以及目前队列长度的大小，来得到个别的链路成本，并将此连接成本加到RREQ报文的header上面，传往下一个节点，当下一个节点收到此RREQ报文时，将自己所计算出来的链路成本累加到RREQ封包的header上，依此类推，直到目的节点收到此RREQ封包为止。目的节点会从所有可能路径中挑选出一条总链路成本最小的作为回传RREP封包及传送数据封包的路径。

举例说明如下：如图2所示，连线上的数字代表两节点之间的距离，而队列图标里的数字表示目前队列的长度，当来源节点S有数据要传给目的节点D时， AODV路由协议选择路径是依据最小跳数，故选择S→3→D为传送数据路径，其每比特能量消耗为924nj。PSR路由协议以缩短节点之间距离为选择依据，其路径为s→1→2→3→5→d，每比特能量消耗为664nj，而MEJCR会在所有可能的路径中，选择队列长度总和最少的路径来做传送，其选择路径为s→1→3→4→d，其每比特能量消耗为最少的374nJ。

图2 路径的建立

4 仿真实验

利用模拟仿真实验来评估MEJCR算法，并且分别与AODV和PSR算法做比较。以下首先介绍实验模拟环境以及效能指标，接着对模拟结果加以分析。

4.1 实验环境设定

模拟环境设定及结果分析主要是采用VC++语言编写，分别在100×100、150×150、200×200、250×250、300×300m2区域范围内分布30个节点以及在100×100、200×200、300×300、400×400、500×500m2区域范围内分布50个节点，以探讨不同密度对于找寻路径所花费成本的影响。以同样数量的节点而言，分布范围越大，则节点密度越小。为提高实验结果的可信度，对每一种分布范围与节点数的组合，分别利用随机数生成100个不同的网络拓扑，而每一节点的队列长度也以随机数生成，其值介于0与10之间，最后结果以不同网络拓扑所得的平均值表示。在MEJCR中选择Qthreshold=7,β=2,γ=1。为简化仿真，假设网络中各节点的剩余电量与初始电量相同，用PSR法选择路径时，两者比值可忽略不计，其路径选择只需考虑距离因素。

使用三种效能指标来评估各种不同路由算法的优劣：(1)数据封包沿着各路由算法所选择路径所花费能量的比较；(2)省电率比较；(3)平均各节点拥塞程度比较。

4.2 结果分析

下图分别显示节点数为30和50的静态网络下，不同网络拓扑范围中三种不同算法每比特能量消耗的模拟结果。由此可见，MEJCR不论在网络拓扑范围小或大时，相较于其他两种方法所得到的每比特能量消耗都小，原因在于其选择路径时既考虑缩短链路的距离又考虑到网络拥塞造成的影响。图3、图4的差别是在其他条件相同的情况下，50个节点所花费的能量比30个节点少，原因在于50节点之间联机机率高，因此花费就小。

图3 30个节点的能量花费

图4 50个节点的能量花费

同时考虑到节省电源因素，将MEJCR所选出来的路径中各节点间的链路成本相加，再分别与AODV和PSR法做比较，其计算方式如下：

(8)

(9)

其中Cπ(s,d)(MEJCR|PSR|AODV)代表各种不同方法所选出来路径能量消耗总和。

图5、图6中显示，MEJCR算法相对于AODV、PSR算法都较省电，省电率为的53%(图5)以及51%(图6)。

图5 30个节点省电率

图6 50个节点省电率

图7,图8显示每个节点在不同方法中所得到的平均队列长度(与拥塞程度正关联)，MEJCR法比其他两种方法所得到的队列长度都小很多，介于2～4之间，因此能量花费也最少。其他两种方法所得到的平均队列长度差异不大，介于4～6之间。经能量成本模型计算后，AODV法由于本身所选的路径其节点之间的距离较远，而队列长度又不比其他方法小，因此其能量花费也最高。

图7 30个节点的平均拥塞程度

图8 50个节点的平均拥塞程度

5 结 论

将ad hoc网络中的传统的路由选择算法加以修改，设计一种新的有效节省电源的路由选择算法最小能量和阻塞成本路由算法，其选择路径的依据不但考虑最小能量消耗的问题，也进一步考虑拥塞对于能量消耗的影响。通过实验结果分析比较可知，这种方法可以有效减少电源消耗，同时也能够有效避免拥塞现象发生。