發(fā)布時(shí)間：2019-06-10 09:05

【摘要】：最近幾十年,全球變暖導(dǎo)致的溫室效應(yīng)等一系列問(wèn)題日益突出,發(fā)展低碳經(jīng)濟(jì)、節(jié)能減排已經(jīng)成為各個(gè)行業(yè)的共識(shí)。在信息技術(shù)領(lǐng)域,節(jié)能問(wèn)題同樣不容小覷。近幾十年信息技術(shù)的迅速發(fā)展,在所有工業(yè)中,信息通信產(chǎn)業(yè)所貢獻(xiàn)的碳排放一直不斷上升。根據(jù)數(shù)據(jù)顯示,在所有人類制造業(yè)產(chǎn)生的二氧化碳排放中,單單信息通信設(shè)備就貢獻(xiàn)了將近2%,這個(gè)數(shù)字與全球航空業(yè)相近,但是卻有著比其更快的增長(zhǎng)速度；并且,在英國(guó)等發(fā)達(dá)國(guó)家,這個(gè)數(shù)字甚至達(dá)到10%,在未來(lái)幾年還有繼續(xù)增長(zhǎng)的趨勢(shì)。在真實(shí)網(wǎng)絡(luò)中,由于流量的突發(fā)性和周期性,大部分時(shí)間網(wǎng)絡(luò)帶寬的利用率不到40%。然而由于網(wǎng)絡(luò)設(shè)備能耗與負(fù)載的相對(duì)獨(dú)立,即使處于低利用率狀態(tài),設(shè)備的能耗也與峰值時(shí)相差無(wú)幾�；谶@種情況,人們提出了綠色網(wǎng)絡(luò)(Green Network)的思想。在工程學(xué)角度,綠色網(wǎng)絡(luò)的核心思想是在滿足當(dāng)前帶寬需求和服務(wù)質(zhì)量(Quality of Service, QoS)的情況下,使網(wǎng)絡(luò)的能量消耗最小。這方面的研究有很多,我們按照優(yōu)化的范圍分為兩個(gè)級(jí)別：一是設(shè)備級(jí),設(shè)備級(jí)的能耗優(yōu)化主要是集中在單個(gè)設(shè)備,比如路由器、交換機(jī)、線卡、網(wǎng)卡等。設(shè)備級(jí)的優(yōu)化目標(biāo)是使得單個(gè)設(shè)備的能耗與負(fù)載成比例,常見(jiàn)的優(yōu)化方法有動(dòng)態(tài)電壓縮放、自適應(yīng)鏈路速率、可擴(kuò)展組件、流量預(yù)測(cè)等。二是網(wǎng)絡(luò)級(jí),網(wǎng)絡(luò)級(jí)優(yōu)化的目標(biāo)是使整個(gè)網(wǎng)絡(luò)的能耗與負(fù)載成比例,網(wǎng)絡(luò)級(jí)優(yōu)化主要是通過(guò)能量感知路由(Energy-Aware Routing, EAR)實(shí)現(xiàn),這個(gè)問(wèn)題已被歸結(jié)為容量約束的多商品流問(wèn)題(Capacitated Multi-commodity Net-work Flow, CMCF),而CMCF是NP完全的。設(shè)備級(jí)節(jié)能和網(wǎng)絡(luò)級(jí)節(jié)能并不是互斥的,實(shí)際上在真實(shí)情況,網(wǎng)絡(luò)級(jí)節(jié)能和設(shè)備級(jí)節(jié)能需要聯(lián)合使用才能達(dá)到最好的節(jié)能效果。CMCF問(wèn)題的基本思想是將所有網(wǎng)絡(luò)流量聚合到整個(gè)網(wǎng)絡(luò)拓?fù)涞囊粋�(gè)子集上,關(guān)閉或者休眠其他空閑的鏈路和節(jié)點(diǎn),從而使得網(wǎng)絡(luò)的整體的能耗與整體負(fù)載成比例,它的目標(biāo)是找到滿足需求的最小能耗子集。CMCF問(wèn)題目前已經(jīng)有了經(jīng)典的數(shù)學(xué)模型,本文在此基礎(chǔ)上將目的相同的需求進(jìn)行了聚合,將變量數(shù)目減少了一個(gè)數(shù)量級(jí),加快了求解速度。然而由于混合整數(shù)規(guī)劃(Mixed Integer Programing,, MIP)是NP-hard的,在拓?fù)湟?guī)模較大時(shí)計(jì)算時(shí)間變的不可接受,因此我們提出了一種基于克隆螞蟻的蟻群優(yōu)化路由算法(CACO-RA)。在算法中。我們將信息素按目的節(jié)點(diǎn)分類,最大限度的將流量聚合到較少的節(jié)點(diǎn)和鏈路；同時(shí)我們實(shí)現(xiàn)的是可分流的流量調(diào)度,充分利用了網(wǎng)絡(luò)帶寬。隨機(jī)網(wǎng)絡(luò)拓?fù)鋵?shí)驗(yàn)顯示我們的算法有著比其他算法更少的能量消耗、更快的計(jì)算速度和更好的實(shí)用性。在CACO-RA算法中,我們使用了分流的思想最小化能耗,效果確實(shí)很好,然而這帶來(lái)了另外一個(gè)問(wèn)題——延遲增大。傳統(tǒng)的基于最短路徑的算法,延遲無(wú)疑是最小的,且流量都是單路徑傳輸,不存在抖動(dòng)問(wèn)題。在CACO-RA算法中,我使用顯式路由為每個(gè)需求對(duì)分配多條路徑,這就帶了延遲和抖動(dòng)的問(wèn)題。為了在能耗和QoS之間取得一個(gè)良好的折中,我們結(jié)合粒子群優(yōu)化的思想修改了CACO-RA算法,我們將新算法命名為混合蟻群優(yōu)化(Hybrid Ant Colony Optimization, HACO)。在HACO中,我們將CACO-RA的輸出作為每個(gè)粒子的輸入,每個(gè)粒子的適應(yīng)度由QoS和負(fù)載均衡兩個(gè)因素決定,每次迭代后粒子間通過(guò)子圖合并來(lái)相互學(xué)習(xí),經(jīng)過(guò)多次迭代,最終我們會(huì)得到一個(gè)具有較低能耗、較小延遲、較優(yōu)負(fù)載的網(wǎng)絡(luò)子集。
[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.
【學(xué)位授予單位】：山東大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2016
【分類號(hào)】：TP18

【相似文獻(xiàn)】

相關(guān)期刊論文 前10條

1 許道云;;全息算法的原理及應(yīng)用[J];計(jì)算機(jī)科學(xué)與探索;2011年02期

2 段海濱,王道波,朱家強(qiáng),黃向華;蟻群算法理論及應(yīng)用研究的進(jìn)展[J];控制與決策;2004年12期

3 段海濱;王道波;于秀芬;;幾種新型仿生優(yōu)化算法的比較研究[J];計(jì)算機(jī)仿真;2007年03期

4 劉永廣;葉梧;馮穗力;;一種基于非線性長(zhǎng)度的多約束路由算法[J];計(jì)算機(jī)應(yīng)用研究;2008年11期

5 劉永廣;葉梧;馮穗力;;一種基于蟻群算法和非線性長(zhǎng)度的多約束路由算法[J];通信技術(shù);2009年08期

6 劉振;胡云安;;一種多粒度模式蟻群算法及其在路徑規(guī)劃中的應(yīng)用[J];中南大學(xué)學(xué)報(bào)(自然科學(xué)版);2013年09期

7 羅景峰;;智能算法求解效果評(píng)價(jià)的物元模型[J];微電子學(xué)與計(jì)算機(jī);2011年04期

8 劉芳,李陽(yáng)陽(yáng);量子克隆進(jìn)化算法[J];電子學(xué)報(bào);2003年S1期

9 周雅蘭;;細(xì)菌覓食優(yōu)化算法的研究與應(yīng)用[J];計(jì)算機(jī)工程與應(yīng)用;2010年20期

10 胡紅莉;張建州;;螺旋錐束CT重建的近似逆算法[J];計(jì)算機(jī)工程與應(yīng)用;2011年21期

相關(guān)會(huì)議論文 前1條

1 董家瑞;王精業(yè);潘麗君;;改進(jìn)的Dijksta算法在裝備保障系統(tǒng)中的應(yīng)用[A];圖像圖形技術(shù)與應(yīng)用進(jìn)展——第三屆圖像圖形技術(shù)與應(yīng)用學(xué)術(shù)會(huì)議論文集[C];2008年

相關(guān)博士學(xué)位論文 前9條

1 高衛(wèi)峰;人工蜂群算法及其應(yīng)用的研究[D];西安電子科技大學(xué);2013年

2 張捷;進(jìn)化算法及智能數(shù)據(jù)挖掘若干問(wèn)題研究[D];西安電子科技大學(xué);2013年

3 程世娟;改進(jìn)蟻群算法及其在結(jié)構(gòu)系統(tǒng)可靠性優(yōu)化中的應(yīng)用[D];西南交通大學(xué);2009年

4 楊振宇;基于自然計(jì)算的實(shí)值優(yōu)化算法與應(yīng)用研究[D];中國(guó)科學(xué)技術(shù)大學(xué);2010年

5 郭慶昌;均值移動(dòng)算法及在圖像處理和目標(biāo)跟蹤中的應(yīng)用研究[D];哈爾濱工程大學(xué);2008年

6 金勁;群集智能算法在網(wǎng)絡(luò)策略中的研究及其應(yīng)用[D];蘭州理工大學(xué);2011年

7 鄭樂(lè);寬頻帶雷達(dá)目標(biāo)跟蹤理論與算法研究[D];北京理工大學(xué);2015年

8 劉劍;非圓信號(hào)波達(dá)方向估計(jì)算法研究[D];國(guó)防科學(xué)技術(shù)大學(xué);2007年

9 張瑞秋;面向SMT的錐束CT圖像重構(gòu)關(guān)鍵理論與BGA焊點(diǎn)檢測(cè)算法[D];華南理工大學(xué);2014年

相關(guān)碩士學(xué)位論文 前10條

1 黃林;空間復(fù)用MIMO系統(tǒng)接收端的球形譯碼檢測(cè)算法研究[D];寧夏大學(xué);2015年

2 牛麗娟;基于Gossip算法的無(wú)線傳感器網(wǎng)絡(luò)分布式參數(shù)場(chǎng)估計(jì)[D];哈爾濱工業(yè)大學(xué);2015年

3 卓靜一;液晶相控陣波前相位校正算法研究[D];電子科技大學(xué);2014年

4 張瑩;視頻異常事件檢測(cè)算法研究[D];大連理工大學(xué);2015年

5 張博;基于多用戶MIMO系統(tǒng)的魯棒性信號(hào)檢測(cè)算法研究[D];大連理工大學(xué);2015年

6 陳望;基于混合算法的室內(nèi)WLAN定位研究[D];新疆大學(xué);2015年

7 陳宗文;霍夫森林框架下的多目標(biāo)檢測(cè)與跟蹤算法研究[D];東北大學(xué);2013年

8 張亞玲;衛(wèi)星導(dǎo)航抗干擾算法研究及系統(tǒng)設(shè)計(jì)[D];西安電子科技大學(xué);2014年

9 賈佳蔚;基于粒子濾波的檢測(cè)前跟蹤算法研究[D];電子科技大學(xué);2015年

10 劉洪彬;Hadoop下基于邊聚類的重疊社區(qū)發(fā)現(xiàn)算法研究[D];安徽工業(yè)大學(xué);2015年

，

本文編號(hào)：2496348