面向多邊緣設(shè)備協(xié)作的任務(wù)卸載和服務(wù)緩存在線聯(lián)合優(yōu)化機(jī)制

張秋平 孫 勝 劉 敏 李忠誠 張?jiān)?/p>

(中國科學(xué)院計(jì)算技術(shù)研究所 北京 100190)

(中國科學(xué)院大學(xué) 北京100049)

(zhangqiuping＠ict.ac.cn)

近年來,隨著無線網(wǎng)絡(luò)技術(shù)的飛速發(fā)展,移動(dòng)終端設(shè)備數(shù)量劇增.數(shù)百億的移動(dòng)終端設(shè)備導(dǎo)致數(shù)據(jù)爆炸性增長,催生出許多計(jì)算密集型和時(shí)延敏感型的新興應(yīng)用,如人臉識別、虛擬/增強(qiáng)現(xiàn)實(shí)等.這些新興應(yīng)用具有低時(shí)延、高帶寬等服務(wù)需求.傳統(tǒng)云計(jì)算將移動(dòng)終端用戶產(chǎn)生的數(shù)據(jù)傳輸?shù)竭h(yuǎn)端云服務(wù)器中進(jìn)行集中處理,由于傳輸距離較長、回程鏈路受限等原因?qū)е马憫?yīng)時(shí)延過高(數(shù)十至百毫秒級[1])、網(wǎng)絡(luò)擁塞等問題,難以滿足計(jì)算密集型和時(shí)延敏感型應(yīng)用的服務(wù)需求.在此背景下,移動(dòng)邊緣計(jì)算(mobile edge computing,MEC)應(yīng)運(yùn)而生.

移動(dòng)邊緣計(jì)算通過在距離移動(dòng)終端用戶較近的無線網(wǎng)內(nèi)部部署一定的通信、計(jì)算、存儲(chǔ)等資源,提供類似云計(jì)算中心的能力,允許終端用戶將自身產(chǎn)生的計(jì)算密集型和時(shí)延敏感型的計(jì)算任務(wù)卸載到邊緣設(shè)備處執(zhí)行,利用邊緣設(shè)備靠近數(shù)據(jù)源的優(yōu)勢達(dá)到顯著縮短傳輸距離、降低處理時(shí)延、改善用戶體驗(yàn)、提升網(wǎng)絡(luò)運(yùn)行效率的目的.區(qū)別于云計(jì)算中的大規(guī)模數(shù)據(jù)處理中心,移動(dòng)邊緣計(jì)算中邊緣設(shè)備的通信、計(jì)算、存儲(chǔ)等資源相對有限.當(dāng)終端用戶的任務(wù)需求激增時(shí),大量終端用戶需要向邊緣設(shè)備卸載任務(wù),但是由于邊緣設(shè)備資源相對有限,因此容易出現(xiàn)任務(wù)負(fù)載過重、處理時(shí)延增加等問題,導(dǎo)致任務(wù)處理的時(shí)效性缺失.另一方面,邊緣設(shè)備間存在負(fù)載分布不均衡的情況,容易出現(xiàn)有些邊緣設(shè)備任務(wù)過載而其他邊緣設(shè)備資源閑置的問題.通過多邊緣設(shè)備協(xié)作共同執(zhí)行計(jì)算任務(wù)可以在保障終端用戶服務(wù)需求的同時(shí)實(shí)現(xiàn)邊緣設(shè)備間負(fù)載均衡,有效應(yīng)對上述問題,因此多邊緣設(shè)備協(xié)作成為一種必然趨勢.

多邊緣設(shè)備協(xié)作是指在具有通信、計(jì)算、存儲(chǔ)能力的邊緣設(shè)備間合理卸載計(jì)算任務(wù),通過多邊緣設(shè)備協(xié)作共同執(zhí)行計(jì)算任務(wù),以期滿足多個(gè)終端用戶的服務(wù)需求,并有效提高邊緣設(shè)備的資源利用效率,實(shí)現(xiàn)邊緣設(shè)備間負(fù)載均衡.邊緣設(shè)備執(zhí)行計(jì)算任務(wù)時(shí)需要進(jìn)行服務(wù)緩存.服務(wù)緩存是指在邊緣設(shè)備中緩存應(yīng)用服務(wù)及相關(guān)數(shù)據(jù)庫,使得相應(yīng)的計(jì)算任務(wù)可以在邊緣設(shè)備處執(zhí)行[2].即使邊緣設(shè)備具有充足的計(jì)算資源,但是若該邊緣設(shè)備沒有緩存相關(guān)服務(wù)則無法執(zhí)行相應(yīng)的計(jì)算任務(wù),從而導(dǎo)致邊緣設(shè)備的計(jì)算資源不能得到充分利用.由此可知,任務(wù)卸載和服務(wù)緩存之間相互耦合,服務(wù)緩存策略決定了能否進(jìn)行任務(wù)卸載,而任務(wù)卸載結(jié)果反映了服務(wù)緩存策略的性能,因此對任務(wù)卸載和服務(wù)緩存進(jìn)行聯(lián)合優(yōu)化是至關(guān)重要的.

本文研究移動(dòng)邊緣計(jì)算中面向多邊緣設(shè)備協(xié)作的任務(wù)卸載和服務(wù)緩存聯(lián)合優(yōu)化問題,解決上述問題面臨2方面挑戰(zhàn):1)任務(wù)卸載和服務(wù)緩存相互耦合,解決上述問題需要考慮2個(gè)子問題之間的相互作用,同時(shí)子問題耦合導(dǎo)致問題求解呈指數(shù)級增長,極大增加了問題求解的難度.2)不同邊緣設(shè)備的任務(wù)負(fù)載及資源狀態(tài)隨時(shí)間、空間動(dòng)態(tài)變化,需要考慮時(shí)空雙維限制.時(shí)間維度上,邊緣設(shè)備服務(wù)的終端用戶隨時(shí)間動(dòng)態(tài)變化,且終端用戶的服務(wù)緩存需求無法提前預(yù)知,邊緣設(shè)備僅能獲取終端用戶的情景信息,終端用戶情景信息相似時(shí)其服務(wù)緩存需求也是相似的,因此可以根據(jù)終端用戶的情景信息在線學(xué)習(xí)其服務(wù)緩存需求,用于制定未來的服務(wù)緩存策略.在空間維度上,終端用戶的位置分布動(dòng)態(tài)變化且存在分布不均衡的現(xiàn)象,導(dǎo)致邊緣設(shè)備間負(fù)載不均衡,進(jìn)而影響邊緣設(shè)備的任務(wù)執(zhí)行性能,因此需要考慮邊緣設(shè)備間協(xié)作.

本文提出一種面向多邊緣設(shè)備協(xié)作的任務(wù)卸載和服務(wù)緩存在線聯(lián)合優(yōu)化機(jī)制,通過多邊緣設(shè)備協(xié)作,實(shí)現(xiàn)邊緣設(shè)備間負(fù)載均衡,目標(biāo)是在滿足任務(wù)執(zhí)行時(shí)延限制的條件下,最小化任務(wù)整體執(zhí)行時(shí)延.本文的主要貢獻(xiàn)包括3個(gè)方面:

1)將面向多邊緣設(shè)備協(xié)作的任務(wù)卸載和服務(wù)緩存聯(lián)合優(yōu)化問題建模為混合整數(shù)非線性規(guī)劃問題,并設(shè)計(jì)一種任務(wù)卸載和服務(wù)緩存在線聯(lián)合優(yōu)化(online Joint optimization of task Offloading and service Caching,JOC)算法求解上述問題,實(shí)現(xiàn)服務(wù)緩存策略的在線動(dòng)態(tài)更新,并通過多邊緣設(shè)備協(xié)作,進(jìn)行任務(wù)卸載,實(shí)現(xiàn)負(fù)載均衡.

2)將原始問題解耦為服務(wù)緩存和任務(wù)卸載2個(gè)子問題.針對服務(wù)緩存子問題,提出基于情景感知組合多臂賭博機(jī)的協(xié)作服務(wù)緩存(collaborative service caching based on contextual combinatorial multiarmed bandit,3CMAB)算法,基于用戶情景信息在線學(xué)習(xí)多邊緣設(shè)備的協(xié)同服務(wù)緩存策略,實(shí)現(xiàn)服務(wù)緩存策略的動(dòng)態(tài)更新;針對任務(wù)卸載子問題,基于3CMAB算法獲得的服務(wù)緩存策略,利用計(jì)算任務(wù)與卸載位置之間的卸載偏好,在計(jì)算任務(wù)與卸載位置之間進(jìn)行匹配,并在多邊緣設(shè)備間進(jìn)行負(fù)載重分配,使得多邊緣設(shè)備間的負(fù)載相對均衡,提高邊緣設(shè)備執(zhí)行任務(wù)的比例,有效降低任務(wù)整體執(zhí)行時(shí)延.

3)利用大量仿真實(shí)驗(yàn)驗(yàn)證JOC算法的性能.將JOC算法與其他4種基準(zhǔn)算法進(jìn)行比較,實(shí)驗(yàn)結(jié)果表明JOC算法可以有效實(shí)現(xiàn)多邊緣設(shè)備間的負(fù)載均衡,降低系統(tǒng)中任務(wù)整體執(zhí)行時(shí)延.與非協(xié)作的算法相比,JOC算法的任務(wù)整體執(zhí)行時(shí)延降低23.8%.與最新的多邊緣設(shè)備協(xié)作的研究工作[3]相比,JOC算法的任務(wù)整體執(zhí)行時(shí)延降低5.4%.此外本文所提服務(wù)緩存算法的執(zhí)行時(shí)延可忽略不計(jì),即可實(shí)現(xiàn)實(shí)時(shí)動(dòng)態(tài)服務(wù)緩存.

1 相關(guān)工作

移動(dòng)邊緣計(jì)算已經(jīng)引起了產(chǎn)業(yè)界和學(xué)術(shù)界的廣泛關(guān)注.近年來涌現(xiàn)出大量與移動(dòng)邊緣計(jì)算相關(guān)的標(biāo)準(zhǔn)化工作[4].歐洲電信標(biāo)準(zhǔn)協(xié)會(huì)(European Telecommunications Standards Institute,ETSI)最早開始推進(jìn)MEC標(biāo)準(zhǔn)化工作,于2014年12月成立了MEC ISG工業(yè)標(biāo)準(zhǔn)組,公布了20余份標(biāo)準(zhǔn)化文稿及白皮書[5-7],研究內(nèi)容涵蓋MEC平臺架構(gòu)、業(yè)務(wù)需求、管理編排等.在ETSI的推動(dòng)下,第3代合作伙伴(The 3rd Generation Partnership Project,3GPP)、中國通信標(biāo)準(zhǔn)化協(xié)會(huì)(China Communications Standards Association,CCSA)等國際及國內(nèi)標(biāo)準(zhǔn)化組織也相繼啟動(dòng)了MEC標(biāo)準(zhǔn)化工作.3GPP SA2 23.501協(xié)議[8]中指出MEC能夠讓運(yùn)營商和第三方服務(wù)部署在靠近終端設(shè)備接入點(diǎn)的地方,縮短端到端時(shí)延,同時(shí)降低傳輸負(fù)載.CCSA無線通信技術(shù)工作委員會(huì)(TC5)針對移動(dòng)邊緣計(jì)算中的平臺架構(gòu)、場景需求、關(guān)鍵技術(shù)等內(nèi)容進(jìn)行立項(xiàng)[9].互聯(lián)網(wǎng)工程任務(wù)組(Internet Engineering Task Force,IETF)中的應(yīng)用層流量優(yōu)化(application layer traffic optimization,ALTO)工作組也積極開展MEC相關(guān)標(biāo)準(zhǔn)化的推進(jìn)工作.

產(chǎn)業(yè)界對移動(dòng)邊緣計(jì)算也尤為關(guān)注.由華為、騰訊等牽頭發(fā)起的業(yè)界首個(gè)5G移動(dòng)邊緣計(jì)算開源平臺EdgeGallery于2020年正式上線.該平臺聚焦5G場景,構(gòu)建MEC資源、應(yīng)用、安全、管理的基礎(chǔ)框架.中國移動(dòng)于2018年成立了邊緣計(jì)算開放實(shí)驗(yàn)室,中國電信設(shè)立了邊緣計(jì)算開放平臺ECOP,中國聯(lián)通在多個(gè)省市開展Edge-Cloud試點(diǎn)工作.

近年來學(xué)術(shù)界出現(xiàn)了很多關(guān)于移動(dòng)邊緣計(jì)算[10]的研究工作,任務(wù)卸載問題是其中研究的重點(diǎn)內(nèi)容.早期研究工作僅考慮單個(gè)邊緣設(shè)備的任務(wù)卸載問題[11-12].文獻(xiàn)[11]中多個(gè)終端用戶采用無中心、非協(xié)作的博弈方式獨(dú)立決策自身計(jì)算任務(wù)的執(zhí)行位置,將計(jì)算任務(wù)卸載到邊緣設(shè)備或者遠(yuǎn)端云.文獻(xiàn)[12]利用半定松弛法和隨機(jī)映射方法聯(lián)合優(yōu)化所有終端用戶的卸載策略,將多個(gè)終端用戶的任務(wù)卸載到一個(gè)邊緣設(shè)備處執(zhí)行.

然而,當(dāng)終端用戶數(shù)量較多時(shí),單個(gè)邊緣設(shè)備由于自身資源限制難以滿足所有終端用戶的服務(wù)需求,容易導(dǎo)致處理時(shí)延較高或者任務(wù)執(zhí)行失敗.因此,最新研究工作考慮多邊緣設(shè)備協(xié)作共同執(zhí)行計(jì)算任務(wù).文獻(xiàn)[13]利用匹配策略制定多個(gè)終端用戶和多個(gè)邊緣設(shè)備間的任務(wù)卸載策略.文獻(xiàn)[14]利用Lyapunov優(yōu)化算法確定每個(gè)終端用戶產(chǎn)生的計(jì)算任務(wù)的執(zhí)行位置.文獻(xiàn)[15]研究邊緣設(shè)備密集部署場景下的任務(wù)卸載問題.多邊緣設(shè)備間通過聯(lián)盟博弈理論,形成協(xié)作聯(lián)盟共同執(zhí)行終端用戶的計(jì)算任務(wù).文獻(xiàn)[16]研究在多個(gè)霧節(jié)點(diǎn)間進(jìn)行任務(wù)卸載,提出分布式交替方向乘子方法(alternating direction method of multipliers,ADMM),在給定功率約束條件下制定任務(wù)卸載策略,提升用戶的體驗(yàn)質(zhì)量(quality of experience,QoE).文獻(xiàn)[17-18]通過分布式博弈方法實(shí)現(xiàn)邊緣設(shè)備間任務(wù)卸載,目標(biāo)是最小化任務(wù)整體執(zhí)行時(shí)延.然而,上述研究工作僅考慮任務(wù)卸載問題,假設(shè)邊緣設(shè)備中已緩存所有任務(wù)所需的相關(guān)服務(wù).當(dāng)任務(wù)卸載到邊緣設(shè)備時(shí),邊緣設(shè)備僅需考慮計(jì)算資源的限制,若邊緣設(shè)備具有足夠的計(jì)算資源即可為任務(wù)提供服務(wù).但是在實(shí)際情況中,邊緣設(shè)備的存儲(chǔ)資源有限,難以緩存所有服務(wù),需要根據(jù)實(shí)際任務(wù)需求制定動(dòng)態(tài)服務(wù)緩存策略.由此可知,任務(wù)卸載和服務(wù)緩存相互耦合,需要進(jìn)行任務(wù)卸載和服務(wù)緩存聯(lián)合優(yōu)化研究.

文獻(xiàn)[2]首次在多基站MEC場景中研究任務(wù)卸載和服務(wù)緩存聯(lián)合優(yōu)化問題,利用ε-greedy方法制定服務(wù)緩存策略,并基于Gibbs采樣制定任務(wù)卸載策略.文獻(xiàn)[19]中不考慮邊緣設(shè)備的計(jì)算資源限制,利用圖著色方法制定邊緣設(shè)備的服務(wù)緩存策略,目標(biāo)是最小化每個(gè)邊緣設(shè)備的能耗開銷.文獻(xiàn)[20]提出一種雙準(zhǔn)則算法聯(lián)合優(yōu)化路由請求和服務(wù)緩存,目標(biāo)是最小化卸載到遠(yuǎn)端云的流量.文獻(xiàn)[21]提出常因子近似算法和啟發(fā)式算法分別用于求解緩存服務(wù)放置和任務(wù)請求調(diào)度問題,旨在最大化邊緣云的用戶請求數(shù)量.文獻(xiàn)[22]考慮單個(gè)終端用戶與多個(gè)可連接邊緣設(shè)備間的關(guān)聯(lián)策略,提出基于本地搜索的迭代算法,以最小化系統(tǒng)開銷為目標(biāo).但是上述研究工作僅考慮終端用戶和邊緣設(shè)備間的任務(wù)卸載和服務(wù)緩存聯(lián)合優(yōu)化問題,當(dāng)邊緣設(shè)備未緩存所需服務(wù)或者計(jì)算資源不足時(shí),需要將任務(wù)卸載到遠(yuǎn)端云處執(zhí)行,而不是將任務(wù)卸載到具有執(zhí)行能力的邊緣設(shè)備上協(xié)作執(zhí)行,從而導(dǎo)致邊緣設(shè)備的資源利用率低下.

文獻(xiàn)[3]考慮可通信的邊緣設(shè)備協(xié)作共同執(zhí)行任務(wù),目標(biāo)是最小化所有任務(wù)的服務(wù)響應(yīng)時(shí)延,提出基于Gibbs采樣的迭代緩存更新(iterative caching update,ICE)算法用于制定服務(wù)緩存策略,同時(shí)提出一種啟發(fā)式負(fù)載調(diào)度算法用于制定負(fù)載調(diào)度策略,通過ICE算法和啟發(fā)式負(fù)載調(diào)度算法迭代執(zhí)行,求解任務(wù)卸載和服務(wù)緩存聯(lián)合優(yōu)化問題.然而該研究工作假設(shè)終端用戶的服務(wù)緩存需求已知,在實(shí)際情況中服務(wù)緩存需求未知,僅能獲取到終端用戶的情景信息,需要根據(jù)情景信息學(xué)習(xí)終端用戶的服務(wù)緩存需求.目前已有工作研究情景信息與服務(wù)緩存需求之間的關(guān)系.文獻(xiàn)[23-24]基于情景感知組合多臂賭博機(jī)(contextual combinatorial multi-armed bandit,CC-MAB)算法在線學(xué)習(xí)終端用戶的情景信息與服務(wù)需求之間的關(guān)系,制定服務(wù)放置策略.但是該方法無法適用于本文研究的多邊緣設(shè)備協(xié)作進(jìn)行服務(wù)緩存的場景,原因在于多邊緣設(shè)備協(xié)作進(jìn)行服務(wù)緩存時(shí),不僅需要考慮自身關(guān)聯(lián)的終端用戶的情景信息,還需要考慮候選協(xié)作的邊緣設(shè)備所關(guān)聯(lián)的終端用戶的情景信息.

綜上所述,本文針對服務(wù)緩存需求未知的真實(shí)場景,研究移動(dòng)邊緣計(jì)算中面向多邊緣設(shè)備協(xié)作的任務(wù)卸載和服務(wù)緩存聯(lián)合優(yōu)化問題,提出一種任務(wù)卸載和服務(wù)緩存在線聯(lián)合優(yōu)化算法,目標(biāo)是在滿足任務(wù)執(zhí)行時(shí)延限制的條件下,最小化任務(wù)整體執(zhí)行時(shí)延.

2 系統(tǒng)模型和問題描述

本節(jié)首先進(jìn)行場景分析,然后介紹系統(tǒng)模型,包括通信模型、服務(wù)緩存模型和任務(wù)卸載模型,最后對本文要解決的問題進(jìn)行形式化描述.本文涉及的主要變量及相關(guān)描述如表1所示:

Table 1 Variable Notation Table表1 變量符號表

續(xù)表1

2.1 場景分析

如圖1所示,假定移動(dòng)邊緣計(jì)算網(wǎng)絡(luò)包含N個(gè)邊緣設(shè)備,為M個(gè)終端用戶提供服務(wù).遠(yuǎn)端云存儲(chǔ)資源充足,因此緩存所有服務(wù).邊緣設(shè)備緩存資源有限,只能選擇部分服務(wù)進(jìn)行緩存.多邊緣設(shè)備協(xié)作執(zhí)行終端用戶的計(jì)算任務(wù),即相互連通的多邊緣設(shè)備間可以進(jìn)行計(jì)算任務(wù)卸載.首先終端用戶產(chǎn)生計(jì)算任務(wù),將計(jì)算任務(wù)上傳到自身關(guān)聯(lián)的邊緣設(shè)備處;然后邊緣設(shè)備根據(jù)任務(wù)的服務(wù)緩存需求、自身可用計(jì)算資源等因素為接收的計(jì)算任務(wù)選擇合適的卸載位置,可選的卸載位置包括邊緣設(shè)備本地、協(xié)作的邊緣設(shè)備和遠(yuǎn)端云;確定計(jì)算任務(wù)的卸載位置后,將計(jì)算任務(wù)傳輸?shù)较鄳?yīng)的位置并執(zhí)行該計(jì)算任務(wù).

Fig.1 Scene for joint optimization for multi-edge device collaboration圖1 面向多邊緣設(shè)備協(xié)作的聯(lián)合優(yōu)化場景

edgen表示第n個(gè)邊緣設(shè)備,其中n∈N,N＝{1,2,…,N},每個(gè)邊緣設(shè)備配置一個(gè)服務(wù)器.edgen可提供的最大計(jì)算量表示為,服務(wù)緩存容量表示為K n.UEm表示第m個(gè)終端用戶,其中m∈M,M＝{1,2,…,M}.由于邊緣設(shè)備密集部署,邊緣設(shè)備的覆蓋范圍存在重疊區(qū)域,位于重疊區(qū)域內(nèi)的終端用戶選擇信道條件最優(yōu)的邊緣設(shè)備進(jìn)行關(guān)聯(lián).edgen關(guān)聯(lián)的終端用戶序號集合表示為M n,若UEm是edgen關(guān)聯(lián)的終端用戶,則m∈M n.所有邊緣設(shè)備關(guān)聯(lián)的終端用戶并集為系統(tǒng)中所有的終端用戶,即M＝∪n∈N M n.該場景可提供S種服務(wù)緩存,SCs表示第s種服務(wù)緩存,其中s∈S,S＝{1,2,…,S}.

將連續(xù)時(shí)間劃分為T個(gè)分離的時(shí)隙,slott表示第t個(gè)時(shí)隙.在每個(gè)時(shí)隙中,終端用戶的位置固定.在不同時(shí)隙間,終端用戶的位置動(dòng)態(tài)變化[13].在每個(gè)時(shí)隙開始時(shí)更新邊緣設(shè)備的服務(wù)緩存策略.假設(shè)每個(gè)時(shí)隙中UEm產(chǎn)生一個(gè)計(jì)算任務(wù)I m＝(λm,γm,d m,s m),其中λm表示任務(wù)I m的輸入數(shù)據(jù)大小,γm表示任務(wù)I m的計(jì)算需求量,d m表示任務(wù)I m的執(zhí)行時(shí)延限制,s m表示任務(wù)I m的服務(wù)緩存需求為SCs m,其中s m∈S.

2.2 通信模型

本節(jié)介紹通信模型,包括終端用戶與邊緣設(shè)備間的通信模型、多邊緣設(shè)備間的通信模型以及邊緣設(shè)備與遠(yuǎn)端云間的通信模型.

2.2.1 終端用戶與邊緣設(shè)備間的通信模型

本文中邊緣設(shè)備采用正交頻分多址(orthogonal frequency division multiple access,OFDMA)的方法與終端用戶進(jìn)行通信,即邊緣設(shè)備為每個(gè)關(guān)聯(lián)的終端用戶分配一個(gè)正交信道用于數(shù)據(jù)傳輸,因此不同傳輸信道間不存在干擾問題[17].依據(jù)香農(nóng)公式可以得到UEm與edgen間的上行鏈路傳輸速率r mn:

其中,B mn＝B n/|M n|表示edgen分配給UEm的傳輸帶寬,B n表示edgen的信道帶寬,|M n|表示edgen關(guān)聯(lián)的終端用戶個(gè)數(shù),關(guān)聯(lián)的終端用戶平均分配信道帶寬.h mn表示UEm與edgen間的信道增益.本文假設(shè)單個(gè)時(shí)隙內(nèi)終端用戶不發(fā)生移動(dòng),因此h mn是一個(gè)定值.P m表示UEm的傳輸功率,σ2表示噪聲功率.由此可以得到UEm將任務(wù)I m卸載到edgen的上行傳輸時(shí)延:

由于任務(wù)結(jié)果比輸入數(shù)據(jù)小很多[19,25],且從邊緣設(shè)備到終端用戶的下行鏈路傳輸速率遠(yuǎn)大于終端用戶到邊緣設(shè)備的上行鏈路傳輸速率,因此終端用戶與邊緣設(shè)備間的通信模型僅考慮上行鏈路,忽略邊緣設(shè)備執(zhí)行任務(wù)后將任務(wù)結(jié)果傳回終端用戶的時(shí)延開銷.

2.2.2 多邊緣設(shè)備間的通信模型

多邊緣設(shè)備間通過本地局域網(wǎng)(local area network,LAN)連接[17].edgen和edgey間的傳輸速率是定值,表示為R ny.當(dāng)edgen將自身關(guān)聯(lián)的UEm產(chǎn)生的任務(wù)I m卸載到edgey處時(shí),edgen與edgey間的傳輸時(shí)延表示為

2.2.3 邊緣設(shè)備與遠(yuǎn)端云間的通信模型

當(dāng)終端用戶產(chǎn)生的任務(wù)選擇在遠(yuǎn)端云處執(zhí)行時(shí),UEm產(chǎn)生的任務(wù)I m將從其關(guān)聯(lián)的邊緣設(shè)備傳輸?shù)竭h(yuǎn)端云.邊緣設(shè)備通過回程鏈路訪問遠(yuǎn)端云,假定邊緣設(shè)備卸載任務(wù)I m到遠(yuǎn)端云的傳輸時(shí)延為恒定值,表示為

2.3 服務(wù)緩存模型

邊緣設(shè)備為終端用戶提供服務(wù)時(shí)需要本地緩存相應(yīng)服務(wù),但是由于邊緣設(shè)備的緩存資源有限,不能同時(shí)在本地緩存所有服務(wù).在每個(gè)時(shí)隙開始時(shí),邊緣設(shè)備根據(jù)待服務(wù)的終端用戶決定需要緩存哪些服務(wù)表示slott時(shí)所有邊緣設(shè)備的服務(wù)緩存策略,其中表示edgen在slott時(shí)的服務(wù)緩存策略是一個(gè)二進(jìn)制變量表示edgen在slott時(shí)緩存SCs;而表示edgen在slott時(shí)未緩存SCs.服務(wù)緩存不能違背邊緣設(shè)備的緩存容量限制,因此每個(gè)edgen進(jìn)行服務(wù)緩存時(shí)需滿足的約束條件為

2.4 任務(wù)卸載模型

在每個(gè)時(shí)隙中每個(gè)終端用戶產(chǎn)生的計(jì)算任務(wù)將卸載到自身能夠關(guān)聯(lián)的信道質(zhì)量最好的邊緣設(shè)備上.若終端用戶關(guān)聯(lián)的邊緣設(shè)備資源不足或者未緩存所需服務(wù),則該終端用戶關(guān)聯(lián)的邊緣設(shè)備將計(jì)算任務(wù)卸載到其他協(xié)作的邊緣設(shè)備或者遠(yuǎn)端云處執(zhí)行.終端用戶產(chǎn)生的計(jì)算任務(wù)可選的卸載位置包括自身關(guān)聯(lián)的邊緣設(shè)備、協(xié)作的邊緣設(shè)備和遠(yuǎn)端云.表示slott時(shí)所有邊緣設(shè)備的資源分配策略.其中表示slott時(shí)edgen分配給任務(wù)I m的計(jì)算量表示edgen處執(zhí)行的任務(wù)集合,包括edgen關(guān)聯(lián)的終端用戶產(chǎn)生的任務(wù)和協(xié)作邊緣設(shè)備卸載的任務(wù).為了方便表示,下文提到時(shí)忽略表示時(shí)隙的變量t.由于edgen計(jì)算資源有限,因此為集合中所有任務(wù)分配計(jì)算資源時(shí)必須滿足邊緣設(shè)備的計(jì)算資源約束,即

下面將分別介紹終端用戶產(chǎn)生的計(jì)算任務(wù)卸載到關(guān)聯(lián)的邊緣設(shè)備、協(xié)作的邊緣設(shè)備和遠(yuǎn)端云處執(zhí)行的任務(wù)卸載模型.

2.4.1 關(guān)聯(lián)的邊緣設(shè)備執(zhí)行任務(wù)

若UEm產(chǎn)生的任務(wù)I m卸載到自身關(guān)聯(lián)的edgen處執(zhí)行,執(zhí)行時(shí)延包括2部分:1)UEm上傳數(shù)據(jù)到edgen所需的傳輸時(shí)延執(zhí)行任務(wù)所需的計(jì)算時(shí)延.edgen處執(zhí)行任務(wù)I m所需的計(jì)算時(shí)延表示為γm/f nm,其中f nm表示edgen分配給任務(wù)I m的計(jì)算量.因此UEm產(chǎn)生的任務(wù)I m在其關(guān)聯(lián)的edgen處執(zhí)行所需的執(zhí)行時(shí)延為

2.4.2 協(xié)作的邊緣設(shè)備執(zhí)行任務(wù)

由于邊緣設(shè)備的計(jì)算和存儲(chǔ)資源有限,且邊緣設(shè)備間存在負(fù)載不均衡的現(xiàn)象,多邊緣設(shè)備協(xié)作共同執(zhí)行任務(wù),可以充分利用邊緣設(shè)備資源,提高系統(tǒng)的資源利用率.edgen接收自身關(guān)聯(lián)的UEm的卸載任務(wù)I m后,若選擇將任務(wù)I m卸載到協(xié)作的edgey處執(zhí)行,執(zhí)行時(shí)延包括3部分:1)UEm上傳數(shù)據(jù)到edgen所需的傳輸時(shí)延與edgey間傳輸數(shù)據(jù)所需的傳輸時(shí)延執(zhí)行任務(wù)所需的計(jì)算時(shí)延.f ym表示edgey分配給任務(wù)I m的計(jì)算量,任務(wù)I m在edgey處執(zhí)行的計(jì)算時(shí)延表示為γm/f ym.將edgen關(guān)聯(lián)的UEm產(chǎn)生的任務(wù)I m卸載到協(xié)作的edgey處執(zhí)行所需的執(zhí)行時(shí)延為

2.4.3 遠(yuǎn)端云執(zhí)行任務(wù)

由于遠(yuǎn)端云具有強(qiáng)大的計(jì)算能力,可以忽略遠(yuǎn)端云的計(jì)算時(shí)延.那么edgen將自身關(guān)聯(lián)的UEm產(chǎn)生的任務(wù)I m卸載到遠(yuǎn)端云處執(zhí)行所需的執(zhí)行時(shí)延包括2部分:1)UEm上傳數(shù)據(jù)到edgen的傳輸時(shí)延傳輸數(shù)據(jù)到遠(yuǎn)端云的傳輸時(shí)延.因此任務(wù)I m在遠(yuǎn)端云處執(zhí)行所需的執(zhí)行時(shí)延為

2.5 問題描述

為了方便表示,在表示單個(gè)時(shí)隙的目標(biāo)時(shí)將表示時(shí)隙的變量t省略.UEm產(chǎn)生的任務(wù)I m可選的卸載位置包括:關(guān)聯(lián)的edgen、edgen協(xié)作的邊緣設(shè)備和遠(yuǎn)端云.每個(gè)計(jì)算任務(wù)僅能選擇一個(gè)卸載位置,并且選擇的卸載位置提前緩存了執(zhí)行該任務(wù)所需的服務(wù).UEm產(chǎn)生的任務(wù)I m的執(zhí)行時(shí)延為

本文研究面向多邊緣設(shè)備協(xié)作的任務(wù)卸載和服務(wù)緩存聯(lián)合優(yōu)化問題,目標(biāo)是在任務(wù)執(zhí)行時(shí)延限制條件下,最小化任務(wù)整體執(zhí)行時(shí)延,問題建模為

約束條件式(10.1)表示每個(gè)邊緣設(shè)備緩存的服務(wù)個(gè)數(shù)不能超過自身的緩存容量限制.約束條件式(10.2)表示終端用戶產(chǎn)生的計(jì)算任務(wù)僅可在關(guān)聯(lián)的邊緣設(shè)備、協(xié)作的邊緣設(shè)備和遠(yuǎn)端云中選擇一個(gè)卸載位置.約束條件式(10.3)表示邊緣設(shè)備為本地執(zhí)行的計(jì)算任務(wù)分配的計(jì)算量為正數(shù).約束條件式(10.4)表示邊緣設(shè)備為本地執(zhí)行的計(jì)算任務(wù)分配的資源總量必須滿足自身的計(jì)算資源總量限制.約束條件式(10.5)表示edgen是否緩存SCs.約束條件式(10.6)表示edgen關(guān)聯(lián)的UEm產(chǎn)生的任務(wù)I m是否卸載到Devicey處執(zhí)行.

3 任務(wù)卸載和服務(wù)緩存在線聯(lián)合優(yōu)化算法

首先證明上述多邊緣設(shè)備協(xié)作的任務(wù)卸載和服務(wù)緩存聯(lián)合優(yōu)化問題是NP難的,利用已知的NP難問題——廣義分配問題(general assignment problem,GAP)[26]進(jìn)行證明.GAP中假設(shè)有N個(gè)容器,M個(gè)物品,將物品m放入容器n中,獲得相應(yīng)收益.該優(yōu)化問題的目標(biāo)是為每個(gè)物品選擇一個(gè)合適的容器放置,在容器成本的約束條件下最大化物品放置的整體收益.針對本文的問題進(jìn)行參數(shù)映射和轉(zhuǎn)換,GAP中的N個(gè)容器對應(yīng)本文中的N個(gè)邊緣設(shè)備和遠(yuǎn)端云,GAP中的M個(gè)物品對應(yīng)本文中的M個(gè)終端用戶產(chǎn)生的任務(wù),本文的優(yōu)化目標(biāo)是為每個(gè)任務(wù)選擇一個(gè)合適的卸載位置,在邊緣設(shè)備的資源約束條件下最大化任務(wù)的整體執(zhí)行收益,即最小化任務(wù)整體執(zhí)行時(shí)延,因此原始問題P1為NP難問題,難以在多項(xiàng)式時(shí)間內(nèi)獲得最優(yōu)的任務(wù)卸載和服務(wù)緩存策略.

上述面向多邊緣設(shè)備協(xié)作的任務(wù)卸載和服務(wù)緩存聯(lián)合優(yōu)化問題是一個(gè)混合整數(shù)非線性優(yōu)化問題.該問題中服務(wù)緩存策略C和任務(wù)卸載位置選擇策略A為二進(jìn)制變量,邊緣設(shè)備上的資源分配策略F為連續(xù)變量.原始問題P1中服務(wù)緩存策略的約束條件式(10.1)(10.5)和任務(wù)卸載策略的約束條件式(10.2)(10.3)(10.4)(10.6)是彼此分開的.因此,為了降低該問題求解的計(jì)算復(fù)雜度,將原始問題P1解耦為2個(gè)子問題——服務(wù)緩存子問題和任務(wù)卸載子問題,通過求解2個(gè)子問題解決原始問題P1.針對這2個(gè)子問題,設(shè)計(jì)任務(wù)卸載和服務(wù)緩存在線聯(lián)合優(yōu)化(JOC)算法.針對服務(wù)緩存子問題,提出基于情景感知組合多臂賭博機(jī)的協(xié)作服務(wù)緩存(3CMAB)算法,在線學(xué)習(xí)邊緣設(shè)備的服務(wù)緩存收益,進(jìn)而制定服務(wù)緩存策略;針對任務(wù)卸載子問題,基于3CMAB算法獲得的服務(wù)緩存策略確定任務(wù)卸載的可選空間,提出基于偏好的雙邊匹配算法,在邊緣設(shè)備間進(jìn)行負(fù)載重分配,實(shí)現(xiàn)多邊緣設(shè)備間負(fù)載均衡,進(jìn)一步依據(jù)任務(wù)卸載結(jié)果更新服務(wù)緩存收益,進(jìn)而影響下一輪的服務(wù)緩存策略.下面將對提出的JOC算法進(jìn)行詳細(xì)介紹.

3.1 邊緣設(shè)備的服務(wù)緩存策略

本節(jié)提出基于情景感知組合多臂賭博機(jī)的協(xié)作服務(wù)緩存(3CMAB)算法求解服務(wù)緩存子問題.每個(gè)邊緣設(shè)備需要利用終端用戶的情景信息判斷其服務(wù)緩存需求,因此該子問題是一個(gè)“contextual”問題;邊緣設(shè)備需要緩存多個(gè)服務(wù),因此該子問題也是一個(gè)“combinatorial”問題.與此同時(shí),不同邊緣設(shè)備的負(fù)載各不相同,多個(gè)邊緣設(shè)備需要協(xié)同提供服務(wù),因此邊緣設(shè)備在制定服務(wù)緩存策略時(shí)需要考慮候選協(xié)作的邊緣設(shè)備所關(guān)聯(lián)的終端用戶的情景信息,因此該子問題還是一個(gè)“collaborative”問題.

根據(jù)負(fù)載情況將邊緣設(shè)備分為2類:Source node和Sink node.Source node負(fù)載較重,僅能為本地關(guān)聯(lián)的終端用戶提供服務(wù),不能處理的任務(wù)卸載到協(xié)作的邊緣設(shè)備或者遠(yuǎn)端云處執(zhí)行.Sink node負(fù)載較輕,除了為本地關(guān)聯(lián)的終端用戶提供服務(wù)外,同時(shí)可以接收候選協(xié)作的邊緣設(shè)備卸載的任務(wù).由此可知,Source node在制定服務(wù)緩存策略時(shí),僅需考慮本地關(guān)聯(lián)的終端用戶的情景信息;而Sink node不僅需要考慮本地關(guān)聯(lián)的終端用戶的情景信息,同時(shí)還需要考慮候選協(xié)作的邊緣設(shè)備所關(guān)聯(lián)的終端用戶的情景信息.

文獻(xiàn)[23-24]均采用終端用戶情景信息相似時(shí)其服務(wù)緩存需求也相似的[27-28]假設(shè).本文基于這種假設(shè)提出3CMAB算法,在線學(xué)習(xí)每種情景信息下終端用戶的服務(wù)緩存需求,在每個(gè)時(shí)隙開始時(shí)邊緣設(shè)備根據(jù)終端用戶的情景信息制定服務(wù)緩存策略,有效提高服務(wù)緩存命中率.

3.1.1 終端用戶的情景信息

邊緣設(shè)備在每個(gè)時(shí)隙開始時(shí)觀察自身關(guān)聯(lián)的終端用戶的情景信息表示在slott時(shí)edgen關(guān)聯(lián)的UEm的情景信息,其中X＝[0,1]D表示情景信息空間,D表示情景信息維度.在slott時(shí)edgen關(guān)聯(lián)的終端用戶的情景信息集合表示為若edgen為Sink node,則需要考慮候選協(xié)作的邊緣設(shè)備所關(guān)聯(lián)的終端用戶的情景信息,Sink noden考慮的協(xié)作情景信息集合表示為

Fig.2 Illustration of context space and partitions圖2 情景信息空間和分區(qū)示意圖

在初始化階段,將情景信息空間X＝[0,1]D劃分為(h T)D個(gè)集合,每個(gè)集合是具有相同大小(1/h T)×…×(1/h T)的D維立方體空間.h T是一個(gè)輸入數(shù)據(jù),決定情景信息空間可劃分的集合個(gè)數(shù).每個(gè)集合作為一個(gè)整體,其情景信息為p,p∈P T.P T表示劃分后的整體情景信息空間.情景信息空間及分區(qū)如圖2所示.每個(gè)邊緣設(shè)備均需要記錄P T中所有情景信息相應(yīng)的數(shù)據(jù)值表示slott時(shí)edgen關(guān)聯(lián)的UEm的情景信息對應(yīng)的分區(qū)情景信息,即表示slott時(shí)edgen關(guān)聯(lián)的終端用戶對應(yīng)的分區(qū)情景信息集合表示edgen記錄的候選協(xié)作的edgey關(guān)聯(lián)的UEw的情景信息對應(yīng)的分區(qū)情景信息.

3.1.2 服務(wù)緩存問題建模

UEm產(chǎn)生的任務(wù)I m的執(zhí)行時(shí)延限制表示為d m,執(zhí)行任務(wù)所獲收益值與d m相關(guān).執(zhí)行任務(wù)時(shí)延越低,與d m間的差值越大,則執(zhí)行該任務(wù)的收益值越大.邊緣設(shè)備只有緩存任務(wù)I m所需的SCs m時(shí),才能執(zhí)行該任務(wù),產(chǎn)生收益值.因此,針對SCs執(zhí)行任務(wù)I m產(chǎn)生的收益值定義為

最小化系統(tǒng)中任務(wù)整體執(zhí)行時(shí)延等價(jià)于最大化系統(tǒng)中任務(wù)整體收益值.任務(wù)整體收益值為執(zhí)行系統(tǒng)中所有終端用戶產(chǎn)生的任務(wù)所獲收益值總和,因此最大化系統(tǒng)中任務(wù)整體收益值表示為3CMAB算法是一個(gè)探索與利用權(quán)衡的過程,為了獲取情景信息對應(yīng)的不同服務(wù)緩存的預(yù)估收益值,需要進(jìn)行多次探索.探索階段針對每種情景信息選擇之前從未探索或者未探索完全的服務(wù)進(jìn)行緩存,任務(wù)執(zhí)行完成后得到緩存該服務(wù)相應(yīng)的收益值,根據(jù)該收益值更新預(yù)估收益值,用于制定下一輪服務(wù)緩存策略.利用階段則為每種情景信息選擇預(yù)估收益值最高的服務(wù)進(jìn)行緩存.為了得到每種情景信息對每種服務(wù)緩存的預(yù)估收益值,需要記錄相關(guān)數(shù)據(jù),因此會(huì)耗費(fèi)一定的存儲(chǔ)空間.當(dāng)學(xué)習(xí)過程完成后,邊緣設(shè)備即可根據(jù)學(xué)習(xí)獲得的情景信息與服務(wù)緩存之間的模型,根據(jù)終端用戶的情景信息選擇預(yù)估收益值最高的服務(wù)進(jìn)行緩存,快速制定服務(wù)緩存策略.

3CMAB算法需要優(yōu)化系統(tǒng)長期收益,即最大化系統(tǒng)中長期任務(wù)整體收益值,具體表示為

3.1.3 3CMAB算法

本節(jié)詳細(xì)介紹3CMAB算法,包括探索和利用2個(gè)階段,算法流程如圖3所示.首先,獲取每個(gè)邊緣設(shè)備本地關(guān)聯(lián)的終端用戶的情景信息集合,然后預(yù)判邊緣設(shè)備類型,并依據(jù)類型設(shè)計(jì)不同的探索和利用過程.探索階段中,每個(gè)邊緣設(shè)備根據(jù)未探索完全的服務(wù)緩存?zhèn)€數(shù)和服務(wù)緩存容量限制之間的關(guān)系,選擇不同的服務(wù)緩存策略進(jìn)行探索.若探索完全,即針對每種情景信息學(xué)習(xí)到最優(yōu)的服務(wù)緩存后,則進(jìn)入利用階段.利用階段可依據(jù)終端用戶的情景信息選擇最優(yōu)的服務(wù)進(jìn)行緩存.

其中,M n表示edgen關(guān)聯(lián)的終端用戶序號集合,表示edgen針對情景信息p未探索完全的服務(wù)緩存序號集合.判斷是否為空,從而確定邊緣設(shè)備運(yùn)行階段.若則邊緣設(shè)備進(jìn)入探索階段;若,則邊緣設(shè)備進(jìn)入利用階段.

Source node和Sink node兩類邊緣設(shè)備需要考慮不同的情景信息,緩存不同服務(wù)所獲得的收益值存在差異,進(jìn)而導(dǎo)致探索與利用策略有所不同.下面首先介紹如何判斷邊緣設(shè)備類型,然后分別介紹2類邊緣設(shè)備的探索與利用過程.

2)判斷邊緣設(shè)備類型

當(dāng)邊緣設(shè)備進(jìn)行服務(wù)緩存時(shí),首先邊緣設(shè)備需要根據(jù)自身關(guān)聯(lián)的終端用戶的情景信息推測任務(wù)計(jì)算需求量以及任務(wù)執(zhí)行時(shí)延限制,進(jìn)而對邊緣設(shè)備類型進(jìn)行預(yù)判斷.

記錄到slott為止,edgen接收的情景信息為p、服務(wù)緩存需求為SCs的任務(wù)請求次數(shù)在slott時(shí),若edgen接收到情景信息為p、服務(wù)緩存需求為SCs的任務(wù)請求,則更新

Fig.3 3CMAB algorithm flow chart圖3 3CMAB算法流程圖

在當(dāng)前時(shí)隙中,edgen關(guān)聯(lián)的UEm產(chǎn)生的任務(wù)I m的計(jì)算需求量為γm,執(zhí)行時(shí)延限制為d m.利用與任務(wù)I m的計(jì)算需求量γm計(jì)算到slott為止,edgen接收的情景信息為p、服務(wù)緩存需求為SCs的平均任務(wù)計(jì)算需求量為

在每個(gè)slott開始時(shí),edgen觀察關(guān)聯(lián)的終端用戶的情景信息根 據(jù)記錄的平均任務(wù)計(jì)算需求量和平均任務(wù)執(zhí)行時(shí)延限制計(jì)算關(guān)聯(lián)的終端用戶的總?cè)蝿?wù)計(jì)算需求量即任務(wù)負(fù)載為和總?cè)蝿?wù)執(zhí)行時(shí)延限制

edgen根據(jù)自身的總?cè)蝿?wù)計(jì)算需求量和計(jì)算能力得到所有任務(wù)均在本地執(zhí)行的平均執(zhí)行時(shí)延:

edgen根據(jù)自身的總?cè)蝿?wù)執(zhí)行時(shí)延限制和任務(wù)數(shù)量,得到edgen執(zhí)行所有任務(wù)的平均執(zhí)行時(shí)延限制:

Source node負(fù)載較重,僅能為本地關(guān)聯(lián)的終端用戶提供服務(wù),因此在制定服務(wù)緩存策略時(shí)僅需要考慮本地關(guān)聯(lián)的終端用戶的情景信息.而Sink node負(fù)載較輕,除了為本地關(guān)聯(lián)的終端用戶提供服務(wù)外,還需要執(zhí)行候選協(xié)作的邊緣設(shè)備卸載的任務(wù),因此在制定服務(wù)緩存策略時(shí)除了考慮本地關(guān)聯(lián)的終端用戶的情景信息,還需要考慮候選協(xié)作的邊緣設(shè)備關(guān)聯(lián)的終端用戶的情景信息.

3)Source node探索與利用過程

Source noden依據(jù)式(11)計(jì)算執(zhí)行自身關(guān)聯(lián)的UEm產(chǎn)生的任務(wù)I m的本地收益值r m.定義r m與后續(xù)Sink node執(zhí)行候選協(xié)作的邊緣設(shè)備卸載的任務(wù)所獲得的協(xié)作收益值進(jìn)行區(qū)分,在4)中將對進(jìn)行詳細(xì)介紹.

若Source noden未探索完全的服務(wù)緩存集合不為空,則進(jìn)入探索階段.在探索階段,Source noden根據(jù)未探索完全的服務(wù)緩存?zhèn)€數(shù)和自身服務(wù)緩存容量限制K n之間的關(guān)系選擇不同的服務(wù)緩存策略.若則Source noden從中隨機(jī)選擇K n個(gè)服務(wù)進(jìn)行緩存;若則Source noden首先選擇中所有服務(wù)進(jìn)行緩存,然后選擇個(gè)總預(yù)估收益值最高的服務(wù)進(jìn)行緩存:

若Source noden未探索完全的服務(wù)緩存集合為空,則進(jìn)入利用階段.在利用階段,Source noden根據(jù)式(25)選擇總預(yù)估收益值最高的K n個(gè)服務(wù)進(jìn)行緩存:

4)Sink node探索與利用過程

Sink node的探索與利用過程和Source node相同,但由于Sink node除了執(zhí)行本地關(guān)聯(lián)的終端用戶產(chǎn)生的任務(wù)外,還需要執(zhí)行候選協(xié)作的邊緣設(shè)備卸載的任務(wù),因此Sink node在制定服務(wù)緩存策略時(shí)需要考慮候選協(xié)作的邊緣設(shè)備的服務(wù)緩存需求.Sink node除了考慮本地關(guān)聯(lián)的終端用戶的情景信息外,還需要考慮候選協(xié)作的邊緣設(shè)備關(guān)聯(lián)的終端用戶的情景信息,該部分情景信息與Sink node自身可接收的任務(wù)量和對候選協(xié)作的邊緣設(shè)備的偏好值相關(guān).

Sink noden自身關(guān)聯(lián)的終端用戶的總?cè)蝿?wù)計(jì)算需求量為表示Sink noden能夠提供的總?cè)蝿?wù)計(jì)算需求量.因此Sink noden可接收的候選協(xié)作的邊緣設(shè)備卸載的總?cè)蝿?wù)計(jì)算需求量為兩者的差值,表示為

計(jì)算Sink noden針對候選協(xié)作的edgey中每種情景信息p的偏好值.該偏好值與edgey和Sink noden之間的歷史協(xié)作次數(shù),以及候選協(xié)作的邊緣設(shè)備edgey可選擇的Sink node個(gè)數(shù)相關(guān)表示edgey候選協(xié)作的Sink node序號集合表示到slott為止,Sink noden執(zhí)行edgey中情景信息為p的任務(wù)次數(shù)表示到slott為止,Sink noden執(zhí)行edgey中情景信息為p、服務(wù)緩存需求為SCs的任務(wù)次數(shù).每執(zhí)行一次,則根據(jù)

Sink noden與edgey針對edgey中情景信息p的歷史協(xié)作次數(shù)越多,edgey可選Sink node數(shù)量越少,則Sink noden針對edgey中情景信息p的偏好值越高.

其中,Nn表示Sink noden候選協(xié)作的邊緣設(shè)備序號集合.

根據(jù)式(28)選擇偏好值最高的情景信息,將選擇的情景信息添加到Sink noden的協(xié)作情景信息集合中.計(jì)算中所有情景信息對應(yīng)的終端用戶的總?cè)蝿?wù)計(jì)算需求量是否達(dá)到Sink noden當(dāng)前可接收的總?cè)蝿?wù)計(jì)算需求量,若達(dá)到則終止;若未達(dá)到則選擇偏好值次高的情景信息,重復(fù)上述過程直到終止,得到Sink noden的協(xié)作情景信息集合

Sink noden執(zhí)行任務(wù)產(chǎn)生的收益值包括r m和兩部分,r m表示Sink noden執(zhí)行自身關(guān)聯(lián)的UEm產(chǎn)生的任務(wù)I m所獲得的本地收益值表示Sink noden處執(zhí)行候選協(xié)作edgey關(guān)聯(lián)的UEw產(chǎn)生的任務(wù)I w所獲得的協(xié)作收益值.根據(jù)式(11)計(jì)算r m和

Sink node的探索與利用過程和Source node相同.若Sink noden未探索完全的服務(wù)緩存集合不為空,則進(jìn)入探索階段.在探索階段,Sink noden根據(jù)未探索完全的服務(wù)緩存?zhèn)€數(shù)和自身服務(wù)緩存容量限制K n之間的關(guān)系,選擇不同的服務(wù)緩存策略.若,則Sink noden從未探索完全的服務(wù)緩存集合中隨機(jī)選擇K n個(gè)服務(wù)進(jìn)行緩存;若則Sink noden先緩存所有未探索完全的服務(wù),然后選擇總預(yù)估收益值最高的個(gè)服務(wù)進(jìn)行緩存:

若Sink noden未探索完全的服務(wù)緩存集合為空,則進(jìn)入利用階段.在利用階段,Sink noden選擇總預(yù)估收益值最高的K n個(gè)服務(wù)進(jìn)行緩存:

5)3CMAB算法流程

首先每個(gè)edgen獲取自身關(guān)聯(lián)的終端用戶的情景信息集合.然后分別依據(jù)式(19)和式(20)計(jì)算edgen中所有任務(wù)均在本地執(zhí)行的平均執(zhí)行時(shí)延和平均執(zhí)行時(shí)延限制,根據(jù)之間的大小關(guān)系預(yù)判斷邊緣設(shè)備類型.然后根據(jù)式(15)計(jì)算edgen針對待執(zhí)行任務(wù)未探索完全的服務(wù)緩存集合,則edgen進(jìn)入探索階段;若,則edgen進(jìn)入利用階段.邊緣設(shè)備類型不同時(shí),總預(yù)估收益值的計(jì)算公式不同.Source node和Sink node分別根據(jù)式(23)和式(30)計(jì)算總預(yù)估收益值.探索階段中,edgen根據(jù)未探索完全的服務(wù)緩存?zhèn)€數(shù)與自身服務(wù)緩存容量限制K n之間的關(guān)系,選擇不同的服務(wù)緩存策略.當(dāng)時(shí),edgen從未探索完全的服務(wù)緩存集合中隨機(jī)選擇K n個(gè)服務(wù)進(jìn)行緩存;當(dāng)K n時(shí),edgen先將所有未探索完全的服務(wù)進(jìn)行緩存,然后選擇總預(yù)估收益值最高的個(gè)服務(wù)進(jìn)行緩存.根據(jù)邊緣設(shè)備類型,Source node和Sink node分別根據(jù)式(24)和式(31)選擇總預(yù)估收益值最高的len個(gè)服務(wù)進(jìn)行緩存.利用階段中,根據(jù)邊緣設(shè)備類型,Source node和Sink node分別根據(jù)式(25)和式(32)選擇K n個(gè)總預(yù)估收益值最高的服務(wù)進(jìn)行緩存.3CMAB算法偽代碼如算法1所示.

算法1.3CMAB算法.

輸入:終端用戶序號集合Mn、終端用戶情景信息、邊緣設(shè)備最大計(jì)算量

3.2 多邊緣設(shè)備間的任務(wù)卸載策略

在給定服務(wù)緩存策略的基礎(chǔ)上制定多邊緣設(shè)備間的任務(wù)卸載策略,目標(biāo)是實(shí)現(xiàn)邊緣設(shè)備間負(fù)載均衡.本節(jié)僅考慮單個(gè)時(shí)隙內(nèi)的任務(wù)卸載,因此將表示時(shí)隙的變量t省略.原始問題P1中的資源分配策略F和任務(wù)卸載位置選擇策略A的約束條件是彼此分開的,因此可以將任務(wù)卸載問題分解為資源分配和任務(wù)卸載位置選擇2個(gè)子問題,分別進(jìn)行求解.

3.2.1 邊緣設(shè)備的資源分配策略

邊緣設(shè)備進(jìn)行資源分配時(shí),假定邊緣設(shè)備上的服務(wù)緩存策略C和任務(wù)卸載位置選擇策略A確定.此時(shí)終端用戶上傳數(shù)據(jù)到關(guān)聯(lián)的邊緣設(shè)備的傳輸時(shí)延、邊緣設(shè)備間的傳輸時(shí)延、邊緣設(shè)備到遠(yuǎn)端云的傳輸時(shí)延均可確定,因此可以將原始優(yōu)化問題P1轉(zhuǎn)化為

此外,由于邊緣設(shè)備的服務(wù)緩存策略c y,sm和任務(wù)卸載位置選擇策略a ny,Im均為定值,可以確定每個(gè)邊緣設(shè)備本地執(zhí)行任務(wù)集合.因此,可以將上述優(yōu)化問題進(jìn)一步轉(zhuǎn)化為子問題P3進(jìn)行求解[13,29]:

值得注意的是約束條件式(34.2)是凸的.定義優(yōu)化目標(biāo)函數(shù)為

求解優(yōu)化目標(biāo)函數(shù)D(F)′對f nm的二階導(dǎo)數(shù),得到:

由式(36)(37)可以得出,子問題P3的Hessian矩陣是對角矩陣,具有嚴(yán)格的正值,即該Hession矩陣為一個(gè)正定矩陣,因此子問題P3是一個(gè)凸優(yōu)化問題,可以通過對偶方法進(jìn)行求解.令υ＝{υn}n∈N表示與約束條件式(34.2)相關(guān)聯(lián)的對偶量.拉格朗日函數(shù)表示為

定義拉格朗日對偶函數(shù)GP3(υ)為

GP3(υ)表示在原始F上求解最小值.將式(39)進(jìn)一步轉(zhuǎn)化為在υ上求解最大值的對偶函數(shù),具體表示為

因?yàn)樽訂栴}P3是凸的,因此可以通過對拉格朗日函數(shù)LP3(F,υ)求解一階導(dǎo)數(shù),令其一階導(dǎo)數(shù)為0來獲得最優(yōu)分配的計(jì)算量f?nm,即:

將式(41)代入式(39)中.由于拉格朗日對偶函數(shù)GP3(υ)也是凸函數(shù),求解GP3(υ)的一階導(dǎo)數(shù),令其等于0即可獲得最優(yōu)對偶量υ?n,即:

將式(42)代入式(41)中,即可得到edgen為本地執(zhí)行任務(wù)集合Iexen中的每個(gè)待執(zhí)行的任務(wù)I m分配的最優(yōu)計(jì)算量:

3.2.2 任務(wù)卸載位置選擇策略

根據(jù)3.2.1節(jié)所述方法可以獲得邊緣設(shè)備的資源分配策略F,在此基礎(chǔ)上制定任務(wù)卸載位置選擇策略A,確定所有任務(wù)的卸載位置.由于終端用戶上傳數(shù)據(jù)到自身關(guān)聯(lián)的邊緣設(shè)備所需的傳輸時(shí)延是確定的,因此可以將原始問題P1轉(zhuǎn)化為子問題P4:

其中,

約束式(44.2)表示UEm產(chǎn)生的任務(wù)I m僅可在關(guān)聯(lián)的邊緣設(shè)備、協(xié)作的邊緣設(shè)備和遠(yuǎn)端云中選擇一個(gè)卸載位置.

edgen為自身關(guān)聯(lián)的UEm產(chǎn)生的任務(wù)I m選擇合適的卸載位置.若edgen緩存任務(wù)I m所需的SCs m,則該任務(wù)為本地緩存命中任務(wù),添加到edgen的本地緩存命中任務(wù)集合中.剩余任務(wù)即本地未緩存命中的任務(wù)添加到edgen的本地未緩存命中任務(wù)集合中任務(wù)可以卸載到協(xié)作的Sink node或者遠(yuǎn)端云處執(zhí)行.

Source node負(fù)載較重,僅能執(zhí)行本地關(guān)聯(lián)的終端用戶卸載的計(jì)算任務(wù),當(dāng)計(jì)算資源不足時(shí)需要將中的部分任務(wù)進(jìn)行卸載.Sink node負(fù)載較輕,除了執(zhí)行中的所有本地緩存命中的任務(wù),還具有多余的計(jì)算資源可以接收候選協(xié)作的邊緣設(shè)備卸載的任務(wù).Source node和Sink node均可將本地未緩存命中任務(wù)集合中的任務(wù)卸載到緩存有相應(yīng)服務(wù)的Sink node或者遠(yuǎn)端云處.

由此論述可以看出,無論是Source node還是Sink node均需要進(jìn)行任務(wù)卸載,而只有Sink node可以接收候選協(xié)作的邊緣設(shè)備卸載的任務(wù).

下面針對Source node和Sink node兩種類型的邊緣設(shè)備,分別介紹如何根據(jù)本地服務(wù)緩存策略、計(jì)算能力以及負(fù)載情況確定各自的本地執(zhí)行任務(wù)集合和本地卸載任務(wù)集合;然后介紹基于偏好的雙邊匹配算法,目的是建立待卸載任務(wù)與Sink node之間的匹配關(guān)系,為本地卸載任務(wù)集合中的每個(gè)待卸載任務(wù)選擇合適的卸載位置,實(shí)現(xiàn)邊緣設(shè)備間負(fù)載均衡.

1)Source node確定本地執(zhí)行任務(wù)集合和本地卸載任務(wù)集合

Source noden從本地緩存命中任務(wù)集合中選擇部分任務(wù)在本地執(zhí)行中剩余任務(wù)和中的任務(wù)則需要進(jìn)行卸載,將其添加到卸載任務(wù)集合中.

若任務(wù)I m卸載到候選協(xié)作的Sink nodey處執(zhí)行,假定Sink nodey中的所有任務(wù)平分計(jì)算資源,則Sink nodey中每個(gè)任務(wù)能夠獲得的計(jì)算量為表示Sink nodey待執(zhí)行的任務(wù)個(gè)數(shù).任務(wù)I m卸載到Sink nodey處執(zhí)行所需的卸載預(yù)估執(zhí)行時(shí)延包括3部分:UEm將任務(wù)I m卸載到自身關(guān)聯(lián)的Source noden所需的傳輸時(shí)延、任務(wù)I m從自身關(guān)聯(lián)的Source noden卸載到Sink nodey處的傳輸時(shí)延和任務(wù)I m在Sink nodey處執(zhí)行所需的計(jì)算時(shí)延,具體表示為

計(jì)算任務(wù)I m在所有候選協(xié)作的Sink node處執(zhí)行所需的最低卸載預(yù)估執(zhí)行時(shí)延表示為

由于遠(yuǎn)端云的計(jì)算能力較強(qiáng),可以忽略遠(yuǎn)端云的計(jì)算時(shí)延.任務(wù)I m卸載到遠(yuǎn)端云處執(zhí)行所需的卸載預(yù)估執(zhí)行時(shí)延包括2部分:UEm將任務(wù)I m卸載到自身關(guān)聯(lián)的Source noden所需的傳輸時(shí)延、任務(wù)I m從自身關(guān)聯(lián)的Source noden處卸載到遠(yuǎn)端云所需的傳輸時(shí)延,即.任務(wù)I m在候選協(xié)作的Sink node和遠(yuǎn)端云處執(zhí)行所需的最低卸載預(yù)估執(zhí)行時(shí)延表示為

2)Sink node確定本地執(zhí)行任務(wù)集合和本地卸載任務(wù)集合

由于Sink node計(jì)算資源充足,所有本地緩存命中任務(wù)集合中的任務(wù)均在本地執(zhí)行,本地未緩存命中的任務(wù)卸載到候選協(xié)作的Sink node或遠(yuǎn)端云處執(zhí)行.本地卸載任務(wù)集合為.此外Sink node還需要執(zhí)行接收的其他候選協(xié)作邊緣設(shè)備卸載的任務(wù),因此Sink noden本地執(zhí)行任務(wù)集合包括本地緩存命中任務(wù)集合和接收的卸載任務(wù)集合

3)基于偏好的雙邊匹配算法

采用基于偏好的雙邊匹配算法為所有邊緣設(shè)備待卸載的任務(wù)(即中的任務(wù))選擇合適的卸載位置.每個(gè)待卸載任務(wù)對不同卸載位置(候選協(xié)作的Sink node和遠(yuǎn)端云)存在偏好,偏好值與卸載位置的卸載預(yù)估執(zhí)行時(shí)延相關(guān),卸載預(yù)估執(zhí)行時(shí)延越低,則偏好值越大.

UEm關(guān)聯(lián)的邊緣設(shè)備確定,此時(shí)UEm將任務(wù)I m卸載到自身關(guān)聯(lián)的edgen所需的傳輸時(shí)延即可確定,因此在計(jì)算偏好值考慮卸載預(yù)估執(zhí)行時(shí)延時(shí),不考慮部分.

edgen中每個(gè)待卸載任務(wù)I m對每個(gè)候選協(xié)作的Sink nodey的偏好值表示為

edgen中每個(gè)待卸載任務(wù)I m卸載到遠(yuǎn)端云的偏好值表示為

每個(gè)edgen優(yōu)先向偏好值最優(yōu)的卸載位置發(fā)送卸載請求.若請求的卸載位置是遠(yuǎn)端云,則遠(yuǎn)端云直接接收該卸載請求,即a n0,Im＝1.若請求的卸載位置為Sink node,則需要等待Sink node回復(fù).若請求的Sink node接收該卸載請求,則可以確定該任務(wù)的卸載位置;若Sink node拒絕該卸載請求,則在下一輪迭代中向偏好值次優(yōu)的卸載位置發(fā)送卸載請求.

接下來介紹Sink nodey如何判斷是否接收卸載請求表示Sink nodey接收到的卸載請求任務(wù)集合表示Sink nodey接收的卸載任務(wù)集合,表示Sink nodey的本地執(zhí)行任務(wù)集合.在每輪迭代中,每個(gè)Sink nodey可能接收到多個(gè)任務(wù)的卸載請求,假定接收所有卸載請求即,同時(shí)根據(jù)更新值.根據(jù)式(43)得到Sink nodey分配給中的每個(gè)任務(wù)的計(jì)算量中本地關(guān)聯(lián)的終端用戶產(chǎn)生的任務(wù)根據(jù)式(6)計(jì)算本地執(zhí)行任務(wù)所需的本地預(yù)估執(zhí)行時(shí)延中接收的協(xié)作邊緣設(shè)備的卸載任務(wù)根據(jù)式(7)計(jì)算卸載到Sink nodey處執(zhí)行所需的卸載預(yù)估執(zhí)行時(shí)延.判斷中所有任務(wù)是否均可滿足執(zhí)行時(shí)延限制.若均可滿足執(zhí)行時(shí)延限制,則Sink nodey接收所有卸載請求,否則將依據(jù)下面步驟拒絕部分卸載請求.

計(jì)算Sink nodey接收中每個(gè)卸載任務(wù)的接收預(yù)估收益值,即在Sink nodey處執(zhí)行該任務(wù)所需的卸載預(yù)估執(zhí)行時(shí)延與該任務(wù)在次優(yōu)執(zhí)行位置所需的卸載預(yù)估執(zhí)行時(shí)延之間的差值,拒絕中接收預(yù)估收益值最低的卸載任務(wù),將該任務(wù)從中刪除,同時(shí)更新值.重復(fù)上述過程,直到能夠滿足中所有任務(wù)的執(zhí)行時(shí)延限制,得到最終接收的卸載任務(wù)集合和本地執(zhí)行任務(wù)集合

上述基于偏好的雙邊匹配算法能夠依據(jù)邊緣設(shè)備的任務(wù)需求、資源狀態(tài)和負(fù)載情況合理卸載計(jì)算任務(wù),實(shí)現(xiàn)邊緣設(shè)備間負(fù)載均衡.由于僅Sink node可以接收卸載任務(wù),待卸載任務(wù)可匹配的卸載位置無需考慮負(fù)載較重的Source node,因此有效降低了任務(wù)卸載的匹配空間,進(jìn)而降低計(jì)算復(fù)雜度.上述算法流程如算法2所示.

算法2.多邊緣設(shè)備間的任務(wù)卸載算法.

3.3 JOC算法復(fù)雜度分析

3CMAB算法在線學(xué)習(xí)終端用戶情景信息對邊緣設(shè)備的服務(wù)緩存收益的影響,基于學(xué)習(xí)獲得的模型,直接通過公式計(jì)算即可得出服務(wù)緩存策略.因此進(jìn)行JOC算法復(fù)雜度分析時(shí)僅考慮多邊緣設(shè)備間的任務(wù)卸載策略的復(fù)雜度.多邊緣設(shè)備間的任務(wù)卸載策略是一種分布式策略,因此從單個(gè)邊緣設(shè)備的角度進(jìn)行算法復(fù)雜度分析.

4 實(shí)驗(yàn)與結(jié)果

本節(jié)給出仿真結(jié)果用于評估所提任務(wù)卸載和服務(wù)緩存在線聯(lián)合優(yōu)化(JOC)算法的性能.

4.1 實(shí)驗(yàn)設(shè)置

移動(dòng)邊緣計(jì)算場景中部署3個(gè)邊緣設(shè)備為終端用戶提供服務(wù).每個(gè)邊緣設(shè)備的帶寬為20 MHz.在每個(gè)邊緣設(shè)備覆蓋區(qū)域內(nèi)隨機(jī)部署終端用戶,所有關(guān)聯(lián)的終端用戶平均分配帶寬.每個(gè)edgen的最大計(jì)算量為.每個(gè)UEm的傳輸功率為,噪聲功率為σ2＝－100 dBm,路徑傳輸損耗模型為Los＝32.5＋20 lgZ＋20 lgX,其中Z表示載波頻率,X表示終端用戶與邊緣設(shè)備之間的距離.終端用戶產(chǎn)生的任務(wù)的輸入數(shù)據(jù)大小λm區(qū)間為[0.3,0.45]Mb/task,任務(wù)的計(jì)算需求量γm區(qū)間為[0.2,0.5]GHz/task.實(shí)驗(yàn)的主要參數(shù)如表2所示:

Table 2 The Main Parameters Setting表2 主要參數(shù)設(shè)置

4.2 對比算法及性能指標(biāo)

1)Cloud.假設(shè)邊緣設(shè)備不緩存任何服務(wù),所有任務(wù)均卸載到遠(yuǎn)端云處執(zhí)行.

2)Service Caching Randomly(Random).每個(gè)邊緣設(shè)備隨機(jī)選擇服務(wù)進(jìn)行緩存,邊緣設(shè)備間不進(jìn)行任務(wù)卸載.

3)Non-Cooperative(Non_Co).每個(gè)邊緣設(shè)備根據(jù)本地關(guān)聯(lián)的終端用戶的情景信息學(xué)習(xí)服務(wù)緩存策略,邊緣設(shè)備間不進(jìn)行任務(wù)卸載.

4)ICE.利用文獻(xiàn)[3]中所提的服務(wù)緩存策略,每次迭代時(shí)依據(jù)收益值以一定概率更新服務(wù)緩存策略,直到達(dá)到迭代終止條件.利用本文所提任務(wù)卸載策略實(shí)現(xiàn)邊緣設(shè)備間協(xié)作.

5)JOC.本文提出的算法,利用3CMAB算法制定服務(wù)緩存策略,利用基于偏好的雙邊匹配算法確定邊緣設(shè)備間的任務(wù)卸載策略,實(shí)現(xiàn)邊緣設(shè)備間協(xié)作.

性能指標(biāo)有:任務(wù)整體執(zhí)行時(shí)延、任務(wù)平均執(zhí)行時(shí)延、邊緣設(shè)備的負(fù)載分配情況以及邊緣設(shè)備的服務(wù)緩存命中率.邊緣設(shè)備的服務(wù)緩存命中率是指對于邊緣設(shè)備能夠執(zhí)行的任務(wù),自身緩存的服務(wù)命中的概率.每個(gè)實(shí)驗(yàn)重復(fù)100次,計(jì)算100組實(shí)驗(yàn)結(jié)果的平均值使得實(shí)驗(yàn)結(jié)果更加準(zhǔn)確.

4.3 實(shí)驗(yàn)結(jié)果

Fig.4 The effect ofβon learning rate圖4 β對學(xué)習(xí)速率的影響

2)拓?fù)浣Y(jié)構(gòu).任務(wù)卸載和服務(wù)緩存均與網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)高度相關(guān),下面通過實(shí)驗(yàn)驗(yàn)證網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)對算法性能的影響.分別針對3個(gè)邊緣設(shè)備的2種拓?fù)浣Y(jié)構(gòu)、4個(gè)邊緣設(shè)備的3種拓?fù)浣Y(jié)構(gòu)以及5個(gè)邊緣設(shè)備的3種拓?fù)浣Y(jié)構(gòu)進(jìn)行實(shí)驗(yàn),網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)如圖5所示,其中每個(gè)邊緣設(shè)備旁的數(shù)字表示可連接的邊緣設(shè)備數(shù)量.

實(shí)驗(yàn)結(jié)果如圖6所示.隨著邊緣設(shè)備數(shù)量增加,可以服務(wù)的終端用戶數(shù)量也隨之增加,任務(wù)整體執(zhí)行時(shí)延也進(jìn)一步增加.當(dāng)邊緣設(shè)備數(shù)量固定時(shí),網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)對算法性能有明顯影響.不同網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)下每個(gè)邊緣設(shè)備可連接的邊緣設(shè)備數(shù)量是不同的.當(dāng)可連接的邊緣設(shè)備數(shù)量增加時(shí),任務(wù)整體執(zhí)行時(shí)延降低.相比于最簡單的鏈?zhǔn)酵負(fù)浣Y(jié)構(gòu),環(huán)形和全連接拓?fù)浣Y(jié)構(gòu)下的任務(wù)整體執(zhí)行時(shí)延分別降低了5.39%到12.38%.原因在于隨著可連接的邊緣設(shè)備數(shù)量增加,負(fù)載較重的邊緣設(shè)備可以選擇的任務(wù)卸載位置變多,使得邊緣設(shè)備間負(fù)載更加均衡,從而有效降低了任務(wù)整體執(zhí)行時(shí)延.

Fig.5 Topological structures for different numbers of edge devices圖5 不同邊緣設(shè)備數(shù)量的拓?fù)浣Y(jié)構(gòu)

Fig.6 Effect of topological structure on JOC algorithm performance圖6 拓?fù)浣Y(jié)構(gòu)對JOC算法性能的影響

3)任務(wù)整體執(zhí)行時(shí)延.下面對5種算法的整體執(zhí)行時(shí)延性能進(jìn)行比較.結(jié)果如圖7所示,算法性能JOC＞ICE＞Non_Co＞Random＞Cloud.

Fig.7 Comparison of different algorithms on overall execution delay of tasks圖7 不同算法的任務(wù)整體執(zhí)行時(shí)延對比圖

Cloud算法將所有任務(wù)部署到遠(yuǎn)端云處執(zhí)行,由于傳輸時(shí)延較長,導(dǎo)致實(shí)驗(yàn)性能最差.Random算法和Non_Co算法不考慮邊緣設(shè)備間協(xié)作,即邊緣設(shè)備間不能進(jìn)行任務(wù)卸載,邊緣設(shè)備只能將本地?zé)o法完成的任務(wù)卸載到遠(yuǎn)端云處執(zhí)行,因此性能相對較差.與Random算法相比,Non_Co算法能夠根據(jù)本地情景信息進(jìn)行服務(wù)緩存,有效提高了服務(wù)緩存命中率,因此Non_Co算法性能優(yōu)于Random算法.

ICE算法和JOC算法均考慮邊緣設(shè)備間協(xié)作,通過邊緣設(shè)備間任務(wù)卸載實(shí)現(xiàn)負(fù)載均衡.與ICE算法相比,JOC算法的任務(wù)整體執(zhí)行時(shí)延降低了5.4%.由于終端用戶的服務(wù)需求與其情景信息相關(guān)聯(lián),具有相似情景信息的用戶會(huì)請求相似的服務(wù),因此相對于未考慮用戶情景信息的ICE算法,JOC算法中基于用戶情景信息的服務(wù)緩存策略可以提高緩存命中率,從而能夠?qū)⒏嗟挠?jì)算任務(wù)部署在邊緣設(shè)備上執(zhí)行,有效降低了任務(wù)整體執(zhí)行時(shí)延.此外,ICE算法制定服務(wù)緩存策略時(shí),需要根據(jù)當(dāng)前輪次的服務(wù)緩存收益值與之前輪次的服務(wù)緩存收益值之間的差值,得到后續(xù)的緩存更新概率,需要進(jìn)行多輪迭代后才可以獲得最終的服務(wù)緩存策略,運(yùn)行該算法需要1.958 s.而JOC算法在學(xué)習(xí)完成后,利用學(xué)習(xí)到的模型可直接計(jì)算出服務(wù)緩存策略,運(yùn)行該算法僅需0.001 95 s.由此可知,JOC算法可以顯著降低計(jì)算開銷并且實(shí)現(xiàn)實(shí)時(shí)動(dòng)態(tài)緩存,而ICE算法的計(jì)算復(fù)雜度較高且緩存相對滯后.

4)服務(wù)緩存容量.下面實(shí)驗(yàn)驗(yàn)證邊緣設(shè)備的服務(wù)緩存容量對實(shí)驗(yàn)性能的影響.如圖8所示,Cloud算法中所有任務(wù)均在遠(yuǎn)端云處執(zhí)行,因此邊緣設(shè)備服務(wù)緩存容量變化對該算法的任務(wù)整體執(zhí)行時(shí)延沒有影響.其他4種算法均存在部分任務(wù)在邊緣設(shè)備處執(zhí)行的情況,因此服務(wù)緩存容量對這些算法的任務(wù)整體執(zhí)行時(shí)延產(chǎn)生明顯影響.當(dāng)邊緣設(shè)備的服務(wù)緩存容量增加時(shí),終端用戶所需的服務(wù)將更有可能緩存在邊緣設(shè)備中,因此邊緣設(shè)備可以為更多的終端用戶提供服務(wù),使得卸載到遠(yuǎn)端云的任務(wù)數(shù)量減少,從而使得任務(wù)整體執(zhí)行時(shí)延呈現(xiàn)下降的趨勢.Random算法隨機(jī)選擇服務(wù)進(jìn)行緩存,隨著緩存容量增加,服務(wù)緩存命中增多,因此其任務(wù)整體執(zhí)行時(shí)延呈現(xiàn)單調(diào)下降趨勢,但由于隨機(jī)緩存命中率不高,Random算法性能低于其他3種算法.與Random算法相比,雖然Non_Co,ICE和JOC這3種算法的服務(wù)緩存命中率有所提高,但是當(dāng)服務(wù)緩存容量達(dá)到一個(gè)臨界值之后,邊緣設(shè)備受自身計(jì)算資源限制,無法執(zhí)行更多任務(wù),因此服務(wù)緩存容量繼續(xù)增加并不會(huì)使得任務(wù)整體執(zhí)行時(shí)延持續(xù)下降,最終任務(wù)整體執(zhí)行時(shí)延保持不變.

Fig.8 Impact of edge devices service caching capacity on overall execution delay of tasks圖8 邊緣設(shè)備的服務(wù)緩存容量對任務(wù)整體執(zhí)行時(shí)延的影響

ICE算法和JOC算法中邊緣設(shè)備間可以進(jìn)行任務(wù)卸載實(shí)現(xiàn)負(fù)載均衡,因此任務(wù)整體執(zhí)行時(shí)延較低.當(dāng)服務(wù)緩存容量較低時(shí),由于JOC算法的服務(wù)緩存策略優(yōu)于ICE算法中的服務(wù)緩存策略,因此JOC算法的整體性能優(yōu)于ICE算法.當(dāng)服務(wù)緩存容量增加到5時(shí),2種算法的服務(wù)緩存效果接近相同,此時(shí)2種算法的性能趨于一致.

5)終端用戶數(shù)量.下面通過實(shí)驗(yàn)驗(yàn)證終端用戶數(shù)量對實(shí)驗(yàn)性能的影響.終端用戶數(shù)量增加,任務(wù)整體執(zhí)行時(shí)延隨之增加.為了驗(yàn)證終端用戶數(shù)量對實(shí)驗(yàn)性能的影響,本次實(shí)驗(yàn)采用任務(wù)平均執(zhí)行時(shí)延這一指標(biāo),任務(wù)平均執(zhí)行時(shí)延為任務(wù)整體執(zhí)行時(shí)延除以執(zhí)行的任務(wù)個(gè)數(shù).如圖9所示,Cloud算法中所有任務(wù)均在遠(yuǎn)端云處執(zhí)行,終端用戶數(shù)量增加會(huì)使得終端用戶間傳輸帶寬競爭加劇,進(jìn)而導(dǎo)致任務(wù)平均執(zhí)行時(shí)延增加.對于其他4種算法,隨著終端用戶數(shù)量增加,任務(wù)平均執(zhí)行時(shí)延增加.這是因?yàn)檫吘壴O(shè)備資源有限,隨著任務(wù)數(shù)量增加,每個(gè)任務(wù)可以獲得的資源量逐漸減少,因此導(dǎo)致任務(wù)平均執(zhí)行時(shí)延增加.當(dāng)終端用戶數(shù)量超過邊緣設(shè)備的服務(wù)容量時(shí),邊緣設(shè)備卸載到遠(yuǎn)端云處執(zhí)行的任務(wù)增加,進(jìn)而導(dǎo)致任務(wù)平均執(zhí)行時(shí)延進(jìn)一步增加.JOC算法與ICE算法可在邊緣設(shè)備間進(jìn)行任務(wù)卸載,有效提高邊緣設(shè)備的資源利用率,使得任務(wù)平均執(zhí)行時(shí)延相對較低,因此這2種算法的性能優(yōu)于Non_Co算法.

當(dāng)終端用戶數(shù)量在5～25時(shí),與ICE算法相比,JOC算法能夠獲得更高的服務(wù)緩存命中率,邊緣設(shè)備能夠執(zhí)行更多的任務(wù),因此性能優(yōu)于ICE算法.然而當(dāng)終端用戶數(shù)量超過25后,邊緣設(shè)備受到其自身計(jì)算資源的限制,JOC算法和ICE算法能夠執(zhí)行的任務(wù)數(shù)量趨于一致,因此2種算法的性能基本持平.

Fig.9 Impact of the number of end users on average execution delay of tasks圖9 終端用戶數(shù)量對任務(wù)平均執(zhí)行時(shí)延的影響

6)服務(wù)緩存命中率.下面通過實(shí)驗(yàn)展示不同算法的服務(wù)緩存命中率.Cloud算法中所有任務(wù)均在遠(yuǎn)端云處執(zhí)行,因此本次對比實(shí)驗(yàn)不考慮Cloud算法,僅對其他4種算法進(jìn)行對比.如圖10所示,JOC算法的服務(wù)緩存命中率最高.Non_Co算法根據(jù)本地的情景信息學(xué)習(xí)服務(wù)緩存策略,其服務(wù)緩存命中率僅次于JOC算法.ICE算法的服務(wù)緩存命中率僅優(yōu)于Random算法.

Fig.10 Comparison of different algorithms on service caching hitting ratio圖10 不同算法的服務(wù)緩存命中率對比圖

7)負(fù)載均衡性能.下面通過實(shí)驗(yàn)驗(yàn)證JOC算法可以在邊緣設(shè)備間實(shí)現(xiàn)負(fù)載均衡.在邊緣設(shè)備負(fù)載不均衡的情況下進(jìn)行實(shí)驗(yàn),觀察每個(gè)邊緣設(shè)備的執(zhí)行任務(wù)數(shù)量.如圖11所示,Cloud算法所有任務(wù)均在遠(yuǎn)端云處執(zhí)行,因此所有邊緣設(shè)備的執(zhí)行任務(wù)數(shù)量均為0.Random算法和Non_Co算法未考慮邊緣設(shè)備間協(xié)作,因此這2種算法的邊緣設(shè)備負(fù)載相對不均衡,邊緣設(shè)備執(zhí)行的任務(wù)數(shù)量與自身服務(wù)緩存命中的任務(wù)數(shù)量相關(guān).而ICE算法與JOC算法允許邊緣設(shè)備間進(jìn)行任務(wù)卸載,因此邊緣設(shè)備間負(fù)載相對均衡.由于JOC算法的服務(wù)緩存策略優(yōu)于ICE算法的服務(wù)緩存策略,因此相比于ICE算法,JOC算法在邊緣設(shè)備處執(zhí)行的任務(wù)數(shù)量更多.

根據(jù)圖11中邊緣設(shè)備執(zhí)行的任務(wù)數(shù)量計(jì)算不同算法將任務(wù)卸載到遠(yuǎn)端云處執(zhí)行的比例,如圖12所示.Random算法和Non_Co算法將任務(wù)卸載到遠(yuǎn)端云處執(zhí)行的比例相對較高.與Random算法相比,Non_Co算法的服務(wù)緩存命中率更高,因此任務(wù)卸載到遠(yuǎn)端云處執(zhí)行的比例低于Random算法.ICE算法和JOC算法允許邊緣設(shè)備間進(jìn)行任務(wù)卸載,因此邊緣設(shè)備能夠執(zhí)行更多的任務(wù),任務(wù)卸載到遠(yuǎn)端云處執(zhí)行的比例相對較低.相比于ICE算法,JOC算法的服務(wù)緩存命中率更高,因此JOC算法將任務(wù)卸載到遠(yuǎn)端云處執(zhí)行的比例更低.

Fig.11 Load balancing between edge devices圖11 邊緣設(shè)備間的負(fù)載均衡情況

Fig.12 The percentage of offloading task to cloud for execution圖12 任務(wù)卸載到遠(yuǎn)端云處的執(zhí)行率

5 總 結(jié)

本文研究面向多邊緣設(shè)備協(xié)作的任務(wù)卸載和服務(wù)緩存聯(lián)合優(yōu)化問題,將該問題形式化描述為混合整數(shù)非線性優(yōu)化問題.為了解決該問題,本文提出一種任務(wù)卸載和服務(wù)緩存在線聯(lián)合優(yōu)化(JOC)算法,將原始問題解耦為服務(wù)緩存和任務(wù)卸載2個(gè)子問題.針對服務(wù)緩存子問題,提出基于情景感知組合多臂賭博機(jī)的協(xié)作服務(wù)緩存算法,用于制定邊緣設(shè)備的服務(wù)緩存策略;針對任務(wù)卸載子問題,設(shè)計(jì)基于偏好的雙邊匹配算法,確定邊緣設(shè)備間的任務(wù)卸載策略.仿真實(shí)驗(yàn)表明:與現(xiàn)有算法相比,JOC算法可以獲得更優(yōu)的任務(wù)執(zhí)行性能,同時(shí)實(shí)現(xiàn)邊緣設(shè)備間負(fù)載均衡.