基于元胞蟻群算法的網(wǎng)絡(luò)生存性研究

江宇波 趙攀

摘 要：針對通信網(wǎng)絡(luò)因鏈路失效而產(chǎn)生的網(wǎng)絡(luò)擁塞問題，基于元胞蟻群算法提出了一種新的網(wǎng)絡(luò)生存性評價方法SACA（Survivability Algorithm based on Cellular Ant）。該方法首先給出了網(wǎng)絡(luò)生存性定義，并且通過元胞蟻群算法設(shè)計了生存性算法流程，以此獲得網(wǎng)絡(luò)剩余數(shù)據(jù)傳輸量。同時，利用NS2和MATLAB進(jìn)行仿真實(shí)驗(yàn)，結(jié)果表明，相比于其它算法，SACA算法具有出較好的適應(yīng)性。

關(guān)鍵詞：生存性；剩余能量；失效；元胞蟻群

中圖分類號：G642 文獻(xiàn)標(biāo)識碼：B 文章編號：1002-7661（2014）09-285-02

目前，如何提高網(wǎng)絡(luò)安全性成為網(wǎng)絡(luò)的研究重點(diǎn)和研究熱點(diǎn)。網(wǎng)絡(luò)生存性已經(jīng)成為影響其性能的關(guān)鍵問題[1]。網(wǎng)絡(luò)生存性主要是指網(wǎng)絡(luò)在遭遇外部攻擊或自身故障等異常情況下，仍然能夠及時維持可接受的業(yè)務(wù)質(zhì)量的能力。為了有效評價并解決這一問題，國內(nèi)外學(xué)者開展大量研究工作。2000年，Albert等[2]首先研究了不同度分布下復(fù)雜網(wǎng)絡(luò)的有效性。Paolo Crucitti等[3]利用度和介概念提出了關(guān)鍵節(jié)點(diǎn)和鏈路評估模型，并討論了不同狀態(tài)下的網(wǎng)絡(luò)生存能力。但是這些優(yōu)化思想并沒有從網(wǎng)絡(luò)模型和網(wǎng)絡(luò)狀態(tài)進(jìn)行深入分析，所以對于從本質(zhì)上解決網(wǎng)絡(luò)抗毀性的作用有限。皇甫偉等[4]定義了網(wǎng)絡(luò)生存性指標(biāo)，并基于災(zāi)害條件對具有SDH自愈環(huán)拓?fù)浣Y(jié)構(gòu)的網(wǎng)絡(luò)生存性進(jìn)行了定量分析。包學(xué)才等[5]針對全連通網(wǎng)絡(luò)定義了不相交路徑抗毀性評估模型，研究了全連通網(wǎng)絡(luò)節(jié)點(diǎn)間不相交路徑數(shù)的比重，從而能夠定量計算通信網(wǎng)絡(luò)的抗毀性。Wang Jianwei等[6]提出了基于局部負(fù)荷分配策略的級聯(lián)失效模型，并且發(fā)現(xiàn)在某些條件下攻擊低度節(jié)點(diǎn)對網(wǎng)絡(luò)的破壞程度反而大于高度的節(jié)點(diǎn)。

針對上述問題，本文首先給出了網(wǎng)絡(luò)生存性定義，并且利用元胞蟻群算法來計算剩余數(shù)據(jù)傳輸量[7-8]，進(jìn)而獲得當(dāng)前網(wǎng)絡(luò)生存性。同時通過NS2和MATAB進(jìn)行仿真實(shí)驗(yàn)，深入研究了影響該方法的關(guān)鍵因素。

1、網(wǎng)絡(luò)生存性定義

假設(shè)存在網(wǎng)絡(luò)G（V， W， F）中，V代表節(jié)點(diǎn)集合（V=[1， 2， …， n]），W代表鏈路權(quán)重集合，F(xiàn)表示網(wǎng)絡(luò)中任意兩點(diǎn)之間的流量集合，假設(shè)網(wǎng)絡(luò)中各節(jié)點(diǎn)位置具有隨機(jī)性，并且節(jié)點(diǎn)的性質(zhì)相同（如數(shù)據(jù)轉(zhuǎn)發(fā)能力，緩沖大小等），這里將各節(jié)點(diǎn)出現(xiàn)失效的情況歸納為對應(yīng)鏈路出現(xiàn)失效，同時假設(shè)各鏈路出現(xiàn)失效的概率相等。令網(wǎng)絡(luò)中存在n段鏈路，正常情況下整個網(wǎng)絡(luò)數(shù)據(jù)傳輸量為f，有k條鏈路失效時網(wǎng)絡(luò)剩余流量為f（k）。那么，網(wǎng)絡(luò)生存性則可以定義為：

（1）

其中：

（2）

在上述定義中，關(guān)鍵在于求解網(wǎng)絡(luò)剩余流量f（k）。本文結(jié)合元胞自動機(jī)和蟻群智能算法對f（k）進(jìn)行研究，將定義的元胞演化規(guī)則替換變異和交叉操作，以達(dá)到快速收斂的目的，同時降低了算法的運(yùn)算量。

2、元胞蟻群算法

元胞自動機(jī)是一種時間和空間離散、可擴(kuò)散的、狀態(tài)有限的多維系統(tǒng)，普遍應(yīng)用于非線性科學(xué)領(lǐng)域。

本文采用Moore型元胞結(jié)構(gòu)，如圖1所示，在下一時刻螞蟻按照概率p選擇周圍8個元胞和自身中的最優(yōu)狀態(tài)進(jìn)行轉(zhuǎn)移：

（3）

其中，ξ和ζ為非負(fù)常數(shù)，λi為螞蟻i為中心r為半徑的鄰域內(nèi)的單位面積內(nèi)的節(jié)點(diǎn)分布，Δλ表示兩相臨鄰域內(nèi)的節(jié)點(diǎn)分布差，yi為每個螞蟻對應(yīng)的狀態(tài)函數(shù)，Δyij=yi-yj，并且狀態(tài)函數(shù)yi為定義為：

（4）

同時這里定義如下元胞演化規(guī)則：

（a） 選擇任意一個元胞i，通過計算臨域內(nèi)各yi值，記錄其中最優(yōu)值yopt=yi。

（b） 在臨域半徑r內(nèi)任意選取元胞i和j，并計算相應(yīng)的yi和yj；如果yi

這里利用元胞蟻群給出上述數(shù)學(xué)模型的求解算法（Botnet Detecting algorithm based on Cellular Ant，BDCA）：

1、在開始時刻T，初始化網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，網(wǎng)絡(luò)剩余數(shù)據(jù)傳輸量f（k）、元胞蟻群規(guī)模為M，并確定元胞蟻群的轉(zhuǎn)移概率p和搜索區(qū)域半徑r，最大迭代閾值MAX；

2、確定螞蟻的搜索區(qū)域及搜索中心位置Oi：

（13）

其中，xmax和xmin為搜索區(qū)域上下邊界，rand（）產(chǎn)生（0， 1）之間的隨機(jī)數(shù)；

3、在Oi為中心、r為搜索半徑的區(qū)域內(nèi)，螞蟻i搜索是否存在比當(dāng)前狀態(tài)函數(shù)yi更優(yōu)的元胞；如果存在則按照概率p進(jìn)行移動，如果移動成功，則丟棄當(dāng)前中心區(qū)域Oi，重新計算當(dāng)前螞蟻i的目標(biāo)函數(shù)值，以及當(dāng)前最優(yōu)解，同時更新方程修改軌跡強(qiáng)度；

4、重復(fù)上述步驟（3），完成所有螞蟻的更新操作；

5、令T=T+1，跳轉(zhuǎn)到步驟（2）繼續(xù)執(zhí)行，直至Δλ趨于0或者跌代次數(shù)超過閾值MAX時停止；

6、輸出當(dāng)前的最優(yōu)解，即為穩(wěn)定狀態(tài)下最優(yōu)的網(wǎng)絡(luò)剩余數(shù)據(jù)傳輸量f（k）；

算法結(jié)束。

本文針對網(wǎng)絡(luò)生存性提出了一種新的刻畫方法SACA。該方法首先根據(jù)網(wǎng)絡(luò)剩余數(shù)據(jù)傳輸能力給出了網(wǎng)絡(luò)生存性指標(biāo)，通過定義元胞演化規(guī)則并結(jié)合蟻群算法，將網(wǎng)絡(luò)節(jié)點(diǎn)集合看作蟻群，使得在網(wǎng)絡(luò)失效的情況下能夠快速收斂，從而獲得全局最優(yōu)。最后，本文將提出的SACA算法與SAICSA 算法、ASATS算法進(jìn)行仿真實(shí)驗(yàn)，結(jié)果發(fā)現(xiàn)該算法具有較好的適應(yīng)性。同時在今后的研究中，可以考慮聯(lián)系網(wǎng)絡(luò)有效性和抗毀性進(jìn)行動態(tài)建模，以此形成較為完善的評價體系結(jié)構(gòu)。

參考文獻(xiàn)：

[1] Lazarou G Y， Baca Julie， Frostv S， Evans J B. Describing network traffic using the index of variability[J]. IEEE /ACM Transactions on Networking， 2009， 17 （5）： 1672-1683.

[2] Albert R， Jeong H， Barabasi A L. Error and attack tolerance of complex networks [J]. Nature， 2000， 406： 378-382.

[3] Crucitti P， Latora V， Marchiori M， Rapisarda A. Error and attack tolerance of complex networks [J]. Physica A， 2004， 340（1）： 388-394.

[4] 皇甫偉， 容鵬， 曾烈光. SDH 自愈環(huán)生存性定量分析[J]. 電子學(xué)報， 2001， 29（11）： 1558-1560.

[5] 包學(xué)才， 戴伏生， 韓衛(wèi)占. 基于拓?fù)涞牟幌嘟宦窂娇箽栽u估方法[J]. 系統(tǒng)工程與電子技術(shù)， 2012， 34（1）： 168-174.

[6] Wang Jianwei， Rong Lili. Cascade-based attack vulnerability on the US power grid[J]. Safety Science， 2009， 47（10）： 1332-1336.

[7] 曹春紅，王利民，趙大哲. 基于離散元胞螞蟻算法的幾何約束求解技術(shù)研究[J].電子學(xué)報，2011，38（5）：1127.