數(shù)學(xué)建模案例多點(diǎn)對(duì)多點(diǎn)的網(wǎng)絡(luò)傳輸優(yōu)化問題

1、多點(diǎn)對(duì)多點(diǎn)的網(wǎng)絡(luò)傳輸優(yōu)化問題問題的提出：針對(duì)internet上網(wǎng)絡(luò)之間文件互傳出現(xiàn)的新形式（主耍研% bittoiTent這款 軟件），即多點(diǎn)對(duì)多點(diǎn)的傳輸。進(jìn)行研究。建模的目的：通過數(shù)學(xué)方法，找到與該敲優(yōu)化問題相關(guān)的參量，控制文件的傳輸分配， 得到最優(yōu)化方案。相關(guān)背景：Bittoirent是近年剛剛興起的一款多點(diǎn)對(duì)多點(diǎn)的卜墩軟件。卜墩時(shí)需要種子 一一即那些只向別人發(fā)送文件流而不接收文件流的計(jì)算機(jī)，和下載者一一 即在接收文件流的同時(shí)也向其他計(jì)算機(jī)發(fā)送文件流。模型的建立：（1）基本假設(shè)：a網(wǎng)絡(luò)傳輸?shù)钠款i在于每臺(tái)電腦前端網(wǎng)線限制速率（這一般由網(wǎng)絡(luò)運(yùn)營(yíng)商 限定）。b網(wǎng)絡(luò)上文件流的傳輸是以光速進(jìn)行的，可

2、以即時(shí)發(fā)出即時(shí)接收，而且接 收的文件可即時(shí)復(fù)制任意份傳送給其他電腦，不用考慮時(shí)間間隔。c.任意兩臺(tái)電腦之間都可進(jìn)行傳輸。d從某一時(shí)刻起，所有下我者和種子同時(shí)開始傳輸。到所令下我者中的放 后一個(gè)完成傳輸時(shí)止，中途沒有任一下載者和種子離開，也沒有其他下 載者和種子加入。（2）變量的定義:a記m個(gè)種子為召宀，"力，n-m個(gè)下我者為川”皿”曲b種子和下載者的限制速率分別為勺,勺,，張衛(wèi)”曲Q”.c兩臺(tái)電腦之間的傳輸速率為 號(hào)。（對(duì)于種子，由于只發(fā)送文件流而不接 收文件流，則xv = 0>b/g1-z）d對(duì)于每個(gè)下載者，其完成一個(gè)文件的接收時(shí)間為（對(duì)于種子，其完成時(shí)間為4 =右=-=：=

3、0）（3）基本模型：認(rèn)為需要傳輸?shù)奈募诵?。由以上列出的假設(shè)和條件，可以得到方程 組：仏=01_ n工-S(wH)1n 工久Z=1目標(biāo)函數(shù)：fX） = niinJ<一一即所有下我者花費(fèi)的總時(shí)間最少。 7=1約束條件:r=lz1F=1Z=1OAX<B2nn工 + 2 "卻) r=lr=l發(fā)送接收1 .mm+1 .n1 mm+1.n1<0- 01 10. o0 -0m0- 01 10 o0 -0A =刃+10- 001000 -1n0- 01 00 01 0該問題為一個(gè)非線性規(guī)劃問題（目標(biāo)函數(shù)為非線性.約束條件均為線性） 分析如下：整個(gè)網(wǎng)絡(luò)的傳輸矩陣：1 mm+1n

4、1(-rll丙”,人l(wH)、mX”力+1Y(w+i)lnr耳（卻）a9tn 7,即其中左邊 "1 上面的矩陣可以分為為零矩陣。我們通過資料查閱，發(fā)現(xiàn)非線性規(guī)劃問題可以用以下幾種方法解：（1）罰函數(shù)法。（2）序列線性規(guī)劃法。（3）序列二次規(guī)劃法。（4）信賴域算法 而Matlab提供的非線性規(guī)劃問題的算法中，中型算法采用了序列：次規(guī)劃法，而大型 算法釆用信賴域算法。下而給出用Matlab解該問題的程序步驟：（1）建立M文件fbn m,定義目標(biāo)兩數(shù)f（X）：function f=fun（x）,f=f（x）,retiun：（2）若約束條件中有非線性約束g（才）0 則建立M文件nonlco

5、nm來(lái)定義g（才）0 :function g=nonlcon（x）,汽（X）,return：（由于該問題的約束條件不包括非線性條件，則不用定義）G）建立主程序.非線性規(guī)劃求解的苗數(shù)是finmcon,命令的基本格式如卜:x,fval,exitflag,outputlninconC fun1,A,b,Aeq,beq,VLB,VUB/nonlcon* ,options,P 1,P2）；說(shuō)明：fbn為目標(biāo)函數(shù)名。A.b.Aeq.beq為線性約束。VLB,VUB為X的I:卜限。nonIcon 為非線性約束函數(shù)名。options為參數(shù)說(shuō)明。P1.P2,為目標(biāo)函數(shù)文件利非線性 約束函數(shù)文件中的可變參數(shù)。ex

6、itflag為返回標(biāo)志，非正時(shí)可能不是可行解。fmincon函數(shù)口I能會(huì)給出局部繪優(yōu)解，這與初值禺的選取有關(guān)。下而對(duì)具體的情況進(jìn)行計(jì)算：有2個(gè)種子，5個(gè)下載者，有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丿為簡(jiǎn)單起見假設(shè)卜載者在右限的寬度內(nèi)卜墩的速率與上傳的速率相等，解得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結(jié)果分析：1. 平均每個(gè)下我者下戦數(shù)據(jù)所需時(shí)間為9.7如果不用該軟件，就以兩個(gè)種子作為下載源，以同樣的條件，總共需要200s,平均28s。由此可見，該軟件大大降低了下載的速率2. 從結(jié)采可得，在上述理想條件下，應(yīng)使種子和下栽者分傳給每個(gè)下戦者以等量的數(shù) 據(jù)，從而可使下載時(shí)間人犬減小。3. 顯而易見，下栽時(shí)種子越多，總的下我所需時(shí)間越少。這個(gè)實(shí)例之所以結(jié)果非常簡(jiǎn)單，是因?yàn)橛辛艘粋€(gè)重要的假設(shè)，就是假設(shè)下我者卜墩的速率與上傳的速率一樣。更般的模型1. 實(shí)際的速率限制不是一個(gè)定值，而