IEEE TSUSC'22：邊緣環境下成本效益優化的服務器網絡構建方法
移動邊緣計算作為一種新型的計算范式，它將邊緣服務器部署在靠近用戶的基站上，提供了類似云數據中心的計算和存儲功能，可以在網絡邊緣滿足應用程序的低延遲需求。邊緣服務器網絡是由區域內的邊緣服務器及其之間的鏈路組成，可以承載應用供應商為附近用戶提供服務的需求。邊緣服務器網絡密度是指服務器之間的連接密度。現有的諸多研究表明，高的邊緣服務器網絡密度可以使邊緣服務器之間進行更高效的通信和資源共享，從而實現較高的業務性能。在現實的邊緣計算環境中，構建高密度的邊緣服務器網絡往往會產生較高的建設成本。建設成本和網絡密度之間的權衡在邊緣服務器網絡的設計中起著至關重要的作用。然而，現有的邊緣計算相關研究在實驗測試中通常只是簡單地假設了這個網絡密度的值或者不予考慮，可能造成實際建設成本遠超預期。為此本文首次嘗試以網絡建設成本與網絡密度之間的平衡為目標，研究如何構建具有高性價比的邊緣服務器網絡構建方法。我們將這個新的邊緣服務器網絡設計問題（ESND）建模為一個約束優化問題，并證明了它的NP難度。我們進一步提出了一種基于整數規劃的ESND-O優化方法和一種名為ESND- A的近似方法分別解決小規模ESND問題和大規模ESND問題。我們對ESND-O和ESND-A在真實數據集上的性能進行了大量的實驗測試，實驗結果證明了它們的有效性和高效性。
該成果“Cost-Effective Edge Server Network Design in Mobile Edge Computing Environment “已被 IEEE Transactions on Sustainable Computing (TSUSC) 期刊錄用。該期刊主要關致力于發表探索可持續計算的不同方面的高質量論文，涉及從軟件和硬件設計到應用的廣泛問題領域和技術。目前該期刊的影響因子為2.456。
- 論文鏈接：
- https://doi.org/10.1109/TSUSC.2022.3178661
研究背景
在邊緣計算環境下，相鄰邊緣服務器之間可以通過高速鏈路進行通信。特定區域內的邊緣服務器及其之間的鏈路構成了邊緣服務器網絡。應用程序供應商可以在邊緣服務器上租用計算和存儲資源并基于邊緣服務器網絡部署相應服務。從而顯著降低昂貴的云端到邊緣端的數據傳輸成本以及端到端的服務延遲。通過邊緣服務器網絡，地理位置鄰近的邊緣服務器可以共享其資源以緩解資源受限問題。與傳統的云-邊架構相比，協同邊緣服務器網絡可以有效克服單點故障問題以及回程網絡所帶來的性能瓶頸問題。
現有的邊緣計算基礎設施相關研究主要關注最小化服務器部署成本，最大化用戶覆蓋率，最大化邊緣網絡魯棒性等服務器部署問題，忽視了邊緣服務器網絡設計的重要性。邊緣服務器網絡密度以每個邊緣服務器的平均鏈路數作為衡量指標，會顯著影響邊緣服務器的協作能力，進而影響部署在邊緣服務器上的服務性能。通常，提升網絡密度不僅能夠通過連接到更多的其他邊緣服務器使邊緣服務器獲得更多資源，也能夠通過保障邊緣服務器之間的低延遲消息傳遞和數據傳輸提升服務性能。這個觀察已經被邊緣用戶分配、邊緣數據緩存、邊緣數據同步、邊緣數據分發和邊緣數據去重等多個邊緣計算領域現有研究的實驗結果所證實。
然而，從亞馬遜、T-Mobile等邊緣基礎設施提供商的角度來看，邊緣網絡的高密度往往會導致網絡建設成本顯著提升。網絡構建成本包括了部署網絡設備(如網線、光纖、路由器、交換機等)的硬件成本和人工成本。在區域內的每一對相鄰邊緣服務器之間都部署上高速鏈路顯然是構建網絡密度較高的邊緣服務器網絡的一個簡單解決方案。然而，由于5G基站的分布密度高達每平方公里50個，這種方案很容易導致過高的網絡建設成本。在實踐中，邊緣基礎設施提供商必須確保網絡建設成本不超過其預算。在此預算范圍內，如何權衡網絡密度和網絡建設成本，是亟待解決的問題。
研究動機實例
為便于闡述本文的研究動機，我們以圖1場景為例進行描述。圖1給出了特定區域（如墨爾本CBD）內的5個邊緣服務器，分別表示為{s1,s2,…, s5}。邊緣基礎設施提供商可以根據周圍的環境來對構建兩個邊緣服務器之間鏈路的實際成本進行估算。為了對ESND問題進行通用性的討論，在本例中鏈路建設成本被注釋為圖中兩個邊緣服務器之間的邊的權重。在該區域內，通過建立邊緣服務器之間的網絡鏈路來構建邊緣服務器網絡的方式可以有很多種。從邊緣基礎設施提供商的角度看，邊緣服務器網絡必須足夠密集從而為部署在其上的應用程序提供更高的性能。然而要實現成本效益優化的邊緣服務器網絡設計則又必須考慮到網絡的構建成本。圖1（a）展示了一個最直觀的邊緣服務器網絡構建方法，即在每個鄰居邊緣服務器之間都建立網絡鏈路。該設計實現了最高的網絡密度為4，然而這種策略所產生的網絡建設成本較高，達到36。這顯然不是最優的ESN設計，例如，s2和s4之間的較長鏈路會產生很高的構建成本。圖1（d）描述的是一種低成本的邊緣服務器網絡設計方法，其網絡建設成本僅為10，比圖1（a）中所設計的網絡建設成本低72%。然而，該設計方案的網絡密度比圖1（a）的網絡密度要低60%。這種設計極大地犧牲了網絡密度，以此轉化為追求極低的構建成本。從邊緣基礎設施提供商的角度來看，它通常也不是最具成本效益的解決方案。
圖1 邊緣服務器網絡設計方案
圖1（b）和圖1（c）給出了另外兩種邊緣服務器網絡設計方案作為設計1和設計4之間的權衡方案。它們的網絡建設成本分別比設計方案1低31%和42%，網絡密度卻只比設計方案1分別低20%和30%。因此，邊緣基礎設施提供商可以根據實際需要來調整網絡密度和網絡建設成本的優先級。例如，如果該地區的用戶密度很高，邊緣基礎設施提供商可能會優先考慮設計2而不是設計3。在真實的邊緣服務器網絡構建場景中，給定一些邊緣服務器，存在著許多可能的網絡設計方案，需要連接的邊緣服務器數量通常較大，不同的邊緣服務器網絡設計方案在網絡密度和網絡建設成本之間提供了不同的權衡。從邊緣基礎設施提供商的角度來看，能夠評估這些不同的網絡設計并在滿足需求下找到一個最佳的網絡設計是極其重要且具有挑戰性的。
設計與實現
基于上述分析，我們研究了基于折衷規劃理論的邊緣服務器網絡設計問題。我們對該問題進行數學建模與抽象，利用折衷規劃方法將最大化網絡密度和最小化網絡構建成本的兩個優化目標進行整合，構建了一個以最小化妥協參數為最終優化目標，以邊緣服務器覆蓋、和網絡構建成本預算為約束的整數線性規劃模型。首先，我們從經典的NP難問題——旅行商（TSP）問題著手，通過規約理論證明了ESND問題是一個NP難問題。然后，我們給出了一種最優方法，即采用整數規劃求解器CPLEX設計的最優算法ESND-O。
針對ESND-O方法在大規模邊緣場景下的計算開銷大的問題，我們進一步設計了一種可應用于大規模邊緣場景快速求解的ESND-A的近似算法。算法工作流程如下：（1）基于迭代思想每次識別出邊緣服務器的鄰居服務器；（2）通過對鄰居服務器的鄰居數量進行排序，并選擇出擁有最多鄰居的服務器；（3）求解妥協參數，并將妥協參數最低的服務器加入候選集合；（4）更新決策矩陣，依次迭代進行上述過程以實現問題的最終求解。為了驗證ESND-A近似算法與最優解之間的差距，我們從理論上分析了其計算復雜度為O(n2)，并且證明了其具有
的近似比。
圖2 小規模實驗下服務器數量的敏感性測試
圖3 小規模實驗下網絡密度優先級的敏感性測試
我們在真實數據集上對提出的兩種方法分別進行了小規模和大規模實驗。小規模的實驗結果如圖2和圖3所示。其可以充分驗證ESND-O的性能提升，6.88%優于ESND-A，25.39%優于Homa，32.94%優于NSGA-II，41.23%優于ESND-C，和59.47%優于ESND-R。同時ESND-O的高計算開銷也證明了ESND問題是一個NP難問題。大規模實驗結果如圖4和圖5所示。相較于其他四種方法，ESND-A在妥協參數，網絡構建成本，網絡密度上分別平均領先了36.34%，42.32%和74.89%。在具有250個邊緣節點的場景下ESND-A求解該問題只需要46ms的計算開銷，證明了ESND-A方法的有效性和高效率。綜上所述，我們提出的兩種邊緣服務器網絡設計方法能夠在保證低計算開銷的同時，較好的實現網絡密度最大化和網絡構建成本最小化的雙重目標。
圖4 大規模實驗下服務器數量的敏感性測試
圖5 大規模實驗下網絡密度優先級的敏感性測試
詳細內容請參見：
Ruikun Luo, Hai Jin, Qiang He, Song Wu, and Xiaoyu Xia. “Cost-Effective Edge Server Network Design in Mobile Edge Computing Environment.” IEEE Transactions on Sustainable Computing.
DOI: 10.1109/ TSUSC.2022.3178661
