趙徐炎，崔允賀*，蔣朝惠，錢 清，申國偉，郭 春，李顯超

（1.貴州大學 計算機科學與技術學院，貴陽 550025；2.文本計算與認知智能教育部工程研究中心（貴州大學），貴陽 550025；3.公共大數(shù)據(jù)國家重點實驗室（貴州大學），貴陽 550025；4.貴州財經(jīng)大學 信息學院，貴陽 550025；5.貴州翔明科技有限責任公司，貴陽 550000）

0 引言

傳統(tǒng)的云計算架構無法滿足物聯(lián)網(wǎng)等新型網(wǎng)絡對時延及隱私性的新要求［1-4］。比如，云計算中心全局性、長周期的大數(shù)據(jù)處理與分析特點難以應對局部實時、短期交互的終端數(shù)據(jù)處理，且遠離終端的云中心增加了數(shù)據(jù)傳輸量，給核心網(wǎng)帶來了巨大壓力。在這種情況下，邊緣計算應運而生。

邊緣計算在網(wǎng)絡邊緣進行計算［5-6］，是一種新型的計算架構。邊緣計算最早可追溯至內(nèi)容分發(fā)網(wǎng)絡中功能緩存的概念，邊緣指從數(shù)據(jù)源到云計算中心路徑之間的任意計算資源。邊緣計算需要將用戶設備上執(zhí)行的任務卸載到邊緣計算節(jié)點上處理，計算卸載的性能受邊緣計算節(jié)點的位置影響，合適的邊緣計算節(jié)點部署策略能有效降低系統(tǒng)時延，減少計算數(shù)據(jù)丟包［7-8］。因此，本文針對邊緣計算節(jié)點的部署問題設計了一種基于重合支配的邊緣計算節(jié)點部署算法。

邊緣計算節(jié)點部署問題是指如何從某區(qū)域備選位置中選擇邊緣計算節(jié)點放置位置，屬于典型的NP 難問題。在邊緣計算環(huán)境中，邊緣計算節(jié)點是分布式放置的。當它受到系統(tǒng)異常、硬件故障、網(wǎng)絡攻擊等事件影響而無法提供正常的邊緣服務時，如果邊緣計算節(jié)點的服務范圍沒有被其他計算節(jié)點覆蓋，邊緣計算節(jié)點將無法為終端用戶提供正常服務。特別是當邊緣計算節(jié)點運行時延敏感型任務時，這一問題將在用戶密集的地區(qū)造成災難級影響。理想的情況是在每個邊緣節(jié)點部署計算節(jié)點，以此提高服務的魯棒性及用戶服務質(zhì)量（Quality of Service，QoS）；但這是不切實際的，因為計算節(jié)點的部署預算有限。用戶的服務體驗要求越高、計算需求越大，邊緣計算節(jié)點的數(shù)量就越大，這將導致更多的人工維護成本和管理成本。

邊緣計算節(jié)點部署方案旨在選擇合適的位置放置邊緣計算節(jié)點，是典型的多目標優(yōu)化問題，按照優(yōu)化目標的不同可分為兩類：一類是在保證接入時延等服務質(zhì)量（QoS）約束的同時最小化邊緣計算節(jié)點部署成本［9］。Wang 等［10］將邊緣服務器部署問題建模為多目標約束優(yōu)化問題，在平衡邊緣服務器的工作負載的同時最小化移動用戶與邊緣服務器之間的訪問時延；Liu 等［11］將該問題建模為最大加權二部圖匹配問題，從而最小化平均時延和平均帶寬資源占用；Lee 等［12］將邊緣計算節(jié)點放置問題建模為有能力的聚類問題，確定給定約束下每個聚類的最小聚類數(shù)量和相關元素，有效降低了時延和工作負載約束下的最小邊緣服務器數(shù)量；Cao 等［13］考慮邊緣服務器的異構性和基站響應時間的公平性，結合用戶移動的動態(tài)特性，優(yōu)化基站群和單個基站的預期響應時間。另一類是在工作負載不確定的情況下最大化邊緣服務魯棒性。Wang 等［14］提出了一種動態(tài)規(guī)劃算法，在給定時延等約束條件下找出節(jié)點的最大覆蓋面積；Lu 等［15］將服務器放置問題表述為魯棒最大最小優(yōu)化問題，揭示其目標函數(shù)是單調(diào)子模，證明了問題約束等價于P無關的系統(tǒng)約束，提出最大化預期總體工作負載的服務器放置策略；Cui 等［16］面向魯棒性的邊緣服務器位置問題進行建模，用邊緣服務器的覆蓋重疊面積衡量系統(tǒng)的魯棒性，最大化邊緣服務器網(wǎng)絡的總體覆蓋重疊，使用重疊面積進行服務器位置部署，取得了較好的部署效果。然而，在使用該方法時，雖然位于部署區(qū)域中心的用戶服務體驗質(zhì)量會大幅提升，但部署區(qū)域邊緣位置的用戶訪問時延極高，犧牲了邊緣位置用戶的服務體驗；同時，當用戶呈分散分布時，小部分地區(qū)用戶服務體驗質(zhì)量較高，但大多數(shù)用戶的訪問時延會很高，服務體驗質(zhì)量極差。

為解決上述問題，在邊緣服務的時延等QoS 因素的約束下，同時最大化邊緣服務的魯棒性并使邊緣計算節(jié)點部署成本最小，本文提出了基于重合支配的邊緣計算節(jié)點放置算法CHAIN（edge server plaCement algoritHm based on overlApping domINation）。本文的主要工作如下：

1）提出了邊緣計算重合度及重合支配、重合支配節(jié)點、重合支配集合的概念，以衡量邊緣服務魯棒性。

2）基于重合度、重合支配、重合支配節(jié)點、重合支配集合的概念，設計了一種基于重合支配的邊緣計算節(jié)點放置算法，以最大化邊緣服務的魯棒性、最小化邊緣計算部署成本。

1 問題描述

本章給出網(wǎng)絡模型并描述邊緣計算節(jié)點部署需要解決的問題。邊緣計算的體系結構包括遠程云、網(wǎng)絡、邊緣節(jié)點和信號接入點（Access Point，AP）。邊緣計算節(jié)點通常部署在AP 附近，便于管理，同時避免多余的傳輸時延，與AP 共存組成邊緣節(jié)點。一個邊緣節(jié)點和多個AP 組成一個簇，在簇中決定部署邊緣計算節(jié)點的位置，即不同的接入點。簇內(nèi)用戶通過最近的AP 連接到邊緣節(jié)點，使用邊緣節(jié)點進行服務。邊緣節(jié)點可以選擇自己提供服務，也可以選擇將計算任務上傳到云端處理。邊緣計算節(jié)點是互聯(lián)的，當其中一個出現(xiàn)故障時可以卸載當前計算任務到相鄰的邊緣計算節(jié)點進行任務處理。因此，本文在部署邊緣計算節(jié)點時，需要從很多待選的部署位置中選擇合適的邊緣計算節(jié)點部署位置，以降低服務響應時延、提高服務魯棒性，同時降低部署成本。

1.1 網(wǎng)絡模型

邊緣計算節(jié)點的部署環(huán)境用連通的無向圖G=(V，E)表示，其中：V為接入基站集合；E為基站之間連接鏈路集合。當且僅當兩個基站u和v能通過通信鏈路連接時，存在一條邊(u，v) ∈E，u∈V，v∈V。n=|V|表示基站數(shù)，接入基站位置都可以選擇作為邊緣計算節(jié)點位置，即邊緣計算節(jié)點和基站共存，以避免額外的時延和成本。假設每個接入基站有相同的發(fā)送時延，任務在邊緣計算節(jié)點執(zhí)行和等待時間為最小常數(shù)，忽略不計。同時，因為兩個基站的時延與距離成正比，表示為d(u，v)，本文使用最大距離H表示最大傳輸時延。

1.2 問題定義

邊緣計算節(jié)點部署在基站附近，可視為邊緣計算節(jié)點與基站共存。因此邊緣計算節(jié)點通過基站實現(xiàn)與用戶之間的通信，可進一步簡化為用戶和無線基站之間的無線通信。下文所述邊緣計算節(jié)點覆蓋區(qū)域指該邊緣計算節(jié)點部署位置的基站的覆蓋區(qū)域。每個基站都有一定的圓形覆蓋區(qū)域，即不同的邊緣計算節(jié)點覆蓋區(qū)域通常會相交，產(chǎn)生覆蓋重疊區(qū)域。當該區(qū)域主要計算節(jié)點出現(xiàn)故障時，該區(qū)域內(nèi)的用戶服務將會被其他邊緣計算節(jié)點接管。兩個邊緣計算節(jié)點相交的覆蓋重疊區(qū)域越大，覆蓋的共同用戶越多，當其中一個邊緣計算節(jié)點發(fā)生故障時，另一個邊緣計算節(jié)點可接收的用戶服務也就越多，該區(qū)域用戶的網(wǎng)絡服務魯棒性就越強。

本文定義二進制變量Xi（i∈V）表示是否在基站i附近部署邊緣計算節(jié)點：Xi=1 表示在基站i部署邊緣計算節(jié)點；Xi=0 表示不在基站i部署邊緣計算節(jié)點。同時本文定義變量Yi，j表示基站i的任務是否卸載到計算節(jié)點j：Yi，j=0 表示任務在本地執(zhí)行；Yi，j=1 表示任務在計算節(jié)點j上計算。本文定義矩陣r(i，i')表示基站i和基站i'共同覆蓋用戶數(shù)，還定義了變量Zj，k表示邊緣計算節(jié)點j和云端k的傳輸時延。

為了最小化邊緣節(jié)點部署成本，即最小化邊緣計算節(jié)點數(shù)量，本文定義如下的目標函數(shù)：

其中：約束（2）表示時延約束，保證每個基站與對應計算節(jié)點之間的訪問時延不超過最大時延，d(i，j)表示節(jié)點i和節(jié)點j之間的時延，H為最大時延；約束（3）表示邊緣服務魯棒約束，考慮邊緣計算節(jié)點共同覆蓋用戶數(shù)和邊緣計算節(jié)點部署成本的平衡，保證用戶覆蓋程度高于可接受的最小限制，φ表示最小共同覆蓋用戶數(shù)；約束（4）表示邊緣計算節(jié)點與云端的傳輸時延。本文重點考慮邊緣端計算節(jié)點的放置，對云端計算卸載等任務的處理不作優(yōu)化，因此本文假設任務上傳云端計算并返回的時延是一個常數(shù)，在具體實驗時，不考慮上傳云端服務的時延影響。需要注意的是，本文考慮的是同構邊緣計算節(jié)點的部署問題，因此邊緣計算節(jié)點對用戶請求服務進行的計算及響應在本文邊緣計算節(jié)點放置時將視為同樣的處理過程，不影響本文的邊緣計算節(jié)點放置結果。

2 本文算法

CHAIN 需要在邊緣服務的魯棒性和時延等QoS 因素的約束下，在保證網(wǎng)絡服務質(zhì)量的同時最小化邊緣計算節(jié)點的部署成本。上述問題類似最小支配集問題，但存在一定差異。不考慮邊緣服務的魯棒性時，假設網(wǎng)絡的每一跳的訪問時延相同，訪問時延約束可以轉(zhuǎn)換為距離約束，邊緣計算節(jié)點的放置問題可以轉(zhuǎn)換為計算給定圖的最小支配集問題。但是當加入網(wǎng)絡的魯棒性約束時，需要考慮如何衡量網(wǎng)絡的魯棒性以及如何定義新的支配集合。為此，本文提出了重合支配的概念。

2.1 重合支配

為更好地衡量系統(tǒng)服務的魯棒性，CHAIN 將重合度定義為兩個節(jié)點之間共同覆蓋用戶數(shù)。進一步，CHAIN 將重合支配定義為當兩個節(jié)點之間重合度達到一定程度時，支配節(jié)點可以滿足對鄰接節(jié)點的支配條件。由重合支配節(jié)點組成的集合稱為重合支配集合，該集合是在可放置邊緣計算節(jié)點的待選位置中滿足重合支配條件的最小數(shù)量的支配集合。

如圖1 所示，基站s是當前集合支配點，基站a、b和c在系統(tǒng)允許的最大時延內(nèi)與基站s交互，是它擬支配的鄰接節(jié)點?？紤]基站之間的重合度和集群平均重合度之間的關系，滿足重合支配條件則稱為重合支配。

圖1 基站支配集合Fig.1 Base station dominating set

在圖1 中，基站s和基站b之間重合度r(s，b)=19，而整個集群平均重合度約為8.3，則基站s重合支配基站b。重合度、重合支配、重合支配節(jié)點、重合支配集合具體定義如下：

定義1 重合度。給定一個用戶接入矩陣A，a(ui，bj)表示用戶ui接入節(jié)點bj的傳輸時延，則節(jié)點bi和bj之間的重合度表示為：

定義2 重合支配。給定候選基站集合U，支配節(jié)點s∈S，對于任意節(jié)點v(v∈U)，如果滿足條件：

則稱支配節(jié)點s重合支配節(jié)點v，表示為η(s，v)。

定義3 重合支配節(jié)點。給定一個集合U，?s，v∈U，如果節(jié)點s和節(jié)點v滿足η(s，v)，則稱s為重合支配節(jié)點。

定義4 重合支配集合。給定一個集合U，存在最小數(shù)量的集合S，S?U。?s∈S，?v∈U-S，如果節(jié)點s和節(jié)點v滿足η(s，v)，則稱S為重合支配集合。

2.2 算法描述

給定n個基站B={b1，b2，…，bn}和m個用戶U={u1，u2，…，um}，每個基站與它的鄰近基站可以互相通信，使用式（7）計算相鄰兩個基站bi和bj間的訪問時延dij：

其中，bi、bj的下標表示基站的坐標，i=(i1，i2)，j=(j1，j2)。

考慮時延約束和基站的度約束，計算基站的鄰接矩陣N={Ni|i=1，2，…，n}，Ni表示基站bi的鄰接基站集合。CHAIN 用式（8）、（9）計算基站-用戶矩陣A，Aik表示基站bi是否覆蓋用戶uk：當Aik=1 時，表示用戶uk在基站bi的通信范圍內(nèi)，可訪問該基站服務；當Aik=0 時，表示用戶uk不在基站bi的通信范圍內(nèi)，基站無法為用戶uk提供服務。

其中，H表示最大時延約束。

為計算邊緣節(jié)點的最優(yōu)位置，CHAIN 初始化未覆蓋節(jié)點集合W=B，已覆蓋節(jié)點集合C=?以及邊緣計算節(jié)點位置D=?，并用式（10）計算基站bi和bj共同覆蓋用戶矩陣COV。

用式（11）、（12）計算支配節(jié)點的鄰接集合CLU：

其中，參數(shù)φ表示魯棒約束。當基站bj與當前支配節(jié)點滿足重合支配條件時，將基站bj加入當前支配節(jié)點的鄰接集合，更新集合W和C。最后把滿足重合支配條件的支配節(jié)點選入邊緣計算節(jié)點位置D。具體步驟如算法1 所示：

算法1 CHAIN。

輸入 服務接入點無向連通圖G=(V，E)；

輸出 邊緣計算節(jié)點位置D。

如算法1 所示，CHAIN 首先對未覆蓋節(jié)點集合按節(jié)點覆蓋用戶數(shù)進行從大到小排序，優(yōu)先考慮用戶數(shù)較多的基站。在第5）～14）行的循環(huán)中，CHAIN 計算當前節(jié)點與未覆蓋節(jié)點間的時延，篩選滿足最大時延約束的節(jié)點，把滿足條件的節(jié)點視為當前節(jié)點的鄰接節(jié)點。稱當前節(jié)點為支配節(jié)點，能支配鄰接節(jié)點。在所有未覆蓋節(jié)點中，計算它支配的鄰接節(jié)點的數(shù)量，作為當前支配節(jié)點的度數(shù)。選擇度數(shù)最大的節(jié)點作為現(xiàn)階段的支配節(jié)點，即在未支配集合中選擇在時延允許范圍內(nèi)度數(shù)最大的節(jié)點作為部署邊緣計算節(jié)點的位置。然后，在第16）～20）行的循環(huán)中，CHAIN 從現(xiàn)階段支配節(jié)點的鄰接節(jié)點中，根據(jù)重合支配定義選擇其支配的節(jié)點集合，構建重合支配集合S。最后，CHAIN 將支配節(jié)點s加入邊緣計算節(jié)點位置集合D，從未覆蓋節(jié)點中刪除重合支配集合S，把集合S加入已覆蓋集合C，經(jīng)過多次篩選，輸出邊緣計算節(jié)點部署位置集合D。

3 實驗與結果分析

3.1 仿真環(huán)境設置

實驗使用一臺具有Intel Core i5-10400H CPU 2.9 GHz 處理器的主機運行，使用Windows 10 操作系統(tǒng)，仿真實驗基于Python 3.8 版本開發(fā)實現(xiàn)。

無線城域網(wǎng)拓撲圖數(shù)據(jù)通常由政府管理，不對外開放。因此，本文參考相關工作實驗設置［17］，根據(jù)需要生成隨機拓撲為實驗建模真實的無線城域網(wǎng)。由于實際無線城域網(wǎng)建模十分復雜，本文只對基站數(shù)和用戶數(shù)進行控制，為保證算法的通用性，通過在給定區(qū)域隨機撒點的方法放置基站和用戶，避免基站和用戶的放置具有一定規(guī)律可循。本文模擬了一個由n臺基站和90 臺終端設備組成的邊緣計算網(wǎng)絡，這些邊緣計算網(wǎng)絡隨機均勻分布在10 km×10 km 的區(qū)域內(nèi)。每個邊緣計算節(jié)點在rem 的通信范圍內(nèi)與其附近的計算節(jié)點建立拓撲連接。每個用戶將調(diào)用一個隨機服務到它的通信范圍內(nèi)的邊緣計算節(jié)點，如果計算節(jié)點接收到用戶的服務請求，并且已經(jīng)部署了相關服務，那么將響應該請求。在實際情況中，邊緣計算節(jié)點同時響應用戶服務請求的容量有限，本文用Da表示邊緣計算節(jié)點允許接受的最大用戶請求數(shù)。

為了量化CHAIN 的性能，實驗初始階段隨機生成了5 組基站分布數(shù)據(jù)集并保存，分別是個數(shù)為｛60，70，80，90，100｝的基站分布隨機數(shù)據(jù)集。之后使用這5 組基站分布隨機數(shù)據(jù)驗證算法性能。在基站數(shù)確定時，通過改變基站覆蓋半徑為｛200，250，300｝m 驗證算法性能指標；在時延約束變化和節(jié)點度變化的實驗中，選擇基站數(shù)為70 的數(shù)據(jù)集進行實驗，通過改變工作負載o或時延約束t來驗證算法性能。

為綜合評價本文算法，通過改變4 個實驗參數(shù)來模擬不同的邊緣計算節(jié)點部署環(huán)境：1）基站數(shù)量n；2）基站覆蓋半徑re；3）邊緣計算節(jié)點最大工作負載o；4）訪問時延約束t。每個邊緣計算節(jié)點的計算資源和存儲資源有限，本文考慮邊緣計算節(jié)點的最大工作負載，最大化仿真真實場景評估算法性能，具體參數(shù)設置如表1 所示。

表1 實驗參數(shù)設置Tab.1 Experimental parameter setting

3.2 對比實驗

本文通過改變網(wǎng)絡大小、時延約束和邊緣計算節(jié)點工作負載等約束條件，給定一組基站B={b1，b2，…，bn}和一組用戶U={u1，u2，…，um}，比較CHAIN 和兩種代表性方法在最小化部署成本和提升邊緣服務魯棒性的有效性和效率，對比方法為：面向覆蓋的近似方法（簡稱APPROX）［16］和面向基站的隨機方法（簡稱RANDOM）［18］。

APPROX：考慮每個基站及鄰接基站，計算基站終端用戶接管可能性（Possibility of End-user Take-over，PET），根據(jù)PET 對相鄰基站識別和排序，邊緣計算節(jié)點被放置在具有最大PET 的基站附近，選擇總體PET 最大的候選策略放置總共k個邊緣計算節(jié)點，最大化給定服務器數(shù)量的邊緣計算節(jié)點覆蓋范圍。詳細情況見文獻［16］。

RANDOM：考慮每個基站及鄰接基站，每個邊緣計算節(jié)點將隨機放置在滿足約束條件的候選基站附近，直到邊緣計算節(jié)點覆蓋所有基站為止。詳細情況見文獻［18］。

本文使用平均時延、平均魯棒和邊緣計算節(jié)點數(shù)量作為對比實驗的性能指標，平均魯棒使用式（13）進行計算：

其中：S是邊緣計算節(jié)點集合；U是所有候選基站集合。對APPROX 計算平均魯棒時，|S|由給定邊緣計算節(jié)點數(shù)k代替。

3.3 實驗結果

為觀察不同基站數(shù)、覆蓋半徑對部署邊緣節(jié)點性能的影響，本實驗分別設置覆蓋半徑為｛200，250，300｝m，基站數(shù)為｛60，70，80，90，100｝，其中，APPROX 的參數(shù)k取20。

三種算法的系統(tǒng)時延對比如圖2 所示，隨著基站數(shù)的增加，CHAIN 和APPROX 的系統(tǒng)時延變化較小，RANDOM 的系統(tǒng)時延變化較大。在所有實驗結果中，CHAIN 的系統(tǒng)時延最小。CHAIN、APPROX 與RANDOM 的平均時延分別為15.05 ms、30.43 ms、30.18 ms，與APPROX 和RANDOM 相比，CHAIN 的系統(tǒng)時延降低了50.54%與50.13%。原因是CHAIN 使用重合支配的方式在保證魯棒性的同時降低了用戶的訪問時延。而RANDOM 的隨機性使它使用過多非最優(yōu)基站作為支配集合節(jié)點，出現(xiàn)額外的通信開銷和重復計算，導致它的系統(tǒng)時延較高；APPROX 的特點是對于分布不均勻的基站排列，邊緣計算節(jié)點更多地部署在用戶密度較高的位置，而用戶密度較小的位置很少甚至不會部署邊緣計算節(jié)點，導致邊緣基站訪問計算節(jié)點的時延變得極大。

圖2 不同基站數(shù)與覆蓋半徑下的系統(tǒng)時延對比Fig.2 System delay comparison under different base stations and coverage radii

3 種算法的服務魯棒性對比如圖3 所示。CHAIN 具有較高的服務魯棒性。在覆蓋半徑為200 m 時，APPROX 魯棒性整體較高，這是由于該算法犧牲邊緣區(qū)域的用戶服務體驗，使位于中心區(qū)域的用戶服務魯棒性較高，存在服務魯棒溢出、分布不均的極端部署情況；在覆蓋半徑為250 m 時，CHAIN 的服務魯棒性出現(xiàn)先下降再上升的趨勢；而在覆蓋半徑為300 m 時，服務魯棒性整體呈現(xiàn)下降趨勢。這是因為覆蓋半徑影響了邊緣計算節(jié)點容量，覆蓋半徑越大，可服務的用戶數(shù)越多，邊緣計算節(jié)點的容量也就越大。CHAIN 的系統(tǒng)整體魯棒性在一定約束條件下不會變化，但隨著基站可服務用戶數(shù)的增多，邊緣計算節(jié)點容量達到瓶頸，服務魯棒性出現(xiàn)一定程度的降低。覆蓋半徑越大，邊緣計算節(jié)點容量越大，所以覆蓋半徑250 m 的實驗中CHAIN 達到極低點。但隨著基站數(shù)量的增長，CHAIN 自適應地增加了邊緣計算節(jié)點的數(shù)量，服務的魯棒性也隨之增加。在這一過程中，CHAIN 的服務魯棒性總體高于RANDOM 和APPROX，可以有效提升用戶服務體驗。

圖3 不同基站數(shù)與覆蓋半徑下的服務魯棒性對比Fig.3 Service robustness comparison under different base stations and coverage radii

3 種算法的時延方差如圖4 所示。CHAIN 的時延方差遠低于APPROX。在覆蓋半徑為250 m，基站數(shù)為80 時，CHAIN 的用戶訪問時延最大值是24.84 ms，最小值是3.16 ms，平均值為16.46 ms，方差為32.78 ms；而APPROX的用戶訪問時延最大值是49.73 ms，最小值是1.41 ms，平均值為30.23 ms，方差為148.06 ms。與APPROX 相比，CHAIN降低了77.86%的時延方差。主要原因是APPROX 的計算節(jié)點分布不均，在中心區(qū)域大量部署計算節(jié)點。由圖4 可知，CHAIN 解決了APPROX 算法中心區(qū)域和邊緣區(qū)域用戶計算節(jié)點分布不均的問題，有效提升了服務體驗。

圖4 不同基站數(shù)與覆蓋半徑下時延方差對比Fig.4 Delay variance comparison under different base stations and coverage radii

圖5 為3 種算法的計算節(jié)點數(shù)對比。隨著時延約束增大，CHAIN 所需的節(jié)點數(shù)降低。因為隨著時延約束的不斷增加，邊緣計算節(jié)點可服務的用戶數(shù)增多，相應的邊緣計算節(jié)點數(shù)減少；在時延約束相同時，CHAIN 所需的節(jié)點數(shù)低于RANDOM 所需節(jié)點數(shù)，而APPROX 的節(jié)點數(shù)為20。APPROX需要人為設定邊緣計算節(jié)點數(shù)，限制了它的通用性及便利性；隨著節(jié)點度增大，CHAIN 的計算節(jié)點數(shù)降低，且在相同條件下低于RANDOM 的節(jié)點數(shù)；此外，與CHAIN 算法規(guī)律的節(jié)點數(shù)變化趨勢相比，RANDOM 所需節(jié)點數(shù)波動較大。

圖5 計算節(jié)點數(shù)量對比Fig.5 Comparison of number of computing nodes

實驗結果表明，與APPROX 和RANDOM 相比，CHAIN 能大幅降低系統(tǒng)時延，提高服務魯棒性；同時，CHAIN 所需計算節(jié)點數(shù)量較少，能夠降低部署成本。

4 結語

本文研究了邊緣計算節(jié)點部署問題，將它描述為在保證訪問時延和邊緣服務網(wǎng)絡等約束的條件下最小化邊緣計算節(jié)點數(shù)量的問題。本文提出了重合度、重合支配、重合支配節(jié)點及重合支配集合的定義衡量邊緣計算節(jié)點的魯棒性，基于上述定義設計了基于重合支配的邊緣計算節(jié)點放置算法——CHAIN。仿真結果表明，CHAIN 在保證訪問時延的約束下有效提升了邊緣服務的魯棒性。在未來的工作中，將研究其他復雜算法提升邊緣計算節(jié)點工作的魯棒性以及異構邊緣計算節(jié)點放置問題。