陳思穎 郭躍 胡歡波

摘要：移動(dòng)云計(jì)算是一種將移動(dòng)互聯(lián)網(wǎng)與云計(jì)算相結(jié)合的新技術(shù)，用戶(hù)可將數(shù)據(jù)的計(jì)算和存儲(chǔ)等任務(wù)調(diào)度至云端來(lái)改善其移動(dòng)終端處理能力弱、存儲(chǔ)空間小及電池續(xù)航時(shí)間短等缺點(diǎn)。本文針對(duì)關(guān)聯(lián)性的混雜任務(wù)序列，建立具有順序相關(guān)性的任務(wù)隊(duì)列模型。針對(duì)任務(wù)的隨機(jī)性，在滿(mǎn)足任務(wù)的平均等待時(shí)間要求的前提下，將移動(dòng)終端對(duì)任務(wù)處理或調(diào)度時(shí)產(chǎn)生的能耗作為優(yōu)化目標(biāo)，建立連續(xù)時(shí)間馬爾可夫決策過(guò)程系統(tǒng)模型。針對(duì)模型采用策略迭代算法對(duì)其進(jìn)行求解，以期望尋找到最優(yōu)策略使之既能滿(mǎn)足時(shí)間要求又能降低能耗，仿真驗(yàn)證算法的有效性。

關(guān)鍵詞：移動(dòng)云計(jì)算；馬爾可夫決策模型；任務(wù)調(diào)度；能耗優(yōu)化；策略迭代

中圖分類(lèi)號(hào)：TP393 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2018）21-0036-04

Abstract：Mobile cloud computing is a new technology that combines mobile internet and cloud computing. To improve mobile terminal's weak processing capabilities， small storage space， and short battery life， users can migrate calculations and storage of data to the cloud..For mutually dependent mixed sequence tasks， a mutually dependent task queue model is established. For the randomness of tasks， a continuous time Markov decision process system model is established. Under the premise of meeting the average waiting time requirement of the task， the energy consumption generated by the mobile terminal during task processing or scheduling is used as an optimization goal. A continuous time Markov decision process system model is established. The model is solved using a strategy iterative algorithm. In order to find the optimal strategy， it can not only satisfy the time requirements but also reduce the energy consumption. The simulation validates the effectiveness of the algorithm.

Key words： Mobile cloud computing；Markov decision process； task scheduling；energy efficiency optimization；strategy iterative algorithm

現(xiàn)如今，世界已經(jīng)進(jìn)入了5G時(shí)代，落后的單一模式的計(jì)算處理已經(jīng)無(wú)法滿(mǎn)足人們對(duì)于海量數(shù)據(jù)的無(wú)限存儲(chǔ)和多類(lèi)信息的高速處理。而云計(jì)算技術(shù)正是迎合了人們對(duì)于信息處理服務(wù)質(zhì)量高標(biāo)準(zhǔn)的理想需求。移動(dòng)云計(jì)算（Mobile Cloud Computing）是基于云計(jì)算技術(shù)的一種新興的移動(dòng)應(yīng)用模式，它是將云計(jì)算引入移動(dòng)環(huán)境中[4]，是云計(jì)算和移動(dòng)互聯(lián)網(wǎng)兩者結(jié)合的產(chǎn)物，它構(gòu)建了一種“云計(jì)算-互聯(lián)網(wǎng)-移動(dòng)終端”的構(gòu)架。

移動(dòng)云計(jì)算主要由移動(dòng)終端，無(wú)線(xiàn)互聯(lián)網(wǎng)絡(luò)，和存儲(chǔ)云計(jì)算資源的云端服務(wù)器三部分組成，移動(dòng)云計(jì)算系統(tǒng)的總體架構(gòu)如圖1所示[5]。首先，用戶(hù)移動(dòng)終端通過(guò)基站（Base Station， BS）或接入點(diǎn)（Access Point， AP）以無(wú)線(xiàn)的形式進(jìn)入通信網(wǎng)絡(luò)中，在該階段中移動(dòng)終端會(huì)與基站或者無(wú)線(xiàn)接入點(diǎn)（如路由器等）之間進(jìn)行空中對(duì)接，將終端的信息發(fā)送給移動(dòng)網(wǎng)絡(luò)服務(wù)器，服務(wù)器將無(wú)線(xiàn)資源合理地分配給移動(dòng)終端，同時(shí)網(wǎng)絡(luò)運(yùn)營(yíng)商（如聯(lián)通，電信等）會(huì)對(duì)用戶(hù)信息進(jìn)行驗(yàn)證以及對(duì)業(yè)務(wù)數(shù)據(jù)庫(kù)進(jìn)行完善。然后，再經(jīng)過(guò)互聯(lián)網(wǎng)接入云服務(wù)供應(yīng)商提供的云計(jì)算資源池中選擇合適的資源進(jìn)行任務(wù)處理。其中，云計(jì)算服務(wù)平臺(tái)主要包括控制器和數(shù)據(jù)中心。控制器是云計(jì)算的核心，擔(dān)任著資源管理的角色，它負(fù)責(zé)對(duì)用戶(hù)任務(wù)的接入控制、對(duì)資源的調(diào)度分配等。存儲(chǔ)資源的數(shù)據(jù)中心會(huì)根據(jù)控制器的決策合理的對(duì)任務(wù)進(jìn)行處理。這里，網(wǎng)絡(luò)運(yùn)營(yíng)商和云供應(yīng)商可統(tǒng)稱(chēng)為基礎(chǔ)設(shè)施提供商（Infrastructure Providers， InP），這也體現(xiàn)出了云計(jì)算基礎(chǔ)設(shè)施即服務(wù)（ Infrastructure as a service，IaaS）的特點(diǎn)。

1 任務(wù)隊(duì)列模型

如果任務(wù)之間存在數(shù)據(jù)依賴(lài)性，那么不同類(lèi)型任務(wù)的執(zhí)行順序會(huì)受任務(wù)之間關(guān)聯(lián)特性的影響，有可能出現(xiàn)某些任務(wù)需要等待與之有關(guān)聯(lián)的任務(wù)處理完成或者達(dá)到某些特定條件后，其自身才會(huì)進(jìn)行處理計(jì)算。因此，關(guān)聯(lián)性任務(wù)之間的觸發(fā)條件或影響因素會(huì)對(duì)系統(tǒng)性能產(chǎn)生較大的影響。

本文主要針對(duì)存在順序相關(guān)性約束條件的任務(wù)進(jìn)行研究。假設(shè)本地移動(dòng)終端內(nèi)有[I]類(lèi)任務(wù)，第i類(lèi)任務(wù)達(dá)到本地移動(dòng)終端的過(guò)程服從泊松分布，在本地移動(dòng)終端和云端服務(wù)器中的處理速率服從負(fù)指數(shù)分布。

考慮到任務(wù)之間有一定的執(zhí)行順序所以在下文中我們對(duì)任務(wù)執(zhí)行調(diào)度的觸發(fā)條件進(jìn)行了研究，建立任務(wù)隊(duì)列模型，此模型中本地移動(dòng)終端中對(duì)每類(lèi)任務(wù)建立長(zhǎng)度為[N]的任務(wù)調(diào)度隊(duì)列和長(zhǎng)度為[M]的任務(wù)緩存隊(duì)列。

移動(dòng)終端會(huì)對(duì)任務(wù)進(jìn)行處理，以此來(lái)判斷不同類(lèi)型的任務(wù)之間是否存在著某種依賴(lài)關(guān)系：如果這些任務(wù)之間是獨(dú)立運(yùn)行的則直接將其都放入如圖2所示的各自的任務(wù)調(diào)度隊(duì)列中，這樣本地移動(dòng)終端可以對(duì)每類(lèi)任務(wù)調(diào)度隊(duì)列中隊(duì)首所指向的任務(wù)進(jìn)行調(diào)度處理；但是，如果到達(dá)的某類(lèi)任務(wù)與其他種類(lèi)的任務(wù)有關(guān)聯(lián)存在著順序關(guān)系：1）當(dāng)此類(lèi)任務(wù)在本地移動(dòng)終端的調(diào)度隊(duì)列處于滿(mǎn)隊(duì)狀態(tài)時(shí)，進(jìn)入此類(lèi)任務(wù)的緩存隊(duì)列進(jìn)行等待，當(dāng)執(zhí)行條件觸發(fā)時(shí)此類(lèi)任務(wù)的調(diào)度隊(duì)列有任務(wù)被調(diào)度處理，使此類(lèi)任務(wù)的緩存隊(duì)列中的任務(wù)進(jìn)入自身的調(diào)度隊(duì)列繼續(xù)等待調(diào)度執(zhí)行。2）當(dāng)此類(lèi)任務(wù)在本地移動(dòng)終端的調(diào)度隊(duì)列處于未滿(mǎn)狀態(tài)時(shí)，任務(wù)直接進(jìn)入調(diào)度隊(duì)列等待執(zhí)行條件的觸發(fā)。在本文中為了方便分析我們假設(shè)在[I]類(lèi)任務(wù)中第[i]類(lèi)任務(wù)的調(diào)度執(zhí)行是第j類(lèi)任務(wù)進(jìn)行調(diào)度執(zhí)行的觸發(fā)條件。

2 連續(xù)時(shí)間馬爾可夫決策過(guò)程任務(wù)調(diào)度模型

如圖2所示的多類(lèi)任務(wù)隊(duì)列的系統(tǒng)模型中根據(jù)任務(wù)達(dá)到的隨機(jī)特性，我們可以建立連續(xù)時(shí)間馬爾科夫決策過(guò)程模型[51]如下所示：

在模型中我們將任務(wù)到達(dá)本地移動(dòng)終端或任務(wù)被服務(wù)完成離開(kāi)服務(wù)器的這些時(shí)間點(diǎn)定義為決策時(shí)刻（decision time），而相應(yīng)的調(diào)度控制決策被稱(chēng)為行動(dòng)（actions）。

2.1 狀態(tài)空間

2.2 行動(dòng)空間

在系統(tǒng)中當(dāng)有任務(wù)到達(dá)或者被服務(wù)完成離開(kāi)時(shí)，本地移動(dòng)終端會(huì)對(duì)其自身內(nèi)的任務(wù)進(jìn)行調(diào)度控制決策?？紤]到實(shí)際生活中終端運(yùn)行時(shí)可能會(huì)達(dá)到最大負(fù)載，結(jié)合所設(shè)計(jì)的帶有有限長(zhǎng)度的隊(duì)列系統(tǒng)模型，用[d=di（s）]表示第[i]類(lèi)任務(wù)在當(dāng)前狀態(tài)下的行動(dòng)。

接下來(lái)，考慮到任務(wù)在本地移動(dòng)終端和云端服務(wù)器中服務(wù)的速率來(lái)自處理器的本身，所以可知任務(wù)在以上兩者中的處理速不變。針對(duì)不同任務(wù)的到達(dá)率進(jìn)行變化，對(duì)模型進(jìn)行求解，如圖4所示。從圖4可以看出針對(duì)不同的到達(dá)率，任務(wù)的平均等待調(diào)度時(shí)間（藍(lán)線(xiàn)），處理任務(wù)的平均花費(fèi)能耗代價(jià)（綠線(xiàn)）和最終的優(yōu)化目標(biāo)（紅線(xiàn)）其三者的運(yùn)動(dòng)曲線(xiàn)都向上移動(dòng)即最終的穩(wěn)定狀態(tài)值增大。

實(shí)驗(yàn)對(duì)不同的任務(wù)調(diào)度策略進(jìn)行仿真以做出對(duì)比性。如圖5所示為在不同策略下調(diào)度任務(wù)時(shí)，隨著任務(wù)的到達(dá)率的變化的代價(jià)效果圖的比較。由圖可看出本文所采用的算法最優(yōu) 。

5 總結(jié)

本文針對(duì)關(guān)聯(lián)性的混雜任務(wù)序列，建立具有順序相關(guān)性的任務(wù)隊(duì)列模型。針對(duì)任務(wù)的隨機(jī)性，在滿(mǎn)足任務(wù)的平均等待時(shí)間要求的前提下，將移動(dòng)終端對(duì)任務(wù)理或調(diào)度時(shí)產(chǎn)生的能耗作為優(yōu)化目標(biāo)，建立連續(xù)時(shí)間馬爾可夫決策過(guò)程系統(tǒng)模型。針對(duì)模型采用策略迭代算法對(duì)其進(jìn)行求解，以期望尋找到最優(yōu)策略使之既能滿(mǎn)足時(shí)間要求又能降低能耗，仿真驗(yàn)證算法的有效性。

參考文獻(xiàn)：

[1] 崔勇，宋健，繆蔥蔥，等. 移動(dòng)云計(jì)算研究進(jìn)展與趨勢(shì)[J].計(jì)算機(jī)學(xué)報(bào)，2017，40（2）：273-295.

[2] Huang D， Wu H. Mobile Cloud Computing：Foundations and Service Models[M]. 2018.

[3] Dinh H T， Lee C， Niyato D， et al. A survey of mobile cloudcomputing： architecture， applications， and approaches[J].Wireless Communications & Mobile Computing， 2013， 13（18）：15871611.

[4] 江琦， 路改香， 唐昊，等. 智能電網(wǎng)彈性響應(yīng)時(shí)間業(yè)務(wù)需求的接入控制 [J]. 控制與決策， 2014（7）：1311-1315.

[5] 江琦， 唐昊， 奚宏生. 無(wú)線(xiàn)多媒體接入網(wǎng)高能效的自適應(yīng)載頻開(kāi)啟控制 [J]. 系統(tǒng)科學(xué)與數(shù)學(xué)， 2014， 34（12）：1517-1526.

[6] Shahzad H， Szymanski T H. A dynamic programming offloading algorithm for mobile cloud computing[C]. Electrical and Computer Engineering， IEEE， 2016.

[7] Basu S， Pattnaik P K. A consistency preservation based approach for data-intensive cloud computing environment[C]. International Conference on Computing， Communication and Networking Technology ， IEEE Computer Society， 2017：1-5.

[8] Huang D， Wang P， Niyato D. A Dynamic offloading algorithm for mobile computing [J]. IEEE Transactions on Wireless Communications， 2012， 11（6）：1991-1995.

[9] 陸鳳山. 排隊(duì)論及其應(yīng)用[M].湖南：湖南科學(xué)技術(shù)出版社，1984.

【通聯(lián)編輯：王力】