基于多商品流的网络能耗模型与智能算法研究
发布时间：2019-06-10 09:05
【摘要】：最近几十年,全球变暖导致的温室效应等一系列问题日益突出,发展低碳经济、节能减排已经成为各个行业的共识。在信息技术领域,节能问题同样不容小觑。近几十年信息技术的迅速发展,在所有工业中,信息通信产业所贡献的碳排放一直不断上升。根据数据显示,在所有人类制造业产生的二氧化碳排放中,单单信息通信设备就贡献了将近2%,这个数字与全球航空业相近,但是却有着比其更快的增长速度；并且,在英国等发达国家,这个数字甚至达到10%,在未来几年还有继续增长的趋势。在真实网络中,由于流量的突发性和周期性,大部分时间网络带宽的利用率不到40%。然而由于网络设备能耗与负载的相对独立,即使处于低利用率状态,设备的能耗也与峰值时相差无几。基于这种情况,人们提出了绿色网络(Green Network)的思想。在工程学角度,绿色网络的核心思想是在满足当前带宽需求和服务质量(Quality of Service, QoS)的情况下,使网络的能量消耗最小。这方面的研究有很多,我们按照优化的范围分为两个级别：一是设备级,设备级的能耗优化主要是集中在单个设备,比如路由器、交换机、线卡、网卡等。设备级的优化目标是使得单个设备的能耗与负载成比例,常见的优化方法有动态电压缩放、自适应链路速率、可扩展组件、流量预测等。二是网络级,网络级优化的目标是使整个网络的能耗与负载成比例,网络级优化主要是通过能量感知路由(Energy-Aware Routing, EAR)实现,这个问题已被归结为容量约束的多商品流问题(Capacitated Multi-commodity Net-work Flow, CMCF),而CMCF是NP完全的。设备级节能和网络级节能并不是互斥的,实际上在真实情况,网络级节能和设备级节能需要联合使用才能达到最好的节能效果。CMCF问题的基本思想是将所有网络流量聚合到整个网络拓扑的一个子集上,关闭或者休眠其他空闲的链路和节点,从而使得网络的整体的能耗与整体负载成比例,它的目标是找到满足需求的最小能耗子集。CMCF问题目前已经有了经典的数学模型,本文在此基础上将目的相同的需求进行了聚合,将变量数目减少了一个数量级,加快了求解速度。然而由于混合整数规划(Mixed Integer Programing,, MIP)是NP-hard的,在拓扑规模较大时计算时间变的不可接受,因此我们提出了一种基于克隆蚂蚁的蚁群优化路由算法(CACO-RA)。在算法中。我们将信息素按目的节点分类,最大限度的将流量聚合到较少的节点和链路；同时我们实现的是可分流的流量调度,充分利用了网络带宽。随机网络拓扑实验显示我们的算法有着比其他算法更少的能量消耗、更快的计算速度和更好的实用性。在CACO-RA算法中,我们使用了分流的思想最小化能耗,效果确实很好,然而这带来了另外一个问题——延迟增大。传统的基于最短路径的算法,延迟无疑是最小的,且流量都是单路径传输,不存在抖动问题。在CACO-RA算法中,我使用显式路由为每个需求对分配多条路径,这就带了延迟和抖动的问题。为了在能耗和QoS之间取得一个良好的折中,我们结合粒子群优化的思想修改了CACO-RA算法,我们将新算法命名为混合蚁群优化(Hybrid Ant Colony Optimization, HACO)。在HACO中,我们将CACO-RA的输出作为每个粒子的输入,每个粒子的适应度由QoS和负载均衡两个因素决定,每次迭代后粒子间通过子图合并来相互学习,经过多次迭代,最终我们会得到一个具有较低能耗、较小延迟、较优负载的网络子集。
[Abstract]:In recent decades, a series of problems such as greenhouse effect caused by global warming have become more and more prominent, and the development of low-carbon economy and energy-saving and emission reduction have become a consensus among the various industries. In the area of information technology, the problem of energy conservation is not the same. With the rapid development of information technology in recent decades, the carbon emissions from the information-communication industry have been rising in all industries. According to data, in all the carbon dioxide emissions from all human manufacturing, the information-only communication device has contributed nearly 2 per cent, which is close to the global aviation industry, but has its faster growth rate; and, in developed countries, such as the United Kingdom, This figure, even up to 10%, has a trend to continue to grow in the coming years. In the real network, the utilization rate of most of the network bandwidth is less than 40% due to the sudden and periodic traffic. However, due to the relatively independent energy consumption of the network equipment and the load, even in the low utilization state, the energy consumption of the equipment is similar to that of the peak value. On the basis of this, people put forward the idea of Green Network. At the angle of engineering, the core idea of the green network is to minimize the energy consumption of the network in the case of meeting the current bandwidth requirements and quality of service (QoS). There are a lot of research in this area. We are divided into two levels according to the scope of the optimization: the first is the equipment level, and the energy consumption optimization of the equipment level is mainly concentrated on a single device, such as a router, a switch, a line card, a network card, and the like. The device-level optimization goal is to make the energy consumption of a single device proportional to the load, and the common optimization method has the dynamic voltage scaling, the adaptive link rate, the scalable component, the flow prediction, and the like. The second is the network level. The goal of network-level optimization is to make the energy consumption of the whole network to be proportional to the load. The network-level optimization is mainly realized by Energy-Aware Routing (EAR), which has been attributed to the capacity-constrained multi-performance Net-work Flow (CCF). And the cmcf is np complete. The device-level energy-saving and network-level energy-saving are not mutually exclusive. In fact, in reality, the network-level energy-saving and the device-level energy-saving need to be used in combination to achieve the best energy-saving effect. The basic idea of the CMCF problem is to aggregate all network traffic to a subset of the entire network topology, close or sleep other free links and nodes, so that the overall energy consumption of the network is proportional to the overall load, and its goal is to find a subset of the minimum energy consumption that meets the requirements. The CCF problem is already a classical mathematical model. On the basis of this, the purpose of this paper is to carry out the aggregation, the number of variables is reduced by an order of magnitude, and the speed of the solution is accelerated. However, because mixed integer programming (MIP) is NP-hard, the computation time becomes unacceptable when the topological scale is large, so we propose an ant colony optimization routing algorithm based on the clone ant (CACO-RA). In that algorithm. We classify the pheromone according to the destination node, and aggregate the traffic to fewer nodes and links to the maximum extent; at the same time, we can realize the flow scheduling of the distributary, and make full use of the network bandwidth. The random network topology experiment shows that our algorithm has less energy consumption, faster calculation speed and better practicability than other algorithms. In the CACO-RA algorithm, we use the idea of shunting to minimize energy consumption, and the effect is really good, but this brings another problem _ delay increases. The traditional algorithm based on the shortest path, the delay is no doubt the minimum, and the traffic is single-path transmission, and there is no jitter problem. In that CACO-RA algorithm, I use an explicit route to assign multiple paths for each demand pair, which has the problem of delay and jitter. In order to get a good compromise between energy consumption and QoS, we have modified the CACO-RA algorithm in combination with the idea of particle swarm optimization, and we named the new algorithm as Hybrid Ant Colony Optimization (IGO). In the ODO, we use the output of CACO-RA as the input of each particle, the fitness of each particle is determined by two factors of QoS and load balance, the particles are combined with each other through the subgraph after each iteration, and after a plurality of iterations, A small delay, a subset of the network that is better loaded.
【学位授予单位】：山东大学
【学位级别】：硕士
【学位授予年份】：2016
【分类号】：TP18
本文编号：2496348
[Abstract]:In recent decades, a series of problems such as greenhouse effect caused by global warming have become more and more prominent, and the development of low-carbon economy and energy-saving and emission reduction have become a consensus among the various industries. In the area of information technology, the problem of energy conservation is not the same. With the rapid development of information technology in recent decades, the carbon emissions from the information-communication industry have been rising in all industries. According to data, in all the carbon dioxide emissions from all human manufacturing, the information-only communication device has contributed nearly 2 per cent, which is close to the global aviation industry, but has its faster growth rate; and, in developed countries, such as the United Kingdom, This figure, even up to 10%, has a trend to continue to grow in the coming years. In the real network, the utilization rate of most of the network bandwidth is less than 40% due to the sudden and periodic traffic. However, due to the relatively independent energy consumption of the network equipment and the load, even in the low utilization state, the energy consumption of the equipment is similar to that of the peak value. On the basis of this, people put forward the idea of Green Network. At the angle of engineering, the core idea of the green network is to minimize the energy consumption of the network in the case of meeting the current bandwidth requirements and quality of service (QoS). There are a lot of research in this area. We are divided into two levels according to the scope of the optimization: the first is the equipment level, and the energy consumption optimization of the equipment level is mainly concentrated on a single device, such as a router, a switch, a line card, a network card, and the like. The device-level optimization goal is to make the energy consumption of a single device proportional to the load, and the common optimization method has the dynamic voltage scaling, the adaptive link rate, the scalable component, the flow prediction, and the like. The second is the network level. The goal of network-level optimization is to make the energy consumption of the whole network to be proportional to the load. The network-level optimization is mainly realized by Energy-Aware Routing (EAR), which has been attributed to the capacity-constrained multi-performance Net-work Flow (CCF). And the cmcf is np complete. The device-level energy-saving and network-level energy-saving are not mutually exclusive. In fact, in reality, the network-level energy-saving and the device-level energy-saving need to be used in combination to achieve the best energy-saving effect. The basic idea of the CMCF problem is to aggregate all network traffic to a subset of the entire network topology, close or sleep other free links and nodes, so that the overall energy consumption of the network is proportional to the overall load, and its goal is to find a subset of the minimum energy consumption that meets the requirements. The CCF problem is already a classical mathematical model. On the basis of this, the purpose of this paper is to carry out the aggregation, the number of variables is reduced by an order of magnitude, and the speed of the solution is accelerated. However, because mixed integer programming (MIP) is NP-hard, the computation time becomes unacceptable when the topological scale is large, so we propose an ant colony optimization routing algorithm based on the clone ant (CACO-RA). In that algorithm. We classify the pheromone according to the destination node, and aggregate the traffic to fewer nodes and links to the maximum extent; at the same time, we can realize the flow scheduling of the distributary, and make full use of the network bandwidth. The random network topology experiment shows that our algorithm has less energy consumption, faster calculation speed and better practicability than other algorithms. In the CACO-RA algorithm, we use the idea of shunting to minimize energy consumption, and the effect is really good, but this brings another problem _ delay increases. The traditional algorithm based on the shortest path, the delay is no doubt the minimum, and the traffic is single-path transmission, and there is no jitter problem. In that CACO-RA algorithm, I use an explicit route to assign multiple paths for each demand pair, which has the problem of delay and jitter. In order to get a good compromise between energy consumption and QoS, we have modified the CACO-RA algorithm in combination with the idea of particle swarm optimization, and we named the new algorithm as Hybrid Ant Colony Optimization (IGO). In the ODO, we use the output of CACO-RA as the input of each particle, the fitness of each particle is determined by two factors of QoS and load balance, the particles are combined with each other through the subgraph after each iteration, and after a plurality of iterations, A small delay, a subset of the network that is better loaded.
【学位授予单位】：山东大学
【学位级别】：硕士
【学位授予年份】：2016
【分类号】：TP18
【相似文献】
相关期刊论文 前10条
1 许道云;;全息算法的原理及应用[J];计算机科学与探索;2011年02期
2 段海滨,王道波,朱家强,黄向华;蚁群算法理论及应用研究的进展[J];控制与决策;2004年12期
3 段海滨;王道波;于秀芬;;几种新型仿生优化算法的比较研究[J];计算机仿真;2007年03期
4 刘永广;叶梧;冯穗力;;一种基于非线性长度的多约束路由算法[J];计算机应用研究;2008年11期
5 刘永广;叶梧;冯穗力;;一种基于蚁群算法和非线性长度的多约束路由算法[J];通信技术;2009年08期
6 刘振;胡云安;;一种多粒度模式蚁群算法及其在路径规划中的应用[J];中南大学学报(自然科学版);2013年09期
7 罗景峰;;智能算法求解效果评价的物元模型[J];微电子学与计算机;2011年04期
8 刘芳,李阳阳;量子克隆进化算法[J];电子学报;2003年S1期
9 周雅兰;;细菌觅食优化算法的研究与应用[J];计算机工程与应用;2010年20期
10 胡红莉;张建州;;螺旋锥束CT重建的近似逆算法[J];计算机工程与应用;2011年21期
相关会议论文 前1条
1 董家瑞;王精业;潘丽君;;改进的Dijksta算法在装备保障系统中的应用[A];图像图形技术与应用进展——第三届图像图形技术与应用学术会议论文集[C];2008年
相关博士学位论文 前9条
1 高卫峰;人工蜂群算法及其应用的研究[D];西安电子科技大学;2013年
2 张捷;进化算法及智能数据挖掘若干问题研究[D];西安电子科技大学;2013年
3 程世娟;改进蚁群算法及其在结构系统可靠性优化中的应用[D];西南交通大学;2009年
4 杨振宇;基于自然计算的实值优化算法与应用研究[D];中国科学技术大学;2010年
5 郭庆昌;均值移动算法及在图像处理和目标跟踪中的应用研究[D];哈尔滨工程大学;2008年
6 金劲;群集智能算法在网络策略中的研究及其应用[D];兰州理工大学;2011年
7 郑乐;宽频带雷达目标跟踪理论与算法研究[D];北京理工大学;2015年
8 刘剑;非圆信号波达方向估计算法研究[D];国防科学技术大学;2007年
9 张瑞秋;面向SMT的锥束CT图像重构关键理论与BGA焊点检测算法[D];华南理工大学;2014年
相关硕士学位论文 前10条
1 黄林;空间复用MIMO系统接收端的球形译码检测算法研究[D];宁夏大学;2015年
2 牛丽娟;基于Gossip算法的无线传感器网络分布式参数场估计[D];哈尔滨工业大学;2015年
3 卓静一;液晶相控阵波前相位校正算法研究[D];电子科技大学;2014年
4 张莹;视频异常事件检测算法研究[D];大连理工大学;2015年
5 张博;基于多用户MIMO系统的鲁棒性信号检测算法研究[D];大连理工大学;2015年
6 陈望;基于混合算法的室内WLAN定位研究[D];新疆大学;2015年
7 陈宗文;霍夫森林框架下的多目标检测与跟踪算法研究[D];东北大学;2013年
8 张亚玲;卫星导航抗干扰算法研究及系统设计[D];西安电子科技大学;2014年
9 贾佳蔚;基于粒子滤波的检测前跟踪算法研究[D];电子科技大学;2015年
10 刘洪彬;Hadoop下基于边聚类的重叠社区发现算法研究[D];安徽工业大学;2015年
，本文编号：2496348
本文链接：https://www.wllwen.com/kejilunwen/zidonghuakongzhilunwen/2496348.html
