魏傳佳， 茆政吉

(1．泉州輕工職業(yè)學(xué)院 計(jì)算機(jī)系,福建 泉州 362200； 2.臺(tái)灣大學(xué) 計(jì)算機(jī)系,臺(tái)灣 10617)

?

基于改進(jìn)DNA算法的QoS路由優(yōu)化研究

魏傳佳1， 茆政吉2

(1．泉州輕工職業(yè)學(xué)院 計(jì)算機(jī)系,福建 泉州 362200； 2.臺(tái)灣大學(xué) 計(jì)算機(jī)系,臺(tái)灣 10617)

摘要：針對(duì)無線網(wǎng)絡(luò)中QoS路由優(yōu)化問題，提出一種綜合改進(jìn)DNA算法的計(jì)算模型.其中對(duì)于QoS路徑尋址提出改進(jìn)DNA頂點(diǎn)著色的算法模型；對(duì)于QoS最優(yōu)路徑尋址提出改進(jìn)DNA貪婪算法的算法模型，最后通過DNA實(shí)驗(yàn)仿真得到QoS路由優(yōu)化結(jié)果對(duì)比.實(shí)驗(yàn)結(jié)果證明此算法的有效性與正確性.

關(guān)鍵詞：QoS路由；改進(jìn)DNA計(jì)算模型；改進(jìn)DNA頂點(diǎn)著色；改進(jìn)DNA貪婪算法

無線網(wǎng)絡(luò)中的QoS路由優(yōu)化問題是最優(yōu)化領(lǐng)域研究的熱點(diǎn)，QoS路由優(yōu)化可作為一種NP完全問題去探討.所涉及參數(shù)有延遲、帶寬、丟包率、抖動(dòng)、跳數(shù)等，主要的研究方法有模擬退火算法、遺傳算法、遺傳混合算法等，QoS路由將其作為一種從源節(jié)點(diǎn)到目的節(jié)點(diǎn)，滿足特定約束條件下，并且代價(jià)最小的分布樹.遺傳算法在計(jì)算過程中會(huì)出現(xiàn)過早收斂和局部搜索能力差的問題，S.Kirkpatrick提出的模擬退火算法雖然局部搜索能力強(qiáng)，但是全局搜索能力差，遺傳混合算法的算法復(fù)雜度比較高.

本文針對(duì)無線網(wǎng)絡(luò)中QoS路由優(yōu)化路徑尋址與最優(yōu)路徑尋址問題，提出一種改進(jìn)的DNA頂點(diǎn)著色算法和改進(jìn)DNA貪婪算法去解決上述問題，通過對(duì)比文獻(xiàn)，本文算法有效性、正確性好.

1QoS路由優(yōu)化模型

則路徑上的總延遲函數(shù)定義為[1]

路徑l上的瓶頸帶寬定義為

B(l)=MIN{B(e),e∈l}B為最小帶寬約束

路徑l上的抖動(dòng)函數(shù)定義為

路徑l上的丟包率函數(shù)定義為

QoS路由選擇問題是滿足如下條件使得C最?。?/p>

2參數(shù)假設(shè)

假設(shè)l=(s,O)為路徑選擇，任意點(diǎn)(s,di)路徑之間交叉相連，如果線路存在交叉，就將交叉線路舍去，繼續(xù)搜索其他路徑，直到尋找出不交叉線路分組為止.此問題可轉(zhuǎn)化為求解l著色問題(即頂點(diǎn)著色問題)，從不交叉分組中求出最優(yōu)分組作為求解QoS的主要參數(shù)條件，那么最優(yōu)分組問題轉(zhuǎn)為求解分組的極大獨(dú)立集問題.解決頂點(diǎn)著色問題有許多經(jīng)典算法，如順序著色算法，并行著色算法等，這些都是解決頂點(diǎn)著色問題相對(duì)比較有效的算法，但是復(fù)雜度比較高，一般執(zhí)行時(shí)間為o(logn).極大獨(dú)立集算法有貪婪算法、MIN算法和VO算法等.

3改進(jìn)DNA頂點(diǎn)著色算法

設(shè)圖G的節(jié)點(diǎn)集與邊集[1-3]分別記為V={v1,v2,v3,…,vn};E={e1,e2,e3,…,en};K種顏色集合C={0,1,2,…,K-1};圖G正常頂點(diǎn)著色，簡稱為圖的K-著色，即K-著色是V到G的一個(gè)映射集合：σ:V(G)|→C(K);σ(vi)≠σ(ej),?e=viej∈E(G).

(1)對(duì)于k-圖的頂點(diǎn)著色，可以逐漸刪除已經(jīng)著色的子集Vi，只對(duì)余下的子集VN-i繼續(xù)進(jìn)行編碼處理即可，這樣可以減少運(yùn)算量；

(2)對(duì)于檢測(cè)的循環(huán)數(shù)T，對(duì)于k-圖頂點(diǎn)著色，如果k-圖頂點(diǎn)可著色，那么只需要k次循環(huán)即可；如果k-圖頂點(diǎn)不可著色，那么只需要T-k+1次循環(huán)即可.

算法設(shè)計(jì)圖如圖1所示。

圖1　DNA算法設(shè)計(jì)步驟圖

3.1算法的優(yōu)點(diǎn)

(1)對(duì)于判定某一個(gè)圖G是否為頂點(diǎn)著色問題，只需要在本算法中刪除循環(huán)體部分就可以.簡化了算法步驟；

(2)對(duì)比經(jīng)典頂點(diǎn)著色算法[4-6]，本算法大大降低了空間復(fù)雜度.

4改進(jìn)DNA極大獨(dú)立集算法

設(shè)I是圖G的最大獨(dú)立集[7]，Pvi是與頂點(diǎn)vi不相鄰的頂點(diǎn)構(gòu)成的集合，即：Pvi={vj|i≠j}，由于獨(dú)立集頂點(diǎn)具有兩點(diǎn)之間不相鄰的特性，那么根據(jù)構(gòu)造的不相鄰頂點(diǎn)集合Pvi來提出改進(jìn)的DNA貪婪算法.

算法步驟如下:

(1)令I(lǐng)=φ,V=V(G,E)，初始化Pvi=Pv0；

(4)重復(fù)進(jìn)行步驟3，一直到I不再增加數(shù)量為止；

(5)查找不存在于獨(dú)立集中，但也能夠被放入獨(dú)立集中的頂點(diǎn)，即：vi?I且vi不能進(jìn)行標(biāo)記，則令I(lǐng)=I∪vi.

4.1算法正確性證明

證明設(shè)獨(dú)立集的初始數(shù)是M，vi是獨(dú)立集I中的一個(gè)頂點(diǎn)，Pvi是vi的不相鄰頂點(diǎn)集合.

又因?yàn)?/p>

NM+ΔM

4.2算法的優(yōu)點(diǎn)

與傳統(tǒng)經(jīng)典的貪婪算法對(duì)比，此改進(jìn)DNA算法有如下的優(yōu)點(diǎn)：

(1)MIN算法[7]是通過不斷的修改圖來實(shí)現(xiàn)的，此算法不用重復(fù)的修改圖，所以可以減少中間的時(shí)間花費(fèi)；

(2)VO算法[6]是先把度進(jìn)行單調(diào)排序，然后按順序取各個(gè)頂點(diǎn)，判斷各個(gè)頂點(diǎn)是否符合加入到最大獨(dú)立集合中；而本算法是從不相鄰的頂點(diǎn)集中選取滿足條件的點(diǎn)，即：把搜索的范圍減少了.

4.3仿真基準(zhǔn)圖比較

表1　改進(jìn)DNA貪婪算法、MIN算法和VO算法實(shí)驗(yàn)結(jié)果對(duì)比

實(shí)驗(yàn)結(jié)果表1中標(biāo)帶星號(hào)的數(shù)字是說明本文算法得出了最優(yōu)解.

5結(jié)語

針對(duì)無線網(wǎng)絡(luò)中QoS路由優(yōu)化問題，本文提出了針對(duì)路徑尋址與最優(yōu)尋址的改進(jìn)DNA頂點(diǎn)著色算法與極大獨(dú)立集算法，切實(shí)解決了無線路由中最短路徑尋址的優(yōu)化問題與P2P數(shù)據(jù)分組[7]問題，對(duì)比其他算法本算法尋址更快，收斂速度更快，為無線網(wǎng)絡(luò)優(yōu)化提供了新的算法.

[參考文獻(xiàn)]

[1]周康，同小軍，劉文斌，等.基于閉環(huán)DNA計(jì)算的最大獨(dú)立集問題的算法[J].計(jì)算機(jī)工程，2008,34(4):40-41.

[2]XU J M.Theory and application of fraphs[M].Dordrecht:Kluwer Academic Publishers,2013.

[3]FALKENAUER E,DELCHAMBER A.A genetic algorithm for bin packing and lin balancing[C].Proceedings of IEEE Intermational Conference on Robotics and Automation,1992.

[4]唐天兵，申文杰，韋凌云.DNA遺傳算法的QoS多播路由優(yōu)化[J].計(jì)算機(jī)工程，2010,36(5):106-108.

[5]LAWLER E L.Combinatotial optimization:networks and matroids[M].New York:Holt Rienhart and Winston,2013.

[6]ZHOU Kang,GAO Zun-hai,XU Jin.An algorithm of DNA computing on 0-1 planning problem[J].Advances in Systems Science and Applications,2005,5(4):587-593.

[7]LIY Wen-bin,et al.TSP problem based on DNA computing[J].Journal of Chemical Information and Computer Science,2002,42(5):1176-1178.

[責(zé)任編輯王新奇]

Research on QoS Routing OptimizationBased on Improved DNA Algorithm

WEI Chuan- jia1， MAO Zheng-ji2

(1．Department of Computer，Quanzhou Technology College，Quanzhou 362200，China；

2．Department of Computer， National Taiwan University，Taiwan 10617，China)

Abstract：Aiming at QoS routing optimization problem, this paper present a complex improved DNA algorithm. For the shortest path for addressing QoS, improves DNA vertex coloring algorithm proposed model, For the QoS packeting, suggests an improvement for DNA greedy algorithm model, and it finally gets QoS routing optimization results through simulation experiments comparing DNA. Experimental results demonstrate the effectiveness and accuracy of the algorithm.

Key words：QoS routing；improved model of DNA computing；improved DNA encoding；improved model of DNA greedy algorthm

中圖分類號(hào)：TP302

文獻(xiàn)標(biāo)志碼：A

作者簡介：魏傳佳(1983—)，男，黑龍江佳木斯人，泉州輕工職業(yè)學(xué)院計(jì)算機(jī)系講師，碩士，高級(jí)網(wǎng)絡(luò)工程師，主要從事網(wǎng)絡(luò)最優(yōu)化，DNA計(jì)算研究；

基金項(xiàng)目：福建省教育廳科技項(xiàng)目(JA15905)

收稿日期：2015-10-28

茆政吉(1964—)，男，臺(tái)灣臺(tái)北人，臺(tái)灣大學(xué)計(jì)算機(jī)系教授，博士，主要從事計(jì)算機(jī)控制，飛彈計(jì)算機(jī)設(shè)計(jì)研究.