基于鏈路重構(gòu)策略的網(wǎng)絡(luò)抗毀性優(yōu)化研究

史文博，劉 東，楊博文

(國防科技大學(xué) 信息通信學(xué)院，湖北 武漢 430014)

0 引 言

隨著科學(xué)技術(shù)的不斷發(fā)展，通過對現(xiàn)有網(wǎng)絡(luò)進(jìn)行重構(gòu)，可以達(dá)到顯著提高網(wǎng)絡(luò)抗毀性性能的目的，對提升通信網(wǎng)絡(luò)抗打擊能力具有十分重要的意義。

祁兵等人[1]采用建立環(huán)路保護(hù)的思想來提高電力通信網(wǎng)絡(luò)的抗毀性能。馮顏[2]則主要考慮了通信網(wǎng)絡(luò)在受到打擊破壞后的動(dòng)態(tài)修復(fù)。張賽男、劉東亮[3]利用CW節(jié)約算法以及遺傳算法實(shí)現(xiàn)網(wǎng)絡(luò)優(yōu)化，該方法結(jié)合了CW節(jié)約算法快速收斂以及遺傳算法避免局部最優(yōu)解的特性，并將該方法與貪婪算法的網(wǎng)絡(luò)優(yōu)化結(jié)果進(jìn)行實(shí)驗(yàn)對比。彭觀勝[4]提出基于禁忌搜索的復(fù)雜網(wǎng)絡(luò)抗毀性優(yōu)化算法。宋曉峰等人[5]用克隆選擇算法對網(wǎng)絡(luò)的抗毀性進(jìn)行優(yōu)化。Wang Wei[6]研究基于隨機(jī)游走間度(RB)的級(jí)聯(lián)故障模型,實(shí)現(xiàn)了復(fù)雜網(wǎng)絡(luò)的級(jí)聯(lián)故障預(yù)防。

文中主要對無線通信網(wǎng)絡(luò)實(shí)現(xiàn)抗毀性優(yōu)化。首先分析了網(wǎng)絡(luò)抗毀性與聚合度的內(nèi)在聯(lián)系；其次對傳統(tǒng)HBF-α算法鏈路重構(gòu)策略進(jìn)行調(diào)整，提高了網(wǎng)絡(luò)優(yōu)化效果；然后結(jié)合通信網(wǎng)絡(luò)實(shí)際要求，提出了保證節(jié)點(diǎn)度不變的鏈路重構(gòu)策略，使用模擬退火算法有效解決了HBF-α策略中局部最優(yōu)解問題，并分析對比兩種優(yōu)化方案的適用情形、優(yōu)化程度以及時(shí)間開銷；最后總結(jié)全文，并提出下一步的研究重點(diǎn)。

1 網(wǎng)絡(luò)抗毀性分析

在通信網(wǎng)絡(luò)打擊過程中，關(guān)鍵節(jié)點(diǎn)[7]常常是優(yōu)先打擊目標(biāo)。根據(jù)田秀雯在文獻(xiàn)[8]中對網(wǎng)絡(luò)聚合度與定點(diǎn)打擊下網(wǎng)絡(luò)崩潰的臨界值之間關(guān)系的分析，發(fā)現(xiàn)降低該臨界值與降低網(wǎng)絡(luò)聚合度對網(wǎng)絡(luò)抗毀性能提升基本一致。下面以由12個(gè)通信節(jié)點(diǎn)與27條鏈路組成的通信網(wǎng)絡(luò)為例，隨機(jī)移除鏈路，同時(shí)隨機(jī)建立鏈路，保持總節(jié)點(diǎn)數(shù)目與鏈路數(shù)量不變。不同網(wǎng)絡(luò)結(jié)構(gòu)下的聚合度與抗毀性[9]指標(biāo)值關(guān)系如圖1所示。

圖1 網(wǎng)絡(luò)抗毀性與聚合度關(guān)系

可以看出，網(wǎng)絡(luò)抗毀性與網(wǎng)絡(luò)聚合度呈反比例關(guān)系。故可以通過降低網(wǎng)絡(luò)聚合度[10]、實(shí)現(xiàn)節(jié)點(diǎn)重要度[11]均衡的方式優(yōu)化網(wǎng)絡(luò)抗毀性能。

對于鏈路可以重構(gòu)的無線通信網(wǎng)絡(luò)，常采用移除關(guān)鍵節(jié)點(diǎn)間鏈路[12]的方法來有效提升網(wǎng)絡(luò)抗毀性能，同時(shí)，降低網(wǎng)絡(luò)聚合度也可以避免部分節(jié)點(diǎn)因負(fù)載較大而崩潰的情況發(fā)生，但網(wǎng)絡(luò)的經(jīng)濟(jì)開銷將會(huì)增加[13]。在移除了部分鏈路之后，從均衡的角度出發(fā)，在業(yè)務(wù)量較小的節(jié)點(diǎn)之間建立新的鏈路，實(shí)現(xiàn)網(wǎng)絡(luò)流量再均衡，網(wǎng)絡(luò)抗毀性可以得到優(yōu)化。

2 HBF-α算法優(yōu)化及實(shí)驗(yàn)分析

2.1 算法步驟

HBF-α策略：對通信網(wǎng)絡(luò)中所有鏈路賦值，權(quán)重Aij由該鏈路兩端的節(jié)點(diǎn)的重要度值之和決定，Aij=G(vi)+G(vj)，賦值結(jié)果為A1,A2,…,An，尋找到其中最大的權(quán)值，該權(quán)值對應(yīng)的鏈路即為需要移除的鏈路。在移除掉該鏈路后，隨機(jī)在所有的節(jié)點(diǎn)中選取兩個(gè)節(jié)點(diǎn)，當(dāng)兩節(jié)點(diǎn)間不存在鏈路時(shí)，建立新的鏈路，否則重新隨機(jī)選取節(jié)點(diǎn)對。重復(fù)上述操作直到達(dá)到規(guī)定的抗毀性指標(biāo)要求，理論上該方法可以將網(wǎng)絡(luò)聚合度降到趨近于0[14]。

對HBF-α算法的新建鏈路策略進(jìn)行優(yōu)化，算法步驟如下：

(1)對所有鏈路進(jìn)行賦值并記為該鏈路的權(quán)重，權(quán)重Aij由該鏈路兩端的節(jié)點(diǎn)的重要度值之和決定，即Aij=G(vi)+G(vj)，并依據(jù)鏈路的權(quán)值大小順序從大到小記為A1,A2,…,An。

(2)按照A1,A2,…,An的順序依次移除鏈路，當(dāng)移除鏈路會(huì)造成節(jié)點(diǎn)中斷時(shí)，保留該條鏈路，當(dāng)移除鏈路的比例達(dá)到規(guī)定的重構(gòu)比例時(shí)，停止移除。

(3)計(jì)算第二步中移除規(guī)定比例鏈路后的節(jié)點(diǎn)重要度，在節(jié)點(diǎn)重要度之和最小的兩節(jié)點(diǎn)之間建立新的鏈路，當(dāng)鏈路已經(jīng)存在時(shí)，選擇重要度之和次小的節(jié)點(diǎn)，以此類推。

(4)循環(huán)進(jìn)行上述(3)操作，直至通信網(wǎng)絡(luò)的鏈路總數(shù)量達(dá)到原網(wǎng)絡(luò)的鏈路數(shù)量時(shí)停止。

2.2 實(shí)驗(yàn)分析

以0.2的連通概率隨機(jī)生成一個(gè)20*20的無向網(wǎng)絡(luò)結(jié)構(gòu)，該網(wǎng)絡(luò)共有98條鏈路，節(jié)點(diǎn)容量均為20，網(wǎng)絡(luò)拓?fù)鋱D如圖2所示。

圖2 20*20網(wǎng)絡(luò)拓?fù)?/p>

使用HBF-α策略和改進(jìn)后的算法分別對該20*20的通信網(wǎng)絡(luò)進(jìn)行優(yōu)化。兩種鏈路重構(gòu)策略不同重構(gòu)比例下的網(wǎng)絡(luò)聚合度(與網(wǎng)絡(luò)抗毀性呈反比)變化規(guī)律如圖3所示。

圖3 聚合度變化

可以看出，當(dāng)網(wǎng)絡(luò)規(guī)模較大時(shí)，改進(jìn)后的算法網(wǎng)絡(luò)抗毀性優(yōu)化能力高于HBF-α策略，當(dāng)重構(gòu)比例大于0.04后，網(wǎng)絡(luò)抗毀性優(yōu)化效果下降，在對0.06比例的鏈路進(jìn)行重構(gòu)優(yōu)化后，網(wǎng)絡(luò)抗毀性大約提高了2.13倍，網(wǎng)絡(luò)鏈路數(shù)量保持不變，滿足優(yōu)化要求。對于規(guī)模較小的網(wǎng)絡(luò)結(jié)構(gòu)，以12*12的通信網(wǎng)絡(luò)為例，兩種鏈路重構(gòu)策略不同重構(gòu)比例下的網(wǎng)絡(luò)聚合度變化規(guī)律如圖4所示。

圖4 12*12網(wǎng)絡(luò)聚合度變化

可以看出，改進(jìn)后的算法優(yōu)化效果穩(wěn)定、適應(yīng)性較強(qiáng)、收斂速度快，網(wǎng)絡(luò)容量以及網(wǎng)絡(luò)通信能力都得到了一定的提升，但存在優(yōu)化瓶頸，當(dāng)達(dá)到一定的優(yōu)化程度后網(wǎng)絡(luò)趨于穩(wěn)定，無法對網(wǎng)絡(luò)進(jìn)行進(jìn)一步的優(yōu)化，而HBF-α算法容錯(cuò)率較低，尤其是當(dāng)網(wǎng)絡(luò)規(guī)模較小時(shí)，優(yōu)化穩(wěn)定性差，在幾次優(yōu)化過程中，對網(wǎng)絡(luò)的優(yōu)化程度各不相同，這是其新建鏈路的隨機(jī)性而決定的。

改進(jìn)后的HBF-α算法對網(wǎng)絡(luò)抗毀性實(shí)現(xiàn)優(yōu)化是在重新調(diào)整網(wǎng)絡(luò)節(jié)點(diǎn)度的基礎(chǔ)上進(jìn)行的，適用于重構(gòu)靈活且對節(jié)點(diǎn)可同時(shí)建鏈的數(shù)量不做要求的通信網(wǎng)絡(luò)。

3 基于模擬退火算法的網(wǎng)絡(luò)抗毀性優(yōu)化

在實(shí)際通信網(wǎng)絡(luò)中，不同節(jié)點(diǎn)的層級(jí)以及功能不同，其節(jié)點(diǎn)度在優(yōu)化過程中應(yīng)當(dāng)基本保持不變，例如作為末端節(jié)點(diǎn)，其節(jié)點(diǎn)度應(yīng)當(dāng)保持為1，作為級(jí)別較高的上一級(jí)通信節(jié)點(diǎn)，其度應(yīng)當(dāng)在3左右。故對HBF-α的重構(gòu)策略進(jìn)行調(diào)整，以符合通信網(wǎng)絡(luò)重構(gòu)過程中任意節(jié)點(diǎn)建立鏈路總數(shù)不變的要求，即節(jié)點(diǎn)度保持不變。采用模擬退火算法[15]解決HBF-α算法中的優(yōu)化瓶頸問題，提出了基于模擬退火算法的網(wǎng)絡(luò)抗毀性優(yōu)化方法。

調(diào)整后的重構(gòu)策略如下所述，用于生成新的通信網(wǎng)絡(luò)：

(1)隨機(jī)選擇網(wǎng)絡(luò)中的任意兩個(gè)節(jié)點(diǎn)va,vb，并建立點(diǎn)集Va,Vb(分別為節(jié)點(diǎn)va,vb的鄰接節(jié)點(diǎn)集合)。

(2)隨機(jī)選擇點(diǎn)集Va中任意節(jié)點(diǎn)vaj。該節(jié)點(diǎn)不能為節(jié)點(diǎn)vb、點(diǎn)集Vb中的元素。同時(shí)隨機(jī)選擇點(diǎn)集Vb中任意一個(gè)節(jié)點(diǎn)vbj，同理，該節(jié)點(diǎn)不能是節(jié)點(diǎn)va、點(diǎn)集Va中的元素。

(3)移除鏈路va→vaj與鏈路vb→vbj，并建立va→vbj與vb→vaj兩條新的鏈路，完成對網(wǎng)絡(luò)的重構(gòu)，判斷新的網(wǎng)絡(luò)是否為全連通網(wǎng)絡(luò)，如果符合條件，完成重構(gòu)步驟，否則返回第一步重新選擇節(jié)點(diǎn)，依次進(jìn)行上述操作。

目標(biāo)函數(shù)為通信網(wǎng)絡(luò)聚合度J(D)：

圖5 抗毀性優(yōu)化過程對比

圖6 優(yōu)化重建策略的HBF-α算法

可以看出，基于模擬退火的網(wǎng)絡(luò)抗毀性優(yōu)化方法優(yōu)化效果穩(wěn)定，可以有效避免局部最優(yōu)解，但與調(diào)整了鏈路重構(gòu)策略后的HBF-α算法的優(yōu)化結(jié)果相比較，最終網(wǎng)絡(luò)抗毀性優(yōu)化效果相對較差，這是其保持節(jié)點(diǎn)度不變的鏈路重構(gòu)策略所決定的。優(yōu)化后的網(wǎng)絡(luò)的節(jié)點(diǎn)度標(biāo)準(zhǔn)差如表1所示。

圖7 基于模擬退火的網(wǎng)絡(luò)抗毀性優(yōu)化方法

表1 網(wǎng)絡(luò)節(jié)點(diǎn)度標(biāo)準(zhǔn)差對比

一般來說，節(jié)點(diǎn)度越大，與該節(jié)點(diǎn)相連接的鏈路數(shù)量越多，與此同時(shí)，該節(jié)點(diǎn)重要度就會(huì)偏大，導(dǎo)致網(wǎng)絡(luò)聚合度偏大，在HBF-α算法的優(yōu)化結(jié)果中可以看到優(yōu)化后網(wǎng)絡(luò)的節(jié)點(diǎn)度標(biāo)準(zhǔn)差降低。而模擬退火優(yōu)化算法的節(jié)點(diǎn)度標(biāo)準(zhǔn)差未發(fā)生變化，雖然優(yōu)化的最終效果相對較差，但符合通信網(wǎng)絡(luò)重構(gòu)過程中任意節(jié)點(diǎn)建立鏈路總數(shù)不變的要求。重構(gòu)6%鏈路時(shí)兩種策略的時(shí)間開銷如表2所示。

表2 時(shí)間開銷對比

可見，基于模擬退火的網(wǎng)絡(luò)抗毀性優(yōu)化算法雖然優(yōu)化效果較好，但產(chǎn)生的時(shí)間花銷極大，因此在網(wǎng)絡(luò)抗毀性優(yōu)化應(yīng)用中，該方法適合于規(guī)模較小、對節(jié)點(diǎn)建鏈數(shù)量有著相關(guān)限制的網(wǎng)絡(luò)，例如軍事通信網(wǎng)。而優(yōu)化的HBF-α策略適合于較大規(guī)模的通信網(wǎng)絡(luò)，且對網(wǎng)絡(luò)中各個(gè)節(jié)點(diǎn)的建鏈能力有著較高的要求。根據(jù)不同的通信背景，采取合理的鏈路重構(gòu)策略，可以有效實(shí)現(xiàn)通信網(wǎng)絡(luò)抗毀性優(yōu)化。

4 結(jié)束語

針對網(wǎng)絡(luò)抗毀性優(yōu)化問題，優(yōu)化重構(gòu)策略后的HBF-α算法復(fù)雜度低、收斂速度快、效率較高，但存在優(yōu)化程度有限、適用范圍較小等問題。對于基于模擬退火的網(wǎng)絡(luò)優(yōu)化方法，在調(diào)整了鏈路重構(gòu)策略后，優(yōu)化結(jié)果更加貼近實(shí)際需求，但算法復(fù)雜度高。由于模擬退火算法中目標(biāo)函數(shù)的計(jì)算是基于最短路徑求解的，進(jìn)一步加劇了計(jì)算的復(fù)雜度，因此下一步可以通過尋求其他計(jì)算復(fù)雜度較低的有效指標(biāo)更換目標(biāo)函數(shù)，提高算法效率。