邊緣計(jì)算中基于馬爾可夫決策過(guò)程的數(shù)據(jù)分流時(shí)間優(yōu)化

楊桂松，候 玲，何杏宇

1(上海理工大學(xué) 光電信息與計(jì)算機(jī)工程學(xué)院，上海 200093) 2(上海理工大學(xué) 出版印刷與藝術(shù)設(shè)計(jì)學(xué)院，上海 200093)

1 引 言

近年來(lái)，隨著物聯(lián)網(wǎng)的發(fā)展，據(jù)HIS markit預(yù)測(cè)，到2025年，物聯(lián)網(wǎng)設(shè)備將增長(zhǎng)約750億臺(tái)[1].這些用于感知和傳輸數(shù)據(jù)終端設(shè)備數(shù)量的急速增長(zhǎng)會(huì)導(dǎo)致在網(wǎng)絡(luò)中傳輸數(shù)據(jù)的急速增長(zhǎng)，因而會(huì)增大網(wǎng)絡(luò)負(fù)載及數(shù)據(jù)傳輸時(shí)延.此外，隨著人工智能的不斷發(fā)展，深度學(xué)習(xí)需要GPU并行計(jì)算，耗費(fèi)了大量的計(jì)算資源，產(chǎn)生大量的數(shù)據(jù).因此，如何低時(shí)延高效率的處理數(shù)據(jù)成為當(dāng)前研究的熱點(diǎn).

為緩解由于數(shù)據(jù)增長(zhǎng)帶來(lái)的網(wǎng)絡(luò)負(fù)載過(guò)大以及處理時(shí)間長(zhǎng)的問(wèn)題，最直接的方法是升級(jí)網(wǎng)絡(luò)以提升網(wǎng)絡(luò)容量和網(wǎng)絡(luò)傳輸速率[2].但是由于升級(jí)網(wǎng)絡(luò)設(shè)備存在部署和成本問(wèn)題，許多研究者開(kāi)始研究通過(guò)數(shù)據(jù)分流來(lái)解決數(shù)據(jù)傳輸時(shí)延大的問(wèn)題.隨著云計(jì)算的出現(xiàn)，終端設(shè)備能將數(shù)據(jù)上傳到云端處理，以滿足數(shù)據(jù)對(duì)截止時(shí)間敏感的需求[3].但由于云端與終端設(shè)備之間距離較遠(yuǎn)，這會(huì)增加數(shù)據(jù)的傳輸時(shí)間，降低網(wǎng)絡(luò)服務(wù)質(zhì)量.近年來(lái)，邊緣計(jì)算作為一種新型的網(wǎng)絡(luò)結(jié)構(gòu)被提出，用來(lái)解決云端與終端設(shè)備距離遠(yuǎn)的問(wèn)題.邊緣計(jì)算是指將原有云計(jì)算中心的部分或全部任務(wù)遷移到數(shù)據(jù)源的附近執(zhí)行[4].

在邊緣計(jì)算中進(jìn)行數(shù)據(jù)分流時(shí)，分流節(jié)點(diǎn)是指被終端設(shè)備選擇用于數(shù)據(jù)分流的邊緣設(shè)備，如何選擇最優(yōu)的分流節(jié)點(diǎn)是低時(shí)延高效率處理數(shù)據(jù)的關(guān)鍵.在文獻(xiàn)[5]中，作者在蜂窩網(wǎng)絡(luò)和無(wú)線局域網(wǎng)的環(huán)境中，提出基于深度強(qiáng)化學(xué)習(xí)技術(shù)的最優(yōu)分流策略，結(jié)合神經(jīng)網(wǎng)絡(luò)和Q-learning算法選擇分流節(jié)點(diǎn)以達(dá)到同時(shí)分流多種數(shù)據(jù)的效果，但由于傳統(tǒng)宏蜂窩基站會(huì)存在弱信號(hào)質(zhì)量問(wèn)題[6].在文獻(xiàn)[7]借助小型蜂窩基站輔助的方法來(lái)提供高吞吐率和高可靠性的網(wǎng)絡(luò)連接，聯(lián)合優(yōu)化吞吐率和傳輸功率，并采用垂直分解的方法實(shí)現(xiàn)大量智能設(shè)備的數(shù)據(jù)分流，但這項(xiàng)工作在設(shè)計(jì)分流方案時(shí)沒(méi)有考慮系統(tǒng)的不確定性.文獻(xiàn)[8]中，作者基于節(jié)點(diǎn)接觸形成的通信機(jī)會(huì)傳輸數(shù)據(jù)，借助機(jī)會(huì)傳輸與主動(dòng)部署感知網(wǎng)絡(luò)相結(jié)合的方式來(lái)滿足數(shù)據(jù)交換和數(shù)據(jù)收集的需求，但是它未關(guān)注節(jié)點(diǎn)之間的接觸概率.文獻(xiàn)[9]中，作者基于節(jié)點(diǎn)的接觸概率預(yù)測(cè)，通過(guò)區(qū)間數(shù)的不確定性理論和區(qū)間數(shù)比較方法，提出一種預(yù)測(cè)輔助的數(shù)據(jù)傳輸機(jī)制，以提高數(shù)據(jù)的傳輸成功率，但是這種預(yù)測(cè)方法依賴對(duì)歷史數(shù)據(jù)的統(tǒng)計(jì)分析，忽略了終端設(shè)備與環(huán)境之間的交互.文獻(xiàn)[10]中，作者基于馬爾科夫(MDP)決策過(guò)程，提出多路徑冗余傳輸調(diào)度算法，實(shí)現(xiàn)對(duì)關(guān)鍵數(shù)據(jù)的實(shí)時(shí)性傳輸，提高數(shù)據(jù)傳輸可靠性.該算法根據(jù)網(wǎng)絡(luò)當(dāng)前狀態(tài)對(duì)數(shù)據(jù)塊以及傳輸路徑數(shù)目進(jìn)行建模，來(lái)選擇當(dāng)前狀態(tài)下最優(yōu)的分流節(jié)點(diǎn)，但是未考慮數(shù)據(jù)量的大小對(duì)數(shù)據(jù)傳輸帶來(lái)的影響.在文獻(xiàn)[11]中，作者研究多個(gè)應(yīng)用程序產(chǎn)生的多流數(shù)據(jù)分流問(wèn)題，通過(guò)考慮多個(gè)文件剩余數(shù)據(jù)量大小，提出一種低時(shí)間復(fù)雜度的啟發(fā)式分流算法，滿足不同應(yīng)用程序的數(shù)據(jù)對(duì)不同截止時(shí)間的需求.但是這種分流策略沒(méi)有考慮終端設(shè)備的移動(dòng)性，而終端設(shè)備的位置變化會(huì)影響分流的效果.

針對(duì)上述工作存在的不足，本文在研究邊緣計(jì)算中數(shù)據(jù)分流的問(wèn)題時(shí)，提出一種基于馬爾可夫決策過(guò)程的最優(yōu)分流節(jié)點(diǎn)選擇策略來(lái)保證數(shù)據(jù)傳輸?shù)耐瑫r(shí)達(dá)到優(yōu)化分流時(shí)間的效果.首先，本文通過(guò)在邊緣層中部署微型蜂窩基站和WiFi AP作為分流節(jié)點(diǎn)，提出一個(gè)支持蜂窩和WiFi通信的網(wǎng)絡(luò)模型；然后，聯(lián)合考慮終端設(shè)備的位置以及上傳數(shù)據(jù)量的大小構(gòu)建馬爾可夫決策過(guò)程模型；最后通過(guò)值迭代算法求解馬爾可夫決策過(guò)程模型，得到最優(yōu)分流節(jié)點(diǎn)選擇策略.通過(guò)與兩個(gè)對(duì)比實(shí)驗(yàn)比較，實(shí)驗(yàn)結(jié)果顯示：本文提出的最優(yōu)分流節(jié)點(diǎn)選擇策略在優(yōu)化分流時(shí)間的效果上有明顯提升.

2 系統(tǒng)模型

2.1 網(wǎng)絡(luò)模型

邊緣計(jì)算中用于流量分流的網(wǎng)絡(luò)模型如圖1所示.其中，為方便描述，模型中使用網(wǎng)格的方式來(lái)描述終端設(shè)備和邊緣設(shè)備的位置.邊緣計(jì)算的網(wǎng)絡(luò)模型層次劃分為：“終端層-邊緣層-云層”.終端層由需要上傳數(shù)據(jù)的終端設(shè)備組成.終端設(shè)備具有移動(dòng)性，它在移動(dòng)過(guò)程中采用兩維無(wú)記憶移動(dòng)模型[12]，且在移動(dòng)時(shí)能實(shí)時(shí)上傳自己的位置；邊緣層是由微蜂窩基站和WiFi AP兩種分流節(jié)點(diǎn)組成.在邊緣層中，邊緣設(shè)備部署位置隨機(jī)且固定，每一個(gè)邊緣設(shè)備有唯一的編號(hào).云層中部署了能為終端設(shè)備提供全覆蓋的網(wǎng)絡(luò)通信保證的宏蜂窩基站，當(dāng)終端設(shè)備不在任何邊緣設(shè)備的通信范圍內(nèi)時(shí)，終端設(shè)備將數(shù)據(jù)分流到云層.由于本文云層只是作為補(bǔ)充手段，重點(diǎn)考慮在邊緣層中選擇分流節(jié)點(diǎn)分流數(shù)據(jù)，故在圖1中沒(méi)有顯示云層.

圖1 網(wǎng)絡(luò)模型Fig.1 Network model

在終端層，終端設(shè)備在移動(dòng)的過(guò)程中產(chǎn)生需要上傳的數(shù)據(jù).這些數(shù)據(jù)之間的拓?fù)浣Y(jié)構(gòu)可以是線性、樹(shù)狀或網(wǎng)格等形式，考慮到分流數(shù)據(jù)可順序分流這一事實(shí)[13]，因此，在本文中，終端設(shè)備以線性的方式順序分流數(shù)據(jù).邊緣層中共部署由微型蜂窩基站和WiFi AP組成的M個(gè)邊緣設(shè)備.其中，這兩種邊緣分別支持蜂窩通信和WiFi通信技術(shù)，對(duì)于支持不同的通信技術(shù)的邊緣設(shè)備，其無(wú)線通信半徑與網(wǎng)絡(luò)傳輸速率不同.

2.2 馬爾科夫決策過(guò)程模型

在如圖1所示的網(wǎng)絡(luò)模型中，考慮到終端設(shè)備的位置和上傳數(shù)據(jù)量的大小都具有不確定性，而馬爾科夫決策過(guò)程是一種有效的數(shù)學(xué)模型，它能用來(lái)在不確定的動(dòng)態(tài)系統(tǒng)中做出最優(yōu)的序列決策.因此，本文將最優(yōu)分流節(jié)點(diǎn)選擇問(wèn)題建模成馬爾科夫決策過(guò)程模型.

馬爾科夫決策過(guò)程模型由5個(gè)元素組成：決策時(shí)期、狀態(tài)空間、動(dòng)作集、轉(zhuǎn)換概率、回報(bào)函數(shù).

1)決策時(shí)期T:決策時(shí)期表示終端設(shè)備選擇分流節(jié)點(diǎn)的時(shí)間，每一個(gè)決策時(shí)期的時(shí)長(zhǎng)為Te.

T={1,2,…,t,…,k}

(1)

其中，k表示終端設(shè)備需要執(zhí)行數(shù)據(jù)分流的次數(shù).

2)狀態(tài)空間S：狀態(tài)空間由終端設(shè)備選擇的分流節(jié)點(diǎn)編號(hào)、上傳數(shù)據(jù)量大小及終端設(shè)備當(dāng)前所處位置的網(wǎng)格編號(hào)組成，定義如下:

S=N×F×L

(2)

其中，N=[N1,N2,…,Ni,…,NM]是一個(gè)M維數(shù)組,表示可用于分流數(shù)據(jù)的M個(gè)分流節(jié)點(diǎn).Ni∈{0,1},i=1，2，…，M.Ni=1表示終端設(shè)備在分流節(jié)點(diǎn)i的通信范圍內(nèi)，Ni=0表示終端設(shè)備不在分流節(jié)點(diǎn)i的通信范圍內(nèi).F=[F1,F2,…,Fj,…,Fk]是一個(gè)k維數(shù)組，表示終端設(shè)備在每個(gè)決策時(shí)期需要分流的數(shù)據(jù)量大小.L=[L1,L2,…,Ll,…,LG]是一個(gè)G維數(shù)組,表示終端設(shè)備所有可能移動(dòng)的G個(gè)網(wǎng)格的編號(hào).

3)動(dòng)作集A：在一個(gè)決策時(shí)期t內(nèi)，終端設(shè)備根據(jù)當(dāng)前狀態(tài)，從動(dòng)作集A中選擇一個(gè)動(dòng)作a來(lái)分流數(shù)據(jù).行為集定義如下:

(3)

4)轉(zhuǎn)換概率P：給定當(dāng)前狀態(tài)s=[Ni,Fj,Ll]以及選定的動(dòng)作a,轉(zhuǎn)換到下一個(gè)狀態(tài)s′=[N′i,F′j,L′l]的概率，定義如下:

(4)

其中，P(L′l|Ll)表示終端設(shè)備從格子Ll移動(dòng)到格子L′l的概率.

(5)

其中，μ是位置穩(wěn)定概率，0≤μ≤1，它表示終端設(shè)備在兩個(gè)連續(xù)決策時(shí)期定位在同一個(gè)網(wǎng)格內(nèi)的概率.相應(yīng)地，終端設(shè)備會(huì)以概率ρ隨機(jī)移動(dòng)到相鄰格子.ρ的具體計(jì)算公式如下:

ρ=(1-μ)/g

(6)

其中，g表示與當(dāng)前格子Ll相鄰的格子L′l的數(shù)目.

對(duì)于終端設(shè)備需分流的數(shù)據(jù)量大小的變化概率，定義如下:

(7)

P[F′j|Fj]表示終端設(shè)備上傳數(shù)據(jù)量從Fj轉(zhuǎn)換到F′j的概率.其中，ri表示終端設(shè)備選中的分流節(jié)點(diǎn)的數(shù)據(jù)傳輸率.

5)回報(bào)函數(shù)f:終端設(shè)備在當(dāng)前狀態(tài)s選擇一個(gè)動(dòng)作a后，將得到一個(gè)與分流時(shí)間相關(guān)的回報(bào)函數(shù)f(s,a).

(8)

其中，TWiFi和TCell分別表示選擇WiFi AP和微型蜂窩基站分流數(shù)據(jù)得到的分流時(shí)間.對(duì)于上傳數(shù)據(jù)的分流時(shí)間計(jì)算公式如下:

當(dāng)選擇的分流節(jié)點(diǎn)是WiFi AP:

(9)

當(dāng)選擇的分流節(jié)點(diǎn)是微型蜂窩基站:

(10)

其中，F(xiàn)j表示上傳數(shù)據(jù)量大小.微型蜂窩基站的通信半徑是Rci，數(shù)據(jù)傳輸率是rci；WiFi AP的通信半徑是Rwi，數(shù)據(jù)傳輸率是rwi.d表示終端設(shè)備和分流節(jié)點(diǎn)之間的距離.

3 基于MDP的最優(yōu)分流節(jié)點(diǎn)選擇策略

這一節(jié)重點(diǎn)將介紹通過(guò)值迭代算法求解MDP模型得到最優(yōu)分流節(jié)點(diǎn)選擇策略的過(guò)程.基于MDP的最優(yōu)分流節(jié)點(diǎn)選擇策略的目的是在k次上傳數(shù)據(jù)分流的過(guò)程中，從M個(gè)分流節(jié)點(diǎn)中選擇最優(yōu)的分流節(jié)點(diǎn)分流數(shù)據(jù)以達(dá)到優(yōu)化分流時(shí)間的效果.

在求解的過(guò)程中，值函數(shù)vπ(s)用來(lái)表示當(dāng)初始狀態(tài)為s，采用分流節(jié)點(diǎn)選擇策略π時(shí)得到的回報(bào)值.該回報(bào)值由當(dāng)前決策時(shí)期的立即回報(bào)以及接下來(lái)的每個(gè)決策時(shí)期產(chǎn)生的未來(lái)回報(bào)之和表示.

(11)

其中，E[·]是期望函數(shù)，它表示終端設(shè)備的初始狀態(tài)是s, 分流節(jié)點(diǎn)選擇策略是π時(shí)的期望值；ft(s,a)表示在決策時(shí)期t時(shí)，終端設(shè)備得到的立即回報(bào)；λ是折扣因子，用來(lái)衡量未來(lái)回報(bào)的重要程度，λ∈(0,1].λ越接近1，未來(lái)回報(bào)的權(quán)重越大[14].

特別地，由于基于MDP的最優(yōu)分流節(jié)點(diǎn)選擇策略的目的是優(yōu)化分流時(shí)間，所以，v(s)用來(lái)表示在初始狀態(tài)s下，從所有的分流節(jié)點(diǎn)選擇策略∏中得出的最優(yōu)分流時(shí)間.

(12)

上式用貝爾曼方程[15]表達(dá)為:

(13)

由于值迭代算法(VIA)的理論簡(jiǎn)單、易于編碼，因此，在本文中，運(yùn)用值迭代算法求解MDP模型得到基于MDP的最優(yōu)分流節(jié)點(diǎn)選擇策略.

(14)

一般來(lái)說(shuō)，值迭代算法的時(shí)間復(fù)雜度為O(|A||S|2)[16].其中，|S|和|A|分別表示狀態(tài)空間和動(dòng)作集的大小.值迭代算法在求解MDP模型時(shí)，首先輸入決策時(shí)期、狀態(tài)空間、動(dòng)作集、轉(zhuǎn)換概率、回報(bào)函數(shù).初始化階段，將所有狀態(tài)、動(dòng)作的回報(bào)值初始化為零，形成一個(gè)|S|行|A|列的全零矩陣.并將用于標(biāo)記迭代次數(shù)的x初始化為0，將閾值ε初始化為一個(gè)極小的正數(shù).迭代階段，在每一個(gè)決策時(shí)期，根據(jù)終端設(shè)備當(dāng)前的狀態(tài)以及可采取的動(dòng)作，通過(guò)MDP模型中的轉(zhuǎn)換概率，計(jì)算在當(dāng)前狀態(tài)下，選擇每一種動(dòng)作獲得的回報(bào)值.再在當(dāng)前狀態(tài)下，從選擇不同動(dòng)作得到的不同回報(bào)值中選出最小的回報(bào)值，用于下一階段的判斷及下一次的迭代.判斷階段，該階段通過(guò)計(jì)算上一階段的回報(bào)值vx+1(s)與上一次迭代的回報(bào)值vx(s)的差值，將差值與閾值進(jìn)行比較.若兩次的差值小于閾值，則返回最優(yōu)分流時(shí)間v(s)及最優(yōu)分流節(jié)點(diǎn)選擇策略π*(s)；否則，則用上一階段的回報(bào)值進(jìn)行下一次迭代.最終，當(dāng)值迭代算法終止時(shí)，算法1輸出基于MDP的最優(yōu)分流節(jié)點(diǎn)選擇策略.對(duì)于給定的狀態(tài)，終端設(shè)備能根據(jù)該策略選擇最優(yōu)的動(dòng)作分流數(shù)據(jù)達(dá)到優(yōu)化分流時(shí)間的效果.

值迭代算法的偽代碼介紹如下：

算法1.基于MDP的最優(yōu)分流節(jié)點(diǎn)選擇策略

輸入：決策時(shí)期、狀態(tài)空間、動(dòng)作集、轉(zhuǎn)換概率、回報(bào)函數(shù)

輸出：最優(yōu)分流節(jié)點(diǎn)選擇策略

a)初始化：?s∈S，?a∈A，vx(s)=0，x=0，ε>0

c)判斷:

如果vx+1(s)-vx(s)<ε，則返回d);

如果vx+1(s)-vx(s)>ε，則x=x+1,返回b)

d)返回:v(s)，π*(s)//根據(jù)公式(13)、公式(14)

4 實(shí)驗(yàn)以及結(jié)果分析

4.1 實(shí)驗(yàn)環(huán)境

為評(píng)估基于MDP的分流節(jié)點(diǎn)選擇策略在優(yōu)化分流時(shí)間上的性能，使用仿真軟件在超級(jí)計(jì)算中心曙光 TC4600E 百億次超級(jí)計(jì)算系統(tǒng)上進(jìn)行100次實(shí)驗(yàn).實(shí)驗(yàn)環(huán)境如表1所示.

表1 實(shí)驗(yàn)環(huán)境Table 1 Lab environment

4.2 實(shí)驗(yàn)參數(shù)

實(shí)驗(yàn)參數(shù)如表2所示.

4.3 實(shí)驗(yàn)分析

本文提出基于MDP的分流節(jié)點(diǎn)選擇策略(MDP)，選擇最優(yōu)分流節(jié)點(diǎn)來(lái)優(yōu)化分流時(shí)間.為評(píng)估本文所提策略在優(yōu)化分流時(shí)間上的性能，本文采用兩個(gè)對(duì)比實(shí)驗(yàn)對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行比較分析.

基準(zhǔn)算法為隨機(jī)分流節(jié)點(diǎn)選擇策略(Random)[17]和優(yōu)先WiFi分流節(jié)點(diǎn)選擇策略(OTSO)[18].其中，Random采用隨機(jī)的思想，從能與終端設(shè)備進(jìn)行通信的分流節(jié)點(diǎn)中隨機(jī)選擇分流節(jié)點(diǎn)分流數(shù)據(jù).OTSO在選擇分流節(jié)點(diǎn)時(shí)，終端用戶一旦能與WiFi AP通信，便選擇WiFi AP節(jié)點(diǎn)分流數(shù)據(jù).

表2 實(shí)驗(yàn)參數(shù)Table 2 Lab parameters

本文所提算法為基于MDP的分流節(jié)點(diǎn)選擇策略(MDP)，終端設(shè)備根據(jù)該策略選擇分流節(jié)點(diǎn)分流數(shù)據(jù).具體來(lái)說(shuō)，算法首先通過(guò)2.1節(jié)中的網(wǎng)絡(luò)模型確定狀態(tài)空間和動(dòng)作集.根據(jù)終端設(shè)備選擇的動(dòng)作，考慮終端設(shè)備位置和需要分流的數(shù)據(jù)量大小的變化，根據(jù)公式(4)計(jì)算不同狀態(tài)之間的轉(zhuǎn)換概率，得到轉(zhuǎn)換概率矩陣.通過(guò)轉(zhuǎn)換概率矩陣和回報(bào)函數(shù)，根據(jù)公式(11)求出每一種狀態(tài)下的回報(bào)值，得到回報(bào)值表.最終通過(guò)迭代回報(bào)值表中的回報(bào)值，選擇每一種策略下最小的回報(bào)值，得到最優(yōu)分流節(jié)點(diǎn)選擇策略.在數(shù)據(jù)分流完成之前，終端設(shè)備在分流數(shù)據(jù)時(shí)，在給定狀態(tài)下，根據(jù)最優(yōu)分流節(jié)點(diǎn)選擇策略，選擇最優(yōu)的分流節(jié)點(diǎn)分流數(shù)據(jù).

根據(jù)2.2節(jié)中的理論分析，本文分別考慮位置穩(wěn)定概率、上傳數(shù)據(jù)量大小和分流節(jié)點(diǎn)個(gè)數(shù)對(duì)分流時(shí)間的影響進(jìn)行實(shí)驗(yàn)，并將100次實(shí)驗(yàn)結(jié)果取平均值用于實(shí)驗(yàn)結(jié)果展示.

a)位置穩(wěn)定概率對(duì)分流時(shí)間的影響

圖2 位置穩(wěn)定概率對(duì)分流時(shí)間的影響Fig.2 Iinfluence of position stability probability on offloading time

圖2描述了在3種分流節(jié)點(diǎn)選擇策略中，終端設(shè)備的位置穩(wěn)定概率變化對(duì)分流時(shí)間的影響.從圖2 可知，上傳數(shù)據(jù)的分流時(shí)間隨終端設(shè)備的位置穩(wěn)定概率增加而減少.這是因?yàn)楫?dāng)終端設(shè)備的位置趨于穩(wěn)定時(shí)，通過(guò)分析公式(6)可知：當(dāng)終端設(shè)備移動(dòng)到其他網(wǎng)格的概率降低時(shí)，公式(13)對(duì)分流時(shí)間的計(jì)算的準(zhǔn)確率提高，因而選擇最優(yōu)分流節(jié)點(diǎn)的的準(zhǔn)確率提高，減少數(shù)據(jù)分流時(shí)間.另外，比較3種分流節(jié)點(diǎn)選擇策略，MDP在優(yōu)化分流時(shí)間的性能上一直優(yōu)于Random和OSTO.這是因?yàn)槿缢惴?中的步驟b)所示，MDP會(huì)考慮到終端設(shè)備位置的變化來(lái)選擇分流節(jié)點(diǎn).因此，即使當(dāng)終端設(shè)備的位置穩(wěn)定概率為0.1時(shí)，相比于Random和OSTO，MDP優(yōu)化分流時(shí)間的效果仍能提高18%和22%.

b)上傳數(shù)據(jù)量對(duì)分流時(shí)間的影響

圖3描述了當(dāng)上傳數(shù)據(jù)量大小變化時(shí)，采用3種不同的分流節(jié)點(diǎn)選擇策略分流數(shù)據(jù)得到的分流時(shí)間.從圖3中可以看出，當(dāng)上傳的數(shù)據(jù)量逐漸增大時(shí)，分流時(shí)間也隨之增大.這是因?yàn)?，在公?9)和公式(10)中，上傳數(shù)據(jù)量的大小正向影響數(shù)據(jù)的分流時(shí)間.另外，相比Random、OSTO這兩個(gè)策略，MDP在數(shù)據(jù)量逐漸增加時(shí)仍表現(xiàn)出了良好的性能，在分流時(shí)間的優(yōu)化上相較于Random、OSTO分別提高了30%和70%.這是因?yàn)镸DP在進(jìn)行分流節(jié)點(diǎn)的選擇過(guò)程中，綜合考慮到終端設(shè)備可能移動(dòng)的位置及上傳的數(shù)據(jù)量大小的變化.根據(jù)公式(4)計(jì)算系統(tǒng)轉(zhuǎn)換概率進(jìn)而計(jì)算選擇不同的分流節(jié)點(diǎn)上傳數(shù)據(jù)的分流時(shí)間，最終通過(guò)值迭代算法選擇能最小化分流時(shí)間的分流節(jié)點(diǎn).而OSTO的分流時(shí)間均大于其余兩個(gè)算法，這是因?yàn)镺STO優(yōu)先選擇支持WiFi通信的分流節(jié)點(diǎn)分流數(shù)據(jù).在這種情況下，OTSO未考慮終端設(shè)備與分流節(jié)點(diǎn)之間的距離，這會(huì)導(dǎo)致由于距離太長(zhǎng)而時(shí)延增大的問(wèn)題，因此，OTSO的分流時(shí)間最長(zhǎng).

圖3 數(shù)據(jù)量對(duì)分流時(shí)間的影響Fig.3 Influence of data size on offloading time

c)分流節(jié)點(diǎn)個(gè)數(shù)對(duì)分流時(shí)間的影響.

考慮到不同場(chǎng)景中微蜂窩基站和WiFi AP部署情況存在差異，在這一節(jié)中分別在WiFi AP：微蜂窩基站=1∶1，WiFi AP：微蜂窩基站=1∶2，WiFi AP：微蜂窩基站=2∶1這3種節(jié)點(diǎn)比例的環(huán)境下進(jìn)行實(shí)驗(yàn).圖4、圖5和圖6分別描述了在不同的節(jié)點(diǎn)比例下，分流節(jié)點(diǎn)個(gè)數(shù)的變化對(duì)分流時(shí)間的影響.從3張圖中可以看出，當(dāng)分流節(jié)點(diǎn)的個(gè)數(shù)增多時(shí),MDP分流時(shí)間呈下降趨勢(shì)，而Random和OSTO這兩種分流節(jié)點(diǎn)選擇策略的分流時(shí)間平均是MDP的2-4倍.這是因?yàn)?，從公?2)可知，分流節(jié)點(diǎn)的增多會(huì)擴(kuò)大MDP的狀態(tài)空間，在進(jìn)行分流節(jié)點(diǎn)選擇時(shí)，MDP能進(jìn)一步優(yōu)化分流節(jié)點(diǎn)的選擇，進(jìn)而優(yōu)化分流時(shí)間.因此當(dāng)節(jié)點(diǎn)個(gè)數(shù)增多時(shí)，采用MDP分流策略得到的分流時(shí)間會(huì)減少.

當(dāng)分流節(jié)點(diǎn)的比例變化時(shí)，從圖4可以看出，當(dāng)節(jié)點(diǎn)比例為1∶1時(shí)，Random和OSTO的分流時(shí)間隨著分流節(jié)點(diǎn)的增多而增大.這是因?yàn)?，?dāng)分流節(jié)點(diǎn)增多時(shí)，Random和OSTO可用來(lái)分流數(shù)據(jù)的分流個(gè)數(shù)增多.這增加了Random和OSTO選擇分流節(jié)點(diǎn)的盲目性，使分流時(shí)間呈上升趨勢(shì).從圖5可以看出，當(dāng)節(jié)點(diǎn)比例為1∶2時(shí)，即：部署的WIFI AP個(gè)數(shù)少于微蜂窩基站個(gè)數(shù)時(shí)，Random算法優(yōu)化分流時(shí)間的效果明顯優(yōu)于OSTO.這是因?yàn)?，Random選擇分流節(jié)點(diǎn)時(shí)不考慮分流節(jié)點(diǎn)支持的通信技術(shù)的區(qū)別，這增大了Random選出最優(yōu)分流節(jié)點(diǎn)的概率，有利于提升優(yōu)化分流時(shí)間的效果.從圖6中可以看出，當(dāng)WIFI AP節(jié)點(diǎn)個(gè)數(shù)多于微蜂窩基站個(gè)數(shù)時(shí)，OTSO優(yōu)化分流時(shí)間的效果大幅度的提高.特別是當(dāng)節(jié)點(diǎn)個(gè)數(shù)大于24

圖4 節(jié)點(diǎn)比例為1∶1時(shí)分流節(jié)點(diǎn)個(gè) 數(shù)對(duì)分流時(shí)間的影響Fig.4 Influence of the number of offloading nodes on the offloading time when the node ratio is 1∶1

圖5 節(jié)點(diǎn)比例為1∶2時(shí)分流節(jié)點(diǎn)個(gè) 數(shù)對(duì)分流時(shí)間的影響Fig.5 Influence of the number of offloading nodes on the offloading time when the node ratio is 1∶2

圖6 節(jié)點(diǎn)比例為2∶1時(shí)分流節(jié)點(diǎn)個(gè) 數(shù)對(duì)分流時(shí)間的影響Fig.6 Influence of the number of offloading nodes on the offloading time when the node ratio is 2∶1

時(shí)，OTSO的最小化分流時(shí)間的效果優(yōu)于Random.這是因?yàn)?，?dāng)分流節(jié)點(diǎn)個(gè)數(shù)增多，WiFi AP：微蜂窩基站=2∶1時(shí)，邊緣層中WiFi AP個(gè)數(shù)的增多能彌補(bǔ)OTSO在選擇分流節(jié)點(diǎn)時(shí)不考慮通信距離的缺陷，并且由于WiFi的傳輸速率快，因此當(dāng)WiFi AP個(gè)數(shù)增多時(shí)，優(yōu)化分流時(shí)間的效果更佳.

5 結(jié)束語(yǔ)

本文研究了邊緣計(jì)算中數(shù)據(jù)分流的問(wèn)題，提出基于MDP的最優(yōu)分流節(jié)點(diǎn)選擇策略.本文通過(guò)考慮到數(shù)據(jù)量變化和終端設(shè)備的位置變化，將分流節(jié)點(diǎn)選擇問(wèn)題建模成MDP模型，并通過(guò)VIA算法求解模型，得到最優(yōu)分流節(jié)點(diǎn)選擇策略.大量實(shí)驗(yàn)結(jié)果表明，相比于Random、OSTO兩個(gè)基準(zhǔn)算法，本文所提策略在優(yōu)化分流時(shí)間上的效果上的有效性.在未來(lái)的工作中，可以通過(guò)增加終端設(shè)備支持的通信技術(shù)(如：D2D通信)，綜合考慮終端設(shè)備傳輸數(shù)據(jù)時(shí)的能耗和成本等其他因素進(jìn)行更深入的研究.