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

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

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

3、0）（3）基本模型：認(rèn)為需要傳輸?shù)奈募诵?。由以上列出的假設(shè)和條件，可以得到方程 組：仏=01_ n工-S(wH)1n 工久Z=1目標(biāo)函數(shù)：fX） = niinJ<一一即所有下我者花費的總時間最少。 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該問題為一個非線性規(guī)劃問題（目標(biāo)函數(shù)為非線性.約束條件均為線性） 分析如下：整個網(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來定義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）；說明：fbn為目標(biāo)函數(shù)名。A.b.Aeq.beq為線性約束。VLB,VUB為X的I:卜限。nonIcon 為非線性約束函數(shù)名。options為參數(shù)說明。P1.P2,為目標(biāo)函數(shù)文件利非線性 約束函數(shù)文件中的可變參數(shù)。ex

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