无线自组织网络中一种拥塞意识的多径路由算法

袁永琼

(中国电子科技集团公司第20研究所通信事业部，陕西西安 710068)

无线组织网络是一种无需固定基础设施支撑的无线多跳网络，具有网络拓扑动态变化、带宽资源受限、链路不可靠等特性。针对以上特性，许多路由协议被提出，以克服这些限制提高网络的传输效率。

首先，在降低路由开销方面，按需路由协议仅建立和维护需要的路径，可有效降低路由的开销和路由表的缓存空间。近年来学者们已提出许多按需路由协议［1－2］。在现有的无线自组织网络按需路由协议中，其多采用简单洪泛机制实现路由发现。由于无线信道的广播特性，简单的洪泛虽保证了发现路由的最大可能性，但往往转发了较多冗余的路由控制分组。为此，学者们提出了一些改进算法。Gossip路由［3－4］和洪泛受限的路由协议［5］有效降低了路由开销。文献［3］提出的Gossip路由无论节点当前的链路状态和负载如何，所有节点均采用同一固定转发概率。为使Gossip机制更好地适用动态无线网络，根据节点网络状态来动态确定转发概率，可有效保证路由请求消息对网络节点覆盖的同时避免不必要的冗余转发。

其次，大多数单径路由协议通常依据某种路由度量选择一条路径传输数据。当源和目的节点之间的路径中任何链路中断，则必须重新唤起路由发现过程，这样将导致路由开销增加和数据分组传输时延增加。多径传输由于同时在多条路径上传输，而当其中一条路径中断时，其可以快速切换到其他路径上，从而缓解上述问题。多径路由能够提高数据分组传输的可靠性、平衡流量负载和节点的功率消耗，减低端到端时延和路由发现频率，解决频繁的拓扑变化而导致的不可靠通信服务［6－7］。近年来学者们已提出多种适用于无线多跳网络的按需多径路由协议［6－9］，有效平衡了网络流量负载和降低路由开销。上述多径路由协议多采用最短路径为路由度量。然而在无线自组织网络，由于链路质量、网络中流量负载不均衡和无线冲突，最小跳数路由难以找到高吞吐量路径。基于ETX的路由［10］已被验证在存在信道衰落的网络环境下是一种有效提高网络吞吐量的路由度量策略。但如果一条路径链路质量良好，但是路径中的节点有较长的队列，则其并不是最好的选择。

考虑到以上问题，文中提出了一种适用于无线自组织网络的多径路由算法——拥塞意识的多径路由算法(Congestion－aware Multipath Routing，CMR)。在路由发现阶段，根据网络节点的队列长度和路径跳数来动态确定转发概率，转发尽可能少的路由请求来覆盖几乎所有的节点，以有效降低路由开销。在多路径选择和流量分配阶段，以路径质量和节点的队列长度作为路由度量标准选择多条路径，以该路由度量值为依据进行流量分配，在使用高质量路径和避免拥塞热点之间做一个折衷。

1 拥塞意识的多径路由算法

CMR的核心思想主要包括两个部分:(1)路由发现。根据网络节点的队列长度和路径跳数来动态确定路由请求分组的动态转发转发概率。(2)路由选择和流量分配。以路径质量和节点的队列长度以路由度量标准进行路径的选择和流量分配。

1.1 基于Gossip机制的路由发现

在CMR路由算法的路由发现过程中，收到路由请求分组(Route REQuest，RREQ)的节点根据其负载的队列长度和路径的跳数来动态转发概率后再决定是否转发该分组。为避免路由请求消息过早消亡，通过接收到邻居节点转发的数量感知消息的传播情况作为一个补充保障手段，即如果中间节点第一次收到RREQ而且没有转发该请求，以一个延迟转发概率转发该请求。基于 Gossip的DSR路由发现机制具体如下:(1)源节点没有到达目的节点的路径时，向邻居节点广播路由请求RREQ。(2)中间节点收到该路由请求RREQ的处理流程如下:1)如果是第一次收到该路由请求RREQ且缓存中存在到达目的节点的路径，给源节点回复一个路由应答RREP。2)如果是第一次收到该路由请求RREQ且缓存中没有到达目的节点的路径时，记录其前一跳节点为NIdSD，按式(1)计算转发概率pforward。以概率pforward转发该路由请求RREQ。在没有转发的情况下，一定时间Ttimeout延迟后，以延迟转发概率pdelay继续转发该路由请求RREQ，防止其过早消亡。其中

式中，α，h为常数(0＜α ＜1，h≥1);mum_hops为路由请求表中路径的跳数;queue_size为节点的队列长度;pqs(queue_size)为根据queue_size确定的概率。

式中，n为时间Ttimeout内收到前两跳节点NIdSD广播的同一路由请求消息的数量。这里Timeout取i×Node_Traversal_time，i∈N，一般 i取 35，Node_Traversal_time是数据包平均一跳转移时间的保守估计，包括排队时间、处理时间、传输和传播时间。3)如果该节点已经收到过相同的RREQ，直接丢弃该包。(3)如果是目的节点收到RREQ，给源节点回复路由应答。

对于式(1)，pforward由路径跳数和节点负载队列长度联合确定。为使路由请求不过早地消亡，在消息刚开始传播时(h跳以内)以较高的概率充分扩散，h跳之外的节点降低转发概率。考虑无线自组织网络的规模，式(1)中h一般取2。节点的队列长度小于队列的期望长度时，表明节点的负载较轻，那么节点以较高的概率转发，反之表明节点的负载较重，那么节点以较低的概率转发。根据当前该节点的队列长度，基于文献［3］，概率pqs(queue_size)的计算如式(3)所示

1.2 拥塞意识的路由度量

在无线自组织网络中，常用的路径选择机制是以跳数度量的最短路径。该路由度量没有考虑网络中链路质量和流量负载，往往难以保证选中高吞吐量的路径。考虑路径质量的路径选择机制可以有效降低因丢包造成的重传延时，但路径中如果某个节点负载较重，从负载均衡的角度来说，应适当减少对该路径的使用以分散流量。考虑到以上因素，论文提出考虑链路质量和节点的队列长度作为路径度量准则，以 CRM表示。链路l(i，j)的CRM定义如下

其中，NQ为节点的期望队列长度。假设在入口处数据流的达到服从特征率为λ的负指数分布，每个数据分组的服务时间服从相同的概率分布且相互独立，采用M/G/1队列服务模型模拟。设Xi表示第i个到达分组的服务时间。随机变量(X1，X2，…)具有相同的概率分布且相互独立，到达时间间隔也相互独立。运用Pollaczek－Khinchin(P －K)和 Little公式［12］可得，队列的期望长度NQ为

其中，Qi(l)为节点i的平均队列长度;pl为分组丢包率。路径P的路由度量为

相比最小跳数的路由度量，CRMP综合考虑网络拓扑和流量负载，以一种统一的表达方式在使用高质量路径和避免拥塞之间做折衷。

1.3 路径选择与流量分配

经过路由发现过程，源节点获得多条到达目的节点的备选路径。路径选择和流量分配机制如下:源节点计算各条路径的CRMP，并按照CRMP值大小升序排列路径后选取前K条不相交路径，该不相交路径集表示为{Pi}Ki=1。其中，K为用户指定参数;K确定流量分配粒度。通常K是一个较小的整数，例如，K取2或3。按照式(7)确定每条路径的选择概率pp。

2 性能仿真

通过在网络仿真软件OPNET中实现了CMR和多径源路由算法(Multipath Source Routing，MSR)［2］，并进行了性能仿真和对比分析模拟的网络为2 200 m×900 m平面内150个移动节点随机均匀分布。MAC层协议为 IEEE 802.11 DCF，信道速率为 2 Mbit·s－1，每个节点的通信半径为250 m。网络业务负载为随机选择10对连接，并且每对链接在仿真开始30 s内随机发起业务流。对于移动性的模拟，使用随机路点模型RWP［13］，速度设置为［1 m/s，10 m/s］。业务流采用CBR形式，服从到达率为的负指数分布，数据有效载荷为2 Mbit，源节点产生分组速率从4 packet/s逐渐增加至16 packet/s。

仿真中主要评估3个性能:(1)成功投递率Packet Delivery Fraction——成功交付给目的节点的数据分组总数与源节点发送的数据分组总数的比值。(2)平均端到端时延Average end－to－end Delay——数据分组传输的平均端到端时延，包括所有可能引起的时延，如路径发现时间、排队时间、传输和传播时延、重传时间等。(3)标准化路由开销 Normalized Routing Overhead——定义为每交付给目的节点一个数据分组所需要发送的路由分组的数量。路由控制分组每被传输一跳，则计算一次路由分组发送。

通过仿真，在上述给定的仿真场景中，α取0.8时可以得到较高的分组交付率及较小的延迟，图1是α=0.8时的仿真结果。如图1所示，相比MSR，CMR有效提高了网络性能。图1(a)给出了不同流量负载下的分组送达率。随着流量负载的增加，CMR的分组投递率缓慢下降而MSR显著下降。这是因为在路径选择和流量分配方面，CMR考虑节点的队列长度和链路质量，有效避免网络拥塞热点，平衡了网络负载，减少重传和分组丢失。图1(b)给出了不同流量负载下的平均端到端时延。随着流量负载的增加，CMR的端到端时延增加显著小于MSR。图1(c)给出了不同流量负载下的标准化路由载荷。图1(c)所示，CMR的路由控制开销小于MSR。原因是，在路由发现过程中，CMR根据节点的网络状态动态地以一定的概率转发路由请求分组以避免不必要冗余转发，而MSR使用简单的洪泛转发机制，仿真结果表明根据网络节点的队列长度和路径的跳数确定的路由请求消息动态转发概率来决定分组是否转发，有效降低了路由开销。

图1 不同流量负载下性能

3 结束语

提出一种拥塞意识的多径路由算法。首先，根据网络节点的队列长度和路径跳数来动态确定路由请求消息的转发概率，保证路由请求消息对网络节点覆盖的同时避免不必要的冗余转发，以有效降低路由开销。其次，在多路径选择和流量分配阶段，以链路质量和节点的队列长度作为路由度量标准来选择多条路径，并以此为依据进行流量分配，在使用高质量路径和避免拥塞热点之间做一个折衷。仿真结果显示所提出的算法有效提高了网络的整体性能。

［1］MARINA M K，DAS S R.On － demand multipath distance vector routing in ad hoc networks［C］.Nineth International Conference on Network Protocols，2001:14 －23.

［2］WANG L，SHU Y，DONGM，et al.Adaptive multipath source routing in ad hoc networks［C］.Proc.of IEEE ICC，2001:867－871.

［3］HAAS Z J，HALPERN J Y.Gossip － based ad hoc routing［J］.IEEE/ACM Transactions on Networking，2006，14(3):479－491.

［4］BAKO B，SCHOCH E，KARGL F，et al.Advanced adaptive gossiping using 2－hop neighborhood information［C］.IEEE Globecom，2008:1 －6.

［5］JIANG Guoxing，YI Ming.Low overhead on － demand routing protocol for mobile ad hoc networks［J］.Journal on Communications，2009，30(7):27 －35.

［6］ABBASA M，JAIN B N.Analysis of disjoint multipath routing for mobile ad hoc networks［C］.Proc.of IEEE ICPWC 2005，2005:42 －46.

［7］VELERA A，SEAH W，RAOS.Improving protocol robustness in ad hoc networks through cooperative packet caching and shortest multipath routing［J］.IEEE Transactions on Mobile Computing，2005，4(5):443 －457.

［8］MARINA M K，DAS S R.On － demand multipath distance vector routing in ad hoc networks［C］.Nineth International Conference on Network Protocols，2001:14 －23.

［9］WANG L，SHU Y，DONGM，et al.Adaptive multipath source routing in ad hoc networks［C］.Proc.of IEEE ICC'2001，2001:867－871.

［10］COUTO D，AGUAYO D，BICKET J，et al.A high － throughput path metric for multi－ hop wireless routing［J］.Wireless Networks，2005，11(4):419 －434.

［11］LASSABE F，CHARLET D，CANALDA P，et al.Friis and iterative trilateration based WiFi devices tracking ［C］.Montbéliard，Sochaux，France:The 14th Euromicro International Conference on Parallel，Distributed and Network －Based Processing(PDP 2006)，2006:362 －365.

［12］DIMITRI B，ROBERT G.Data networks［M］.Newyork:Prentice Hall，1992.

［13］YOON J，LIU M，NOBLE B.Random waypoint considered harmful［C］.Proc.of IEEE Infocom，2003:1312－1321.