張源境 東北大學(xué) 王浩棟 宋曉可 山東科技大學(xué) 李藝帆 西安電子科技大學(xué)

基于網(wǎng)絡(luò)優(yōu)化的云數(shù)據(jù)傳輸?shù)淖畲笫找鎲栴}

張源境 東北大學(xué) 王浩棟 宋曉可 山東科技大學(xué) 李藝帆 西安電子科技大學(xué)

云數(shù)據(jù)傳輸問題是研究文件的傳輸順序，使傳輸總時間最短的問題，屬于“時間表問題”的一種。而時間表問題屬于離散最優(yōu)化領(lǐng)域。我們構(gòu)造頂點矩陣a，得到飽和頂點并傳輸其最大邊，對最大權(quán)匹配思想進行變異，得出所有頂點的最短傳輸時間，其中的最大值即為問題的最優(yōu)解。部分節(jié)點的傳輸能力變?yōu)榇笥?的值，所以可將這部分節(jié)點的最大值與次大值同時傳輸，以保證結(jié)果最優(yōu)。由于虛擬機內(nèi)存容量以及虛擬機遷移的影響，使問題變得復(fù)雜，不能簡單地通過求飽和點的方法來求解。

網(wǎng)絡(luò)優(yōu)化問題 飽和點 最大邊

1 問題描述

已知所有機器之間的聯(lián)系情況，有聯(lián)系的計算機之間傳輸文件的時間，可以將實際問題抽象為一個對稱矩陣a，行數(shù)和列數(shù)表示對應(yīng)的節(jié)點Vy的值，對應(yīng)元素a（i，j）即為文件從計算機i到計算機j（計算機j到計算機i）之間的傳輸時間。將同時與三臺其他計算機相聯(lián)系的計算機抽象為飽和點，連接兩個飽和點的邊抽象為飽和邊。易知，只要求解出所有點傳輸完成所有邊的總時間，再比較出各個點傳輸完邊所用的時間，就可以確定完成所有過程所需的總時間。只要對這一求解過程進行優(yōu)化，避免不必要的等待和錯誤的傳輸順序，就可以得到最短的傳輸時間。由于飽和點和飽和邊處的復(fù)雜程度在圖形中占主要位置，并且飽和點所連的邊數(shù)大于非飽和點所連的邊數(shù)，且可以保證在大多數(shù)情況下飽和點的相連的三條邊的總傳輸時間大于非飽和點的總傳輸時間，故只需考慮飽和點的傳輸總時間即可。將部分飽和點的傳輸能力改變?yōu)?或者3，并且一部分?jǐn)?shù)據(jù)變?yōu)槲粗?。先將所有頂點的傳輸能力均視為1，即為第一步中得到的解法。之后篩選出實際傳輸能力不為1的頂點，對這部分頂點的傳輸時間進一步壓縮優(yōu)化，即可得到傳輸問題的最短時間。對于未知量N的問題，可以從“已知到未知求解”的角度出發(fā)，先用已知值替換，之后改變該替換值，從中發(fā)現(xiàn)替換規(guī)律，得到最優(yōu)解以及N值的影響。

2 問題求解

Step1：求解飽和頂點；Step2：對飽和頂點的相關(guān)邊比較，尋找飽和頂點之間相連的最大邊；Step3：最大邊傳輸完成；繼續(xù)進行比較算法，求出飽和頂點的實際次大邊和最小邊；Step4：循環(huán)計算，依次得到所有飽和頂點的傳輸時間；飽和頂點傳輸完成，循環(huán)結(jié)束。

當(dāng)頂點的傳輸能力變化時，真正對傳輸時間產(chǎn)生影響的只有飽和頂點?？梢韵葘⑺许旤c傳輸能力全部看做1，通過上述方法求解出三條邊傳輸過程中的實際傳輸時間。此時需要注意，對于傳輸能力為2的點，其次大邊的傳輸可以與最大邊同時進行以得到傳輸最短時間；對于傳輸能力為3的點，可以使3條邊的傳輸同時進行以保證傳輸時間。

Step1：求解飽和頂點；Step2：對飽和頂點的相關(guān)邊比較，尋找飽和頂點最大邊；Step3：求解傳輸能力為2的點，讓這類點在可能的情況下傳輸剩下的邊；Step4：求解傳輸能力為3的點，讓這類點在可能的情況下傳輸與之相鄰的所有邊；Step5：傳輸剩下的所有邊；Step6：計算傳輸時間。于未知量N的求解，最直觀的辦法是對N進行賦值，在合理區(qū)間內(nèi)為N賦值，通過改變N，觀察結(jié)果中產(chǎn)生的影響。

如果該服務(wù)器為不可靠類，則交換機需時刻準(zhǔn)備將請求轉(zhuǎn)移至傳輸完成的出錯率最低的較可靠類機器。傳輸消耗的時間由所給無向圖決定。當(dāng)傳輸尚未完成而又有新的可靠度高于原轉(zhuǎn)移目標(biāo)的服務(wù)器空閑，且道路中的服務(wù)器尚未被占用時，交換機根據(jù)期望值的大小決定轉(zhuǎn)移是否至新的可靠服務(wù)器。顯然，即便在高故障率的服務(wù)器上，當(dāng)任務(wù)快要完成時在選擇遷移是不劃算的。

[1]圖論（第四版）---[德]Reinhard Diestel著，北京，高等教育出版社

[2]基于云計算的網(wǎng)絡(luò)操作系統(tǒng)中虛擬機動態(tài)遷移的研究與實現(xiàn)---鄒超，陸月明

第一作者：張源境（1997—），女，漢族，遼寧省沈陽市，本科生，東北大學(xué)，研究方向為云計算與大數(shù)據(jù)。第二作者：王浩棟（1997—），男，漢族，山東省威海市。大學(xué)本科在校生，山東科技大學(xué)礦業(yè)與安全工程學(xué)院采礦工程16級，研究方向為采礦工程。第三作者：宋曉可（1996—），女，漢族，山東省聊城市。本科，山東科技大學(xué)數(shù)學(xué)與系統(tǒng)科學(xué)學(xué)院統(tǒng)計學(xué)2014級，研究方向為統(tǒng)計學(xué)。李藝帆（1996—），性別：女，民族：漢，籍貫：陜西西安。職務(wù)/職稱：無，學(xué)歷：大學(xué)本科，單位：西安電子科技大學(xué)，研究方向：云計算。