物聯網感知數據邊緣卸載機制研究*

袁培燕,耿麗娟,張 豪

(河南師范大學計算機與信息工程學院,河南 新鄉 453007)

1 引言

目前，可穿戴設備、智能家居和智慧醫療等物聯網應用發展迅速，產生了海量感知數據。如果將數據直接發送至云計算平臺，產生的流量會給當前的骨干網絡帶來沉重負擔。此外，傳感器和數據中心之間的距離會造成長時間的傳輸延遲，導致用戶體驗不好。相比之下，邊緣網絡設備逐漸具備一定的計算、存儲和通信能力，因此在邊緣設備附近處理物聯網設備的感知數據，可滿足物聯網應用海量數據分析的需求。在這種情況下，物聯網感知終端將數據發送至邊緣而不是云計算平臺，以減少骨干網絡流量。當感知數據到達時，邊緣節點負責處理數據，然后響應用戶或將處理后的結果發送至云端。

考慮到單個邊緣服務器計算資源有限，如果單獨處理收到的任務請求，過量的工作負載將導致一定的排隊延遲，影響用戶體驗。在這種情況下，假定計算任務可分割，則可將一部分任務卸載到云層進行處理。顯然，從邊緣服務器的角度出發，確定最優的邊緣卸載比例是一個值得關注的問題。本文以物聯網設備能耗為約束條件，最小化任務的卸載時間，具體來說：

(1)假定邊緣服務器設備可以使用本地計算資源處理其感知終端設備Di發送的工作負載的一部分為αi，1≤i≤n,n為物聯網中感知終端設備的數量,αi=0意味著將所有接收的工作負載轉發到云層。

(2)考慮邊緣服務器設備的計算功耗和物聯網應用設備的響應時間，將最優卸載比例問題表述為一個受能耗約束的響應時間最小化問題，然后使用序列二次規劃算法進行求解。求解出最小響應時間下的最優卸載比例αi。在此基礎上分析邊緣服務器設備單位時間內處理的最大工作負載μ對響應時間的影響。

本文的其余部分組織如下:第2節回顧相關的工作，第3節建立模型，第4節進行建模與求解，第5節進行仿真并對結果進行分析，第6節對全文進行總結。

2 相關工作

在邊緣計算中，對物聯網感知數據卸載的研究剛剛起步。大多數研究[1 - 3]是在數據卸載的過程中尋找一個中繼節點，中繼節點參與數據的傳輸，但不對數據做任何處理。例如，文獻[1]使用隨機線性網絡編碼來傳輸數據，當車輛進入路邊設備RSU(Road-Side Unit)的覆蓋范圍時，將編碼數據發送給RSU，RSU再將數據轉發給數據中心。文獻[3]使用移動節點來幫助傳感器收集感知數據，當移動節點進入傳感器的覆蓋范圍時，傳感器將數據發送給移動節點，移動節點再將數據傳輸至云端。此外，可以利用邊緣設備有限的計算資源，將全部數據優先卸載到邊緣設備中進行處理。如文獻[4]提出一種計算卸載架構，利用資源受限的物聯網設備附近的可用計算資源，優先將任務轉移到附近有空閑資源的邊緣網絡設備上。文獻[5]提出了一種基于寬帶約束的局部物聯網分流技術，充分利用網關資源提高帶寬的使用效率，降低系統能耗。文獻[6]提出一種數據上傳框架PTDU(Pu- blic Transit Data Uploading)，利用PTS(Public Transit System)的優勢，將PTS作為傳送數據的中繼節點。文獻[7]為了提高數據傳輸的可靠性和處理速度，提出了一種基于簡化變量鄰域搜索的傳感器數據處理框架。

需要指出的是，考慮到邊緣設備的計算資源和存儲資源有限，并不是所有的傳感器數據都可以在邊緣服務器進行本地處理。為了更好地提供服務，邊緣服務器卸載數據的比例也成為研究的重點。文獻[8]將排隊系統分為表征局部隊列和遠程隊列2類，考慮2類隊列狀態信息對計算卸載的影響，構造了一個多變量決策框架優化計算約束的MEC系統的延遲性能。文獻[9]將聯合負載均衡與卸載問題轉換為一個混合整數非線性規劃問題，以使系統效用最大化，通過聯合優化選擇決策、卸載和計算資源，提出了一種低復雜度的聯合優化算法。文獻[10]通過聯合優化智能移動設備的計算速度、傳輸功率和卸載比例來研究部分計算卸載問題，并擴展到多個云服務器系統。文獻[11]考慮到網絡的利用率，提出了一種基于網絡利用率和卸載偏好來確定卸載比例的卸載算法。文獻[12]提出了基于吸引子的能夠自適應選擇最優卸載比例的算法。該算法基于吸引子活動自適應地調整卸載比例，能快速、自適應地對環境變化做出響應。

3 系統模型構架

本文考慮3層邊緣計算架構場景，如圖1所示，該場景包含n個物聯網感知終端，基站與邊緣服務器相連。由于物聯網設備不具備數據處理能力，故其數據需上傳至邊緣服務器進行處理。受計算能力和存儲能力的限制，邊緣服務器只能處理部分數據，其余的數據需傳輸至遠程數據中心進行遠端處理。

Figure 1 Single cell edge calculation scenario

假設每一個物聯網感知終端設備Di(1≤i≤n)傳輸到其通信范圍內的邊緣服務器的任務負載到達率為λi(如果在其通信半徑內有多個邊緣服務器，感知終端設備選擇距離最近的一個進行傳輸，則由自由空間傳播模型可知，其信噪比相對較大)，且λi為常量。由于任務負載可分割，用αi表示Di傳輸到某個邊緣服務器的任務負載的比例。αi=1，表示邊緣服務器處理所有的任務負載；αi=0，表示邊緣服務器將所有的任務負載轉發至云層數據中心進行處理。

4 問題建模與求解

4.1 問題的建模

本文的目標是考慮卸載比例與訪問延遲之間的關系，并在能耗約束下使用戶的訪問延遲達到最小，使系統性能達到最優。考慮到2個性能指標：物聯網應用的響應延遲和邊緣服務器的能量消耗。邊緣服務器單位時間的能耗表示如式(1)所示：

(1)

該指標表示邊緣服務器卸載每單位任務負載所花費的能量，即邊緣服務器卸載每單位任務負載的電能消耗。邊緣服務器消耗的總功耗取決于靜態功耗Ws和動態功耗Wd，靜態功耗又稱泄露功耗，主要是由泄露電流引起的，與邊緣服務器計算資源的使用無關，動態功耗由計算資源的使用決定[13]。

邊緣服務器的能耗效率η表示為：

(2)

響應時延主要包括感知終端設備與邊緣服務器之間傳輸任務負載的往返時延和任務負載在邊緣服務器上處理時的逗留時間。設τi為任務負載在邊緣服務器與感知終端設備之間的平均往返時延。另外，本文假設邊緣服務器處理任務卸載請求屬于M/M/1排隊系統。由排隊論可知，其顧客源是無限的，且服從泊松分布。假設所有設備的任務負載到達率平均值為λ，邊緣服務器單位時間的最大處理能力為μ。任務在系統中的逗留時間(包括等待時間和處理時間)則服從參數為(μ-λ)的負指數分布，在系統中任務負載的平均逗留時間為1/(μ-λi)。本文處理任務負載包括以下3種情況：

(1)αi=0。

此時邊緣服務器通過骨干網絡直接將接收到的所有任務負載全部轉發到云數據中心。由于云數據中心通常配置高性能任務負載處理單元，處理任務負載的響應時間要比任務負載傳輸的時間短得多，因此假設云數據中心處理每個邊緣服務器轉發的任務負載所造成的延遲可以忽略不計。在此種情況下，物聯網感知終端應用的平均響應延遲表示可如式(3)所示:

Ti(αi)=τi+τc

(3)

其中，τc為邊緣服務器與云層之間傳輸單位任務負載的往返時間。邊緣服務器沒有使用任何計算資源來處理其接收到的任務負載，所以能量消耗將不依賴于物聯網應用的響應延遲，故式(3)為邊緣服務器向應用提供的響應延遲的閾值。

(2)αi=1。

邊緣服務器使用本地資源獨立處理接收的所有任務負載。在這種情況下，云數據中心不參與任務負載的處理，故物聯網應用響應延遲只包括物聯網感知終端與邊緣服務器之間的傳輸延遲和在邊緣服務器上處理所用的時間。此時Di與邊緣服務器之間的平均響應時延Ti可表示如式(4)所示：

(4)

(3) 0<αi<1。

此時應用的平均響應延遲為：

(5)

本文的主要目標是在給定的能耗功率約束下，設計分配任務負載策略，使物聯網應用的平均響應時延Ti最小化，即：

(6)

4.2 問題求解

本文的優化問題可具體表示如式(7)所示：

(7)

式(7)中的目標函數的一階導數為：

(8)

(9)

由于Pi>0，目標函數的一階導數存在且二階導數大于零，滿足凸函數的判定條件[14],故優化問題在定義域內存在最優解。

(10)

(11)

令C和H分別表示目標函數的一階導數和二階導數，令B和A分別表示函數g和g的一階導數組成的向量。有:

(12)

即二次規劃問題的一般形式為：

s.t.AS≤B

(13)

有效集算法可以求解此二次規劃問題的一般形式。由定理1知[15]，可構造一個集合序列逼近有效集，從初始可行點S0出發計算有效集Q(S0)，解對應的等式約束子問題。重復上述過程，得到有效集序列{Q(Sk)},k=0,1,…，求得一般形式二次規劃問題的最優解。

定理1設S*是一般凸二次規劃問題的全局極小點，且在S*處的有效集為Q(S*)=E∪I(S*)，則S*也是下列等式約束凸二次規劃的全局極小點。

s.t.ahS-bh=0,h∈Q(S*)

(14)

其中,集合E和集合I(S*)分別是指等式約束集和不等式約束集，ah和bh均為等式約束中的系數。

s.t.ahd=0,h∈Q(Sk)

(15)

其拉格朗日函數形式為：

(16)

其中，β為拉格朗日乘子。

令式(16)的一階導數為零，可求得函數L(d,β)的解。

基于上述分析，有效集算法的步驟如算法1所示。

算法1求解二次規劃子問題的有效集

1：Initializek=0,S0∈R;

2：Solve the subproblem described by equation (14), SetQk=E∪I(Sk);

3：Solve equation(16)to get the minimumdkequation and the Lagrange multiplierβk;

4：ifdk≠0then

5：gotoline 15;

6：else

7：gotoline 9;

8：endif

10：if(βk)t≥0 then

11：Skis the global minimum point;

12：else

13： Select one constraint that makes theβksmaller than zero,gotoline 2;

14：endif

16：iflk=1 then

17：Qk+1=Qk;

18：else//lk<1

19：Qk+1=Qk∪{jk};

20：endif

21：k=k+1;gotoline 2;

綜上，序列二次規劃(SQP)算法的迭代步驟如算法2所示。

算法2序列二次規劃

3:The optimal solutionS*is obtained from Algorithm 1, then letSk=S*;

7：else

8：gotoline 10;

9：endif

10：Fix Hessian matrixHk+1;Letk=k+1;gotostep 2;

5 仿真結果

圖2表示當邊緣服務器μ=100時，平均響應延遲Ti與卸載比例αi之間的關系。由圖2可知,平均響應延遲隨卸載比例的增大而減小，當任務負載到達率大大超過邊緣服務器的處理速率時，由于長隊列延遲，平均響應時間呈指數增長。另一現象是隨著任務負載λ的逐漸增大，邊緣服務器的最優卸載比例α將逐漸減小，同時平均響應延遲也將逐漸增大。

Figure 2 Relationship between α and T

圖3顯示當任務負載到達率λ=100時，在邊緣服務器處理速率μ不同的條件下，平均響應延遲T與卸載比例α之間的關系。從圖3中可以看到，最優卸載比例與邊緣服務器處理速率μ呈正相關，平均響應延遲與μ則相反。特別地，當邊緣服務器的處理速率遠大于任務負載到達率時，最優卸載比例將為1，此時邊緣服務器將處理所有的任務負載，物聯網應用的平均響應延遲將達到最小值。

Figure 3 Relationship between α and T when λ=100

圖4顯示在邊緣服務器處理速率μ=150時，任務負載到達率和最優卸載比例之間的相關性。從圖4中可以看到，當任務負載到達率λ小于邊緣服務器處理速率μ時，邊緣服務器將處理所有任務負載；當任務負載到達率λ大于邊緣服務器處理速率μ時，二者負相關，即任務負載到達率越高，卸載比例越低。此外，圖5顯示了平均響應延遲T隨任務負載到達率λ的變化情況。在邊緣服務器處理速率不變的情況下，隊列延遲隨著數據量的增大而增加，應用的平均響應延遲也隨之增大。

Figure 4 Relationship between λ and α

Figure 5 Relationship between λ and T

以上都是在能量閾值一定的條件下，分析各參數對所提解決方案性能的影響。圖6和圖7是平均響應時延和卸載比例隨能量閾值的變化趨勢。實驗中設定邊緣服務器的處理速率μ=100，任務負載的到達率λ=150。從圖6中可以看到，隨著能量閾值的增加，卸載比例增大到一定值后便保持不變。出現這種現象的原因是任務負載在邊緣服務器上的卸載處理屬于M/M/1排隊模型，為使模型趨于穩定，邊緣服務器的處理速率必須大于任務負載到達率，即μ>λ，剩下的任務負載將由邊緣服務器上傳至云層數據中心處理。因此，當能量閾值增大到一定程度后，約束條件μ>λ起主要作用，此時卸載比例便不會隨能耗閾值的增大而增大。同樣地，在圖7中，由于卸載比例不能隨著能量閾值的增大而無限增大，應用的平均響應延遲也會減小到一定值后保持不變。

Figure 6 Relationship between η and α

Figure 7 Relationship between η and T

為了進一步驗證所提解決方案的性能，本文引入了以下2種基準測試方案。一種是沒有卸載(NO)方案，NO方案表示邊緣服務器不在本地卸載感知數據的情況，即α的值等于零。另一種是完全卸載(FO)方案，在FO方案中，所有的傳感器數據都是在邊緣服務器本地進行處理，即α=1。圖8顯示了3種方案中每種方案的平均響應延遲隨任務負載到達率的變化趨勢，其中PO表示本文提出的部分卸載方案。由于NO方案是將所有的任務負載上傳至云層處理，故其平均響應時延只包括單位任務負載的往返傳輸時間，由于網絡帶寬一定，不同的任務負載到達率的傳輸速率不同，因此單位時間的傳輸延遲與任務負載到達率成正比。因此，可以把NO方案中的響應延遲作為物聯網應用響應延遲的上限。值得注意的是FO方案，當任務負載到達率λ大于邊緣服務器的處理速率μ=150時，根據M/M/1排隊模型應用的平均響應延遲趨于無限。從圖8中可以明顯看出，當λ≥μ時，PO方案具有最佳的延遲性能。

Figure 8 Response time of three unloading schemes

6 結束語

本文研究了移動邊緣場景下物聯網應用終端設備感知數據量的最優卸載比例問題。考慮了2個性能指標：邊緣服務器的平均響應延遲和能量消耗。通過將這2個指標表示為一個最小化問題，利用序列二次規劃算法給出了該問題的最優解。本文分析了不同任務負載到達率對最優卸載比例和訪問延遲的影響，并將提出的解決方案與基準方案進行了對比。仿真結果表明，本文所提方案在任務負載到達率大于邊緣服務器處理速率的情況下具有最佳的延遲性能。