陳 雷

中國(guó)刑事警察學(xué)院公安信息技術(shù)與情報(bào)學(xué)院，遼寧沈陽(yáng)110854

0 引言

快速發(fā)展的移動(dòng)通信技術(shù)促使大量新穎業(yè)務(wù)出現(xiàn)，例如：增強(qiáng)現(xiàn)實(shí)、虛擬現(xiàn)實(shí)等。然而用戶終端設(shè)備有限的計(jì)算能力和電池容量，很難滿足以上業(yè)務(wù)的需求。云無(wú)線接入網(wǎng)絡(luò)，雖然可以提供強(qiáng)大的計(jì)算資源，但是由于云端遠(yuǎn)離本地，系統(tǒng)帶寬受到限制，傳輸時(shí)延較長(zhǎng)，因此，對(duì)傳輸延遲敏感的業(yè)務(wù)很難得到應(yīng)用。為解決該問(wèn)題，霧計(jì)算網(wǎng)絡(luò)應(yīng)運(yùn)而生。由于霧計(jì)算節(jié)點(diǎn)（fog computing node,FCN）部署在用戶的附近，如果用戶的任務(wù)卸載到FCNs上執(zhí)行，則可以大大減少通信的傳輸延遲并節(jié)省從FCNs到云服務(wù)器（cloud servers,CSs）間回傳鏈路的帶寬[1]。

霧計(jì)算網(wǎng)絡(luò)可以通過(guò)多維資源管理來(lái)改善能量消耗、傳輸時(shí)延，滿足QoS需求等，但在霧計(jì)算網(wǎng)絡(luò)的資源分配領(lǐng)域還面臨一些挑戰(zhàn)，例如：1）FCN的計(jì)算能力受限時(shí)，為了減少能量消耗，如何優(yōu)化任務(wù)卸載和資源分配的問(wèn)題；2）為了提升系統(tǒng)性能，F(xiàn)CN如何協(xié)作匹配的問(wèn)題；3）由于用戶的移動(dòng)性產(chǎn)生任務(wù)遷移，進(jìn)而產(chǎn)生額外的資源消耗，在考慮用戶移動(dòng)性的條件下，如何設(shè)計(jì)任務(wù)卸載策略減少資源消耗的問(wèn)題。針對(duì)這些問(wèn)題，現(xiàn)有一些文獻(xiàn)進(jìn)行了研究。文獻(xiàn)[2～5]研究了任務(wù)卸載和資源分配問(wèn)題。文獻(xiàn)[2]提出了一種基于社會(huì)感知的動(dòng)態(tài)任務(wù)卸載策略，并通過(guò)博弈論方法來(lái)最小化任務(wù)執(zhí)行消耗。文獻(xiàn)[3]提出一種近似最優(yōu)的資源分配策略應(yīng)用于任務(wù)卸載中。文獻(xiàn)[4]提出了一種減少能量消耗和任務(wù)延遲的任務(wù)卸載策略。文獻(xiàn)[5]提出了一種基于邊緣計(jì)算的部分任務(wù)卸載策略來(lái)減少霧節(jié)點(diǎn)的能量消耗和減少任務(wù)平均延遲。文獻(xiàn)[6～9]研究了FCN協(xié)作匹配問(wèn)題。文獻(xiàn)[6]提出了一種延遲最小的協(xié)作和卸載策略用于霧節(jié)點(diǎn)協(xié)作。文獻(xiàn)[7]采用博弈論方法，研究了霧節(jié)點(diǎn)間的協(xié)作關(guān)系。文獻(xiàn)[8]在霧計(jì)算網(wǎng)絡(luò)中采用排隊(duì)論來(lái)解決多FCN最優(yōu)化匹配問(wèn)題。文獻(xiàn)[9]提出了一種匹配博弈的延遲接收算法，用來(lái)減少霧節(jié)點(diǎn)協(xié)作時(shí)的平均等待時(shí)間。文獻(xiàn)[10～13]在考慮用戶移動(dòng)性的條件下，研究任務(wù)卸載策略。文獻(xiàn)[10]在霧計(jì)算網(wǎng)絡(luò)中研究了一種基于用戶移動(dòng)性和網(wǎng)絡(luò)異構(gòu)性的劃分算法。文獻(xiàn)[11]提出了一種基于遺傳算法的卸載策略來(lái)提高用戶的服務(wù)質(zhì)量和最小化資源消耗。文獻(xiàn)[12]提出了一種考慮用戶移動(dòng)性的機(jī)會(huì)任務(wù)卸載策略。文獻(xiàn)[13]提出了一種基于跟蹤匹配子序列方法的用戶接入預(yù)測(cè)算法，該算法用來(lái)減少任務(wù)完成時(shí)間，減少能量消耗和提升任務(wù)卸載成功率。通過(guò)以上的分析我們可以看到，這些研究都是將問(wèn)題獨(dú)立分解研究，而實(shí)際應(yīng)用中，往往會(huì)聯(lián)合考慮FCN的計(jì)算能力、用戶的移動(dòng)性、任務(wù)遷移帶來(lái)的資源消耗、傳輸資源和計(jì)算資源的聯(lián)合調(diào)度問(wèn)題。

因此，與以往獨(dú)立研究不同，本文在三層霧計(jì)算網(wǎng)絡(luò)中，通過(guò)用戶駐留時(shí)間分析用戶的移動(dòng)性，并通過(guò)聯(lián)合考慮任務(wù)卸載策略、FCN選擇和計(jì)算資源分配來(lái)減少任務(wù)遷移的概率，降低系統(tǒng)開(kāi)銷(xiāo)，進(jìn)而最大化用戶的總收益。本文研究的用戶收益最大化問(wèn)題可以轉(zhuǎn)換為一個(gè)混合整數(shù)非線性規(guī)劃問(wèn)題，該問(wèn)題是一個(gè)非確定性多項(xiàng)式難題（non-deterministic polynomialhard problem，NP-hard problem），可分解為任務(wù)卸載和資源分配兩部分，我們分別采用基于基尼系數(shù)的霧計(jì)算節(jié)點(diǎn)選擇算法（FCN selection algorithm based on Ginicoefficient,FSAGC）和基于遺傳算法的分布式資源分配算法（distributed resource allocation algorithm based on genetic algorithm,DRAAGA）進(jìn)行求解。

1 霧計(jì)算網(wǎng)絡(luò)架構(gòu)與計(jì)算模型

1.1 霧計(jì)算網(wǎng)絡(luò)架構(gòu)

圖1為三層霧計(jì)算網(wǎng)絡(luò)架構(gòu)中的用戶移動(dòng)模型。三層霧計(jì)算網(wǎng)絡(luò)包括云計(jì)算層、霧計(jì)算層和用戶層。云計(jì)算層距離用戶端較遠(yuǎn)，其計(jì)算和存儲(chǔ)能力強(qiáng)大，但執(zhí)行用戶任務(wù)時(shí)傳輸時(shí)延大。霧計(jì)算層包括大量具有計(jì)算功能的FCN，并且這些節(jié)點(diǎn)距離用戶端較近，可以為用戶提供計(jì)算資源。當(dāng)用戶的任務(wù)卸載到FCN進(jìn)行計(jì)算時(shí)，可以降低任務(wù)傳輸?shù)皆朴?jì)算層的傳輸時(shí)延。用戶層包括大量的用戶設(shè)備，例如車(chē)輛、智能終端等，這些設(shè)備具有移動(dòng)性和計(jì)算能力。

圖1 三層霧計(jì)算網(wǎng)絡(luò)架構(gòu)中的用戶移動(dòng)模型Fig.1 User mobility model in three layers fog computing networks architecture

在圖1中，考慮了用戶設(shè)備的移動(dòng)性，由于FCN覆蓋的范圍有限，如果一個(gè)移動(dòng)設(shè)備已經(jīng)將任務(wù)卸載給FCN，但是在他離開(kāi)原FCN覆蓋范圍前，任務(wù)仍然沒(méi)有執(zhí)行完成，這時(shí)執(zhí)行結(jié)果將通過(guò)云服務(wù)器遷移給正在提供服務(wù)的FCN，這會(huì)引起額外的開(kāi)銷(xiāo)，包括能量消耗和時(shí)間延遲。

在該網(wǎng)絡(luò)中，用戶設(shè)備廣泛分布在FCN附近，而FCN則是隨機(jī)分布的。令NF={FCN1,FCN2,…,FCNf,…,FCNF}表示霧計(jì)算網(wǎng)絡(luò)中的FCN集合,其中F表示FCN的數(shù)量，F(xiàn)CNf用f代替。NU={user1,user2,…,useru,…,userU}表示用戶設(shè)備的集合，其中U表示用戶設(shè)備的數(shù)量，任意用戶設(shè)備useru本文用u代替。假設(shè)每個(gè)用戶設(shè)備每個(gè)時(shí)刻只有一個(gè)任務(wù)需要去執(zhí)行。每個(gè)計(jì)算任務(wù)Zu包含有3個(gè)參數(shù)，?u∈NU。這 里Du（bit）表示從用戶設(shè)備端到FCN端需要傳輸執(zhí)行的任務(wù)量的大?。ɡ纾狠敵鰠?shù)、程序代碼和系統(tǒng)設(shè)置等）;fu（ GHz）表示完成用戶u的任務(wù)所需的計(jì)算資源表示完成任務(wù)Zu允許的最大時(shí)延。本文用CPU周期數(shù)衡量任務(wù)需要的計(jì)算資源[14]。每個(gè)任務(wù)可以本地執(zhí)行或卸載到FCN中執(zhí)行。S={su,u∈NU}表示卸載決定的集合，其中su={0,1}。su=1表示任務(wù)Zu將被卸載到一個(gè)FCN中去執(zhí)行；su=0表示任務(wù)將在本地移動(dòng)設(shè)備上執(zhí)行。

本文考慮正交頻分多址接入（orthogonal frequency division multiple access,OFDMA）上行系統(tǒng)采用多接入的方式。假設(shè)在一個(gè)FCN的覆蓋區(qū)域內(nèi)，一個(gè)FCN能同時(shí)連接多個(gè)用戶設(shè)備。即使設(shè)備在重疊覆蓋區(qū)域內(nèi)，每個(gè)用戶設(shè)備也只能同時(shí)連接到一個(gè)FCN中。定義集合A表示包含所有FCN選擇的變量集合，即A={auf|u∈NU,f∈NF}，auf=1表示用戶設(shè)備u選擇卸載它的任務(wù)給第f個(gè)FCN即FCNf。選擇策略必須滿足如下限制

其中，K表示每個(gè)FCN擁有的最大子信道數(shù)。（1）式表示每個(gè)FCN能同時(shí)服務(wù)的用戶設(shè)備數(shù)目最大為K。（2）式表示每個(gè)用戶設(shè)備同時(shí)只能連接到一個(gè)FCN。令Uf={u∈NU|auf=1}表示卸載任務(wù)給FCNf去執(zhí)行的用戶設(shè)備集合。設(shè)置Uoff=表示系統(tǒng)中卸載任務(wù)給FCNs的所有用戶設(shè)備的集合。用戶設(shè)備的收益可以通過(guò)卸載任務(wù)給FCN來(lái)實(shí)現(xiàn)。定義用戶的收益為任務(wù)在本地執(zhí)行時(shí)的消耗與任務(wù)卸載到FCN執(zhí)行時(shí)的消耗之差。執(zhí)行一個(gè)任務(wù)的消耗可以包括能量消耗和計(jì)算延遲。本地計(jì)算模型和霧計(jì)算模型將會(huì)在下文分別討論。

1.2 計(jì)算模型

1.2.1 本地計(jì)算模型

當(dāng)任務(wù)在本地執(zhí)行時(shí)，能量消耗可以用每個(gè)CPU周期消耗的能量表示，即表示為E=κc2,這里κ是與芯片結(jié)構(gòu)有關(guān)的系數(shù)，c是在本地執(zhí)行任務(wù)時(shí)，執(zhí)行該任務(wù)需要的CPU的計(jì)算資源[15]。基于該模型，任務(wù)Zu的能量消耗Eulocal可以通過(guò)下式得到

因此，本地執(zhí)行的開(kāi)銷(xiāo)可以表示為

1.2.2 霧計(jì)算模型

如果當(dāng)用戶u卸載它的任務(wù)Zu給一個(gè)FCN時(shí)，總執(zhí)行過(guò)程的延遲包括：

1）從用戶u到FCNf的上行傳輸時(shí)間

2）FCNf處理任務(wù)Zu的執(zhí)行時(shí)間

3）從FCNf返回用戶的傳輸時(shí)間。

本文假設(shè)執(zhí)行結(jié)果的數(shù)據(jù)量都遠(yuǎn)小于輸入的數(shù)據(jù)量，并且下行信道的條件要遠(yuǎn)好于上行信道的條件。因此，執(zhí)行結(jié)果回傳給用戶的傳輸延遲可以被忽略[16]。

每個(gè)FCN能同時(shí)服務(wù)于多個(gè)用戶。只要每個(gè)用戶到FCNf的傳輸信干噪比SINRuf能滿足下列要求，該用戶就能接入。

其中，SINRth是保障用戶收益的門(mén)限。因此，能夠接入到FCNf的用戶集合可以表示為={u∈NU|SINRuf≥SINRth}。假設(shè)用戶傳輸他們的任務(wù)給FCN的最大傳輸功率為P={pu|u∈NU}，pu表示用戶u上分配的功率。用戶與FCN間的子信道增益用G表示，G={guf|?u∈NU,?f∈NF}，guf表示從用戶u到FCNf的上行子信道增益。用戶u與FCNf間的SINRuf可以表示為

其中，σ2為背景噪聲，用高斯白噪聲表示。分母中的第二部分表示在相同子載波上，從所有用戶到其他FCN的積累干擾。因此，傳輸速率ruf可以表示為

這里w表示子信道的帶寬。當(dāng)用戶u的任務(wù)卸載到FCNf時(shí)，傳輸時(shí)間可以表示為

因此，任務(wù)在FCNf上處理過(guò)程的總時(shí)間可以表示為上傳時(shí)間與在FCN上執(zhí)行時(shí)間之和

傳輸時(shí)消耗的能量可以表示為

于是用戶u在FCNf上執(zhí)行任務(wù)總的消耗可以表示為

1.2.3 考慮用戶移動(dòng)性的霧計(jì)算模型

在以上霧計(jì)算模型基礎(chǔ)上，考慮FCN的覆蓋范圍有限和用戶的移動(dòng)性，根據(jù)文獻(xiàn)[16]，用戶的移動(dòng)性可以用駐留時(shí)間進(jìn)行衡量，用戶的駐留時(shí)間可以表示為一個(gè)指數(shù)函數(shù)。令表示用戶u在FCNf的覆蓋范圍內(nèi)的駐留時(shí)間。因此，的概率密度函數(shù)為

其中，τuf表示用戶u在FCNf的覆蓋范圍內(nèi)的平均駐留時(shí)間。由于用戶設(shè)備有不同的移動(dòng)軌跡和特點(diǎn)，τuf是一個(gè)變量。假設(shè)每個(gè)用戶的駐留時(shí)間τuf是獨(dú)立同分布的，為了簡(jiǎn)化處理，假設(shè)τuf服從高斯獨(dú)立同分布。

考慮到用戶的移動(dòng)性，當(dāng)任務(wù)卸載給FCN時(shí)，按照?qǐng)?zhí)行過(guò)程的延遲和預(yù)測(cè)用戶的駐留時(shí)間之間的關(guān)系，任務(wù)在FCN中執(zhí)行有以下兩種情況。

情況2：如果用戶的駐留時(shí)間短于傳輸時(shí)間，任務(wù)卸載過(guò)程將不能完成，任務(wù)將在本地執(zhí)行。對(duì)于某些用戶來(lái)說(shuō)，如果任務(wù)Zu卸載給FCNf，并且用戶u的駐留時(shí)間短于FCNf上處理過(guò)程的總時(shí)間此時(shí)的概率是執(zhí)行結(jié)果將通過(guò)云服務(wù)器遷移給正在為用戶u提供服務(wù)的FCN中。這時(shí)的遷移過(guò)程將引起額外的能量消耗和時(shí)間延遲，這些都是用戶消耗的部分。實(shí)際上，遷移消耗也與任務(wù)類(lèi)型和與FCN的距離等因素有關(guān)[17]，為了簡(jiǎn)化，本文假設(shè)任務(wù)發(fā)生遷移時(shí)的消耗只與需要遷移任務(wù)量的大小有關(guān)，因此可以表示為=δDu，其中δ表示遷移消耗系數(shù)。因此，情況2條件下，用戶u的總消耗可以表示為

從（16）和（17）式可以得出，執(zhí)行任務(wù)Zu在這兩種情況下的消耗可表示為

其中，

2 數(shù)學(xué)模型及求解算法

2.1 數(shù)學(xué)模型

如上所述，用戶u的收益與能量消耗和計(jì)算延遲相關(guān)。因此，當(dāng)任務(wù)Zu卸載給FCN，則將收益定義為本地執(zhí)行任務(wù)時(shí)的消耗與FCN上執(zhí)行相同任務(wù)時(shí)的消耗之差。當(dāng)用戶u的任務(wù)Zu在FCN上執(zhí)行時(shí)，令Qu表示用戶u所能獲得的收益。因此，當(dāng)確定了哪些用戶卸載任務(wù)給FCNf去執(zhí)行時(shí)，Qu可表示為

基于以上對(duì)用戶設(shè)備的收益分析，本文提出了一個(gè)在計(jì)算資源和延遲限制條件下最大化用戶總收益的問(wèn)題,表達(dá)如下

由（23）式可知，用戶的總收益與任務(wù)卸載決策、FCN選擇和計(jì)算資源分配有關(guān)。而且用戶的移動(dòng)性對(duì)用戶的總收益有很大的影響。如果卸載任務(wù)的執(zhí)行結(jié)果不能直接傳回用戶端，則FCN需要將結(jié)果通過(guò)云服務(wù)器遷移給另一個(gè)FCN。遷移過(guò)程將引起能量消耗和時(shí)間延遲。

按照用戶的不同駐留時(shí)間，通過(guò)采用比較合適的卸載策略，選擇穩(wěn)定的FCN和分配合適的資源，遷移概率將會(huì)大大降低。這時(shí)遷移消耗也將減少，用戶的收益將提高。因此，在下節(jié)，我們提出了一種基于基尼系數(shù)的霧計(jì)算節(jié)點(diǎn)選擇算法FSAGC來(lái)聯(lián)合考慮最優(yōu)化任務(wù)卸載決策和FCN選擇，隨后提出一種基于遺傳算法的分布式資源分配算法DRAAGA解決計(jì)算資源分配的最優(yōu)化問(wèn)題。

2.2 求解算法

2.2.1 基于基尼系數(shù)的霧計(jì)算節(jié)點(diǎn)選擇算法

根據(jù)文獻(xiàn)[18],基尼系數(shù)常用于經(jīng)濟(jì)學(xué)領(lǐng)域用來(lái)衡量收益差距的指標(biāo)，我們受到基尼系數(shù)的啟發(fā)，采用基尼系數(shù)解決FCN選擇問(wèn)題。本文每個(gè)用戶設(shè)備的收益被定義為一個(gè)選擇函數(shù)，不同的用戶設(shè)備對(duì)系統(tǒng)總收益有不同貢獻(xiàn)。采用選擇函數(shù)獲得Uf={u∈NU|auf=1}，這里被選中的用戶設(shè)備可以貢獻(xiàn)主要收益，收益包括能量、時(shí)間和遷移量。因此基于基尼系數(shù)的霧計(jì)算節(jié)點(diǎn)選擇算法（FCN selection algorithm based on Gini coefficient,FSAGC），詳見(jiàn)算法1。

1）算法步驟

步驟1預(yù)卸載

首先設(shè)置FCNf的候選用戶集合Bf為空集。如果用戶u的任務(wù)Zu能夠卸載到FCN去執(zhí)行，這時(shí)需要滿足以下兩個(gè)限制條件，分別是當(dāng)用戶u滿足以上兩個(gè)限制條件時(shí)，任務(wù)能夠卸載給FCN去執(zhí)行，這時(shí)將該用戶添加到Bf中。如果則任務(wù)在一個(gè)較高概率下將被終止傳輸，這是由于在FCN的覆蓋范圍內(nèi)，用戶u駐留時(shí)間較短。如果則表示用戶u的任務(wù)在FCN上的計(jì)算消耗要大于任務(wù)在本地執(zhí)行時(shí)的計(jì)算消耗，這時(shí)用戶u任務(wù)將在本地執(zhí)行。因此，F(xiàn)CN就需要選擇為其他用戶提供服務(wù)。這樣由于用戶數(shù)量減少，進(jìn)而減少了（23）式中的計(jì)算難度。

步驟2基尼系數(shù)計(jì)算

首先，通過(guò)選擇函數(shù)來(lái)計(jì)算用戶的收益，選擇函數(shù)可以表示為

其中，[x]+=max{x,0}，并且ηuf是用戶u的收益權(quán)重值，可以通過(guò)下式計(jì)算

最后，（23）式中的系數(shù)問(wèn)題可以進(jìn)一步簡(jiǎn)化并且FCNf服務(wù)的用戶的卸載空間可以表示為

步驟3匹配選擇

（23）式中的C5和C6表示限制每個(gè)用戶能連接到FCN的數(shù)量。但是在基尼系數(shù)計(jì)算中被選的用戶可能同時(shí)連接的FCN數(shù)量多于一個(gè)。因此，集合將進(jìn)一步設(shè)置來(lái)滿足C5和C6的要求，具體設(shè)置如下。

首先，如果用戶u被多個(gè)FCN選擇，可以比較該用戶從不同F(xiàn)CN上獲得的收益，進(jìn)而選擇收益最大的FCN。同時(shí)從另一個(gè)Bsf.o集合中刪除用戶u，并且從集合中添加新的用戶。然后，做循環(huán)操作直到所有的用戶滿足C6的要求。最后，獲得每個(gè)FCN的集合Uf={u∈NU|auf=1}，如果用戶沒(méi)有被任何FCN選中，則該用戶的任務(wù)將在本地執(zhí)行。

2）算法復(fù)雜度分析

FSAGC算法的復(fù)雜性是多項(xiàng)式復(fù)雜性，分析如下：

做|NF||Uf|次迭代來(lái)確定某些不適合卸載任務(wù)的用戶，這些用戶在本地執(zhí)行任務(wù)。

計(jì)算復(fù)雜度是Ο(|Bf|)并且存儲(chǔ)過(guò)程的復(fù)雜度是

通過(guò)|NF||Uf|次迭代獲得每個(gè)FCN的集合Uf。因此，F(xiàn)SAGC的計(jì)算復(fù)雜度可以表示為由 于因此復(fù)雜度能進(jìn)一步表示為Ο(K2F)，可以看到FSAGC算法的復(fù)雜度只與FCN中的信道數(shù)和FCN的數(shù)量有關(guān)。由此可知FSAGC算法復(fù)雜度較低，可以滿足在實(shí)際系統(tǒng)中的應(yīng)用。

2.2.2 基于遺傳算法的分布式資源分配算法

由于FCNs是彼此相互獨(dú)立的，因此，每個(gè)FCN的資源分配能夠獨(dú)立進(jìn)行。用戶的收益可表示為一個(gè)適應(yīng)度函數(shù)，該函數(shù)用來(lái)估計(jì)每個(gè)個(gè)體的適合程度。問(wèn)題（23）的約束條件將在初始條件和選擇時(shí)得到保障。選用實(shí)數(shù)編碼串作為算法所用的染色體。每個(gè)染色體都是問(wèn)題（23）的一個(gè)解，可以表示為

這里Ju=表示用戶u在FCNf上分配的計(jì)算資源。

當(dāng)任務(wù)卸載決策和FCN選擇完成后，（23）式的求解問(wèn)題轉(zhuǎn)化為對(duì)資源進(jìn)行分配的求解問(wèn)題，常見(jiàn)的求解方法有回溯法［15］、動(dòng)態(tài)規(guī)劃法算法［15］等，但是這些算法需要較多的迭代次數(shù)，時(shí)間復(fù)雜度和空間復(fù)雜度都較高。為了減少迭代次數(shù)和時(shí)間、空間復(fù)雜度，本文提出了一種基于遺傳算法的分布式資源分配算法（distributed resource allocation algorithm based on genetic algorithm,DRAAGA），如算法2。該算法受達(dá)爾文進(jìn)化論的啟發(fā)，是一種啟發(fā)式搜索方法，用于逼近最佳解，算法過(guò)程體現(xiàn)了自然選擇，它選擇最合適的個(gè)體進(jìn)行后代遺傳，該算法廣泛應(yīng)用于機(jī)器學(xué)習(xí)、組合優(yōu)化和智能計(jì)算中。

首先，在算法開(kāi)始時(shí)，將隨機(jī)生成K個(gè)個(gè)體。這里的個(gè)體就是資源分配方案，包括了FCN中計(jì)算資源的分配、用戶設(shè)備的上行信道和功率的分配。其次，在每次進(jìn)化的過(guò)程中都要做概率為Pc的交叉操作和概率為Pm的變異操作。最后，經(jīng)過(guò)多次進(jìn)化后，最佳個(gè)體即資源分配方案將被計(jì)算出來(lái)。在交叉操作和變異操作中，將采用隨機(jī)競(jìng)賽選擇法［15］。該方法有較低的計(jì)算復(fù)雜度和較好的個(gè)體選擇性。每次隨機(jī)選擇兩個(gè)個(gè)體，保留其中最好的一個(gè)個(gè)體。直到所有個(gè)體都被選到。如果在選擇操作中最好的個(gè)體被忽略，則下一代中最好的個(gè)體將被提取出來(lái)，并代替最好的個(gè)體。

3 仿真分析

3.1 仿真參數(shù)及對(duì)比算法

為了驗(yàn)證本文所提算法在不同參數(shù)下的用戶收益，在Win10系統(tǒng)下，采用Matlab R2014a進(jìn)行1 000次的蒙特卡洛隨機(jī)仿真實(shí)驗(yàn)。我們依據(jù)參考文獻(xiàn)[3]和[19]設(shè)置仿真參數(shù)如表1。霧計(jì)算網(wǎng)絡(luò)的基站覆蓋半 徑是500 m，每個(gè)FCN的覆蓋半徑是100 m。

表1 仿真參數(shù)Table 1 Simulation par ameter s

FCN和用戶是隨機(jī)分布的，隨著用戶的移動(dòng)，用戶的平均駐留時(shí)間服從高斯分布，這里μt=30 s并且σt=10。DRAAGA算法中的子信道數(shù)K=32，Pc=0.6，Pm=0.1。本文提出的算法將與另外4種算法進(jìn)行比較。第一種算法采用了接近最優(yōu)的資源分配機(jī)制（near optimal resource allocation mechanism，NORAM），該機(jī)制中的計(jì)算資源均勻分配，但是該機(jī)制沒(méi)有考慮用戶的移動(dòng)性[3]。第二種算法是忽略移動(dòng)性的資源分配算法（allocation algorithm regardless of mobility，AARM），類(lèi)似于NORAM算法，計(jì)算資源采用最優(yōu)的分配方式，AARM算法也沒(méi)有考慮用戶的移動(dòng)性。第三種算法是隨機(jī)卸載算法（randomly offloading algorithm regard of mobility，ROARM），隨機(jī)卸載的概率是0.5，計(jì)算資源均勻分配。第四種算法是全卸載算法（all offloading algorithm regard of mobility，AOARM），任務(wù)全部卸載，并且計(jì)算資源均勻分配。

3.2 FCN的數(shù)量與用戶總收益之間的關(guān)系

假定仿真參數(shù)：用戶數(shù)量為70，遷移消耗δ=0.05，cF=4 GHz。對(duì)用戶的總收益隨FCN的數(shù)量變化情況進(jìn)行仿真實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果如圖2所示。

從圖2可以看到，隨著FCN數(shù)量的變化，不同算法下的用戶總收益不斷提升。用戶是隨機(jī)分布在FCNs附近。由于每個(gè)FCN計(jì)算資源有限，因此只有少部分用戶能夠得到服務(wù)。隨著部署在用戶附近的FCN越多，將會(huì)有越多的用戶能得到服務(wù)，更多的任務(wù)將被卸載，進(jìn)而提高用戶的總收益。根據(jù)執(zhí)行任務(wù)所需求的計(jì)算資源和用戶的平均駐留時(shí)間，考慮用戶的移動(dòng)性并根據(jù)信道條件，可以幫助FCN選擇合適的用戶卸載任務(wù)。由于駐留時(shí)間服從指數(shù)分布，因此根據(jù)每個(gè)用戶的平均駐留時(shí)間，再分配一定數(shù)量的計(jì)算資源，就可以幫助FCN去計(jì)算用戶的遷移概率。因此，通過(guò)采用最優(yōu)化的任務(wù)卸載和資源分配策略，用戶的遷移概率可以盡可能地降低，最終提升用戶的總收益。

圖2 FCN的數(shù)量與用戶總收益之間的關(guān)系Fig.2 Relationship between the number of FCNs and the revenue of users

從圖2中還可以看到，在ROARM算法中，當(dāng)FCN的數(shù)量大于25時(shí)，算法取得的總收益基本保持不變；在本文提出的算法、AOARM算法、AARM算法和NORAM算法中，當(dāng)FCN的數(shù)量大于35時(shí)，所有算法所取得的總收益基本保持不變。這是由于被服務(wù)的用戶的數(shù)量保持不變，當(dāng)FCN的數(shù)量大到足夠給所有用戶提供服務(wù)時(shí)，隨著FCN數(shù)量的增加，由于某些用戶的信道條件較差和某些用戶的駐留時(shí)間較短，因此這些用戶不能將任務(wù)卸載到FCN，所以算法得到的總收益也不會(huì)進(jìn)一步提升，這也是為什么ROARM算法的總收益最差，而本文提出的算法的總收益最好的原因。由于NORAM算法的計(jì)算資源采用近似最優(yōu)的分配方法，這也使得NORAM算法的總收益要略小于計(jì)算資源最優(yōu)分配的AARM算法。

3.3 用戶數(shù)量與未遷移任務(wù)比例之間的關(guān)系

假定仿真參數(shù)：每個(gè)FCN的總計(jì)算容量cF=4 GHz，遷移消耗δ=0.05，F(xiàn)CN的數(shù)量為20。對(duì)未遷移任務(wù)的比例隨用戶數(shù)量變化情況進(jìn)行仿真，實(shí)驗(yàn)結(jié)果如圖3。

未遷移任務(wù)的比例是指未遷移任務(wù)的數(shù)量占總卸載任務(wù)數(shù)量的比例。由圖3可知，當(dāng)用戶的數(shù)量較小時(shí)，本文提出的算法可保障94%的卸載任務(wù)在用戶離開(kāi)FCN的覆蓋區(qū)域前被執(zhí)行完畢。隨著用戶數(shù)量的增加，采用AOARM算法、AARM算法和NORAM算法時(shí)，未遷移任務(wù)的比例的下降速度要快過(guò)本文提出的算法和ROARM算法的下降速度。這是由于AARM和NORAM算法沒(méi)有考慮用戶的移動(dòng)性，出現(xiàn)卸載量大的問(wèn)題，而AOARM算法是任務(wù)全部卸載的算法，因此它是所有算法中未遷移任務(wù)的比例最小的。從圖3中還可知，當(dāng)用戶數(shù)量較多時(shí)，采用AARM和NORAM算法，有近一半的卸載任務(wù)不能在用戶離開(kāi)前執(zhí)行完畢，因此產(chǎn)生了任務(wù)遷移。這也說(shuō)明，如果選擇不合適的FCN也會(huì)降低未遷移任務(wù)的比例。采用AOARM算法時(shí)未遷移任務(wù)的比例的下降速度最快的原因是，由于AOARM算法是卸載所有的任務(wù)，故未遷移任務(wù)的比例要小于其他算法。采用本文提出的算法時(shí)未遷移任務(wù)的比例也降低，但是降速較慢，這是因?yàn)楸疚奶岢龅乃惴ǔ浞挚紤]了用戶的移動(dòng)性進(jìn)行了最優(yōu)的任務(wù)卸載，并且也采用了最優(yōu)的資源分配方式。同時(shí)，我們還能看到采用ROARM算法時(shí)，未遷移任務(wù)的比例下降最慢，這是因?yàn)殡S機(jī)卸載50%的任務(wù)，卸載量較小。同時(shí)結(jié)合仿真圖4，我們還能分析出，當(dāng)任務(wù)卸載越多，任務(wù)遷移就越多，對(duì)用戶的總收益影響越大，因?yàn)檫w移任務(wù)將產(chǎn)生系統(tǒng)的消耗。

圖3 用戶數(shù)量與未遷移任務(wù)比例之間的關(guān)系Fig.3 Relationship between the number of users and the ratio of not migrated tasks

3.4 用戶數(shù)量與用戶總收益之間的關(guān)系

假定仿真參數(shù)：每個(gè)FCN的總計(jì)算容量cF=4 GHz，遷移消耗δ=0.05，F(xiàn)CN的數(shù)量為20。對(duì)用戶的總收益隨用戶數(shù)量變化情況進(jìn)行仿真，實(shí)驗(yàn)結(jié)果如圖4。

圖4 用戶數(shù)量與用戶總收益之間的關(guān)系Fig.4 Relationship between the number of users and the revenue of users

從圖4中可以看到隨著用戶數(shù)量的增加，AOARM、AARM和NORAM算法的用戶總收益的變化不同于本文算法和ROARM算法。起初，所有算法的總收益都隨著用戶數(shù)量的增加而增加。然而，隨著用戶數(shù)量的增加，AOARM、AARM和NORAM算法增長(zhǎng)的速率逐漸變慢，當(dāng)用戶數(shù)量值達(dá)到60時(shí)，總收益開(kāi)始降低。由于FCN數(shù)量和計(jì)算容量的限制，因此FCN只能服務(wù)于有限的用戶數(shù)量。用戶數(shù)量沒(méi)有達(dá)到上限時(shí)，這些算法總收益不斷增加；伴隨著任務(wù)卸載量的增加，遷移的任務(wù)也在增加，當(dāng)增加的遷移消耗大于任務(wù)卸載所獲得的收益時(shí)，這些算法的用戶總收益開(kāi)始下降。因?yàn)锳OARM算法卸載所有的任務(wù)，AARM算法沒(méi)有考慮用戶的移動(dòng)性，只要FCN有計(jì)算容量，AARM算法就卸載任務(wù)，因此AOARM算法任務(wù)遷移量要多于AARM算法，AOARM算法的收益要低于AARM算法。另外，當(dāng)用戶數(shù)量大于60時(shí)，NORAM算法的收益也隨著用戶數(shù)量的增加逐漸變小，這是因?yàn)?，F(xiàn)CN的計(jì)算資源均勻分配給每個(gè)用戶，當(dāng)用戶數(shù)量增多時(shí)，就使得有更多的任務(wù)不能在用戶離開(kāi)FCN覆蓋區(qū)域前執(zhí)行完畢，就會(huì)產(chǎn)生遷移，使得用戶收益開(kāi)始下降。本文提出的算法和ROARM算法還未開(kāi)始下降，是因?yàn)楸疚奶岢龅乃惴紤]了用戶的移動(dòng)性和遷移的概率，因此較好地控制了卸載任務(wù)數(shù)量；ROARM算法采用隨機(jī)卸載的概率是0.5，使得卸載量較少。因此這兩種算法在用戶數(shù)量為20～80時(shí)都還未達(dá)到FCN處理的瓶頸，所以用戶的總收益未隨著用戶數(shù)量的增加而下降。從圖4中還能夠看到，NORAM算法的收益要低于AARM算法，這是因?yàn)镹ORAM算法是均勻的分配資源給用戶，而AARM算法是最優(yōu)的方式分配資源給用戶。

3.5 FCN的計(jì)算容量與用戶總收益之間的關(guān)系

假定仿真參數(shù)：用戶數(shù)量為70，F(xiàn)CN的數(shù)量為20，遷移消耗δ=0.05。對(duì)用戶總收益隨FCN的計(jì)算容量cF變化情況進(jìn)行仿真，實(shí)驗(yàn)結(jié)果如圖5。

圖5 FCN的計(jì)算容量與用戶總收益之間的關(guān)系Fig.5 Relationship between the computing capacity of each FCN and the revenue of users

從圖5中可以看到，隨著FCN的計(jì)算容量從4～8 GHz變化時(shí)，所有算法的總收益隨著每個(gè)FCN的計(jì)算容量的提升而增加。當(dāng)起始處FCN的計(jì)算容量較小時(shí)，本文算法的總收益仍然高于其他算法，這說(shuō)明本文算法能較好地利用FCN的計(jì)算資源。然而，隨著FCN計(jì)算容量的增加，本文算法與AARM和NORAM算法相比差距在逐漸變小。因?yàn)楸疚乃惴榱藴p少遷移的概率將以用戶總收益最大化為目標(biāo)，選擇性地卸載任務(wù)，隨著FCN計(jì)算容量的增加，卸載的任務(wù)需要保證在用戶離開(kāi)FCN覆蓋的范圍前，能以較高概率執(zhí)行完畢。由于本文算法中卸載任務(wù)的數(shù)量沒(méi)有快速地改變，因此總收益增長(zhǎng)得較慢。然而，在AARM和NORAM算法中，當(dāng)FCN計(jì)算容量增加時(shí)，任務(wù)遷移減少，使得這兩種算法用戶總收益增長(zhǎng)的速度要大于本文算法。從圖5中還可以看到，當(dāng)FCN計(jì)算容量增加，AARM算法和NORAM算法所獲得的用戶總收益，與AOARM算法所獲得的用戶總收益之間的差距將越來(lái)越大。這是因?yàn)锳OARM算法卸載任務(wù)的數(shù)量和遷移任務(wù)的數(shù)量都大于AARM和NORAM算法，在AOARM算法中所有任務(wù)被卸載，使得某些用戶只能在較差的信道條件下也進(jìn)行卸載，因此影響了用戶總收益。在ROARM算法中由于是隨機(jī)卸載50%的任務(wù)，任務(wù)量較少，隨著FCN計(jì)算容量的增加，卸載的任務(wù)都能在用戶離開(kāi)FCN覆蓋范圍前執(zhí)行完畢，因此，ROARM算法所獲得的用戶總收益增長(zhǎng)最少。

3.6 用戶平均駐留時(shí)間與用戶總收益之間的關(guān)系

假定仿真參數(shù)：用戶數(shù)量為70，F(xiàn)CN的數(shù)量為20，遷移消耗δ=0.05，計(jì)算容量cF=4 GHz。在這里用戶的平均駐留時(shí)間服從高斯分布其中μt=30 s，σt=10。對(duì)用戶總收益隨用戶平均駐留時(shí)間μt變化情況進(jìn)行仿真，實(shí)驗(yàn)結(jié)果如圖6。

在圖6中，能看到當(dāng)用μt小于40 s時(shí)，本文算法在用戶總收益上增加得比其他四種算法要快。這是因?yàn)殡S著μt的增加，參與仿真的用戶數(shù)量也要多于以前。因此，考慮到每個(gè)用戶的駐留時(shí)間的增加，能幫助FCN選擇更多的用戶提供服務(wù)，而且不需要分配過(guò)多的計(jì)算資源來(lái)減少遷移概率，因此有更多用戶的計(jì)算資源得以節(jié)省。需要注意的是當(dāng)μt大于50 s時(shí)，幾乎每種算法的總收益都停止增加。因?yàn)楫?dāng)駐留時(shí)間足夠長(zhǎng)時(shí)，用戶絕大部分的卸載任務(wù)都能在遷移前完成，并將結(jié)果傳回用戶端。再看算法間的不同，雖然μt增加，但每個(gè)用戶仿真所用的平均駐留時(shí)間較小，增加的平均駐留時(shí)間不會(huì)給用戶帶來(lái)更多的總收益，因此增加μt將不會(huì)縮小本文算法與其他算法間的差距。

圖6 用戶平均駐留時(shí)間與用戶總收益之間的關(guān)系Fig.6 Relationship between the average sojourn time of users and the revenue of users

3.7 任務(wù)遷移消耗與用戶總收益之間的關(guān)系

假定仿真參數(shù)：用戶數(shù)量為70，F(xiàn)CN的數(shù)量為20，計(jì)算容量cF=4 GHz。對(duì)用戶的總收益隨遷移消耗數(shù)量變化情況進(jìn)行仿真，實(shí)驗(yàn)結(jié)果如圖7。

圖7 遷移消耗與用戶總收益之間的關(guān)系Fig.7 Relationship between the migration cost and the revenue of users

從仿真中可以看到，盡管隨著遷移消耗的增加，用戶的總收益下降，但是本文算法所獲得的總收益與其他算法相比要多，這證明了本文算法能有效的降低用戶遷移的概率。在AARM算法、NORAM算法和AOARM算法中，由于忽略了用戶的移動(dòng)性，將導(dǎo)致較多的任務(wù)卸載。由于用戶和FCN上的計(jì)算資源有限，使得遷移概率變高，因此，大量增加的遷移消耗將引起用戶總收益的下降。很明顯地可以看到，AOARM算法與AARM算法和NORAM算法相比，隨遷移消耗的增加所獲得的用戶總收益降低的幅度要少，這是因?yàn)?，AOARM算法在卸載全部任務(wù)的同時(shí)，與AARM和NORAM算法相比，更能夠平衡用戶短駐留時(shí)間和長(zhǎng)駐留時(shí)間所產(chǎn)生的影響，因此用戶總收益變化幅度較小。由于ROARM算法采用隨機(jī)卸載的方法，并且計(jì)算資源相對(duì)充足，因此有較少的任務(wù)被卸載，所以遷移概率較小，遷移消耗的增加對(duì)用戶總收益產(chǎn)生的影響較小，因此仿真曲線比較平滑。

4 結(jié)語(yǔ)

本文將用戶的移動(dòng)性用符合指數(shù)分布的駐留時(shí)間進(jìn)行描述。在霧計(jì)算網(wǎng)絡(luò)中，為了減少遷移概率的同時(shí)最大化用戶的總收益，提出了一個(gè)考慮移動(dòng)感知下的任務(wù)卸載和計(jì)算資源分配算法。提出的算法在考慮用戶移動(dòng)性的同時(shí)，能最大化用戶設(shè)備的總收益。仿真結(jié)果顯示，本文提出的算法與其他現(xiàn)有的算法相比較，能提高用戶的總收益。