一种解决Ad hoc网络拥塞的优化算法

郭　晗,　范琳琳,　杜　润

(长春工业大学 基础科学学院， 吉林 长春　130012)



一种解决Ad hoc网络拥塞的优化算法

郭晗,范琳琳,杜润

(长春工业大学 基础科学学院， 吉林 长春130012)

摘要：提出了一种基于网络中信息流竞争的成本框架机制，利用链路中干扰的总成本对拥塞进行衡量，从而对拥塞问题进行分治处理，即将所要解决的问题分解为若干子问题，由此提出成本控制算法对拥塞问题进行优化。

关键词：Ad hoc网络； 路由协议； 竞争转发； 自组织

0引言

Ad hoc网络是一组带有无线接收和发送装置的移动节点组成的具有多跳、临时性、自组织等特征的网络系统。主要特点有无控制中心、节点移动、多跳无线连接，在军事通信、灾后紧急救援、传感器网络等环境中被广泛应用。

在互联网领域，TCP拥塞控制算法[1-3]已经比较成熟，能够作为保证网络性能稳定的一种重要手段。但是传统TCP的方法并不适合于Ad hoc网络，所以当网络拥堵出现时会导致Ad hoc网络的性能严重下降。因此,学者们将优化控制理论引入到Ad hoc拥塞控制当中，在这个过程中产生了很多用于提高Ad hoc网络性能的优化算法。比如文献[3]根据物理层的功率变化对拥塞控制的影响，提出了TCP Vegas和功率控制的联合优化算法[4-6]；文献[4]根据MAC对拥塞控制的影响，提出了拥塞控制和MAC的联合优化算法。然而这些算法并没有深入考虑Ad hoc网络具有多跳无线连接的这一特点，因此用于解决Internet拥塞的优秀算法并不能很好地适应Ad hoc的多源信息流相互竞争的特点。为了解决这种情况，文中构建了一个基于链路干扰集合的成本框架机制来解决Ad hoc网络中信息流相互竞争的问题，在框架中利用某一条信息链路的总成本来衡量本链路的拥塞程度，通过针对本链路成本的成本控制算法(Cost Control Algorithm， CCA)，将拥塞问题分解为若干相对独立的子问题并加以解决。最终结合Ad hoc网络节点的移动特性验证CCA算法在网络动态变化的情况下对于优化网络拥塞的适应性。实验结果表明，CCA算法的收敛性较好，对于网络动态变化的适应性有较高的自适应能力，从而使得Ad hoc网络的性能得到了一定程度的提高。

1问题描述

在解决Ad hoc网络中出现拥塞的情况时，假设在一定单位时间内的网络状态是稳定不变的[7-9]。用G=(WN，WL)来描述Ad hoc网络的结构，用WN={1,2,…,N}表示无线节点的集合，WL={1,2,…,L}表示无线链路的集合。并假设无线链路l∈L的数据传输量为Ci，IS={1,2，…，S}是网络中共享网络资源的所有信息流的集合。若每个信息流s∈S都是由源节点s发出并经过无线链路集合L(s)∈L到达目的节点，则称这种情况下的信息流为P2P，即节点到节点的多跳信息流，同时命名这条信息流在当前无线链路上的传输状态为信息子流。S(i)={s∈S,i∈L(s)}是流经当前无线链路的信息子流的集合。为了更好地描述信息子流之间相互竞争的关系，文中提出了干扰集合的概念，即无线链路w的干扰集W是由能够干扰信息子流，并且在无线链路w上进行传输的那些链路组成的集合。在信息子流相互竞争资源的过程中，某一特定时刻有且只有一个信息子流能够占用链路w。因此，在无线链路上进行传输的所有信息流的累加容量不能高于链路l的信道容量。

结合信息流在传输过程中的竞争特点，将Ad hoc网络的拥塞控制问题转换为线性优化问题，此时的目标是使所有源节点的总效用最大化，即有如下表达：

(1)

2成本控制算法CCA

结合式(1)以及成熟的优化理论可以知道，源节点在进行数据发送的过程中存在一个唯一的最优解。文中的CCA算法把原有的问题分解成多个并行的，可以进行分布式解决的子问题，并对分解后的各子问题进行求解。

2.1基本算法描述及分析

在无线网络中，每一个独立的节点的接收功率会随着路径的改变而发生变化，即接收端与发送端之间的距离越远，其接收功率就会变得越小，而理论上拥堵状况也会逐渐降到最低。拥堵降到最低时也是传输数据最弱、最不可靠的时刻，因此,在设计算法时需要考虑如何平衡拥堵与接收功率之间的关系。现将式(1)进行拉格朗日描述，其对应的拉格朗日函数为：

(2)

式中:p----整个无线链路中的解决拥堵时的成本，调整算法中的p即可完成网络拥堵的优化控制。

基于此，对CCA分析如下：

在理想情况下，Ad hoc网络的网络状态是稳定不变的，只有在这种情况下CCA的优化能力才是最理想的，对于求解的结果才是最实用有效的，为了使实际情况尽可能接近理想状况，在利用算法进行优化时要尽可能使其应用在最小的时间间隔内。与此同时,Ad hoc网络的网络状态的变化是随机、无序的，为此需要考察CCA适应网络变化的能力。

在验证过程中选取了现实中网络运行时3个阶段的网络状态，如图1所示。

图中包含了4个信息流f1、f2、f3、f4，且都经历了3种网络状态，链路源节点和目的节点在图中已经标记。假设信息的传输速率为0到600之间，链路4、5、8、10的网络容量取为2 500，其他链路的容量则取为1 000进行实验验证。

图1　网络运行时状态模拟图

2.2实验结果

在进行实验1时，假设CCA算法的初始解为65，从而验证CCA此时所具有的收敛性能。实验结果见表1。

表1　实验1的结果

在进行实验2时，假设仍在迭代65次的前提下，网络状态会从阶段1转换至阶段2，并且当迭代次数达到130次时，网络状态会从阶段2转换至阶段3，同时与AIMD算法对同样的数据进行比较，结果见表2。

为了充分体现CCA对网络动态变化所对应的实时响应及其性能，从表2可以看出，CCA与AIMD两种算法中，源节点的总效率函数的时间均值与全局效率函数的误差对比，CCA算法的效率较高，误差较小。

3结语

结合Ad hoc网络的状态多变以及其具有的多跳连接等特点，从信息流的成本控制角度出发，提出了成本控制算法CCA用以解决网络拥堵控制，通过实验表明，CCA算法的效率和误差都较低，能够有效提高网络拥堵的控制效率。

参考文献：

[1]李秀明.车载Ad hoc网络中基于位置的路由协议研究[D]．重庆:重庆交通大学，2011.

[2]Yang Shuangmao, Guo Wei, Tang Wei. National key laboratory of science and technology on communications [J]． University of Electronic Science and Technology of China, Chengdu,2014,39(6):130-13.

[3]郭浩洋.基于遗传算法的网络拥塞控制研究[D]．南昌：江西理工大学，2013.

[4]H Zhai, Y Fang. Medium aeeess control protoeolsin mobile Ad Hoe neorks: problemsand solutions.[D]．Florid: Teehnieal Rort, University of Florid,2004.

[5]Anon. ADASE: Advanced driver assistance systems in europe[EB/OL]．(2009-10-20)[2016-01-11]. http://www.adase2.net.

[6]Anon. COMCAR: Communication and mobility by cellular advanced radio[EB/OL]．(2009-10-20)[2016-01-11]. http://www.comcar.de.

[7]Anon. DRiVE: Dynamic radio for IP-services in vehicular environments [EB/OL]．(2009-10-20)[2016-01-11]. http://www.ist-drive.org.

[8]常促宇，向勇，史美林.车载自组织网的现状与发展[J]．通信学报，2007，28(11)：116-126.

[9]高伟峰.基于蚁群优化算法的Ad Hoc网络路由协议研究[D]．北京：北京交通大学，2014.

An optimization algorithm for solving the congestion of hoc Ad networks

GUO Han,FAN Linlin,DU Run

(School of Basic Sciences, Changchun University of Technology, Changchun 130012， China)

Abstract：A cost framework is put forward based on network information flow competition, and the total cost of link interference is used to evaluate the congestion. Consequently the congestion is classified into parts, and the cost control algorithm is applied to optimize the congestion.

Key words：Ad hoc network; routing protocol; competition forwarding; self-organization.

收稿日期：2016-01-11

作者简介：郭晗(1979-)，女，汉族，吉林长春人，长春工业大学讲师,硕士，主要从事计算机应用技术方向研究,E-mail:35550447@qq.com.

DOI:10.15923/j.cnki.cn22-1382/t.2016.2.19

中图分类号：TP 311

文献标志码：A

文章编号：1674-1374(2016)02-0200-03