数学建模案例多点对多点的网络传输优化问题

1、多点对多点的网络传输优化问题问题的提出：针对internet上网络之间文件互传出现的新形式（主耍研% bittoiTent这款 软件），即多点对多点的传输。进行研究。建模的目的：通过数学方法，找到与该敲优化问题相关的参量，控制文件的传输分配， 得到最优化方案。相关背景：Bittoirent是近年刚刚兴起的一款多点对多点的卜墩软件。卜墩时需要种子 一一即那些只向别人发送文件流而不接收文件流的计算机，和下载者一一 即在接收文件流的同时也向其他计算机发送文件流。模型的建立：（1）基本假设：a网络传输的瓶颈在于每台电脑前端网线限制速率（这一般由网络运营商 限定）。b网络上文件流的传输是以光速进行的，可

2、以即时发出即时接收，而且接 收的文件可即时复制任意份传送给其他电脑，不用考虑时间间隔。c.任意两台电脑之间都可进行传输。d从某一时刻起，所有下我者和种子同时开始传输。到所令下我者中的放 后一个完成传输时止，中途没有任一下载者和种子离开，也没有其他下 载者和种子加入。（2）变量的定义:a记m个种子为召宀，"力，n-m个下我者为川”皿”曲b种子和下载者的限制速率分别为勺,勺,，张卫”曲Q”.c两台电脑之间的传输速率为 号。（对于种子，由于只发送文件流而不接 收文件流，则xv = 0>b/g1-z）d对于每个下载者，其完成一个文件的接收时间为（对于种子，其完成时间为4 =右=-=：=

3、0）（3）基本模型：认为需要传输的文件人小为1。由以上列出的假设和条件，可以得到方程 组：仏=01_ n工-S(wH)1n 工久Z=1目标函数：fX） = niinJ<一一即所有下我者花费的总时间最少。 7=1约束条件:r=lz1F=1Z=1OAX<B2nn工 + 2 "却) r=lr=l发送接收1 .mm+1 .n1 mm+1.n1<0- 01 10. o0 -0m0- 01 10 o0 -0A =刃+10- 001000 -1n0- 01 00 01 0该问题为一个非线性规划问题（目标函数为非线性.约束条件均为线性） 分析如下：整个网络的传输矩阵：1 mm+1n

4、1(-rll丙”,人l(wH)、mX”力+1Y(w+i)lnr耳（却）a9tn 7,即其中左边 "1 上面的矩阵可以分为为零矩阵。我们通过资料查阅，发现非线性规划问题可以用以下几种方法解：（1）罚函数法。（2）序列线性规划法。（3）序列二次规划法。（4）信赖域算法 而Matlab提供的非线性规划问题的算法中，中型算法采用了序列：次规划法，而大型 算法釆用信赖域算法。下而给出用Matlab解该问题的程序步骤：（1）建立M文件fbn m,定义目标两数f（X）：function f=fun（x）,f=f（x）,retiun：（2）若约束条件中有非线性约束g（才）0 则建立M文件nonlco

5、nm来定义g（才）0 :function g=nonlcon（x）,汽（X）,return：（由于该问题的约束条件不包括非线性条件，则不用定义）G）建立主程序.非线性规划求解的苗数是finmcon,命令的基本格式如卜:x,fval,exitflag,outputlninconC fun1,A,b,Aeq,beq,VLB,VUB/nonlcon* ,options,P 1,P2）；说明：fbn为目标函数名。A.b.Aeq.beq为线性约束。VLB,VUB为X的I:卜限。nonIcon 为非线性约束函数名。options为参数说明。P1.P2,为目标函数文件利非线性 约束函数文件中的可变参数。ex

6、itflag为返回标志，非正时可能不是可行解。fmincon函数口I能会给出局部绘优解，这与初值禺的选取有关。下而对具体的情况进行计算：有2个种子，5个下载者，有10000k大小的文件.限制速率为:'750初/少、1000妙/，800 初/，*4=1200M/$1600/力/$“61200/s3 800初/£,则该问题为:= min-一+ + + -一+- z=lr=lz=lr=lz=lst AX <try<00111110000000）"0.075、001111100000000.100000111100011110.080其中：/ =00101110

7、010111,b =0.120001101100110110.160001110100111010.1201°0111100011110丿(0.080丿为简单起见假设卜载者在右限的宽度内卜墩的速率与上传的速率相等，解得ri3"14-ri5"16-ri7P.015 0.015 0.015 0.015 0.015、r23”24“25-r26“270.020 0.020 0.020 0.020 0.020才33码4才35"箔才370.010 0.010 0.010 0.010 0.010解得:r43“44“45”46才470.014 0.014 0.014 0

8、.014 0.014丫53 巧4 乌5 *r56570.020 0.020 0.020 0.020 0.020r63“64“65X66-T670.014 0.014 0.014 0.014 0.014<-r73-T74“75-r76丫77 丿,0.010 0.010 0.010 0.010 0.010,血二 68s结果分析：1. 平均每个下我者下戦数据所需时间为9.7如果不用该软件，就以两个种子作为下载源，以同样的条件，总共需要200s,平均28s。由此可见，该软件大大降低了下载的速率2. 从结采可得，在上述理想条件下，应使种子和下栽者分传给每个下戦者以等量的数 据，从而可使下载时间人犬减小。3. 显而易见，下栽时种子越多，总的下我所需时间越少。这个实例之所以结果非常简单，是因为有了一个重要的假设，就是假设下我者卜墩的速率与上传的速率一样。更般的模型1. 实际的速率限制不是一个定值，而