基于改进DNA算法的QoS路由优化研究

魏传佳， 茆政吉

(1．泉州轻工职业学院 计算机系,福建 泉州 362200； 2.台湾大学 计算机系,台湾 10617)



基于改进DNA算法的QoS路由优化研究

魏传佳1， 茆政吉2

(1．泉州轻工职业学院 计算机系,福建 泉州 362200； 2.台湾大学 计算机系,台湾 10617)

摘要：针对无线网络中QoS路由优化问题，提出一种综合改进DNA算法的计算模型.其中对于QoS路径寻址提出改进DNA顶点着色的算法模型；对于QoS最优路径寻址提出改进DNA贪婪算法的算法模型，最后通过DNA实验仿真得到QoS路由优化结果对比.实验结果证明此算法的有效性与正确性.

关键词：QoS路由；改进DNA计算模型；改进DNA顶点着色；改进DNA贪婪算法

无线网络中的QoS路由优化问题是最优化领域研究的热点，QoS路由优化可作为一种NP完全问题去探讨.所涉及参数有延迟、带宽、丢包率、抖动、跳数等，主要的研究方法有模拟退火算法、遗传算法、遗传混合算法等，QoS路由将其作为一种从源节点到目的节点，满足特定约束条件下，并且代价最小的分布树.遗传算法在计算过程中会出现过早收敛和局部搜索能力差的问题，S.Kirkpatrick提出的模拟退火算法虽然局部搜索能力强，但是全局搜索能力差，遗传混合算法的算法复杂度比较高.

本文针对无线网络中QoS路由优化路径寻址与最优路径寻址问题，提出一种改进的DNA顶点着色算法和改进DNA贪婪算法去解决上述问题，通过对比文献，本文算法有效性、正确性好.

1QoS路由优化模型

则路径上的总延迟函数定义为[1]

路径l上的瓶颈带宽定义为

B(l)=MIN{B(e),e∈l}B为最小带宽约束

路径l上的抖动函数定义为

路径l上的丢包率函数定义为

QoS路由选择问题是满足如下条件使得C最小：

2参数假设

假设l=(s,O)为路径选择，任意点(s,di)路径之间交叉相连，如果线路存在交叉，就将交叉线路舍去，继续搜索其他路径，直到寻找出不交叉线路分组为止.此问题可转化为求解l着色问题(即顶点着色问题)，从不交叉分组中求出最优分组作为求解QoS的主要参数条件，那么最优分组问题转为求解分组的极大独立集问题.解决顶点着色问题有许多经典算法，如顺序着色算法，并行着色算法等，这些都是解决顶点着色问题相对比较有效的算法，但是复杂度比较高，一般执行时间为o(logn).极大独立集算法有贪婪算法、MIN算法和VO算法等.

3改进DNA顶点着色算法

设图G的节点集与边集[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-图的顶点着色，可以逐渐删除已经着色的子集Vi，只对余下的子集VN-i继续进行编码处理即可，这样可以减少运算量；

(2)对于检测的循环数T，对于k-图顶点着色，如果k-图顶点可着色，那么只需要k次循环即可；如果k-图顶点不可着色，那么只需要T-k+1次循环即可.

算法设计图如图1所示。

图1　DNA算法设计步骤图

3.1算法的优点

(1)对于判定某一个图G是否为顶点着色问题，只需要在本算法中删除循环体部分就可以.简化了算法步骤；

(2)对比经典顶点着色算法[4-6]，本算法大大降低了空间复杂度.

4改进DNA极大独立集算法

设I是图G的最大独立集[7]，Pvi是与顶点vi不相邻的顶点构成的集合，即：Pvi={vj|i≠j}，由于独立集顶点具有两点之间不相邻的特性，那么根据构造的不相邻顶点集合Pvi来提出改进的DNA贪婪算法.

算法步骤如下:

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

(4)重复进行步骤3，一直到I不再增加数量为止；

(5)查找不存在于独立集中，但也能够被放入独立集中的顶点，即：vi∉I且vi不能进行标记，则令I=I∪vi.

4.1算法正确性证明

证明设独立集的初始数是M，vi是独立集I中的一个顶点，Pvi是vi的不相邻顶点集合.

又因为

NM+ΔM

4.2算法的优点

与传统经典的贪婪算法对比，此改进DNA算法有如下的优点：

(1)MIN算法[7]是通过不断的修改图来实现的，此算法不用重复的修改图，所以可以减少中间的时间花费；

(2)VO算法[6]是先把度进行单调排序，然后按顺序取各个顶点，判断各个顶点是否符合加入到最大独立集合中；而本算法是从不相邻的顶点集中选取满足条件的点，即：把搜索的范围减少了.

4.3仿真基准图比较

表1　改进DNA贪婪算法、MIN算法和VO算法实验结果对比

实验结果表1中标带星号的数字是说明本文算法得出了最优解.

5结语

针对无线网络中QoS路由优化问题，本文提出了针对路径寻址与最优寻址的改进DNA顶点着色算法与极大独立集算法，切实解决了无线路由中最短路径寻址的优化问题与P2P数据分组[7]问题，对比其他算法本算法寻址更快，收敛速度更快，为无线网络优化提供了新的算法.

[参考文献]

[1]周康，同小军，刘文斌，等.基于闭环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多播路由优化[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—)，男，黑龙江佳木斯人，泉州轻工职业学院计算机系讲师，硕士，高级网络工程师，主要从事网络最优化，DNA计算研究；

基金项目：福建省教育厅科技项目(JA15905)

收稿日期：2015-10-28

茆政吉(1964—)，男，台湾台北人，台湾大学计算机系教授，博士，主要从事计算机控制，飞弹计算机设计研究.