任子斌

(東華大學(xué) 計算機(jī)科學(xué)與技術(shù)學(xué)院， 上海 201620)

0 引 言

近年來，移動設(shè)備在人們的日常生活中無處不在[1]。這些移動設(shè)備受資源限制，并且通常使用云資源來滿足其計算要求。許多移動應(yīng)用程序?qū)ρ舆t敏感，就像增強(qiáng)現(xiàn)實和交互式游戲[2]一樣，需要低服務(wù)延遲。然而，這些應(yīng)用程序的延遲要求無法通過傳統(tǒng)云的架構(gòu)[3]來得到滿足。這個問題引起了研究者和用戶更多的關(guān)注與重視。

在文獻(xiàn)[4-5]中提出了移動邊緣計算，以滿足移動用戶這些需要超低延遲的應(yīng)用程序。為了便于托管延遲敏感應(yīng)用程序，邊緣計算節(jié)點被認(rèn)為實現(xiàn)了快速資源響應(yīng)的優(yōu)先級[6-7]。邊緣計算旨在將云功能推送到網(wǎng)絡(luò)邊緣，此外還提供低延遲[8]。

在智能城市中，具有任意移動性的用戶設(shè)備給選擇邊緣計算的目標(biāo)微云帶來了新的挑戰(zhàn)[9-11]。為了提供低延遲服務(wù)，在考慮用戶位置時盡可能選擇為用戶提供最低延遲的微云是一個頗具挑戰(zhàn)性的難題[12]。為了解決這個問題，本文根據(jù)用戶的位置提出了一種目標(biāo)微云選擇方案、即最低局部延遲算法。該算法考慮了傳輸時間、計算時間、選擇時間和用戶在目標(biāo)微云選擇過程中的位置。對不同網(wǎng)絡(luò)狀況進(jìn)行仿真，以評估本文提出的算法的性能。將本文提出的算法與現(xiàn)有算法進(jìn)行了比較。仿真結(jié)果表明，該算法為移動用戶提供了更低的服務(wù)延遲。

1 資源分配技術(shù)研究現(xiàn)狀

隨著用戶的移動，現(xiàn)有的一些算法諸如：設(shè)備與AP接入點之間的最短距離算法、設(shè)備與微云之間的最短距離算法、最低延遲算法，雖然能夠在一定程度上滿足用戶延遲需求，但總體用戶的滿意度仍不理想，因此，本文提出了局部最低延遲算法。

2 面向移動用戶的最優(yōu)微云選擇機(jī)制與算法設(shè)計

在本節(jié)中，微云和AP接入點在網(wǎng)絡(luò)中均勻分布。每個AP接入點都覆蓋一個半徑為R的區(qū)域。位于AP接入點的覆蓋區(qū)域圓圈中的用戶可以直接與AP接入點通信。AP接入點通過相鄰的AP接入點與不在其覆蓋區(qū)域的微云進(jìn)行通信。網(wǎng)絡(luò)中有一個微云控制中心，記錄著網(wǎng)絡(luò)的一些重要信息，例如網(wǎng)絡(luò)中的微云數(shù)量、每個微云的可用資源、每個用戶的位置以及每個AP接入點和微云的位置。所有微云和用戶都可以通過AP接入點與微云控制中心通信，以更新或接收信息。每個微云可以實時監(jiān)控其剩余可用的資源，并將這些信息發(fā)送到微云控制中心。每個用戶都通過GPS確定其位置，并將位置信息發(fā)送到微云控制中心。

當(dāng)移動用戶生成需要微云服務(wù)的任務(wù)時，移動用戶將連接到AP接入點并通過AP接入點將任務(wù)傳輸?shù)轿⒃?。由于網(wǎng)絡(luò)中的用戶是移動的，微云控制中心應(yīng)根據(jù)用戶的位置為用戶選擇合適的AP接入點和服務(wù)微云，如此即可為用戶提供低延遲的服務(wù)。根據(jù)用戶位置為用戶分配合適的AP接入點和服務(wù)微云從而最小化總服務(wù)延遲是本節(jié)的主要研究目標(biāo)。

針對于目前三種算法，本文提出了局部最低延遲算法，局部最低延遲算法具體實現(xiàn)偽代碼詳見如下。

算法1 局部最低延遲算法

mark destination cloudlet for taskjas null;

get the nearestAPto the user, and denote the nearestAPasAPm;

letAPmbe the newAPfor the user;

letsAPmdenote the set of cloudlets in the coverage area ofAPm;

for each cloudlet insAPmdo

update service latencyτsi,u,si∈sAPm,i=1,2,...,|sAPm|;

end for

get the smallestτsi,ufrom {τs1,u,τs2,u,...,τs|APm|,u}, and denote the cloudlet which has the smallestτsi,uassm;

let the cloudletsmas the destination cloudlet;

對上述算法進(jìn)行剖析后詳述如下：如果微云控制中心收到用戶的資源分配請求，微云控制中心將運行遷移策略4，將給用戶分配連接的AP和服務(wù)微云。研究時將用戶表示為u，每個AP接入點的覆蓋半徑為R的圓形區(qū)域。首先，獲取最接近用戶的AP接入點，并將此AP接入點表示為APm(請參閱第2行)。讓APm成為用戶的新接入的AP(見第3行)。讓sAPm表示APm覆蓋區(qū)域中的微云的集合(見第4行)。sAPm中的所有微云都可以與APm直接通信。然后，算法更新每個微云si(si∈sAPm,i=1,2,...,|sAPm|)和用戶u之間的服務(wù)延遲τsi,u(請參閱第6～9行)，其中|sAPm|表示sAPm中的微云的數(shù)量。然后，從{τs1,u,τs2,u,...,τs|APm|,u}集合中選擇的最小的τsi,u并表示成sm(請參見第10～12行)。最后，該算法將sm作為任務(wù)j的目標(biāo)微云(見第13行)。

3 仿真實現(xiàn)

在本節(jié)中，將提出的最低局部延遲算法與現(xiàn)有算法進(jìn)行比較，即設(shè)備與AP接入點之間的最短距離算法、設(shè)備與微云之間的最短距離算法以及最低延遲算法。所有仿真均使用iFogSim[13]在英特爾酷睿i5處理器(2.7 GHz)上執(zhí)行。iFogSim是一個模擬框架，用于建模和模擬云計算基礎(chǔ)設(shè)施和服務(wù)。

在本文的模擬中，使用了200×200公里區(qū)域。此區(qū)域中有一個移動用戶。研究中為用戶設(shè)置了8個移動方向。用戶在實驗開始時隨機(jī)選擇一個方向。用戶在實驗過程中不會更改其移動方向。用戶的移動速度為19 m/s。每個微云服務(wù)器的處理器速度是每秒2 800萬條指令(MIPS)，即vcloudlet=2 800 MIPS。網(wǎng)絡(luò)中有400個微云和930個AP接入點。微云均勻分布，且相互間隔為10 Km, 即dcloudlets=10 Km，AP接入點均勻分布，且相互間隔為6.5 Km, 即dAPs=6.5 Km。每個AP接入點的覆蓋范圍為5 Km，即R=5 Km。模擬時間是1 h。用戶每隔20 s生成一個任務(wù)。任務(wù)的上傳數(shù)據(jù)大小為1 KB，任務(wù)的下載數(shù)據(jù)大小為1 KB。用戶和AP接入點之間的上行帶寬為每秒100 Mbps，用戶和AP接入點之間的下行帶寬為2 Mbps。

研究中比較了3個不同網(wǎng)絡(luò)環(huán)境中的4種算法，即：微云和AP接入點之間的帶寬均勻分布在10～20 Mbps之間；微云和AP接入點之間的帶寬均勻分布于90～100 Mbps之間；微云和AP接入點之間的帶寬均勻地分布在990～1 000 Mbps之間。

4 實驗結(jié)果與分析

本節(jié)以服務(wù)延遲為性能指標(biāo)對不同的遷移策略進(jìn)行仿真實驗，不同微云和AP接入點之間帶寬不同的仿真結(jié)果分別如圖1～圖3所示。從圖1中可以看到，遷移策略4的服務(wù)延遲(即最低的本地延遲算法)是最低的。盡管遷移策略1選擇最接近用戶的AP接入點并選擇距離所選AP接入點最近的微云以向用戶提供服務(wù)，但微云和用戶可能不是距離最短的。因此，傳輸時間可能不是最短的。此外，遷移策略1在目標(biāo)微云選擇過程中不考慮微云的處理時間。因此，遷移策略1的服務(wù)延遲是最大的。為了最大程度地縮短微云和用戶之間的傳輸時間，遷移策略2選擇最接近用戶的微云作為目標(biāo)微云。因此，傳輸時間縮短。從圖1也可以看出，遷移策略2的服務(wù)延遲小于遷移策略1的服務(wù)延遲。盡管遷移策略2選擇的目標(biāo)微云是最接近用戶的微云，但考慮到網(wǎng)絡(luò)擁塞，傳輸時間可能不是最短的時間。此外，遷移策略1和遷移策略2 在微云選擇過程中不考慮微云選擇時間，這可能會增加服務(wù)延遲。為了提供低服務(wù)延遲，遷移策略3選擇服務(wù)延遲最短的微云作為目標(biāo)微云。因此，可以減少遷移策略3的服務(wù)延遲。由圖1可知，遷移策略3的服務(wù)延遲小于遷移策略1和遷移策略2的服務(wù)延遲。但是，要獲得每個微云提供的服務(wù)延遲，遷移策略3應(yīng)計算網(wǎng)絡(luò)中所有微云的服務(wù)延遲，對于具有大量微云的網(wǎng)絡(luò)，這尤其會增加選擇時間。為了最小化選擇時間，遷移策略4僅計算用戶附近微云提供的服務(wù)延遲。綜合前文分析后，并參見圖1可知，遷移策略4的服務(wù)延遲最低。這是因為遷移策略4在目標(biāo)微云選擇過程中同時考慮傳輸時間、計算時間和選擇時間。

圖1 當(dāng)帶寬較小時各種遷移策略的服務(wù)延遲

Fig. 1 Service delay for various migration strategies when bandwidth is small

從圖2和圖3中，還可以看到遷移策略4的服務(wù)延遲最低。與其他三種算法相比，遷移策略是目標(biāo)微云選擇的最佳算法，該算法在考慮用戶的移動的同時，提供了最低的服務(wù)延遲。

圖2 當(dāng)帶寬較中等時各種遷移策略的服務(wù)延遲

Fig. 2 Service delay for various migration strategies when bandwidth is moderate

圖3 當(dāng)帶寬較大時各種遷移策略的服務(wù)延遲

Fig. 3 Service delay for various migration strategies when bandwidth is large

5 結(jié)束語

本文研究了目標(biāo)微云的選擇問題。提出了最低局部延遲算法，為移動用戶提供低服務(wù)延遲。在此算法中，在目標(biāo)微云選擇過程中考慮了傳輸時間、計算時間、微云選擇時間和用戶位置。研究中還進(jìn)行了廣泛的模擬，以證明最低局部延遲算法的有效性。對于未來的工作，將重點討論移動用戶的一組云子選擇和 VM 選擇問題。