霧計算網(wǎng)絡(luò)中基于移動感知的任務(wù)卸載和資源分配

陳 雷

中國刑事警察學院公安信息技術(shù)與情報學院，遼寧沈陽110854

0 引言

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

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

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

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

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

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

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

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

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

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

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

1.2 計算模型

1.2.1 本地計算模型

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

因此，本地執(zhí)行的開銷可以表示為

1.2.2 霧計算模型

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

1）從用戶u到FCNf的上行傳輸時間

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

3）從FCNf返回用戶的傳輸時間。

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

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

其中，SINRth是保障用戶收益的門限。因此，能夠接入到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表示子信道的帶寬。當用戶u的任務(wù)卸載到FCNf時，傳輸時間可以表示為

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

傳輸時消耗的能量可以表示為

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

1.2.3 考慮用戶移動性的霧計算模型

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

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

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

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

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

其中，

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

2.1 數(shù)學模型

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

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

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

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

2.2 求解算法

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

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

1）算法步驟

步驟1預卸載

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

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

首先，通過選擇函數(shù)來計算用戶的收益，選擇函數(shù)可以表示為

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

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

步驟3匹配選擇

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

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

2）算法復雜度分析

FSAGC算法的復雜性是多項式復雜性，分析如下：

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

計算復雜度是Ο(|Bf|)并且存儲過程的復雜度是

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

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

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

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

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

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

3 仿真分析

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

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

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

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

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

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

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

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

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

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

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

未遷移任務(wù)的比例是指未遷移任務(wù)的數(shù)量占總卸載任務(wù)數(shù)量的比例。由圖3可知，當用戶的數(shù)量較小時，本文提出的算法可保障94%的卸載任務(wù)在用戶離開FCN的覆蓋區(qū)域前被執(zhí)行完畢。隨著用戶數(shù)量的增加，采用AOARM算法、AARM算法和NORAM算法時，未遷移任務(wù)的比例的下降速度要快過本文提出的算法和ROARM算法的下降速度。這是由于AARM和NORAM算法沒有考慮用戶的移動性，出現(xiàn)卸載量大的問題，而AOARM算法是任務(wù)全部卸載的算法，因此它是所有算法中未遷移任務(wù)的比例最小的。從圖3中還可知，當用戶數(shù)量較多時，采用AARM和NORAM算法，有近一半的卸載任務(wù)不能在用戶離開前執(zhí)行完畢，因此產(chǎn)生了任務(wù)遷移。這也說明，如果選擇不合適的FCN也會降低未遷移任務(wù)的比例。采用AOARM算法時未遷移任務(wù)的比例的下降速度最快的原因是，由于AOARM算法是卸載所有的任務(wù)，故未遷移任務(wù)的比例要小于其他算法。采用本文提出的算法時未遷移任務(wù)的比例也降低，但是降速較慢，這是因為本文提出的算法充分考慮了用戶的移動性進行了最優(yōu)的任務(wù)卸載，并且也采用了最優(yōu)的資源分配方式。同時，我們還能看到采用ROARM算法時，未遷移任務(wù)的比例下降最慢，這是因為隨機卸載50%的任務(wù)，卸載量較小。同時結(jié)合仿真圖4，我們還能分析出，當任務(wù)卸載越多，任務(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ù)：每個FCN的總計算容量cF=4 GHz，遷移消耗δ=0.05，F(xiàn)CN的數(shù)量為20。對用戶的總收益隨用戶數(shù)量變化情況進行仿真，實驗結(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算法增長的速率逐漸變慢，當用戶數(shù)量值達到60時，總收益開始降低。由于FCN數(shù)量和計算容量的限制，因此FCN只能服務(wù)于有限的用戶數(shù)量。用戶數(shù)量沒有達到上限時，這些算法總收益不斷增加；伴隨著任務(wù)卸載量的增加，遷移的任務(wù)也在增加，當增加的遷移消耗大于任務(wù)卸載所獲得的收益時，這些算法的用戶總收益開始下降。因為AOARM算法卸載所有的任務(wù)，AARM算法沒有考慮用戶的移動性，只要FCN有計算容量，AARM算法就卸載任務(wù)，因此AOARM算法任務(wù)遷移量要多于AARM算法，AOARM算法的收益要低于AARM算法。另外，當用戶數(shù)量大于60時，NORAM算法的收益也隨著用戶數(shù)量的增加逐漸變小，這是因為，F(xiàn)CN的計算資源均勻分配給每個用戶，當用戶數(shù)量增多時，就使得有更多的任務(wù)不能在用戶離開FCN覆蓋區(qū)域前執(zhí)行完畢，就會產(chǎn)生遷移，使得用戶收益開始下降。本文提出的算法和ROARM算法還未開始下降，是因為本文提出的算法考慮了用戶的移動性和遷移的概率，因此較好地控制了卸載任務(wù)數(shù)量；ROARM算法采用隨機卸載的概率是0.5，使得卸載量較少。因此這兩種算法在用戶數(shù)量為20～80時都還未達到FCN處理的瓶頸，所以用戶的總收益未隨著用戶數(shù)量的增加而下降。從圖4中還能夠看到，NORAM算法的收益要低于AARM算法，這是因為NORAM算法是均勻的分配資源給用戶，而AARM算法是最優(yōu)的方式分配資源給用戶。

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

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

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

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

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

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

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

圖6 用戶平均駐留時間與用戶總收益之間的關(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，計算容量cF=4 GHz。對用戶的總收益隨遷移消耗數(shù)量變化情況進行仿真，實驗結(jié)果如圖7。

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

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

4 結(jié)語

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