薛 寧 霍 如 劉 江

1 北京工業(yè)大學(xué)北京未來網(wǎng)絡(luò)科技高精尖創(chuàng)新中心 北京 100124

2 北京郵電大學(xué)網(wǎng)絡(luò)與交換技術(shù)國家重點(diǎn)實(shí)驗(yàn)室 北京 100876

引言

近年來，移動(dòng)互聯(lián)網(wǎng)和物聯(lián)網(wǎng)兩大網(wǎng)絡(luò)得到了快速發(fā)展，對(duì)網(wǎng)絡(luò)的時(shí)延、可靠性提出了更高的要求，而移動(dòng)邊緣計(jì)算(Mobile-edge Computing，MEC)由于其靠近用戶的特性，可以為用戶提供更低時(shí)延、更可靠的網(wǎng)絡(luò)體驗(yàn)[1]。在移動(dòng)邊緣計(jì)算的場(chǎng)景下，用戶和服務(wù)器的距離很近，數(shù)據(jù)的傳輸速率會(huì)很快，在處理任務(wù)時(shí)既可以利用服務(wù)器強(qiáng)大的計(jì)算能力又可以節(jié)省移動(dòng)設(shè)備的資源消耗。因此，移動(dòng)設(shè)備更傾向于向MEC服務(wù)器遷移任務(wù)從而提高任務(wù)的執(zhí)行性能，降低任務(wù)在移動(dòng)設(shè)備上的開銷。這種變化使得移動(dòng)設(shè)備計(jì)算任務(wù)的遷移算法變得十分重要。

學(xué)術(shù)界在任務(wù)遷移方面有一定的研究成果，文獻(xiàn)[2]將一個(gè)應(yīng)用劃分為一組有數(shù)據(jù)依賴關(guān)系的子任務(wù)，通過將子任務(wù)間共同需要的數(shù)據(jù)在移動(dòng)端和服務(wù)器各存一份的方式來減少傳輸能耗。但是，在真實(shí)環(huán)境中是無法預(yù)知子任務(wù)間共同需要的數(shù)據(jù)的。文獻(xiàn)[3-5]則提出對(duì)多個(gè)隨機(jī)任務(wù)的調(diào)度遷移策略進(jìn)行優(yōu)化，利用MDP理論、Lyapunov優(yōu)化算法以最小化移動(dòng)設(shè)備能耗和執(zhí)行時(shí)延為目標(biāo)來決策調(diào)度策略。然而在真實(shí)場(chǎng)景中部分任務(wù)需要和移動(dòng)設(shè)備進(jìn)行交互而必須在本地執(zhí)行，并且子任務(wù)之間是存在關(guān)聯(lián)性的，使得調(diào)度策略無法達(dá)到能耗和時(shí)延最小化的目標(biāo)。所以本文首先將應(yīng)用轉(zhuǎn)換為包含多個(gè)子任務(wù)的有向圖，從而表征應(yīng)用本身子任務(wù)間的內(nèi)在聯(lián)系，在此基礎(chǔ)上提出了一種基于貝葉斯網(wǎng)的隨機(jī)任務(wù)遷移算法，利用子任務(wù)之間的依賴關(guān)系預(yù)估每一個(gè)子任務(wù)執(zhí)行兩種遷移決策所產(chǎn)生的能耗，并得出每個(gè)子任務(wù)執(zhí)行兩種遷移決策的先驗(yàn)概率，最后根據(jù)先驗(yàn)概率以移動(dòng)設(shè)備能耗最小化為優(yōu)化目標(biāo)生成一組調(diào)度策略。

1 系統(tǒng)模型

本文考慮的MEC系統(tǒng)模型如圖1所示，包含一個(gè)移動(dòng)設(shè)備和一個(gè)MEC服務(wù)器。移動(dòng)設(shè)備是由遷移決策單元、本地處理單元和傳輸單元組成，移動(dòng)設(shè)備通過傳輸單元將一些計(jì)算密集型的計(jì)算任務(wù)遷移到MEC服務(wù)器上執(zhí)行，以解決移動(dòng)終端計(jì)算能力有限的問題。MEC服務(wù)器是一個(gè)部署在無線接入點(diǎn)處并安裝了小型數(shù)據(jù)中心的虛擬機(jī)設(shè)備，可以為移動(dòng)設(shè)備提供強(qiáng)大的IT服務(wù)[6]。

圖1 單用戶MEC系統(tǒng)場(chǎng)景圖

1.1 任務(wù)模型

圖2所展示的是一個(gè)應(yīng)用的細(xì)粒度任務(wù)劃分圖，本文將應(yīng)用劃分為多個(gè)獨(dú)立執(zhí)行的子任務(wù)，并用一個(gè)有向圖來表示[2]。圖2中的節(jié)點(diǎn)表示分割出來的子任務(wù)，圖2中的邊表示任務(wù)之間的傳輸數(shù)據(jù)，例如：表示任務(wù)執(zhí)行完成后，會(huì)傳輸?shù)臄?shù)據(jù)給任務(wù)而任務(wù)只有在接受到任務(wù)執(zhí)行完后傳輸過來的數(shù)據(jù)，才能開始執(zhí)行。圖2中的子任務(wù)可以分成兩類：一類是必須本地執(zhí)行的任務(wù)，如圖中的實(shí)心任務(wù)0、5表示為另一類為可遷移任務(wù)，如圖中的空心任務(wù)1、2、3、4，表示為

圖2 細(xì)粒度任務(wù)劃分圖

1.2 計(jì)算模型

由于執(zhí)行任務(wù)的能耗與任務(wù)在移動(dòng)設(shè)備執(zhí)行還是被遷移到MEC服務(wù)器執(zhí)行有關(guān)，所以本文定義表示任務(wù)執(zhí)行位置：

由于執(zhí)行任務(wù)的能耗與該任務(wù)的前置任務(wù)的執(zhí)行位置有關(guān)，當(dāng)此任務(wù)及其前置任務(wù)都在同一位置執(zhí)行時(shí)，兩個(gè)任務(wù)之間的數(shù)據(jù)傳輸消耗可以忽略不計(jì)。所以本文定義表示一個(gè)任務(wù)的前置任務(wù)的執(zhí)行位置和該任務(wù)的執(zhí)行位置：

假設(shè)移動(dòng)設(shè)備配備單核CPU和一個(gè)數(shù)據(jù)傳輸單元，執(zhí)行任務(wù)時(shí)CPU的頻率為其功率為空閑時(shí)CPU的功率為數(shù)據(jù)傳輸單元發(fā)送功率為發(fā)送速率為接收功率為接收速率為MEC服務(wù)器執(zhí)行任務(wù)時(shí)CPU的頻率為為任務(wù)的計(jì)算量，單位為(CPU cycles)。表示任務(wù)執(zhí)行完成后，會(huì)傳輸?shù)臄?shù)據(jù)給任務(wù)，單位為(bites)。

本文通過優(yōu)化任務(wù)調(diào)度的遷移策略來最小化執(zhí)行能耗，從而節(jié)約移動(dòng)設(shè)備的能耗。

2 隨機(jī)任務(wù)遷移算法

本節(jié)提出一種基于貝葉斯網(wǎng)絡(luò)的任務(wù)遷移算法，根據(jù)子任務(wù)之間的依賴關(guān)系構(gòu)造貝葉斯網(wǎng)，并求出最小化能耗的遷移策略。

2.1 貝葉斯網(wǎng)絡(luò)

貝葉斯網(wǎng)絡(luò)結(jié)合了圖論、概率論以及機(jī)器學(xué)習(xí)等理論和技術(shù)，是以有向無環(huán)圖的形式建模。用節(jié)點(diǎn)表示系統(tǒng)中的變量，用有向邊表示變量間的依賴關(guān)系。

貝葉斯網(wǎng)絡(luò)可以通過圖形化的方式對(duì)變量間的定量依賴關(guān)系進(jìn)行描述，在聯(lián)合概率分布中給各個(gè)變量均賦予一個(gè)特定值于是利用貝葉斯網(wǎng)絡(luò)中的各個(gè)節(jié)點(diǎn)所對(duì)應(yīng)的條件概率分布表，將所需的其他概率信息計(jì)算出來[8]。表示概率，則有：

貝葉斯網(wǎng)絡(luò)中節(jié)點(diǎn)之間的依賴關(guān)系由條件概率函數(shù)決定。每一個(gè)沒有父節(jié)點(diǎn)的節(jié)點(diǎn)都有一個(gè)先驗(yàn)概率分布。這些節(jié)點(diǎn)都具有各自的邊緣概率表，該邊緣概率表顯示相應(yīng)節(jié)點(diǎn)獨(dú)立的概率分布。邊緣概率表中的概率數(shù)值表示了相應(yīng)節(jié)點(diǎn)處于各個(gè)狀態(tài)的概率。每一個(gè)邊緣概率表中所有概率數(shù)值的和都為1。

每個(gè)具有父節(jié)點(diǎn)的節(jié)點(diǎn)都有相應(yīng)的條件概率函數(shù)，該條件概率函數(shù)表示父節(jié)點(diǎn)和子節(jié)點(diǎn)之間的條件概率關(guān)系。兩個(gè)節(jié)點(diǎn)之間的條件概率關(guān)系由條件概率表表示。條件概率表為子節(jié)點(diǎn)變量在給定父節(jié)點(diǎn)變量情況下的概率情況。

當(dāng)貝葉斯網(wǎng)絡(luò)建立后，通過一定的計(jì)算，可以獲得貝葉斯網(wǎng)絡(luò)內(nèi)變量之間的依賴關(guān)系以及變量的概率分布。由此，依據(jù)貝葉斯網(wǎng)絡(luò)中節(jié)點(diǎn)間的依賴關(guān)系以及變量的條件概率表，可以獲得聯(lián)合概率分布。此外，使用貝葉斯推理，可以利用已知的變量，通過貝葉斯網(wǎng)絡(luò)中節(jié)點(diǎn)間的連接，計(jì)算出其它未知變量的信息[8]。

2.2 基于貝葉斯網(wǎng)絡(luò)的遷移算法

根據(jù)應(yīng)用的任務(wù)劃分圖構(gòu)造一個(gè)貝葉斯網(wǎng)，每個(gè)子任務(wù)作為貝葉斯網(wǎng)的一個(gè)節(jié)點(diǎn)，根據(jù)子任務(wù)間的依賴關(guān)系構(gòu)造貝葉斯網(wǎng)中各個(gè)節(jié)點(diǎn)之間的依賴關(guān)系。在貝葉斯網(wǎng)中可將不可遷移任務(wù)對(duì)可遷移任務(wù)的調(diào)度決策的影響轉(zhuǎn)換為依賴前置任務(wù)的本地執(zhí)行概率和依賴后置任務(wù)的本地執(zhí)行概率，即當(dāng)某個(gè)子任務(wù)屬于不可遷移子任務(wù)，在對(duì)該子任務(wù)的前置子任務(wù)和后置子任務(wù)(均屬于可遷移子任務(wù))做調(diào)度時(shí)，考慮后置任務(wù)的執(zhí)行位置是更有利于得出最優(yōu)調(diào)度策略的。

當(dāng)任務(wù)v有前置任務(wù)u時(shí)，任務(wù)v和任務(wù)u的條件概率表分別如表1和表2所示。

表1 任務(wù)的條件概率表

表2 任務(wù)的條件概率表

表2 任務(wù)的條件概率表

根據(jù)構(gòu)造的貝葉斯網(wǎng)絡(luò)的依賴關(guān)系可以得出貝葉斯網(wǎng)的聯(lián)合概率：

由于有的任務(wù)被設(shè)定為必須在本地移動(dòng)設(shè)備上執(zhí)行的任務(wù)，所以圖2中的任務(wù)0、5可以表示為其他任務(wù)則利用聯(lián)合概率計(jì)算出每個(gè)任務(wù)在本地移動(dòng)設(shè)備執(zhí)行的概率，以任務(wù)1為例，其依賴前置任務(wù)時(shí)在本地執(zhí)行的概率為：

利用動(dòng)態(tài)規(guī)劃對(duì)上式進(jìn)行化解得：

任務(wù)1依賴后置任務(wù)時(shí)在本地執(zhí)行的概率：

利用動(dòng)態(tài)規(guī)劃對(duì)上式進(jìn)行化解得：

當(dāng)獲得任務(wù)v在本地移動(dòng)設(shè)備執(zhí)行的前置和后置概率后，若本地移動(dòng)設(shè)備執(zhí)行的前置和后置概率之和大于MEC服務(wù)器執(zhí)行的前置和后置概率之和，則任務(wù)v在本地移動(dòng)設(shè)備執(zhí)行，否則，則任務(wù)v遷移到MEC服務(wù)器執(zhí)行，計(jì)算式如下：

至此，可獲得一組次優(yōu)的遷移策略，然后對(duì)這組次優(yōu)遷移策略執(zhí)行一種弱窮舉算法，該弱窮舉算法認(rèn)為每一個(gè)位置的狀態(tài)與其他位置的狀態(tài)是不相干的，在進(jìn)行窮舉時(shí)，每次只改變某一個(gè)位置的狀態(tài)，并且在下一次窮舉時(shí)，上一次改變的狀態(tài)要恢復(fù)原樣。弱窮舉算法是為了解決原算法陷入局部最優(yōu)解的問題，通過改變每一個(gè)位置的狀態(tài)來跳出局部最優(yōu)解，并且弱窮舉算法具有低復(fù)雜度的特點(diǎn)，使得算法的能耗并沒有大幅增加。在本算法中執(zhí)行弱窮舉算法即依次在這組次優(yōu)遷移策略中選擇一個(gè)位置(該位置必須為可遷移任務(wù)所在位置)，將其替換為相反的遷移策略，再計(jì)算其總能耗，最后在所得的結(jié)果中選擇能耗最小的遷移策略為最終遷移策略。

根據(jù)上述的方法，對(duì)可遷移子任務(wù)逐個(gè)計(jì)算在本地移動(dòng)設(shè)備執(zhí)行的概率，并依據(jù)前置依賴和后置概率決定任務(wù)的執(zhí)行位置，再通過弱窮舉算法得出一組最小化能耗的最優(yōu)遷移策略。在計(jì)算最優(yōu)遷移策略時(shí)，需要遍歷整個(gè)任務(wù)拓?fù)鋱D，其時(shí)間復(fù)雜度為而通過窮舉法遍歷整個(gè)解空間來找到最優(yōu)解，由于所有解的數(shù)量為個(gè)，故窮舉法的時(shí)間復(fù)雜度為貝葉斯遷移算法的時(shí)間復(fù)雜度是常數(shù)級(jí)別的，而窮舉法的時(shí)間復(fù)雜度卻是指數(shù)級(jí)的。由此得出，貝葉斯遷移算法的時(shí)間復(fù)雜度遠(yuǎn)小于窮舉法，極大地減小了計(jì)算量。

3 仿真結(jié)果

在本節(jié)中，對(duì)提出的算法在python環(huán)境中進(jìn)行了編碼實(shí)現(xiàn)并且通過仿真實(shí)驗(yàn)對(duì)其性能進(jìn)行了評(píng)估。仿真場(chǎng)景是：一個(gè)移動(dòng)設(shè)備，一個(gè)搭載MEC服務(wù)器的基站，它們之間通過無線網(wǎng)絡(luò)連接。移動(dòng)設(shè)備和MEC服務(wù)器參數(shù)如表3所示。

表3 移動(dòng)設(shè)備和MEC服務(wù)器參數(shù)

為驗(yàn)證算法的有效性，引入3種基本的任務(wù)調(diào)度算法作為對(duì)比，包括隨機(jī)任務(wù)隨機(jī)遷移算法、MEC服務(wù)器遷移算法和移動(dòng)設(shè)備本地執(zhí)行算法[6]。與此同時(shí)，為驗(yàn)證算法魯棒性，仿真中構(gòu)建了10種不同的應(yīng)用，這些應(yīng)用的子任務(wù)數(shù)和子任務(wù)間的依賴關(guān)系均不相同，子任務(wù)構(gòu)造如表4所示，并且任務(wù)子模塊數(shù)據(jù)大小和任務(wù)的負(fù)載量服從均勻分布，即根據(jù)應(yīng)用的子任務(wù)劃分圖，將每個(gè)子任務(wù)作為貝葉斯網(wǎng)中的一個(gè)節(jié)點(diǎn)，按照子任務(wù)間的依賴關(guān)系構(gòu)造貝葉斯網(wǎng)中節(jié)點(diǎn)間的依賴關(guān)系。

表4 應(yīng)用子任務(wù)構(gòu)造表

圖3展示了1000個(gè)任務(wù)在不同任務(wù)遷移策略下的能耗，從圖4中可以看到隨著任務(wù)數(shù)的增加，移動(dòng)設(shè)備的能耗值呈線性增長，但是可以看到使用不同的遷移策略對(duì)能耗值的增加幅度的影響不同[10]。全部本地遷移策略由于其所有任務(wù)都在本地執(zhí)行，所以它的總能耗值是最高的。全部服務(wù)器遷移策略由于其所有可遷移任務(wù)都在服務(wù)器執(zhí)行，移動(dòng)設(shè)備的能耗只有傳輸能耗，所以它的總能耗值小于全部本地遷移策略的總能耗值。隨機(jī)遷移策略由于其遷移決策是隨機(jī)的，對(duì)能耗產(chǎn)生的影響時(shí)好時(shí)壞，所以它的總能耗值介于全部本地遷移策略的能耗值和全部服務(wù)器遷移策略的能耗值之間。貝葉斯遷移策略所得出的遷移策略近似于最優(yōu)解，所以它的總能耗值是最小的。

圖4展示了1000個(gè)任務(wù)在貝葉斯遷移策略和窮舉策略下的能耗，從圖4中可以觀察到在不同任務(wù)數(shù)下，貝葉斯遷移策略和窮舉策略的能耗值是幾乎重疊的。這說明了貝葉斯遷移策略雖然沒有遍歷整個(gè)解空間，但是最終得到的最優(yōu)解和窮舉策略得到的最優(yōu)解基本一致，這也證明了貝葉斯遷移策略在降低時(shí)間復(fù)雜度的同時(shí)對(duì)能耗的優(yōu)化效果沒有損失。

圖3 不同任務(wù)遷移策略能耗圖

圖4 貝葉斯遷移策略和窮舉策略能耗圖

4 結(jié)語

本文提出了在單用戶MEC系統(tǒng)中基于貝葉斯網(wǎng)絡(luò)的隨機(jī)任務(wù)遷移算法，通過將應(yīng)用轉(zhuǎn)換為包含多個(gè)子任務(wù)的有向圖，利用貝葉斯網(wǎng)絡(luò)中對(duì)子節(jié)點(diǎn)的概率計(jì)算方法來計(jì)算當(dāng)前子任務(wù)遷移決策的先驗(yàn)概率，然后根據(jù)概率以移動(dòng)設(shè)備能耗最小化為優(yōu)化目標(biāo)生成一組調(diào)度策略，最后利用弱窮舉算法對(duì)生成的調(diào)度策略進(jìn)行調(diào)整來得出最佳的調(diào)度策略。該算法在一個(gè)隨機(jī)任務(wù)到達(dá)時(shí)能夠以常數(shù)級(jí)別的時(shí)間復(fù)雜度找到該任務(wù)的近似最優(yōu)解，提高了優(yōu)化效率。仿真結(jié)果表明，該算法對(duì)大量任務(wù)的遷移決策是非常有效的，使能耗得到了大幅度的減少。未來的研究工作主要包括加入對(duì)多任務(wù)能耗的優(yōu)化、對(duì)移動(dòng)設(shè)備無線信道傳輸功率的控制等。