工業(yè)物聯(lián)網(wǎng)中大規(guī)模受損邊緣計算網(wǎng)絡(luò)修復(fù)機(jī)制

田輝，伍浩，田洋，任建陽，崔亞娟，艾文寶，袁健華

（1.北京郵電大學(xué)網(wǎng)絡(luò)與交換技術(shù)國家重點實驗室，北京 100876；2.北京郵電大學(xué)理學(xué)院，北京 100876）

1 引言

工業(yè)物聯(lián)網(wǎng)（IIoT,industrial Internet of things）被視為全球工業(yè)體系智能化變革的重要推手。依靠數(shù)以億計無縫部署的感知器、采集器與控制器，工業(yè)物聯(lián)網(wǎng)可以實現(xiàn)對生產(chǎn)制造過程全周期的模擬、預(yù)測與控制[1]。作為工業(yè)物聯(lián)網(wǎng)的“大腦”，邊緣計算網(wǎng)絡(luò)為無線采集設(shè)備提供了更充足的計算處理能力，有效降低了處理、傳輸時延，為數(shù)字孿生（DT,digital twin）[2]、虛擬現(xiàn)實（VR,virtual reality）等企業(yè)高層應(yīng)用打下了堅實的基礎(chǔ)[3]。同時，邊緣計算節(jié)點間有線的鏈路連接方式，也使節(jié)點間的計算任務(wù)遷移更加順暢，有效緩解了工業(yè)物聯(lián)網(wǎng)計算需求空時波動所造成的計算資源空時分配不均衡問題。

邊緣計算網(wǎng)絡(luò)的正常、穩(wěn)定運行是工業(yè)物聯(lián)網(wǎng)高效運轉(zhuǎn)的關(guān)鍵，一旦“大腦”受損，工業(yè)物聯(lián)網(wǎng)系統(tǒng)將失去對“四肢”（例如供應(yīng)鏈監(jiān)控、數(shù)據(jù)可視化分析）的有效控制，帶來難以計數(shù)的經(jīng)濟(jì)損失，甚至威脅生命。然而，邊緣計算網(wǎng)絡(luò)的穩(wěn)定性需求面臨內(nèi)外兩方面的挑戰(zhàn)。一方面，邊緣計算網(wǎng)絡(luò)與工業(yè)物聯(lián)網(wǎng)中的電網(wǎng)、控制網(wǎng)等多種子網(wǎng)相互耦合，形成了極易受損的互依賴網(wǎng)絡(luò)[4]。其他子網(wǎng)的任意微小波動，都有可能傳導(dǎo)到邊緣計算網(wǎng)絡(luò)，造成大規(guī)模的系統(tǒng)級聯(lián)故障。另一方面，自然災(zāi)害與人為攻擊等不可預(yù)測事件也隨時考驗著邊緣計算網(wǎng)絡(luò)的穩(wěn)健性[5]。為應(yīng)對上述挑戰(zhàn)，一方面可以加強邊緣計算網(wǎng)絡(luò)的可靠性，使其能夠自適應(yīng)地應(yīng)對各種網(wǎng)絡(luò)波動，防止網(wǎng)絡(luò)出現(xiàn)故障；另一方面，也是更重要的，需要探究網(wǎng)絡(luò)受損后的快速修復(fù)機(jī)制，使網(wǎng)絡(luò)性能盡快恢復(fù)到接近受損前的水平。

盡管修復(fù)機(jī)制的設(shè)計對網(wǎng)絡(luò)可持續(xù)穩(wěn)定運行至關(guān)重要，當(dāng)前尚無特定針對工業(yè)物聯(lián)網(wǎng)中邊緣計算網(wǎng)絡(luò)場景的研究文獻(xiàn)。鑒于網(wǎng)絡(luò)拓?fù)洹⒕W(wǎng)絡(luò)動態(tài)等特征的相似性，部分現(xiàn)存網(wǎng)絡(luò)修復(fù)策略仍可以為工業(yè)物聯(lián)網(wǎng)中邊緣計算網(wǎng)絡(luò)修復(fù)機(jī)制設(shè)計提供一定的借鑒。現(xiàn)存網(wǎng)絡(luò)修復(fù)機(jī)制的研究主要著重于局部網(wǎng)絡(luò)受損后的快速修復(fù)。文獻(xiàn)[6]將網(wǎng)絡(luò)單一節(jié)點或鏈路受損問題構(gòu)建為一個整數(shù)線性規(guī)劃問題，提出了一種數(shù)據(jù)遷移感知的修復(fù)模型，實現(xiàn)了服務(wù)中斷率與修復(fù)成本的有效均衡。進(jìn)一步地，文獻(xiàn)[7-8]考慮到多節(jié)點失效場景網(wǎng)絡(luò)連通性受損問題，提出可以通過設(shè)備到設(shè)備（D2D,device to device）方式利用用戶作為失連邊緣節(jié)點間的中轉(zhuǎn)節(jié)點[7]或者利用可移動接入節(jié)點實現(xiàn)網(wǎng)絡(luò)節(jié)點間數(shù)據(jù)的處處可達(dá)[8]，保障受損網(wǎng)絡(luò)的連通性。與上述研究不同，文獻(xiàn)[9]考慮到網(wǎng)絡(luò)受攻擊情況下的持續(xù)性受損狀態(tài)，將網(wǎng)絡(luò)動態(tài)修復(fù)問題轉(zhuǎn)化為微分博弈論問題，并通過納什均衡必要條件與競爭策略集增強了網(wǎng)絡(luò)修復(fù)能力。然而，上述針對局部網(wǎng)絡(luò)修復(fù)的研究，往往忽略了全局網(wǎng)絡(luò)節(jié)點、鏈路間的動態(tài)特征（例如流遷移）和實際場景限制（例如鏈路空間布局無法改動），難以有效擴(kuò)展至工業(yè)物聯(lián)網(wǎng)中更可能發(fā)生的網(wǎng)絡(luò)大規(guī)模受損場景。

網(wǎng)絡(luò)大規(guī)模受損后，初期可利用的修復(fù)資源（例如修理人員數(shù)量、可替換設(shè)備數(shù)量）往往是有限的。如何有效平衡修復(fù)初期受限的系統(tǒng)修復(fù)資源與急迫的系統(tǒng)性能恢復(fù)需求是當(dāng)前工業(yè)物聯(lián)網(wǎng)中亟待解決的問題。當(dāng)前研究主要集中于對網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的分析。文獻(xiàn)[10]認(rèn)為，大度節(jié)點，即節(jié)點度大的節(jié)點，在網(wǎng)絡(luò)連通性方面有著更重要的作用，需要優(yōu)先修復(fù)。類似地，文獻(xiàn)[11]考慮鏈路受損情況下，應(yīng)優(yōu)先修復(fù)介數(shù)中心性（BC,betweenness centrality）大的鏈路。文獻(xiàn)[12]通過實際網(wǎng)絡(luò)數(shù)據(jù)分析發(fā)現(xiàn)，網(wǎng)絡(luò)中的弱連接節(jié)點，即自身的度不高但連接著數(shù)個大度節(jié)點的節(jié)點，在網(wǎng)絡(luò)連通性上發(fā)揮著最關(guān)鍵的作用，其修復(fù)優(yōu)先級應(yīng)比大度節(jié)點更高。然而，上述基于網(wǎng)絡(luò)連通性不斷壯大最大連通子圖的方案均是靜態(tài)網(wǎng)絡(luò)架構(gòu)分析，忽略了網(wǎng)絡(luò)的動態(tài)性特征。真實環(huán)境下的網(wǎng)絡(luò)大規(guī)模修復(fù)往往是先形成相互獨立的子圖，然后將多子圖連接形成最大連通圖[13]。因此，工程分析中，需要融入更多的網(wǎng)絡(luò)設(shè)備細(xì)節(jié)與實際傳輸動態(tài)分析[14]。這類問題也被稱為網(wǎng)絡(luò)設(shè)計問題（NDP,network design problem）。由于網(wǎng)絡(luò)動態(tài)性特征的加入，網(wǎng)絡(luò)設(shè)計問題的復(fù)雜性極高（至少是NP 完全問題），傳統(tǒng)動態(tài)規(guī)劃算法將引發(fā)“維度災(zāi)難”[15]。為解決上述問題，文獻(xiàn)[16]提出了一種更易求解的啟發(fā)式算法，然而，其缺乏網(wǎng)絡(luò)宏觀分析，算法性能方差大，無法提供可靠的性能保障。類似地，模擬退火算法[17]與遺傳算法[18]均面臨一般啟發(fā)式算法的相同困境，且極易陷入局部最優(yōu)解。盡管通過爬山算法[19]或梯度下降算法[20]可以方便地跳出局部最優(yōu)點并極大降低問題計算復(fù)雜度，但解的最優(yōu)性仍無法得到保障。

針對當(dāng)前研究所面臨的現(xiàn)實困境，本文提出了一種針對工業(yè)物聯(lián)網(wǎng)環(huán)境下受損邊緣計算網(wǎng)絡(luò)的修復(fù)機(jī)制。區(qū)別于現(xiàn)有文獻(xiàn)，本文基于工業(yè)物聯(lián)網(wǎng)子網(wǎng)間的互依賴特性所造成的網(wǎng)絡(luò)脆弱性，深入挖掘了大規(guī)模受損邊緣計算網(wǎng)絡(luò)的結(jié)構(gòu)特性（拓?fù)潢P(guān)系、鏈路容量）與動態(tài)特性（節(jié)點計算需求），聯(lián)合考慮了鏈路優(yōu)先修復(fù)集合決策與網(wǎng)絡(luò)計算遷移問題，以期實現(xiàn)網(wǎng)絡(luò)修復(fù)初期計算需求與修復(fù)開銷的高效均衡。本文主要貢獻(xiàn)總結(jié)如下。

1) 提出了一種邊緣計算網(wǎng)絡(luò)大規(guī)模受損情況下的網(wǎng)絡(luò)修復(fù)機(jī)制。結(jié)合邊緣計算網(wǎng)絡(luò)結(jié)構(gòu)與動態(tài)特征，提供了一種網(wǎng)絡(luò)修復(fù)初期優(yōu)先修復(fù)集合決策與資源調(diào)度分析框架。

2) 基于Benders 分解算法，將復(fù)雜的混合整數(shù)問題分解為更易求解的主問題與子問題兩部分，通過各自解集的相互迭代，逐漸逼近系統(tǒng)最優(yōu)解。針對多變量組的子問題，通過添加虛擬源節(jié)點與目的節(jié)點，將問題轉(zhuǎn)化為網(wǎng)絡(luò)最大流問題進(jìn)行求解。

3) 設(shè)計了一種基于局部分支法的Benders 分解加速算法。采用基于漢明距離的信賴域，收縮可行域的搜索范圍，加速算法的收斂速度。

仿真結(jié)果表明，本文所提算法具有較好的收斂性能與較低的系統(tǒng)總開銷。相對現(xiàn)有隨機(jī)修復(fù)、最大連通圖修復(fù)和介數(shù)中心性排序修復(fù)算法等基于拓?fù)浣Y(jié)構(gòu)的修復(fù)算法，本文所提算法在多場景下均具有較優(yōu)表現(xiàn)和具有很好的可擴(kuò)展性與適應(yīng)性。

2 系統(tǒng)模型

針對工業(yè)物聯(lián)網(wǎng)中邊緣計算網(wǎng)絡(luò)，考慮一個含有N個節(jié)點的邊緣計算網(wǎng)絡(luò)，用集合?i∈ N={1,2,…,N}表示。邊緣節(jié)點之間均通過有線鏈路連接，鏈路集合用Ε表示，網(wǎng)絡(luò)中總鏈路數(shù)量為。由于有線鏈路通常是可靠的，且相對邊緣節(jié)點的計算任務(wù)只需要少量的信道編碼復(fù)雜性，2 個邊緣節(jié)點間的鏈路可以認(rèn)為是無差錯的[21]。系統(tǒng)參數(shù)如表1所示。值得注意的是，實際工業(yè)物聯(lián)網(wǎng)中邊緣計算網(wǎng)絡(luò)往往是由有線鏈路與無線鏈路組成的混合鏈路傳輸網(wǎng)絡(luò)。由于無線鏈路幾乎不存在受損情況，且其修復(fù)成本相對于有線鏈路可以忽略不計，本文只考慮所有傳輸鏈路均為有線鏈路的情況。盡管如此，如果不考慮短期無線信道的深衰弱，靜態(tài)場景下的無線鏈路（不考慮修復(fù)過程中的頻譜重分配）可視為容量不變的不可受損鏈路，混合鏈路傳輸網(wǎng)絡(luò)可以等效為純有線鏈路網(wǎng)絡(luò)進(jìn)行考慮，本文所提算法仍將適用。

表1 系統(tǒng)參數(shù)

受損邊緣計算網(wǎng)絡(luò)拓?fù)潢P(guān)系如圖1 所示。在實際網(wǎng)絡(luò)中，由于邊緣節(jié)點常擁有復(fù)雜的自我保護(hù)機(jī)制（例如過熱保護(hù)），通常不易發(fā)生損壞，因此本文不考慮節(jié)點損壞的情況，重點關(guān)注鏈路受損問題。為模擬因自然災(zāi)害等因素而導(dǎo)致大面積網(wǎng)絡(luò)故障的狀態(tài)，假設(shè)初始時刻網(wǎng)絡(luò)中有條有線鏈路遭到破壞，其中q表示受損鏈路占所有鏈路的百分比，集合Ε0表示受損鏈路集合，Ε1=ΕΕ0表示仍可以正常工作的鏈路集合。鏈路的受損將導(dǎo)致邊緣節(jié)點間平衡的計算遷移流被打破，甚至形成計算孤島（無法進(jìn)行計算遷移，如圖1 中節(jié)點1 所示），從而造成計算需求與計算能力不匹配，影響網(wǎng)絡(luò)計算性能。受限于網(wǎng)絡(luò)修復(fù)初期的有限修復(fù)資源（例如修理人員數(shù)量、可替換設(shè)備庫存），同時修復(fù)所有的受損鏈路不切實際。為使網(wǎng)絡(luò)狀態(tài)盡快得到恢復(fù)，可以根據(jù)網(wǎng)絡(luò)計算需求分布，優(yōu)先修復(fù)部分受損鏈路，用集合Εr（Εr?Ε0）表示。對于任意鏈路ij∈Ε0，由于受損程度不同，對其進(jìn)行維護(hù)、檢修、替換的成本cij也各不相同。

圖1 受損邊緣計算網(wǎng)絡(luò)拓?fù)潢P(guān)系

令節(jié)點i與節(jié)點之間的遷移計算量為fij。若fij>0，數(shù)據(jù)計算任務(wù)由節(jié)點i遷移至節(jié)點j；若fij<0，數(shù)據(jù)計算任務(wù)由節(jié)點j遷移至節(jié)點i。受有線鏈路容量限制，鏈路ij實際計算遷移量滿足

進(jìn)一步地，對于受損鏈路，其實際計算遷移量不僅取決于有線鏈路容量，也受到鏈路修復(fù)決策的影響，即

其中，有

其中，eij=1表示優(yōu)先修復(fù)鏈路ij，即ij∈Εr；當(dāng)eij=0表示鏈路ij未被修復(fù)，其實際計算遷移量fij=0。此外，對于單一鏈路ij，由遷移流對稱性可知

當(dāng)集合Εr中鏈路得到修復(fù)時，根據(jù)節(jié)點的計算量守恒定律可知

其中，ri表示節(jié)點i的本地數(shù)據(jù)計算量需求；di表示因計算能力有限導(dǎo)致數(shù)據(jù)積壓，邊緣節(jié)點i不得不舍棄的計算任務(wù)量，有

為了修復(fù)盡可能多的鏈路，可以減少數(shù)據(jù)的丟棄量，提升系統(tǒng)性能，但會造成較大的系統(tǒng)修復(fù)開銷。修復(fù)鏈路過少，系統(tǒng)修復(fù)開銷固然變小，但可能造成數(shù)據(jù)因堆積在本地?zé)o法處理而被丟棄，損害網(wǎng)絡(luò)性能。為進(jìn)行量化分析，本文中網(wǎng)絡(luò)性能通過系統(tǒng)數(shù)據(jù)丟棄總代價來進(jìn)行衡量，數(shù)據(jù)丟棄量越大，數(shù)據(jù)丟棄總代價越高，網(wǎng)絡(luò)性能越差。因此，為均衡網(wǎng)絡(luò)修復(fù)初期的修復(fù)開銷與網(wǎng)絡(luò)性能（數(shù)據(jù)丟棄總代價），可以構(gòu)建如下的系統(tǒng)總開銷最小化問題

其中，cij表示修復(fù)鏈路ij∈Ε0所需要的修復(fù)成本，ci表示節(jié)點丟棄每單位數(shù)據(jù)的代價，鏈路修復(fù)決策向量e=(eij,?ij∈Ε0)，數(shù)據(jù)丟棄決策向量d=(di,?i∈N)，流分配向量f=(fij,?ij∈Ε)，本地實際計算量向量p=(pi,?i∈N)。問題P 中，系統(tǒng)總開銷包含兩部分內(nèi)容：系統(tǒng)修復(fù)開銷與數(shù)據(jù)丟棄總代價。如前文所述，系統(tǒng)修復(fù)開銷與數(shù)據(jù)丟棄總代價是一對相互矛盾的量，一個值的增加將導(dǎo)致另一個值的減少，最小化它們的和可以有效均衡兩者影響。當(dāng)鏈路修復(fù)成本cij較大時，表明計算數(shù)據(jù)重要性相對不高，系統(tǒng)傾向于暫時修復(fù)較少的受損鏈路，并丟棄無法處理的數(shù)據(jù)；而當(dāng)每單位數(shù)據(jù)丟棄代價ci較大時，系統(tǒng)傾向于修復(fù)更多的受損鏈路以減少計算數(shù)據(jù)的丟棄。

問題P 是一個混合整數(shù)問題，是NP-hard 問題，且其數(shù)據(jù)規(guī)模較大，目前還沒有已知的多項式時間算法能夠解決上述問題。當(dāng)前求解上述問題的方法可以分為三大類：啟發(fā)式算法[22]、近似算法[23]與精確算法[24]。啟發(fā)式算法速度快、應(yīng)用簡單，但缺乏嚴(yán)格的理論證明，結(jié)果常常嚴(yán)重偏離最優(yōu)解。近似算法，例如松弛變量法，其求解規(guī)模有限，松弛問題的解也不能準(zhǔn)確描述原問題最優(yōu)解。與上述2 種方法不同，精確算法，例如割平面算法，通過割平面的迭代更新，可以很好地探索問題最優(yōu)解，在混合整數(shù)問題求解過程中被廣泛采用。

3 算法設(shè)計

Benders 分解算法[25]是一種經(jīng)典的割平面算法，被廣泛用于處理現(xiàn)實中的混合整數(shù)規(guī)劃問題（例如機(jī)車調(diào)度、航空路線規(guī)劃）。該算法既不會像分支定界法那樣迭代次數(shù)隨著運算變量的增多而顯著增加，也不會像動態(tài)規(guī)劃那樣產(chǎn)生維度災(zāi)難，同時不會出現(xiàn)啟發(fā)式、模擬退火等算法的巨大方差[26]。本節(jié)將基于Benders 分解算法，給出問題P 的高效解決方案。

3.1 子問題描述與轉(zhuǎn)換

在Benders 分解算法中，原問題可以被分解為主問題與子問題兩部分，主問題中的優(yōu)化變量稱為復(fù)雜變量。當(dāng)復(fù)雜變量固定后，原問題中剩下的優(yōu)化問題（即子問題）變得相對容易求解。對于問題P，若給定第t次迭代過程中的復(fù)雜變量的值，則子問題可以表示為

由于原問題P 中的0-1 變量eij被分解到主問題中，上述子問題中優(yōu)化變量均為連續(xù)變量，該問題可以等效為一個最小費用流問題。本文考慮工業(yè)物聯(lián)網(wǎng)中典型的環(huán)境監(jiān)控場景，邊緣網(wǎng)絡(luò)中各邊緣節(jié)點負(fù)責(zé)處理無線傳感器采集的環(huán)境數(shù)據(jù)。在環(huán)境監(jiān)控場景下，各邊緣節(jié)點處的計算任務(wù)有著相同的計算優(yōu)先級[3,15]，即節(jié)點丟棄每單位數(shù)據(jù)的代價相同(ci=cj,?i,j∈N)。從而問題可進(jìn)一步轉(zhuǎn)化為網(wǎng)絡(luò)最大流問題[27]。圖2 通過一個含有4 個節(jié)點的邊緣網(wǎng)絡(luò)對上述等效關(guān)系進(jìn)行了說明。

圖2 子問題等效最大流問題示例

在圖2 中，節(jié)點2 與節(jié)點3 之間的連接線為迭代過程中所確定的需要修復(fù)的受損鏈路，即{ij,ij∈Εr,Εr?Ε0}。源節(jié)點s與目的節(jié)點z為新增的虛擬節(jié)點，源節(jié)點s與4 個邊緣節(jié)點的虛擬鏈路容量為4 個邊緣節(jié)點的最大計算能力，4 個邊緣節(jié)點與目的節(jié)點z的虛擬鏈路表示各邊緣節(jié)點的本地數(shù)據(jù)計算量需求。圖2 中各邊上的數(shù)值表示該鏈路的鏈路容量，從而最大化目的節(jié)點z的總到達(dá)流等價于最小化總數(shù)據(jù)的丟棄量。上述轉(zhuǎn)化后的最大流問題，可以通過已有算法，如Ford-Fulkerson 算法[28]，進(jìn)行高效的多變量問題求解。

3.2 割平面生成與主問題構(gòu)建

在Benders 分解算法中，子問題的解將代入主問題用于生成主問題中的線性約束，即Benders 割平面。由于本文考慮了完善資源[29]，即對于任意可行的主問題解，總有可行的子問題解，不需要再生成可行割，只需要構(gòu)建最優(yōu)割即可。為形成Benders最優(yōu)割平面，需要利用對偶問題的互補松馳性原理[30]，根據(jù)上述子問題的解，提取限制條件式(3)所對應(yīng)的對偶變量，即可修復(fù)鏈路ij的邊際系統(tǒng)增量。

定理1在第t次迭代中的Benders 最優(yōu)割平面可以表示為

其中，η為子問題目標(biāo)函數(shù)的最優(yōu)解的上界，θt為子問題在第t次迭代中所求得的目標(biāo)函數(shù)的最優(yōu)值，即第t次迭代中的最小數(shù)據(jù)丟棄總代價。

證明見附錄1。

將上述Benders 最優(yōu)割平面代入主問題求解的限制條件中，可得主問題為

與子問題確定邊緣網(wǎng)絡(luò)的數(shù)據(jù)遷移、計算與丟棄不同，主問題負(fù)責(zé)確定受損鏈路集合Ε0中需要被優(yōu)先修復(fù)的鏈路集合Er。在主、子問題的循環(huán)迭代過程中，主問題的求解都是在給定數(shù)據(jù)遷移、計算與丟棄量的情況下進(jìn)行的。主問題求解所得的Εr反過來被用于子問題的進(jìn)一步求解，從而逐步逼近系統(tǒng)的最優(yōu)數(shù)據(jù)遷移、計算、丟棄與鏈路修復(fù)策略。

3.3 基于Benders 分解理論的迭代路徑修復(fù)與計算遷移算法

將上述主問題初始化后代入子問題，并開始循環(huán)迭代尋找最優(yōu)解。若在迭代過程中主問題的決策變量不能滿足所有約束條件，則終止算法，原問題無解；否則持續(xù)迭代過程直至找到網(wǎng)絡(luò)最優(yōu)配置。上述過程的具體步驟如算法1 所示。

算法1基于Benders 分解理論的迭代路徑修復(fù)與計算遷移算法

當(dāng)算法收斂后，系統(tǒng)將根據(jù)當(dāng)前迭代計算所得的et，修復(fù)其中值為1 的鏈路。之后，利用子問題的解ft確定節(jié)點間的數(shù)據(jù)流遷移量，依據(jù)pt調(diào)整各節(jié)點的實際計算能力，并丟棄超出計算能力的數(shù)據(jù)dt。需要注意的是，主問題中η為一個連續(xù)變量，e為離散變量，該問題仍是一個混合整數(shù)問題。盡管可以采用諸如遺傳蟻群算法在內(nèi)的算法進(jìn)行求解，但由于其搜索域空間較大，算法復(fù)雜度依舊很高。此外，在每次迭代過程中，主問題中新的割平面的引入使算法下界保持了非減特性，但并沒有類似機(jī)制保障算法上界的單調(diào)特性。這種非單調(diào)約束界特性將進(jìn)一步加劇上述算法的計算時間開銷。

4 Benders 分解加速算法設(shè)計

為解決算法1 提出的基于Benders 分解理論的迭代路徑修復(fù)與計算遷移算法所存在的問題，本文在迭代求解過程中進(jìn)一步引入了局部分支技術(shù)[31]。其主要目的在于在每次迭代過程中找到更好的問題上界，以期實現(xiàn)上下界的內(nèi)向夾逼，減少主問題的計算復(fù)雜性。

4.1 信賴域與漢明距離

如前文所述，基于割平面的Benders 分解算法并不是一種穩(wěn)定的算法，在迭代的早期，問題的解會在不同的可行域內(nèi)大范圍波動，從而導(dǎo)致較慢的收斂速度。在本文所考慮的工業(yè)物聯(lián)網(wǎng)中的邊緣計算場景下，大規(guī)模網(wǎng)絡(luò)受損所引入的大量優(yōu)化變量，特別是初始搜索空間為的修復(fù)鏈路決策向量e的引入，將使該收斂速度問題進(jìn)一步惡化。信賴域是解決上述大范圍波動特性問題的一種極佳策略[32]。考慮到主問題中的e是一組0-1 變量，可以采用漢明距離來限制兩次迭代解的距離。

假設(shè)(e t,d t,p t,ft)為原問題第t次迭代所得到的可行解，此時所有0-1 優(yōu)化變量中值為1 的集合可以表示為，則第t+1次迭代與第t次迭代的漢明距離為

即第t+1 次迭代中e相對第t次迭代中變化的二進(jìn)制變量的數(shù)目。

為加快收斂速度，可以將解空間分解為2 個相互獨立的信賴域

其中，Δt+1表示在第t+1 次迭代中信賴域的規(guī)模大小，其值的選取取決于主問題的復(fù)雜性及搜索范圍的波動性需求。通過上述方式，原問題自然地被分為2 個子解空間，局部分支法便是基于此產(chǎn)生。在局部分支法中，式(11)和式(12)分別被稱為左枝和右枝。

4.2 局部分支法

基于漢明距離，原問題P 的解空間可根據(jù)Benders 分解第t次迭代所得的可行解(e t,d t,p t,ft)，分割為2 個緊密相連的鄰域空間。設(shè)ek,k∈Kt為Benders 分解第t次迭代過程中局部分支法迭代所計算的所有e的解（包括可行解與非可行解），其中可行解的集合表示為Lt（Lt?Kt）。根據(jù)漢明距離，原問題P 可以分支為2 個獨立的左右枝問題。其中左枝問題為

其中，式(13)表示不重復(fù)比較之前已比較過的e值，式(14)表示當(dāng)前左枝應(yīng)該是上一級分支中的右分枝的分枝，式(15)表示左枝限制條件，為當(dāng)前獲取的最優(yōu)解。相應(yīng)地可以得到右枝問題為

其中，式(16)表示右枝限制。

令(ek+1,dk+1,pk+1,fk+1)為左枝問題Pk的最優(yōu)解，對應(yīng)的目標(biāo)函數(shù)值為φk1+，則有局部分支法算法流程如算法2 所示。

算法2局部分支算法

算法2 循環(huán)條件中的Tmax是為了避免在計算過程中，由于漢明距離設(shè)置過大導(dǎo)致分枝問題無法解出的情況。在大規(guī)模受損網(wǎng)絡(luò)下，修復(fù)鏈路決策e的解空間規(guī)模十分龐大，選取較小的信賴域規(guī)模Δt將更有利于提升左枝問題的計算速度。

4.3 基于局部分支法的Benders 分解加速算法

將局部分支算法融入Benders 分解得到的基于局部分支法加速的Benders 分解算法如算法3 所示。

算法3基于局部分支法的Benders 分解加速理論的迭代路徑修復(fù)與計算遷移算法

與算法1 類似，當(dāng)算法3 收斂后，系統(tǒng)將根據(jù)當(dāng)前迭代計算所得的et確定修復(fù)鏈路集合。然后，根據(jù)計算所得ft、pt及dt的值，確定網(wǎng)絡(luò)中數(shù)據(jù)的遷移、計算與丟棄量。不同于算法1，算法3 通過局部分支技術(shù)，保證了原問題P 的上界在迭代過程中的嚴(yán)格遞減。對于大規(guī)模受損網(wǎng)絡(luò)，這意味著每次迭代過程中，主問題M 所需優(yōu)化的鏈路修復(fù)決策向量te的搜索空間逐步減少，解的搜索速度隨著迭代次數(shù)的增加而逐漸加快。

上述算法每次迭代獲得的新割平面中，并不是所有的割平面都需要加入主問題求解過程，可以只添加最深的割平面（即使可行域最大程度減少的割平面）。考慮到算法的收斂性要求與Benders 分解初始階段的糟糕表現(xiàn)，可以僅在初始迭代階段添加信賴域限制。當(dāng)?shù)呌诜€(wěn)定后，解除該限制條件。

值得注意的是，在每次分支過程中，分支問題P1,P2,…都擁有與原問題P 相同的結(jié)構(gòu)。因此針對每個分支問題，可以單獨使用算法1 進(jìn)行求解。之前的分支問題求得的割平面也可以繼續(xù)用于后續(xù)分支問題的求解。

5 仿真分析

本節(jié)對所提基于Benders 分解理論的迭代路徑修復(fù)與計算遷移算法（下文簡稱為Benders 分解算法）以及基于局部分支法的Benders 分解加速理論的迭代路徑修復(fù)與計算遷移算法（下文簡稱為Benders 分解加速算法）性能進(jìn)行了仿真測試，并驗證分析了所提算法相較于其他基準(zhǔn)算法的性能優(yōu)勢。

5.1 仿真參數(shù)與對比算法

本文考慮一個包含N=50 個節(jié)點的邊緣計算網(wǎng)絡(luò)，網(wǎng)絡(luò)修復(fù)初期各節(jié)點的最大計算能力相互獨立且均勻分布于[10,25]Gbit。考慮到計算能力與計算需求的匹配性，網(wǎng)絡(luò)修復(fù)初期節(jié)點的計算需求ir同樣服從[10,25]Gbit 上的均勻分布。不失一般性地，假設(shè)邊緣網(wǎng)絡(luò)原始拓?fù)渲杏芯€鏈路數(shù)量=2N，網(wǎng)絡(luò)拓?fù)渫S機(jī)網(wǎng)絡(luò)[4]，且節(jié)點間數(shù)據(jù)傳輸處處可達(dá)。考慮到計算節(jié)點的處理能力波動范圍，鏈路容量服從[5,15]Gbit 上的均勻分布。為模擬網(wǎng)絡(luò)大規(guī)模受損情況，在下文中，如無特殊說明，鏈路受損比例q=75%。假設(shè)修復(fù)每條受損鏈路的成本cij均勻分布于[1×104,2×104]元，因計算能力不足而丟棄數(shù)據(jù)的代價ci為104元/Gbit。

為了驗證本文所提受損網(wǎng)絡(luò)修復(fù)機(jī)制的效果，將本文算法與以下基準(zhǔn)算法進(jìn)行比較。

1）隨機(jī)修復(fù)算法。隨機(jī)選擇網(wǎng)絡(luò)中受損的鏈路進(jìn)行修復(fù)，不考慮網(wǎng)絡(luò)的具體拓?fù)浣Y(jié)構(gòu)與網(wǎng)絡(luò)計算流遷移的動態(tài)特征。

2）最大連通圖修復(fù)算法[16]。修復(fù)網(wǎng)絡(luò)的最大連通圖中的所有受損鏈路，確保網(wǎng)絡(luò)中最大連通圖中的所有節(jié)點能達(dá)到強連通狀態(tài)。

3）介數(shù)中心性排序修復(fù)算法[11]。分析邊緣網(wǎng)絡(luò)受損前的拓?fù)浣Y(jié)構(gòu)，對各條有線鏈路的介數(shù)中心性進(jìn)行排序，優(yōu)先修復(fù)介數(shù)中心性大的受損鏈路，修復(fù)鏈路數(shù)量與所提算法相同。

5.2 算法收斂性

圖3 為所提Benders 分解算法與Benders 分解加速算法的收斂性對比。從圖3 可以看出，2 種算法可以在有限次數(shù)內(nèi)實現(xiàn)快速迭代，具有較好的收斂性。需要注意的是，圖3 中迭代次數(shù)表征的是算法1 與算法3 中主問題與子問題的總循環(huán)迭代次數(shù)。在每次迭代過程中，子問題的計算復(fù)雜度為O(|N||Ε|2)，主問題計算復(fù)雜度為O(n|Ε0|3),其中n為主問題求解的內(nèi)循環(huán)迭代次數(shù)。盡管Benders分解加速算法相對Benders 分解算法，總迭代次數(shù)只減少一次，但其實際計算時間復(fù)雜度降低O(|N||Ε|2+n|Ε0|3)。在大規(guī)模受損網(wǎng)絡(luò)環(huán)境下，該計算時間復(fù)雜度的改善仍十分可觀。從圖3 中相同迭代次數(shù)情況下算法上下界的對比可以看出，相對于Benders 分解算法，局部分支法輔助的Benders分解加速算法由于有更深割平面的引入，收斂速度得到顯著提升，能夠更好地適應(yīng)大規(guī)模網(wǎng)絡(luò)的應(yīng)用需求。此外，Benders 分解算法與Benders 分解加速算法在收斂后系統(tǒng)總開銷趨于一致。因此，在下文中，為便于與基準(zhǔn)算法進(jìn)行對比，Benders 分解算法和Benders 分解加速算法統(tǒng)稱為“本文算法”。

圖3 所提Benders 分解算法與Benders 分解加速算法收斂性對比

5.3 算法性能

圖4 和圖5 分別為不同網(wǎng)絡(luò)受損程度q以及不同網(wǎng)絡(luò)規(guī)模N情況下，本文算法、隨機(jī)修復(fù)算法、最大連通圖修復(fù)算法、介數(shù)中心性排序修復(fù)算法的系統(tǒng)總開銷曲線。從圖4 和圖5 可以看出，在不同網(wǎng)絡(luò)受損程度以及網(wǎng)絡(luò)規(guī)模情況下，由于考慮了網(wǎng)絡(luò)中節(jié)點的計算需求與實際計算能力、鏈路容量限制等網(wǎng)絡(luò)動態(tài)特征，本文算法性能均優(yōu)于基準(zhǔn)算法。值得注意的是，最大連通圖修復(fù)算法的系統(tǒng)總開銷性能是所有算法中最差的，甚至弱于隨機(jī)修復(fù)算法，這與現(xiàn)實網(wǎng)絡(luò)中網(wǎng)絡(luò)修復(fù)呈現(xiàn)的狀態(tài)十分吻合。在現(xiàn)實網(wǎng)絡(luò)中，修復(fù)過程總是先使網(wǎng)絡(luò)中形成大大小小各自獨立的簇，在修復(fù)的最后才將各個簇連接起來形成最大連通圖[13]。

圖4 不同網(wǎng)絡(luò)受損程度下算法性能對比

圖5 不同網(wǎng)絡(luò)規(guī)模下算法性能對比

5.4 算法多場景適用性

圖6 和圖7 分別表示不同單位數(shù)據(jù)丟棄代價場景下本文算法修復(fù)的受損鏈路數(shù)目與計算數(shù)據(jù)丟棄量。考慮到本文算法系統(tǒng)總開銷對于鏈路修復(fù)成本和計算數(shù)據(jù)丟棄的雙重考量，隨著單位數(shù)據(jù)丟棄代價ci的增大，修復(fù)鏈路數(shù)目與數(shù)據(jù)丟棄量呈現(xiàn)出相反的增減關(guān)系。與經(jīng)驗相符，隨著ci增大，即數(shù)據(jù)丟棄成本增大，網(wǎng)絡(luò)傾向于修復(fù)更多的鏈路使計算需求得以滿足。當(dāng)ci取值在[1,1.5]萬元/Gbit 時，圖7 中數(shù)據(jù)丟棄量開始出現(xiàn)顯著下降，這是因為在該范圍內(nèi)，系統(tǒng)剛好處于敏感臨界點附近。在該值附近，系統(tǒng)均衡修復(fù)成本與丟棄數(shù)據(jù)開銷的能力最強。任意微小的ci值變化都可能帶來均衡決策的較大幅度改變。在ci超過2 萬元/Gbit 后，繼續(xù)修復(fù)受損鏈路帶來的邊際效益降低，網(wǎng)絡(luò)修復(fù)鏈路數(shù)目與計算數(shù)據(jù)丟棄量保持穩(wěn)定。可以看出，本文算法能夠很好地適用于各種不同數(shù)據(jù)丟棄代價場景，具有較好的可擴(kuò)展性與適應(yīng)性。

圖6 不同單位數(shù)據(jù)丟棄代價下本文算法受損鏈路修復(fù)數(shù)目

圖7 不同單位數(shù)據(jù)丟棄代價下本文算法計算數(shù)據(jù)丟棄量

為進(jìn)一步分析本文算法在不同網(wǎng)絡(luò)拓?fù)鋱鼍跋碌男阅埽疚膶⒕W(wǎng)絡(luò)形式由單一的隨機(jī)網(wǎng)絡(luò)場景擴(kuò)展至柵格網(wǎng)絡(luò)與無標(biāo)度網(wǎng)絡(luò)[33]。與隨機(jī)網(wǎng)絡(luò)不同，柵格網(wǎng)絡(luò)各節(jié)點的度完全相同，無標(biāo)度網(wǎng)絡(luò)節(jié)點的度服從冪律分布。從圖8 可以看出，在3 類網(wǎng)絡(luò)下，各算法性能均會產(chǎn)生不同程度的波動，但本文算法的系統(tǒng)總開銷性能均優(yōu)于基準(zhǔn)算法。得益于對于網(wǎng)絡(luò)拓?fù)渑c動態(tài)特征的聯(lián)合分析，本文算法具有很好的多場景適應(yīng)性。

圖8 不同網(wǎng)絡(luò)拓?fù)湎滤惴▽Ρ惹闆r（N=100）

6 結(jié)束語

本文針對工業(yè)物聯(lián)網(wǎng)中邊緣計算網(wǎng)絡(luò)的易受損特征，提出了一種網(wǎng)絡(luò)大規(guī)模受損后的修復(fù)機(jī)制，給出了優(yōu)先修復(fù)鏈路集合決策與計算遷移配置的聯(lián)合優(yōu)化方法，有效緩解了網(wǎng)絡(luò)修復(fù)初期有限修復(fù)資源與大量數(shù)據(jù)計算需求的矛盾。考慮到原始問題的求解困難，利用Benders 分解算法將其轉(zhuǎn)化為更易求解的主問題與子問題，通過割平面的不斷更新，逐步逼近問題最優(yōu)解。進(jìn)一步地，結(jié)合局部分支法，設(shè)計了一種Benders 分解加速算法，有效提升了算法收斂速度。仿真結(jié)果表明，相對現(xiàn)有基于拓?fù)浣Y(jié)構(gòu)的修復(fù)算法，本文算法具有較好的系統(tǒng)修復(fù)性能。

盡管出于數(shù)據(jù)公平性考量，本文考慮計算數(shù)據(jù)具有相同處理優(yōu)先級，即不同節(jié)點丟棄每單位數(shù)據(jù)的代價相同，本文思想仍可以十分便捷地擴(kuò)展至每單位數(shù)據(jù)丟棄代價不同的場景，只需將子問題解法替換為現(xiàn)有最小費用流算法（如Dinic 算法）即可。

本文算法主要針對節(jié)點間為有線鏈路連接的情況。對于存在動態(tài)無線鏈路的場景，例如無人機(jī)充當(dāng)移動邊緣節(jié)點的場景，信道容量隨無人機(jī)位置改變而改變，需要進(jìn)一步聯(lián)合考量無人機(jī)運行軌跡、無線頻譜分配等問題。這將使本已復(fù)雜的網(wǎng)絡(luò)修復(fù)問題變得更加難以求解，已超出本文的考慮范圍，留待后續(xù)研究。

附錄1 Benders 最優(yōu)割平面證明