基于多商品流的網絡能耗模型與智能算法研究
發(fā)布時間：2019-06-10 09:05
【摘要】：最近幾十年,全球變暖導致的溫室效應等一系列問題日益突出,發(fā)展低碳經濟、節(jié)能減排已經成為各個行業(yè)的共識。在信息技術領域,節(jié)能問題同樣不容小覷。近幾十年信息技術的迅速發(fā)展,在所有工業(yè)中,信息通信產業(yè)所貢獻的碳排放一直不斷上升。根據數據顯示,在所有人類制造業(yè)產生的二氧化碳排放中,單單信息通信設備就貢獻了將近2%,這個數字與全球航空業(yè)相近,但是卻有著比其更快的增長速度；并且,在英國等發(fā)達國家,這個數字甚至達到10%,在未來幾年還有繼續(xù)增長的趨勢。在真實網絡中,由于流量的突發(fā)性和周期性,大部分時間網絡帶寬的利用率不到40%。然而由于網絡設備能耗與負載的相對獨立,即使處于低利用率狀態(tài),設備的能耗也與峰值時相差無幾�；谶@種情況,人們提出了綠色網絡(Green Network)的思想。在工程學角度,綠色網絡的核心思想是在滿足當前帶寬需求和服務質量(Quality of Service, QoS)的情況下,使網絡的能量消耗最小。這方面的研究有很多,我們按照優(yōu)化的范圍分為兩個級別：一是設備級,設備級的能耗優(yōu)化主要是集中在單個設備,比如路由器、交換機、線卡、網卡等。設備級的優(yōu)化目標是使得單個設備的能耗與負載成比例,常見的優(yōu)化方法有動態(tài)電壓縮放、自適應鏈路速率、可擴展組件、流量預測等。二是網絡級,網絡級優(yōu)化的目標是使整個網絡的能耗與負載成比例,網絡級優(yōu)化主要是通過能量感知路由(Energy-Aware Routing, EAR)實現,這個問題已被歸結為容量約束的多商品流問題(Capacitated Multi-commodity Net-work Flow, CMCF),而CMCF是NP完全的。設備級節(jié)能和網絡級節(jié)能并不是互斥的,實際上在真實情況,網絡級節(jié)能和設備級節(jié)能需要聯合使用才能達到最好的節(jié)能效果。CMCF問題的基本思想是將所有網絡流量聚合到整個網絡拓撲的一個子集上,關閉或者休眠其他空閑的鏈路和節(jié)點,從而使得網絡的整體的能耗與整體負載成比例,它的目標是找到滿足需求的最小能耗子集。CMCF問題目前已經有了經典的數學模型,本文在此基礎上將目的相同的需求進行了聚合,將變量數目減少了一個數量級,加快了求解速度。然而由于混合整數規(guī)劃(Mixed Integer Programing,, MIP)是NP-hard的,在拓撲規(guī)模較大時計算時間變的不可接受,因此我們提出了一種基于克隆螞蟻的蟻群優(yōu)化路由算法(CACO-RA)。在算法中。我們將信息素按目的節(jié)點分類,最大限度的將流量聚合到較少的節(jié)點和鏈路；同時我們實現的是可分流的流量調度,充分利用了網絡帶寬。隨機網絡拓撲實驗顯示我們的算法有著比其他算法更少的能量消耗、更快的計算速度和更好的實用性。在CACO-RA算法中,我們使用了分流的思想最小化能耗,效果確實很好,然而這帶來了另外一個問題——延遲增大。傳統(tǒng)的基于最短路徑的算法,延遲無疑是最小的,且流量都是單路徑傳輸,不存在抖動問題。在CACO-RA算法中,我使用顯式路由為每個需求對分配多條路徑,這就帶了延遲和抖動的問題。為了在能耗和QoS之間取得一個良好的折中,我們結合粒子群優(yōu)化的思想修改了CACO-RA算法,我們將新算法命名為混合蟻群優(yōu)化(Hybrid Ant Colony Optimization, HACO)。在HACO中,我們將CACO-RA的輸出作為每個粒子的輸入,每個粒子的適應度由QoS和負載均衡兩個因素決定,每次迭代后粒子間通過子圖合并來相互學習,經過多次迭代,最終我們會得到一個具有較低能耗、較小延遲、較優(yōu)負載的網絡子集。
[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 段海濱;王道波;于秀芬;;幾種新型仿生優(yōu)化算法的比較研究[J];計算機仿真;2007年03期
4 劉永廣;葉梧;馮穗力;;一種基于非線性長度的多約束路由算法[J];計算機應用研究;2008年11期
5 劉永廣;葉梧;馮穗力;;一種基于蟻群算法和非線性長度的多約束路由算法[J];通信技術;2009年08期
6 劉振;胡云安;;一種多粒度模式蟻群算法及其在路徑規(guī)劃中的應用[J];中南大學學報(自然科學版);2013年09期
7 羅景峰;;智能算法求解效果評價的物元模型[J];微電子學與計算機;2011年04期
8 劉芳,李陽陽;量子克隆進化算法[J];電子學報;2003年S1期
9 周雅蘭;;細菌覓食優(yōu)化算法的研究與應用[J];計算機工程與應用;2010年20期
10 胡紅莉;張建州;;螺旋錐束CT重建的近似逆算法[J];計算機工程與應用;2011年21期
相關會議論文 前1條
1 董家瑞;王精業(yè);潘麗君;;改進的Dijksta算法在裝備保障系統(tǒng)中的應用[A];圖像圖形技術與應用進展——第三屆圖像圖形技術與應用學術會議論文集[C];2008年
相關博士學位論文 前9條
1 高衛(wèi)峰;人工蜂群算法及其應用的研究[D];西安電子科技大學;2013年
2 張捷;進化算法及智能數據挖掘若干問題研究[D];西安電子科技大學;2013年
3 程世娟;改進蟻群算法及其在結構系統(tǒng)可靠性優(yōu)化中的應用[D];西南交通大學;2009年
4 楊振宇;基于自然計算的實值優(yōu)化算法與應用研究[D];中國科學技術大學;2010年
5 郭慶昌;均值移動算法及在圖像處理和目標跟蹤中的應用研究[D];哈爾濱工程大學;2008年
6 金勁;群集智能算法在網絡策略中的研究及其應用[D];蘭州理工大學;2011年
7 鄭樂;寬頻帶雷達目標跟蹤理論與算法研究[D];北京理工大學;2015年
8 劉劍;非圓信號波達方向估計算法研究[D];國防科學技術大學;2007年
9 張瑞秋;面向SMT的錐束CT圖像重構關鍵理論與BGA焊點檢測算法[D];華南理工大學;2014年
相關碩士學位論文 前10條
1 黃林;空間復用MIMO系統(tǒng)接收端的球形譯碼檢測算法研究[D];寧夏大學;2015年
2 牛麗娟;基于Gossip算法的無線傳感器網絡分布式參數場估計[D];哈爾濱工業(yè)大學;2015年
3 卓靜一;液晶相控陣波前相位校正算法研究[D];電子科技大學;2014年
4 張瑩;視頻異常事件檢測算法研究[D];大連理工大學;2015年
5 張博;基于多用戶MIMO系統(tǒng)的魯棒性信號檢測算法研究[D];大連理工大學;2015年
6 陳望;基于混合算法的室內WLAN定位研究[D];新疆大學;2015年
7 陳宗文;霍夫森林框架下的多目標檢測與跟蹤算法研究[D];東北大學;2013年
8 張亞玲;衛(wèi)星導航抗干擾算法研究及系統(tǒng)設計[D];西安電子科技大學;2014年
9 賈佳蔚;基于粒子濾波的檢測前跟蹤算法研究[D];電子科技大學;2015年
10 劉洪彬;Hadoop下基于邊聚類的重疊社區(qū)發(fā)現算法研究[D];安徽工業(yè)大學;2015年
，本文編號：2496348
本文鏈接：http://www.sikaile.net/kejilunwen/zidonghuakongzhilunwen/2496348.html
