段謨意

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

0 引 言

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

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

1 抗毀性定義

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

圖1 網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)

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

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

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

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

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

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

2.1 魚群行為定義

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

（1）覓食行為

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

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

（2）聚群行為

在聚群移動(dòng)的過程中需要同時(shí)保證魚群周圍的食物濃度和魚群間距離。假設(shè)魚群當(dāng)前狀態(tài)為fi，對(duì)應(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í)行隨機(jī)行為；

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

（3）追尾行為

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

（4）隨機(jī)行為

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

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

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

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

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

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

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

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

（4）對(duì)魚群執(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）計(jì)算網(wǎng)絡(luò)節(jié)點(diǎn)Vi的抗毀系數(shù)ki；

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

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

3 仿真實(shí)驗(yàn)

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

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

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

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

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

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

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

4 結(jié)束語

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

［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é)點(diǎn)重要度的Ad Hoc網(wǎng)絡(luò)抗毀性測度研究 ［J］.小型微型計(jì)算機(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ò)動(dòng)態(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é)點(diǎn)重要性評(píng)價(jià)方法［J］.計(jì)算機(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ò)抗毀性的評(píng)價(jià)方法 ［J］.空軍工程大學(xué)學(xué)報(bào) （自然科學(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］.計(jì)算機(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é)報(bào)，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］.計(jì)算機(jī)科學(xué)，2007，34 （7）：47－54.］