计算机通信网络中容量与流量分配的优化研究(1)

计算机通信网络中容量与流量分配的优化研究(1)

第29卷第2期2003年6月

　　文章编号:100025889(2003)0220077204

甘　肃　工　业　大　学　学　报

JournalofGansuUniversityofTechnologyVol.29No.2

Jun.2003

计算机通信网络中容量与流量分配的优化研究

许福永,林晓辉

(兰州大学信息科学与工程学院,甘肃兰州　730000)

摘要:为了改进计算机通信网络的性能并降低其运营费用,采用改进的并行遗传算法,对计算机网络中容量与流量分配问题进行了优化,比较了不同算法所得到的网络运营费用.大量的计算机仿真实验结果表明,该算法能较迅速地求出全局近似最优解,并且与传统的方法相比较,解的质量能大幅度地提高.这对于减少网络运营费用及合理利用网络资源等方面都具有重大意义,在计算机通信网络及其它网络的规划设计、性能优化及评估中具有重要的理论和实用价值以及广阔的应用前景.

关键词:计算机通信网络;改进的并行遗传算法;容量与流量分配;组合优化中图分类号:TP393　　文献标识码:A

StudyonoptimizationsforcapacityandflowincomputerX2y(University,Lanzhou　730000,China)

Abstract:Intoproveperformancesofcomputercommunicationnetworksandtodecreasetheiroperational

costs,theproblemofcapacityandflowassignmentsincomputernetworksisoptimizedbyusinganimprovedparallelge2neticalgorithm.Theoperationalcostsofnetworksobtainedbyusingdifferentalgorithmsarecompared.Theoutcomesofagreatnumberofcomputersimulationexperimentsareshownthat,thenearoveralloptimalsolutionbyusingthealgorithmcanbemorerapidlysolved,andthequalityofsolutioncanbegreatlyimprovedincomparisonwiththetraditionalmethod.Itisofgreatsignificanceforreducingtheoperationalcostsinnetworksandrationalutilizingnetworkresourceetc.Andithasimportanttheoreticalandpracticalapplicationvaluesaswellasbroadapplicationprospectsinprogram2minganddesign,performanceoptimizationandevaluationofcomputercommunicationnetworksandothernetw

orks.

Keywords:computercommunicationnetworks;improvedparallelgeneticalgorithm;capacityandflowassignments;

combinatorialoptimization

　　在规划设计或者扩展计算机网络时,所面临的

主要问题是在已知网络拓扑及各节点对通信需求的前提下,计算机通信网的链路容量优化分配与最佳路由选择问题.但该问题是一个约束条件诸多而复杂的非线性规划,属于组合优化中的NP完全一类的问题,目前在传统的数学理论中尚无切实有效的求解方法.国内外学者对该问题的求解进行了探索[1,2].1975年美国Holland教授[3]首次系统地提出了遗传算法,利用计算机模拟生物进化过程的人

　　收稿日期:2002207215　　基金项目:甘肃省自然科学基金(ZS0012A2220162G)　　作者简介:许福永(19412),男,河北吴桥人,教授.

工寻优方法,在解的空间内能并行搜索的区域大、效率高,能以较大的概率求得全局近似最优解,特别适用于求解传统的数学优化方法难以解决的工程优化

问题.目前遗传算法在工程结构优化、电力系统规划、模式识别、人工神经网络等方面得到了广泛应用[4].我国叶大振等人[5]将遗传算法用于网络的路由选择及容量与流量分配问题,得出了较满意的结果.我们对简单遗传算法进行了改进[6],并应用于计算机网络中路由选择的优化问题.

本文应用改进的并行遗传算法对计算机网络中的容量与流量分配问题进行了优化,大幅度地提高了计算机网络的性能指标及其运营费用.

计算机通信网络中容量与流量分配的优化研究(1)

　　　　　　　　　　　　　　　　　　　甘肃工业大学学报　　　　　　　　　　　　　　 78 　第29卷

1　计算机网络中的链路容量与流量分2　应用改进的并行遗传算法求解CFA

配问题的数学模型

　　链路容量与流量分配问题可描述为:在给定网络拓扑结构与每对节点通信量的前提下,如何选择网络中各条链路的容量及各节点对之间的通信路由,才能既保证网络的通信需求,又能使网络的运行成本最低.所需要作的简化与假设同文献[6].这是一个约束条件多而复杂的非线性问题,其数学模型为

Z=

l∈L

的优化问题

　　应用文献[6]所提出的改进型并行遗传算法求解计算机通信网络中容量与流量分配(CFA)的优化问题与求解其路由选择优化问题的不同是,染色体分为两个基因片段:前面的基因片段表示路由,其基因位由随机法产生,后面的基因片段表示每条链路的容量指标,其基因位要保证链路容量大于其流量;CFA优化问题的适应值为1/Z.

∑∑Q

D

k∈I

l

lkylk

-FlC∑

l

+

3　计算机仿真结果及其分析

在计算机仿真过程中,对文献[6]所给出的

(1)

G

l∈Lk∈I

∑(S

l

lkylk+dlmlk)+VlkFlylk

l∈Lk∈I

ARPA网和OCT网中每对节点的路由按最少跳数法

规定了5条候选路由,并进行了编号,每个染色体的前部为路由表,后部为网络候选链路容量.

(2)(3(5)(6)

　　此问题的约束条件为

λδ

μ∑x

r∈Rk∈I

rrlr

≤

k∈I

Q∑

l

lkyk

　(Πl∈L)

,但比,CFA优化..在选择网络中各条链路容量及各节点对之间的通信路由时,既要保证网络的性能指标要求,又要使网络的运营成本最低.因此,要综合考虑影响网络运营总费用的诸多因素.

表1　候选链路容量及相应费用

Tab.1　Capacitiesofchaincircuits2candidatesandtheircosts链路容量

/bps480096001920050000108000230000460000

y∑

l

lk

=1　(Πl∈L)=p)r∈S

x∑

p

r

xr=0,1(k∈Il,l∈L)ylk

=0,1　(Πk∈Il,l∈L)

式中,Z为网络运营的总费用的优化变量;Fl=

λδ∑rrlxrμ为链路l上的数据流量;Il为第l条链路的候选链路型号指标集,l∈L;Qlk为第l条链路的型号指标选为k时的线路容量(bit/s),l∈L,k∈Il;Slk为第l条链路的型号指标选为k时的链路固定造价

(元/月),l∈L,k∈Il;Clk为第l条链路的型号指标

固定造价

/元

650750850850240013001300

距离费用/(元 km)

0.40.52.14.24.221

60

流量费用系数

/(元 bps)

0.3600.2520.1260.0300.0240.0200.017

选为k时的链路非固定(可变)成本系数(元/bps),l

∈L,k∈Il;ylk为优化变量,当第l条链路的型号指标选为k时,取值为1,否则为0;dl为第l条链路的长度;mlk为第l条链路的型号指标选为k时的每公里距离费用;D为单位平均时延的费用成本系数

(元/月 分组);G与V分别为固定费用和可变费用

　　分组长度与网络各项费用的关系如表2所示.在计算中,单位平均时延的费用成本系数为2000元/月 分组,固定及可变费用加权系数均为1.从表2可以看出,网络的运营总费用随分组长度的增加

的加权系数;其余符号的定义与文献[6]相同.式(1)表示网络运营的总费用为三项费用之和,其中第一项为链路的时延费用,第二项和第三项分别为网络的固定费用与可变费用.约束条件(2)表示链路l的容量要大于其通信流量;约束条件(3)和(4)表示必须给链路l选择某一链路容量;约束条件(5)与 …… 此处隐藏：6428字，全部文档内容请下载后查看。喜欢就下载吧 ……