邊緣計算中基于馬爾可夫決策過程的數據分流時間優化

楊桂松，候 玲，何杏宇

1(上海理工大學 光電信息與計算機工程學院，上海 200093) 2(上海理工大學 出版印刷與藝術設計學院，上海 200093)

1 引 言

近年來，隨著物聯網的發展，據HIS markit預測，到2025年，物聯網設備將增長約750億臺[1].這些用于感知和傳輸數據終端設備數量的急速增長會導致在網絡中傳輸數據的急速增長，因而會增大網絡負載及數據傳輸時延.此外，隨著人工智能的不斷發展，深度學習需要GPU并行計算，耗費了大量的計算資源，產生大量的數據.因此，如何低時延高效率的處理數據成為當前研究的熱點.

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

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

針對上述工作存在的不足，本文在研究邊緣計算中數據分流的問題時，提出一種基于馬爾可夫決策過程的最優分流節點選擇策略來保證數據傳輸的同時達到優化分流時間的效果.首先，本文通過在邊緣層中部署微型蜂窩基站和WiFi AP作為分流節點，提出一個支持蜂窩和WiFi通信的網絡模型；然后，聯合考慮終端設備的位置以及上傳數據量的大小構建馬爾可夫決策過程模型；最后通過值迭代算法求解馬爾可夫決策過程模型，得到最優分流節點選擇策略.通過與兩個對比實驗比較，實驗結果顯示：本文提出的最優分流節點選擇策略在優化分流時間的效果上有明顯提升.

2 系統模型

2.1 網絡模型

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

圖1 網絡模型Fig.1 Network model

在終端層，終端設備在移動的過程中產生需要上傳的數據.這些數據之間的拓撲結構可以是線性、樹狀或網格等形式，考慮到分流數據可順序分流這一事實[13]，因此，在本文中，終端設備以線性的方式順序分流數據.邊緣層中共部署由微型蜂窩基站和WiFi AP組成的M個邊緣設備.其中，這兩種邊緣分別支持蜂窩通信和WiFi通信技術，對于支持不同的通信技術的邊緣設備，其無線通信半徑與網絡傳輸速率不同.

2.2 馬爾科夫決策過程模型

在如圖1所示的網絡模型中，考慮到終端設備的位置和上傳數據量的大小都具有不確定性，而馬爾科夫決策過程是一種有效的數學模型，它能用來在不確定的動態系統中做出最優的序列決策.因此，本文將最優分流節點選擇問題建模成馬爾科夫決策過程模型.

馬爾科夫決策過程模型由5個元素組成：決策時期、狀態空間、動作集、轉換概率、回報函數.

1)決策時期T:決策時期表示終端設備選擇分流節點的時間，每一個決策時期的時長為Te.

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

(1)

其中，k表示終端設備需要執行數據分流的次數.

2)狀態空間S：狀態空間由終端設備選擇的分流節點編號、上傳數據量大小及終端設備當前所處位置的網格編號組成，定義如下:

S=N×F×L

(2)

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

3)動作集A：在一個決策時期t內，終端設備根據當前狀態，從動作集A中選擇一個動作a來分流數據.行為集定義如下:

(3)

4)轉換概率P：給定當前狀態s=[Ni,Fj,Ll]以及選定的動作a,轉換到下一個狀態s′=[N′i,F′j,L′l]的概率，定義如下:

(4)

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

(5)

其中，μ是位置穩定概率，0≤μ≤1，它表示終端設備在兩個連續決策時期定位在同一個網格內的概率.相應地，終端設備會以概率ρ隨機移動到相鄰格子.ρ的具體計算公式如下:

ρ=(1-μ)/g

(6)

其中，g表示與當前格子Ll相鄰的格子L′l的數目.

對于終端設備需分流的數據量大小的變化概率，定義如下:

(7)

P[F′j|Fj]表示終端設備上傳數據量從Fj轉換到F′j的概率.其中，ri表示終端設備選中的分流節點的數據傳輸率.

5)回報函數f:終端設備在當前狀態s選擇一個動作a后，將得到一個與分流時間相關的回報函數f(s,a).

(8)

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

當選擇的分流節點是WiFi AP:

(9)

當選擇的分流節點是微型蜂窩基站:

(10)

其中，Fj表示上傳數據量大小.微型蜂窩基站的通信半徑是Rci，數據傳輸率是rci；WiFi AP的通信半徑是Rwi，數據傳輸率是rwi.d表示終端設備和分流節點之間的距離.

3 基于MDP的最優分流節點選擇策略

這一節重點將介紹通過值迭代算法求解MDP模型得到最優分流節點選擇策略的過程.基于MDP的最優分流節點選擇策略的目的是在k次上傳數據分流的過程中，從M個分流節點中選擇最優的分流節點分流數據以達到優化分流時間的效果.

在求解的過程中，值函數vπ(s)用來表示當初始狀態為s，采用分流節點選擇策略π時得到的回報值.該回報值由當前決策時期的立即回報以及接下來的每個決策時期產生的未來回報之和表示.

(11)

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

特別地，由于基于MDP的最優分流節點選擇策略的目的是優化分流時間，所以，v(s)用來表示在初始狀態s下，從所有的分流節點選擇策略∏中得出的最優分流時間.

(12)

上式用貝爾曼方程[15]表達為:

(13)

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

(14)

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

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

算法1.基于MDP的最優分流節點選擇策略

輸入：決策時期、狀態空間、動作集、轉換概率、回報函數

輸出：最優分流節點選擇策略

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)//根據公式(13)、公式(14)

4 實驗以及結果分析

4.1 實驗環境

為評估基于MDP的分流節點選擇策略在優化分流時間上的性能，使用仿真軟件在超級計算中心曙光 TC4600E 百億次超級計算系統上進行100次實驗.實驗環境如表1所示.

表1 實驗環境Table 1 Lab environment

4.2 實驗參數

實驗參數如表2所示.

4.3 實驗分析

本文提出基于MDP的分流節點選擇策略(MDP)，選擇最優分流節點來優化分流時間.為評估本文所提策略在優化分流時間上的性能，本文采用兩個對比實驗對實驗結果進行比較分析.

基準算法為隨機分流節點選擇策略(Random)[17]和優先WiFi分流節點選擇策略(OTSO)[18].其中，Random采用隨機的思想，從能與終端設備進行通信的分流節點中隨機選擇分流節點分流數據.OTSO在選擇分流節點時，終端用戶一旦能與WiFi AP通信，便選擇WiFi AP節點分流數據.

表2 實驗參數Table 2 Lab parameters

本文所提算法為基于MDP的分流節點選擇策略(MDP)，終端設備根據該策略選擇分流節點分流數據.具體來說，算法首先通過2.1節中的網絡模型確定狀態空間和動作集.根據終端設備選擇的動作，考慮終端設備位置和需要分流的數據量大小的變化，根據公式(4)計算不同狀態之間的轉換概率，得到轉換概率矩陣.通過轉換概率矩陣和回報函數，根據公式(11)求出每一種狀態下的回報值，得到回報值表.最終通過迭代回報值表中的回報值，選擇每一種策略下最小的回報值，得到最優分流節點選擇策略.在數據分流完成之前，終端設備在分流數據時，在給定狀態下，根據最優分流節點選擇策略，選擇最優的分流節點分流數據.

根據2.2節中的理論分析，本文分別考慮位置穩定概率、上傳數據量大小和分流節點個數對分流時間的影響進行實驗，并將100次實驗結果取平均值用于實驗結果展示.

a)位置穩定概率對分流時間的影響

圖2 位置穩定概率對分流時間的影響Fig.2 Iinfluence of position stability probability on offloading time

圖2描述了在3種分流節點選擇策略中，終端設備的位置穩定概率變化對分流時間的影響.從圖2 可知，上傳數據的分流時間隨終端設備的位置穩定概率增加而減少.這是因為當終端設備的位置趨于穩定時，通過分析公式(6)可知：當終端設備移動到其他網格的概率降低時，公式(13)對分流時間的計算的準確率提高，因而選擇最優分流節點的的準確率提高，減少數據分流時間.另外，比較3種分流節點選擇策略，MDP在優化分流時間的性能上一直優于Random和OSTO.這是因為如算法1中的步驟b)所示，MDP會考慮到終端設備位置的變化來選擇分流節點.因此，即使當終端設備的位置穩定概率為0.1時，相比于Random和OSTO，MDP優化分流時間的效果仍能提高18%和22%.

b)上傳數據量對分流時間的影響

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

圖3 數據量對分流時間的影響Fig.3 Influence of data size on offloading time

c)分流節點個數對分流時間的影響.

考慮到不同場景中微蜂窩基站和WiFi AP部署情況存在差異，在這一節中分別在WiFi AP：微蜂窩基站=1∶1，WiFi AP：微蜂窩基站=1∶2，WiFi AP：微蜂窩基站=2∶1這3種節點比例的環境下進行實驗.圖4、圖5和圖6分別描述了在不同的節點比例下，分流節點個數的變化對分流時間的影響.從3張圖中可以看出，當分流節點的個數增多時,MDP分流時間呈下降趨勢，而Random和OSTO這兩種分流節點選擇策略的分流時間平均是MDP的2-4倍.這是因為，從公式(2)可知，分流節點的增多會擴大MDP的狀態空間，在進行分流節點選擇時，MDP能進一步優化分流節點的選擇，進而優化分流時間.因此當節點個數增多時，采用MDP分流策略得到的分流時間會減少.

當分流節點的比例變化時，從圖4可以看出，當節點比例為1∶1時，Random和OSTO的分流時間隨著分流節點的增多而增大.這是因為，當分流節點增多時，Random和OSTO可用來分流數據的分流個數增多.這增加了Random和OSTO選擇分流節點的盲目性，使分流時間呈上升趨勢.從圖5可以看出，當節點比例為1∶2時，即：部署的WIFI AP個數少于微蜂窩基站個數時，Random算法優化分流時間的效果明顯優于OSTO.這是因為，Random選擇分流節點時不考慮分流節點支持的通信技術的區別，這增大了Random選出最優分流節點的概率，有利于提升優化分流時間的效果.從圖6中可以看出，當WIFI AP節點個數多于微蜂窩基站個數時，OTSO優化分流時間的效果大幅度的提高.特別是當節點個數大于24

圖4 節點比例為1∶1時分流節點個 數對分流時間的影響Fig.4 Influence of the number of offloading nodes on the offloading time when the node ratio is 1∶1

圖5 節點比例為1∶2時分流節點個 數對分流時間的影響Fig.5 Influence of the number of offloading nodes on the offloading time when the node ratio is 1∶2

圖6 節點比例為2∶1時分流節點個 數對分流時間的影響Fig.6 Influence of the number of offloading nodes on the offloading time when the node ratio is 2∶1

時，OTSO的最小化分流時間的效果優于Random.這是因為，當分流節點個數增多，WiFi AP：微蜂窩基站=2∶1時，邊緣層中WiFi AP個數的增多能彌補OTSO在選擇分流節點時不考慮通信距離的缺陷，并且由于WiFi的傳輸速率快，因此當WiFi AP個數增多時，優化分流時間的效果更佳.

5 結束語

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