MANETs中能量感知-低拥塞的动态源路由

邢静宇，单平平

(南阳理工学院，河南 南阳 473000)

0 引 言

移动自组织网 (Mobile ad hoc Networks，MANETs)[1-2]是无中心控制单元、并由节点自行构建的无线网络。由于节点可自由移动，MANETs网络拓扑具有动态变化特性。而变化的拓扑使得网络通信链路不稳定。此外，节点通信距离有限，节点需要通过多跳通信才能将数据传输更远的目的节点。

多跳通信是由一系列的中间节点转发而形成的通信方式[3]。当拥有数据包的节点(源节点)需要以多跳通信方式向远距离的目的节点传输数据包时，源节点就需构建一条合适的路径。实际上，此路径也是由一系列的中间节点组成[4]。构建合适路径的过程也称为路由发现(Route-discovery)。然而，由于MANETs的拓扑动态变化、节点通信距离短等原因，有效地完成路由发现过程存在挑战。

针对MANETs网络特性，研究人员提出了许多路由协议[6-7]。这些协议可分为三类：按需路由、表格驱动路由以及混合路由。这些路由均需要实施路由发现过程。

在表格驱动路由中，节点得先获取并维持路由信息，并且移动节点能够周期地共享路由信息。在按需路由中，仅当节点需要传输数据包时，它才建立路径，节点无需预先维护路由信息，这也是按需路由的由来。而混合路由结合表格驱动路由和按需路由这两者特点。通常，混合路由将网络划分多个区域，在区域内和区域间实施不同的路由发现策略。在区域内实施表格驱动路由，而区域间实施按需路由，但是这种策略增加了路由开销。

动态源路由(Dynamic Source Routing, DSR)[8]是工作于TCP/IP协议簇的网际层的路由协议。通过发送路由请求、应答和确认请求等控制包，建立从源节点至目的节点的路。DSR是按需路由的代表，被广泛应用于MANETs。

为此，考虑到动态源路由(Dynamic Source Routing, DSR)的广泛应用性，分析了传统DSR路由的不足，并提出基于能量感知和低拥塞的DSR改进路由(Energy-aware and congestion-less -based DSR improved routing, EACL-DSR)。EACL-DSR路由在构建路由时，充分考虑了节点的拥塞率和能量信息，避免了传统DSR路由因流量不均衡而引起的拥塞问题。仿真数据表明，提出的EACL-DSR路由有效地提高了数据包传递率和吞吐量。

1 DSR路由及问题描述

DSR路由主要有两个阶段构成。在第一阶段，源节点构建通往目的节点的路由；在第二阶段，对上一阶段的构建的路由进行维护。当节点需要传输数据，它首先查询缓冲区[9]。此缓冲区存储已构建的路由。如果已有存在的路由，它就广播请求包RREQ。当邻居节点接收RREQ，它也沿着网络转播RREQ，直到它传输到目的节点。

RREQ包主要包括四项信息：数据包ID、源节点ID、目的节点ID、源IP地址、目的IP地址和跳数清单Hop_List，如表格1所示。

表1 DSR路由中RREQ格式

当目的节点接收到RREQ，它就沿传输RREQ反向路径，并以单播方式回复RREP，直到源节点接收RREP。当源节点接收RREP后，它就从RREP中提取已建的路由[10]，并存储于缓冲区，并选择最短路径传输数据包。RREQ和RREP的传输过程如图1所示。

图1 DSR路由发现阶段

为了维护路由，一旦中间节点数据传输失败，它就通过传输路由错误RERR包通知源节点。源节点收到RERR包，源节点就更新路由。如果缓存区内有可选的路由[11]，就直接从缓存区内选择新的路由。若没有，就重新构建新路由。

然而，DSR路由也存在一些不足。由于节点频繁地移动，DSR路由导致低的数据传递率，并提高了链路断裂概率。而链路断裂后，又需重新构建路由，这必然会增加路由开销，也会增加节点能量消耗。这些不足，促使需要对DSR路由进行改进。此外，DSR路由在进行路由发现时，仅转播第一时间所接收的RREQ，而并没有考虑到节点的信息，如能量、节点负载，这均不利于路由稳定。

2 EACL-DSR

EACL-DSR路由对DSR路由的发现阶段进行修改。传统的DSR路由总是选择最短路径传输数据，而没有考虑到能量和拥塞情况。若一直采用最短路径传输，势必会影响部分节点的负载过重，这不利于网内流量的平衡和路由的稳定。

在EACL-DSR路由中，一旦接收到RREQ包，节点就判断自己的拥塞率。如果拥塞率低于预定的阈值[12]，则接收该RREQ包，否则丢弃。一旦接收RREQ包后，节点就计算自己的适度因子(Fitness Factor, FF)，其包含了网络负载和节点剩余能量信息。随后，将FF值嵌入RREQ包，再继续向目的节点转播。

当中间节点接收RREQ包后，先确认是否第一次接收了该数据包。随后，再确认自己的拥塞率。如果拥塞率低于阈值，就接收，并从中提取包中的FF值，再判断FF值是否满足阈值。如果不满足，就不转播RREQ。否则，节点就计算的FF值，再嵌入RREQ包中，再转播，直至目的节点接收了该RREQ包。

当目的节点接收RREQ包，目的节点就依据传输RREQ包的反向路由回复RREP。当源节点接收RREP包后，就沿着该路径传输数据包。

2.1 拥塞率

拥塞率反映了节点当前需要传输的数据包数[13]。具体而言，每个节点均有一个缓存区，且缓存区的容量表示Buffer。而进入队列里的数据包，表示节点即将需要传输的数据包。用Numqueue表示进入队列里的数据包数。Numqueue占Buffer的比例越大，拥塞情况越严重。因此，节点i拥塞率ρi:

(1)

2.2 适度因子FF

FF在EACL-DSR路由协议中扮演着重要作用。传统的DSR路由，只是将第一时间接收的RREQ转播[14]，后期接收的RREQ并不理睬。而提出的EACL-DSR路由考虑了节点的拥塞率和适度因子。适度因子FF的定义如式(2)所示：

(2)

2.3 路由发现过程

EACL-DSR路由在转播RREQ时，充分考虑了节点拥塞率和适度因子[15]。路由发现过程如图2所示。具体而言，当源节点S需要向目的节点D传输数据时，节点S先确认它的缓存区内是否有通往节点D的路由，如果有，就依据此路由传输数据包。若没有，则节点S就开启路由发现过程。

图2 路由框架图

图2描述了路由发现过程。节点S先广播RREQ包(记为RREQ_S)，假定节点N1接收RREQ。然后节点N1先计算自己拥塞率ρN1，并判断ρN1是否小于阈值ρth。如果满足，则节点N1就接纳此RREQ。然后，节点N1就依据式(2)计算它的适度因子，并将FF插入RREQ包中，并转播RREQ包(记为RREQ_N1)。表2显示了EACL-DSR路由中的RREQ的格式：

表2 EACL-DSR路由中RREQ格式

假定节点N2接收了来自节点i的发送的RREQ_N1。类似地，节点N2先检测自己的拥塞率ρN2是否小于阈值ρth。如果满足，则接纳RREQ_N1。到目前为止，节点N2与节点N1的处理过程相似，但后续处理过程不同[16]。

随后，节点N2就从RREQ_N1提取FF值，并判断FF值是否大于阈值FFth。如果满足，则接纳RREQ_N1包，也计算自己FF值，然后插入RREQ_N1包中，再转播RREQ包(记为RREQ_N2)。

重复上述过程，直到目的节点D接收到RREQ包。一旦目的节点D接收了RREQ包，就沿着传输RREQ包的路径回复RREP包。当源节点接收了RREP，源节点就沿着此路径传输数据。

图3 RREQ的转播流程

2.4 路由发现示例

图4显示19个节点的网络拓扑结构，其中S、D分别表示源节点和目的节点。由于传统的DSR路由没有考虑节点能量和拥塞率信息，它通常只选择最短路径作为数据传输的通道，即S→N3→N6→N10→N14→D。

而EACL-DSR路由考虑了每个节点的拥塞率和FF值。假定每个节点的拥塞率和FF值如表3所示，其中ρth=0.3，FFth=30，Buffer=10。

图4 传统的DSR路由

在EACL-DSR路由中，源节点S先广播RREQ包。一旦接收RREQ包，源节点S的邻居节点确认是否满足它们的拥塞率。由于节点3不满足拥塞率(它的拥塞率大于阈值)，则节点3就丢弃RREQ包，而其他节点1、4满足要求，就接纳RREQ包。随后，这些节点将FF加入RREQ，再转播。

当节点5接收了来自节点4转播的RREQ包后，然后检测拥塞率和FF值。随后，再转播。重复上述过程，直到RREQ包传输至目的节点D。依据表3可知，节点N9、N13、N11、N16不满足条件，无法构建路由，最终形成了S→N1→N5→N6→N10→N14→D路径，如图5所示。

图5 EACL-DSR路由示例

3 数值分析

3.1 仿真场景

利用NS2.35仿真软件建立仿真平台[17-18]。N个节点随机分布于1500×1500 m2区域，节点的传输范围为250 m。具体的仿真参数如表4所示。

表4 仿真参数

为了更充分地分析EACL-DSR协议性能，建立两个仿真场景：密度场景和流量场景。在密度场景中，节点数从20～160变化，数据率为30 kbps；而在流量场景中，数据率从10～40 kbps变化，节点数100。

3.2 密度场景

首先分析节点数的变化对平均吞吐量的变化，实验数据如图6所示。

图6 平均吞吐量

从图6可知，当节点数为50时，EACL-DSR和DSR路由的吞吐量达到最高。然而，当节点数从50增加至150时，吞吐量也随之下降。原因在于：当节点数增加，参与路由的节点也随之增加，节点能耗也增加，加速了节点能量消耗速度。同时，节点数的增加会引起节点对信道资源的增加。最终，控制吞吐量。此外，与DSR路由相比，提出的EACL-DSR路由提高了网络吞吐量。

随后，分析了节点数对数据包传递率的变化，实验数据如图7所示。

图7 数据包传递率

图6的曲线变化与图6类似。当节点数大于50时后，数据包传递率随节点数的增加而下降。原因在于：当节点数增加至一定数量后，再增加节点数，会引用数据包传输的碰撞，最终，降低数据包传递率。与DSR路由相比，提出的EACL-DSR路由的数据包传递率得到有效地提升。这主要是因为：EACL-DSR路由在构建路由时，考虑了节点能量和拥塞信息，避免了拥塞率高的、低能量节点构建路由。

3.3 流量场景

数据率越快，网络内流量越大。本次实验分析数据率对吞吐量和数据包传递率的影响，实验数据分别如图8、图9所示。

图8 平均吞吐量

图9 平均数据包传递率

从图8可知，数据率的增加，有利于吞吐量的提升。这主要是因为：数据率越大，单位时间内传输的数据量就越多。但从图8可知，吞吐量与数据率并不完全呈线性关系。尽管数据率提高，但是只有网络能够成功传输数据，才能提高吞吐量。而EACL-DSR路由提高了平均吞吐量。这要归功于：EACL-DSR路由避免了拥塞率高的节点构建路由，增加了网终吞吐量。

图9显示了平均数据包传递率随数据率的变化曲线。从图9可知，数据率的增加降低了平均数据包传递率。原因在于：数据率的增加，加大了节点负载，提高了路由断裂的概率，最终，降低了数据包传递率。与DSR路由相比，提出的EACL-DSR路由提高了数据包传递率。

4 结 语

结合DSR路由，提出新的路由EACL-DSR。EACL-DSR路由以能量效率方式处理拥塞问题。提出的EACL-DSR路由不仅处理了拥塞，也提高能量利用率，进而延长了网络寿命。仿真数据表明，提出的EACL-DSR路由提高了网络吞吐量和数据包传递率。后期，将进一步优化路由算法，并考虑拥塞率和能量在适度因子中权重比例，并分析它们比例对路由性能的影响。