宋 煜，張 帥，嚴永輝，錢柱中

（1.江蘇方天電力技術(shù)有限公司，南京 211102；2.南京大學(xué)計算機軟件新技術(shù)國家重點實驗室，南京 210023；3.南京大學(xué)軟件新技術(shù)與產(chǎn)業(yè)化協(xié)同創(chuàng)新中心，南京 210023）

0 概述

虛擬現(xiàn)實（Virtual Reality，VR）和增強現(xiàn)實（Augmented Reality，AR）技術(shù)能夠幫助用戶在各類應(yīng)用中獲得更好的體驗，如醫(yī)生利用VR 技術(shù)可以重復(fù)地模擬手術(shù)以尋找最佳手術(shù)方案，消費者借助AR技術(shù)可以在商場中實時查看各類產(chǎn)品信息。VR 任務(wù)中對用戶視野的3D 實時渲染以及AR 任務(wù)中對真實場景的實時識別均為計算密集型任務(wù)，由于用戶終端計算性能有限，因此需要在遠程云服務(wù)器上完成此類任務(wù)。然而，移動終端和遠程云服務(wù)器之間帶寬有限且網(wǎng)絡(luò)不穩(wěn)定，當(dāng)終端發(fā)起與遠程云服務(wù)器之間的大量實時數(shù)據(jù)傳輸時，網(wǎng)絡(luò)延時會對應(yīng)用效果造成較大影響。

在5G 時代，移動基站可以作為邊緣云計算節(jié)點取代遠程云服務(wù)器的部分功能。相較于遠程云服務(wù)器，邊緣云計算節(jié)點到用戶終端物理距離更近。一方面，邊緣云計算節(jié)點到用戶終端具有更高的傳輸速度；另一方面，由于物理距離近，因此可以對某些特定場景下的應(yīng)用做更細致的優(yōu)化。例如，同一個VR 場景中的多個用戶所需要渲染的視野圖像都來自同一個虛擬世界建模，為這幾個用戶渲染的圖像往往存在冗余，文獻［1］針對此類冗余進行了優(yōu)化，顯著提升了VR 應(yīng)用的實時響應(yīng)性能。

在一些AR 應(yīng)用中同樣也存在著類似的冗余。以AR 導(dǎo)航為例，在一個邊緣云計算節(jié)點附近的AR導(dǎo)航用戶往往具有非常相似的周邊環(huán)境，那么在AR識別過程中，多個導(dǎo)航用戶對環(huán)境的識別任務(wù)就會存在冗余。因此，如何利用這樣的冗余來減少邊緣云節(jié)點的計算量，提升整體的用戶體驗，成為一個有待研究的問題。

本文介紹基于緩存的AR 性能優(yōu)化方法，包括任務(wù)請求處理、邊緣節(jié)點組織和緩存管理等方面的優(yōu)化。在此基礎(chǔ)上，對可部署資源有限場景下優(yōu)化用戶時延的問題進行數(shù)學(xué)建模，進而針對中小規(guī)模和大規(guī)模場景分別提出IDM 和LDM 算法，并通過實驗驗證算法性能。

1 相關(guān)工作

本節(jié)介紹計算卸載、移動AR/VR 應(yīng)用、服務(wù)緩存放置和邊緣計算資源管理等方面的相關(guān)工作。

在計算卸載方面，學(xué)者針對卸載內(nèi)容、卸載時機、卸載方法等進行了大量研究［2-4］。WANG 等人將邊緣節(jié)點網(wǎng)絡(luò)抽象成一個圖結(jié)構(gòu)，研究對于給定的基站集合如何放置單獨的邊緣節(jié)點，從而使一個節(jié)點服務(wù)于多個基站，以盡可能地均衡負載并降低訪問時延［5］。本文將邊緣節(jié)點網(wǎng)絡(luò)抽象成一個自組織并定時同步的網(wǎng)絡(luò)，關(guān)注當(dāng)多個用戶都卸載到同一個邊緣云網(wǎng)絡(luò)時可能存在冗余計算的問題。在此基礎(chǔ)上，研究在原基站添加邊緣節(jié)點功能的部署問題，在總部署代價有限的情況下，通過安排新增邊緣節(jié)點的計算資源量以降低用戶時延。

筆者著眼于邊緣計算背景下移動AR 應(yīng)用的性能優(yōu)化。在此之前，也有類似基于云計算的研究工作［6］，例如：Glimpse 通過緩存機制提升了識別準(zhǔn)確率，使用觸發(fā)幀選擇的方法降低了無線傳輸時延［7］；面向指紋識別設(shè)計的VisualPrint 系統(tǒng)方案僅上傳圖像中最不同的特征，從而在低帶寬的情況下對AR 任務(wù)進行卸載［8］。類似于AR，VR 也是邊緣計算的殺手級應(yīng)用，在此方面，LI 等人設(shè)計了MUVR 系統(tǒng)，在多用戶的邊緣云上對3D 渲染的冗余任務(wù)進行優(yōu)化，提升了應(yīng)用性能［1］。本文根據(jù)AR 和邊緣計算節(jié)點的共同點做了進一步的優(yōu)化：AR 的環(huán)境識別與請求發(fā)出的位置密切相關(guān)，而被分配到的邊緣計算節(jié)點往往也與請求發(fā)出的位置距離不遠，因此，針對這樣特定的環(huán)境，本文使用緩存來進行計算冗余消減，從而有效減少傳輸和計算開銷。

當(dāng)多個服務(wù)器在處理相似的內(nèi)容時，使用緩存就可以避免不必要的重復(fù)處理。關(guān)于如何放置服務(wù)緩存的問題，之前的一些工作調(diào)研內(nèi)容包括視頻緩存到服務(wù)器的最優(yōu)分配方案、減少數(shù)據(jù)傳輸量的最優(yōu)緩存位置、在稠密蜂窩網(wǎng)絡(luò)中的動態(tài)服務(wù)緩存等［9-11］。本文研究在基站具有邊緣計算能力的場景下如何部署計算緩存的邊緣服務(wù)器和分配有限的資源，從而使用戶獲得時延更低的使用體驗。

在邊緣云中，資源管理對于服務(wù)質(zhì)量和系統(tǒng)效率有著重要作用。目前，學(xué)者主要對資源分配和任務(wù)調(diào)度進行研究，包括均衡網(wǎng)絡(luò)節(jié)點負載以優(yōu)化應(yīng)用性能、動態(tài)適應(yīng)環(huán)境變化、基于層次架構(gòu)的啟發(fā)式負載分配算法、最小化總的加權(quán)服務(wù)響應(yīng)時間的在線任務(wù)分配與調(diào)度算法等［12-14］?？紤]到直接為基站增加邊緣計算功能可以避免單獨部署邊緣節(jié)點的較大開銷，本文研究在可部署代價有限的情況下如何分配可部署的計算資源，從而使用戶時延降到最低。

因為移動增強現(xiàn)實（Mobile AR，MAR）是在現(xiàn)實世界情境下應(yīng)用的，所以快速準(zhǔn)確的物體識別成為能夠?qū)⑻摂M世界與真實世界互相融合的關(guān)鍵環(huán)節(jié)［15］?，F(xiàn)有物體識別方法包括傳統(tǒng)方法［16-18］和基于深度卷積神經(jīng)網(wǎng)絡(luò)的方法［19-20］。訓(xùn)練深度卷積神經(jīng)網(wǎng)絡(luò)是目前較為流行的方法，但是要達到一定的精度需要不小的計算代價。Chameleon 系統(tǒng)通過多節(jié)點協(xié)作，在計算資源投入和物體識別精度上取得了很好的權(quán)衡［19］。Focus系統(tǒng)通過使用簡單的卷積神經(jīng)網(wǎng)絡(luò)構(gòu)建近似索引，加快了對數(shù)據(jù)集的吸收和查詢［20］。本文關(guān)注AR 識別請求與其物理位置之間的關(guān)系，以緩存的方式對物體識別進行加速。

2 問題描述

本節(jié)介紹基于緩存的冗余消減系統(tǒng)模型，對用戶請求時延、用戶軌跡預(yù)處理和節(jié)點部署做形式化表述，將問題聚焦于已知用戶請求軌跡且部署總代價有限的情況下，如何為基站部署邊緣節(jié)點的計算資源，以取得最低的平均時延，并證明此問題是NP-Complete 的。

2.1 基于緩存的冗余消減

2.1.1 節(jié)點緩存

本文考慮在一個城市中多個部署邊緣計算功能的基站協(xié)作進行AR 識別的場景。當(dāng)一個移動終端需要發(fā)起任務(wù)請求時，它會尋找距離自己最近的基站并將任務(wù)相關(guān)數(shù)據(jù)傳送出去?；臼盏竭@樣的請求后，首先會檢查相關(guān)數(shù)據(jù)是否已經(jīng)被計算過。如果自己計算過，則直接返回計算結(jié)果；如果在其他節(jié)點計算過，則將請求重定向到緩存所在節(jié)點，由緩存所在節(jié)點返回計算結(jié)果；如果沒有計算過，則在當(dāng)前節(jié)點進行計算并把結(jié)果緩存在當(dāng)前節(jié)點中，并通知所有其他節(jié)點。

為避免冗余計算，本文設(shè)置緩存為全局式的，即在整個城市中任意一個位置的請求都只會被計算一次。一次典型的基于緩存的AR 任務(wù)執(zhí)行過程如圖1 所示。

圖1 一次典型的基于緩存的AR 任務(wù)執(zhí)行過程Fig.1 A typical cache-based AR task execution process

2.1.2 全局緩存

要實現(xiàn)全局緩存，就需要全局節(jié)點通過一定方式保持同步。在本文構(gòu)建的冗余消減模型中，全局節(jié)點自組織地形成一棵最小生成樹（Minimum Spanning Tree，MST），每個節(jié)點只需要和父子節(jié)點周期性地發(fā)送?；顖笪募纯删S持此結(jié)構(gòu)的正常運行。當(dāng)節(jié)點離開或失效時，其父子節(jié)點就可以檢測到，子節(jié)點直接連接到失效節(jié)點的父節(jié)點上。若根節(jié)點失效，則從根節(jié)點的子節(jié)點中隨機選取一個作為根節(jié)點。在每個節(jié)點中維護一張如表1 所示的緩存表，以保存符合某些特征的數(shù)據(jù)是否已經(jīng)被計算過并緩存至所在的節(jié)點。節(jié)點接收到新的請求時，會先查詢這張表以獲取緩存信息。若沒有緩存，節(jié)點經(jīng)過計算生成新緩存之后，它會通知其父子節(jié)點遞歸地更新所有節(jié)點的緩存表，具體過程如圖2 所示。

表1 全局緩存的緩存表Table 1 Cache table for global cache

圖2 緩存更新示意圖Fig.2 Schematic diagram of cache update

2.2 請求時延

由于信號隨著距離增加而衰減，因此基站的服務(wù)范圍通常情況下是一個以基站為圓心的圓。本文設(shè)基站的有效服務(wù)距離為r，即在半徑r內(nèi)的用戶都可以接收到該基站的有效服務(wù)。同樣地，位于基站覆蓋范圍內(nèi)的用戶在收發(fā)數(shù)據(jù)時也會受到距離的影響，考慮到坐標(biāo)是一個多維信息，因此，用向量來表示用戶與基站的位置，使用函數(shù)dist(x，y)來表示兩個坐標(biāo)向量x與y的距離。

AR 識別任務(wù)往往是一個計算密集型任務(wù)，因此，一個邊緣服務(wù)器所具有的CPU 核心數(shù)、主頻以及GPU 時鐘速度、內(nèi)存總線容量等計算資源參數(shù)對于AR 任務(wù)的效率起到重要作用?？紤]到相關(guān)參數(shù)往往是整數(shù)，本文把計算資源抽象為一個正整數(shù)c。

在AR 識別請求中，輸入的數(shù)據(jù)通常為圖像視頻信息。不同設(shè)備、不同用戶在進行AR 識別時分辨率和圖像大小往往各不相同，因此，定義變量s表示請求的數(shù)據(jù)量大小。

對于一個位置為y且計算資源量為c的邊緣服務(wù)器，當(dāng)它收到一個來自位置x且數(shù)據(jù)量為s的請求時，其請求時延可能出現(xiàn)以下兩種情況：

1）若請求數(shù)據(jù)已在服務(wù)器的緩存表中，則可以直接獲取計算結(jié)果，此時用戶時延包括數(shù)據(jù)傳輸時延與獲取結(jié)果時延兩部分。數(shù)據(jù)傳輸時延表示為μs·dist(x，y)，時延與數(shù)據(jù)量、距離成正比，其中，μ為比例系數(shù)。獲取結(jié)果時延定義為一個較小的常量η，因為獲取計算結(jié)果時，無論是返回本地結(jié)果還是返回其他服務(wù)器結(jié)果，開銷都很小。

2）若請求數(shù)據(jù)不在服務(wù)器的緩存表中，則節(jié)點需要先對請求數(shù)據(jù)進行處理并緩存，然后將緩存結(jié)果返回給用戶，此過程的時延包括數(shù)據(jù)傳輸時延和數(shù)據(jù)處理時延。數(shù)據(jù)傳輸時延與上一種情況相同，為μs·dist(x，y)。數(shù)據(jù)處理時延定義為λ·，即處理時延與任務(wù)量成正比，與計算資源量成反比，其中，λ為比例系數(shù)。

2.3 用戶軌跡

對現(xiàn)有基站和云服務(wù)器的數(shù)據(jù)進行分析，得到AR 用戶的歷史軌跡數(shù)據(jù)集U={X，S}，其中，X為所有請求的位置信息，X={x1，x2，…，xn}，S為所有請求的任務(wù)量，S={s1，s2，…，sn}。數(shù)據(jù)集包含n個請求，按照時間先后順序排序，第i個請求的發(fā)出位置為xi，數(shù)據(jù)量為si。

此外，通過對歷史AR 用戶識別任務(wù)數(shù)據(jù)進行分析，可以得到識別任務(wù)結(jié)果重用的相關(guān)信息。本文將相互之間可以重用識別結(jié)果的請求稱為同一類別，從而可以得到κ×n的分類矩陣K，其中，總類別數(shù)為κ，矩陣元素取值為：

對于屬于同一類別的識別請求，其識別目標(biāo)往往是相同的，如同一個路口、同一家商店等，顯然這樣的請求屬于且只會屬于一個類別，即：

對于每一個類別，系統(tǒng)會在最早的請求到來時計算一次，之后就可以直接返回緩存結(jié)果?？紤]到每個類別第一次請求的特殊性，本文定義gi為第i類中第一個到達的請求。而數(shù)據(jù)集按照時間先后順序排序，因此，即第i類中使得Kik=1 的k最小者。

2.4 節(jié)點部署

根據(jù)收集到的用戶軌跡信息，需要對邊緣服務(wù)器節(jié)點部署位置進行決策。因為是在現(xiàn)有基站基礎(chǔ)上新增功能，所以擁有候選基站位置集合L={l1，l2，…，lm}，并且可以認為這些基站覆蓋了所有的請求位置，即對于任一請求位置，必定存在一個基站到它的距離小于等于r，也即：

因此，需要決策的就是在各個節(jié)點上分配的計算資源量C={c1，c2，…，cm}（?1≤h≤m，ch∈N，ci=0 表示此處不會部署邊緣計算節(jié)點）。筆者希望在有限的部署代價之內(nèi)盡可能提升用戶體驗，因此考慮了部署開銷與用戶時延。

部署開銷指為每個候選基站要部署特定計算資源量所付出的代價。因為不同的基站位置不同，具體情況也不盡相同，所以用集合D={d1，d2，…，dm}(di＞0)來表示在各基站部署單位計算資源所需代價，其中，dh表示在基站h部署1 個計算資源所需代價。為使部署開銷處于可控范圍內(nèi)，設(shè)定：

其中，R為總部署代價上限。

2.5 總時延優(yōu)化

請求平均時延應(yīng)當(dāng)盡可能地小，以提升用戶體驗。由于請求數(shù)量為常數(shù)，因此等價于讓所有請求的總時延最小，本文將其定義為：

其中，Tu為未命中緩存的總時延，Tc為命中緩存的總時延。

未命中緩存的總時延即K中所有類別第一次計算耗時，因此，要對每個類別i分別計算其第一次請求即gi的時延。當(dāng)緩存未命中時，計算要在被請求的服務(wù)器本地完成，而被請求的服務(wù)器就是距離請求j位置最近的部署了邊緣服務(wù)器的基站，因此，基站序號為。根據(jù)2.2 節(jié)，計算時延和數(shù)據(jù)傳輸時延分別可按照λ·與μs·dist(x，y)計算，如式（6）所示：

命中緩存的總時延為同類別中第一次到達請求之后的請求時延之和，因此，需要計算各類別中所有序號大于gi的請求時延。根據(jù)2.2 節(jié)，命中緩存的時延包括傳輸時延和獲取結(jié)果時延，如式（7）所示：

因此，所有請求總時延為：

本文的優(yōu)化問題描述為問題1：

其中，C1 表示有限的可部署資源，C2 表示每個請求位置附近距離r內(nèi)都存在一個邊緣節(jié)點，從而確保所部署的邊緣節(jié)點可以覆蓋所有的請求位置，C3 表示可部署資源量為非負整數(shù)。

由于優(yōu)化目標(biāo)函數(shù)中的求最小值操作難度較大，因此本文考察原問題中的一種特殊情況，即所有基站均部署邊緣節(jié)點的情況。修改優(yōu)化問題1 的約束條件C3，確保每個基站都有可用的計算資源，如式（10）所示：

在此約束條件下，由2.4 節(jié)所述，基站集合L覆蓋了所有請求，那么根據(jù)式（3），約束條件C2 永遠成立，同樣地，f(i)就變?yōu)榕c自變量C無關(guān)的函數(shù)f(i)=，則優(yōu)化目標(biāo)T變?yōu)椋?/p>

式（11）中唯一與自變量C相關(guān)的就是第1 項，且只需決定cf(i)的取值。令表示基站h所收到的所有第一次請求任務(wù)量之和，F(xiàn)={f(i)|1≤i≤κ}表示所有類別中第一次到達的請求所指向的基站的集合，則對于不在集合F中的基站h確保ch＞0，這樣即得到簡化的優(yōu)化問題，即問題2：

3 中小規(guī)模場景下的時延優(yōu)化算法

針對一個城市，所研究的任務(wù)與位置密切結(jié)合的MAR 應(yīng)用場景往往局限于少數(shù)區(qū)域，如AR 導(dǎo)航可能集中在一些特定的復(fù)雜路口或繁華的中心地帶，AR 商場購物可能集中在購物中心區(qū)域。在一個請求量較為稀疏的較小范圍內(nèi)，基站數(shù)量m與最大代價R都不至于太大，此時可以基于動態(tài)規(guī)劃構(gòu)造偽多項式算法求得問題2 的最優(yōu)解，從而得到與問題1 最優(yōu)解接近的解。

3.1 問題簡化

根據(jù)上文分析，在從問題1 到問題2 的轉(zhuǎn)化過程中，可以直接使所有基站都至少部署最低的計算資源量以簡化優(yōu)化目標(biāo)函數(shù)，但需要對集合F中的基站進行優(yōu)化，所以，直接使不在F中的所有基站計算資源量為最低即可，即令h?F的ch為大于0 的最小整數(shù)1，此處令：

設(shè)|F|為F集合中元素的個數(shù)，那么求解問題2 就只需要確定ch(h∈F)的值，上文定義了F={f(i)|1≤i≤κ}，但由于可能會有多個類別的第一次請求訪問同一個基站，因此對F中元素按照基站序號從小到大排序，得到F={F1，F(xiàn)2，…，F(xiàn)|F|}，F(xiàn)1＜F2＜…＜F|F|，那么cFu就是基站Fu所具有的計算資源量，WFu就是基站Fu接收到的所有第一次請求的任務(wù)總量。

由于分配給不在F中的每個基站的計算資源量均為1，因此對于F中基站的計算資源分配問題總的可付出代價就要從R中去除，因此，新的可付出代價為

由此得到一個只需對ch(h∈F)進行決策的新問題，即問題3：

其中，WFu＞0，dFu＞0，R′＞0，?1≤u≤|F|。

3.2 最優(yōu)子結(jié)構(gòu)

觀察發(fā)現(xiàn)問題3 具有最優(yōu)子結(jié)構(gòu)，即解為(cF1，cF2，…，cF|F|)，資源總量為R′的問題3 的最優(yōu)解可以由解為(cF1，cF2，…，cFk)(1≤k≤|F|)資源總量為r(1≤r≤R′)的規(guī)模更小的問題3 的最優(yōu)解構(gòu)造得到。本文用(|F|+1)×(R′+1)二維數(shù)組a保存子問題的最優(yōu)解（ai，j表示解為(cF1，cF2，…，cFi)、資源總量為j的子問題的最優(yōu)解），用二維數(shù)組p保存子問題的最優(yōu)解的值（pi，j表示ai，j相應(yīng)的最優(yōu)解的值）。

對于ai，j與pi，j的子問題，可以將其理解為：有i個基站分配總量為j的資源，一個基站的資源量越大則其服務(wù)時延越低，本文目標(biāo)是使它們的總服務(wù)時延最低，解(cF1，cF2，…，cFi)即為各基站資源的部署量?；谥挥校╥-1）個基站的子問題，可以通過遍歷所有可能的新加基站（即基站i）的數(shù)量，得到有i個基站的問題的最優(yōu)解，因此，有：

需要注意的是，所有的索引都從0 開始計，p0，·與p·，0、a0，·與a·，0為特殊情況。此外，還約定當(dāng)分母k=0時

對于使式（18）取得最小值的k，問題3 的最優(yōu)解可以直接通過在ai-1，j-k之后增加cj=k得到：

3.3 算法構(gòu)造

問題3 與普通非線性背包問題的不同之處在于，問題中除了決策變量以外，參數(shù)均為實數(shù)而非整數(shù)。但是對于中小規(guī)模的輸入，可以通過將dFi與R′同乘以10、100 或1 000 再四舍五入取整得到一定精度的近似解。此過程不涉及算法核心問題，因此，算法設(shè)計中默認前述參數(shù)是已經(jīng)通過相關(guān)操作取整過的參數(shù)。

本文通過設(shè)計動態(tài)規(guī)劃算法IDM（Integral Delay Minimization）對上述問題進行求解，如算法1 所示。首先對初始的特殊情況進行設(shè)置。對于m=0 的子問題，問題3 中F集合為空，解為空集，因此，目標(biāo)函數(shù)值為0；對于m＞0 且R′=0 的子問題，目標(biāo)函數(shù)中每一項分母均為0，即此基站資源量為0，那么服務(wù)時延為∞，故值初始化為∞。然后按式（18）和式（19）所示的狀態(tài)轉(zhuǎn)移方程從小到大計算p的值，得到|F|個解和資源量為R′的問題3 最優(yōu)解。最后對不在F中基站的賦值，得到問題1 的解。

算法1IDM

3.4 時間復(fù)雜度分析

IDM 算法的時間復(fù)雜度分析如下：計算gi復(fù)雜度為O(κn)，計算Wh復(fù)雜度為O(κm)，構(gòu)造集合F復(fù)雜度為O(κm)，對集合F進行排序復(fù)雜度為O(κlbκ)，動態(tài)規(guī)劃最大次數(shù)為。因此，IDM 算法總時間復(fù)雜度為由于IDM 是一個偽多項式算法，因此該算法更適合在中小規(guī)模場景下求解。

4 大規(guī)模場景下的啟發(fā)式算法

在一個用戶終端密集、基站分布多的城市人流密集區(qū)域，數(shù)據(jù)集中的請求數(shù)量往往非常多，而基站數(shù)量也非常多，因此，總部署代價上限通常較高，這就導(dǎo)致動態(tài)規(guī)劃算法會有很高的時間復(fù)雜度而不再適用，因此，本文研究大規(guī)模場景下的啟發(fā)式算法。

4.1 大規(guī)模場景分析

大規(guī)模場景有如下特征：

1）請求量大。小規(guī)模場景中請求稀疏，相應(yīng)類別較少，而大規(guī)模場景中會存在很多用戶在很多位置發(fā)起請求的情況，這也導(dǎo)致其具有請求類別多的特征。當(dāng)請求數(shù)n和類別數(shù)κ較大時，算法1 中為動態(tài)規(guī)劃生成輔助變量過程中的時間復(fù)雜度O(κn+κm+κlbκ)就變得不可忽視。

2）基站密集，代價上限高。在小規(guī)模場景下，由于請求不多，因此稀疏部署的基站足以滿足用戶需求。在大規(guī)模請求場景中，為保證用戶體驗的流暢性，往往會部署很多基站，而該區(qū)域總可用代價也會很高。IDM 算法中動態(tài)規(guī)劃的時間復(fù)雜度為這在基站數(shù)m和可用代價R很大時是不可接受的。

因此，在大規(guī)模場景下，應(yīng)選擇在用戶平均時延目標(biāo)不降低太多的情況下時間復(fù)雜度較低的算法。經(jīng)過觀察可以發(fā)現(xiàn)，對于本文所研究的服務(wù)與位置緊密關(guān)聯(lián)的AR 識別任務(wù)，屬于同一類別的任務(wù)往往是集中分布的，同類的任務(wù)集中在一個很小的區(qū)域中，而不同類的任務(wù)散布在整個區(qū)域中。IDM 算法在尋找每個類別執(zhí)行計算任務(wù)的基站時，對所有基站都進行了遍歷，但實際上距離一個類別較遠的基站基本上是不可能執(zhí)行該類別的計算任務(wù)的，尤其是在大規(guī)模場景中，基站分布較為密集，一個類別的計算任務(wù)必然在其附近的基站執(zhí)行。

根據(jù)以上分析可知，在尋找每個類別執(zhí)行計算任務(wù)的基站時，并不需要遍歷所有基站。同樣地，在為每個基站決定其計算資源部署情況時，也并不需要遍歷所有請求。那么，就可以把所有請求與基站按照空間分布進行切分，從而得到多個規(guī)模較小的子問題，對于每個子問題使用IDM 算法求解后，再得到最終的解。

4.2 算法設(shè)計

考慮到子問題中的基站與請求應(yīng)在空間上聚集在一起，因此本文通過聚類對原問題進行切分。因為數(shù)據(jù)規(guī)模較大且對聚類密度和層次沒有特殊需求，所以本文選擇具有線性時間復(fù)雜度的K-Means聚類算法。

通過構(gòu)造啟發(fā)式算法LDM（Large-scale Delay Minimization）來求解大規(guī)模場景下的問題，如算法2所示。對各個類別的請求計算它們的中心點，即同一類別所有請求位置坐標(biāo)的均值，得到中心點集合A。將中心點集合A與基站集合L取并集并使用K-Means 聚類，得到具有φ個簇的聚類結(jié)果集合F，其中每個簇Fi包括該簇的請求集合與該簇的基站集合。據(jù)此，可以生成子問題的各基站位置集合Li′、各基站單位部署開銷Di′、請求數(shù)據(jù)集Ui′中的請求位置集合Xi′、請求數(shù)據(jù)量集合Si′和請求分類矩陣Ki′。對于子問題的總部署代價上限Ri′，直接按照當(dāng)前簇的基站數(shù)量占全局基站數(shù)量的比例來分配，Ri′=。至此，(Li′，Di′，Ui′，Ki′，Ri′)就形成了一個完整的子問題。

算法2LDM

上文2.4 節(jié)中提到，在解原問題的時候有一個最基礎(chǔ)的假設(shè)——所有基站應(yīng)該能夠覆蓋所有的請求位置。如果切分得到的子問題不能滿足這一條件，那么就無法使用IDM 算法對子問題進行求解。因此，在得到子問題集合P之后，對各子問題進行檢查，若存在基站不能覆蓋所有請求的子問題，那么就對那些沒有服務(wù)基站的請求進行搜索，查找距離它們最近的基站，將最近的基站所在子問題與當(dāng)前子問題合并成為一個子問題。若被合并的子問題也不能滿足覆蓋條件，則遞歸地合并，直到滿足覆蓋條件為止。

經(jīng)過覆蓋條件檢查與合并，對新的子問題可以分別使用IDM 算法求解。由于子問題之間相互獨立，因此可以并行化完成求解這一過程，從而進一步加快本文算法的運行速度。子問題的解Ci就是子問題Pi內(nèi)部對它們基站資源分配量的賦值，經(jīng)合并即為最終對全局基站的賦值C。

4.3 時間復(fù)雜度分析

假設(shè)大規(guī)模場景中基站、請求都是均勻分布的，那么平均每個子問題的基站數(shù)量、請求數(shù)量都是原問題的。據(jù)此分析如下：計算各類別中心點集合為O(n)，K-Means 聚類的時間復(fù)雜度為O(κ+m)，構(gòu)造子問題復(fù)雜度為O(n+m)。檢查子問題覆蓋條件整體時間復(fù)雜度為O(ξn)，其中，ξ為較小的常數(shù)。合并不滿足覆蓋條件的子問題為常數(shù)O(1)。求解單個子問題時間復(fù)雜度為則φ個子問題總的時間復(fù)雜度為綜上分析，順序執(zhí)行LDM 的時間復(fù)雜度為，相比于IDM 的O(κn+本文通過線性時間復(fù)雜度的操作，使得IDM 的輔助參數(shù)計算部分效率提高了φ倍，動態(tài)規(guī)劃部分效率提高了φ2倍以上。

5 實驗與結(jié)果分析

本節(jié)分別模擬中小規(guī)模場景和大規(guī)模場景，對IDM 算法和LDM 算法進行實驗分析，并使用直接均分和數(shù)值優(yōu)化兩種方法作為對比。直接均分法令所有m個基站chdh=，把總代價上限均分為m份，這樣基站h的計算資源量為因為解必須為整數(shù)，所以此處進行了下取整。數(shù)值優(yōu)化法通過數(shù)值方法迭代逼近原問題的最優(yōu)解，但是無法得到整數(shù)解，可以一定程度上代表此問題的最優(yōu)解。

5.1 實驗設(shè)置

本節(jié)從研究場景和緩存模型兩方面介紹模擬實驗中的背景設(shè)置和相關(guān)參數(shù)。

5.1.1 研究場景

本文研究500 m×500 m 的矩形區(qū)域，以坐標(biāo)（0，0）為左下角，以坐標(biāo)（500，500）為右上角。該區(qū)域中已部署基站，每個基站的有效服務(wù)半徑為100 m。在區(qū)域中隨機產(chǎn)生AR 識別任務(wù)請求，任務(wù)可重用者為同一類別。因為同一類別往往產(chǎn)生位置相近，所以同一類別的請求坐標(biāo)在區(qū)域中呈現(xiàn)標(biāo)準(zhǔn)差較小的高斯分布，這樣同一類的請求就會在高斯分布的中心點附近集中分布，符合實際場景。此處設(shè)置標(biāo)準(zhǔn)差σ=5。不同類別的中心點在區(qū)域中均勻分布?？紤]到實際場景中交付云計算的數(shù)據(jù)往往是圖像，因此，設(shè)置隨機生成的請求數(shù)據(jù)量范圍為［1 MB，10 MB］，以表示圖像的大小。在3.3 節(jié)IDM 算法設(shè)計中提到，在執(zhí)行IDM 算法之前應(yīng)當(dāng)對基站部署單位計算資源的開銷進行四舍五入取整，因此，本文設(shè)置每個基站部署1 個計算資源的開銷為整數(shù)，在［1，10］之間均勻分布。

5.1.2 緩存模型

對于本文的緩存模型：設(shè)置計算時延參數(shù)λ=500，即在具有1 個計算資源的邊緣服務(wù)器上計算1 MB的數(shù)據(jù)需要500 ms；設(shè)置傳輸時延參數(shù)μ=1，即在距離基站1 m 的位置向基站傳輸1 MB 的數(shù)據(jù)耗時為1 ms；設(shè)置緩存命中后獲取結(jié)果參數(shù)η=3，即當(dāng)請求數(shù)據(jù)的計算結(jié)果已在緩存中時，基站從收到數(shù)據(jù)，到用戶獲取到計算結(jié)果耗時為3 ms。

5.2 中小規(guī)模場景下的實驗結(jié)果

本節(jié)按照中小規(guī)模的場景對IDM 算法進行實驗測試。在此場景下，基站足以覆蓋研究區(qū)域的大部分地區(qū)，但是較為稀疏，因此，設(shè)置基站數(shù)量為30 個且在研究區(qū)域中均勻分布。由于場景中請求不會太密集，因此設(shè)置請求數(shù)量為500 個。此外，由于各個類別的請求數(shù)量往往不相同，但單個類別的請求不會太多，因此設(shè)置每個類別的請求數(shù)量在［1，10］之間均勻分布。部署的總代價上限為500。本文將以此為基礎(chǔ)，改變一些變量觀察算法性能。

首先研究請求數(shù)量對于平均時延的影響，如圖3所示。當(dāng)請求數(shù)量較少時，請求可能集中地被少數(shù)基站處理，因此，直接均分會使很多不需要執(zhí)行任務(wù)的基站分配到較多的資源，導(dǎo)致需要計算的基站資源減少，從而增加時延。之后隨著請求數(shù)量提升，請求分布更趨均勻，基站的任務(wù)分配也更均衡，所以，時延會有下降趨勢。IDM 算法的平均時延始終與數(shù)值最優(yōu)的平均時延非常相近，保持在常數(shù)級的差別，由此可以看出IDM 算法對最優(yōu)的逼近效果較好，對于請求數(shù)量的變化表現(xiàn)也很穩(wěn)定。

圖3 中小規(guī)模場景下請求數(shù)量對平均時延的影響Fig.3 Influence of number of requests on average delay under small and medium scale scenarios

在部署計算資源過程中，總代價上限會對整體系統(tǒng)性能造成較大影響。如圖4 所示，隨著總代價上限的提升，3 種方法的平均時延均有所下降，而且不同部署策略之間的差異也會不斷減小。這是因為當(dāng)總代價上限提升時，各基站的計算資源逐漸充裕，由此部署策略對于總時延的影響也會減弱。可以看出，IDM 算法從最開始的與數(shù)值最優(yōu)略有差距，直到總代價上限為900 時差距幾乎消失，整個過程中兩者的差距始終很小。

圖4 中小規(guī)模場景下總代價上限對平均時延的影響Fig.4 Influence of limit of total cost on average delay under small and medium scale scenarios

5.3 大規(guī)模場景下的實驗結(jié)果

本節(jié)對大規(guī)模場景進行模擬，測試LDM 算法的時延優(yōu)化能力和執(zhí)行時間。在1 000 m×1 000 m 的矩形區(qū)域內(nèi)進行研究。大規(guī)模場景中基站往往較為密集，所以將基站數(shù)量增加到了300 個，是中小規(guī)模場景的10 倍，仍然均勻分布在研究區(qū)域中。大規(guī)模場景中請求數(shù)量也會很多，因此，設(shè)置請求數(shù)量為5 000 個。請求增多會帶來類別的增加，但是每個類別中請求的數(shù)量往往不會有太多變化，因此，仍然設(shè)置每個類別的請求數(shù)量在［1，10］之間均勻分布。由于請求數(shù)很多，部署資源時的總代價上限也隨之提升，本文設(shè)置為5 000。此外，LDM 算法本身有一個超參數(shù)φ用于調(diào)節(jié)子問題數(shù)量，設(shè)置為10。本文將以此為基礎(chǔ)，變化一些參數(shù)觀察算法性能。

考慮到請求數(shù)量是大規(guī)模場景中最重要的影響因素，因此本文研究在請求數(shù)量達到2 000 以上的情況下，隨著請求數(shù)量增加各部署算法平均時延的變化情況，如圖5 所示?？梢钥闯觯褐苯泳址ǖ钠骄鶗r延上升極為緩慢，基本不變；LDM 算法、IDM 算法與數(shù)值最優(yōu)的平均時延都在緩慢上升，增長也越來越緩慢；當(dāng)請求數(shù)量越來越多時，LDM 算法與數(shù)值最優(yōu)的差距越來越小，不斷逼近；在整個過程中，LDM 算法的平均時延都與數(shù)值最優(yōu)相差不多。由此可見，LDM 算法更適用于存在大量請求的環(huán)境。

圖5 大規(guī)模場景下請求數(shù)量對平均時延的影響Fig.5 Influence of number of requests on average delay under large scale scenarios

LDM 算法雖然平均時延略高于IDM 算法，但是算法運行時間遠低于IDM 算法。在大規(guī)模場景下，IDM 算法處理5 000 個請求的平均時延為1 852 ms，運行時間為384 s，而LDM 算法完成同樣的任務(wù)平均時延為1 696 ms，運行算法卻只需7 s，其速度是IDM 算法的54 倍，而平均時延卻只增加了9%，這無疑是值得的。如圖6 所示：隨著請求數(shù)量的增加，IDM 算法運行時間顯著增加，而LDM 算法的運行時間卻始終保持在非常低的水平。由此可見，LDM 算法對于大規(guī)模密集場景犧牲了少量的平均時延優(yōu)化效果，卻帶來了大幅的運行時間縮減。

圖6 大規(guī)模場景下請求數(shù)量對運行時間的影響Fig.6 Influence of number of requests on running time under large scale scenarios

6 結(jié)束語

本文以邊緣計算為背景，研究基于冗余任務(wù)消減的AR 性能優(yōu)化方法，針對AR 任務(wù)的冗余性，設(shè)計冗余消減的系統(tǒng)結(jié)構(gòu)，包括節(jié)點本地緩存生成與管理、全局緩存同步等。以現(xiàn)有緩存系統(tǒng)為基礎(chǔ)，對如何為基站部署邊緣服務(wù)器的計算資源以最優(yōu)化平均用戶時延的問題進行建模，并借助動態(tài)規(guī)劃的思想設(shè)計求解整數(shù)問題的IDM 算法。中小規(guī)模場景下的實驗結(jié)果表明，IDM 的平均時延只比實數(shù)最優(yōu)解增加5.85%。此外，對大規(guī)模場景進行分析，并借助分而治之的思想，使用K-Means 聚類將原問題切分成多個子問題用LDM 進行分別求解，以加快算法運行速度。實驗結(jié)果表明，相比于IDM 算法，LDM 算法在平均時延只增加9.20%的情況下，運行時間下降了98.15%。下一步將以更準(zhǔn)確的真實場景建模和online 任務(wù)調(diào)度為出發(fā)點對本文算法進行優(yōu)化。