基于冗余任務消減的邊緣應用性能優化

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

（1.江蘇方天電力技術有限公司，南京 211102；2.南京大學計算機軟件新技術國家重點實驗室，南京 210023；3.南京大學軟件新技術與產業化協同創新中心，南京 210023）

0 概述

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

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

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

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

1 相關工作

本節介紹計算卸載、移動AR/VR 應用、服務緩存放置和邊緣計算資源管理等方面的相關工作。

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

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

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

在邊緣云中，資源管理對于服務質量和系統效率有著重要作用。目前，學者主要對資源分配和任務調度進行研究，包括均衡網絡節點負載以優化應用性能、動態適應環境變化、基于層次架構的啟發式負載分配算法、最小化總的加權服務響應時間的在線任務分配與調度算法等［12-14］。考慮到直接為基站增加邊緣計算功能可以避免單獨部署邊緣節點的較大開銷，本文研究在可部署代價有限的情況下如何分配可部署的計算資源，從而使用戶時延降到最低。

因為移動增強現實（Mobile AR，MAR）是在現實世界情境下應用的，所以快速準確的物體識別成為能夠將虛擬世界與真實世界互相融合的關鍵環節［15］。現有物體識別方法包括傳統方法［16-18］和基于深度卷積神經網絡的方法［19-20］。訓練深度卷積神經網絡是目前較為流行的方法，但是要達到一定的精度需要不小的計算代價。Chameleon 系統通過多節點協作，在計算資源投入和物體識別精度上取得了很好的權衡［19］。Focus系統通過使用簡單的卷積神經網絡構建近似索引，加快了對數據集的吸收和查詢［20］。本文關注AR 識別請求與其物理位置之間的關系，以緩存的方式對物體識別進行加速。

2 問題描述

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

2.1 基于緩存的冗余消減

2.1.1 節點緩存

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

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

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

2.1.2 全局緩存

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

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

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

2.2 請求時延

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

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

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

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

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

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

2.3 用戶軌跡

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

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

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

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

2.4 節點部署

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

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

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

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

2.5 總時延優化

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

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

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

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

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

本文的優化問題描述為問題1：

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

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

在此約束條件下，由2.4 節所述，基站集合L覆蓋了所有請求，那么根據式（3），約束條件C2 永遠成立，同樣地，f(i)就變為與自變量C無關的函數f(i)=，則優化目標T變為：

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

3 中小規模場景下的時延優化算法

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

3.1 問題簡化

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

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

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

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

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

3.2 最優子結構

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

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

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

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

3.3 算法構造

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

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

算法1IDM

3.4 時間復雜度分析

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

4 大規模場景下的啟發式算法

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

4.1 大規模場景分析

大規模場景有如下特征：

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

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

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

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

4.2 算法設計

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

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

算法2LDM

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

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

4.3 時間復雜度分析

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

5 實驗與結果分析

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

5.1 實驗設置

本節從研究場景和緩存模型兩方面介紹模擬實驗中的背景設置和相關參數。

5.1.1 研究場景

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

5.1.2 緩存模型

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

5.2 中小規模場景下的實驗結果

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

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

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

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

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

5.3 大規模場景下的實驗結果

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

考慮到請求數量是大規模場景中最重要的影響因素，因此本文研究在請求數量達到2 000 以上的情況下，隨著請求數量增加各部署算法平均時延的變化情況，如圖5 所示。可以看出：直接均分法的平均時延上升極為緩慢，基本不變；LDM 算法、IDM 算法與數值最優的平均時延都在緩慢上升，增長也越來越緩慢；當請求數量越來越多時，LDM 算法與數值最優的差距越來越小，不斷逼近；在整個過程中，LDM 算法的平均時延都與數值最優相差不多。由此可見，LDM 算法更適用于存在大量請求的環境。

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

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

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

6 結束語

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