多链路负载分担的网络传输时间最小化问题

多链路负载分担的网络传输时间最小化问题

摘要：

本文提出了一个简单的，三条链路负载分担网络的传输时间最小化问题，并通过一系列基本假设和参数设置转换为有约束极值问题，用外点罚函数法求出使传输时间最小的全局最优解。最后对结果进行分析讨论。

所谓多链路负载分担的网络，是指从发送信息的源主机到接收信息的目的主机之间，有两条或两条以上可达的物理链路，这些不同的物理链路往往有着不同的平均传送速率和可靠度，因此在进行负载分担时，需要综合考虑这些因素，经计算得出使传输时间最小的最优解。

本文的这种讨论，仅仅是一种粗糙的理论上的分析，忽略了一些现实问题，比如发送者是如何获知网络拓扑的具体信息、通过什么方法实现流量的负载分担等等。本文的讨论，旨在深化或者说具体化对于最优化算法的理解，以及学习如何使用最优化算法来解决现实问题的方法。

一、 三条链路负载分担网络问题

假设如图所示，从主机甲到主机乙之间有三条可达的物理链路A、B和C，其平均传输速率分别为r1、r2和r3，如果要从甲传送大小为s的信息到乙，则涉及到如何将消息负载分配到三条链路上使传输时间最短的最优化问题。

甲乙A

BC

图1.1 三条链路负载分担网络示例

假设传输速率123r> r>r，三条链路上分担的负载分别为x1、x2和x3。

（1） 当没有其他的约束因素需要考虑时。显然，使得传输时间最短的条件是123123x:x:x=r:r:r，123x+x+x=s。此时传输所需的时间为min112233t=x/r=x/r=x/r。

（2） 现考虑，为了正确的传输信息，每条实际链路上是需要增加大小为a的控制信息。此时使得传输时间最短的条件是123123123(x+a):(x+a):(x+a)=r:r:r,x+x+x=s。传输时间min11t=(x+a)/r。

（3） 如果再考虑到，信息通过链路传输实际上不一定能完全到达，可能因为拥塞或者线路故障或者校验失败而被丢弃，假设用传输能力来表示，三条链路的传输能力分别为p1、p2和p3，i0

（4） 正如在视频图像传输的实际应用中，允许少量马赛克；而在网页浏览中允许少量的乱码那样，现实的通信运用中，不一定严格要求接受方接收到所有发出的信息。考虑负载分担方案的时候，需要在接收方设置限制条件以保障传输质量。现在假设只要收到的信息大小大于sp就认为传输质量符合要求。3ii1(x+a)pisp，iimin{p}

综合以上条件，数学模型如下：

111233ii1112233imin x+a/rs.t. x+x+xs, (x+a)p, i=1,2,3 (x+a)/r=(x+a)/r=(x+a)/r, x0, i=1,2,3isp

二、 外点罚函数法求解有约束极值问题

该数学模型进一步展开并写成外点罚函数法所需要的标准形式得：

11112332ii1121121223113133322323min f(x)=(x+a)/rs.t. g(x)=x+x+xs0, g(x)=(x+a)0, i=1,2,3 (x)=0, (x)=0, (x)=0,ipsphrxrxarrhrxrxarrhrxrxarr

因为内点罚函数适用于只有不等式约束的问题，而该问题同时有不等式约束和等式约束，所以选择用外点罚函数方法。

定义函数(,)()(),FxfxPx其中()Px为

23112222212123()(())(()) max0,()max0,()()()()ijijPxgxhxgxgxhxhxhx

设置参数，并用matlab实现该算法：

设 12312310,6,4,1000,20,0.8,0.9,0.95,0.88rrrsapppp

代入原约束问题得：

111232123112213323min f(x)=(x+20)/10s.t. g(x)=x+x+x10000, g(x)=(x+20)0.8(x+20)0.9(x+20)0.9510000.880 (x)=610201060, (x)=410201040, (x)=46hxxhxxhxx20640,

外点罚函数法计算步骤为：

（1） 给定初始点(0)x，初始罚因子1，放大系数1c，允许误差0，置1k。

（2） 以(1)kx为初点，求解无约束问题min()()kfxPx，设其极小点为()kx。

（3） 若()kPx，则停止计算，得到点()kx；否则，令1kkc，置:1kk，返回步骤（2）。

Matlab实现如下：

% Optimal load-sharing

e=0.001;%Permissible error

c=10;%Magnification factor

a=10;%initial punishment factor

%initializtion

y=[200;200;200];

[fx,p] = func(y,a);

while a*p(y)>=e

[fx,p] = func(y,a);%func is a function of demand for auxiliary

function F (x, a)

y = fminunc(fx,y);%find the minimum of fx

a = a*c;

End

函数func定义如下：

function [fx,p] = func(x,ax)

a = ax;

y = x;

g1 = @(x)x(1)+x(2)+x(3)-1000;

g2 = @(x)0.8*x(1)+0.9*x(2)+0.95*x(3)-827;

h1 = @(x)6*x(1)-10*x(2)+80;

h2 = @(x)4*x(1)-10*x(3)+120;

h3 = @(x)4*x(2)-6*x(3)+40;

if(g1(y)<0)

if(g2(y)<0)

p1 = @(x)g1(x).^2+g2(x).^2;

else

p1 = @(x)g1(x).^2;

end

else

if(g2(y)<0)

p1 = @(x)g2(x).^2;

else

p1 = @(x)0;

end

end

p = @(x)p1(x)+h1(x).^2+h2(x).^2+h3(x).^2;

fx = @(x)0.1*x(1)+2+a*p(x);

return;

三、 结果分析

以下给出几种不同的参数设置下的程序运行结果。并对其不同之处进行分析：

（1） 当给定初始点(0)200200200Tx，初始罚因子110，放大系数10c，允许误差0.001。得到的结果为()=489.9998301.9999207.9999Tkx。由于精度的问题，得到的结果三条链路上负载相加等于999.9996，并不是完全的达到了大于等于1000。

（2） 当给定初始点(0)300300300Tx，其余参数不变时，可以得到相同的结果。 （3） 当给定初始点(0)400400400Tx，其余参数不变时，得到的将会是错误的结果：()=519.9999320.0000220.0000Tkx，这也验证了外点罚函数法是从可行域外部趋向于最优解的。

（4） 当给定初始点(0)200200200Tx，初始罚因子110，放大系数10c，允许误差0.0001。因为减小了允许误差，导致a*p(y)>=e的条件永远为真，程序陷入死循环。这是本程序需要进一步改进的地方。

（5） 当给定初始点(0)200200200Tx，初始罚因子1100，放大系数10c，允许误差0.001。得到的结果为()=489.9999301.9999208.0000Tkx，三条链路上负载相加等于999.9998，也就是，增大了初始罚因子相应增加了程序的精度，使得计算结果更加接近罚因子趋于无穷时得到的最优解。这个结果也和算法的理论分析结论相吻合。