基于差分-精英蟻群的QoS組播路由優(yōu)化算法

陳 樹，許 博，徐保國

（江南大學(xué)物聯(lián)網(wǎng)工程學(xué)院，江蘇 無錫 214122）

基于差分-精英蟻群的QoS組播路由優(yōu)化算法

陳 樹，許 博，徐保國

（江南大學(xué)物聯(lián)網(wǎng)工程學(xué)院，江蘇 無錫 214122）

無線傳感器網(wǎng)絡(luò)通信鏈路在特定服務(wù)質(zhì)量（QoS）下存在帶寬和節(jié)點(diǎn)能量分配不均、延時(shí)較長，且對(duì)服務(wù)類型適應(yīng)能力差等問題。為此，提出一種差分-精英蟻群算法。該算法通過差分進(jìn)化算法對(duì)蟻群優(yōu)化算法中的參數(shù)組合進(jìn)行尋優(yōu)，獲得最優(yōu)參數(shù)組合，并吸收了精英保存策略、蟻群排序的優(yōu)點(diǎn)，增加算法收斂速度，利用QoS路由服務(wù)類型的特點(diǎn)設(shè)置目標(biāo)函數(shù)。仿真結(jié)果表明，與基本蟻群算法相比，該算法能以較小的迭代次數(shù)收斂到最優(yōu)解，獲得系統(tǒng)最小熵。

蟻群算法；差分進(jìn)化算法；精英保存；服務(wù)質(zhì)量；熵

1 概述

無線傳感器網(wǎng)絡(luò)（Wireless Sensor Network，WSN）對(duì)性能要求不斷提高，網(wǎng)絡(luò)服務(wù)質(zhì)量成為設(shè)計(jì)者必須考慮的重要因素，實(shí)質(zhì)主要是從源端到目的端選擇一條滿足用戶服務(wù)質(zhì)量要求的最優(yōu)路徑。其本質(zhì)為含多參、非線性約束的路徑尋優(yōu)算法問題。

目前，路徑尋優(yōu)研究方面，2013年，李擎等人［1］提出基于粒子群算法改進(jìn)人工蟻群，優(yōu)化蟻群算法的基本參數(shù)，在樣本較多條件下大大減少了算法的時(shí)間成本。文獻(xiàn)［2］提出基于差分進(jìn)化優(yōu)化服務(wù)質(zhì)量（Quality of Service，QoS）組播路由，相比較遺傳算法擁有更短的收斂時(shí)間。文獻(xiàn)［3］提出在混合差分進(jìn)化法中使用蟻群算法進(jìn)行選擇適當(dāng)?shù)耐蛔冞\(yùn)算，加速搜尋全局解。文獻(xiàn)［4］將蟻群迭代中較好的螞蟻通過正反饋來增加信息素濃度，來提高收斂速度，但同時(shí)也會(huì)增加陷入局部最優(yōu)解的可能。文獻(xiàn)［5］將遺傳算法中排序概念擴(kuò)展到精英機(jī)制當(dāng)中，建立了改進(jìn)蟻群算法模型，但是其蟻群參數(shù)仍依賴人工經(jīng)驗(yàn)選取，限制了算法的泛化能力。

為此，本文在蟻群算法基礎(chǔ)上，利用差分進(jìn)化

算法對(duì)蟻群參數(shù)向量進(jìn)行變異、交叉操作，獲得蟻群最優(yōu)參數(shù)解，在差分-蟻群基礎(chǔ)上，優(yōu)化信息素濃度更新方式，改良精英螞蟻的獎(jiǎng)懲機(jī)制以及排序策略，將不同QoS服務(wù)類型統(tǒng)一到系統(tǒng)熵模型當(dāng)中，提出具有系統(tǒng)熵意識(shí)的差分-精英螞蟻算法。

2 差分-精英蟻群算法

為了克服蟻群參數(shù)過于依賴人工經(jīng)驗(yàn)缺陷，本文提出將差分進(jìn)化算法引入蟻群系統(tǒng)，形成差分-蟻群，對(duì)由原始蟻群參數(shù)構(gòu)成個(gè)體（α，β，ρ）進(jìn)行優(yōu)化選擇，最終獲得不同 WSN環(huán)境下的最優(yōu)參數(shù)組合。

在差分-蟻群的基礎(chǔ)上，本文對(duì)蟻群自身性能進(jìn)行優(yōu)化，主要表現(xiàn)為：（1）為獲得快速收斂性，借鑒遺傳算法中精英保存策略，將每次迭代時(shí)信息素按照一定準(zhǔn)則排序，優(yōu)先級(jí)較高的螞蟻才可獲得更多的信息素濃度，擁有最高信息素的螞蟻成為本次迭代的精英螞蟻；（2）排序策略中采用黃金分割優(yōu)選法，并用自然對(duì)數(shù)的權(quán)系數(shù)遞增方式平滑遞增信息素；（3）將不同服務(wù)類型統(tǒng)一到系統(tǒng)熵（entropy）效用函數(shù)中，對(duì)任意服務(wù)類型在兼顧系統(tǒng)多決策變量指標(biāo)要求下尋找系統(tǒng)最小熵。仿真結(jié)果表明，將提出的差分-精英螞蟻系統(tǒng)應(yīng)用于無線傳感網(wǎng)QoS組播路徑尋優(yōu)當(dāng)中，可以快速獲取信息素濃度表征因子、帶寬啟發(fā)因子、延時(shí)啟發(fā)因子最優(yōu)矢量組合。在兼顧節(jié)點(diǎn)能耗、延時(shí)、帶寬需求等關(guān)鍵信息量指標(biāo)條件下，選擇合適的熵權(quán)值系數(shù)，對(duì) QoS服務(wù)類型使得WSN獲得最小系統(tǒng)熵。

3 差分-蟻群算法實(shí)現(xiàn)

3.1 蟻群參數(shù)優(yōu)化

差分進(jìn)化算法基于優(yōu)勝劣汰原則，是在連續(xù)空間隨機(jī)搜索尋找最優(yōu)解的智能優(yōu)化算法，基本步驟包括變異、交叉和選擇3種操作［6］。

3.1.1 優(yōu)化步驟

差分進(jìn)化算法優(yōu)化蟻群參數(shù)步驟如下表示：

Step1 設(shè)置DE種群規(guī)模N、縮放因子F、交叉因子CR、最大迭代次數(shù)gmax。初始化種群：

其中，P0（X）表示第0代種群；表示第0代種群的第i個(gè)個(gè)體；gmax表示最大進(jìn)化代數(shù)。

Step2 讀取ACO適應(yīng)度函數(shù)，進(jìn)行個(gè)體評(píng)價(jià)并求最優(yōu)解。

Step3 若達(dá)到終止條件（迭代次數(shù)到gmax，或者連續(xù)2個(gè)適應(yīng)度函數(shù)值小于臨界值）則算法終止，輸出結(jié)果；否則轉(zhuǎn)Step4。

Step4 根據(jù)下面的式（1）變異操作、式（2）交叉操作得到實(shí)驗(yàn)種群：

Step5 根據(jù)式（3）選擇下一代的進(jìn)化種群：

Step6 迭代計(jì)數(shù)器累加1，轉(zhuǎn)到Step2。

3.1.2 優(yōu)化效果

為了更好說明采用DE算法優(yōu)化蟻群參數(shù)的優(yōu)越性，讀取文獻(xiàn)［7］中國31個(gè)城市坐標(biāo)數(shù)據(jù)，作為無線傳感網(wǎng)拓?fù)浣Y(jié)構(gòu)的節(jié)點(diǎn)坐標(biāo)，將本文提出的差分-精英蟻群優(yōu)化（Difference-elite Ant Colony Optimization，DEACO）算法分別與基本蟻群優(yōu)化算法［8］、基于遺傳算法的蟻群求解算法［7］作對(duì)比。本文DE參數(shù)設(shè)置：種群規(guī)模N=20，縮放因子F=0.7，交叉因子CR= 0.8，最大迭代次數(shù)gmax=50。ACO參數(shù)設(shè)置：螞蟻數(shù)m=13，常量Q=100，城市數(shù)量（節(jié)點(diǎn)個(gè)數(shù)）n=31，最大周游次數(shù) Nc-max=200。實(shí)驗(yàn)環(huán)境為：內(nèi)存2.0 GB，硬盤250 GB，Intel（R）Core（TM）2 Duo CPU，運(yùn)行操作系統(tǒng)為Window s 7，使用Matlab2010編程。實(shí)驗(yàn)結(jié)果如表1所示。

表1 3種算法實(shí)驗(yàn)結(jié)果對(duì)比

從表1可以看出，DEACO算法經(jīng)過23次進(jìn)化迭代后，找到最優(yōu)解，（α，β，ρ）=（1.185 2，6.391 5，0.750 1），最優(yōu)路徑長度13 092 km，比基本ACO算法路徑長度少7 049 km，比文獻(xiàn)［7］少3 356 km。實(shí)驗(yàn)結(jié)果表明，本文提出的DEACO算法大大降低了周游節(jié)點(diǎn)的長度，從而可以極大地減少網(wǎng)絡(luò)延時(shí)與能耗，降低了網(wǎng)絡(luò)成本。

為了更直觀體現(xiàn)DEACO算法最優(yōu)路徑的情形，將采用最優(yōu)（α，β，ρ）組合后得到的DEACO路徑以及路徑長度的收斂狀況如圖1所示。

圖1 DEACO路徑以及收斂狀況

在說明了DEACO在蟻群參數(shù)自適應(yīng)優(yōu)化方面的優(yōu)越性后，繼續(xù)對(duì)算法進(jìn)行優(yōu)化，并在DEACO基礎(chǔ)上得到了差分-精英系統(tǒng)。

3.2 精英保存策略

為保證系統(tǒng)能夠最快收斂到全局最優(yōu)解，吸收遺傳算法中精英保存策略思想，當(dāng)某路徑信息素濃度大于信息素閾值時(shí)，信息素按照一定比率增加［9］。選擇精英螞蟻算法如下：

Step1 產(chǎn)生信息素閾值τon（θ），θ表示為第θ次迭代。τon（θ）=μ（τi，j（θ-1）），μ（·）為常系數(shù)連續(xù)函數(shù)。

Step2 將｛τi，j（θ）|（0＜i＜m，0＜j＜n）｝依次與信息素閾值 τon（θ）作比較，并找出滿足條件的信息素集

Step4 邊界判定：

本文提出的差分-精英蟻群系統(tǒng)將每只螞蟻爬行距離按大小排序，按排名位次進(jìn)行加權(quán)來釋放信息素［10］。 更新規(guī)則策略如下：

同時(shí)對(duì)每輪周游后得到全局最優(yōu)解的螞蟻給予額外的信息素補(bǔ)償：

其中，kr（0＜kr＜μ）為螞蟻排名；κ為算法選取的螞蟻數(shù)；L*是找到最優(yōu)解長度。在一定范圍內(nèi)，精英螞蟻數(shù)量與算法發(fā)現(xiàn)全局解具有正相關(guān)性。在超過一定范圍后，由于搜索會(huì)過于快速地集中在極優(yōu)解周圍而導(dǎo)致整個(gè)系統(tǒng)早熟收斂。本文黃金分割取整κ：κ=ceil（0.618×m）。同時(shí)，不同于文獻(xiàn)［11］信息素遞增系數(shù)采用常比例（線性）的方式，本文根據(jù)式（5）按照自然對(duì)數(shù)的權(quán)系數(shù)遞增，這種平緩的對(duì)數(shù)遞增速率可以避免線性或指數(shù)性增長導(dǎo)致信息素陡增而陷入局部解。

4 螞蟻的QoS熵意識(shí)

針對(duì)QoS 3種服務(wù)類型切換時(shí)調(diào)整參數(shù)存在較多的重復(fù)性工作問題，將3種服務(wù)類型統(tǒng)一到系統(tǒng)熵的效用函數(shù)上來。

依據(jù)QoS不同的服務(wù)，即音視頻流服務(wù)（高帶寬、耗能低、低延時(shí)），異常報(bào)警服務(wù)（低延時(shí)、耗能無要求），普通信息服務(wù)（帶寬、耗能及時(shí)延要求都不高），將組播樹帶寬消耗w1（帶寬指標(biāo)）、節(jié)點(diǎn)剩余能量的均方差w2（耗能指標(biāo)）、每輪迭代的延時(shí)w3（延時(shí)指標(biāo)）作為信息量，根據(jù)不同的服務(wù)類型，為3個(gè)信息量設(shè)置不同的權(quán)系數(shù)，由此構(gòu)建描述組播樹穩(wěn)定性好壞的表達(dá)式S，并稱之為組播樹的衍生熵。需

特別指出的是，w1，w2，w33個(gè)指標(biāo)屬于不同量綱，其數(shù)據(jù)歸一化采用Z-score標(biāo)準(zhǔn)化算法，即：

其中，μ為均值；σ為標(biāo)準(zhǔn)差。

最終得到S表達(dá)式為：

其中，ki（i=1，2，3）為熵權(quán)值系數(shù)；表示w1，w2，w3的歸一化數(shù)據(jù)。

針對(duì)不同的QoS服務(wù)類型，只需要修改相應(yīng)權(quán)系數(shù)即可，在WSN不同的網(wǎng)絡(luò)服務(wù)中具有較好的適應(yīng)性。

5 仿真結(jié)果與分析

5.1 仿真環(huán)境

將本文提出的差分-精英螞蟻算法應(yīng)用于無線傳感器網(wǎng)絡(luò)QoS仿真實(shí)驗(yàn)，實(shí)驗(yàn)計(jì)算機(jī)系統(tǒng)環(huán)境與圖1相同。實(shí)驗(yàn)中差分進(jìn)化參數(shù)設(shè)置為：N=10，F(xiàn)= 0.8，CR=0.6，gmax=200；QoS蟻群參數(shù)設(shè)置：m= 13，Q=10，n=18，Nc-m ax=200。WSN網(wǎng)絡(luò)18個(gè)節(jié)點(diǎn)由隨機(jī)鄰接矩陣產(chǎn)生，其基本參數(shù)采用系統(tǒng)默認(rèn)設(shè)置，每個(gè)節(jié)點(diǎn)以及鏈路屬性，由表2給出。鏈路延時(shí)鄰接矩陣D、帶寬鄰接矩陣C均為由隨機(jī)數(shù)產(chǎn)生的18階方陣；除源節(jié)點(diǎn)外其他節(jié)點(diǎn)能量初始值為100 J，源節(jié)點(diǎn)1 000 J；衍生熵的權(quán)值系數(shù)設(shè)置為：k1=0.4，k2=0.3，k3=0.3。

表2 網(wǎng)絡(luò)配置

5.2 實(shí)驗(yàn)結(jié)果

經(jīng)過算法程序多次運(yùn)行并選擇最優(yōu)解，得到實(shí)驗(yàn)仿真結(jié)果如圖2所示。其中，圖2（a）與圖2（b）分別表示基本蟻群與差分精英蟻群；在帶寬需求、延時(shí)上的對(duì)比仿真曲線；圖2（c）表示由隨機(jī)鄰接矩陣生成的網(wǎng)絡(luò)拓?fù)湟约皩?duì)應(yīng)的組播路徑；圖2（d）表示衍生熵的收斂曲線。

圖2 本文算法的網(wǎng)絡(luò)性能仿真對(duì)比實(shí)驗(yàn)

在圖2（a）中，基本蟻群對(duì)應(yīng)的帶寬需求在迭代到132次時(shí)收斂到穩(wěn)定值（1.283 7），差分精英蟻群在迭代到 82次時(shí)收斂到穩(wěn)定值（0.353 3）；在圖2（b）中，基本蟻群對(duì)應(yīng)的網(wǎng)絡(luò)延時(shí)，在迭代到120次時(shí)收斂到穩(wěn)定值（2.396 7），而差分精英蟻群在迭代到84次時(shí)，收斂到穩(wěn)定值（1.410 8）。對(duì)比分析表明，相對(duì)于基本蟻群，差分精英蟻群能夠以更少的迭代次數(shù)得到更好的優(yōu)化值。圖2（c）為隨機(jī)鄰接矩陣產(chǎn)生的網(wǎng)絡(luò)拓?fù)?，粗線表示在綜合考慮帶寬、時(shí)延、節(jié)點(diǎn)能量條件后，差分精英蟻群針對(duì)系統(tǒng)衍生熵優(yōu)化后的組播路徑。其原始隨機(jī)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)生成，借鑒了最小距離均值聚類算法［12］。 圖2（d）為本文提出的衍生熵收斂情況，在迭代到147次時(shí)，收斂到穩(wěn)定值（0.418 1）。 6 結(jié)束語

本文針對(duì)無線傳感器網(wǎng)絡(luò)QoS路由優(yōu)化問題，通過差分-蟻群獲得系統(tǒng)最優(yōu)參數(shù)組合，對(duì)比實(shí)驗(yàn)驗(yàn)證了其在優(yōu)化參數(shù)、求取最佳路線上的優(yōu)越性，給出差分-精英螞蟻系統(tǒng)。仿真結(jié)果表明，將本文系統(tǒng)應(yīng)用于無線傳感網(wǎng)組播中，能夠?qū)θ我釷oS服務(wù)類型，以最小熵收斂到最優(yōu)解，在降低網(wǎng)絡(luò)延時(shí)以及帶寬需求的同時(shí)，提高網(wǎng)絡(luò)壽命與能量利用率。

［1］ 李 擎，張 超，陳 鵬，等.一種基于粒子群參數(shù)優(yōu)化的改進(jìn)蟻群算法［J］.控制與決策，2013，28（6）：873-878.

［2］ Akan O B，Akyildiz I F.Event-to-sink Reliable Transport in Wireless Sensor Networks［J］.IEEE/ACM Transactions on Networking，2005，13（5）：1003-1016.

［3］ 羅中良，易明珠，劉小勇.最優(yōu)化問題的蟻群混合差分進(jìn)化算法研究［J］.中山大學(xué)學(xué)報(bào)，2008，47（3）：33-36.

［4］ 鄭衛(wèi)國，田其沖，張 磊.基于信息素強(qiáng)度的改進(jìn)蟻群算法［J］.計(jì)算機(jī)仿真，2010，27（7）：191-193.

［5］ 張家善，王志宏，陳應(yīng)顯.一種基于精英策略的改進(jìn)蟻群算法及應(yīng)用［J］.計(jì)算機(jī)系統(tǒng)應(yīng)用，2012，21（10）：105-108.

［6］ Storm R，Price K.Differential Evolution——A Sim ple and Efficient Heuristic for Global Optimization over Continuous Spaces［J］.Journal of Global Optimization，1997，11（4）：341-359.

［7］ 李明海，邢桂華.用MATLAB實(shí)現(xiàn)中國旅行商問題的求解［J］.微計(jì)算機(jī)應(yīng)用，2004，25（2）：218-222.

［8］ 史 峰，王 輝.MATLAB智能算法30個(gè)案例分析［M］.北京：北京航空航天大學(xué)出版社，2011.

［9］ Marco D，Thomas S.Ant Colony Optimization［M］. London，UK：MIT Press，2004.

［10］ Dorigo M.A Short Convergence Proof for a Class of Ant Colony Optimization Algorithms［J］.IEEE Transactions on Evolutionary Computation，2002，6（4）：358-365.

［11］ Bullnheimer B，Hartl R F，Strauss C.A New Rank-based Version of the Ant System：A Computational Study［J］. Central European Journal for Operations Research and Economics，1999，7（1）：25-38.

［12］ 許 博，楊慧中.軟測量建模中的數(shù)據(jù)校正［J］.河北科技大學(xué)學(xué)報(bào)，2012，33（6）：510-513.

編輯 劉 冰

QoS Multicast Routing Optimization Algorithm Based on Difference-elite Ant Colony

CHEN Shu，XU Bo，XU Baoguo

（College of Internet of Things Engineering，Jiangnan University，Wuxi214122，China）

For the communication link problem existing in Wireless Sensor Network（WSN），with the unequal distribution of bandwidth and nodes’energy，as well as longer delays and poor performance in adjustment with Quality of Service（QoS），this paper puts forward a difference-elite ant colony algorithm.The novel algorithm takes advantage of differential evolution algorithm to gain the combinatorial optimization in the ant colony algorithm，and the novel algorithm has the merit of elite preservation strategy，ant sort to improve convergence speed，and sets objective function based on QoS service types.Simulation results show that com pared with basic ant colony algorithm，the new algorithm can converge to the global optimal solution，and gains minimal entropy.

ant colony algorithm；differential evolution algorithm；elite preservation；Quality of Service（QoS）；entropyDO I：10.3969/j.issn.1000-3428.2015.10.022

陳 樹，許 博，徐保國.基于差分-精英蟻群的 QoS組播路由優(yōu)化算法［J］.計(jì)算機(jī)工程，2015，41（10）：117-120，125.

英文引用格式：Chen Shu，Xu Bo，Xu Baoguo.QoS Multicast Routing Optimization Algorithm Based on Difference-elite Ant Colony［J］.Com puter Engineering，2015，41（10）：117-120，125.

1000-3428（2015）10-0117-04

A

TN915

國家自然科學(xué)基金資助項(xiàng)目（21206053，21276111）；江蘇省六大人才高峰基金資助項(xiàng)目（2012-W LW-006）。

陳 樹（1969-），男，副教授，主研方向：無線傳感器網(wǎng)絡(luò)；許 博，碩士研究生；徐保國，教授。

2014-11-04

2014-12-03E-mail：15061805582@163.com