物聯(lián)網(wǎng)邊緣計(jì)算資源分配模糊建模與優(yōu)化研究

郭榮佐，鄧涵文，陳芳瑩，黃 君

1(四川師范大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院，成都 610101)2(四川工商職業(yè)技術(shù)學(xué)院 經(jīng)濟(jì)與管理系，四川 都江堰 611830)

E-mail：469497691@qq.com

1 引 言

物聯(lián)網(wǎng)(Internet of Things，IoT)已成為一種擁有大量互聯(lián)事物和應(yīng)用的新型范式，正在促進(jìn)互聯(lián)網(wǎng)從連接網(wǎng)絡(luò)向連接物理世界轉(zhuǎn)變[1].IoT將數(shù)據(jù)傳輸?shù)綌?shù)據(jù)中心或云端進(jìn)行進(jìn)一步處理，從而實(shí)現(xiàn)物與物、物與人和人與人的互聯(lián)互通.而現(xiàn)用物聯(lián)網(wǎng)以集中式的數(shù)據(jù)中心或云端進(jìn)行數(shù)據(jù)處理，帶來設(shè)備端的網(wǎng)絡(luò)延遲大、無法滿足設(shè)備的爆炸式增長、設(shè)備端的數(shù)據(jù)安全受到威脅和造成設(shè)備數(shù)據(jù)傳輸?shù)哪芎拇蟠笤黾拥热毕?邊緣計(jì)算的提出和應(yīng)用，使集中式物聯(lián)網(wǎng)的這些缺陷得到緩和，將計(jì)算任務(wù)轉(zhuǎn)移到邊緣服務(wù)側(cè)而使延遲和能耗得到顯著的改善，特別是對延遲和能耗敏感的物聯(lián)網(wǎng)應(yīng)用而言[2].

現(xiàn)有研究成果主要集中于對邊緣計(jì)算、物聯(lián)網(wǎng)邊緣計(jì)算(Edge-Computing-based Internet of Things，ECIoT)的計(jì)算卸載的研究.如文獻(xiàn)[3]就對邊緣計(jì)算的計(jì)算卸載決策模型進(jìn)行研究，提出一種改進(jìn)的分層拓?fù)浣Y(jié)構(gòu)的決策模型，并對模型進(jìn)行了實(shí)驗(yàn)驗(yàn)證；文獻(xiàn)[4]對移動(dòng)邊緣云計(jì)算的計(jì)算卸載問題進(jìn)行研究，提出一種基于博弈論的分布式移動(dòng)邊緣云計(jì)算的計(jì)算卸載算法，并將算法應(yīng)用于多通道無線競爭的多用戶計(jì)算卸載場景中，驗(yàn)證了算法的計(jì)算卸載性能；文獻(xiàn)[5]從數(shù)據(jù)安全角度研究移動(dòng)邊緣計(jì)算的計(jì)算資源分配與計(jì)算卸載，提出一種具有資源安全的多用戶資源分配與計(jì)算卸載模式；文獻(xiàn)[6、7]對移動(dòng)邊緣計(jì)算網(wǎng)絡(luò)的計(jì)算遷移與內(nèi)容緩存、邊緣計(jì)算的計(jì)算卸載研究現(xiàn)狀進(jìn)行綜述，綜述了計(jì)算卸載的各個(gè)方面，包括能耗最小化、服務(wù)質(zhì)量保證和經(jīng)驗(yàn)質(zhì)量提高，對資源調(diào)度方法、系統(tǒng)性能和計(jì)算卸載決策開銷之間的博弈和權(quán)衡進(jìn)行了綜述.亦有研究者對邊緣計(jì)算、物聯(lián)網(wǎng)邊緣計(jì)算的資源分配進(jìn)行研究的.如文獻(xiàn)[8]對邊緣計(jì)算系統(tǒng)的計(jì)算卸載進(jìn)行研究，提出一種基于Stackelberg策略的邊緣計(jì)算的無線和計(jì)算資源分散均衡卸載算法，并對算法進(jìn)行了仿真驗(yàn)證；文獻(xiàn)[9]提出了一種新的邊緣計(jì)算物聯(lián)網(wǎng)體系結(jié)構(gòu)，并對結(jié)構(gòu)的無線資源、計(jì)算資源、接入控制和功率控制等進(jìn)行了基于Lyapunov的隨機(jī)跨層動(dòng)態(tài)優(yōu)化研究；文獻(xiàn)[10]對正交多址的物聯(lián)網(wǎng)移動(dòng)邊緣計(jì)算的通信與計(jì)算資源分配進(jìn)行關(guān)聯(lián)研究，提出一種有效分層的系統(tǒng)成本和延遲最優(yōu)化的通信與計(jì)算資源關(guān)聯(lián)分配于邊緣服務(wù)器的算法，并對算法進(jìn)行驗(yàn)證.同樣，有利用模糊理論與模糊優(yōu)化方法對邊緣計(jì)算進(jìn)行研究的.如文獻(xiàn)[11]利用模糊理論，對邊緣計(jì)算的邊緣卸載切換進(jìn)行研究，提出了一種基于帶寬、處理器速度和延遲的邊緣模糊切換控制器算法，來提高邊緣計(jì)算系統(tǒng)的邊緣切換時(shí)間而降低系統(tǒng)的響應(yīng)時(shí)間和成本；文獻(xiàn)[12]利用模糊理論對物聯(lián)網(wǎng)工作分類和資源分配進(jìn)行研究，設(shè)計(jì)了一種模糊干擾系統(tǒng)，從通信和成本角度對物聯(lián)網(wǎng)作業(yè)進(jìn)行分類和資源進(jìn)行分配.這些研究，為研究ECIoT資源分配與優(yōu)化奠定了一定的基礎(chǔ)，但由于ECIoT的特性和資源的有限性，以及邊緣計(jì)算的計(jì)算任務(wù)的動(dòng)態(tài)性和隨機(jī)性，使得ECIoT的資源分配呈現(xiàn)并發(fā)性、資源請求的沖突性和隨機(jī)多階段任務(wù)特性等，必須進(jìn)一步研究ECIoT的資源分配與優(yōu)化問題，以使其資源得到有效利用，從而提高ECIoT的應(yīng)用范圍.

綜上所述，對物聯(lián)網(wǎng)邊緣計(jì)算的研究，雖有相關(guān)研究者進(jìn)行了研究，但僅設(shè)計(jì)了相應(yīng)的模糊系統(tǒng)，未對其資源分配和算法進(jìn)行深入研究.另外，基于文獻(xiàn)[13]對協(xié)同物流網(wǎng)的資源分配進(jìn)行模糊優(yōu)化分配建模和物聯(lián)網(wǎng)邊緣計(jì)算本身的模糊特性，利用模糊理論對物聯(lián)網(wǎng)邊緣計(jì)算進(jìn)行資源分配問題的建模與優(yōu)化研究，以解決其資源分配的最優(yōu)化問題和提高資源利用率等.因此，本文主要貢獻(xiàn)為：提出一種具有虛擬化控制器的邊緣網(wǎng)關(guān)型物聯(lián)網(wǎng)邊緣計(jì)算結(jié)構(gòu)；對物聯(lián)網(wǎng)邊緣計(jì)算的任務(wù)進(jìn)行研究，設(shè)計(jì)了一種任務(wù)分解模型；利用模糊理論，建立了多目標(biāo)模糊函數(shù)；利用非線性六角模糊數(shù)，對多目標(biāo)模糊函數(shù)進(jìn)行量化，設(shè)計(jì)了多目標(biāo)模糊函數(shù)轉(zhuǎn)換算法和一種基于改進(jìn)遺傳算法的模因算法的優(yōu)化算法，以求解多目標(biāo)函數(shù)最優(yōu)解，以此得到物聯(lián)網(wǎng)邊緣計(jì)算資源分配的最優(yōu)分配方案.

2 ECIoT架構(gòu)

低成本感知器件的普及使得物聯(lián)網(wǎng)由傳統(tǒng)集中式向邊緣計(jì)算范式發(fā)展，即物聯(lián)網(wǎng)與邊緣計(jì)算結(jié)合，將云計(jì)算的功能和優(yōu)點(diǎn)向邊緣推移，使得云計(jì)算的部分功能接近于數(shù)據(jù)生成的邊緣設(shè)備，從而使得ECIoT引起了多個(gè)行業(yè)的極大興趣和成為研究熱點(diǎn)，并導(dǎo)致傳統(tǒng)物聯(lián)網(wǎng)架構(gòu)的演繹和優(yōu)化.

由此，物聯(lián)網(wǎng)由集中式向邊緣計(jì)算范式發(fā)展，基于邊緣計(jì)算的物聯(lián)網(wǎng)架構(gòu)演化為如圖1所示的結(jié)構(gòu)，稱為ECIoT系統(tǒng)架構(gòu)(Architecture of Edge-Computing-based Internet of Things Systems，AECIoTs).AECIoTs分為4層，分別為物理事物層、物聯(lián)網(wǎng)邊緣設(shè)備層、邊緣網(wǎng)關(guān)層和邊緣服務(wù)層，其中邊緣服務(wù)層通過網(wǎng)絡(luò)與遠(yuǎn)端云計(jì)算平臺(tái)鏈接，以實(shí)現(xiàn)云計(jì)算功能.邊緣服務(wù)層由邊緣服務(wù)器(Edge Server，ES)和邊緣應(yīng)用服務(wù)器(Edge Application Server，EAS)等構(gòu)成，ES具有邊緣網(wǎng)關(guān)控制單元(Edge Gateway Control Unit，EGCU)，EGCU發(fā)送控制命令給EGs；同時(shí)，邊緣服務(wù)層還通過網(wǎng)絡(luò)與后端/遠(yuǎn)端的云計(jì)算平臺(tái)鏈接.邊緣網(wǎng)關(guān)層由若干邊緣網(wǎng)關(guān)(Edge Gateways，EGs)組成，EGs具有負(fù)載平衡與卸載功能，以實(shí)現(xiàn)邊緣設(shè)備的自動(dòng)卸載與掛起；EGs具有流量監(jiān)控報(bào)告(Report Monitoring Traffic，RMT)、數(shù)據(jù)預(yù)處理單元(Data Preprocessing Unit，DPU)、數(shù)據(jù)暫存單元(Data Temporary Storage Unit，DTSU)和邊緣控制單元等，可實(shí)現(xiàn)對邊緣設(shè)備通信流量的監(jiān)測、數(shù)據(jù)的預(yù)處理、數(shù)據(jù)暫存和接受邊緣服務(wù)器的邊緣控制信息(Edge Control messages，ECMs)的控制等功能.而物理事物層通過移動(dòng)通信、寬帶、近距離通信和現(xiàn)場總線等通信技術(shù)，實(shí)現(xiàn)與邊緣設(shè)備層的連接，即現(xiàn)實(shí)物理世界通過各種感知技術(shù)進(jìn)行信息感知.

圖1 ECIoT架構(gòu)圖Fig.1 Architecture figure of edge-computing-based internet of things systems

如圖1所示的架構(gòu)中，物聯(lián)網(wǎng)邊緣設(shè)備層的邊緣設(shè)備(Edge Devices，EDs)執(zhí)行對物理世界數(shù)據(jù)源端的感知和簡單數(shù)據(jù)處理任務(wù).在AECIoTs中，設(shè)X個(gè)私有EDs組成EDs集合SEDs，即SEDs={Eds1，Eds2，…，EdsX}在數(shù)據(jù)源端附近完成數(shù)據(jù)感知與采集和計(jì)算，并通過EGs的預(yù)處理和計(jì)算與暫存，將數(shù)據(jù)傳輸?shù)竭吘壏?wù)層.邊緣服務(wù)層中，EAS承擔(dān)后端/遠(yuǎn)端云計(jì)算鏈接，并為Eds提供全局服務(wù)接口，通過命令控制EG來管理和調(diào)度所有的EDs.設(shè)Y個(gè)本地ES構(gòu)成本地邊緣服務(wù)集合SESs，即SESs={Ess1，Ess2，…，EssY}，SESs可能為微數(shù)據(jù)中心、微云計(jì)算、智能路由器或具有計(jì)算能力的EGs等，為靠近EDs側(cè)提供數(shù)據(jù)存儲(chǔ)和計(jì)算.設(shè)M個(gè)本地EGs構(gòu)成本地邊緣網(wǎng)關(guān)層，即SEGs={Egs1，Egs2，…，EgsM}，Egs為邊緣網(wǎng)關(guān).

圖2 邊緣網(wǎng)關(guān)置入的虛擬化控制器結(jié)構(gòu)圖Fig.2 Structure of virtualization controller of edge gateways

如圖2所示，在邊緣網(wǎng)關(guān)層的邊緣網(wǎng)關(guān)中，置入虛擬化控制器，以實(shí)現(xiàn)對上層邊緣服務(wù)層提供服務(wù)和對下層的邊緣設(shè)備層進(jìn)行能耗與時(shí)延、應(yīng)用程序與任務(wù)分解和其他應(yīng)用處理等.虛擬化控制器中間部分為上層資源分配與調(diào)度、流量監(jiān)考報(bào)告和應(yīng)用處理核提供服務(wù)，且處理下層的能耗與時(shí)延分析、任務(wù)分解和應(yīng)用處理，協(xié)調(diào)實(shí)現(xiàn)延遲、能耗、任務(wù)分解等來完成資源有效分配.通過邊緣網(wǎng)關(guān)層的邊緣網(wǎng)關(guān)置入該虛擬化控制器，可處理大部分邊緣任務(wù)，減少邊緣設(shè)備層的應(yīng)用請求的整體服務(wù)延遲和能耗，以提高整個(gè)ECIoT系統(tǒng)的服務(wù)滿意度.

3 系統(tǒng)模型

本部分描述如何依據(jù)ECIoT系統(tǒng)的延遲和能耗等來研究其資源分配，主要描述ECIoT系統(tǒng)的任務(wù)模型，并對系統(tǒng)的時(shí)延、能耗和滿意度等進(jìn)行描述，擬在能耗和延遲之間做出權(quán)衡.

3.1 任務(wù)模型

對ECIoT系統(tǒng)的任務(wù)，需按一定策略進(jìn)行分解.故定義系統(tǒng)任務(wù)模型和任務(wù)劃分策略.

定義1.設(shè)物聯(lián)網(wǎng)邊緣計(jì)算的任務(wù)TD具有可分解特性，則任務(wù)TD定義為五元組表，即：

TD={Ic，Ks，Stfd，Tds，Ecfs}，

(1)

其中：Ic表示任務(wù)TD的初始條件集合，包括TD產(chǎn)生時(shí)擁有的知識(shí)，如TD產(chǎn)生時(shí)間、環(huán)境和執(zhí)行估計(jì)時(shí)間等等；Ks表示任務(wù)TD分解的知識(shí)集，包含任務(wù)TD執(zhí)行所需所有子任務(wù)執(zhí)行先后順序和任務(wù)TD的功能特征描述等任務(wù)TD完成分解的關(guān)鍵因子；Stfd表示任務(wù)TD分解中的子任務(wù)，依據(jù)子任務(wù)的復(fù)雜度來判斷其是否繼續(xù)進(jìn)行分解；Tds表示任務(wù)TD分解過程完成后，得到的能夠由相應(yīng)設(shè)備直接完成的子任務(wù)，該子任務(wù)可通過資源分配可直接對應(yīng)到相應(yīng)的設(shè)備資源；Ecfs表示子任務(wù)Tds對應(yīng)的設(shè)備角色，且與Tds成映射關(guān)系，為可執(zhí)行對應(yīng)終結(jié)子任務(wù)的邊緣設(shè)備，與邊緣設(shè)備的具體性能和能力相關(guān).

依據(jù)定義1，ECIoT的任務(wù)，無論其復(fù)雜程度如何，都需要進(jìn)行按照定義1的描述進(jìn)行分解.

ECIoT系統(tǒng)一旦建成，其執(zhí)行的所有任務(wù)，均為周期性初始化且具有一定的周期和時(shí)間間隔[14].假定AECIoTs中應(yīng)用持續(xù)具有Z個(gè)任務(wù)，即TAZ={Td1，Td2，…，TdZ}，在每個(gè)周期開始時(shí)由應(yīng)用程序初始化，則Tdi與四元組Di={Ai，Tsi，DOi，Maxi，x}具有強(qiáng)相關(guān)性，其中Di表示與任務(wù)Tdi相關(guān)聯(lián)的量的集合；Ai表示任務(wù)Tdi將要處理的數(shù)據(jù)量；Tsi表示任務(wù)或子任務(wù)開始時(shí)間的先后的時(shí)間因子；DOi表示任務(wù)Tdi執(zhí)行完成后的數(shù)據(jù)輸出量的大小；Maxi，x表示Tdi分配給邊緣設(shè)備Ecfsx時(shí)的最壞情況下的執(zhí)行時(shí)間.

由此，得到AECIoTs中任務(wù)分解樹如圖3所示.圖3所示，頂層為ECIoT系統(tǒng)應(yīng)用程序任務(wù)集合TAZ，接下來是任務(wù)Tdi的中間分解的子任務(wù)集Stfd={Stfd1，…，Stfdn}，然后是不可再分的最終子任務(wù)集Tds，每個(gè)最終子任務(wù)都對應(yīng)相應(yīng)的邊緣設(shè)備Ecfsx.任務(wù)間或子任務(wù)間的相關(guān)性，由四元組Di描述，并在圖3中表示為最終子任務(wù)間的Ai和Tsi.

圖3 ECIoT中應(yīng)用程序任務(wù)分解樹Fig.3 Application task decomposition tree in ECIoT

3.2 系統(tǒng)時(shí)延、能耗與滿意度

從ECIoT系統(tǒng)內(nèi)的信息傳輸需要消耗時(shí)間和能量，故本節(jié)對系統(tǒng)的時(shí)延、能耗和服務(wù)滿意度進(jìn)行描述[15].

設(shè)ECIoT系統(tǒng)中，從邊緣設(shè)備層的Edsi傳輸數(shù)據(jù)到邊緣網(wǎng)關(guān)層Egsj，或通過邊緣網(wǎng)關(guān)層Egsj傳輸?shù)竭吘壏?wù)層Essk的數(shù)據(jù)傳輸為上傳服務(wù)，其上傳服務(wù)速率為Ri，j或Ri，k，否則為下載服務(wù)，且下載服務(wù)的時(shí)間和能耗在此忽略不計(jì)，其中i∈X，j∈Y，k∈M；又設(shè)ECIoT系統(tǒng)可用通信通道為Comm={1，2，…，C}，則Commn，m∈{0}∪Comm表示請求n的任務(wù)m選擇了通道Commn，m>0上傳，Commn，m=0為任務(wù)m在本地設(shè)備上執(zhí)行；若假設(shè)所有請求任務(wù)的信道分配候選方案為Cancc={c1，1，c1，2，…，c1，m，…，cn，1，…，cn，m}，則Commn，m的上傳速率為：

(2)

其中：CBn，m是信道的帶寬，Transpn，m是請求n的任務(wù)m的發(fā)送功率，CGn，m是信道增益，Cinp是干擾噪聲功率，αi，j是為計(jì)算卸載因子，有卸載時(shí)αi，j=1，否則αi，j=0.

若ECIoT系統(tǒng)中請求n的任務(wù)m的輸入數(shù)據(jù)大小為An，m，執(zhí)行該任務(wù)所需的處理器周期數(shù)用Tccn，m表示，則該任務(wù)將在EDsi，Egsj，Egsk(i∈X，j∈Y，k∈M)中選一個(gè)設(shè)備進(jìn)行執(zhí)行，這將涉及到計(jì)算時(shí)延、能耗和滿意度等.

定義2.假設(shè)ECIoT系統(tǒng)中最終子任務(wù)Tdsi卸載到Egsj執(zhí)行，則卸載成本Timeij(tij)為傳輸時(shí)間timeij(tij)和子任務(wù)執(zhí)行時(shí)間timei(ti)構(gòu)成，即：

(3)

其中：Ai，j為傳輸數(shù)據(jù)量、Ri，j為式(2)所描述、Tcci，j為執(zhí)行子任務(wù)Tdsi的Egsj的CPU周期數(shù)；di，j表示最終子任務(wù)Tdsi提交設(shè)備到Egsj的距離；pri，j表示Egsj的CPU處理速率.

由定義2可知，若請求n的任務(wù)Tdm，分解為若干最終子任務(wù)，即Tdm={Tds1，Tds2，…，Tdsh}，則任務(wù)Tdm的卸載成本為：

(4)

其中：Tdm表示任務(wù)分解為h個(gè)最終子任務(wù).因此，ECIoT系統(tǒng)中，有Z個(gè)任務(wù)的計(jì)算卸載時(shí)間成本按照式(4)累加[16].

(5)

針對電池供電的設(shè)備，需要對其提供經(jīng)綜合考慮計(jì)算負(fù)載均衡與通信相關(guān)的高效計(jì)算卸載算法[17].僅有EDs需要關(guān)注能耗，其能耗主要開銷于本地計(jì)算、任務(wù)卸載和數(shù)據(jù)傳輸.

若邊緣設(shè)備Edsi空閑能耗忽略不計(jì)，且設(shè)其初始能量為Edei，則在經(jīng)歷時(shí)間t所消耗能量為：

(6)

其中：Ei，lc(tlc)、Ei，dt(tdt)、Ei，oe(toe)分別表示Edsi在時(shí)間tlc、tdt、toe完成本地計(jì)算、數(shù)據(jù)傳輸、任務(wù)卸載所消耗的能量.

定義3.假設(shè)ECIoT系統(tǒng)中，用戶n獲得資源m的體驗(yàn)函數(shù)為fe(xn，m)，則體驗(yàn)函數(shù)fe(xn，m)定義為：

fe(xn，m)=1-e-μxn，m

(7)

其中：μ為用戶體驗(yàn)函數(shù)fe(xn，m)的權(quán)值因子，且μ>0；xn，m表示用戶獲得的資源.

由定義3可知，fe(xn，m)∈[0，1]，但并不是與資源擁有量成線性關(guān)系；當(dāng)用戶n獲得資源多時(shí)，的值會(huì)逐步向1方向增加，但增速會(huì)慢慢放緩.因此，用戶n得到資源m服務(wù)滿意度效用函數(shù)fn，m(CBn，m)為：

(8)

3.3 問題描述

邊緣設(shè)備的本地計(jì)算到達(dá)具有隨機(jī)性，遠(yuǎn)端/后端云計(jì)算平臺(tái)下達(dá)的計(jì)算命令是隨機(jī)的，而ECIoT系統(tǒng)的資源總量是固定的，每個(gè)應(yīng)用程序任務(wù)從本地資源庫分配相應(yīng)的資源以滿足任務(wù)執(zhí)行的要求，但由圖1可知，應(yīng)用程序任務(wù)分解為最終子任務(wù)可用資源數(shù)是不確定的和模糊的.另一方面，每個(gè)任務(wù)的約束條件為能耗、執(zhí)行時(shí)間、可靠性、可用性、可卸載度、通信帶寬和鄰居節(jié)點(diǎn)相似度等，也具有不確定性和模糊特性.

假定卸載策略和返回策略的計(jì)算產(chǎn)生的時(shí)延在此不予考慮，則由式(4)、式(5)、式(6)和式(8)可得到系統(tǒng)的時(shí)延、能耗和滿意度效用函數(shù)，即：

(9)

依據(jù)定義1，任務(wù)分解為最終子任務(wù)時(shí)，存在約束為子任務(wù)的處理能力、狀態(tài)和所處環(huán)境，而邊緣層的設(shè)備亦具有能力特征、狀態(tài)屬性和部署位置等約束[18].因此，ECIoT系統(tǒng)的資源分配問題，就轉(zhuǎn)化為在子任務(wù)約束和邊緣層設(shè)備約束下，使得Ttotal和Ern最小，且Utotal最大的資源分配的策略、算法或方法問題.

4 模糊優(yōu)化

利用模糊優(yōu)化方法，建立ECIoT系統(tǒng)的資源分配的模糊模型，并設(shè)計(jì)算法對模型進(jìn)行最優(yōu)化求解.

4.1 模糊多目標(biāo)模型

在ECIoT系統(tǒng)里，任務(wù)的產(chǎn)生在周期性里具有隨機(jī)特性.為了使隨機(jī)任務(wù)與模糊資源之間的優(yōu)化，假設(shè)任務(wù)間相互獨(dú)立且到達(dá)時(shí)間服從相同的概率分布，每個(gè)任務(wù)都按照前面描述進(jìn)行隨機(jī)和模糊分解，多個(gè)子任務(wù)通過計(jì)算卸載可在系統(tǒng)多個(gè)資源并行運(yùn)行，而系統(tǒng)總的資源是恒定的.

目標(biāo)函數(shù)為：

其中的各種變量定義服從前面的描述.

系統(tǒng)所有任務(wù)經(jīng)分解為最終子任務(wù)后，均需要配置資源，以確保子任務(wù)得以執(zhí)行，因此，系統(tǒng)資源分配應(yīng)滿足子任務(wù)執(zhí)行的最小資源需求.另外，系統(tǒng)可用的資源總量不超過Star=SEDs∪SESs∪SEGs，Star為系統(tǒng)總的可用資源集合，故有：

(13)

因此，系統(tǒng)總的延時(shí)必須滿足：

(14)

(15)

其中：λm表示請求n的任務(wù)m的卸載決策因子.

系統(tǒng)中，若請求n的任務(wù)m得以執(zhí)行，其能耗不能多于請求n的初始能量，即得到系統(tǒng)剩余能量約束為：

(16)

同時(shí)，滿意度必須滿足以下約束條件，即：

(17)

(18)

即得到目標(biāo)函數(shù)為式(10)、(11)、(12)，該目標(biāo)函數(shù)必須在約束式(13)、式(14)、式(15)、式(16)、式(17)和式(18)下，求得最優(yōu)解，即為ECIoT系統(tǒng)的最優(yōu)資源分配.

4.2 模型求解

約束條件具有不確定性，在完全滿足條件的可用資源分配到不完全滿足條件間，存在過渡區(qū)間.這要求得最優(yōu)解，必須在所有模糊約束條件下，用模糊優(yōu)化探索其最優(yōu)解[19].

1.數(shù)據(jù)庫：利用2016年以前的國家專利局中國專利文獻(xiàn)數(shù)據(jù)庫和七國兩組織數(shù)據(jù)庫及歐洲專利局?jǐn)?shù)據(jù)庫有關(guān)關(guān)鍵詞檢索，獲取潛水醫(yī)學(xué)相關(guān)的國內(nèi)專利申請文獻(xiàn)，運(yùn)用智慧牙專利分析軟件對這些專利進(jìn)行分析。

模糊多目標(biāo)優(yōu)化能針對多個(gè)互斥與沖突的目標(biāo)提供多種靈活的決策而被廣泛應(yīng)用.在ECIoT系統(tǒng)中，系統(tǒng)延時(shí)、能耗和滿意度間的關(guān)系是模糊的，可使用隸屬函數(shù)對模型的多個(gè)子優(yōu)化目標(biāo)分別進(jìn)行模糊化處理，以得到模型的最優(yōu)解.選擇合適隸屬函數(shù)是求解模糊優(yōu)化的前提，故利用文獻(xiàn)[20]的六角模糊數(shù)來構(gòu)造隸屬函數(shù).

(19)

則將0<ζ<1的(ξ1，ξ2，ξ3，ξ4，ξ5，ξ6；ζ)γ稱為非線性六角模糊數(shù)(Nonlinear Hexagonal Fuzzy Number，NHFN)，函數(shù)式(19)稱為NHFN隸屬函數(shù)，式(19)的示意圖如圖4所示.

(20)

(21)

圖4 六角模糊數(shù)示意圖Fig.4 Schematic diagram of hexagon fuzzy number

對得到的目標(biāo)函數(shù)利用算法1進(jìn)行轉(zhuǎn)換，再利用最優(yōu)化算法搜索最優(yōu)解.其模糊多目標(biāo)函數(shù)轉(zhuǎn)換算法，如算法1所示.

算法1.模糊目標(biāo)函數(shù)轉(zhuǎn)換算法

輸入：設(shè)置系統(tǒng)最大容許時(shí)延tMad、最大能耗EMec、滿意度μ、初始能量E0

②目標(biāo)函數(shù)和約束條件

③模糊決策水平參數(shù)(σ，τ，δ)

output：多目標(biāo)轉(zhuǎn)換為單目標(biāo)的模型

if(σ，τ，δ)//符合要求目標(biāo)函數(shù)有最佳、最有可能和最壞，σ為決策者決策因子；τ，v為決策者偏好級(jí)別；權(quán)重系數(shù)δi

{

if(σi==σ0i) //給定決策因子，每個(gè)目標(biāo)函數(shù)具有給定的決策因子初始值，σ0i，i= 1，2，3

{

//flmgv(x)是給定解向量的第v個(gè)目標(biāo)函數(shù)的梯形隸屬函數(shù)

//多目標(biāo)轉(zhuǎn)化為雙目標(biāo)函數(shù).τv為v個(gè)目標(biāo)函數(shù)的最低初值，取決于決策者，且∑τv=1，τv∈[0，1]

//雙目標(biāo)轉(zhuǎn)單目標(biāo)；且θ≤flmgv(x)，v=1，2，…，V；δ1，δ2∈[0，1]，δ1+δ2=1.

}

return(fsogv(x))；

}

else //輸出的單目標(biāo)不符合要求，重新設(shè)置(σ，τ，δ)，重新開始

{重新設(shè)置(σ，τ，δ)→從該算法開始處重新執(zhí)行，直到符合要求}

算法1先將多目標(biāo)模糊問題轉(zhuǎn)化為單目標(biāo)問題.對算法1中的fsogv(x)}的最優(yōu)解，即為多目標(biāo)模糊函數(shù)式(10)、式(11)和式(12)的最優(yōu)解.因此，利用基于改進(jìn)遺傳算法的模因算法(Memetic Algorithm Based on Improved Genetic Algorithm，MABIGA)來求解fsogv(x)}的最優(yōu)解，具體步驟為[21]：

第1步.初始化種群.依據(jù)ECIoT系統(tǒng)特點(diǎn)，設(shè)計(jì)其資源分配優(yōu)化編碼.任務(wù)數(shù)為Z，總的資源數(shù)為Rnum=X+Y+M；先為fsogv(x)設(shè)置初始化種群，并對每個(gè)種群進(jìn)行編碼，并初始化所有約束.

第2步.種群交叉.在fsogv(x)的所有初始化種群中，隨機(jī)選擇交叉點(diǎn)，使交叉點(diǎn)后的種群按照反序重新排列，并建立新的子種群.

第3步.種群突變.隨機(jī)選擇新產(chǎn)生的子種群進(jìn)行比賽，將突變的種群轉(zhuǎn)移到下一代的每個(gè)種群；得到的子種群修改為具有一定概率δi的突變算子進(jìn)行進(jìn)化，與隨機(jī)塊內(nèi)種群交換突變，每個(gè)塊內(nèi)包括滿足δi∈[0，1]的多個(gè)種群，突變算子僅交換種群的相關(guān)屬性字符串；在父種群和子種群中，經(jīng)過突變算子優(yōu)化得到ksur個(gè)幸存者.

第4步.本地搜索.要對fsogv(x)求得最優(yōu)解，需要對種群交叉和突變進(jìn)行局部最優(yōu)化搜索.由此，使用可變領(lǐng)域局部搜索(Variable Neighborhood Local Search，VNLS)算法來提高M(jìn)ABIGA的效率、收斂速度和準(zhǔn)確度[22].首先所有幸存者種群隨機(jī)生成kmax≤ksur個(gè)具有鄰域結(jié)構(gòu)的Rk(k=1，2，…，kmax)，并在鄰域Rk中隨機(jī)選擇初始解ψ1，對ψ1進(jìn)行抖動(dòng)得到解ψ2；然后使用ψ2進(jìn)行可變鄰域搜索來改進(jìn)抖動(dòng)得到的解而得到解ψ3；最后進(jìn)行邊界判定，達(dá)到邊界條件Rkmax，結(jié)束搜索，輸出最優(yōu)解ψ3，否則重新產(chǎn)生初始隨機(jī)解重新開始算法；VNLS具體算法如算法2所示.

第5步.新種群產(chǎn)生.經(jīng)過進(jìn)化和局部搜索存在后，種群數(shù)量大于初始種群數(shù)，使用改進(jìn)關(guān)鍵路徑啟發(fā)式算法選出優(yōu)異個(gè)體形成新的種群.

第6步.終止算法.檢查得到fsogv(x)的最優(yōu)解是否符合決策者對該最優(yōu)解設(shè)置的(σ，τ，δ)的要求，若符合則最優(yōu)解符合要求而停止算法；否則返回第2步，重新執(zhí)行算法.

算法2.VNLS本地搜索最優(yōu)解算法

輸入：鄰域結(jié)構(gòu)Rt(t=1,2,…,tmax)

終止條件：迭代最大值tmax≤kmax≤ksur

輸出：局部最優(yōu)解Ψ3

Ψ1=Randomly_generated_initial_solution();

While (k

{t=1;

Ψ2=shking(Ψ1)；//對隨機(jī)初始解Ψ1進(jìn)行抖動(dòng)，得到解Ψ2在鄰域進(jìn)行搜索，若找到最優(yōu)解，

next1：if(t

在Rt里搜索，找到Ψ3

if (fsogv(Ψ2)≥fsogv(Ψ3))

{t=t+1;

goto next1；}

else

{goto next2；}

}

else

{goto next3；}

next2：Ψ2=Ψ3；

next3：k=k+1；

}

return Ψ3

由此，通過對模糊目標(biāo)函數(shù)的轉(zhuǎn)換算法和MABIGA算法求得最優(yōu)解.

5 實(shí)驗(yàn)與仿真

本部分用建立的ECIoT系統(tǒng)資源分配的模糊模型，對系統(tǒng)隨機(jī)任務(wù)模糊資源分配的方案進(jìn)行優(yōu)化與分析.

5.1 實(shí)驗(yàn)與分析

按照前面ECIoT系統(tǒng)架構(gòu)的要求，利用臺(tái)式電腦、ARM Cortex A8的網(wǎng)關(guān)和各種具有無線收發(fā)的物聯(lián)網(wǎng)邊緣感知設(shè)備，構(gòu)成如圖5所示的實(shí)驗(yàn)環(huán)境.實(shí)驗(yàn)時(shí)，使用PC機(jī)作為邊緣服務(wù)器，4個(gè)ARM Cortex A8處理器的多協(xié)議網(wǎng)關(guān)作為邊緣網(wǎng)關(guān)，而13個(gè)各種具有無線收發(fā)的電池供電的物聯(lián)網(wǎng)邊緣感知設(shè)備作為系統(tǒng)的邊緣設(shè)備，直接感知物理世界.

如圖5(a)所示，為用我校物聯(lián)網(wǎng)實(shí)驗(yàn)室設(shè)備而搭建的實(shí)驗(yàn)環(huán)境.傳感器模塊有光照、溫濕度、霍爾、噪聲、火焰、超聲波、震動(dòng)、氣壓和煙霧等，共用13個(gè)感知模塊，其中霍爾傳感器檢測直接變速電機(jī)的轉(zhuǎn)速.所有傳感器模塊均通過帶有CC2530的ZigBee模塊的創(chuàng)新節(jié)點(diǎn)與網(wǎng)關(guān)的信息交互，創(chuàng)新節(jié)點(diǎn)主控芯片為STM32F103VET6處理器.網(wǎng)關(guān)采用具有ARM Cortex A8內(nèi)核的三星電子有限公司的S5PV210芯片，擴(kuò)展ZigBee、以太、移動(dòng)4G和藍(lán)牙等通信方式，添加虛擬化控制器模塊.邊緣服務(wù)端采用三臺(tái)實(shí)驗(yàn)室PC機(jī)充當(dāng).

在創(chuàng)新節(jié)點(diǎn)和網(wǎng)關(guān)上，分別串入一個(gè)采樣電阻，用示波器和萬用表測量程序運(yùn)行時(shí)間和采樣電阻壓降，測量原理如圖5(b)所示.采樣電阻阻值為12.2歐姆，將萬用表的開關(guān)調(diào)節(jié)到mV檔，測量采用電阻端壓降.若節(jié)點(diǎn)被分配并執(zhí)行子任務(wù)前，將創(chuàng)新節(jié)點(diǎn)的電路板進(jìn)行LED燈飛線到對應(yīng)可測試點(diǎn)的引腳，而使其電平拉高，執(zhí)行完畢之后再將電平拉低，通過示波器測量LED燈引腳高電平的持續(xù)時(shí)間，即得到該節(jié)點(diǎn)運(yùn)行時(shí)間.實(shí)物測量如圖5(c)所示.

圖5 實(shí)驗(yàn)環(huán)境及測量圖Fig.5 Experimental environment and measurement diagram

依據(jù)本文建立的模型、模型求解算法和求解模型時(shí)的偏好因子σ(σ={0.45，0.56，0.82})，利用隨機(jī)產(chǎn)生NHFN數(shù)和ζ，γ值，對模糊目標(biāo)函數(shù)偏好因子σ分解，并進(jìn)行約束條件的權(quán)重δj(j=1，2，…，6，∑δj=1)的隨機(jī)產(chǎn)生；再設(shè)置最大容忍時(shí)延tMad、最大能耗容許值EMec和最低滿意度μs，各感知節(jié)點(diǎn)初始能量值E0均為9v380mAh電池.由此得到表1所示的各種參數(shù)設(shè)定值.實(shí)驗(yàn)的資源總量為邊緣服務(wù)器數(shù)、邊緣網(wǎng)關(guān)數(shù)和邊緣設(shè)備數(shù)之和，即Rnum=Y+M+X=20.

表1 初始化參數(shù)設(shè)置值Table 1 Value of initialization parameter settings

()b實(shí)驗(yàn)時(shí)資源分配數(shù)據(jù)采集實(shí)例圖6 實(shí)驗(yàn)操作參數(shù)設(shè)計(jì)與資源分配的數(shù)據(jù)采集實(shí)例Fig.6 Data collection example of experimental operation parameter design and resource allocation

實(shí)驗(yàn)時(shí)先將模糊多目標(biāo)模型用算法1進(jìn)行單目標(biāo)化處理，且用MABIGA算法及算法2求解最優(yōu)解.在Windows7操作系統(tǒng)下，用微軟公司的Visual C++6.0編寫邊緣服務(wù)端程序，邊緣網(wǎng)關(guān)在Keil中加載ARM開發(fā)環(huán)境，用C語言編寫代碼，并通過JTAG下載；創(chuàng)新節(jié)點(diǎn)在IAR7.10中用C語言開發(fā)，通過JLINK下載燒寫.如圖6(a)所示，在服務(wù)器端設(shè)置網(wǎng)絡(luò)參數(shù)，即可與邊緣網(wǎng)關(guān)和創(chuàng)新節(jié)點(diǎn)進(jìn)行通信；不同任務(wù)對現(xiàn)場不同邊緣網(wǎng)關(guān)、不同創(chuàng)新節(jié)點(diǎn)傳感器的數(shù)據(jù)采集，如圖6(b)所示.

實(shí)驗(yàn)測試得到任務(wù)1、2、3分解后的子任務(wù)數(shù)發(fā)表為6、10、12，依據(jù)表1參數(shù)進(jìn)行參數(shù)設(shè)置，得到模糊多目標(biāo)模型的延時(shí)tMad、能耗EMec(為完成某任務(wù)所有邊緣設(shè)備的平均能耗)和計(jì)算得到滿意度μs；且資源分配的模糊多目標(biāo)模型、算法1和MABIGA算法實(shí)驗(yàn)得到的分配的資源序列，如表2的資源分配行所示.

表2 不同任務(wù)資源分配實(shí)驗(yàn)數(shù)據(jù)表Table 2 Experimental data of resource allocation for different tasks

5.2 仿真比較

用Matlab對禁忌搜索元啟發(fā)式算法(Tabu Search Element Heuristic Algorithm，TSEHA)[23]、捕食搜索算法(Predatory Search Algorithm，PSA)[24]和多目標(biāo)遺傳算法(Multi-Objective Genetic Algorithm，MoGA)[18]進(jìn)行仿真資源分配，在時(shí)延、能耗和滿意度等方面與本文算法進(jìn)行同資源下的仿真實(shí)驗(yàn).

仿真時(shí)，任務(wù)數(shù)為0-40個(gè)，且每個(gè)任務(wù)復(fù)雜度相當(dāng).分別對不同任務(wù)數(shù)下，TSEHA、PSA、MoGA和This(本文算法)算法進(jìn)行延時(shí)、能耗、滿意度和邊緣設(shè)備資源分配的仿真，得到如圖7所示的仿真圖；其中圖7(a)為延時(shí)對比圖，圖7(b)為邊緣設(shè)備平均能耗對比圖，圖7(c)為滿意度對比圖，圖7(d)為邊緣設(shè)備資源分配對比圖.

由仿真實(shí)驗(yàn)和圖7(a)可知，當(dāng)任務(wù)數(shù)小于20時(shí)，參比算法和本文算法在延時(shí)上的差異較?。划?dāng)任務(wù)數(shù)由20增加至25時(shí)，各算法的時(shí)延增加值為MoGA最大、本文算法最小.從圖7(b)可知，在邊緣設(shè)備能耗方面，PSA算法當(dāng)任務(wù)數(shù)增加到25以后，其后序隨著任務(wù)數(shù)的增加，能耗增加較其他算法快，而本文算法能耗增加程度較為平緩.從滿意度來看，TSEHA、PSA和MoGA算法在任務(wù)數(shù)達(dá)到一定量時(shí)，若繼續(xù)增加任務(wù)數(shù)，則滿意度呈現(xiàn)明顯的下降，而本文算法隨著任務(wù)數(shù)的增加而略有增加.圖7(d)對邊緣設(shè)備資源分配進(jìn)行了仿真，TSEHA、PSA、MoGA隨著任務(wù)數(shù)的增加，邊緣設(shè)備資源分配數(shù)也隨著增加，本文算法邊緣設(shè)備資源分配數(shù)在任務(wù)達(dá)到40而繼續(xù)增加任務(wù)時(shí)，還有剩余資源可分配.

圖7 對比仿真實(shí)驗(yàn)圖Fig.7 Comparison of simulation experiment

6 總 結(jié)

本文對物聯(lián)網(wǎng)邊緣計(jì)算架構(gòu)進(jìn)行設(shè)計(jì)，提出一種含有虛擬化控制器的邊緣網(wǎng)關(guān)型物聯(lián)網(wǎng)邊緣計(jì)算系統(tǒng)架構(gòu)，并對系統(tǒng)任務(wù)分解進(jìn)行定義和描述.然后，利用模糊優(yōu)化理論，建立了ECIoT系統(tǒng)資源分配模糊多目標(biāo)函數(shù)模型，利用非線性六角模糊數(shù)對目標(biāo)函數(shù)進(jìn)行求解，提出了多目標(biāo)向單目標(biāo)轉(zhuǎn)換算法和一種基于改進(jìn)遺傳算法的模因算法的模糊目標(biāo)函數(shù)優(yōu)化算法.最后，對所提出的ECIoT系統(tǒng)資源分配的模糊優(yōu)化方法進(jìn)行實(shí)驗(yàn)和對比仿真，有實(shí)驗(yàn)和仿真可知，本文算法在系統(tǒng)時(shí)延、邊緣設(shè)備平均能耗、滿意度等方面，都得到比較優(yōu)異的資源分配結(jié)果.