基于差分-精英蟻群的QoS組播路由優化算法

陳 樹，許 博，徐保國

（江南大學物聯網工程學院，江蘇 無錫 214122）

基于差分-精英蟻群的QoS組播路由優化算法

陳 樹，許 博，徐保國

（江南大學物聯網工程學院，江蘇 無錫 214122）

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

蟻群算法；差分進化算法；精英保存；服務質量；熵

1 概述

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

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

為此，本文在蟻群算法基礎上，利用差分進化

算法對蟻群參數向量進行變異、交叉操作，獲得蟻群最優參數解，在差分-蟻群基礎上，優化信息素濃度更新方式，改良精英螞蟻的獎懲機制以及排序策略，將不同QoS服務類型統一到系統熵模型當中，提出具有系統熵意識的差分-精英螞蟻算法。

2 差分-精英蟻群算法

為了克服蟻群參數過于依賴人工經驗缺陷，本文提出將差分進化算法引入蟻群系統，形成差分-蟻群，對由原始蟻群參數構成個體（α，β，ρ）進行優化選擇，最終獲得不同 WSN環境下的最優參數組合。

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

3 差分-蟻群算法實現

3.1 蟻群參數優化

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

3.1.1 優化步驟

差分進化算法優化蟻群參數步驟如下表示：

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

其中，P0（X）表示第0代種群；表示第0代種群的第i個個體；gmax表示最大進化代數。

Step2 讀取ACO適應度函數，進行個體評價并求最優解。

Step3 若達到終止條件（迭代次數到gmax，或者連續2個適應度函數值小于臨界值）則算法終止，輸出結果；否則轉Step4。

Step4 根據下面的式（1）變異操作、式（2）交叉操作得到實驗種群：

Step5 根據式（3）選擇下一代的進化種群：

Step6 迭代計數器累加1，轉到Step2。

3.1.2 優化效果

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

表1 3種算法實驗結果對比

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

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

圖1 DEACO路徑以及收斂狀況

在說明了DEACO在蟻群參數自適應優化方面的優越性后，繼續對算法進行優化，并在DEACO基礎上得到了差分-精英系統。

3.2 精英保存策略

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

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

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

Step4 邊界判定：

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

同時對每輪周游后得到全局最優解的螞蟻給予額外的信息素補償：

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

4 螞蟻的QoS熵意識

針對QoS 3種服務類型切換時調整參數存在較多的重復性工作問題，將3種服務類型統一到系統熵的效用函數上來。

依據QoS不同的服務，即音視頻流服務（高帶寬、耗能低、低延時），異常報警服務（低延時、耗能無要求），普通信息服務（帶寬、耗能及時延要求都不高），將組播樹帶寬消耗w1（帶寬指標）、節點剩余能量的均方差w2（耗能指標）、每輪迭代的延時w3（延時指標）作為信息量，根據不同的服務類型，為3個信息量設置不同的權系數，由此構建描述組播樹穩定性好壞的表達式S，并稱之為組播樹的衍生熵。需

特別指出的是，w1，w2，w33個指標屬于不同量綱，其數據歸一化采用Z-score標準化算法，即：

其中，μ為均值；σ為標準差。

最終得到S表達式為：

其中，ki（i=1，2，3）為熵權值系數；表示w1，w2，w3的歸一化數據。

針對不同的QoS服務類型，只需要修改相應權系數即可，在WSN不同的網絡服務中具有較好的適應性。

5 仿真結果與分析

5.1 仿真環境

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

表2 網絡配置

5.2 實驗結果

經過算法程序多次運行并選擇最優解，得到實驗仿真結果如圖2所示。其中，圖2（a）與圖2（b）分別表示基本蟻群與差分精英蟻群；在帶寬需求、延時上的對比仿真曲線；圖2（c）表示由隨機鄰接矩陣生成的網絡拓撲以及對應的組播路徑；圖2（d）表示衍生熵的收斂曲線。

圖2 本文算法的網絡性能仿真對比實驗

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

本文針對無線傳感器網絡QoS路由優化問題，通過差分-蟻群獲得系統最優參數組合，對比實驗驗證了其在優化參數、求取最佳路線上的優越性，給出差分-精英螞蟻系統。仿真結果表明，將本文系統應用于無線傳感網組播中，能夠對任意QoS服務類型，以最小熵收斂到最優解，在降低網絡延時以及帶寬需求的同時，提高網絡壽命與能量利用率。

［1］ 李 擎，張 超，陳 鵬，等.一種基于粒子群參數優化的改進蟻群算法［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］ 羅中良，易明珠，劉小勇.最優化問題的蟻群混合差分進化算法研究［J］.中山大學學報，2008，47（3）：33-36.

［4］ 鄭衛國，田其沖，張 磊.基于信息素強度的改進蟻群算法［J］.計算機仿真，2010，27（7）：191-193.

［5］ 張家善，王志宏，陳應顯.一種基于精英策略的改進蟻群算法及應用［J］.計算機系統應用，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實現中國旅行商問題的求解［J］.微計算機應用，2004，25（2）：218-222.

［8］ 史 峰，王 輝.MATLAB智能算法30個案例分析［M］.北京：北京航空航天大學出版社，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］ 許 博，楊慧中.軟測量建模中的數據校正［J］.河北科技大學學報，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組播路由優化算法［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

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

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

2014-11-04

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