選擇目標微云以最大程度地減少服務延遲

任子斌

(東華大學 計算機科學與技術學院， 上海 201620)

0 引 言

近年來，移動設備在人們的日常生活中無處不在[1]。這些移動設備受資源限制，并且通常使用云資源來滿足其計算要求。許多移動應用程序對延遲敏感，就像增強現實和交互式游戲[2]一樣，需要低服務延遲。然而，這些應用程序的延遲要求無法通過傳統云的架構[3]來得到滿足。這個問題引起了研究者和用戶更多的關注與重視。

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

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

1 資源分配技術研究現狀

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

2 面向移動用戶的最優微云選擇機制與算法設計

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

當移動用戶生成需要微云服務的任務時，移動用戶將連接到AP接入點并通過AP接入點將任務傳輸到微云。由于網絡中的用戶是移動的，微云控制中心應根據用戶的位置為用戶選擇合適的AP接入點和服務微云，如此即可為用戶提供低延遲的服務。根據用戶位置為用戶分配合適的AP接入點和服務微云從而最小化總服務延遲是本節的主要研究目標。

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

算法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;

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

3 仿真實現

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

在本文的模擬中，使用了200×200公里區域。此區域中有一個移動用戶。研究中為用戶設置了8個移動方向。用戶在實驗開始時隨機選擇一個方向。用戶在實驗過程中不會更改其移動方向。用戶的移動速度為19 m/s。每個微云服務器的處理器速度是每秒2 800萬條指令(MIPS)，即vcloudlet=2 800 MIPS。網絡中有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生成一個任務。任務的上傳數據大小為1 KB，任務的下載數據大小為1 KB。用戶和AP接入點之間的上行帶寬為每秒100 Mbps，用戶和AP接入點之間的下行帶寬為2 Mbps。

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

4 實驗結果與分析

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

圖1 當帶寬較小時各種遷移策略的服務延遲

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

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

圖2 當帶寬較中等時各種遷移策略的服務延遲

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

圖3 當帶寬較大時各種遷移策略的服務延遲

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

5 結束語

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