引入擁擠度概念的蜂群算法與網(wǎng)絡(luò)組播路由研究*

吳宗月，樊麗娟，王文國

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

引入擁擠度概念的蜂群算法與網(wǎng)絡(luò)組播路由研究*

吳宗月，樊麗娟，王文國

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

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

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

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

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

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

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

1 基本蜂群算法

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

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

(1)初始化蜜源信息。

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

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

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

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

③偵查蜂在解空間區(qū)域不斷搜索，試圖發(fā)現(xiàn)新的食物源；

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

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

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

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

(1)

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

(2)

適應(yīng)度的計算公式是：

(3)

其中fiti是第i個位置的適應(yīng)度。

觀察蜂的任務(wù)主要是根據(jù)采蜜蜂提供的食物源相關(guān)信息，以一定的概率選擇食物源。

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

(4)

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

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

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

2.1 蜂群算法的改進

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

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

圖1 一種假設(shè)的蜜源分布情況

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

(5)

觀察蜂選擇食物源的概率相應(yīng)修改為:

(6)

此外，原始人工蜂群算法初始化時蜜蜂的群體會被分為采蜜峰和觀察蜂，觀察蜂在蜂巢中被動等待采蜜峰帶回的蜜源信息。本文的另一項改進是假設(shè)蜂群中偵查蜂一直存在，一般使其比例保持在蜂群總數(shù)的5%～10%，這樣會迫使部分觀察蜂轉(zhuǎn)變?yōu)閭刹榉洌员憷^續(xù)保持對解空間的不斷搜索。

2.2QoS組播路由問題

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

對于源節(jié)點s, 目的節(jié)點d, 每個QoS參數(shù)須滿足以下約束：

(7)

(8)

(9)

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

(10)

(11)

確定QoS路由算法的理想路徑可以轉(zhuǎn)化為在源節(jié)點s和目的節(jié)點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為丟包率。

從源節(jié)點到目的節(jié)點得到的路徑記為kpath，其適應(yīng)度計算函數(shù)記為fitk，本文適應(yīng)值采用越小越優(yōu)的原則，fitk函數(shù)計算得到的不符合服務(wù)質(zhì)量各約束條件的解記為劣質(zhì)解，定義如下：

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

(12)

(13)

(14)

(15)

其中RD，RDJ，RPL均為懲罰系數(shù)且大于1，本文算法中取2。fitk越小，對應(yīng)解越優(yōu)。

算法流程如下：

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

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

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

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

(5)若蜜源在Limit次數(shù)內(nèi)沒有得到改善，則采蜜蜂變?yōu)閭刹榉湓诮饪臻g內(nèi)進行全局搜索，否則返回第三步。

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

3 仿真實驗與結(jié)果分析

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

圖2 網(wǎng)絡(luò)拓撲圖

仿真實驗網(wǎng)絡(luò)的相關(guān)參數(shù)選擇如表1所示。

表1 網(wǎng)絡(luò)相關(guān)參數(shù)

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

表2 基本蜂群算法實驗數(shù)據(jù)

表3 改進的蜂群算法實驗數(shù)據(jù)

4 結(jié)論

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

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

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

[3] 楊原.基于群智能優(yōu)化算法的QoS組播路由算法研究[D].西安:西安科技大學(xué),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

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

0 引言

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

2016-07-28)

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

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

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