朱兆偉，劉婷，錢驊，羅喜良

(1 中國(guó)科學(xué)院上海微系統(tǒng)與信息技術(shù)研究所， 上海 200050； 2 中國(guó)科學(xué)院大學(xué)， 北京 100049；3 上?？萍即髮W(xué)， 上海 201210； 4 中國(guó)科學(xué)院上海高等研究院， 上海 201210)

隨著物聯(lián)網(wǎng)的快速發(fā)展，各類移動(dòng)智能設(shè)備需要處理的任務(wù)量不斷提高。比如，應(yīng)用增強(qiáng)現(xiàn)實(shí)技術(shù)的在線交互游戲設(shè)備需要大量計(jì)算和通信資源。因此，傳統(tǒng)的個(gè)人電腦、智能手機(jī)等移動(dòng)設(shè)備和物聯(lián)網(wǎng)設(shè)備在電池和計(jì)算能力方面面臨巨大的挑戰(zhàn)。一個(gè)經(jīng)典的解決方案是將這些任務(wù)卸載到能源、存儲(chǔ)和計(jì)算資源豐富的云端服務(wù)器[1]，但是遠(yuǎn)距離云端傳輸將會(huì)帶來額外的通信時(shí)間。為了滿足低時(shí)延的服務(wù)要求，研究人員提出利用霧計(jì)算節(jié)點(diǎn)(如具有閑置可用資源的移動(dòng)、物聯(lián)網(wǎng)設(shè)備)數(shù)量龐大、無處不在的天然優(yōu)勢(shì)，將計(jì)算、存儲(chǔ)、控制和通信服務(wù)分布在云到霧的連續(xù)體中。因此，為了更好地利用周圍的霧節(jié)點(diǎn)，急需一個(gè)高效的算法，來決定在霧計(jì)算網(wǎng)絡(luò)中哪些計(jì)算任務(wù)需要卸載以及應(yīng)卸載到哪個(gè)節(jié)點(diǎn)。

一般來說，把高復(fù)雜度的計(jì)算任務(wù)卸載到其他的節(jié)點(diǎn)上能夠有效地節(jié)約本地節(jié)點(diǎn)的計(jì)算資源與能量資源。在一些文獻(xiàn)中，任務(wù)卸載被建模為確定性優(yōu)化問題，例如，Dinh等[2]研究的能量和延遲的聯(lián)合最小化，以及You等[3]研究的延遲約束下的能耗最小化。然而，一個(gè)實(shí)用的任務(wù)卸載策略需要依賴于用戶和服務(wù)器的實(shí)時(shí)狀態(tài)，例如，計(jì)算隊(duì)列的長(zhǎng)度等信息。從這個(gè)方面來說，因計(jì)算隊(duì)列長(zhǎng)度的不確定性，任務(wù)卸載是典型的隨機(jī)規(guī)劃問題，傳統(tǒng)的基于確定性參數(shù)的優(yōu)化方法并不適用。為了解決這個(gè)問題，在文獻(xiàn)[4-7]中，研究人員調(diào)用李雅普諾夫(Lyapunov)優(yōu)化方法，將具有挑戰(zhàn)性的隨機(jī)規(guī)劃問題轉(zhuǎn)換為順序決策問題，其中包括每個(gè)時(shí)隙中的一系列確定性問題。此外，Chen[8]提出一種基于博弈論的分布式解決方案，每個(gè)用戶可以自主地進(jìn)行卸載決策。

上述文獻(xiàn)中提出的任務(wù)卸載方案都假定可以獲得關(guān)于系統(tǒng)參數(shù)的全部信息。但是，在實(shí)際系統(tǒng)中，存在參數(shù)在用戶處未知或部分已知的情況。例如，一些特定的值可能只能作為后驗(yàn)信息，當(dāng)特定節(jié)點(diǎn)被訪問時(shí)才能獲得。Chen和Giannakis[9]將每個(gè)任務(wù)的通信延遲和計(jì)算延遲視為后驗(yàn)信息。Tekin和Van Der Schaar[10]假設(shè)每個(gè)用戶的移動(dòng)性是不可預(yù)測(cè)的。在實(shí)際系統(tǒng)中，可用資源通常是有限的，從而導(dǎo)致每次決策可訪問的節(jié)點(diǎn)數(shù)量非常有限。此時(shí)，若以最小化長(zhǎng)期開銷為目標(biāo)，所做出的決策就必須平衡“探索”與“開發(fā)”之間的權(quán)重。一方面，為了減小眼前的開銷，決策應(yīng)偏向盡可能 “開發(fā)”經(jīng)驗(yàn)最佳節(jié)點(diǎn)；另一方面，從長(zhǎng)遠(yuǎn)角度考慮，用戶需要“探索”其他節(jié)點(diǎn)以找到潛在的性能更優(yōu)的節(jié)點(diǎn)。為了平衡這種關(guān)系，一種流行的方法是將“探索”與“開發(fā)”困境建模為多臂老虎機(jī)(MAB，multi-armed bandit)[11-13]問題。這一理論模型在統(tǒng)計(jì)學(xué)中受到廣泛關(guān)注[13]。

在霧計(jì)算網(wǎng)絡(luò)任務(wù)卸載的研究中，很少有先前的工作研究這種探索與開發(fā)權(quán)衡的關(guān)系，本文將詳細(xì)探討這個(gè)問題。首先，假設(shè)每個(gè)任務(wù)的準(zhǔn)確的處理時(shí)延在任務(wù)處理之前是未知的。基于此，嘗試基于有限的反饋提出一種高效的任務(wù)卸載算法，從而最小化用戶長(zhǎng)期時(shí)延。因此，引入一個(gè)非穩(wěn)態(tài)多臂老虎機(jī)模型以捕捉隨機(jī)且未知的時(shí)延變動(dòng)。相比于以往如文獻(xiàn)[2-7]中的確定性模型，該隨機(jī)模型更加符合實(shí)際模型。之后，基于置信上界(UCB, upper-confidence bound)策略提出一種高效的任務(wù)卸載算法。由于該算法不是直接的UCB策略的應(yīng)用，因此傳統(tǒng)的理論分析無法直接適用。針對(duì)這一改進(jìn)版的UCB算法，將從理論層面給出算法的性能保證。

1 系統(tǒng)模型

1.1 網(wǎng)絡(luò)模型

考慮一個(gè)霧賦能的網(wǎng)絡(luò)(參見圖1)，其中霧節(jié)點(diǎn)按照其功能可分為任務(wù)節(jié)點(diǎn)和輔助節(jié)點(diǎn)兩類。每個(gè)霧節(jié)點(diǎn)都有可能產(chǎn)生計(jì)算任務(wù)，也可以與附近的節(jié)點(diǎn)通信。假定每個(gè)節(jié)點(diǎn)未完成的任務(wù)被緩存在各自節(jié)點(diǎn)的先入先出(FIFO, first-input-first-output)隊(duì)列中。由于單一節(jié)點(diǎn)內(nèi)的計(jì)算和存儲(chǔ)資源有限，在本地處理的任務(wù)通常會(huì)經(jīng)歷較高延遲，這會(huì)降低服務(wù)質(zhì)量(QoS,quality of service)和體驗(yàn)質(zhì)量(QoE, quality of experience)。為了實(shí)現(xiàn)低延遲處理，一個(gè)任務(wù)節(jié)點(diǎn)可以將其一些計(jì)算任務(wù)卸載到附近的輔助節(jié)點(diǎn)。這些輔助節(jié)點(diǎn)通常擁有更多的計(jì)算和存儲(chǔ)資源，并且可以按需部署以幫助其他任務(wù)節(jié)點(diǎn)。在諸如在線游戲等典型應(yīng)用中，任務(wù)通常是周期性地生成的，并且不能任意拆分。因此，假設(shè)每個(gè)節(jié)點(diǎn)在每個(gè)時(shí)隙t的開始生成一個(gè)任務(wù)t，該任務(wù)可以作為一個(gè)整體由本地節(jié)點(diǎn)計(jì)算或者分配給一個(gè)相鄰的輔助節(jié)點(diǎn)。

圖1 霧賦能網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)圖Fig.1 Topography of a fog-enabled network

(1)

在本文中，假設(shè)任務(wù)節(jié)點(diǎn)不能將任務(wù)卸載到正在與其他節(jié)點(diǎn)通信的輔助節(jié)點(diǎn)。還假設(shè)每個(gè)任務(wù)都是獨(dú)立生成的，且任務(wù)節(jié)點(diǎn)之間不合作。

用T(i)表示傳輸每一比特信息到節(jié)點(diǎn)i所需要的時(shí)間，它是一個(gè)依賴于距離的值，并且可以在傳輸前進(jìn)行測(cè)量。在這里，假設(shè)不同任務(wù)節(jié)點(diǎn)占用預(yù)先分配的正交時(shí)間或頻譜資源與輔助節(jié)點(diǎn)通信，如TDMA或FDMA。任務(wù)t的數(shù)據(jù)長(zhǎng)度用Lt表示，假設(shè)任務(wù)大小傳輸延遲LtT(i)不超過一個(gè)時(shí)隙。在本地處理的任務(wù)傳輸延遲為零，即LtT(K)=0。

用Qt(i)表示節(jié)點(diǎn)i在時(shí)隙t開始時(shí)的任務(wù)隊(duì)列長(zhǎng)度。同時(shí)，Wt(i)表示節(jié)點(diǎn)i處理每一比特隊(duì)列中的任務(wù)所需的時(shí)間，Pt(i)表示節(jié)點(diǎn)i處理任務(wù)t中每一比特所需的時(shí)間。在本文中，變量Wt(i)和Pt(i)被定義為隨機(jī)變量，它們的數(shù)學(xué)期望分別為

(2)

假設(shè)每個(gè)任務(wù)的總時(shí)延主要由上述時(shí)延構(gòu)成，即傳輸時(shí)延LtT(i)、隊(duì)列中的等待時(shí)延Qt(i)Wt(i)以及處理時(shí)延LtPt(i)。傳輸計(jì)算結(jié)果等反饋信息所需要的時(shí)延在本文中不考慮。根據(jù)上述定義，將任務(wù)t分配給節(jié)點(diǎn)i處理所需的時(shí)延可以定義為

(3)

在進(jìn)一步分析問題之前，給出下列假設(shè)：

· 假設(shè)1：時(shí)延Ut(i)在任務(wù)t處理完之前是未知的；

· 假設(shè)2：隊(duì)列長(zhǎng)度Qt(i)在每個(gè)時(shí)隙t開始時(shí)由節(jié)點(diǎn)i廣播至各個(gè)霧計(jì)算節(jié)點(diǎn)；

與文獻(xiàn)[2-7]中基于已知系統(tǒng)參數(shù)的模型的任務(wù)卸載問題不同，我們?cè)诩僭O(shè)1和假設(shè)3中對(duì)CPU頻率等系統(tǒng)參數(shù)與處理延遲之間的關(guān)系沒有任何限制，文獻(xiàn)[9]中也體現(xiàn)出這一思想。這是更加實(shí)際的設(shè)置，原因如下。首先，任務(wù)的復(fù)雜度等變量應(yīng)該被建模為一系列獨(dú)立的隨機(jī)變量。這是因?yàn)橛?jì)算本身的不確定性，而且它們的分布可能會(huì)由于任務(wù)類型的變化而發(fā)生突變(1)例如，移動(dòng)用戶在使用不同應(yīng)用程序時(shí)，任務(wù)類型、任務(wù)復(fù)雜度等參數(shù)會(huì)發(fā)生改變。。另外，節(jié)點(diǎn)的計(jì)算能力，例如每個(gè)節(jié)點(diǎn)所分配用于計(jì)算的CPU頻率、CPU內(nèi)核數(shù)目、內(nèi)存大小等都有差異，而且也可能會(huì)發(fā)生突變。上面提到的所有這些不確定性使得系統(tǒng)難以預(yù)測(cè)單一節(jié)點(diǎn)處理不同任務(wù)的時(shí)延。而且，單個(gè)節(jié)點(diǎn)獲取系統(tǒng)的全局節(jié)點(diǎn)的信息會(huì)花費(fèi)大量通信開銷。在傳統(tǒng)模型中，如Mao等[5]假設(shè)時(shí)延簡(jiǎn)單地由任務(wù)數(shù)據(jù)長(zhǎng)度和配置的CPU頻率決定，然而在實(shí)際系統(tǒng)中，單個(gè)任務(wù)節(jié)點(diǎn)很難像傳統(tǒng)模型那樣準(zhǔn)確地估計(jì)計(jì)算時(shí)延和等待時(shí)延。

式中：It表示處理任務(wù)t的節(jié)點(diǎn)的編號(hào)；1{·}為指示函數(shù)，當(dāng)花括號(hào)內(nèi)條件滿足時(shí)，該函數(shù)取值為1，否則為0。

1.2 問題建模

一般的長(zhǎng)期平均時(shí)延最小化問題可以被建模成如下形式：

(4)

解決上述問題有兩個(gè)困難。首先，它是一個(gè)隨機(jī)規(guī)劃問題。在第t個(gè)任務(wù)完成之前，無法得到時(shí)延Ut(i)的確切信息。另外，即使Ut(i)為已知的先驗(yàn)信息，這個(gè)問題仍然是組合優(yōu)化問題，復(fù)雜度為(KT)量級(jí)。這是因?yàn)橄惹暗男遁d決策確定了每個(gè)霧節(jié)點(diǎn)中的隊(duì)列長(zhǎng)度，并進(jìn)一步影響未來任務(wù)的決策。有關(guān)示例，請(qǐng)參閱文獻(xiàn)[10]。為使任務(wù)卸載策略具備在線更新、動(dòng)態(tài)調(diào)整的能力，一種流行的方法是在每個(gè)時(shí)間段將這個(gè)具有挑戰(zhàn)性的隨機(jī)和組合優(yōu)化問題轉(zhuǎn)換為一個(gè)低復(fù)雜度的順序決策問題[2-7]?；谠谥暗?t-1)個(gè)時(shí)隙中做出的任務(wù)卸載決策，最優(yōu)策略變?yōu)閷⑷蝿?wù)t卸載到t時(shí)刻能夠獲得最低時(shí)延的節(jié)點(diǎn)。同時(shí)，在隨機(jī)問題的框架下[12]，關(guān)注隨機(jī)變量的期望是更自然的做法，即[Ut(i)]。因此，表達(dá)式(4)中的問題在第t個(gè)時(shí)隙中變成以下問題：

(5)

2 高效的任務(wù)卸載策略

2.1 基于SW-UCB的任務(wù)卸載

按照前面的假設(shè)，任務(wù)節(jié)點(diǎn)在每個(gè)時(shí)隙開始時(shí)產(chǎn)生一個(gè)任務(wù)。令τs≤s+τmax為收到第s個(gè)任務(wù)反饋的時(shí)間，其中τmax是最大容許時(shí)延。如果任務(wù)時(shí)延超過最大容許時(shí)延，即τs>s+τmax，該任務(wù)視為失敗并被丟棄。根據(jù)文獻(xiàn)[14]，隨機(jī)變量Wt(i)和Pt(i)的估計(jì)值可以由歷史觀測(cè)值的滑動(dòng)窗口平均值得到，即

(6)

式中τ>0表示滑動(dòng)窗口的長(zhǎng)度，以及

(7)

那么，時(shí)延Ut(i)就可以被估計(jì)為

(8)

注意到式(8)中的延遲是根據(jù)Ws(i)和Ps(i)的歷史信息估算的，而不是之前的延遲值，即Us(i),s

(9)

我們用UCB算法來權(quán)衡探索和開發(fā)之間的關(guān)系。從本質(zhì)上來說，這種折中關(guān)系由探索獎(jiǎng)勵(lì)ct(τ,i)來衡量，即探索節(jié)點(diǎn)i會(huì)有額外的獎(jiǎng)勵(lì)。在本文中，令

(10)

(11)

本文算法的具體流程見算法1。

算法1 TOS(task offloading with sliding-window-UCB)任務(wù)卸載算法

步驟2) 令I(lǐng)t=t，卸載任務(wù)t至節(jié)點(diǎn)It；

步驟3)t=t+1；

步驟4) 若t>K，轉(zhuǎn)至步驟5)；否則跳轉(zhuǎn)至步驟2)；

步驟7) 根據(jù)式(11)做出決策It，卸載任務(wù)t至節(jié)點(diǎn)It；

步驟8)t=t+1；

步驟9) 若t>T，算法結(jié)束；否則跳轉(zhuǎn)至步驟5)。

由算法1可知，本文算法的復(fù)雜度主要集中于步驟5)。若直接按照式(6)、式(7)執(zhí)行步驟5)，則該步驟復(fù)雜度為(Kτ)。因此，在執(zhí)行每一次任務(wù)卸載時(shí)，決策復(fù)雜度為(Kτ)。若步驟5)采取增量更新的方式，只關(guān)注最新移入或移出窗口的部分，每次決策的復(fù)雜度可進(jìn)一步降低為(K)。根據(jù)假設(shè)2，為保障算法運(yùn)行，每個(gè)節(jié)點(diǎn)廣播其隊(duì)列長(zhǎng)度。因此，對(duì)于算法本身來說，功耗主要集中于廣播隊(duì)列長(zhǎng)度以及執(zhí)行決策的功耗。此外，任務(wù)卸載本身還包含實(shí)際卸載任務(wù)的功耗(任務(wù)節(jié)點(diǎn)承擔(dān))以及實(shí)際執(zhí)行任務(wù)的功耗(按需部分由輔助節(jié)點(diǎn)承擔(dān))。

雖然上面提出的任務(wù)卸載模型本質(zhì)上是一個(gè)非穩(wěn)態(tài)的MAB模型，但與文獻(xiàn)[14]中提出的傳統(tǒng)模型相比，存在兩個(gè)主要差異。首先，在傳統(tǒng)模型中，決策的反饋是即時(shí)獲得的。而在我們的模型中，如式(6)所示，在任務(wù)完成之前，即τs≤t時(shí)，反饋是無法得到的。而相應(yīng)的延遲是無法忽略的，因?yàn)樗『檬俏覀冃枰男畔?。值得注意的是，延遲的反饋會(huì)影響算法性能，這一現(xiàn)象被Joulani等指出并在文獻(xiàn)[15]中分析。其次，常規(guī)的非穩(wěn)態(tài)MAB模型[14]假設(shè)最好的節(jié)點(diǎn)只在斷點(diǎn)處改變。但是，我們的模型允許最佳節(jié)點(diǎn)在不同時(shí)刻、處理不同任務(wù)時(shí)發(fā)生變化。因此，目前已有的SW-UCB算法的性能保證不能直接應(yīng)用于我們提出的TOS。

2.2 理論分析

(12)

其中

證明見附錄。顯然，該上界取決于總?cè)蝿?wù)數(shù)T、斷點(diǎn)數(shù)ΥT以及窗長(zhǎng)τ的選擇。從式(12)中，可以看出第1項(xiàng)(TB(τ)lnτ)/τ隨著τ增加而減少。另一方面，后面兩項(xiàng)，即ΥT(τ+τmax)和(2(lnτ)2+2lnτ)/ln(1+η)，隨著τ增加而增加。這種折中關(guān)系與我們的直覺一致，即更高的窗口長(zhǎng)度τ有助于在穩(wěn)定情況下更好地估計(jì)，但同時(shí)導(dǎo)致對(duì)環(huán)境突然變化的緩慢反應(yīng)。因此，在式(12)中的不同項(xiàng)之間存在權(quán)衡。為了在穩(wěn)定和突然變化的環(huán)境之間取得平衡，類似于文獻(xiàn)[14]，將τ定義為

(13)

相應(yīng)地，有以下推論。

推論2當(dāng)ΥT=(Tβ),β∈[0,1)，以及T→∞時(shí)，期望的數(shù)量級(jí)為

為了證明所提出的算法的最優(yōu)性，定義卸載前T個(gè)任務(wù)的偽后悔度為

(14)

關(guān)于ζT，有如下推論。

推論3當(dāng)ΥT=(Tβ),β∈[0,1)時(shí)，算法1中的算法是漸進(jìn)最優(yōu)的，即

(15)

根據(jù)推論1和推論2，有

ζT=

那么對(duì)于任意ε>0，存在一個(gè)有限整數(shù)Nε，使得

因此，

推論3說明，在條件ΥT=(Tβ),β∈[0,1)下，當(dāng)T→∞時(shí)，該算法的后悔度以概率為1趨近于零。由知，該算法線性收斂。

3 仿真實(shí)驗(yàn)

在這一章節(jié)中，通過仿真104次任務(wù)卸載來驗(yàn)證本文提出的算法。每次任務(wù)卸載時(shí)，任務(wù)節(jié)點(diǎn)產(chǎn)生一個(gè)任務(wù)。以下是各個(gè)場(chǎng)景中共同的仿真參數(shù)設(shè)定。

· 該霧賦能的網(wǎng)絡(luò)包含1個(gè)任務(wù)節(jié)點(diǎn)和9個(gè)輔助節(jié)點(diǎn)；

· 每個(gè)時(shí)隙長(zhǎng)度為20 ms。任務(wù)數(shù)據(jù)長(zhǎng)度服從Unif(1,15)KB；

· 最大允許時(shí)延為τmax=20時(shí)隙，參數(shù)ξ=0.6；

· 每一比特任務(wù)的處理時(shí)延按照公式Pt(i)=

將算法TOS的性能與兩個(gè)基本的策略(貪婪算法和輪詢算法)、以及我們之前提出的基于折扣因子的在線任務(wù)卸載算法[16]，即TOD(task offloading with discounted-UCB)算法，進(jìn)行比較(2)注意到本文的核心問題在于，當(dāng)任務(wù)卸載的代價(jià)需通過在線學(xué)習(xí)獲得時(shí)，如何權(quán)衡“探索”和“開發(fā)”之間的折中關(guān)系。因此，其他預(yù)知代價(jià)的算法，如文獻(xiàn)[5-8]中提到的李雅普諾夫(Lyapunov)優(yōu)化方法，在本文中難以直接適用。。在貪婪算法中，假設(shè)任務(wù)節(jié)點(diǎn)已知任務(wù)卸載相關(guān)隨機(jī)變量的每一個(gè)樣本值，并在每個(gè)時(shí)隙將任務(wù)卸載給時(shí)延最小的節(jié)點(diǎn)。值得注意的是，雖然貪婪算法代表每一時(shí)刻所能做出的最優(yōu)決策，但該貪婪算法不是因果的，現(xiàn)實(shí)中不能實(shí)現(xiàn)。此外，由于當(dāng)前時(shí)刻決策與下一時(shí)刻狀態(tài)相互耦合，每一時(shí)刻的最優(yōu)決策聯(lián)合起來并不一定代表問題(4)的最優(yōu)解。在輪詢算法中，每個(gè)任務(wù)以循環(huán)的方式依次分配給各個(gè)霧節(jié)點(diǎn)。在TOD算法中，基于D-UCB框架，利用折扣因子γ應(yīng)對(duì)非穩(wěn)態(tài)環(huán)境。據(jù)我們所知，TOD算法為符合本文場(chǎng)景的最新算法。

在圖2中，通過仿真不同的斷點(diǎn)數(shù)目，TOS算法的有效性和穩(wěn)定性得到證明。算法性能通過仿真中各個(gè)任務(wù)的時(shí)延的累積分布函數(shù)(CDF, cumulative distribution function)來體現(xiàn)。圖中，TOD算法的折扣因子γ和TOS算法的滑動(dòng)窗口長(zhǎng)度τ各自按照其理論公式計(jì)算得到。圖2中的兩個(gè)場(chǎng)景都證明TOS算法的性能遠(yuǎn)遠(yuǎn)優(yōu)于輪詢算法，接近于貪婪算法，并且略微優(yōu)于TOD算法。在圖2(a)中，當(dāng)斷點(diǎn)數(shù)目ΥT設(shè)置成150時(shí)，平均每67個(gè)任務(wù)就會(huì)有一次系統(tǒng)參數(shù)的突變。這暗示著TOS算法能夠快速學(xué)習(xí)并適應(yīng)頻繁的系統(tǒng)變化，并且適應(yīng)能力在一定程度上優(yōu)于TOD算法。同樣值得注意的是，從圖2(b)可以看出，當(dāng)系統(tǒng)變化次數(shù)非常有限(ΥT=10)時(shí)，TOS甚至表現(xiàn)出比貪婪算法更小的平均時(shí)延。這一現(xiàn)象揭示每個(gè)時(shí)隙的最優(yōu)決策組合起來并不一定是全局最優(yōu)這一事實(shí)。同時(shí)，這也佐證了我們之前的分析，即節(jié)點(diǎn)的每一時(shí)刻的決策都會(huì)影響系統(tǒng)后續(xù)的狀態(tài)，進(jìn)而影響后續(xù)的決策。

圖3 不同算法的平均后悔度曲線Fig.3 Average regret curves for different algorithms

4 結(jié)束語

本文研究霧賦能的網(wǎng)絡(luò)中一種高效的在線任務(wù)卸載策略以及相應(yīng)的性能保證。考慮到節(jié)點(diǎn)處理速度的期望可能在未知時(shí)刻發(fā)生突變，并且相關(guān)系統(tǒng)參數(shù)信息僅在完成相應(yīng)任務(wù)之后才獲得這一場(chǎng)景，將任務(wù)卸載問題建模成帶有延遲老虎機(jī)反饋的隨機(jī)優(yōu)化問題。為解決這個(gè)問題，基于UCB算法提供一個(gè)高效的在線任務(wù)卸載方案，即TOS。給定特定數(shù)量的斷點(diǎn)ΥT，證明卸載到非最佳節(jié)點(diǎn)的任務(wù)數(shù)量的上界是此外，還證明，當(dāng)任務(wù)數(shù)量趨近于無窮大時(shí)，偽后悔度以概率為1趨近于零。數(shù)值仿真證明，所提出的TOS算法能夠在非穩(wěn)態(tài)環(huán)境中學(xué)習(xí)并選擇正確的節(jié)點(diǎn)以卸載任務(wù)，且表現(xiàn)優(yōu)于TOD算法。

附錄

證明首先，根據(jù)定義做如下事件分解：

此外，將從時(shí)隙(t-τ)到時(shí)隙(t-1)期間缺失的反饋數(shù)量表示為

顯然，缺失的反饋數(shù)目小于τmax，即Gt(τ,i)≤τmax,?t,i。由于

有

令m=A(τ,i)+τmax，得

對(duì)于第2項(xiàng)，定義T(τ)為“卸載良好”的集合。數(shù)學(xué)上，其定義為：

式中：C(τ)表示卸載時(shí)估計(jì)較差的任務(wù)的數(shù)目。特別地，令C(τ)=τ+τmax。將這些估計(jì)較差的任務(wù)孤立出來，得到以下不等式

接下來，需要求得上式中最后一項(xiàng)的上界。注意到3個(gè)事實(shí)：

基于以上事實(shí)，可得

定義

然而，根據(jù)ΔμT(i)的定義有

根據(jù)對(duì)稱性，可知

因此

將所有相關(guān)項(xiàng)求和并作適當(dāng)放縮可得

其中

證畢。