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

張?jiān)淳?東北大學(xué) 王浩棟 宋曉可 山東科技大學(xué) 李藝帆 西安電子科技大學(xué)

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

張?jiān)淳?東北大學(xué) 王浩棟 宋曉可 山東科技大學(xué) 李藝帆 西安電子科技大學(xué)

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

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

1 問題描述

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

2 問題求解

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

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

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

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

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

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

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