劉祥樓　王東雪　趙冬巖等

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

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

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

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

1.1 節(jié)點休眠機理

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

1.2 人工魚群算法機理

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

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

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

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

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

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

2 實驗仿真

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

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

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

3 結(jié) 論

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

參考文獻：

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

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

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

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

[5] 王沛棟.改進蟻群算法及在路徑規(guī)劃問題中的應(yīng)用研究[D].青島：中國海洋大學(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].計算機測量與控制，2013，21（10）：2885-2887.

[8] 常歡，呂麗軍，劉鑫，等.混入逃逸函數(shù)的遺傳算法優(yōu)化超大視場光學(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.

（編輯：劉鐵英）