摘 要:智慧樓宇的邊緣計(jì)算環(huán)境中,為了在資源受限且環(huán)境復(fù)雜的情況下最小化系統(tǒng)的整體時(shí)延和能耗,提出了一種結(jié)合數(shù)據(jù)壓縮和改進(jìn)灰狼算法(CLGWO)的邊緣計(jì)算卸載方法。該方法首先采用差分字典編碼壓縮技術(shù)對(duì)數(shù)據(jù)進(jìn)行壓縮,預(yù)估數(shù)據(jù)壓縮率及其產(chǎn)生的開銷;隨后引入萊維飛行算法和螺旋漸近狩獵方式對(duì)灰狼算法進(jìn)行改進(jìn),以增強(qiáng)其全局搜索能力;最后結(jié)合預(yù)估壓縮效果和改進(jìn)灰狼算法求得最佳卸載方案。實(shí)驗(yàn)結(jié)果表明,CLGWO方法能夠顯著降低計(jì)算任務(wù)卸載的整體延遲和能耗,證實(shí)了該方法的有效性和可行性,為樓宇中邊緣計(jì)算卸載問(wèn)題提供了一種新的解決方案。
關(guān)鍵詞:移動(dòng)邊緣計(jì)算;計(jì)算卸載;數(shù)據(jù)壓縮;任務(wù)調(diào)度;灰狼算法優(yōu)化
中圖分類號(hào):TP393 文獻(xiàn)標(biāo)志碼:A 文章編號(hào):1001-3695(2024)11-015-3311-06
doi:10.19734/j.issn.1001-3695.2024.03.0095
Edge computing offloading method based on data compression and improved grey wolf optimizer on smart building
Shen Zheng, Lu Xianling?
(School of Internet of Things Engineering, Jiangnan University, Wuxi Jiangsu 214122, China)
Abstract:In the edge computing environment of smart buildings, to minimize the overall system latency and energy consumption in resource-constrained and complex conditions, this paper proposed an edge computing offloading method based on data compression and improved gray wolf algorithm (CLGWO). Firstly, it used the differential dictionary encoding compression method to estimate the data compression rate and the overhead incurred by compression. It combined the Lévy flight algorithm and spiral asymptotic hunting method to enhance the global search capability of the grey wolf optimizer. Finally, it determined the optimal offloading scheme by combining the estimated compression effects with the improved grey wolf optimizer. Experimental results indicate that the CLGWO method reduces the overall latency and energy consumption of computing task offloa-ding, thereby verifying its effectiveness and feasibility. This approach provides a new solution to the edge computing offloading problem in buildings.
Key words:mobile edge computing; calculate offloading; data compression; task scheduling; gray wolf algorithm optimization
0 引言
在物聯(lián)網(wǎng)技術(shù)的推動(dòng)下,智能樓宇的發(fā)展催生了大量網(wǎng)絡(luò)終端設(shè)備,這些設(shè)備支撐著對(duì)實(shí)時(shí)響應(yīng)速度有嚴(yán)格要求的計(jì)算密集型應(yīng)用。例如安防監(jiān)控、火災(zāi)預(yù)警系統(tǒng)、門禁控制等。特別是在醫(yī)院這樣的特殊樓宇環(huán)境中,還需要設(shè)備實(shí)時(shí)監(jiān)測(cè)病人的關(guān)鍵生命體征,包括體溫、心率、血氧飽和度,以及進(jìn)行防跌倒的姿態(tài)檢測(cè)。這些應(yīng)用不僅需要快速處理大量數(shù)據(jù),還要求極低的延遲[1,2]。由于移動(dòng)終端的計(jì)算能力和能源有限,它們?cè)谔幚磉@些大規(guī)模數(shù)據(jù)時(shí)往往需要依賴云計(jì)算資源[3]。但云計(jì)算在處理高并發(fā)和低延遲需求時(shí)存在局限性。為了克服這些挑戰(zhàn),邊緣計(jì)算作為一種新興的計(jì)算架構(gòu)應(yīng)運(yùn)而生。
通過(guò)將計(jì)算任務(wù)從云端遷移到用戶附近的邊緣服務(wù)器,邊緣計(jì)算不僅優(yōu)化了數(shù)據(jù)傳輸路徑,減少了數(shù)據(jù)在網(wǎng)絡(luò)中的傳輸時(shí)間,還提高了處理效率和響應(yīng)速度。這種計(jì)算卸載策略使得邊緣服務(wù)器能夠承擔(dān)更多的數(shù)據(jù)處理任務(wù),減輕了云端的負(fù)擔(dān),同時(shí)也為用戶提供了更快速、更可靠的服務(wù)[4~6]。因此,研究如何根據(jù)具體的應(yīng)用場(chǎng)景和需求,制定合理的任務(wù)卸載策略,成為了邊緣計(jì)算領(lǐng)域的關(guān)鍵研究課題。
文獻(xiàn)[7]中提出聯(lián)合卸載決策和任務(wù)調(diào)度算法(JODTS),通過(guò)將范圍遺傳算法(PGA)與啟發(fā)式規(guī)則相結(jié)合,實(shí)現(xiàn)邊緣計(jì)算中任務(wù)卸載問(wèn)題的優(yōu)化。文獻(xiàn)[8]中提出的IMTS-D3QN算法采用競(jìng)爭(zhēng)網(wǎng)絡(luò)結(jié)構(gòu)對(duì)神經(jīng)網(wǎng)絡(luò)進(jìn)行優(yōu)化,通過(guò)不同線性加權(quán)組合得出帕累托最優(yōu)解,達(dá)到響應(yīng)時(shí)間和能耗最小化。文獻(xiàn)[9]中基于深度強(qiáng)化學(xué)習(xí)的分布式任務(wù)卸載算法,允許每個(gè)移動(dòng)設(shè)備在不了解其他移動(dòng)設(shè)備任務(wù)模型和卸載決策的情況下作出卸載決策,減少延遲和丟包的比例,提升服務(wù)效率。上述文獻(xiàn)致力于開發(fā)算法提升解決方案性能,但這些算法普遍基于深度學(xué)習(xí)或群智能算法求解問(wèn)題,全局尋優(yōu)能力有限,算法本身仍然存在局限性。
文獻(xiàn)[10]提出的HCOGA基于5G實(shí)時(shí)環(huán)境,通過(guò)深度神經(jīng)網(wǎng)絡(luò)擬合改進(jìn)非支配遺傳算法輸入、輸出間的非線性關(guān)系,構(gòu)成完備的卸載預(yù)測(cè)模型,快速、準(zhǔn)確地作出卸載決策。文獻(xiàn)[11]中提出的IVA-GWO算法通過(guò)平衡全局和局部搜索的能力,引入自適應(yīng)變異因子防止算法陷入局部極值,提高了算法的效率和準(zhǔn)確性。文獻(xiàn)[12]中提出的IGHA,結(jié)合系統(tǒng)對(duì)其內(nèi)部的平均開銷、時(shí)延與能耗的要求,在任務(wù)卸載過(guò)程中實(shí)現(xiàn)最優(yōu)資源分配。上述文獻(xiàn)側(cè)重于結(jié)合實(shí)際應(yīng)用場(chǎng)景構(gòu)建有針對(duì)性的數(shù)學(xué)模型,如基于車聯(lián)網(wǎng)、移動(dòng)多用戶等相關(guān)環(huán)境進(jìn)行研究,尚未對(duì)卸載數(shù)據(jù)壓縮性質(zhì)方面進(jìn)行研究,且現(xiàn)有算法提升效果不顯著。
相比于車聯(lián)網(wǎng)邊緣計(jì)算環(huán)境[13],智慧樓宇環(huán)境中產(chǎn)生的數(shù)據(jù)具備強(qiáng)周期性和時(shí)間重復(fù)性,本文針對(duì)這類與時(shí)間序列緊密關(guān)聯(lián)的數(shù)據(jù),提出采用差分字典編碼壓縮技術(shù)[14],以期通過(guò)壓縮算法減少數(shù)據(jù)量來(lái)降低數(shù)據(jù)傳輸時(shí)延。同時(shí)鑒于樓宇邊緣計(jì)算環(huán)境的復(fù)雜性、能耗限制和實(shí)時(shí)性要求,進(jìn)一步構(gòu)建了一個(gè)優(yōu)化模型,該模型綜合考慮了本地執(zhí)行、云端傳輸、數(shù)據(jù)壓縮等多個(gè)因素,以最小化整體時(shí)延和能耗為目標(biāo),從而尋找最優(yōu)的任務(wù)卸載策略。
為了實(shí)現(xiàn)這一目標(biāo),本文又引入了改進(jìn)灰狼算法來(lái)求解該優(yōu)化模型,進(jìn)而得到最優(yōu)策略?;依撬惴ㄒ云浣Y(jié)構(gòu)簡(jiǎn)潔、參數(shù)調(diào)整少、易于實(shí)現(xiàn)的特點(diǎn),在求解精度和收斂速度上均表現(xiàn)出色[15]。然而,傳統(tǒng)灰狼算法在迭代后期可能因種群初始化方式的隨機(jī)性導(dǎo)致大量重復(fù),進(jìn)而陷入局部最優(yōu)解[16~19]。因此,本文提出了結(jié)合萊維飛行算法的策略,通過(guò)引入隨機(jī)步長(zhǎng)來(lái)擴(kuò)展搜索范圍,增強(qiáng)灰狼種群的多樣性,從而有效提升算法的性能。
本文主要貢獻(xiàn)如下:
a)系統(tǒng)模型構(gòu)建:構(gòu)建了一個(gè)適用于樓宇邊緣計(jì)算環(huán)境的計(jì)算時(shí)延與能耗模型。該模型綜合考慮了任務(wù)的計(jì)算時(shí)延、能耗以及移動(dòng)邊緣計(jì)算(MEC)服務(wù)器的計(jì)算資源限制。同時(shí)設(shè)計(jì)了系統(tǒng)整體開銷函數(shù)用于對(duì)計(jì)算卸載策略的評(píng)價(jià),將計(jì)算任務(wù)卸載問(wèn)題轉(zhuǎn)換為在約束條件下的單目標(biāo)優(yōu)化問(wèn)題。
b)基于數(shù)據(jù)壓縮和改進(jìn)灰狼算法的卸載方法:提出了一種新穎的計(jì)算方法用于求解卸載問(wèn)題,該方法將待卸載數(shù)據(jù)分為字典和差分?jǐn)?shù)據(jù)兩部分來(lái)減小傳輸數(shù)據(jù)量。同時(shí)在灰狼算法的基礎(chǔ)上引入了螺旋漸近狩獵策略和萊維飛行算法,對(duì)灰狼算法的種群初始化、最優(yōu)解選擇等環(huán)節(jié)進(jìn)行改進(jìn),以提高求解的效率。
c)仿真實(shí)驗(yàn)驗(yàn)證和應(yīng)用測(cè)試分析:設(shè)計(jì)仿真實(shí)驗(yàn)對(duì)邊緣計(jì)算卸載策略進(jìn)行驗(yàn)證,從計(jì)算時(shí)延、計(jì)算能耗、收斂性等方面對(duì)邊緣計(jì)算卸載策略的性能進(jìn)行評(píng)估分析。
1 系統(tǒng)模型和問(wèn)題描述
1.1 系統(tǒng)模型
本文構(gòu)建了智慧樓宇物聯(lián)網(wǎng)邊緣計(jì)算環(huán)境的系統(tǒng)模型,適用于住宅、醫(yī)院、園區(qū)等環(huán)境,雖然應(yīng)用場(chǎng)景有所差異,但其核心架構(gòu)統(tǒng)一由終端、邊緣端和云端三層構(gòu)成。系統(tǒng)模型如圖1所示。
終端設(shè)備層:包含多類傳感器(溫濕度、亮度、煙霧等)和控制器(水泵、暖閥等),負(fù)責(zé)數(shù)據(jù)收集和控制任務(wù)。大多數(shù)設(shè)備采用低功耗技術(shù)延長(zhǎng)電池壽命。
邊緣端服務(wù)器層:由邊緣服務(wù)器構(gòu)成,接收終端設(shè)備數(shù)據(jù),進(jìn)行初步處理,減輕云端負(fù)擔(dān)。同時(shí)邊緣端距離應(yīng)用場(chǎng)景較近,任務(wù)處理時(shí)效性好。
云端服務(wù)器層:其擁有近乎無(wú)限的計(jì)算能力,當(dāng)邊緣端服務(wù)器面臨算力瓶頸時(shí),它們可以將復(fù)雜任務(wù)和數(shù)據(jù)上傳至云端進(jìn)行進(jìn)一步處理,但云端會(huì)存在一定的通信延時(shí)。
與車聯(lián)網(wǎng)等邊緣計(jì)算應(yīng)用場(chǎng)景相比,智慧樓宇環(huán)境下的邊緣計(jì)算面臨著一系列挑戰(zhàn)。如圖2所示,首先是環(huán)境復(fù)雜性,如多樓層、房間分隔導(dǎo)致多樣化的設(shè)備布局,以及設(shè)備的失效或者受到干擾可能導(dǎo)致通信質(zhì)量的不穩(wěn)定,IoT設(shè)備基于自動(dòng)組網(wǎng)的能力動(dòng)態(tài)調(diào)整網(wǎng)絡(luò)拓?fù)浼軜?gòu)。這些因素導(dǎo)致其難以預(yù)先設(shè)計(jì)好邊緣端算力,只能在部署完成后再生成適用于當(dāng)前布局的卸載策略。其次是實(shí)時(shí)性,樓宇數(shù)據(jù)具有更強(qiáng)的周期性和時(shí)間重復(fù)性,要求邊緣計(jì)算卸載策略能夠適應(yīng)這種數(shù)據(jù)特性,以實(shí)現(xiàn)有效的數(shù)據(jù)壓縮和傳輸,保證低延遲的數(shù)據(jù)處理。最后是能耗限制,樓宇設(shè)備依賴電池需節(jié)能運(yùn)行,生成邊緣計(jì)算卸載策略需兼顧計(jì)算效率、實(shí)時(shí)性與能耗,以實(shí)現(xiàn)能源高效利用。
基于上述架構(gòu),終端設(shè)備的集合表示為N={N1,N2,…,Ni},邊緣端設(shè)備的集合表示為S={S1,S2,…,Si}。通過(guò)調(diào)整可控參數(shù),制定最合適的卸載策略,達(dá)到最佳平衡點(diǎn)以實(shí)現(xiàn)整體時(shí)延最小和能耗最低。
1)本地執(zhí)行計(jì)算開銷
在評(píng)估執(zhí)行任務(wù)的成本時(shí)主要考慮時(shí)延和能耗兩個(gè)關(guān)鍵的性能指標(biāo)。時(shí)延直接反映了系統(tǒng)對(duì)任務(wù)的響應(yīng)速度,而能耗則關(guān)聯(lián)到設(shè)備的運(yùn)行成本和環(huán)境影響。將時(shí)延和能耗放在一起加權(quán)求和作為衡量系統(tǒng)總成本的指標(biāo),可使系統(tǒng)在滿足實(shí)時(shí)性要求的同時(shí),盡可能地降低能耗。
本地計(jì)算的時(shí)延直接取決于本身的計(jì)算能力。終端設(shè)備Ni產(chǎn)生任務(wù)i的數(shù)據(jù)量表示為Datai,Li表示該任務(wù)的復(fù)雜度指標(biāo),Li值越大,任務(wù)所需的CPU資源越多,相應(yīng)的計(jì)算時(shí)間復(fù)雜度也就越高。定義di作為卸載策略參數(shù),取值在[0,1],0代表任務(wù)在本地執(zhí)行,1則表示任務(wù)被上傳至云端。
本地執(zhí)行任務(wù)i時(shí),其計(jì)算時(shí)延ti由式(1)給出[10]:
tlocal,i=(1-di)LiDataifi(1)
其中: fi表示本地設(shè)備Si執(zhí)行任務(wù)i時(shí)的CPU頻率。CPU頻率越高,執(zhí)行速度越快,任務(wù)的計(jì)算時(shí)延就越小。同時(shí),任務(wù)的能耗elocal,i與任務(wù)的CPU需求、數(shù)據(jù)量等因素緊密相關(guān),表示為
elocal,i=Zi(1-di)LiDatai(2)
此處,Zi代表執(zhí)行任務(wù)i時(shí)每單位CPU周期的能耗,其計(jì)算公式為Zi=10-27f2i。隨著CPU頻率的升高,雖然時(shí)延減小,但能耗也隨之增加;相反,低頻率下的能耗雖低,卻會(huì)導(dǎo)致時(shí)延增大。將時(shí)延與能耗結(jié)合,可以定義任務(wù)i在本地執(zhí)行的整體成本Flocal,i:
Flocal,i=witlocal,i+(1-wi)elocal,i(3)
這里的加權(quán)系數(shù)0lt;ωilt;1用來(lái)平衡任務(wù)i對(duì)于時(shí)延和能耗的敏感度,wi接近1表示任務(wù)對(duì)時(shí)延非常敏感,而1-wi接近1則表示任務(wù)對(duì)能耗較為敏感。默認(rèn)情況下,設(shè)定時(shí)延和能耗的加權(quán)因子相等,均為0.5。
當(dāng)所有任務(wù)都在本地執(zhí)行時(shí),整個(gè)系統(tǒng)的總時(shí)延和能耗成本為
Costlocal=∑ni=1Flocal,i(4)
2)上傳到云端計(jì)算開銷
除本地執(zhí)行外,設(shè)備還可以選擇將任務(wù)卸載到云端進(jìn)行處理。卸載過(guò)程主要包括三步:首先,通過(guò)設(shè)備差分字典編碼法對(duì)即將上傳的數(shù)據(jù)進(jìn)行壓縮,壓縮方法將在2.1節(jié)中詳細(xì)闡述;然后通過(guò)無(wú)線網(wǎng)絡(luò)將壓縮后的數(shù)據(jù)上傳至云服務(wù)器,服務(wù)器接收到任務(wù)請(qǐng)求后,對(duì)數(shù)據(jù)進(jìn)行解碼解壓并執(zhí)行計(jì)算;最后,計(jì)算結(jié)果通過(guò)下行鏈路返回給設(shè)備。
任務(wù)i在云端和邊緣端傳輸?shù)臅r(shí)延計(jì)算公式為
ttransmit,i=diciDataiVi(5)
其中:Vi是用戶上傳任務(wù)i的數(shù)據(jù)傳輸速率。假設(shè)邊緣端網(wǎng)絡(luò)設(shè)備覆蓋范圍內(nèi),用戶端k的信道增益為hkj,網(wǎng)關(guān)j的發(fā)射功率為Pj,終端設(shè)備k的上行發(fā)射功率為Pk,高斯白噪聲為δ2 。用戶k的信噪比可以通過(guò)香農(nóng)公式計(jì)算得到
rk=h2kjPk∑jh2kjPj+δ2(6)
實(shí)際應(yīng)用中,無(wú)線信道帶寬設(shè)為W,基于信噪比rk,終端設(shè)備k上傳任務(wù)i時(shí)的最大上傳速率可近似為Vmax=W lg(1+rk)。為了簡(jiǎn)化計(jì)算,通??梢岳迷O(shè)備通信模塊中的RSSI值來(lái)估算傳輸速率。例如在Wi-Fi環(huán)境下,RSSI值遵循公式RSSI=-10n log10(d)+A,其中d為設(shè)備間距離,n為環(huán)境衰減系數(shù),A為校準(zhǔn)因子。
任務(wù)i上傳過(guò)程中的能耗etransmit,i可由以下公式表示:
etransmit,i=PidiciDataiVi+Ecompress(7)
其中:Ecompress為使用差分字典編碼過(guò)程帶來(lái)的額外能耗,與壓縮率ci有關(guān)。傳輸過(guò)程的綜合成本為
Ftransmit,i=wittransmit,i+(1-wi)etransmit,i(8)
上傳至云端的任務(wù)i的計(jì)算時(shí)延可視為
tedge,i=diXifcloud(9)
其中: fcloud是云端運(yùn)算的CPU主頻,一般選取主流服務(wù)器的1~4 GHz。這里忽略了云端解壓縮的時(shí)間,假設(shè)云端在已有字典的情況下能夠快速解壓縮數(shù)據(jù)。
云端計(jì)算任務(wù)i的能耗簡(jiǎn)化為與其運(yùn)行時(shí)間直接相關(guān),即
eedge,i=Wcloud*tedge,i(10)
其中:Wcloud是服務(wù)器平均功率,取主流服務(wù)器功率大約是400 W。
當(dāng)所有任務(wù)都卸載至云端執(zhí)行時(shí),整個(gè)系統(tǒng)的時(shí)延和能耗成本為
Costcloud=∑ni=1Ftransmit,i+Fedge,i(11)
1.2 問(wèn)題描述
依據(jù)卸載策略合理分配計(jì)算任務(wù)在本地和云端執(zhí)行,任務(wù)i的整體成本可表示為
Ftotal,i=wi(tlocal,i+ttransmit,i+tedge,i)+
(1-wi)(elocal,i+etransmit,i+eedge,i)(12)
假設(shè)所有任務(wù)必須在限定時(shí)間內(nèi)完成,即任務(wù)完成時(shí)限為τ,優(yōu)化目標(biāo)是在滿足最大系統(tǒng)時(shí)延和最大系統(tǒng)容量限制條件下,最小化系統(tǒng)整體成本。
因此,問(wèn)題可以描述為
Costtotal=∑ni=1Ftotal,i
C1:di∈[0,1],wi∈[0,1]C2:tlocal,ilt;τ
C3:ttransmit,i+tedge,ilt;τ
C4:fi∈[100 MHz,1000 MHz]C5:Pi∈[1 W,10 W](13)
約束條件C1描述了變量范圍。約束條件C2和C3表示任務(wù)的最大完成時(shí)間不能超過(guò)預(yù)設(shè)的最終交付時(shí)間,否則不能保證結(jié)果的實(shí)時(shí)性。C4、C5分別是本地設(shè)備主頻和發(fā)射功率的限制范圍。該問(wèn)題是混合整數(shù)非線性規(guī)劃,具有非確定多項(xiàng)式難度(NP-hard)。
2 問(wèn)題求解
2.1 任務(wù)數(shù)據(jù)的壓縮方法
在智能樓宇環(huán)境下的邊緣計(jì)算場(chǎng)景中,數(shù)據(jù)通常呈現(xiàn)出強(qiáng)烈的時(shí)間相關(guān)性和周期性特征,這為數(shù)據(jù)壓縮提供了優(yōu)化空間。本文創(chuàng)新性地提出了差分字典編碼壓縮技術(shù),專門針對(duì)此類具有重復(fù)模式的時(shí)間序列數(shù)據(jù)。該方法的核心機(jī)制在于構(gòu)建一個(gè)動(dòng)態(tài)字典,將相似的時(shí)間序列片段視為字典中的條目來(lái)進(jìn)行處理[13]。
首先,在邊緣計(jì)算環(huán)境初始化階段,將全天時(shí)間分割為多個(gè)連續(xù)時(shí)段,并按時(shí)段收集終端上傳的數(shù)據(jù)。以智能樓宇光環(huán)境下的光電傳感器數(shù)據(jù)為例,將峰譜去除底噪后分解成單個(gè)有效峰譜,對(duì)每個(gè)峰譜進(jìn)行高斯擬合后產(chǎn)生特征碼Ymax和δ,保存成字典編碼lighti=[Ymax,δ]。上述傳感器數(shù)據(jù)預(yù)處理過(guò)程如圖3所示。
初始狀態(tài)下,字典D為空集。當(dāng)接收到首個(gè)時(shí)段的數(shù)據(jù)集M0(包括但不限于亮度light0、溫度tmp0、風(fēng)速wind0等多種參數(shù)的變化曲線)時(shí),將其添加至字典D中,即D={M0}。
接下來(lái),在收到第二個(gè)時(shí)段的數(shù)據(jù)集Mtemp={lighttemp,tmptemp,windtemp,…}時(shí),逐一與字典中已有的數(shù)據(jù)項(xiàng)進(jìn)行比較,若各參數(shù)值的平方差之和小于預(yù)設(shè)閾值ε,即滿足M2temp-M20lt;ε,則記錄當(dāng)前數(shù)據(jù)的微小變化量形成差分?jǐn)?shù)據(jù)包Ni,由于N的數(shù)據(jù)量明顯小于原始數(shù)據(jù)M,從而得到高效的壓縮效果。若平方差之和超過(guò)閾值,則生成新的編碼M1并更新字典D為D={M0,M1}。
按照這一規(guī)律迭代進(jìn)行,直至處理第n個(gè)時(shí)段的數(shù)據(jù)。每當(dāng)新的時(shí)段數(shù)據(jù)到來(lái)時(shí),與字典D={M0,M1,…,Mi}中的所有編碼逐一比對(duì),若無(wú)相近數(shù)據(jù),則更新字典。隨著字典不斷積累與更新,后續(xù)數(shù)據(jù)匹配到已有編碼的概率逐步提升,進(jìn)而持續(xù)提高壓縮效率。
依據(jù)數(shù)據(jù)和字典中的匹配程度,預(yù)估數(shù)據(jù)壓縮率和壓縮開銷(額外時(shí)間和額外能耗)導(dǎo)入給改進(jìn)灰狼算法,判斷當(dāng)前任務(wù)是本地執(zhí)行還是上傳執(zhí)行(卸載執(zhí)行),如果是上傳執(zhí)行則進(jìn)行數(shù)據(jù)壓縮操作,改進(jìn)灰狼算法將在2.2節(jié)詳細(xì)敘述。
差分字典編碼壓縮流程如圖4所示。
2.2 改進(jìn)灰狼算法
灰狼優(yōu)化算法(GWO)是一種受自然界灰狼狩獵行為及其社會(huì)層級(jí)結(jié)構(gòu)啟發(fā)的群體智能優(yōu)化算法。算法設(shè)計(jì)的核心在于借鑒灰狼的狩獵過(guò)程,包括包圍、追蹤、精確攻擊獵物以及不斷探索新目標(biāo)的行為。然而,傳統(tǒng)的灰狼優(yōu)化算法在處理復(fù)雜多模態(tài)優(yōu)化問(wèn)題時(shí),往往容易陷入局部最優(yōu),導(dǎo)致計(jì)算時(shí)間長(zhǎng)、收斂性能差以及優(yōu)化效果不理想。
2.2.1 算法初始解的改進(jìn)
為克服傳統(tǒng)灰狼優(yōu)化算法易陷入局部最優(yōu)的局限,本研究改進(jìn)了種群初始化策略,采用混沌映射生成初始種群位置,以增強(qiáng)全局搜索能力。針對(duì)智能樓宇中常見(jiàn)的周期性離散數(shù)據(jù),采用Circle映射進(jìn)行初始化,其數(shù)學(xué)表達(dá)式如下:
xk+1=mod(xk+b-(a2π)sin(2πxk),1)(14)
其中:a和b是常數(shù)。在Circle映射中,通常取a=0.5, b=0.2。
Circle映射在迭代過(guò)程中生成的混沌序列展現(xiàn)出獨(dú)特的隨機(jī)性、遍歷性和規(guī)律性,這些特性與樓宇環(huán)境中的數(shù)據(jù)存在相似之處,有助于提升算法的收斂速度。
2.2.2 算法搜索范圍的改進(jìn)
為避免灰狼算法陷入局部最優(yōu)解,可以融入鯨魚算法中的螺旋漸近狩獵方式和隨機(jī)概率因子進(jìn)行對(duì)比選擇,同時(shí)引入萊維飛行算法利用隨機(jī)步長(zhǎng)來(lái)擴(kuò)展算法搜索范圍,可以增強(qiáng)算法的搜索范圍和豐富灰狼種群的多樣性。具體改進(jìn)方法如下。
首先,按照Mantegna提出的隨機(jī)步長(zhǎng)公式生成Levy(d),公式如下:
Levy(d)=u|v|1d(15)
其中:參數(shù)d一般取值于[0,2]的常數(shù),這里取值1.5;u和v分別服從u~N(0,σ2)和v~N(0,1)。
σ=Γ(1+d)×sind×π2d×Γ1+d2×2d-121d(16)
然后,引入隨機(jī)概率因子p∈[0,1],當(dāng)p≥0.5時(shí),灰狼群體根據(jù)最優(yōu)解的位置結(jié)合著Lévy飛行算法和螺旋泡網(wǎng)狩獵行為進(jìn)行位置更新,如下所示。
X′(t)=Xbest(t)+evlcos(2πl(wèi))|Xbest-X(t)|·Levy(d)(17)
其中:Xbest表示全局的最優(yōu)解; X表示灰狼個(gè)體的位置;Xα、Xβ、Xδ分別代表領(lǐng)導(dǎo)狼群的三只頭狼;v為螺旋方程中的常量系數(shù),其值通常被設(shè)定為1;l是-1~1的隨機(jī)數(shù)。當(dāng)p≤0.5時(shí),算法按照式(18)~(21)進(jìn)行包圍計(jì)算,在這個(gè)計(jì)算過(guò)程中,n1和n2是在[0,1]中隨機(jī)取值的向量,m=2-2t/T,t表示當(dāng)前迭代次數(shù),T表示最大迭代次數(shù),隨著迭代次數(shù)的增加,m的值會(huì)從2線性遞減到0。
A=2×m×n1-mC=2×n2(18)
Dα=|C1·Xα-X(t)|Dβ=|C2·Xβ-X(t)|Dδ=|C3·Xδ-X(t)|(19)
X1(t+1)=Xα(t)-A1·DαX2(t+1)=Xβ(t)-A2·DβX3(t+1)=Xδ(t)-A3·Dδ(20)
X(t+1)=13(X1(t+1)+X2(t+1)+X3(t+1))(21)
灰狼算法在尋找最優(yōu)解時(shí),α狼對(duì)應(yīng)的位置不一定是全局最優(yōu)解,其他等級(jí)的灰狼個(gè)體也很難跳出各自的局部最優(yōu)解,從而導(dǎo)致算法處理時(shí)間大幅度增加,收斂性下降。為了改進(jìn)GWO的求解精度和收斂速度,受自定義權(quán)重的啟發(fā),設(shè)置了一種新的比例權(quán)重,設(shè)定不同灰狼個(gè)體影響最優(yōu)解的比例不同,動(dòng)態(tài)權(quán)重表達(dá)式如下:
W1=|X1||X1|+|X2|+|X3|W2=|X2||X1|+|X2|+|X3|W3=|X3||X1|+|X2|+|X3|(22)
X′(t)=W1·(X1-Xα)+W2·(X1-Xβ)+W3·(X1-Xδ)(23)
為了選擇更好的結(jié)果,需比較X(t+1)和X(t)的適應(yīng)度值,保留其對(duì)應(yīng)的最小適應(yīng)度函數(shù)值,作為本次迭代結(jié)果X(t+1),并記錄其位置,即
X(t+1)=X′(t)
fitness(X′(t))lt;fitness(X(t))
X(t+1)=X(t) otherwise(24)
2.3 算法流程及描述
算法1 CLGWO算法
輸入:種群數(shù)量population_size,最大迭代數(shù)量max_iter,時(shí)延和能耗權(quán)重配比wi,任務(wù)完成時(shí)限τ,每個(gè)設(shè)備待處理的數(shù)據(jù)量Datai,傳輸速率Vi,設(shè)備數(shù)量n,以及參數(shù)的上下界。
輸出:全局最優(yōu)值Xbest。
a)根據(jù)Datai與字典的匹配程度預(yù)估壓縮率ci和壓縮開銷cpi,其中(i=1,2,…,n)。
b)使用式(14)來(lái)初始化卸載分配參數(shù)di,邊緣設(shè)備主頻fi及發(fā)射功率Pi,其中(i=1,2,…,n)。
c)將上述參數(shù)合并成一個(gè)向量作為初始化的灰狼種群位置Xi(0)=[di, fi,Pi] (i=1,2,…,n)。
d)for t=1,2,…,max_iter do
e)for i=1,2,…,1∶population_size do
f) 代入Datai,wi, Vi,τ,ci,cpi計(jì)算Xi(t)適應(yīng)度值fitness,選擇fitness最好的三頭狼作為頭狼Xα(t),Xβ(t),Xδ(t)
g)end for
h)if (pgt;=0.5) 使用式(17)來(lái)計(jì)算X′(t)
i)else if (plt;0.5) 使用式(18)~(22)來(lái)計(jì)算X′(t)
j) 使用式(24)來(lái)比較X′(t)與X(t)的fitness,較好結(jié)果保存為頭狼位置X(t+1)
k) 根據(jù)限制條件修正灰狼個(gè)體參數(shù),保證在有效范圍內(nèi)
l) 循環(huán)迭代次數(shù)max_iter加一
m) end for
n) 將α狼的fitness賦給Xmin,將α狼的位置賦給Xpos
o) return Xbest=[Xmin,Xpos]3 仿真結(jié)果分析和應(yīng)用測(cè)試分析
3.1 仿真設(shè)定
基于MATLAB 2022b仿真平臺(tái)進(jìn)行實(shí)驗(yàn)驗(yàn)證,構(gòu)建智能樓宇環(huán)境下的邊緣計(jì)算卸載模型,對(duì)CLGWO算法進(jìn)行性能仿真,并選擇以下六種卸載方式進(jìn)行對(duì)比:Local、Cloud、Random、PSO、GWO和 LGWO。其中 Local 方式代表任務(wù)只在本地執(zhí)行,Cloud方式代表任務(wù)全部上傳(卸載)到云端執(zhí)行,Random 方式代表任務(wù)在本地或者云端隨機(jī)進(jìn)行計(jì)算卸載,PSO方式為基于傳統(tǒng)群智能優(yōu)化方式粒子群算法求解輸出的最優(yōu)卸載策略[20,21],GWO方式為基于灰狼算法進(jìn)行求解輸出的最優(yōu)卸載策略,LGWO 方式為基于動(dòng)態(tài)權(quán)重策略的改進(jìn)灰狼算法進(jìn)行求解輸出最優(yōu)卸載策略。具體仿真參數(shù)設(shè)置如表1所示。
3.2 仿真結(jié)果分析
3.2.1 邊緣設(shè)備數(shù)量對(duì)總成本的影響
圖5為邊緣設(shè)備數(shù)量與系統(tǒng)總成本(全部設(shè)備時(shí)延與能耗總和)的關(guān)系,在終端數(shù)為30時(shí),CLGWO策略相比Local方式降低了85.8%,比Cloud方式降低31.7%,比Random方式降低30.08%,比GWO方式降低10.6%,比LGWO方式降低10.03%,比PSO方式降低10.7%。
可以看出,隨著邊緣設(shè)備接入數(shù)量的增加,總?cè)蝿?wù)量也在增加,相應(yīng)的系統(tǒng)總成本也在增加。本地執(zhí)行總成本增加得最快,基本和邊緣設(shè)備數(shù)量呈線性關(guān)系。而其他幾種卸載方式因?yàn)橛性贫说膮⑴c,一定程度上緩解了總成本的增加速度。CLGWO方式因?yàn)槭褂昧瞬罘肿值渚幋a對(duì)數(shù)據(jù)進(jìn)行預(yù)壓縮,減小了數(shù)據(jù)體積也減小了能耗。
3.2.2 通信環(huán)境對(duì)總成本的影響
圖6為邊緣設(shè)備上通信模塊的RSSI(received signal strength indication)值與系統(tǒng)總成本的關(guān)系,RSSI值獲取比較直觀,而且能真實(shí)反映當(dāng)前的通信環(huán)境。對(duì)比來(lái)看,CLGWO 策略的系統(tǒng)總成本最小。RSSI值為 80 dBm 時(shí),CLGWO方式系統(tǒng)總成本相比Local方式降低了16.9%,比Cloud方式降低了8.4%,比Random 方式降低 9.7%,比 GWO方式降低4.4%,比LGWO方法降低4.2%,比PSO方式降低4.7%。
可以看到CLGWO因?yàn)槭褂昧瞬罘肿值渚幋a對(duì)數(shù)據(jù)進(jìn)行預(yù)壓縮,減小了數(shù)據(jù)體積,受通信環(huán)境的影響較小,而全部卸載到云端的Cloud方法受RSSI影響最大。
3.2.3 每個(gè)邊緣設(shè)備的任務(wù)量對(duì)總成本的影響
圖7為每個(gè)邊緣設(shè)備的任務(wù)量與系統(tǒng)總成本的關(guān)系,對(duì)于不同卸載策略,隨著每個(gè)邊緣設(shè)備的計(jì)算任務(wù)量加大,系統(tǒng)總成本總體呈上升趨勢(shì)。但本地執(zhí)行任務(wù)會(huì)隨著本地資源的耗盡,系統(tǒng)時(shí)延快速增加,導(dǎo)致相較于其他有云端輔助的方法,系統(tǒng)總成本上升較快。而其他幾種算法中,CLGWO上升趨勢(shì)最小,卸載效果最佳。另外,總體來(lái)看,在任務(wù)量為50 MB時(shí),CLGWO方式相比Local方式降低了66.72%,比Cloud方式降低41.84%,比Random方式降低36.03%,比GWO方式降低1.87%,比LGWO方式降低2.12%,比PSO方式降低2.20%,這證明CLGWO方法在六種卸載策略中應(yīng)對(duì)數(shù)據(jù)量的增加效果最好。
3.2.4 算法收斂性對(duì)比
為了對(duì)比GWO、LGWO、CLGWO三種算法的收斂性能,設(shè)置邊緣設(shè)備數(shù)量為20,邊緣設(shè)備主頻為200 MHz,云端主頻為4 GHz,任務(wù)量為500 MB。實(shí)驗(yàn)結(jié)果如圖8所示,整體來(lái)看GWO和LGWO算法的收斂速度最快,但收斂時(shí)系統(tǒng)總成本不如CLGWO低;PSO算法的收斂速度較慢,收斂時(shí)系統(tǒng)總成本也不如CLGWO低;CLGWO算法收斂速度比前兩個(gè)算法略慢,但是收斂時(shí)系統(tǒng)總成本最優(yōu)。三種算法都能在50次迭代之前達(dá)到穩(wěn)定狀態(tài)并達(dá)到最佳的收斂值。因此,CLGWO算法在收斂速度和收斂時(shí)系統(tǒng)總成本上都具有優(yōu)異表現(xiàn)。
3.3 應(yīng)用測(cè)試和分析
基于上述理論,邊緣端自行設(shè)計(jì)了邊緣計(jì)算網(wǎng)關(guān)。終端設(shè)備使用現(xiàn)成的傳感器和控制器。云端使用新思聯(lián)云服務(wù)器,搭配手機(jī)端的微信小程序查看終端的數(shù)據(jù)和狀態(tài)。
整個(gè)系統(tǒng)的工作流程如圖9所示。終端采集數(shù)據(jù),使用433 MHz通信模塊的設(shè)備上傳到Sub-1GHz網(wǎng)關(guān),使用藍(lán)牙或者Wifi設(shè)備上傳到Wifi/藍(lán)牙網(wǎng)關(guān)。邊緣端通過(guò)寬帶網(wǎng)絡(luò)連接云端,云端上的數(shù)據(jù)可以被多端訪問(wèn)。邊緣端和云端集成了相同功能的任務(wù)處理單元,如PID控制單元、數(shù)據(jù)壓縮和解壓?jiǎn)卧?、編解碼單元等,邊緣端基于卸載策略將任務(wù)部分卸載至云端處理。整個(gè)系統(tǒng)協(xié)同調(diào)配控制物理量如風(fēng)量、亮度、溫度、開關(guān)等。
3.3.1 軟硬件設(shè)計(jì)
硬件層面:Wifi/藍(lán)牙網(wǎng)關(guān)使用Raspberry Pi 4B,具備64-bit四核處理器,內(nèi)置2.4/5.0 GHz 雙頻WLAN和藍(lán)牙BLE 5.0。Sub-1GHz網(wǎng)關(guān)使用AT32F403A作為微控制器,包含以太網(wǎng)PHY和RJ45接口,通過(guò)SPI接口連接CMT2300A射頻芯片模塊與其他433 MHz設(shè)備通信。
軟件層面:使用MQTT協(xié)議作為網(wǎng)關(guān)的上行傳輸協(xié)議。MQTT以其輕量級(jí)的二進(jìn)制結(jié)構(gòu)、簡(jiǎn)潔的消息頭、穩(wěn)定的持久連接和低功耗特性,特別適用于帶寬有限和網(wǎng)絡(luò)不穩(wěn)定的環(huán)境,確保數(shù)據(jù)傳輸?shù)母咝c穩(wěn)定。同時(shí)為了實(shí)現(xiàn)云與邊緣設(shè)備的無(wú)縫協(xié)作,引入KubeEdge邊緣計(jì)算框架。該框架不僅將容器化應(yīng)用的編排功能拓展至邊緣端設(shè)備,還確保了云與邊之間的部署同步與數(shù)據(jù)一致性,極大提升了任務(wù)處理的靈活性和效率。
3.3.2 邊緣網(wǎng)關(guān)測(cè)試和分析
基于上述的整體設(shè)計(jì)和部署,選取環(huán)境為建筑物內(nèi)部,相鄰設(shè)備空間間隔超過(guò)20 m且存在墻體遮擋的復(fù)雜環(huán)境進(jìn)行測(cè)試。結(jié)果如下:相較于完全本地執(zhí)行,采用卸載策略算法后,任務(wù)處理時(shí)延降低42%,能耗減少61%。與將所有任務(wù)全部卸載至云端執(zhí)行相比,時(shí)延降低10%,能耗減少6%。
測(cè)試結(jié)果與仿真模擬所得趨勢(shì)相吻合,從而驗(yàn)證了基于數(shù)據(jù)壓縮和改進(jìn)灰狼算法的邊緣計(jì)算卸載方法能夠有效降低系統(tǒng)整體時(shí)延和能耗,在實(shí)際應(yīng)用中有一定的實(shí)用效果。
4 結(jié)束語(yǔ)
本文針對(duì)智能樓宇場(chǎng)景中計(jì)算任務(wù)的時(shí)延與能耗問(wèn)題進(jìn)行了深入探討,成功建立了面向任務(wù)卸載的智能樓宇環(huán)境數(shù)學(xué)模型。在該模型框架下,本文創(chuàng)新設(shè)計(jì)了一種針對(duì)樓宇特點(diǎn)的差分字典編碼壓縮技術(shù),用于高效壓縮傳遞至云端的數(shù)據(jù);與此同時(shí),對(duì)灰狼算法進(jìn)行了優(yōu)化升級(jí),巧妙地融入螺旋漸近狩獵策略與萊維飛行算法,以彌補(bǔ)原有算法在搜索性能上的不足,從而尋找到最優(yōu)的任務(wù)卸載策略。仿真實(shí)驗(yàn)結(jié)果顯示本文方法的顯著優(yōu)勢(shì),有效地降低了整體計(jì)算任務(wù)卸載過(guò)程中產(chǎn)生的時(shí)延和能耗,且具有可觀的收斂速度。在理論研究的基礎(chǔ)上設(shè)計(jì)了適用于樓宇場(chǎng)景的邊緣網(wǎng)關(guān)設(shè)備,測(cè)試結(jié)果表明,采用本文方法后,系統(tǒng)整體時(shí)延和能耗得到了明顯的降低,充分體現(xiàn)了該方法在實(shí)際應(yīng)用中的可行性與價(jià)值。
參考文獻(xiàn):
[1]Yi Lingzhi, Gao Xieyi, Li Zongpin, et al. task offloading of intelligent building based on CO-HHO algorithm in edge computing [J]. Journal of Electrical Engineering amp; Technology, 2022, 17(6): 3525-3539.
[2]Liu Yi, Yang Chao, Jiang Li, et al. Intelligent edge computing for IoT-based energy management in smart cities [J]. IEEE Network, 2019, 33(2): 111-117.
[3]Carvalho G, Cabral B, Pereira V, et al. Edge computing: current trends, research challenges and future directions [J]. Computing, 2021, 103(5): 993-1023.
[4]Safavat S, Sapavath N N, Rawat D B. Recent advances in mobile edge computing and content caching [J]. Digital Communications and Networks, 2020, 6(2): 189-194.
[5]Sadatdiynov K, Cui Laizhong, Zhang Lei, et al. A review of optimization methods for computation offloading in edge computing networks [J]. Digital Communications and Networks, 2023, 9(2): 450-461.
[6]Liu Zhanjun, Tan Xin, Wen Miaowen, et al. An energy-efficient selection mechanism of relay and edge computing in UAV-assisted cellular networks [J]. IEEE Trans on Green Communications and Networking, 2021, 5(3): 1306-1318.
[7]Sun Jianan, Gu Qing, Zheng Tao, et al. Joint optimization of computation offloading and task scheduling in vehicular edge computing networks [J]. IEEE Access, 2020, 8: 10466-10477.
[8]盛煜, 朱正偉, 朱晨陽(yáng), 等. 基于深度強(qiáng)化學(xué)習(xí)的多目標(biāo)邊緣任務(wù)調(diào)度研究 [J]. 電子測(cè)量技術(shù), 2023, 46(8): 74-81. (Sheng Yu, Zhu Zhengwei, Zhu Chenyang, et al. Research on multi-objective edge task scheduling based on deep reinforcement learning [J]. Electronic Measurement Technology, 2023, 46(8): 74-81.)
[9]Tang Ming, Wong V W S. Deep reinforcement learning for task offloading in mobile edge computing systems [J]. IEEE Trans on Mobile Computing, 2020, 21(6): 1985-1997.
[10]葛海波, 李文浩, 馮安琪,等. 改進(jìn)遺傳算法的邊緣計(jì)算卸載策略 [J]. 西安郵電大學(xué)學(xué)報(bào), 2020, 25(3): 7-13. (Ge Haibo, Li Wenhao, Feng Anqi, et al. Edge computing offloading strategy of improved genetic algorithm [J]. Journal of Xi’an University of Posts and Telecommunications, 2020, 25(3): 7-13.)
[11]王冶. 車聯(lián)網(wǎng)中基于優(yōu)先級(jí)的任務(wù)卸載和資源分配聯(lián)合優(yōu)化方法研究 [D]. 長(zhǎng)春:吉林大學(xué), 2023. (Wang Ye. Research on joint optimization method of task offloading and resource allocation based on priority in Internet of Vehicles [D]. Changchun: Jilin University, 2023.)
[12]叢玉良, 孫聞晞, 薛科, 等. 基于改進(jìn)的混合遺傳算法的車聯(lián)網(wǎng)任務(wù)卸載策略研究 [J]. 通信學(xué)報(bào), 2022, 43(10): 77-85. (Cong Yuliang, Sun Wenxi, Xue Ke, et al. Research on task offloading strategy of Internet of Vehicles based on improved hybrid genetic algorithm [J]. Journal on Communication, 2022, 43(10): 77-85.)
[13]陳發(fā)堂, 李璐, 張若凡. 基于改進(jìn)式免疫遺傳算法的車聯(lián)網(wǎng)任務(wù)卸載方案 [J]. 計(jì)算機(jī)應(yīng)用研究, 2024, 41(2): 558-562. (Chen Fatang, Li Lu, Zhang Ruofan. Task offloading scheme of Internet of Vehicles based on improved immune genetic algorithm [J]. Application Research of Computers, 2024, 41(2): 558-562.)
[14]Bagherian M, Chehade S, Whitney B, et al. Classical and quantum compression for edge computing: the ubiquitous data dimensionality reduction [J]. Computing, 2023, 105(7): 1419-1465.
[15]Mirjalili S, Saremi S, Mirjalili S M, et al. Multi-objective grey wolf optimizer: a novel algorithm for multi-criterion optimization [J]. Expert Systems with Applications, 2016, 47: 106-119.
[16]Nadimi-Shahraki M H, Taghian S, Mirjalili S. An improved grey wolf optimizer for solving engineering problems [J]. Expert Systems with Applications, 2021, 166: 113917.
[17]Sihwail R, Omar K, Ariffin K A Z, et al. Improved Harris hawks optimization using elite opposition-based learning and novel search mechanism for feature selection [J]. IEEE Access, 2020, 8: 121127-121145.
[18]Abualigah L, Yousri D, Abd Elaziz M, et al. Aquila optimizer: a novel meta-heuristic optimization algorithm [J]. Computers amp; Industrial Engineering, 2021, 157: 107250.
[19]丁瑞成, 周玉成. 引入萊維飛行與動(dòng)態(tài)權(quán)重的改進(jìn)灰狼算法 [J]. 計(jì)算機(jī)工程與應(yīng)用, 2022, 58(23): 74-82. (Ding Ruicheng, Zhou Yucheng. Improved grey wolf algorithm with Lévy flight and dynamic weight [J]. Computer Engineering and Application, 2022, 58(23): 74-82.)
[20]Bi Jing, Yuan Haitao, Duanmu S, et al. Energy-optimized partial computation offloading in mobile-edge computing with genetic simulated-annealing-based particle swarm optimization [J]. IEEE Internet of Things Journal, 2020, 8(5): 3774-3785.
[21]羅斌, 于波. 移動(dòng)邊緣計(jì)算中基于粒子群優(yōu)化的計(jì)算卸載策略 [J]. 計(jì)算機(jī)應(yīng)用, 2020, 40(8): 2293-2298. (Luo Bin, Yu Bo. Computation offloading strategy based on particle swarm optimization in mobile edge computing [J]. Journal of Computer Applications, 2020, 40(8): 2293-2298.)