魏傳佳， 茆政吉

(1．泉州輕工職業(yè)學院 計算機系,福建 泉州 362200； 2.臺灣大學 計算機系,臺灣 10617)

?

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

魏傳佳1， 茆政吉2

(1．泉州輕工職業(yè)學院 計算機系,福建 泉州 362200； 2.臺灣大學 計算機系,臺灣 10617)

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

關鍵詞：QoS路由；改進DNA計算模型；改進DNA頂點著色；改進DNA貪婪算法

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

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

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

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

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

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

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

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

QoS路由選擇問題是滿足如下條件使得C最小：

2參數(shù)假設

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

3改進DNA頂點著色算法

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

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

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

算法設計圖如圖1所示。

圖1　DNA算法設計步驟圖

3.1算法的優(yōu)點

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

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

4改進DNA極大獨立集算法

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

算法步驟如下:

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

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

(5)查找不存在于獨立集中，但也能夠被放入獨立集中的頂點，即：vi?I且vi不能進行標記，則令I=I∪vi.

4.1算法正確性證明

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

又因為

NM+ΔM

4.2算法的優(yōu)點

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

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

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

4.3仿真基準圖比較

表1　改進DNA貪婪算法、MIN算法和VO算法實驗結(jié)果對比

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

5結(jié)語

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

[參考文獻]

[1]周康，同小軍，劉文斌，等.基于閉環(huán)DNA計算的最大獨立集問題的算法[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].計算機工程，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.

[責任編輯王新奇]

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

中圖分類號：TP302

文獻標志碼：A

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

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

收稿日期：2015-10-28

茆政吉(1964—)，男，臺灣臺北人，臺灣大學計算機系教授，博士，主要從事計算機控制，飛彈計算機設計研究.