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

吳宗月，樊麗娟，王文國(guó)

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

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

吳宗月，樊麗娟，王文國(guó)

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

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

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

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

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

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

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

1 基本蜂群算法

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

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

(1)初始化蜜源信息。

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

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

①采蜜峰確定食物源的位置并進(jìn)行鄰域搜索存儲(chǔ)食物源信息；

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

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

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

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

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

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

(1)

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

(2)

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

(3)

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

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

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

(4)

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

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

2 改進(jìn)的蜂群算法與QoS組播路由選擇

2.1 蜂群算法的改進(jìn)

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

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

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

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

(5)

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

(6)

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

2.2QoS組播路由問(wèn)題

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

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

(7)

(8)

(9)

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

(10)

(11)

確定QoS路由算法的理想路徑可以轉(zhuǎn)化為在源節(jié)點(diǎn)s和目的節(jié)點(diǎn)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為時(shí)延，B為帶寬，DJ為延時(shí)抖動(dòng)，PL為丟包率。

從源節(jié)點(diǎn)到目的節(jié)點(diǎn)得到的路徑記為kpath，其適應(yīng)度計(jì)算函數(shù)記為fitk，本文適應(yīng)值采用越小越優(yōu)的原則，fitk函數(shù)計(jì)算得到的不符合服務(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越小，對(duì)應(yīng)解越優(yōu)。

算法流程如下：

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

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

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

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

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

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

3 仿真實(shí)驗(yàn)與結(jié)果分析

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

圖2 網(wǎng)絡(luò)拓?fù)鋱D

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

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

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

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

表3 改進(jìn)的蜂群算法實(shí)驗(yàn)數(shù)據(jù)

4 結(jié)論

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

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

[2] 劉洋,王文國(guó).差異化密集蟻群算法與網(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

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

0 引言

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

2016-07-28)

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

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

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