引入擁擠度概念的蜂群算法與網絡組播路由研究*

吳宗月，樊麗娟，王文國

(曲阜師范大學 信息科學與工程學院，山東 日照276826)

引入擁擠度概念的蜂群算法與網絡組播路由研究*

吳宗月，樊麗娟，王文國

(曲阜師范大學 信息科學與工程學院，山東 日照276826)

計算機網絡中的QoS組播路由選擇是一個NP完全問題，采用改進的人工蜂群算法對其進行優化。當采蜜蜂進行鄰域搜索時，引入擁擠度參數可以對其數量進行調控，避免過多的采蜜蜂在同一蜜源附近搜索；當擁擠度高時則增加偵查蜂的數量，從而有效提高算法的全局搜索能力。算法通過人工蜂群遍歷所有滿足時延、延遲抖動、帶寬、丟包率等約束條件下的可能路徑，進而選擇組播路由的最佳方案。對于靜態網絡拓撲的仿真實驗表明，上述改進算法的收斂性能明顯優于基本蜂群算法。

人工蜂群算法；QoS；擁擠度；組播路由

隨著人們對端到端通信以及點到多點通信需求的不斷增加，用戶對通信的QoS(QualityofService) 要求越來越高，因此網絡需要更好的QoS路由策略以滿足這一趨勢。這就要求網絡在同時考慮時延、延遲抖動、帶寬、丟包率等多個約束條件下解決最佳路由問題，而其本質是一個多目標優化問題，其解集滿足Pareto最優。

基于對昆蟲類社會性行為的研究，人們發現這些群體突出的特點是自組織及分布式運行，能夠有效應對外界不斷變化的環境。自然啟發式算法借鑒了生物系統的這些行為特點，這類算法包括遺傳算法、神經網絡算法、蟻群算法、粒子群算法、螢火蟲算法等[1-3]。群體智能是人工智能的一部分，主要研究個體在種群分散系統中的分工合作行為。例如人工蜂群可以通過相互協作求解復雜的組合優化問題[4]。

為了解決原始人工蜂群算法中執行效率低和收斂速度慢的缺點[5]，引入了擁擠度概念對其進行改進。當采蜜蜂進行鄰域搜索時，通過一個擁擠度參數對采蜜蜂進行數量調控，避免過多的采蜜蜂在同一蜜源附近搜索；當擁擠度較高時，適當增加偵查蜂的數量，從而有效提高算法的全局搜索能力，特別是加快算法后期的收斂。

本文把上述改進的蜂群算法應用于解決計算機網絡的QoS組播路由問題，且通過仿真實驗證實了其可行性和有效性。

1 基本蜂群算法

人工蜂群算法是由Karaboga在2005年提出的一種群體、智能算法，是模擬蜂群尋找更優食物源的仿生優化模型。該模型定義了三種蜜蜂：偵查蜂、采蜜蜂和觀察蜂，其工作模式為：采蜜蜂招募觀察蜂去食物源附近采蜜，當蜜源開采到一定程度就會放棄開采；偵查蜂負責發現新的食物源，其評估因素包含蜜源的豐富程度、開采的難易程度等多個方面；采蜜蜂存儲著有關當前蜜源的相關信息如食物源的距離、方向、豐富程度等，并在蜂巢分享給觀察蜂；觀察蜂在蜂巢中等待采蜜蜂分享蜜源信息，根據這些信息決定是否去開采食物源。

人工蜂群算法的主要流程如下：

(1)初始化蜜源信息。

(2)偵查蜂評估蜜源的優劣程度。

(3)重復以下四個步驟：

①采蜜峰確定食物源的位置并進行鄰域搜索存儲食物源信息；

②觀察蜂根據采蜜蜂提供的信息以一定的概率選擇食物源；

③偵查蜂在解空間區域不斷搜索，試圖發現新的食物源；

④保存到目前為止的最佳食物源信息。

(4)若滿足某種約束條件則終止算法。

這里假定蜜蜂的數量與食物源的數量相等，記為N。

在初始化階段，人工蜂群算法按照如下公式隨機生成N個解決方案：

(1)

采蜜蜂會計算每種解決方案的適應度，然后每個蜜蜂在當前位置按式(2)進行鄰域搜索產生新的解決方案：

(2)

適應度的計算公式是：

(3)

其中fiti是第i個位置的適應度。

觀察蜂的任務主要是根據采蜜蜂提供的食物源相關信息，以一定的概率選擇食物源。

食物源被選擇的概率如下：

(4)

對于觀察蜂來說，它們使用輪盤賭選擇法挑選食物源。觀察蜂選定食物源之后，開始并行執行任務。在其選定的蜜源附近進行鄰域搜索，如果食物源的適應度一直沒有提高，達到預先設定的循環次數Limit的食物源就會被放棄。放棄蜜源后的采蜜峰變成偵查蜂，開始在整個解空間中隨機搜索新的解決方案，搜索到蜜源之后偵查蜂又轉變成采蜜蜂執行任務。

最后，系統存儲到目前為止適應度最佳的蜜源，然后重復搜索過程直至終止條件滿足，比如到達預先設定的最大周期數，或者搜索結果偏差小于預先設定閾值等。

2 改進的蜂群算法與QoS組播路由選擇

2.1 蜂群算法的改進

在上述基本人工蜂群算法的搜索機制中，適應度高的食物源附近會有大量的采蜜峰進行鄰域搜索，而局部匯聚大量蜜蜂將導致其他區域的搜索能力下降，其結果會降低該算法的收斂速度和搜索效率。

如圖1所示，假設x1是采蜜蜂的當前位置，而算法在執行搜索過程中，一個新的蜜源可能會在x1的鄰域空間出現。如圖中的x2是一個局部的最優值，但是算法在執行的過程中會在x1附近不斷發現比x1優秀的解，從而吸引大量的采蜜蜂在臨近區域搜索，這樣算法會在局部最優位置的鄰域空間來回擺動，容易陷入局部收斂。采蜜蜂的大量聚集必然會影響到x3、x4等優秀蜜源的發現效率，導致算法運行后期的收斂速度相對較慢。為了避免這種不利情況出現，引入“擁擠度”這一概念來限制采蜜蜂的數量：當擁擠度低時，蜂群不需要進行任何的調整，當擁擠度高時，適當減少采蜜蜂的數量，同時增加偵查蜂的數量來擴大對解空間的全局搜索，這樣就能在一定程度上幫助算法避免早熟現象，同時在后期提高算法的收斂速度。

圖1 一種假設的蜜源分布情況

定義crowd為擁擠度參數，表示解空間中采蜜蜂與其鄰域空間中的其他個體之間的接近程度，crowd的值越大表示該區域內的采蜜蜂越少。

(5)

觀察蜂選擇食物源的概率相應修改為:

(6)

此外，原始人工蜂群算法初始化時蜜蜂的群體會被分為采蜜峰和觀察蜂，觀察蜂在蜂巢中被動等待采蜜峰帶回的蜜源信息。本文的另一項改進是假設蜂群中偵查蜂一直存在，一般使其比例保持在蜂群總數的5%～10%，這樣會迫使部分觀察蜂轉變為偵查蜂，以便繼續保持對解空間的不斷搜索。

2.2QoS組播路由問題

用賦權圖G=(V, E)來模擬網絡,其中V為圖中所有網絡節點組成的集合，E為網絡中鏈路的集合。s∈V為源節點，d∈{V-{s}}為目的節點。對網絡中的每個節點n∈V定義四種函數：代價函數Cost(n)，丟包率函數PL(n)，延時抖動函數Delay_Jitter(n)，時延函數Delay(n)。對每條鏈路e∈E也定義四種函數：代價函數Cost(e), 帶寬函數BandWidth(e), 延時抖動函數Delay_jitter(e), 時延函數Delay(e)。

對于源節點s, 目的節點d, 每個QoS參數須滿足以下約束：

(7)

(8)

(9)

BandWidth(p(s,d))=Min(BandWidth(e))

(10)

(11)

確定QoS路由算法的理想路徑可以轉化為在源節點s和目的節點d之間尋找一條滿足以下條件的路徑：

Delay(p(s,d))≤D

BandWidth(p(s,d))≥B

Delay_Jitter(p(s,d))≤DJ

PL(p(s,d))≤PL

Min(Cost(p(s,d)))

其中D為時延，B為帶寬，DJ為延時抖動，PL為丟包率。

從源節點到目的節點得到的路徑記為kpath，其適應度計算函數記為fitk，本文適應值采用越小越優的原則，fitk函數計算得到的不符合服務質量各約束條件的解記為劣質解，定義如下：

fitk=Cost(kpath)*ΦD(Delay(kpath)-D)*ΦDJ(Delay_Jitter(kpath)-D)*ΦPL(PL(kpath)-D)

(12)

(13)

(14)

(15)

其中RD，RDJ，RPL均為懲罰系數且大于1，本文算法中取2。fitk越小，對應解越優。

算法流程如下：

(1)初始化相關參數。設置蜂群數量N,最大搜索次數Limit,迭代次數iter, 最大迭代次數maxCycle,源節點s，目的節點d， 各邊約束參數(C,B,DJ,D), 各頂點約束參數(C,PL,DJ,D)的值。

(2)使用Dijkstra第K條最短路徑算法確定從源節點到目的節點的若干路徑，構建非劣解集。

(3)采蜜蜂根據公式(2)，在非劣解集中進行鄰域搜索，通過公式(10)計算適應度并根據貪婪策略保留更優的解。

(4)觀察蜂根據公式(3)隨機選擇蜜源開采。

(5)若蜜源在Limit次數內沒有得到改善，則采蜜蜂變為偵查蜂在解空間內進行全局搜索，否則返回第三步。

(6)算法執行至最大迭代次數或滿足誤差要求，輸出最優路徑并停止算法。

3 仿真實驗與結果分析

本文采用MATLAB平臺, 在Intel(R)PentiumE6500 2.93GHzCPU、2GB內存、Windows7 操作系統下進行了仿真實驗。應用Salam隨機生成算法生成網絡拓撲如圖2所示。

圖2 網絡拓撲圖

仿真實驗網絡的相關參數選擇如表1所示。

表1 網絡相關參數

基本蜂群算法與改進蜂群算法的實驗結果總結如表2和表3所示。實驗結果表明，改進的人工蜂群算法在執行效率和收斂速度上明顯優于基本型蜂群算法。

表2 基本蜂群算法實驗數據

表3 改進的蜂群算法實驗數據

4 結論

本文對基本人工蜂群算法引入了擁擠度概念加以改進。當采蜜蜂在進行鄰域搜索時，擁擠度參數可以對采蜜蜂進行數量限制，避免過多的采蜜蜂在同一蜜源附近搜索，擁擠度高時增加偵查蜂的數量，從而有效提高了全局搜索能力并且加快了算法后期的收斂速度。通過應用改進的蜂群算法對網絡QoS組播路由問題進行仿真實驗，結果證明其在靜態網絡中性能表現優異，但是在動態網絡實驗中尚表現不佳。下一步將著力于解決動態網絡優化問題。

[1]WangZheng,CROWCROFTJ.Quality-of-serviceforroutingsupportingmultimediaapplications[J].IEEEJournalofSelectedAreasinCommunications, 1996,14(7):1228-1234.

[2] 劉洋,王文國.差異化密集蟻群算法與網絡QoS路由選擇[J].通信技術,2015,48(8):949-953.

[3] 楊原.基于群智能優化算法的QoS組播路由算法研究[D].西安:西安科技大學,2014.

[4]KARABOGAD.Anideabasedonhoneybeeswarmfornumericaloptimization[R].TR06.KayseriErciyesUniversity, 2005.

[5]SAXENAS,SHARMAK,SHIWANIS,etal.Bestartificialbeecolonyusingstructuredswarm[C].Gurgaon:ProceedingsofIEEEInternationalAdvancedComputingConference,2014:1354-1360.

The research on the concept drifting based on three-way decision rough set

WuZongyue,FanLijuan,WangWenguo,

(DepartmentofInformationScience&Engineering,QufuNormalUniversity,Rizhao276826,China)

QoSmulticastroutingincomputernetworksisaNPcompleteproblem.Animprovedartificialbeecolony(ABC)algorithmwiththeconceptofcongestionwillbestudiedandusedtotackletheprobleminthispaper.Theproposedcongestionconceptisusedmainlyforemployedbees,andfunctionswhenmanyemployedbeessearchinginadjacentdomainstendtoaffecteachother;itwilladjustnumberofemployedbeesworkinginthesameareaandincreasethenumberofscouts,thereforeenhancesglobalsearchingabilityofthealgorithm.SimulationtestsonmulticastQoSroutingprocesswithstaticnetworktopologyshowthattheimprovedABCprocedureoutperformsthebasicalgorithminbothexecutionefficiencyandspeedofconvergence.

artificialbeecolonyalgorithm;QoS;Congestion;multicastrouting

TP

ADOI： 10.19358/j.issn.1674- 7720.2016.22.016

吳宗月，樊麗娟，王文國. 引入擁擠度概念的蜂群算法與網絡組播路由研究[J].微型機與應用，2016,35(22)：61-64.

0 引言

國家人事部高層次留學人員回國工作資助項目(200461)

2016-07-28)

吳宗月(1990-)，男，碩士研究生，主要研究方向:計算機網絡。

樊麗娟(1990-)，女，碩士研究生，主要研究方向:計算機網絡。

王文國(1960-)，男，博士，教授，主要研究方向:網絡與信息安全。