基于多目标拆分优化思维的拥塞网络数值调度方法*

陈鸿俊， 范太华， 穆　炯

(1. 西南科技大学 计算机科学与技术学院， 四川 绵阳 621010； 2. 四川水利职业技术学院 信息工程系， 成都 611231； 3. 四川农业大学 信息工程学院， 四川 雅安 625014)



基于多目标拆分优化思维的拥塞网络数值调度方法*

陈鸿俊1，2， 范太华1， 穆炯3

(1. 西南科技大学 计算机科学与技术学院， 四川 绵阳 621010； 2. 四川水利职业技术学院 信息工程系， 成都 611231； 3. 四川农业大学 信息工程学院， 四川 雅安 625014)

针对网络拥塞数值调度中存在的盲目性问题，提出了一种基于多目标拆分优化的网络拥塞数值调度方法.将拥塞网络的数值调度问题进行模型化表示，并将拥塞过程调度的最优问题分解为多个目标同时优化问题：即信道最优任务分配问题和路由拥塞调度问题.根据粒子群算法，对信道分配问题的最优解进行计算，同时设计约束模型并利用遗传算法求解拥塞调度问题，实现了在拥塞状态下的网络数值调度.结果表明，所提出算法获得的拥塞调度方案具有较好的可执行性.

网络拥塞； 目标拆分； 粒子群优化； 遗传算法； 数值调度； 信道分配； 网络吞吐

随着网络计算的快速发展，网络接入量逐渐呈现大数据的特点，当前网络受拥塞问题的影响越来越明显[1].网络接入量的不定和猛增给当前计算机网络信道容量带来了较大的负荷压力[2]，虽然网络带宽技术在不断完善，但远远不能满足网络吞吐量巨大的需求给网络任务的合理调度带来的问题[3-4].

在网络拥塞控制中，对数值的调度问题可以看成一个NP问题，针对这一问题，很多学者提出了不同的方法.文献[5]结合粒子群优化(PSO)方法对多种信息调度过程进行建模，以时间作为约束完成数据调度，由于网络调度数据种类差别较大，数据的网络接入时间和接入量存在较大的变化，所以PSO解决单一的NP问题存在较大的弊端；文献[6]提出了一种改进PSO的网络数据调度方法，虽然在原方法基础上进行了必要的改进，但由于调度过程本身存在矛盾，导致应用环境受限；文献[7]突出了基于遗传算法的网络资源调度优点，从链路调度与信道分配为目标函数构建标准，虽然已经具备了一定的任务拆分理论模型，但是由于选取的约束目标为硬件，导致应用被大大限制.本文提出了一种基于多目标拆分优化思维的拥塞网络数值调度方法，实现了在拥塞状态下网络数值调度.

1　拥塞状态下调度数据的多目标拆分

当网络发生拥塞时，其拥塞区域和路由区域会发生较为明显的变化，这种变化会直接反应到网络的MAC层和应用层.2个层级直接的关联性为0，故对拥塞资源进行调度的目标函数为

(1)

式中：U(r)为数据调度路径最大承载量；e为网络中的某个信道；E为常数；αe为宽带空闲系数，αe越大表示网络信道e上拥塞程度越严重.至此，对网络拥塞控制的问题可以分解为这2个层次相关的子问题，其中MAC层的分配可以表示为

(2)

式中：c、γ、q为MAC层、应用层及2层之间过渡时传输数据帧数；H为总传输数据帧数.

应用层上路由调度可以表示为

Subjectto(r，f)∈R

(3)

式中：fei为数据调度路径数量；S为总路径值；R为总传输数据队列长度；r、f分别为MAC层、应用层中传输数据队列长度.这样在拥塞过程中，数据调度的问题就自动转换为2个子问题了.

2　信道最优数据分配的求解过程

对拥塞状态下数据调度过程进行最优解计算，在任务完成分解的基础上，可以对这2个相互独立的子问题进行分别求解.

2.1信道数据分配过程的转换

在信道数据调度的最优解计算过程中，需要综合考虑信道容量和噪声因素的影响，故设计信道数据拥塞控制模型为

ce=blog(1+K)

(4)

式中：K和b为信道的容量参数和噪声参数；ce为数据传输速率.不同信道e和e′的关联度参数Iee′和分离度是可以通过计算得出的，例如，对于IEEE 802.11信道分离度和相关性如图1所示，Ie1e1=1.0，Ie1e2=0.790 6，Ie1e3=0.526 7和Ie1e5=0.通过以上关系可以得出：信道拥塞条件下数据分配问题可以表示为

(5)

式中，Ke为信道e传输数据量.

图1　802.11信道的分离度和相关性Fig.1　Resolution degree and dependency of 802.11 channel

2.2基于PSO算法的最优解计算

结合粒子群(PSO)算法[8-10]可以对上文中转换后的问题进行最优解的计算.结合粒子群算法强大的寻优能力，在信道数据最优调度过程中，结合式(5)最优解的计算过程如下：

1) 在信道数据分配过程中，初始化时用n代表信道中拥堵数据的级别，由m代表算法中的运算规模.

2) 在均衡化过程中，由pi(i=1，2，…，m)代表每个粒子位置，由pg代表全局最优位置，通过式(6)计算出相应的Z矩阵，即

(6)

式中，o为粒子的飞行速度.

3) 在信道数据的均衡化过程中，需要结合适当的约束条件，更新每个粒子pi(i=1，2，…，m)的位置，保证粒子的最优化.在一定的约束条件下，pi代表无限靠近全局最优位置.

4) 在均衡化过程中，判断是否达到最优信道数据调度均衡条件可以通过设定迭代次数完成.假如设定一个最大迭代次数，只要误差满足条件，则搜索停止，输出最优调度的结果；否则，继续计算.

在信道数据调度的均衡化过程中，需要对调度的结果进行验证，设定系数φe来测试信道调度结果的性能，信道e的验证函数为

φe=∑Iee′/de′

(7)

式中，de′为与信道e′最近节点的距离.软件算法的实现过程如下：

输入：信道数据，信道种类，约束条件

输出：最优数据调度结果

PSO

{设定参数信息；

对种群进行最优化设置；

设定式(5)的约束函数；

do

{粒子计算；

粒子和全局粒子最优解比较；

更新位置；

进行调度；

判断终止计算条件；

}

While(条件不满足)

}

2.3路由数据调度问题的约束

由于路由数据的突变性，故对其约束过程较为复杂.可以将路由的数据任务调度问题视为一个特定约束下的最优解计算问题，通过设定基础的约束问题模型，结合特定的寻优算法来求解路由数据最合理的调度方案，约束的过程可表示为

(8)

2.4基于遗传算法的调度最优解计算

在上述约束条件的基础上，利用遗传算法对调度过程进行最优解计算，其中变异时间参数为

pri(t)=p(t)hi(t)+npi(t)

(9)

式中，hi(t)、p(t)和npi(t)均为遗传算法中最优解计算过程中的均衡调节参数.定义响应函数为

(10)

k=Tfmaxfmin/B

(11)

式中：T为遗传算法下拥塞网络数值调度的总时间；fmax、fmin分别为遗传算法下拥塞网络数值调度的极限频率；B为遗传算法下进行数据调度产生的最小总费用.

调度均衡性的目标函数为

(12)

结合约束条件和目标函数完成最优解的计算，计算步骤如下：

输入：信道数据，信道种类，约束条件

输出：最优数据调度结果

遗传算法

{设定参数信息；

对遗传算法进行最优化设置；

设定式(8)的约束函数；

do

{变异时间参数计算；

最优解比较；

目标函数对比；

进行调度；

判断终止计算条件；

}

While(条件不满足)

}

3　实验与分析

3.1收敛性分析

以NS2为基础构建10×10的二维网状网络结构[11-13]，在此结构内随机布置30个节点来进行本文算法下收敛性的分析.其中，设定30个节点的初始功率为200 mW，在此基础上获取吞吐量与迭代次数的变化关系如图2～3所示.其中，图2和图3中所有的仿真实验条件和配置都相同，不同的是图2中每两个节点之间的距离为40～50 m，图3为25～30 m.

图2　稀疏网络下组播率的收敛性能Fig.2　Convergence performance of multicast rate under coefficient network

图3　密集网络下组播率的收敛性能Fig.3　Convergence performance of multicast rate under dense network

分析图2、3可知，虽然仿真实验条件和配置都相同，但是在节点间距离不同的情况下，算法的收敛速度也不同，因为节点之间的距离会对信号质量和干扰水平产生强烈影响.节点之间的距离小，接收从邻近节点发射的信号质量低，干扰水平也低，但是并不会对吞吐量产生很大影响，收敛曲线的变化不显著.研究表明，拓扑结构和干扰算法的收敛速度不会对系统产生强烈影响，合理选择初始值，并及时更新变量的步长，可以保证算法的收敛性.

为了进一步验证改进数值调度方法的性能，在调度数据量一定的情况下，采用改进的数值调度方法与文献[6]、[7]所用方法进行对比验证，比较结果如图4所示.

图4　不同算法的调度时间对比图Fig.4　Contrast in scheduling time of different algorithms

从图4可以看出，在调度数据量一定的情况下，采用改进方法进行数值调度，其调度时间约为4 s；采用文献[7]方法进行数值调度，其调度时间约为6.4 s；采用文献[6]调度时间约为7.2 s.改进算法相比文献[6]、文献[7]方法均有一定的优越性.

3.2性能分析

首先构建Mesh无线网络，在面积为2 000 m×2 000 m的区域内随机分布30和55个节点，分别建立了稀疏和高密集二维网格进行本文算法性能分析.设定传播范围和干扰范围为100 m，将实验中所有节点都在IEEE 802.11协议下运行[14-15]，将最初的传输功率设定为200 mW.在稀疏和高密集二维网格中，随机选取40%的节点作为接收节点，随机分配5%的节点作为网关节点.以干扰模型为依据进行分析，若对象i或对象j位于公共信道进行通信，并且在x或y的干扰区间内，则通信链路(i，j)和(x，y)为相互干扰关系.

本文采用网络干扰比值对算法的性能进行评估.网络干扰比值是指网络干扰总体信道数量与网络干扰潜在信道数量的比值，也等于信道分配后多信道网络干扰数量与单信道网络干扰数量的比值.

仿真实验中，将每个网络节点都配备2～12个设备，其中，在24个信道的稀疏和高密度网络环境下，网络干扰比值比较结果如图5所示.由图5a可知，与其它传统算法相比，本文算法下网络干扰比值最小，在24个信道和4个设备的配置环境下，本文算法、文献[6]、[7]计算的网络干扰比值分别为0.269，1.767，1.228，本文算法平均网络干扰值相对文献[6]、[7]分别降低了84.8%和78.1%.由图5b可知，与稀疏网络相比，高密度网络环境下的网络拓扑结构的节点数和链路数量增多.通过分析可知，本文算法网络下计算的网络干扰比值最小，在4个设备的配置环境下，与文献[6]、[7]计算的网络干扰比值相比降低了87.1%和80.6%.

图5　24信道下的网络干扰比值Fig.5　Network interference value under channel

4　结　语

本文提出了一种基于多目标拆分优化思维的拥塞网络数值调度方法.首先将拥塞网络的数值调度问题进行模型化表示，然后将拥塞过程调度的最优问题分解为多个目标同时优化问题：信道最优任务分配问题和路由拥塞调度问题，根据粒子群算法对信道分配问题的最优解进行计算，同时设计约束模型，利用遗传算法求解路由拥塞调度问题.但是实验中存在调度时间过长的情况，是下一步需要解决的问题.

[1]冯琳函，钱志鸿，金冬成.增强型的无线mesh网络信道分配方法 [J].通信学报，2012，33(10)：44-50.

(FENG Lin-han，QIAN Zhi-hong，JIN Dong-cheng.Research on enhanced channel assignment scheme in wireless mesh network [J].Journal on Communications，2012，33(10)：44-50.)

[2]Zeng G，Wang B，Ding Y，et al.Efficient multicast algorithms for multichannel wireless mesh networks [J].Parallel and Distributed Systems，IEEE Transactions，2012，21(1)：86-99.

[3]苏丹，李章勇，章敬雪，等.基于转发节点的无线体域网动态信道研究 [J].重庆邮电大学学报(自然科学版)，2015，27(2)：235-240.

(SU Dan，LI Zhang-yong，ZHANG Jing-xue，et al.Dynamic body communication channels base-relay nodes for wireless body area networks [J].Journal of Chongqing University of Posts and Telecommunications(Natural Science Edition)，2015，27(2)：235-240.)

[4]罗成，谢维信.传感器网络拥塞避免与控制的模糊AQM算法 [J].电子学报，2014，10(4)：679-684.

(LUO Cheng，XIE Wei-xin.Fuzzy AQM for congestion avoidance and control in sensor networks [J].Electronic Journals，2014，10(4)：679-684.)

[5]Cheng H，Xiong N，Vasilakos A V，et al.Nodes organization for channel assignment with topology pre-servation in multi-radio wireless mesh networks [J].Ad Hoc Networks，2012，10(5)：760-773.

[6]Peng Y，Yu Y，Guo L，et al.An efficient joint channel assignment and QoS routing protocol for IEEE 802.11 multi-radio multi-channel wireless mesh networks [J].Journal of Network and Computer Applications，2013，36(2)：843-857.

[7]Jahanshahi M，Dehghan M，Meybodi M R.On channel assignment and multicast routing in multi-channel multi-radio wireless mesh networks [J].International Journal of Ad Hoc & Ubiquitous Computing，2013，12(4)：225-244.

[8]肖春静，刘明，龚海刚，等.无线 Mesh 网络低干扰组播 [J].软件学报，2013，24(6)：1295-1309.

(XIAO Chun-jing，LIU Ming，GONG Hai-gang，et al.Low-interference multicast in wireless Mesh networks [J].Journal of Software，2013，24(6)：1295-1309.)

[9]吴志强，吴艳洁.基于OpenFlow的网络拥塞控制机制研究 [J].河南理工大学学报(自然科学版)，2015，34(4)：547-549.

(WU Zhi-qiang，WU Yan-jie.Study on network congestion control mechanism based on OpenFlow [J]Journal of Henan Polytechnic University(Natural Science)，2015，34(4)：547-549.)

[10]Condat L.A primal-dual splitting method for convex optimization involving lipschitzian，proximable and linear composite terms [J].Journal of Optimization Theory & Applications，2013，158(2)：460-479.

[11]孔金生，任平英.TCP网络拥塞控制研究 [J].计算机技术与发展，2014，24(1)：43-46.

(KONG Jin-sheng，REN Ping-ying.Summary of TCP network congestion control research [J]Computer Technology and Development，2014，24(1)：43-46.)

[12]Karimi O B，Liu J，Li Z.Multicast with cooperative gateways in multi-channel wireless mesh networks [J].Ad Hoc Networks，2014，12(1)：170-180.

[13]Sarafrazi S，Nezamabadi P H，Saryazdi S.Disruption：a new operator in gravitational search algorithm [J].Scientia Iranica，2011，18(3)：539-548.

[14]邝祝芳，陈志刚.认知无线Mesh网络中一种有效的多目标优化频谱分配算法 [J].中南大学学报(自然科学版)，2013，44(6)：124-129.

(KUANG Zhu-fang，CHEN Zhi-gang.A effective multi-objective optimization spectrum allocation algorithm in cognitive wireless Mesh networks [J].Journal of Central South University (Science and Techno-logy)，2013，44(6)：124-129.)

[15]宫华，张彪，许可.并行机生产与成批配送协调调度问题的近似策略 [J].沈阳工业大学学报，2015，37(3)：324-328.

(GONG Hua，ZHANG Biao，XU Ke.Approximation strategy for coordinated scheduling problem in production and batch delivery of parallel machines [J].Journal of Shenyang University of Technology，2015，37(3)：324-328.)

(责任编辑：景勇英文审校：尹淑英)

Numerical scheduling method for network congestion based on multi-objective resolution optimization

CHEN Hong-jun1, 2, FAN Tai-hua1, MU Jiong3

(1. School of Computer Science and Technology, Southwest University of Science and Technology, Mianyang 621010, China; 2. Department of Information Engineering, Sichuan Water Conservancy Vocational College, Chengdu 611231, China; 3. College of Information Engineering, Sichuan Agricultural University, Ya’an 625014, China)

In order to solve the blindness problem existing in the numerical scheduling of network congestion, a numerical scheduling method for network congestion based on multi-objective resolution optimization was proposed. The modeling expression for the numerical scheduling problem of network congestion was carried out. In addition, the optimal problem of congestion process scheduling was decomposed into the multi-objective optimization problem at the same time, namely the optimal task allocation problem of channel and routing congestion scheduling problem. According to the particle swarm optimization (PSO) algorithm, the calculation for the optimal solution of channel allocation problem was performed. Meanwhile, the constraint model was designed, and the congestion scheduling problem was solved with the genetic algorithm (GA). Moreover, the numerical scheduling of network at the congestion state was realized. The results show that the congestion scheduling scheme in the proposed algorithm has good enforceability.

network congestion; target resolution; particle swarm optimization; genetic algorithm (GA); numerical scheduling; channel allocation; network throughput

2016-01-27.

四川省教育厅资助项目(14ZB0113，12ZB326).

陈鸿俊(1981-)，男，四川成都人，讲师，主要从事计算机软件设计和数据处理等方面的研究.

10.7688/j.issn.1000-1646.2016.04.14

TP 393

A

1000-1646(2016)04-0440-05

*本文已于2016-05-12 14∶02在中国知网优先数字出版. 网络出版地址： http：∥www.cnki.net/kcms/detail/21.1189.T.20160512.1402.042.html