CHAIN：基于重合支配的邊緣計(jì)算節(jié)點(diǎn)放置算法

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

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

0 引言

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

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

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

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

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

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

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

1 問題描述

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

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

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

1.2 問題定義

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

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

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

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

2 本文算法

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

2.1 重合支配

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

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

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

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

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

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

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

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

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

2.2 算法描述

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

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

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

其中，H表示最大時(shí)延約束。

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

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

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

算法1 CHAIN。

輸入 服務(wù)接入點(diǎn)無向連通圖G=(V，E)；

輸出 邊緣計(jì)算節(jié)點(diǎn)位置D。

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

3 實(shí)驗(yàn)與結(jié)果分析

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

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

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

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

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

表1 實(shí)驗(yàn)參數(shù)設(shè)置Tab.1 Experimental parameter setting

3.2 對(duì)比實(shí)驗(yàn)

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

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

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

本文使用平均時(shí)延、平均魯棒和邊緣計(jì)算節(jié)點(diǎn)數(shù)量作為對(duì)比實(shí)驗(yàn)的性能指標(biāo)，平均魯棒使用式（13）進(jìn)行計(jì)算：

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

3.3 實(shí)驗(yàn)結(jié)果

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

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

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

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

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

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

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

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

圖5 計(jì)算節(jié)點(diǎn)數(shù)量對(duì)比Fig.5 Comparison of number of computing nodes

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

4 結(jié)語

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