《数学建模案例多点对多点的网络传输优化问题》由会员分享，可在线阅读，更多相关《数学建模案例多点对多点的网络传输优化问题（5页珍藏版）》请在金锄头文库上搜索。
1、1多点对多点的网络传输优化问题问题的提出：针对 internet 上网络之间文件互传出现的新形式（主要研究 bittorrent 这款软件） ，即多点对多点的传输。进行研究。建模的目的：通过数学方法，找到与该最优化问题相关的参量，控制文件的传输分配，得到最优化方案。相关背景：Bittorrent 是近年刚刚兴起的一款多点对多点的下载软件。下载时需要种子即那些只向别人发送文件流而不接收文件流的计算机， 和下载者 即在接收文件流的同时也向其他计算机发送文件流。模型的建立：（1）基本假设： a.网络传输的瓶颈在于每台电脑前端网线限制速率（这一般由网络运营商 限定） 。 b.网络上文件流的传输是以光速
2、进行的，可以即时发出即时接收，而且接 收的文件可即时复制任意份传送给其他电脑，不用考虑时间间隔。 c.任意两台电脑之间都可进行传输。 d.从某一时刻起，所有下载者和种子同时开始传输。到所有下载者中的最 后一个完成传输时止，中途没有任一下载者和种子离开，也没有其他下 载者和种子加入。 （2）变量的定义：2a.记 m 个种子为12,mn nn，n-m 个下载者为12mmnnnn+。b.种子和下载者的限制速率分别为1212,mmmna aaaaa+.c.两台电脑之间的传输速率为ijx。(对于种子，由于只发送文件流而不接收文件流，则0,1ijxjm= )d.对于每个下载者，其完成一个文件的接收时间为1
3、2,mmnttt+。 （对于种子，其完成时间为120mttt=）（3）基本模型： 认为需要传输的文件大小为 1。由以上列出的假设和条件，可以得到方程 组：11(1) 110011mmni m innin ittt xt x+ = = = = 目标函数：1()minni if Xt=即所有下载者花费的总时间最少。约束条件：.111 1111(1)(1)1 1111nnii iinnmiimm iinnmii mm iinnniinn iixxaxxaxxaxxa=+ =+ + + + AXB0, ,ijxi jn3接收发送1mm+1 n1.mm+1 n 10011000000110000 1 0
4、001000100100010mAmn =+ 该问题为一个非线性规划问题.(目标函数为非线性，约束条件均为线性) 分析如下：整个网络的传输矩阵：1mm+1n11m mn+1111(1)11(1)1(1)1(1)mmnmmnmmnnnmn mnxxxxxx xxxxxa+ 上面的矩阵可以分为0 0A B ，即其中左边1111mnnmxxxx 为零矩阵。我们通过资料查阅，发现非线性规划问题可以用以下几种方法解： （1）罚函数法。 （2）序列线性规划法。 （3）序列二次规划法。 （4）信赖域算法 而 Matlab 提供的非线性规划问题的算法中，中型算法采用了序列二次规划法，而大型 算法采用信赖域算法
5、。 下面给出用 Matlab 解该问题的程序步骤： （1）建立.M 文件 fun .m，定义目标函数 f(X)： function f=fun(x); f=f(x); return；（2）若约束条件中有非线性约束()0g X,则建立 M 文件 nonlcon.m 来定义()0g X：function g=nonlcon(x); g=g(x); return； (由于该问题的约束条件不包括非线性条件，则不用定义）4(3)建立主程序，非线性规划求解的函数是 fmincon,命令的基本格式如下：x,fval,exitflag,output=fmincon(fun,0X,A,b,Aeq,beq,VLB
6、,VUB,nonlcon,options,P1,P2,); 说明：fun 为目标函数名。A,b,Aeq,beq 为线性约束。VLB,VUB 为 X 的上下限。nonlcon 为非线性约束函数名。options 为参数说明。P1, P2,为目标函数文件和非线性 约束函数文件中的可变参数。exitflag 为返回标志，非正时可能不是可行解。fmincon 函数可能会给出局部最优解，这与初值0X的选取有关。下面对具体的情况进行计算： 有 2 个种子，5 个下载者，有 10000k 大小的文件，限制速率为：1234567750/1000/ 800/1200/ 1600/1200/ 800/akbs a
7、kbsakbs akbsakbs akbsakbs = 则该问题为：7777734567 1111111111()miniiiii iiiiif X xxxxx=+ s.t;AXb0, ,ijxi jn其中：00111110000000 00111110000000 00011110001111 00101110010111 00110110011011 00111010011101 00111100011110A = ，0.075 0.100 0.080 0.120 0.160 0.120 0.080b = 为简单起见,假设下载者在有限的宽度内下载的速率与上传的速率相等，解得5解得:1314
8、151617232425262733343536374344454647535455565763646566677374757677xxxxx xxxxx xxxxx xxxxx xxxxx xxxxxxxxxx =0.0150.0150.0150.0150.015 0.0200.0200.0200.0200.020 0.0100.0100.0100.0100.010 0.0140.0140.0140.0140.014 0.0200.0200.0200.0200.020 0.0140.0140.0140.0140.014 0.0100.0100.0100.0100.010 min68fs=结果
9、分析：1平均每个下载者下载数据所需时间为9.7s，如果不用该软件，就以两个种子作为下载源，以同样的条件，总共需要 200s，平均 28s。由此可见，该软件大大降低了下载的速率 2从结果可得，在上述理想条件下，应使种子和下载者分传给每个下载者以等量的数据，从而可使下载时间大大减小。3显而易见，下载时种子越多，总的下载所需时间越少。这个实例之所以结果非常简单，是因为有了一个重要的假设，就是假设下载者下载的速率与上传的速率一样。更一般的模型1实际的速率限制不是一个定值，而是关于时间的一个函数；2在 t 时刻还有新的种子加入，或者有下载者下载完成后退出；对于这种复杂的情况，我们一直都没有编出相关的程序，由于时间有限，我们就没有做深一步的研究。第五十一组：雷鸣 3021132052 王军 3021132077 李邺 3023001157
