袁培燕,耿麗娟,張 豪

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

1 引言

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

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

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

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

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

2 相關(guān)工作

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

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

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

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

Figure 1 Single cell edge calculation scenario

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

4 問題建模與求解

4.1 問題的建模

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

(1)

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

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

(2)

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

(1)αi=0。

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

Ti(αi)=τi+τc

(3)

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

(2)αi=1。

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

(4)

(3) 0<αi<1。

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

(5)

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

(6)

4.2 問題求解

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

(7)

式(7)中的目標(biāo)函數(shù)的一階導(dǎo)數(shù)為：

(8)

(9)

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

(10)

(11)

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

(12)

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

s.t.AS≤B

(13)

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

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

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

Figure 2 Relationship between α and T

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

Figure 3 Relationship between α and T when λ=100

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

Figure 4 Relationship between λ and α

Figure 5 Relationship between λ and T

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

Figure 6 Relationship between η and α

Figure 7 Relationship between η and T

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

Figure 8 Response time of three unloading schemes

6 結(jié)束語

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