第5章-通信网中的流量优化

第5章通信网中的流量优化引言网的作用主要是将业务流从源端送到宿端。为了充分利用网资源，包括线路、转接设备等，总希望合理的分配流量，以使从源到宿的流量尽可能大，传输代价尽可能小等。流量分配的好坏将直接关系到网的使用效率和相应的经济效益，是网运行的重要指标之一。网内流量的分配并不是任意的，它受限于网的拓扑结构、边和端的容量，所以流量分配实际上是在某些限制条件下的优化问题。5.1流量优化的一般性问题用有向图表示通信网。其中端集：。对于各边，设为有向边，其中eij表示从Vi到Vj的边。每条边能够通过的最大流量称为边的容量，以Cij表示；而这条边上实际的流量记为fij。一组流量的安排｛fij｝称为网内的一个流。若这个流使得从源端到宿端有总流量F，则，fij必须满足以下条件：（1）非负性和有限性(,)GVE12{,,,}nVvvv0ijijfc（2）连续性其中，具有m条边、n个端的图共有2m＋n-1个限制条件，其中包括：m个非负性条件，因为m条边的非负性；m个有限性条件，因为m条边的有限性；n－1个连续性条件，因为对应于n个端的n个等式，有一个不是独立的，故只有n－1个端的连续性。则满足（1）和（2）条件的称为可行流。()()0jijiisijjiijijidvvvvFvvffFvv、若为源端若为源端其它()={:}ijvvijeE()={:}ijvvjieE、不同的流量分配可得不同的可行流。一般有两种优化可行流的问题：（1）最大流问题：研究变更可行流中各fij值，使得总流量最大。（2）最佳流问题（即最小费用流）：由于各条边的参数中，有容量Cij的规定，费用aij的差别，即单位流量所需的费用。调整fij使得总费用：最小。更复杂的问题是：流量fij可以调整；容量Cij可选择，但边有容量的限制；各端有转接容量的限制；源端和宿端可能有多个；各边中单位容量的费用βij；各端中转接容量的费用βii； ijijijeEaf＝则转接容量；目标函数即总费用：。ijjijCf＝ijij,ijC＝5.2最大流量问题有向图G＝（V，E），设X是端集V的一个真子集，并且源端Vs∈X，宿端Vt∈G－X；（X，）表示X和的界上的边集，这个边集是把Vs和Vt分开的一个割集（最小割边集）。取Vs－Vt的方向为割集的方向。与割集方向一致的边，称为前向边；与割集方向相反的边，称为反向边；显然，前向边的集合可以割断Vs－Vt的通路。定义割集中前向边容量之和为其割容量，或简称割量。记为；XX,(,)ijijvXvXcXXc源宿端的总流量F符合两个关系：证明：由连续性公式，对于，有对所有X中的求和，可得(1)(,)(,)(2)(,)FfXXfXXFcXXivX0jjisijjivVvVisFvvffvv=ivijijjiijvXvVvXvVffF求和时一项为正，一项为负而抵消，所以可得根据定义可得（1），如下由于和流量必不大于容量，得再由流量的非负性和，得(2)iijjjiijvXvXvXvXffF(,)(,)fXXfXXF(,)(,)fXXcXX(,)FcXX饱和边：fij＝Cij的前向边称为饱和边；fijCij的前向边称为非饱和边;反向边则分为零流量和非零流量：可增流路：从Vs→Vt的一条路径P中，如果所有的前向边都未饱和，所有的反向边都是非零流量，则此条路径称为可增流路。可增流路的性质：在可增流路上，所有正向边的流量均可增加不致破坏流量的有限性；所有反向边上均可减流不致破坏非负性；可减流路上的减流相当于正向边上增流；含有多条边的可增流链路上的增流（包含反向边上减流）的最小值，应当是：此处eij代表链路中的正向边，eji代表反向边。可增流路在增流以后（反向边上减流），可得一新的可行流并使源宿端间的流量增加。min(min(),min)ijjiijijjiePePcff如果可行流｛fij｝已经使得源宿端间的流量得到最大值，则从Vs－Vt的每一条路上，至少有一个饱和的前向边，或一个零流的反向边，也就是不存在一条可增流（可减流）的路。最大流量－最小割量定理：当源宿间的流量达到最大，每个割集中的前向流量都等于最大流量Fmax，并且总存在这样一个割集，其每条正向边都是饱和的，其割量在各个割集中达到最小值，并且也等于Fmax，也可以看出，这个最小割量的割集影响到这个网络的最大流量。最大流量的标志算法称M算法基本思想：寻找源—宿端流可增广路径，使网络流的流量得到增加，直到最大流为止。算法分2个过程：1是标记过程，通过标记过程找到一条可增广路径；2是增广过程，即沿增广路径增加网络流量的过程。(,)XX(,)fXX算法步骤M0：初始，令fij＝0，标出其相邻端的流量、方向；选择任一链路；M1:标源端为（＋，s，∞）；M2：查已标、未查端Vi，标出其所有的邻端.方法：若eij在已标域E，且cijfij,即可增流，则标（＋，i，ei），表示i－j有边，可增流ei其中ej＝min（Cij－fij，ei）；1.未标记节点：所有未赋标记的节点；2.未检查的标记节点：如果节点x已有标记，但其邻接节点y没有完全标记，则x称为未检验的标记节点；3.已检查的标记节点：若节点x已标记，x所有邻接的节点都已标记，则x称为已检验的标记节点；标记：(+，x，w)或(−，x，w)表示，其中x∈V，w是标记值。M算法中图G的节点标记有三种情况：（1）.未标记节点：所有未赋标记的节点；（2）.未检查的标记节点：如果节点x已有标记，但其邻接节点y没有完全标记，则x称为未检验的标记节点；（3）.已检查的标记节点：若节点x已标记，x所有邻接的节点都已标记，则x称为已检验的标记节点；1．标记过程第1步：对源节点S标记(+,s,∞)；第2步：任选一个未检查的标记节点x，对与x邻接未标记节点y：(a).对所有(x,y)∈E的未标记节点y，若f(x,y)C(x,y)，则对节点y标记(+,x,w(y))，其中w(y)=min[w(x),c(x,y)−f(x,y)]。(b).对所有(y,x)∈E的未标记节点y，若f(y,x)0，则对节点y标记（−,x,w(y)），其中w(y)=min[w(x),f(y,x)]；在x的标记+或-上加上圆圈，x就成为已检查的标记节点。第3步：A.若节点t被标记，则转至算法的增广过程；B.若节点t虽然未被标记，但标记过程不能继续下去，就结束算法；否则，就返回标记过程的第2步。2．增广过程第1步：设节点Z=t，转至下面的第2步；(逆向增广)第2步：若Z的标记(+,q,w(z))，或(⊕,q,w(z))，将流f(q,z)变成f(q,z)+w(z)；若Z标记(−,q,w(z))，或(Θ,q,w(z))，将流f(z,q)变成f(z,q)−w(z)；第3步：若q=s，取消网G中所有节点的标记，并转至算法标记过程第1步，进行下一次迭代过程；若q≠s，设q=Z，返回增广过程第2步。(三)、算法复杂度在一次迭代中，标记过程需比较：(n−1)+(n−2)+…+1=0.5n(n−1)次;在增广过程的第2步需进行加法/减法运算为：≤(n-1)次；若网络可增的最大流量为fst，则算法复杂度为O(fst•n2)。M算法推广1.无向网和混合网中的最大流无向网和混合网中的最大流在无向图或混合网G‘中，无向边(x,y)可理解为：C(x,y)=c(y,x)；c(x,y)≥f(x,y),c(x,y)≥f(y,x)且f(x,y)•f(y,x)=0。求无向网或混合网G’中最大流的一般过程为：1）．先将混合网G’(V,E’,c’,f)中的每条无向边变换成一对有向边(x,y)和(y,x)；且c(x,y)=c(y,x)=c’(x,y)。2）．为了保证混合网G’(V,E’,c’,f)的无向边的流量只在一个方向上流动，即在有向网G(V,E,c,f)中，满足：max[f(x,y)，f(y,x)]=f’(x,y)，且f(x,y)•f(y,x)=0；3）．应用前面介绍的求最大流方法，求有向网G的最大流fmax。4）.应用公式f’(x,y)=max[0,|f(x,y)-f(y,x)|]，构造原网G’可行流型。2.节点—弧限容量网的流求节点-弧限容量网最大流方法：把节点弧容量网G转化为弧限容量网G’，在G’中求出最大流，即是G网的最大流。对每个节点和弧有：;hifi,v,it,i,vE;htft,v,t,vE可行流存在的条件求节点-弧限容量的一般过程：1．在节点-弧限容量网G(V,E,c,f)中的每一节点i,对应仅有弧限的容量网G’(V’,E’,c’,f’)中的两点i’，i’’,其中i’，i’’∈V’；2．G网中的弧(i,j)∈E，则对应G’中的弧(i’,j’’)∈E’；同时，G’网中弧容量为：C’(i’,j’’)=C(i,j);C(i’’,i’)=h(i),i∈V；3．对弧限网G’，用前面介绍的福特-福克森算法求G’网中s’’到t’的最大流fmax，这即是网G的最大流。3.多源多宿最大流问题将Vs与网络内所有源端用容量为∞的有向边相连接；z将Vt与网络内所有宿端用容量为∞的有向边相连接；上2步将多源多宿问题转变为单源单宿问题；如何使用介绍的M算法，求Vs到Vt的最大流量方法也就解决了多源多宿总流量最大的问题。5.3最佳流问题给定网络的结构：G＝（V，E）；边容量Cij；eij为流量，其边费用aij；总流量要求Fst，计算总的Φ＝Σaijcij最小。最佳流的算法，一般使用负价环算法(N算法)：如果网络的源宿端之间有两条以上的径，则源宿之间的可行流在保持总量不变的情况下，总有改变流量分配的可能性，即按照不同的路径分配流量。由于各路径的可行流不同，将使得总经费（或其它参数）最佳。例：图5－6负价环求最佳流的N算法。7,23,25,63,17,4（a）Cij,aij容量和费用VsV1V2V3VtVsV1V2V3Vt6,-21,-21,22,25,-62,11,-11,46,-4（c)补图和负价环VsV1V2V3Vt61516（b）fij可行流（d)降低费用后的可行流VsV1V2V3Vt63336补图：调整网络中路径的可行流，使得网络的运行状况改变。此图对于原图，称为补图。负价环：补图上如果存在一个有向环，环上各边的aij之和是负数，则称此环为负价环。负价环的特性：若网络沿负价环方向增流，并不破坏环上诸端的流量连续性，也不破坏各边的非负性和有限性。结果得到一个Fst不变的可行流，其总费用将有所降低。由此可见，降低任一可行流的总费用，可归结为在该流的补图上寻找负价环。当一个可行流的补图上不存在负价环时，此流就是最佳流或者是最小费用流。若在补图上存在零价环（补图各边之和为0），则在环上增流可得到总费用相同的另外一组可行流。最佳流可以有几种，但是总费用是一样的。负价环算法－N算法N0：在图上找任一满足总流量Fst的可行流；N1：作补图。对所有边eij，若Cijfij，作边e’ij，其容量为Cij－fij，费用为aij；若fij0，再作e’’ij,其容量为C’ij＝fij，费用为－aij。N2：在补图上找负价环。如果无负价环，算法终止；如果有负价环，则沿负价环C方向使各边增流，增流值为：δ＝MinCij；并且修改原图的边流量，得新的可行流，返回N1。负价环算法在选择某一回路时，遵循同一回路最大化的原则。因为在一个回路内，相邻的链路，可以增流，也可以减流，都可以达到改善的效果，我们只需要使得其总的效果最佳即可。即使得效益最大化即可。负价环例2：VsV1V2V3V4Vt6,14,54,61,76,33,16,34,16,34,6（a）V1V2V3V4Vt633654（b）2VsVsV1V2V3