基于小波變換和魚群算法的網(wǎng)絡(luò)抗毀性研究

段謨意

（南京鐵道職業(yè)技術(shù)學(xué)院 軟件學(xué)院，江蘇 南京210031）

0 引 言

隨著無線傳感器網(wǎng)絡(luò)的快速發(fā)展，網(wǎng)絡(luò)抗毀性的重大理論意義和應(yīng)用價值也日益凸顯。網(wǎng)絡(luò)抗毀性描述了網(wǎng)絡(luò)在遭受意外故障或蓄意攻擊時的可靠性，其節(jié)點和鏈路的性能對網(wǎng)絡(luò)的抗毀性產(chǎn)生非常重要作用。當(dāng)網(wǎng)絡(luò)中某個熱點節(jié)點的能量耗盡時，該節(jié)點的失效使得網(wǎng)絡(luò)被分割，從而導(dǎo)致性能快速下降。同時，由于節(jié)點負荷的加重，容易導(dǎo)致?lián)砣头纸M丟失，造成鏈路中斷。所以，如何避免熱點節(jié)點成為無線傳感器網(wǎng)絡(luò)抗毀性能的瓶頸，國內(nèi)外學(xué)者對此做了大量研究。郭虹等［1］針對無線網(wǎng)絡(luò)節(jié)點的重要度，利用結(jié)構(gòu)熵定義了網(wǎng)絡(luò)抗毀熵、節(jié)點抗毀度和全網(wǎng)抗毀度，并通過仿真分析了所定義的測度是移動無線網(wǎng)絡(luò)抗毀性評估的有效指標(biāo)。黎放等［2］在網(wǎng)絡(luò)總?cè)萘坎蛔?、容許參數(shù)可變的基礎(chǔ)上，構(gòu)建了資源有限的級聯(lián)失效模型，并建立了四種典型的容量分配策略，但是存在度偏好容量分配策略不如負荷偏好策略，以及平均容量分配策略效果不好等問題。文獻 ［3］提出了基于局部負荷分配策略的級聯(lián)失效模型，并且發(fā)現(xiàn)在某些條件下攻擊低度節(jié)點對網(wǎng)絡(luò)的破壞程度反而大于高度的節(jié)點。文獻 ［4］的研究說明了當(dāng)高度節(jié)點獲得更多的容量分配時，能夠有效提高網(wǎng)絡(luò)抵抗級聯(lián)失效的能力。文獻 ［5］利用凝聚度及生成樹宏觀評估全連通網(wǎng)絡(luò)的相對抗毀性，但缺乏對非連通網(wǎng)絡(luò)節(jié)點重要性的有效計算。文獻 ［6］基于通信網(wǎng)絡(luò)抗毀性的定義，采用多抗毀性度量值的評估技術(shù)，對通信網(wǎng)絡(luò)的抗毀性進行評價，并構(gòu)建了抗毀性模型。文獻 ［7－8］針對網(wǎng)絡(luò)部件失效情況采用概率加權(quán)法，深入研究了滿足業(yè)務(wù)要求的狀態(tài)概率求和。

針對上述問題，本文在以往定義的網(wǎng)絡(luò)節(jié)點抗毀性基礎(chǔ)上，首先采用小波變換減少業(yè)務(wù)流的相關(guān)性，并且通過魚群算法來刻畫業(yè)務(wù)流狀態(tài)。同時，利用仿真實驗深入研究了該方法的有效性。

1 抗毀性定義

假設(shè)存在如圖1所示的無線傳感器網(wǎng)絡(luò)G （V，E，F(xiàn)），其中，V表示點集，E表示邊集，F(xiàn)表示兩節(jié)點間的流量。令D＝ （dij）表示節(jié)點Vi和Vj的最短路徑的邊數(shù)，并且假設(shè)某邊ek上對應(yīng)的權(quán)重為 （k，fij表示節(jié)點Vi和Vj之間的流量。

圖1 網(wǎng)絡(luò)拓撲結(jié)構(gòu)

作者曾提出節(jié)點Vi關(guān)于路徑 （Vi，Vj）的重要度定義

式中：m——路徑 （Vi，Vj）上存在的節(jié)點數(shù)。在網(wǎng)絡(luò)遭受攻擊時，隨著平均路徑長度dij的增加，μi不斷增大，當(dāng)網(wǎng)絡(luò)的連通性遭到破壞時dij＝0，μi＝0。

同時，定義了節(jié)點Vi的抗毀性指標(biāo)

式中：B——節(jié)點初始能量，b——節(jié)點剩余能量，c1和c2——能量因子和流量因子，且c1＋c2＝1。

從式 （1）和 （2）可知，節(jié)點抗毀性主要受到的節(jié)點能量與節(jié)點流量影響，而節(jié)點能量與自身環(huán)境有著重要關(guān)聯(lián)，所以這里針對節(jié)點流量進行詳細研究。此前作者曾基于元胞蟻群算法提出過一種計算方法ICA （invulnerability based on cellular ant），其思路是通過定義元胞移動規(guī)則來改進蟻群算法，以此評價節(jié)點抗毀性。對此，本文提出另外一 種 計 算 方 法 IWA （invulnerability based on wavelet transform and fish swarm algorithm），采用小波變換和魚群算法來研究節(jié)點抗毀性。

2 數(shù)學(xué)模型

2.1 魚群行為定義

這里將業(yè)務(wù)流看作魚群［9－10］，節(jié)點重要度看作食物濃度，其流量作為狀態(tài)指標(biāo)，以下給出四種魚群行為定義。

（1）覓食行為

覓食行為是魚群生存的基本行為，魚群通過感官向食物濃度大的地方移動。假設(shè)魚群當(dāng)前狀態(tài)為fi，在其鄰域內(nèi)隨機選擇另外一個狀態(tài)fj，根據(jù)式 （3）將魚群置于區(qū)域中心ri

式中：xi和yi——搜索區(qū)域位置，該k為魚群數(shù)量。由式（1）計算當(dāng)前的食物濃度ui和uj。如果ui＜uj，則該魚群朝此方向移動一步，令ui＝ui＋1，并將fj作為當(dāng)前狀態(tài)，否則停止不動。直到試探多次后仍未移動，則考慮采取其它行為。

（2）聚群行為

在聚群移動的過程中需要同時保證魚群周圍的食物濃度和魚群間距離。假設(shè)魚群當(dāng)前狀態(tài)為fi，對應(yīng)的食物濃度為ui，并且該區(qū)域內(nèi)的魚群數(shù)量為ni，總的魚群數(shù)量為n，umin表示食物濃度的最小閾值，（min用于衡量魚群間最小距離。定義

1）如果ui＜umin，并且 （i≥ （min，說明該區(qū)域內(nèi)魚群有足夠距離，但是食物濃度不高，則執(zhí)行覓食行為；

2）如果ui≥umin，并且λi＜λmin，說明該區(qū)域內(nèi)食物濃度足夠，但是存在過多魚群，魚群間隔空間不夠，則朝著該區(qū)域中心反方向執(zhí)行隨機行為；

3）如果ui≥umin，并且λi≥λmin，則該區(qū)域內(nèi)的食物濃度和魚群間距離，魚群將向該區(qū)域中心位置ri移動一步，令ui＝ui＋1，并更新當(dāng)前狀態(tài)。

（3）追尾行為

當(dāng)魚群中的個體尋到食物，其它個體會尾隨其后，朝著距自身最優(yōu)的個體靠攏。假設(shè)魚群當(dāng)前狀態(tài)為fi，在鄰域ri內(nèi)存在最優(yōu)個體fk，如果ui＜uk，并且保證λi≥λmin，則說明該區(qū)域內(nèi)保證了足夠的食物濃度和魚群間距，則朝fk方向移動一步，令ui＝ui＋1，并更新當(dāng)前狀態(tài)。否則執(zhí)行覓食行為。

（4）隨機行為

隨機行為是從當(dāng)前狀態(tài)fi轉(zhuǎn)移到另一可行狀態(tài)fj。在求解過程中，當(dāng)長時間沒有獲得最優(yōu)解時，可考慮加入隨機概率，使魚群移動到鄰域來搜索可行解。令魚群的隨機移動概率為

其中，△fij＝fi－fj，0≤θ≤1。

2.2 算法設(shè)計

考慮到實際業(yè)務(wù)流具有的分形特性［11－12］，首先利用小波變換［13］來平滑業(yè)務(wù)流，使網(wǎng)絡(luò)節(jié)點有能力處理突發(fā)數(shù)據(jù)。然后根據(jù)定義的魚群行為，對網(wǎng)絡(luò)的抗毀性進行求解。具體算法如下所述：

（1）在開始時刻t，初始化各網(wǎng)絡(luò)節(jié)點參數(shù)，同時設(shè)置魚群相關(guān)信息；

（2）收集當(dāng)前網(wǎng)絡(luò)節(jié)點Vi的業(yè)務(wù)流狀態(tài)，利用結(jié)合式（6）對業(yè)務(wù)流進行小波變換，以平滑突發(fā)情況

式中：j——小波分解層次，k——每一層的小波系數(shù)，Dj，k——小波系數(shù)，Aj，k——近似系數(shù)；

（3）將小波變換之后的業(yè)務(wù)流看作魚群個體，根據(jù)式（1）計算其食物濃度ui；

（4）對魚群執(zhí)行定義的四種行為，獲取最優(yōu)值OPT；

（5）令i＝i＋1，并判斷當(dāng)前循環(huán)是否結(jié)束，或者最優(yōu)值OPT已經(jīng)連續(xù)有多次未變 （這里假設(shè)為8次），則結(jié)束尋優(yōu)操作，跳轉(zhuǎn)到步驟 （6），否則跳轉(zhuǎn)到步驟 （2）；

（6）根據(jù)當(dāng)前最優(yōu)值OPT，結(jié)合式 （2）計算網(wǎng)絡(luò)節(jié)點Vi的抗毀系數(shù)ki；

（7）令t＝t＋1，跳轉(zhuǎn)到步驟 （1），直至最后時刻；

（8）算法結(jié)束。

3 仿真實驗

首先，在OPNET中建立如圖1所示的網(wǎng)絡(luò)仿真圖，各參數(shù)設(shè)定為：鏈路容量為10Mbps，延時10ms，各節(jié)點緩存大小為500packets，數(shù)據(jù)包大小為200Byte。并且采用分形高斯噪聲FGN模型來產(chǎn)生分形業(yè)務(wù)流，令各節(jié)點發(fā)送業(yè)務(wù)流的速率為2000kbit／s，其相關(guān)程度指標(biāo)H＝0.9。這里針對的路徑為 （Va，Vk），需要計算的是節(jié)點k的抗毀性。將IWA算法與ICA算法獲得的抗毀性進行比較，如圖2所示。在10s內(nèi)，IWA的抗毀性整體要高于ICA。經(jīng)過數(shù)據(jù)統(tǒng)計，IWA較ICA的性能提高了6.41%。

圖2 IWA算法與ICA算法的抗毀性比較

其次，為了更清楚比較兩種算法的性能，這里依次減少路徑 （Va，Vk）上的連接邊數(shù)，觀察節(jié)點k抗毀性的變化情況，結(jié)果如圖3所示。整體趨勢上，隨著失效邊的增多，兩種算法的抗毀性隨之減小。這是因為減少了連接邊相當(dāng)于降低了節(jié)點之間的連通度，使得網(wǎng)絡(luò)抵抗破壞的能力降低。但是IWA比ICA降低的速度較慢，這說明在同等情況下，IWA抵抗破壞的能力更強。并且，在圖4中顯示了節(jié)點k的抗毀性與失效節(jié)點之間的關(guān)系。從整體趨勢上說，圖4和圖3有著類似情況，隨著失效節(jié)點的增多，節(jié)點k的抗毀性減小。在失效節(jié)點數(shù)比較少時，IWA比ICA降低的速度較慢，但是失效節(jié)點在達到4之后，IWA和ICA對應(yīng)的抗毀性比較接近。

進一步地，為了研究IWA算法的性能，在圖5中顯示了不同流量因子c2下，節(jié)點k的抗毀性與節(jié)點負載之間的關(guān)系。整體趨勢上來說，隨著負載的增加，節(jié)點k的抗毀性先呈上升趨勢，達到極大值點后又呈現(xiàn)出下降趨勢。在抗毀性達到極大值點前，當(dāng)負載小于800bit時，c2對應(yīng)的值越小反而其抗毀性越大，而負載介于800－1200bit時，情況發(fā)生了突變，c2對應(yīng)的值越小其抗毀性越小。當(dāng)抗毀性超過極大值點后，整個情況正好與之前狀態(tài)相反。

圖5 抗毀性與節(jié)點負載 （bit／s）之間的關(guān)系

同時，這里將長相關(guān)參數(shù)H作為應(yīng)變量，圖6顯示了不同流量因子c2下節(jié)點k抗毀性的變化情況。從圖6可以看出，隨著H值的增加抗毀性是隨之增加的。當(dāng)H值較小時，c2對應(yīng)的值越小其抗毀性越大，當(dāng)H值超過0.7－08區(qū)域時，c2對應(yīng)的值越大其抗毀性越大。這里存在突變情況，分析其原因是由于有限帶寬產(chǎn)生的作用。

圖6 抗毀性與H之間的關(guān)系

4 結(jié)束語

本文基于小波變換和魚群算法提出了一種新的網(wǎng)絡(luò)節(jié)點抗毀性評價方法IWA。該方法首先針對作者以往定義的網(wǎng)絡(luò)節(jié)點抗毀性指標(biāo)，采用魚群算法來刻畫業(yè)務(wù)流的性能狀態(tài)。同時針對業(yè)務(wù)流的突發(fā)，利用小波變換來減少其相關(guān)性。并且通過仿真實驗，對比研究了與ICA評價方法的優(yōu)劣，說明了IWA方法具有一定的適應(yīng)性。在后續(xù)研究中，可考慮結(jié)合網(wǎng)絡(luò)有效性和生存性進行動態(tài)關(guān)聯(lián)建模，以此形成比較完善的評價體系。

［1］GUO Hong，LAN Julong，LIU Luokun.Research of metrics of Ad Hoc networks invulnerability considering node importance assessment ［J］.Journal of Chinese Computer Systems，2010，31 （6）：1063－1066 （in Chinese）. ［郭虹，蘭巨龍，劉洛琨.考慮節(jié)點重要度的Ad Hoc網(wǎng)絡(luò)抗毀性測度研究 ［J］.小型微型計算機系統(tǒng)，2010，31 （6）：1063－1066.］

［2］LI Fang，HU Bin，DI Peng.Optimization of dynamic invulnerability of scale free networks based on limited resource model［J］.System Engineering and Electronics，2012，34 （1）：175－178（in Chinese）.［黎放，胡斌，狄鵬.基于資源有限模型的無標(biāo)度網(wǎng)絡(luò)動態(tài)抗毀性優(yōu)化 ［J］.系統(tǒng)工程與電子技術(shù)，2012，34 （1）：175－178.］

［3］WANG Jianwei，RONG Lili.Cascade－based attack vulnerability on the US power grid［J］.Safety Science，2009，47 （10）：1332－1336.

［4］LI P，WANG B H，SUN H，et al.A limited resource model of fault－tolerant capability against cascading failure of complex network［J］.The European Physical Journal B，2008，62 （1）：101－104.

［5］RAO Yuping，LIN Jingyu，ZHOU Dongfang.Method for network invulnerability and node importance evaluation ［J］.Computer Engineering，2009，35 （6）：14－16 （in Chinese）.［饒育萍，林競羽，周東方.網(wǎng)絡(luò)抗毀度和節(jié)點重要性評價方法［J］.計算機工程，2009，35 （6）：14－16.］

［6］REN Junliang，SHEN Maoxing，SHI Xiangfeng.A method of evaluating the invulnerability of communication networks structure ［J］.Journal of Air Force Engineering University （Natural Science Edition），2010，11 （1）：70－73 （in Chinese）. ［任俊亮，申卯興，史向峰.通信網(wǎng)絡(luò)抗毀性的評價方法 ［J］.空軍工程大學(xué)學(xué)報 （自然科學(xué)版），2010，11 （1）：70－73.］

［7］LIN Y K.Reliability of a computer network in case capacity weight varying with arcs，nodes and types of commodity ［J］.Reliability Engineering and System Safety，2007，92 （5）：646－652.

［8］Gunawan I.Redundant paths and reliability bounds in gamma networks ［J］.Applied Mathematical Modeling，2008，32 （4）：588－594.

［9］DAI Shangping，JI Yinli，WANG Hua，et al.Extracting classification rules based on multi artificialfish swarm cooperation algorithm ［J］.Application Research of Computers，2012，29（5）：1676－1679 （in Chinese）. ［戴上平，姬盈利，王華，等.基于多群協(xié)同人工魚群算法的分類規(guī)則提取算法 ［J］.計算機應(yīng)用研究，2012，29 （5）：1676－1679.］

［10］SHEN Wei，GUO Xiaopen，WU Chao，et al.Forecasting stock indices using radial basis function neural networks optimized by artificial fish swarm algorithm ［J］.Knowledgebased Systems，2011，24 （3）：378－385.

［11］Masugi M.Multi－fractal analysis of IP－network traffic based on a hierarchical clustering approach ［J］.Communications in Nonlinear Science and Numerical Simulation，2007，12 （7）：1316－1325.

［12］XU Xiaodong，ZHU Shirui，SUN Yamin.Anomaly detection algorithm based on fractal characteristics of large－scale network traffic［J］.Journal on Communications，2009，30 （9）：43－53 （in Chinese）.［許曉東，朱士瑞，孫亞民.基于分形特性的宏觀網(wǎng)絡(luò)流量異常分析 ［J］.通信學(xué)報，2009，30 （9）：43－53.］

［13］BAI Xiangyu，YE Xinming，JIANG Hai.Network traffic predicting based on wavelet transform and autoregressive model［J］.Computer Science，2007，34 （7）：47－54 （in Chinese）.［白翔宇，葉新銘，蔣海.基于小波變換與自回歸模型的網(wǎng)絡(luò)流量預(yù)測 ［J］.計算機科學(xué)，2007，34 （7）：47－54.］