袁培燕,耿麗娟,張 豪

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

1 引言

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

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

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

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

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

2 相關(guān)工作

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

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

3 系統(tǒng)模型構(gòu)架

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

Figure 1 Single cell edge calculation scenario

假設(shè)每一個物聯(lián)網(wǎng)感知終端設(shè)備Di(1≤i≤n)傳輸?shù)狡渫ㄐ欧秶鷥?nèi)的邊緣服務(wù)器的任務(wù)負載到達率為λi(如果在其通信半徑內(nèi)有多個邊緣服務(wù)器，感知終端設(shè)備選擇距離最近的一個進行傳輸，則由自由空間傳播模型可知，其信噪比相對較大)，且λi為常量。由于任務(wù)負載可分割，用αi表示Di傳輸?shù)侥硞€邊緣服務(wù)器的任務(wù)負載的比例。αi=1，表示邊緣服務(wù)器處理所有的任務(wù)負載；αi=0，表示邊緣服務(wù)器將所有的任務(wù)負載轉(zhuǎn)發(fā)至云層數(shù)據(jù)中心進行處理。

4 問題建模與求解

4.1 問題的建模

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

(1)

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

邊緣服務(wù)器的能耗效率η表示為：

(2)

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

(1)αi=0。

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

Ti(αi)=τi+τc

(3)

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

(2)αi=1。

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

(4)

(3) 0<αi<1。

此時應(yīng)用的平均響應(yīng)延遲為：

(5)

本文的主要目標是在給定的能耗功率約束下，設(shè)計分配任務(wù)負載策略，使物聯(lián)網(wǎng)應(yīng)用的平均響應(yīng)時延Ti最小化，即：

(6)

4.2 問題求解

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

(7)

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

(8)

(9)

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

(10)

(11)

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

(12)

即二次規(guī)劃問題的一般形式為：

s.t.AS≤B

(13)

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

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

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

(14)

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

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

(15)

其拉格朗日函數(shù)形式為：

(16)

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

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

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

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

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;

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

算法2序列二次規(guī)劃

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 仿真結(jié)果

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

Figure 2 Relationship between α and T

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

Figure 3 Relationship between α and T when λ=100

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

Figure 4 Relationship between λ and α

Figure 5 Relationship between λ and T

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

Figure 6 Relationship between η and α

Figure 7 Relationship between η and T

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

Figure 8 Response time of three unloading schemes

6 結(jié)束語

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