鄧慈云 劉澤文 寧林一

摘要:對(duì)于多約束QoS路由選擇問(wèn)題，將其轉(zhuǎn)化為一個(gè)多約束賦權(quán)圖，通過(guò)捕食模型調(diào)整最小時(shí)延和最小丟包率這兩個(gè)目標(biāo)的權(quán)值，找到非劣解集；然后，利用人工魚(yú)群算法較好地平衡全局搜索能力和局部搜索能力，完成最小成本的路由選擇。實(shí)驗(yàn)表明：該算法是可行的。

關(guān)鍵詞: QoS路由選擇；捕食模型；非劣解集；人工魚(yú)群算法

中圖分類號(hào)：TP301文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)：1009-3044(2012)22-5321-03

Research of multiple constrained QoS routing algorithm

DENG Ci-yun, LIU Ze-wen, NING Lin-yi

(Hunan College of Information, Changsha 410200, China)

Abstract: The paper transforms multiple constrained QoS routing problem as the most short path problem of multiple constrained assign-weight chart through aiming at it,and use the prey-predator model to find the non-inferior set immediately by adjusting the objects right of the minimum delay and the minimum packet loss rate,The Artificial Fish Swarm Algorithm,which can keep the balance between global and local search ability. It has accomplished ultimate routing with the minimum cost by using the ability of searching the global optimization.The experiment results show that the algor-ithm is effective.

Key words: QoS routing; prey-predator model; non-inferior set; artificial fish swarm algorithm

隨著Internet高速網(wǎng)絡(luò)迅速發(fā)展，要求通信網(wǎng)絡(luò)能提供高效率服務(wù)質(zhì)量（Qos）支持，當(dāng)QoS路由選擇時(shí)，通常對(duì)帶寬、延時(shí)、成本以及丟包率都存在一定的要求。而現(xiàn)有很多算法只針對(duì)一個(gè)或兩個(gè)約束條件產(chǎn)生,在多約束Qos下,這些算法具有局限性。如何解決多約束Qos路由問(wèn)題，及滿足業(yè)務(wù)要求時(shí)，盡量減少資源消耗，合理分配網(wǎng)絡(luò)流量負(fù)荷，減少阻塞率，成為關(guān)注的熱點(diǎn)。生態(tài)系統(tǒng)的捕食模型為解決上述問(wèn)題提供了新解決方法，通常在捕食模型中，捕食者與被捕食者這兩者之間能夠始終保持一種動(dòng)態(tài)的平衡，兩個(gè)種群能夠?qū)崿F(xiàn)交替占優(yōu)，種群規(guī)模發(fā)生周期性的變化，通過(guò)借鑒了上述模型，把路由選擇時(shí)延與丟包率這兩個(gè)約束條件作為目標(biāo)，捕食者和被捕食者種群通過(guò)進(jìn)化從而生成最小時(shí)延與最小丟包率的非劣解集[1]。在路由選擇的約束條件中，通常優(yōu)先考慮成本，通過(guò)運(yùn)用人工魚(yú)群算法，通過(guò)從捕食模型產(chǎn)生的滿足最小時(shí)延與最小丟包率的非劣解集中得到滿足最小成本的最優(yōu)解。

1多約束QoS路由模型

通常一個(gè)無(wú)向賦權(quán)圖G（V, E）可以用來(lái)表示一個(gè)網(wǎng)絡(luò)，網(wǎng)絡(luò)的節(jié)點(diǎn)用圖中的頂點(diǎn)表示，網(wǎng)絡(luò)連接節(jié)點(diǎn)的通信鏈路用圖中的邊表示。假設(shè)網(wǎng)絡(luò)節(jié)點(diǎn)集用V表示，連接節(jié)點(diǎn)的通信鏈路集用E表示。為了使問(wèn)題簡(jiǎn)化，設(shè)網(wǎng)絡(luò)中的每對(duì)節(jié)點(diǎn)間最多只存在一條鏈路。基于無(wú)向賦權(quán)圖G(V,E)，假設(shè)p=p(r,s)表示從源結(jié)點(diǎn)r到達(dá)目的節(jié)點(diǎn)s的一條路徑，e表示路徑p上的一條鏈路，即e∈p。常用QoS指標(biāo)的數(shù)學(xué)表示如下[3]：

1)瓶頸帶寬：bandwidth(p)=min{b(e)},設(shè)b(e)為鏈路e上的帶寬; 2)鏈路時(shí)延:delay(p)=∑

2基于捕食模型的多目標(biāo)優(yōu)化求解算法

將多約束QoS路由選擇時(shí)延與丟包率這兩個(gè)約束條件映射到捕食模型之中，最小鏈路時(shí)延與最小丟包率為我們要考慮的兩個(gè)目標(biāo)，一個(gè)種群對(duì)應(yīng)了待求解問(wèn)題的一目標(biāo)，種群數(shù)量代表相應(yīng)目標(biāo)的權(quán)值。通過(guò)把種群數(shù)量對(duì)應(yīng)到多目標(biāo)優(yōu)化問(wèn)題的目標(biāo)權(quán)值，

3人工魚(yú)群算法尋最優(yōu)解

多約束QoS路由選擇基于捕食模型得到滿足最小鏈路時(shí)延和最小丟包率的非劣解集,其中包含捕食者與被捕食者種群,尋找最優(yōu)解時(shí)，兩類種群歸為一類，把非劣解看成路由選擇中若干個(gè)結(jié)點(diǎn)，再利用人工魚(yú)群算法獲取符合最小成本的最優(yōu)路徑即最優(yōu)解。具體算法步驟如下：

步驟1：初始化人工魚(yú)群規(guī)模M、每條人工魚(yú)的初始位置、視野Visual和步長(zhǎng)Step、擁擠度δ、最大重復(fù)嘗試次數(shù)try_number、最大迭代次數(shù)等參數(shù)。從非劣解集中給出各個(gè)節(jié)點(diǎn)的值和每條存在的邊的值，給出約束條件中bandwidth(p)、delay(p)、cost(p)和loss(p)的值。然后，從源節(jié)點(diǎn)開(kāi)始放出M條人工魚(yú)，每條人工魚(yú)都執(zhí)行步驟2。

步驟2：每條人工魚(yú)按照選擇路徑規(guī)則，從相鄰節(jié)點(diǎn)集合中隨機(jī)地選擇一個(gè)節(jié)點(diǎn)，計(jì)算每條人工魚(yú)的適應(yīng)度，并與公告板的狀態(tài)比較，若較好，則將其賦給公告板。當(dāng)該人工魚(yú)成功地完成路由選擇后，計(jì)算成本值，根據(jù)其最優(yōu)值得到全局最優(yōu)的路由。

步驟3：按式7計(jì)算視野Visual和步長(zhǎng)Step。

4仿真實(shí)驗(yàn)及分析

用圖2所示網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)對(duì)本文算法進(jìn)行仿真實(shí)驗(yàn)。源節(jié)點(diǎn)和目的節(jié)點(diǎn)隨機(jī)產(chǎn)生，鏈路屬性參數(shù)用四元組（W1,W2,W3,W4）來(lái)描述，四個(gè)值分別為這條邊的四個(gè)約束值：帶寬、最大時(shí)延、丟包率、成本。設(shè)源節(jié)點(diǎn)為節(jié)點(diǎn)A，目標(biāo)點(diǎn)為節(jié)點(diǎn)J，QoS指標(biāo)約束為：所需帶寬值為10，最大時(shí)延值為20，成本≤18，丟包率≤0.2。

5結(jié)束語(yǔ)

通過(guò)捕食模型來(lái)解決QoS路由選擇中約束條件不能均衡考慮的問(wèn)題，選擇最小鏈路時(shí)延和最小丟包率作為QoS優(yōu)化的目標(biāo)，通過(guò)捕食者－被捕食者差分方程模型控制目標(biāo)權(quán)值，種群的進(jìn)化獲得一個(gè)非劣解集；再采用人工魚(yú)群算法從非劣解集中提取滿足最小成本的最優(yōu)解。兩種方法結(jié)合,有利于豐富優(yōu)化過(guò)程中的搜索行為,增強(qiáng)全局和局部意義下的搜索能力和效率,極大地發(fā)揮了人工魚(yú)群算法的全局搜索能力，取得相對(duì)較好的優(yōu)化效果，算法通過(guò)Matlab程序設(shè)計(jì)應(yīng)用于網(wǎng)絡(luò)拓?fù)鋱D中獲得了最優(yōu)路徑，證實(shí)了算法的可行性。

該文作者創(chuàng)新點(diǎn):針對(duì)多約束QoS路由選擇問(wèn)題，首先將其轉(zhuǎn)化為一個(gè)多約束賦權(quán)圖，然后通過(guò)捕食模型調(diào)整最小時(shí)延和最小丟包率這兩個(gè)目標(biāo)的權(quán)值，找到非劣解集；最后，結(jié)合人工魚(yú)群算法較好地平衡全局搜索能力和局部搜索能力，完成最小成本的路由選擇。通過(guò)實(shí)驗(yàn)表明該算法的可行。

參考文獻(xiàn)：

[1]王聯(lián)國(guó),洪毅,趙付青,余冬梅.一種改進(jìn)的人工魚(yú)群算法[J].計(jì)算機(jī)工程,2008,34(19).

[2]梁文,羅文堅(jiān),曹先彬,王煦法.基于生態(tài)捕食模型的多目標(biāo)優(yōu)化問(wèn)題求解算法[J].中國(guó)科學(xué)技術(shù)大學(xué)學(xué)報(bào),2005,35(3).

[3]冉敏,高隨祥,徐葆.一種基于蟻群系統(tǒng)的多約束QoS路由算法[J].計(jì)算機(jī)工程與應(yīng)用,2005,142-144.

[4]王正初,周慕遜,李軍,孫寶軍.基于人工魚(yú)群算法的水庫(kù)優(yōu)化調(diào)度研究[J].繼電器,2007,35(21).

[5]李曉磊,邵之江,錢積新.一種基于動(dòng)物自治體的尋優(yōu)模式:魚(yú)群算法[J].系統(tǒng)工程理論與實(shí)踐,2002,22: 32-38.

[6]李曉磊,錢積新.基于分解協(xié)調(diào)的人工魚(yú)群優(yōu)化算法研究[J].電路與系統(tǒng)學(xué)報(bào),2003,8(1):126.

[7]李倩,黃臨平.人工魚(yú)算法的重磁位場(chǎng)反演方法[J].內(nèi)蒙古石油化工,2010(16).

[8]徐飛,何定潤(rùn),楊俊儒.基于魚(yú)群算法的城市交通仿真[J].微計(jì)算機(jī)信息,2010(10).

[9]龍鵬飛,張純,賀亮.基于捕食模型與蟻群算法的多約束QoS路由選擇[J].計(jì)算機(jī)工程與應(yīng)用,2009(5).