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

田輝，伍浩，田洋，任建陽(yáng)，崔亞娟，艾文寶，袁健華

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

1 引言

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

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

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

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

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

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

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

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

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

2 系統(tǒng)模型

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

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

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

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

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

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

其中，有

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

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

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

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

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

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

3 算法設(shè)計(jì)

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

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

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

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

圖2 子問(wèn)題等效最大流問(wèn)題示例

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

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

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

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

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

證明見(jiàn)附錄1。

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

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

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

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

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

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

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

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

4.1 信賴域與漢明距離

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

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

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

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

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

4.2 局部分支法

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

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

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

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

算法2局部分支算法

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

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

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

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

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

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

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

5 仿真分析

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

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

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

為了驗(yàn)證本文所提受損網(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ò)計(jì)算流遷移的動(dòng)態(tài)特征。

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

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

5.2 算法收斂性

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

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

5.3 算法性能

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

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

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

5.4 算法多場(chǎng)景適用性

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

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

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

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

圖8 不同網(wǎng)絡(luò)拓?fù)湎滤惴▽?duì)比情況（N=100）

6 結(jié)束語(yǔ)

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

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

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

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