光網(wǎng)絡(luò)中基于人工魚群算法的節(jié)點(diǎn)休眠技術(shù)

劉祥樓　王東雪　趙冬巖等

摘要：鑒于人工魚群算法（AFSA）具有收斂速度快，易于尋址尋優(yōu)等特點(diǎn)，在光網(wǎng)絡(luò)節(jié)點(diǎn)休眠技術(shù)中引入人工魚群算法。以光路由域中的網(wǎng)關(guān)節(jié)點(diǎn)作為研究對(duì)象，選用業(yè)務(wù)量作為搜索函數(shù)，執(zhí)行算法中的各種尋址行為找到最優(yōu)解，休眠不符合條件的節(jié)點(diǎn)，并根據(jù)傳輸?shù)姆泵εc空閑狀態(tài)轉(zhuǎn)換限定值，從而節(jié)約傳輸過程中的能耗。通過2組7個(gè)節(jié)點(diǎn)進(jìn)行計(jì)算機(jī)仿真，并分別設(shè)定最大值的40%和50%為限定值，得到原始能耗與后期能耗的對(duì)比結(jié)果。由此可知，當(dāng)限定值為最大值的40%時(shí)，2組數(shù)據(jù)均節(jié)能14%，當(dāng)限定值為最大值50%時(shí)，能耗節(jié)約比例分別為28%和42%。證明該方法可有效節(jié)能。

關(guān)鍵詞：網(wǎng)關(guān)節(jié)點(diǎn)； 業(yè)務(wù)量； 人工魚群算法； 休眠

中圖分類號(hào)： TN 929.14 文獻(xiàn)標(biāo)志碼： A doi： 10.3969/j.issn.1005-5630.2015.01.005

Abstract：Because of many characteristics of artificial fish swarm algorithm （AFSA） such as easy implementation， rapid convergence， addressing and optimizing， we use AFSA in the optical network of the node hibernation technology for the first time in order to save the routing energy. We let the gateway node to be the research object， choose traffic load to be the search function， conduct the addressing behavior to find the best solution， and then make the node that do not match the solution hibernate so that energy saving can be achieved. This method can change the limitation between busy and free， which saves the energy with transmission ongoing. Simulation of two groups with seven nodes is carried out. We set 40% and 50% of the maximum as the limitation. To compare the energy with and without using the algorithm， we find that when the limitation is 40% of the maximum， the both groups save 14% energy， and when the limitation is 50% of the maximum， 28% and 41% energy is saved. It proves that the method can save energy efficiently.

Keywords：gateway node； traffic load； AFSA； hibernation

引 言

隨著網(wǎng)絡(luò)的發(fā)展，光網(wǎng)絡(luò)的應(yīng)用也越來越廣泛，隨之而來的能耗問題也日漸凸顯，由于能耗的大量浪費(fèi)導(dǎo)致的經(jīng)濟(jì)壓力也在日益增大。所以，近來國(guó)內(nèi)外已開始針對(duì)光網(wǎng)絡(luò)節(jié)能問題進(jìn)行研究[1]并初見成效，其中改進(jìn)路由協(xié)議[2]，改變網(wǎng)絡(luò)權(quán)值[3]，改善網(wǎng)絡(luò)節(jié)點(diǎn)覆蓋[4]，進(jìn)行網(wǎng)絡(luò)路徑規(guī)劃[5]等都是網(wǎng)絡(luò)節(jié)能的熱門方法。路由節(jié)能研究中的遺傳算法、蟻群算法[6]、粒子群算法[7]等都是本領(lǐng)域的經(jīng)典算法且應(yīng)用領(lǐng)域日益廣泛[8]。蟻群算法雖然運(yùn)行簡(jiǎn)單，但是算法求解過程開銷過大；遺傳算法雖然能準(zhǔn)確解決問題，但是編程復(fù)雜，其解碼過程相對(duì)耗時(shí)費(fèi)力；粒子群算法雖然求解簡(jiǎn)單且運(yùn)算快但容易陷入局部最優(yōu)解。蟻群算法和遺傳算法的研究已經(jīng)進(jìn)入瓶頸階段，突破性不大。鑒于人工魚群算法在電力系統(tǒng)及運(yùn)輸系統(tǒng)優(yōu)化中體現(xiàn)出運(yùn)行簡(jiǎn)單、快速、準(zhǔn)確等優(yōu)點(diǎn)，本文將它獨(dú)特的尋址尋優(yōu)特性運(yùn)用在節(jié)點(diǎn)休眠技術(shù)中，目的是改善網(wǎng)絡(luò)節(jié)點(diǎn)的業(yè)務(wù)量負(fù)載，在網(wǎng)絡(luò)工作狀態(tài)下快速且準(zhǔn)確地找到空閑的節(jié)點(diǎn)進(jìn)行休眠，從而省去該節(jié)點(diǎn)的能耗，繼而達(dá)到網(wǎng)絡(luò)節(jié)能的效果。

1 光網(wǎng)絡(luò)節(jié)能技術(shù)機(jī)理

1.1 節(jié)點(diǎn)休眠機(jī)理

網(wǎng)絡(luò)節(jié)點(diǎn)處于休眠狀態(tài)時(shí)保留正常工作時(shí)的數(shù)據(jù)，只是關(guān)閉了其中的顯示設(shè)備和耗電的程序，從而達(dá)到節(jié)能效果。當(dāng)網(wǎng)絡(luò)節(jié)點(diǎn)需要工作而重新啟動(dòng)時(shí)，能快速進(jìn)入工作狀態(tài)，這是一種介于開啟與關(guān)閉的中間狀態(tài)。在網(wǎng)絡(luò)中引入休眠狀態(tài)，可以有以下四種方法：一是在網(wǎng)絡(luò)設(shè)備中設(shè)置兩種狀態(tài)，復(fù)蘇狀態(tài)和休眠狀態(tài)。設(shè)備在閑置時(shí)進(jìn)入休眠狀態(tài)，從而降低能耗。二是在網(wǎng)絡(luò)層面，當(dāng)網(wǎng)內(nèi)業(yè)務(wù)負(fù)載較低時(shí)，使業(yè)務(wù)路由匯聚在少數(shù)的設(shè)備上，從而降低能耗。三是在網(wǎng)絡(luò)協(xié)議層面，對(duì)因特網(wǎng)協(xié)議進(jìn)行適當(dāng)?shù)男薷?，在業(yè)務(wù)量大的時(shí)候調(diào)用設(shè)備，在業(yè)務(wù)量相應(yīng)少的時(shí)候使設(shè)備進(jìn)行休眠，從而減少能耗。四是在網(wǎng)絡(luò)路由層面，當(dāng)傳輸數(shù)據(jù)量變少時(shí)，休眠承載業(yè)務(wù)量少的節(jié)點(diǎn)，從而達(dá)到節(jié)能效果，而本文采用的是此種方法。

1.2 人工魚群算法機(jī)理

在一片水域中，魚往往能自行或尾隨其他魚，找到營(yíng)養(yǎng)物質(zhì)多的地方，因而魚生存數(shù)目最多的地方一般就是本水域中營(yíng)養(yǎng)物質(zhì)最多的地方。人工魚群算法就是根據(jù)這一特點(diǎn)，通過構(gòu)造人工魚來模仿魚群的覓食、聚群、追尾及隨機(jī)行為，從而實(shí)現(xiàn)尋優(yōu)。人工魚覓食的路線如圖1所示，圖中X為一條人工魚的位置，它的視野范圍為V（V為圖1大圓以內(nèi)區(qū)域），Xa、Xb表示為視野范圍內(nèi)兩條魚的位置，位置Xv為X在某時(shí)刻視點(diǎn)所在的位置，如果該位置的食物濃度高于當(dāng)前位置則考慮向前進(jìn)一步，即為Xnext；若食物的濃度不及當(dāng)前位置，則繼續(xù)巡視視野內(nèi)其他位置。巡視的次數(shù)越多，則對(duì)視野內(nèi)的狀態(tài)越了解，則對(duì)周圍的環(huán)境有個(gè)立體的認(rèn)知，有助于做出相應(yīng)的判斷與決策。而對(duì)于狀態(tài)多或無限狀態(tài)的環(huán)境，也不必全部遍歷，允許一定的不確定性對(duì)于擺脫局部最優(yōu)尋找全局最優(yōu)是有幫助的。在圖1中，位置X=（x1，x2，…，xn），位置Xv=（xv1，xv2，…，xvn），則該過程表示如下：

式中，r是[-1，1]區(qū)間的隨機(jī)數(shù)，S為移動(dòng)步長(zhǎng)。由于環(huán)境中同伴的數(shù)目是有限的，因此在視野中感知同伴的位置，并相應(yīng)地調(diào)整自身位置的方法與上式相似。假設(shè)在一個(gè)n維的目標(biāo)搜索空間中，有N條組成一個(gè)群體的人工魚，人工魚個(gè)體的狀態(tài)可表示為向量X=（x1，x2，…，xn），其中xi（i=1，2，…，n）為欲尋優(yōu)的變量；人工魚當(dāng)前所在位置的食物濃度表示為Y=f（X），其中Y為目標(biāo)函數(shù)；S為人工魚移動(dòng)步長(zhǎng)。

魚群行為可描述為四種：一是隨機(jī)行為，即魚在水中游動(dòng)基本上是隨機(jī)的，當(dāng)發(fā)現(xiàn)食物時(shí)，會(huì)向食物逐漸增多的方向快速移動(dòng)。二是覓食行為，即生物的一種最基本的行為，魚趨向食物的一種活動(dòng)，人工魚Xi在其視野內(nèi)隨機(jī)選擇一個(gè)狀態(tài)Xj，分別計(jì)算它們的目標(biāo)函數(shù)值進(jìn)行比較，如果發(fā)現(xiàn)Yj大于Yi，則Xi向Xj的方向移動(dòng)；否則，Xi繼續(xù)在其視野內(nèi)選擇狀態(tài)Xj，判斷是否滿足前進(jìn)條件，反復(fù)嘗試T次后，仍沒有滿足前進(jìn)條件，則隨機(jī)移動(dòng)一步使Xi到達(dá)一個(gè)新的狀態(tài)。三是聚群行為，即一種魚類常見的現(xiàn)象，這是它們?cè)谶M(jìn)化過程中形成的生存模式，為了集體覓食和躲避敵害。四是追尾行為，即當(dāng)魚群中的一條魚或幾條魚發(fā)現(xiàn)食物時(shí)，它們附近的魚會(huì)尾隨其后迅速游過去，進(jìn)而導(dǎo)致更遠(yuǎn)的魚也尾隨過來。以上是魚的四種典型行為，這些行為在不同時(shí)刻會(huì)相互轉(zhuǎn)換，而轉(zhuǎn)換一般是魚通過對(duì)周圍環(huán)境的認(rèn)知來實(shí)現(xiàn)的。在解決優(yōu)化問題時(shí)，可以選擇最優(yōu)的行為執(zhí)行，也就是在當(dāng)前狀態(tài)下，哪種行為會(huì)達(dá)到最優(yōu)的狀態(tài)；也可以選擇較優(yōu)的行為，就是任選一種狀態(tài)，只要朝向最優(yōu)的狀態(tài)即可。兩種選擇最后都會(huì)尋找到最優(yōu)的結(jié)果。

1.3 網(wǎng)絡(luò)節(jié)能機(jī)理

雖然人工魚群算法可應(yīng)用在網(wǎng)絡(luò)傳輸中，但目前還沒有節(jié)能上的應(yīng)用，結(jié)合該算法尋址尋優(yōu)的特性，在此選用這種算法進(jìn)行光網(wǎng)節(jié)能。在光網(wǎng)絡(luò)層面，業(yè)務(wù)量能直接顯示出節(jié)點(diǎn)的利用率[9]，承載高業(yè)務(wù)量的節(jié)點(diǎn)在傳輸過程中起著較大的作用，而同一時(shí)段某些節(jié)點(diǎn)則承載著較少的業(yè)務(wù)量，且能根據(jù)時(shí)間段進(jìn)行多次監(jiān)測(cè)。在不同的時(shí)間段內(nèi)，節(jié)點(diǎn)承載的業(yè)務(wù)量不同，則擬定業(yè)務(wù)量為搜索函數(shù)，選擇業(yè)務(wù)量少的節(jié)點(diǎn)作為休眠的對(duì)象，能直接解決路由傳輸過程中的能耗問題，針對(duì)性強(qiáng)且具有靈活性。

根據(jù)研究，節(jié)點(diǎn)分為網(wǎng)關(guān)節(jié)點(diǎn)和域內(nèi)節(jié)點(diǎn)。光路由域中網(wǎng)關(guān)節(jié)點(diǎn)和域內(nèi)節(jié)點(diǎn)的分布如圖2所示，網(wǎng)關(guān)節(jié)點(diǎn)的能耗遠(yuǎn)大于域內(nèi)節(jié)點(diǎn)的能耗值，則在人工魚群算法中只對(duì)網(wǎng)關(guān)節(jié)點(diǎn)進(jìn)行計(jì)算。所以設(shè)定每個(gè)網(wǎng)關(guān)節(jié)點(diǎn)為一個(gè)個(gè)體，而每個(gè)包括節(jié)點(diǎn)的路由域?yàn)榉N群，此種算法就是針對(duì)種群中的個(gè)體進(jìn)行篩選。人工魚群算法的流程如圖3所示，初始化魚群時(shí)，需要確定算法中需要的參數(shù)，種群規(guī)模N，即在變量可行域內(nèi)隨機(jī)生成N個(gè)個(gè)體，設(shè)定人工魚的可視域V，步長(zhǎng)S，擁擠度因子δ，嘗試次數(shù)T，且在給定的范圍內(nèi)隨機(jī)產(chǎn)生數(shù)組代表人工魚。本算法是要得到大于限定值的個(gè)體，則當(dāng)魚群得到新個(gè)體時(shí)，與限定值進(jìn)行對(duì)比，若符合條件，則向著該個(gè)體前進(jìn)，直至出現(xiàn)最優(yōu)解，否則進(jìn)行下一次尋找。最后當(dāng)最優(yōu)解達(dá)到滿意度，算法結(jié)束。若想得到最優(yōu)解的集合，則在執(zhí)行算法后，可將最優(yōu)解剔除，重新進(jìn)行運(yùn)算，再次得到最優(yōu)解，多次執(zhí)行后可得最優(yōu)解集合。

2 實(shí)驗(yàn)仿真

人工魚群算法是根據(jù)業(yè)務(wù)量的大小來決定休眠的節(jié)點(diǎn)，所以節(jié)點(diǎn)的業(yè)務(wù)量是重點(diǎn)。本文引用文獻(xiàn)[10]中的數(shù)據(jù)，在其網(wǎng)絡(luò)節(jié)點(diǎn)拓?fù)浣Y(jié)果中取出2組數(shù)據(jù)進(jìn)行仿真實(shí)驗(yàn)，每組數(shù)據(jù)各選取連續(xù)的7個(gè)節(jié)點(diǎn)，并對(duì)此數(shù)據(jù)進(jìn)行業(yè)務(wù)量概率轉(zhuǎn)換，具體數(shù)據(jù)參見表1和表2。表1為本次實(shí)驗(yàn)選取的2組實(shí)驗(yàn)數(shù)據(jù)，表2為進(jìn)行業(yè)務(wù)量概率轉(zhuǎn)換后的數(shù)據(jù)。從中可以看出在進(jìn)行路由傳輸時(shí)，節(jié)點(diǎn)所帶的業(yè)務(wù)量是不同的，而本文則利用這種不同選擇了此種休眠技術(shù)。

本次實(shí)驗(yàn)進(jìn)行了2次限定值的選取，當(dāng)選取限定值為最大值的40%時(shí)，2組數(shù)據(jù)均有1個(gè)節(jié)點(diǎn)不符合限定值要求，則分別休眠該節(jié)點(diǎn)，參見圖4（a）。由此可得到休眠后的能耗與原始能耗對(duì)比如圖5（a）所示，從圖中看出，進(jìn)行休眠技術(shù)后的路由能耗少于原始能耗，比例均在14%左右。因?yàn)檫x的限定值不同則休眠節(jié)點(diǎn)的個(gè)數(shù)不同，此限定值可選擇在傳輸較為繁忙的時(shí)候，大部分的節(jié)點(diǎn)進(jìn)行工作，只有少數(shù)的節(jié)點(diǎn)休眠，不僅不影響傳輸速率也能節(jié)約傳輸過程中的能耗。圖4（b）所示為限定條件定為最大值的50%，從圖中可看出，在此限定條件下，數(shù)據(jù)1有2個(gè)節(jié)點(diǎn)不符合條件，而數(shù)據(jù)2則有3個(gè)節(jié)點(diǎn)，當(dāng)對(duì)這些節(jié)點(diǎn)進(jìn)行休眠處理后，得到的能耗對(duì)比如圖5（b）所示。從圖中可看出，數(shù)據(jù)1和數(shù)據(jù)2的能耗大幅度下降，數(shù)據(jù)1的能

耗相對(duì)于原始能耗下降28%左右，而數(shù)據(jù)2則下降42%左右。此限定值可選在傳輸較為空閑時(shí)，即使休眠的節(jié)點(diǎn)增多，但是總傳輸量少，所以也不會(huì)影響傳輸速率仍可保持傳輸流通暢。對(duì)比圖4（a）、（b）可看出當(dāng)限定值改變時(shí)選定的休眠節(jié)點(diǎn)個(gè)數(shù)不同，圖5（a）、（b）顯示出節(jié)約能耗的比例也大有不同，相較于之前的限定值，第二次實(shí)驗(yàn)的效果更突出，節(jié)能效果更為明顯。由此可知，此種方法可達(dá)到預(yù)期節(jié)能效果，且根據(jù)需要可進(jìn)行算法中參數(shù)的改變，具有靈活性。

3 結(jié) 論

人工魚群算法是源于魚的生物特性而研發(fā)出來的，具有可靠性。該方法相對(duì)原始的迭代方法而言，簡(jiǎn)單易行且可達(dá)到路由節(jié)能效果。本文實(shí)驗(yàn)選擇節(jié)點(diǎn)較少，得到的效果相對(duì)明顯。當(dāng)該項(xiàng)技術(shù)應(yīng)用到整個(gè)光網(wǎng)絡(luò)中，由于節(jié)點(diǎn)數(shù)量大增，預(yù)期休眠效果或許不會(huì)如此凸顯，但一定能夠?qū)崿F(xiàn)相對(duì)應(yīng)的節(jié)能效果。實(shí)驗(yàn)表明：選取不同的限定值，節(jié)約的能耗會(huì)有所不同，在實(shí)際應(yīng)用過程中，保證傳輸速率的前提下，可通過改變限定值，保證最大限度的節(jié)約能耗。在網(wǎng)絡(luò)應(yīng)用日益廣泛的今天，本文提出的節(jié)能算法對(duì)光網(wǎng)節(jié)能有一定的參考價(jià)值。

參考文獻(xiàn)：

[1] 秦建兵，王坤，周駿華.EPON網(wǎng)絡(luò)中OAM子層的擴(kuò)展[J].光學(xué)儀器，2005，27（5）：43-46.

[2] 任秀麗，梁宏偉，汪宇.基于多路徑蟻群算法的無線傳感器網(wǎng)絡(luò)的路由[J].計(jì)算機(jī)科學(xué)，2009，36（4）：116-118.

[3] 姚明海.改進(jìn)的遺傳算法在優(yōu)化BP網(wǎng)絡(luò)權(quán)值中的應(yīng)用[J].計(jì)算機(jī)工程與應(yīng)用，2013，49（24）：49-54.

[4] 彭麗英.改進(jìn)的蟻群算法網(wǎng)絡(luò)節(jié)點(diǎn)覆蓋優(yōu)化研究[J].計(jì)算機(jī)仿真，2011，28（9）：251-255.

[5] 王沛棟.改進(jìn)蟻群算法及在路徑規(guī)劃問題中的應(yīng)用研究[D].青島：中國(guó)海洋大學(xué)，2012：14-90.

[6] SHI L，YANG S P.Research and application of an improved ant colony algorithm[J].Applied Mechanics and Materials，2014，543：1864-1867.

[7] 譚德坤，王冠.基于反向?qū)W習(xí)粒子群算法的無線傳感器網(wǎng)絡(luò)路由優(yōu)化[J].計(jì)算機(jī)測(cè)量與控制，2013，21（10）：2885-2887.

[8] 常歡，呂麗軍，劉鑫，等.混入逃逸函數(shù)的遺傳算法優(yōu)化超大視場(chǎng)光學(xué)系統(tǒng)[J].光學(xué)儀器，2013，35（4）：27-33.

[9] 張力方.基于GMPLS的多層多域智能光網(wǎng)絡(luò)若干關(guān)鍵技術(shù)研究[D].北京：北京郵電大學(xué)，2012：46-55.

[10] 任鵬.WDM光網(wǎng)絡(luò)業(yè)務(wù)量疏導(dǎo)的魯棒規(guī)劃算法研究[D].成都：電子科技大學(xué)，2007：19-30.

（編輯：劉鐵英）