基于弗洛伊得算法的云端文件存儲(chǔ)負(fù)載平衡算法研究

陳 園，劉軍華，雷超陽(yáng)

（湖南郵電職業(yè)技術(shù)學(xué)院 互聯(lián)網(wǎng)工程系，湖南 長(zhǎng)沙 410015）

基于弗洛伊得算法的云端文件存儲(chǔ)負(fù)載平衡算法研究

陳 園，劉軍華，雷超陽(yáng)

（湖南郵電職業(yè)技術(shù)學(xué)院 互聯(lián)網(wǎng)工程系，湖南 長(zhǎng)沙 410015）

文章提出了基于弗洛伊得算法的云端文件儲(chǔ)存負(fù)載平衡算法，依據(jù)客戶端對(duì)文件的存取頻率與文件大小，綜合最短網(wǎng)絡(luò)距離的計(jì)算來優(yōu)選文件存放位置,且依據(jù)所有客戶端與所有服務(wù)節(jié)點(diǎn)間的跳躍計(jì)數(shù)與網(wǎng)絡(luò)頻寬視作其網(wǎng)絡(luò)距離。仿真實(shí)驗(yàn)表明:本文研究方法其文件平均存取成本較隨機(jī)與輪轉(zhuǎn)兩種方法明顯要低，對(duì)所有使用者公平存放文件位置，讓使用者能以最少的跳轉(zhuǎn)次數(shù)或最佳的頻寬路徑進(jìn)行存取，提升了客戶端文件存取效率。且當(dāng)多數(shù)叢集空間滿載時(shí)本研究方法仍可計(jì)算出較佳的存放位置。

弗洛伊得算法；云端文件；負(fù)載平衡；算法

0 引言

隨著云計(jì)算相關(guān)技術(shù)的普及以及用云技術(shù)應(yīng)用的越來越廣泛，如將不同云文件合理存放于不同云服務(wù)器，以滿足大量用戶快速存取、高吞吐量及大儲(chǔ)存空間需求。因而，怎樣合理安排文件的云存放位置，使客戶端獲取時(shí)響應(yīng)時(shí)間較短非常重要。通常的思路是每隔一段時(shí)間周期性的收集云端系統(tǒng)內(nèi)文件的存取需求作為負(fù)載平衡的依據(jù)，依此分析當(dāng)前時(shí)間段文件的合適存放位置，即通過周期性的收集與分析云系統(tǒng)信息使近階段文件的存放位置接近最佳化[1-5]。而判斷文件存放的位置考慮因素既可以是存放在較空閑服務(wù)器來降低客戶端的等待時(shí)間，也可以是存放在距離客戶端較近的位置來降低傳輸成本[6-8]。

本文提出的弗洛伊得算法的云端文件存儲(chǔ)負(fù)載平衡算法，以弗洛伊得算法計(jì)算出客戶端至所有服務(wù)節(jié)點(diǎn)的最短網(wǎng)絡(luò)路徑，同時(shí)考慮不同客戶端對(duì)同文件存取需求，不只將文件存放在離單一客戶端最近位置，即不同客戶端存取文件次數(shù)及大小也是考慮要素。對(duì)于較大文件即使被存取次數(shù)較少，也要考慮將其存放在較近位置，以避免存取該文件的客戶端因傳輸所需文件而造成較大延遲。而對(duì)于存取次數(shù)較多但較小文件，即使存放在離其較遠(yuǎn)位置也不至于造成太大延遲。且當(dāng)計(jì)算出適合存放的服務(wù)節(jié)點(diǎn)滿載時(shí)，通過設(shè)計(jì)好的滿載文件遷移規(guī)則，使服務(wù)節(jié)點(diǎn)中的文件遷移調(diào)整后對(duì)客戶端造成的影響最低。

1 弗洛伊得算法思路

弗洛伊得算法（Floyd）是一種在有向加權(quán)圓中尋找任意兩點(diǎn)間最短路徑的算法[9-12]。其思路是如果一個(gè)問題存在最佳解則其子問題必有最佳解，將有向加權(quán)圓中的任意兩點(diǎn)間所有可經(jīng)過點(diǎn)間最短距離作為子問題，先分別解出各子問題最佳解，最后將子問題解進(jìn)行最佳組合從而得到問題的最佳解。其算法描述為：設(shè)Di,j,k為某圖從點(diǎn)i到點(diǎn)j經(jīng)由（1~k）集合點(diǎn)為中間節(jié)點(diǎn)的路徑長(zhǎng)度為子問題，則子問題可分兩種情況。

（1）經(jīng)過中間k節(jié)點(diǎn)的路徑距離Di,j,k=Di,k,k-1+

（2）不經(jīng)過中間k節(jié)點(diǎn)的路徑距離Di,j,k=Di,j,k-1

這樣子問題最短路徑變?yōu)椋篋i,j,k= min（Di,k,k-1+Dk,j,k-1, Di,j,k-1），即取經(jīng)過中間k節(jié)點(diǎn)路徑距離與不經(jīng)過中間k節(jié)點(diǎn)路徑距離（即直接相連節(jié)點(diǎn)）兩者的較小值。若經(jīng)過中間節(jié)點(diǎn)距離較短，則以此距離取代原本兩點(diǎn)直連的距離，依此不斷的比較與取代將加權(quán)圓中任意兩節(jié)點(diǎn)間的最短路徑距離計(jì)算出來。

2 網(wǎng)絡(luò)距離計(jì)算

網(wǎng)絡(luò)距離通常是計(jì)算云端文件儲(chǔ)存位置的主要評(píng)估要素，其計(jì)算方式是以客戶端入口點(diǎn)與文件服務(wù)器叢集之間的跳躍計(jì)數(shù)及頻寬來計(jì)算，如圖1所示。

圖1 服務(wù)器叢集與入口點(diǎn)連線頻寬示意圖Fig.1 Bandwidth map of the server cluster and the entry point

圖1中沒帶箭頭線段上的數(shù)字表示叢集間的頻寬，帶箭頭線段上的數(shù)字表示入口點(diǎn)到直連叢集間的頻寬，入口點(diǎn)到叢集為有向，叢集間為無向且互相連通，但不一定直連。取頻寬的倒數(shù)來表示叢集間的相連傳輸延遲（即時(shí)間距離），頻寬數(shù)值與時(shí)間距離成反比，以下公式1為點(diǎn)x到點(diǎn)y的時(shí)間距離計(jì)算方法。

由圖1計(jì)算出的時(shí)間距離結(jié)果如表1所示。

表1 服務(wù)器叢集直接相連網(wǎng)絡(luò)距離表Tab.1 Network distance table of server cluster directly connected

可知有些叢集間無直接連接，需經(jīng)其他叢集轉(zhuǎn)連，此轉(zhuǎn)連所經(jīng)過的叢集數(shù)即為跳躍計(jì)數(shù)。此跳躍路徑不一定為唯一路徑，有時(shí)直連的距離較近，有時(shí)經(jīng)由別的叢集路徑較近，且選擇頻寬總和最小跳躍路徑，這時(shí)需根據(jù)弗洛伊得算法尋找任意兩點(diǎn)最短路徑的特性，以叢集為點(diǎn)計(jì)算出任意兩點(diǎn)的最短路徑，計(jì)算結(jié)果為兩點(diǎn)間跳躍計(jì)數(shù)的時(shí)間距離綜合。最短距離計(jì)算方法如公式（2）。

公式2中j為兩點(diǎn)間可經(jīng)過的點(diǎn)集合。將頻寬倒數(shù)的時(shí)間距離計(jì)算方法套用到弗洛伊得算法中，最短距離為直接相連時(shí)間距離與有經(jīng)由中間點(diǎn)時(shí)間距離的較小值。表1加上入口時(shí)間距離后通過公式2計(jì)算的結(jié)果如表2所示。

表2 弗洛伊得算法計(jì)算網(wǎng)絡(luò)距離表Tab.2 Floyd algorithm to compute the network distance table

由表 2可知，入口點(diǎn) P1與叢集 SA、SB的連接速度較快，而入口點(diǎn) P2與叢集 SC、SD的連接速度較快。但當(dāng)需確定文件存放至哪個(gè)叢集時(shí)不能僅以連接速度來評(píng)估，因如果有兩個(gè)入口點(diǎn)都要存取同一文件，如將文件存放在離入口點(diǎn)P1較近叢集SB，則會(huì)對(duì)入口點(diǎn)P2造成較遠(yuǎn)網(wǎng)絡(luò)距離存取。所以需考慮多方面因素來計(jì)算每個(gè)入口點(diǎn)的存取成本，以便將文件存放在更合適的叢集。

3 文件存取成本計(jì)算

文件存取成本的計(jì)算需針對(duì)單獨(dú)文件分別計(jì)算，考慮的要素有距離、各入口點(diǎn)文件存取次數(shù)及文件大小。通過計(jì)算各入口點(diǎn)對(duì)某文件的需求量，從而分別計(jì)算出每個(gè)叢集存放此文件對(duì)所有入口點(diǎn)造成的影響。

以下以文件f的存取成本來說明其計(jì)算步驟。

（1）先分別計(jì)算每入口點(diǎn)對(duì)文件f的存取需求量 ATp,f×FSf；

（2）再乘以該入口點(diǎn)至叢集距離 ATp,f×FSf×Dp,S；

此計(jì)算結(jié)果為單一入口點(diǎn)由叢集 S存取文件 f所需成本，將所有入口點(diǎn)的存取成本求和得TACs,f，求和計(jì)算公式3如下。

TACS,f表示所有入口點(diǎn) p從叢集 S存取文件 f的成本總和。公式（3）中各代號(hào)含義如下：

P：入口點(diǎn)（Portal），p=1…n

S：服務(wù)器叢集（Server Cluster），S=1…m

ATp,f：文件 f從入口點(diǎn) p的存取次數(shù)（Access Times）

FSf：文件f的大?。‵ile Size）

Dp,s：入口點(diǎn)p到叢集s的距離

TACs,f：所有入口點(diǎn)由存取叢集s中文件f的總存取成本

將此公式代入不同叢集 s的距離，就能計(jì)算出文件f存放到不同叢集對(duì)應(yīng)的TACs,f值，TACs,f值越小表示文件f越適合存放于叢集s。計(jì)算TACs,f值目的在于得到存取需求量與各入口點(diǎn)跟叢集的距離關(guān)系，計(jì)算存取文件所需成本，依照各入口點(diǎn)存取成本來比較，使每個(gè)入口點(diǎn)公平，避免只針對(duì)單一存取成本較低的入口點(diǎn)文件來決定最佳存放位置。即使每個(gè)文件都計(jì)算出最小 TACs,f值決定文件的存放叢集，仍可能出現(xiàn)多個(gè)文件存放于同一叢集情況，而叢集空間有限，這就涉及到將部分文件遷移到其他服務(wù)器的處理。

4 文件存放策略

本文所研究的文件存放策略是讓每個(gè)叢集分別對(duì)所有文件中進(jìn)行挑選。其挑選方式為：選出所有存放于某叢集時(shí)存取成本最低的文件。如果叢集挑選的文件大小總和超出了其儲(chǔ)存空間，則從所有存放于該叢集的文件中選出一個(gè)移至別的服務(wù)器，直到空間足夠。本算法的中止條件為所有文件都確定存放的叢集不再變動(dòng)。由存取成本計(jì)算后可得到每個(gè)文件在不同叢集的存取成本，假設(shè)為TAC，并將TAC數(shù)值以矩陣編排，如表3案例所示，其中橫排表示叢集編號(hào)，縱排表示文件編號(hào)，中間數(shù)值表示如文件存放在此叢集時(shí)的TAC值。

表3 文件存放成本矩陣案例Tab.3 Study of file storage cost matrix

接著先將TAC矩陣轉(zhuǎn)換成相對(duì)成本矩陣，因每個(gè)文件的TAC值都是針對(duì)個(gè)別情況計(jì)算出來的，文件間的TAC值無法相互比較，所以叢集無法以TAC值確定哪個(gè)文件更適合保留。這時(shí)只能根據(jù)文件被移至別的叢集時(shí)分別增加了多少TAC值，即相對(duì)成本，相對(duì)成本計(jì)算程序如下：

Compute-relative-cost（）

for i=1 to m

for j=1 to n

Ri,j=TACi,j—min{TACk,j|k=1-m, TACk,j> 0}

相對(duì)成本算法程序

以上相對(duì)成本算法程序中 i表示服務(wù)器叢集編號(hào) 1~m，j表示文件編號(hào) 1~n，Ri,j表示文件存放于叢集i的相對(duì)成本。每個(gè)文件都將其對(duì)應(yīng)TAC數(shù)值減去最小TAC值，以表3案例中的文件f1為例，其最小TAC值為2，將其對(duì)應(yīng)TAC值減去2，其他文件依此類推，結(jié)果如表4所示。

表4 相對(duì)成本計(jì)算結(jié)果案例Tab.4 Relative cost calculation case

由表4可看出最佳叢集為TAC增長(zhǎng)為 0的叢集，當(dāng)需選擇移至別的叢集文件時(shí)就可選擇TAC增長(zhǎng)較少的文件。依照相對(duì)成本矩陣，叢集進(jìn)行本身文件篩選，其文件篩選算法程序如下：

Main

-function（）

for j =1 to n

FStatusj=false

While（?false∈{FStatusj| j=1~n}）

Compute-relative-cost（）

for i=1 to m

if（Spi>0）

For j=1 to n

if（Ri,j=0 and FStatusj=false）

add j in FileListi

Spi=Spi-Fsj

FStatusj=true

end for

end for

for i=1 to m

if（Spi<0）

File-Transfer（i）

end

文件篩選算法程序

以上文件篩選算法程序中，F(xiàn)Statusj表示文件 j是否已決定存放位置的狀態(tài)，F(xiàn)ileListi表示服務(wù)器叢集i的文件存放列表，Spi表示服務(wù)器叢集i的剩余空間，F(xiàn)sj表示文件j的大小。依據(jù)相對(duì)成本矩陣，叢集分別挑選出成本為0且還沒決定存放位置的文件，并將叢集空間扣除文件大小，最后每個(gè)叢集檢查其剩余空間是否為負(fù)值，如果是則表示此叢集空間不足，需要將部分文件移至別的叢集存放。將文件移出的相對(duì)成本比較算法程序如下：

File-Site（i）

for each filejin FileListi

MoveCostj=min｛Ri,j｜i=1~n，Ri,j>0

While（Spi<0）

j=min｛MoveCostj｝

Delete j from FileListi

Spi=Spi+ Fsj

FStatusj=false

Ri,j= —1

delete j from｛MoveCostj｝

end

服務(wù)器叢集滿載文件移動(dòng)算法程序

上述服務(wù)器叢集滿載文件移動(dòng)算法程序中，F(xiàn)ile-Transfer（i）表示服務(wù)器叢集i的文件移動(dòng)設(shè)置，MoveCostj表示文件編號(hào)j的移出成本。

相對(duì)成本矩陣表示文件被移至其他叢集時(shí)其增加的TAC數(shù)值有多少。通過上述算法，首先將欲存放此叢集的文件分別找出其在其他叢集時(shí)最小的相對(duì)成本，也就是第二個(gè)適合存放此文件的叢集。將每個(gè)文件相對(duì)成本比較并選出最小的，表示此文件被移出時(shí)增加的TAC最少，影響也最小。所以可決定將其移至別的服務(wù)器，如此重復(fù)挑選直到叢集空間足夠。如由表4來計(jì)算結(jié)果如表5所示，可看出在叢集S2所有文件中，f3從叢集S2移至叢集所造成S3所造成的 TAC增長(zhǎng)最少。所以在 S2滿載時(shí)在移動(dòng)文件檔案會(huì)優(yōu)先選擇f3移出。

表5 文件移動(dòng)增長(zhǎng)成本Tab.5 Mobile cost of file growth

文件移出結(jié)束后回到主程序?qū)?huì)把相對(duì)矩陣重新計(jì)算一次，此時(shí)被移出的文件其存在第二個(gè)合適叢集的相對(duì)成本會(huì)變?yōu)?0，在下次重復(fù)挑選便會(huì)被第二合適的叢集選擇。如此不斷重復(fù)的選擇、比較，直到所有文件都決定存放位置為止，完成文件最佳存放位置的近似解。

5 實(shí)驗(yàn)仿真

5.1 叢集數(shù)與分支度及文件數(shù)對(duì)存取成本影響仿真

在叢集數(shù)量與分支度對(duì)存取成本影響實(shí)驗(yàn)仿真中，分4種不同的叢集數(shù)及分支度進(jìn)行交叉測(cè)試，叢集數(shù)分別為30/40/50/60，每個(gè)服務(wù)器叢集總空間為1000位元單位，叢集的連外分支數(shù)為1/2/3/4四種，入口點(diǎn)數(shù)固定為10，文件數(shù)固定為2000，每個(gè)文件的大小為3~5位元單位隨機(jī)，使用者數(shù)為3000。圖2為叢集數(shù)與分支度對(duì)存取成本影響的實(shí)驗(yàn)仿真結(jié)果。

叢集數(shù)與文件數(shù)對(duì)存取成本影響實(shí)驗(yàn)仿真中，以2種不同的叢集數(shù)與1000到4600文件數(shù)進(jìn)行交叉測(cè)試，叢集數(shù)為30/60，每個(gè)服務(wù)器叢集總空間為1000，叢集的連外支數(shù)固定為 3，入口點(diǎn)數(shù)固定為10，文件數(shù)從1000到4600每次增加50個(gè)，每個(gè)文件的大小為3~6隨機(jī)，使用者數(shù)為3000，圖3為叢集數(shù)與文件數(shù)對(duì)存取成本影響的實(shí)驗(yàn)仿真結(jié)果。

圖2 叢集數(shù)與分支度對(duì)存取成本影響Fig.2 The influence of cluster Number and branch degree on access cost

圖3 叢集數(shù)量與文件數(shù)對(duì)存取成本影響Fig.3 The impact of the number of clusters and the number of files on the access cost

從圖2可看出，四種分支度在不同服務(wù)器叢集數(shù)各進(jìn)行10次的平均結(jié)果，在固定的文件與入口點(diǎn)數(shù)下，叢集數(shù)越多反而會(huì)增加存取成本。因?yàn)樵跊]有相對(duì)提升分支度即提高每個(gè)叢集連外數(shù)情況下，增加叢集數(shù)同樣會(huì)增加叢集間的跳躍計(jì)數(shù)從而增加了路徑長(zhǎng)度。提升分支度數(shù)后當(dāng)叢集數(shù)增加時(shí)，因跳躍路徑減少使存取成本增高率也相對(duì)下降，圖 2中分支度到達(dá) 3時(shí)平均存取成本才約文件大小的3~4間，分支度到4時(shí)平均存取成本才在2~3間。

從圖3中可看出，當(dāng)文件數(shù)增加時(shí)，叢集數(shù)越多對(duì)存取成本的影響越低。當(dāng)叢集數(shù)為30，當(dāng)文件數(shù)增加時(shí)因叢集空間有限且叢集數(shù)較少，則必須將部分文件存放于距離較遠(yuǎn)的叢集，無法完全針對(duì)入口點(diǎn)需求量來存放文件，因此平均存取成本隨文件數(shù)增加逐漸上升。而當(dāng)叢集數(shù)為60時(shí)，平均存取成本在文件數(shù)增加時(shí)卻逐漸下降，因?yàn)榉?wù)器較多則表示網(wǎng)絡(luò)距離分布較遠(yuǎn)，入口點(diǎn)間的距離也會(huì)增加。而在文件少量時(shí)多數(shù)使用者會(huì)選擇相同文件，所以文件便會(huì)被存放離多個(gè)入口點(diǎn)都不至于過遠(yuǎn)的中間叢集位置，則在網(wǎng)絡(luò)結(jié)構(gòu)分布較廣狀態(tài)下對(duì)每個(gè)入口點(diǎn)的距離都會(huì)多少增加，但當(dāng)文件數(shù)增多會(huì)分散使用者選擇的文件。部分用者選擇的文件不一定為熱門文件，不必存放于中間位置，可存放于針對(duì)存放該文件較多的入口點(diǎn)附近。而叢集數(shù)較多狀態(tài)下，文件因空間不足被迫移至較遠(yuǎn)叢集的情況減少，相對(duì)的存取成本也會(huì)降低。因此文件數(shù)多時(shí)所有使用者的平均存取成本相對(duì)于文件數(shù)少時(shí)會(huì)較低。

5.2 隨機(jī)和輪轉(zhuǎn)存放方式對(duì)存取成本影響仿真

（1）叢集數(shù)對(duì)存取成本影響實(shí)驗(yàn)仿真

叢集數(shù)對(duì)存取成本影響實(shí)驗(yàn)仿真參數(shù)設(shè)定分為叢集數(shù)為30/60兩種情況，叢集數(shù)為30/60的入口點(diǎn)數(shù)分別設(shè)定為5/15，服務(wù)器叢集總空間都設(shè)為1000位元單位，節(jié)點(diǎn)分支度都設(shè)為 3，頻寬數(shù)值都設(shè)為2~8，文件數(shù)都設(shè)為1000~4600，文件大小都設(shè)為3~6位元單位，使用者數(shù)都設(shè)為3000。因叢集數(shù)多時(shí)叢集間的跳躍計(jì)數(shù)會(huì)增加，如入口點(diǎn)數(shù)與叢集少時(shí)設(shè)定相同，則入口點(diǎn)間的距離也會(huì)相對(duì)增加。所以在叢集數(shù)較多的實(shí)驗(yàn)仿真中設(shè)定有較多的入口以保證距離的公平性，仿真結(jié)果如圖4所示。

圖4 叢集數(shù)對(duì)存取成本影響Fig.4 The impact of cluster numbers on access costs

由圖4可知，隨機(jī)與輪轉(zhuǎn)兩種文件存放方法平均成本差距不大，且兩種方法的存取成本與文件數(shù)沒太多影響，而本文研究方法其平均存取成本相較于以上兩種方法明顯要低。且在文件總數(shù)相同條件下，叢集數(shù)為60時(shí)本文研究方法的平均存取成本與其他兩種方法的差距大于叢集數(shù)為30時(shí)對(duì)應(yīng)情況。即在儲(chǔ)存空間充裕狀態(tài)下本文研究方法能更有效安排文件的存放，而其他兩種方法當(dāng)叢集數(shù)增加后，因結(jié)構(gòu)范圍擴(kuò)大提高了距離，從而使得平均存取成本大幅增高，由此可見本文研究方法在文件數(shù)與叢集數(shù)均衡情況下，更能將每個(gè)文件存放在有利于所有使用者的叢集位置。

（2）文件大小范圍對(duì)存取成本影響實(shí)驗(yàn)仿真

仿真時(shí)文件大小隨機(jī)范圍分別設(shè)為4~6與1~9，叢集數(shù)都設(shè)為30，節(jié)點(diǎn)分支度都設(shè)為3，服務(wù)器叢集空間都設(shè)為1000位元單位，入口點(diǎn)數(shù)都設(shè)為5，頻寬數(shù)值設(shè)為2~8，文件數(shù)設(shè)為1000~4600，使用者數(shù)設(shè)為3000，仿真結(jié)果如下圖5所示。

由圖5可知，本文研究方法與隨機(jī)、輪轉(zhuǎn)兩方法當(dāng)文件范圍增加時(shí)，平均存取成本總體都有相對(duì)增加現(xiàn)象，且不管哪種文件大小范圍，其平均存取成本數(shù)均大于文件大小范圍。而本文研究方法當(dāng)范圍增加時(shí)，且文件數(shù)為1000~2350時(shí)因文件數(shù)較少易產(chǎn)生部分極端大小的文件，造成存取成本變異數(shù)較大；而當(dāng)文件數(shù)超過2800后，存取成本變動(dòng)范圍明顯縮小。表示即使文件大小的差異較大，本文研究方法仍然視使用者的使用情況處理極端大小的文件，不會(huì)造成因極度偏袒部分使用者而使整體平均存取成本降低。

圖5 文件范圍對(duì)存取成本影響Fig.5 Scope of the file affects access costs

6 總結(jié)

本文所設(shè)計(jì)的云文件存放策略算法，針對(duì)客戶端對(duì)文件的存取頻率與文件大小，綜合最短網(wǎng)絡(luò)距離的計(jì)算來優(yōu)選文件存放位置。通過弗洛伊得算法計(jì)算出任兩點(diǎn)最短距離的特性，計(jì)算入口點(diǎn)至任意叢集的最短網(wǎng)絡(luò)距離，讓使用者能以最少的跳轉(zhuǎn)次數(shù)或最佳的頻寬路徑進(jìn)行存取，提升了效率。在分支度數(shù)實(shí)驗(yàn)中，當(dāng)分支度增加使得路徑選擇變多時(shí)能計(jì)算出更佳路徑，效率也相對(duì)提升。當(dāng)多個(gè)使用者存取相同文件時(shí)，算法依據(jù)不同使用者存取入口點(diǎn)位置、存取文件大小、存取頻率來計(jì)算出對(duì)所有使用者公平的存放位置，避免了文件只針對(duì)單一使用者情況來計(jì)算存放位置，造成其他多數(shù)使用者存取成本的增加。在叢集數(shù)與文件數(shù)實(shí)驗(yàn)中，本文研究的存放策略考慮到了所有使用者。當(dāng)叢集存放空間滿載時(shí)，本文研究的算法選出對(duì)使用者影響最低文件并移到別的叢集存放。當(dāng)叢集數(shù)較少，且多數(shù)叢集空間都滿載情況下，本研究方法仍然能夠與其他兩種方法有明顯差距，證實(shí)本文研究算法能在叢集滿載時(shí)，仍可計(jì)算出較佳的存放位置。

[1] 馬小龍, 劉蘭娟. 基于在線機(jī)制設(shè)計(jì)的私有云資源分配研究[J]. 計(jì)算機(jī)應(yīng)用研究. 2015(2): 539-542.

[2] 徐曉斌, 張光衛(wèi), 孫其博, 楊放春. 一種誤差可控傳輸均衡的WSN數(shù)據(jù)融合算法[J]. 電子學(xué)報(bào). 2014(06): 1205-1209.

[3] 朱志祥, 許輝輝, 王雄. 基于云計(jì)算的彈性負(fù)載均衡方案[J]. 西安郵電大學(xué)學(xué)報(bào). 2013(6): 43-47.

[4] 馮小靖, 潘郁. 云計(jì)算環(huán)境下的DPSO資源負(fù)載均衡算法[J]. 計(jì)算機(jī)工程與應(yīng)用. 2013(6): 105-108.

[5] 裴養(yǎng), 吳杰, 王鑫. 基于粒子群優(yōu)化算法的虛擬機(jī)放置策略[J]. 計(jì)算機(jī)工程. 2012(16): 291-293.

[6] 劉媛媛, 高慶一, 陳陽(yáng). 虛擬計(jì)算環(huán)境下虛擬機(jī)資源負(fù)載均衡方法[J]. 計(jì)算機(jī)工程. 2010(16): 30-32.

[7] 劉春波, 陳建業(yè). 基于SDN的虛擬網(wǎng)絡(luò)重映射方法研究[J].軟件. 2016(10): 82-88.

[8] 齊小航, 田清華. 空間信息網(wǎng)中面向任務(wù)的多拓?fù)渎酚伤惴╗J]. 軟件. 2014(9): 49-56.

[9] 趙禮峰, 梁娟. 最短路問題的Floyd改進(jìn)算法[J]. 計(jì)算機(jī)技術(shù)與發(fā)展. 2014(8): 31-34.

[10] 陳雅良, 溫朝暉, 周浩然, 王甜甜. 基于Floyd算法對(duì)交通流最優(yōu)路徑選擇的研究[J]. 佳木斯大學(xué)學(xué)報(bào)(自然科學(xué)版).2016(6): 917-919+942.

[11] 許克平, 曾明月, 鄢好, 袁麗娟, 彭圓紅. 基于不確定因素下的Floyd算法改進(jìn)[J]. 中國(guó)科技信息. 2016(18): 49-50+14.

[12] 左秀峰, 沈萬(wàn)杰. 基于Floyd算法的多重最短路問題的改進(jìn)算法[J]. 計(jì)算機(jī)科學(xué). 2017(5): 232-234+267.

Research on Cloud File Storage Load Balancing Algorithm based on Floyd Algorithm

CHEN Yuan, LIU Jun-hua, LEI Chao-yang
(Internet engineering department, Hunan Post and Telecommunication College, Changsha 410015 China)

This paper proposes the cloud file storage load balancing algorithm based on Floydalgorithm, Based on the client′s access frequency and file size, the calculation of the shortest network distance to optimize the file storage location, and the hop count and network bandwidth between all clients and all service nodes are considered to be their network distance. The simulation results show that: In this paper, the average access cost of the paper is significantly lower than that of random and rotary methods, to place the file location fairly for all users, Allows users to access at least the number of hops or the best bandwidth path, improves the access efficiency of client file. And when most of the cluster space is full, the research methodcan still calculate the better storage location.

: Floydalgorithm; Cloud files; Load balancing; Algorithm

TP301

A

10.3969/j.issn.1003-6970.2017.10.012

本文著錄格式：陳園，劉軍華，雷超陽(yáng). 基于弗洛伊得算法的云端文件存儲(chǔ)負(fù)載平衡算法研究[J]. 軟件，2017，38（10）：67-72

湖南省教育廳科研項(xiàng)目(編號(hào)：16C720)

陳園(1983-），女，湖南長(zhǎng)沙人，講師，碩士研究生，研究方向：圖像處理、計(jì)算機(jī)網(wǎng)絡(luò)；劉軍華(1979-)，男，湖南衡陽(yáng)人，副教授，碩士，研究方向：移動(dòng)互聯(lián)網(wǎng)應(yīng)用技術(shù)、軟件工程；雷超陽(yáng)(1971-)，男，湖南耒陽(yáng)人，教授，博士，研究方向：圖像處理、計(jì)算機(jī)網(wǎng)絡(luò)。