李英華梁 妍

(鄭州工商學(xué)院，河南 鄭州451400)

無線傳感器網(wǎng)絡(luò)(wireless sensor net works，WSN)是一種由大量傳感器節(jié)點(diǎn)通過無線方式協(xié)作檢測感知和處理各種環(huán)境信息的分布式網(wǎng)絡(luò)系統(tǒng)。通常無線傳感器網(wǎng)絡(luò)(WSN)的運(yùn)行環(huán)境多為無人值守模式，因此存在傳感器節(jié)點(diǎn)能量耗盡、軟硬件故障、故意攻擊等風(fēng)險[1－2]。傳感器節(jié)點(diǎn)故障將導(dǎo)致最初集成的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)進(jìn)行重新劃分，并降低網(wǎng)絡(luò)的覆蓋范圍，甚至可能導(dǎo)致整個網(wǎng)絡(luò)癱瘓[3]。因此，如何建立高度抗毀性無線傳感器網(wǎng)絡(luò)是當(dāng)前無線傳感器網(wǎng)絡(luò)研究的重點(diǎn)[4]。

現(xiàn)有的無線傳感器網(wǎng)絡(luò)抗毀性研究多從靜態(tài)角度出發(fā)，研究移除點(diǎn)或邊界對網(wǎng)絡(luò)拓?fù)溥B通性與可用性的影響，并未考慮網(wǎng)絡(luò)的動態(tài)過程。但在現(xiàn)實(shí)無線傳感器網(wǎng)絡(luò)中，網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的改變將會造成網(wǎng)絡(luò)數(shù)據(jù)流的重新分配，導(dǎo)致網(wǎng)絡(luò)通信負(fù)載發(fā)生動態(tài)變化。網(wǎng)絡(luò)通信負(fù)載的更新可能由于過載而導(dǎo)致新的節(jié)點(diǎn)故障，從而觸發(fā)新的級聯(lián)故障。但當(dāng)前無線傳感器網(wǎng)絡(luò)的級聯(lián)故障模型主要側(cè)重于節(jié)點(diǎn)容量對網(wǎng)絡(luò)性能的研究，忽略了鏈路容量的影響，從而導(dǎo)致流量指標(biāo)無法正確的反映無線傳感器網(wǎng)絡(luò)的匯聚特征[5－6]。

針對無線傳感器網(wǎng)絡(luò)級聯(lián)故障的抗毀性，國內(nèi)外眾多學(xué)者開展了大量研究。文獻(xiàn)[7]指出傳感器節(jié)點(diǎn)的流量負(fù)載與節(jié)點(diǎn)程度有關(guān)，但是由于模型忽略了節(jié)點(diǎn)在網(wǎng)絡(luò)流量中的作用，其不能正確反映無線傳感器網(wǎng)絡(luò)的流量特征。在實(shí)際的無線傳感器網(wǎng)絡(luò)中，每個數(shù)據(jù)包都會生成傳感器節(jié)點(diǎn)，并最終聚集在接收節(jié)點(diǎn)上，這使得網(wǎng)絡(luò)流量以匯聚特征得以表現(xiàn)。文獻(xiàn)[8]指出當(dāng)傳感器節(jié)點(diǎn)超出其負(fù)載能力時將過載，但是由于模型沒有考慮無線鏈路的容量，從而無法揭示無線傳感器網(wǎng)絡(luò)級聯(lián)過程的本質(zhì)現(xiàn)象。

在無線傳感器網(wǎng)絡(luò)級聯(lián)故障研究方面，文獻(xiàn)[9]提出了一種負(fù)載－容量模型，該模型定義每個節(jié)點(diǎn)均擁有一定容量并承擔(dān)相關(guān)負(fù)載，當(dāng)節(jié)點(diǎn)發(fā)生失效行為時，該節(jié)點(diǎn)所承擔(dān)的負(fù)載按照預(yù)設(shè)規(guī)則轉(zhuǎn)移至網(wǎng)絡(luò)中剩余其他節(jié)點(diǎn)，而其他節(jié)點(diǎn)也將可能因負(fù)載超出自身容量而導(dǎo)致失效，并引發(fā)新一輪的負(fù)載轉(zhuǎn)移，后續(xù)諸如CASCADE模型、OPA模型、DC-Flow模型和RENEW模型等均是在負(fù)載－容量模型基礎(chǔ)之上發(fā)展而來的?，F(xiàn)實(shí)世界中，不同類型網(wǎng)絡(luò)所對應(yīng)的級聯(lián)故障情形各不相同，研究表明輸配電網(wǎng)絡(luò)、物流保障網(wǎng)絡(luò)、交通網(wǎng)絡(luò)及因特網(wǎng)等均具有明顯的級聯(lián)失效特征且彼此間具有明顯的差異性。文獻(xiàn)[10]根據(jù)節(jié)點(diǎn)可變負(fù)載與恒定容量等特點(diǎn)，針對WSN無標(biāo)度拓?fù)湔归_研究，得到度分布指數(shù)和冪律系數(shù)與WSN容錯性能呈正相關(guān)；文獻(xiàn)[11]則在此研究基礎(chǔ)上，借助概率母函數(shù)法求解WSN無標(biāo)度拓?fù)浼壜?lián)失效的臨界負(fù)載值。盡管現(xiàn)有WSN級聯(lián)失效研究取得了一定成果，然而在現(xiàn)實(shí)情形中，由于受網(wǎng)絡(luò)規(guī)模和能耗限制，多數(shù)WSN均采用典型的分簇結(jié)構(gòu)進(jìn)行數(shù)據(jù)采集與傳遞，現(xiàn)有的WSN級聯(lián)失效研究對于此類情況并不適用。

鑒于此，本文建立了一種受節(jié)點(diǎn)容量和鏈路容量限制的無線傳感器網(wǎng)絡(luò)級聯(lián)故障模型，旨在通過構(gòu)建網(wǎng)絡(luò)級聯(lián)抗毀性模型，使故障節(jié)點(diǎn)可在一定時間延遲后從故障狀態(tài)恢復(fù)，從而提高網(wǎng)絡(luò)穩(wěn)定性。

1 問題描述

在不失一般性的前提下，提出了如圖1所示的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)。由圖1可知，該結(jié)構(gòu)包括300個傳感器節(jié)點(diǎn)，宿節(jié)點(diǎn)位于網(wǎng)絡(luò)中心。在無線傳感器網(wǎng)絡(luò)中，傳感器節(jié)點(diǎn)有兩個任務(wù):一是傳輸由自身創(chuàng)建的數(shù)據(jù)包，二是轉(zhuǎn)發(fā)來自其他傳感器節(jié)點(diǎn)的中繼數(shù)據(jù)包，然后所有數(shù)據(jù)包最終聚集在宿節(jié)點(diǎn)。圖2表示由LEACH生成的網(wǎng)絡(luò)流量分布圖，從圖中可以看到接近宿節(jié)點(diǎn)的傳感器節(jié)點(diǎn)具有更大的流量負(fù)載。圖3表示由度和介數(shù)創(chuàng)建的網(wǎng)絡(luò)流量分布圖。

圖1 參考的網(wǎng)絡(luò)拓?fù)?/p>

圖2 LEACH路由協(xié)議生成的網(wǎng)絡(luò)流量的分布

圖3 網(wǎng)絡(luò)流量分布圖

如圖3所示，為度和介數(shù)生成的網(wǎng)絡(luò)流量分布圖。其中，圖3(a)中，傳感器節(jié)點(diǎn)的連接越多，其負(fù)載往往越大，由此可知由節(jié)點(diǎn)度產(chǎn)生的流量分布只能反映鄰近區(qū)域的流量交換；圖3(b)中，在網(wǎng)絡(luò)中每對傳感器節(jié)點(diǎn)之間維持大量最短路徑的節(jié)點(diǎn)，將承受更大負(fù)荷的網(wǎng)絡(luò)負(fù)載。因此，在基于網(wǎng)際網(wǎng)絡(luò)的負(fù)載模型中，僅假設(shè)數(shù)據(jù)包是從一個傳感器節(jié)點(diǎn)，傳遞到另一個傳感器節(jié)點(diǎn)，而不是從源傳感器節(jié)點(diǎn)傳遞到宿節(jié)點(diǎn)。

此外，當(dāng)前WSN級聯(lián)故障模型僅考慮了節(jié)點(diǎn)的容量，沒有考慮鏈路受限的情況，而節(jié)點(diǎn)到鏈路的容量因素也會對WSN流量分布產(chǎn)生重要影響。而現(xiàn)有模型過于簡化了負(fù)載和容量，導(dǎo)致獲得結(jié)果與實(shí)際偏差較大。另外，現(xiàn)有模型主要關(guān)注節(jié)點(diǎn)攻擊引起的級聯(lián)過程，實(shí)際上與由硬件故障引起的節(jié)點(diǎn)故障相比，WSN中的鏈路故障更常見。當(dāng)發(fā)生鏈路故障時，鏈路負(fù)載將會重新分配，網(wǎng)絡(luò)中的流量分配將得到更新，并且如果有任何傳感器節(jié)點(diǎn)變?yōu)檫^載狀態(tài)，級聯(lián)故障將會繼續(xù)，因此無線傳感器網(wǎng)絡(luò)的抗毀性評估是十分必要的。

2 方向介數(shù)原理

為正確反映WSN的流量特征，為WSN提出了一種新的流量度量“方向介數(shù)”，如式(1)所示[12]:

式中，gi，j(t)為在時間t經(jīng)過節(jié)點(diǎn)i從節(jié)點(diǎn)j到宿節(jié)點(diǎn)的最短路徑數(shù)；gj(t)為在時間t從節(jié)點(diǎn)j到宿節(jié)點(diǎn)的最短路徑數(shù)；V是除宿節(jié)點(diǎn)之外的節(jié)點(diǎn)集合；N是除宿節(jié)點(diǎn)以外的傳感器節(jié)點(diǎn)數(shù)。其中，方向之間的最極端情況為，從任何傳感器節(jié)點(diǎn)到宿節(jié)點(diǎn)的最短路徑中每條路徑都會經(jīng)過節(jié)點(diǎn)i，此時Ci(t)將為最大值1。當(dāng)節(jié)點(diǎn)i位于網(wǎng)絡(luò)邊界，且沒有節(jié)點(diǎn)要求它中繼數(shù)據(jù)包時，其承擔(dān)的負(fù)載只是其自身生成的數(shù)據(jù)包，此時Ci(t)將為最小值1/N。傳統(tǒng)的介數(shù)主要用來量化一個節(jié)點(diǎn)沿著其他兩個節(jié)點(diǎn)之間的最短路徑的橋接次數(shù)，而方向介數(shù)是用來量化一個節(jié)點(diǎn)沿著所有其他節(jié)點(diǎn)到接收器節(jié)點(diǎn)之間的最短路徑橋接次數(shù)。

在不失一般性的前提下，選擇WSN中最常用的網(wǎng)絡(luò)結(jié)構(gòu)，如圖4所示。表1為圖4中通過度、介數(shù)和方向介數(shù)來測量的網(wǎng)絡(luò)通信量。由圖4可知，在該網(wǎng)絡(luò)拓?fù)渲校總€節(jié)點(diǎn)都必須經(jīng)過節(jié)點(diǎn)1才能到達(dá)宿節(jié)點(diǎn)。因此，可以合理地認(rèn)為整個網(wǎng)絡(luò)流量將通過節(jié)點(diǎn)1。除了自行生成的數(shù)據(jù)包外，還需要節(jié)點(diǎn)2和節(jié)點(diǎn)3分別中繼來自5個節(jié)點(diǎn)的數(shù)據(jù)包。由此可知，幾乎有一半的網(wǎng)絡(luò)流量將通過節(jié)點(diǎn)2和節(jié)點(diǎn)3，而其余傳感器節(jié)點(diǎn)不承擔(dān)任何中繼任務(wù)，且其承擔(dān)的唯一負(fù)載是自身負(fù)載。根據(jù)表1可知，方向介數(shù)完美地描述了上述流量分配功能，而度和介數(shù)都無法反映這一特征。

圖4 WSN集群結(jié)構(gòu)示例圖

表1 網(wǎng)絡(luò)流量分布表

如圖5所示，為通過方向介數(shù)創(chuàng)建的網(wǎng)絡(luò)流量的分布圖。由圖可知，WSN中的匯聚收斂功能與圖2中的流量分布非常相似，表明無線傳感器網(wǎng)絡(luò)方向之間的合理性得到進(jìn)一步驗(yàn)證。

圖5 方向介數(shù)產(chǎn)生的網(wǎng)絡(luò)流量分布

3 WSN級聯(lián)故障模型構(gòu)建

3.1 網(wǎng)絡(luò)假設(shè)

WSN可以用無向圖G＝(V，E)來描述，其中V＝{vi｜i＝1，2，…，N}是傳感器節(jié)點(diǎn)的集合，而E＝{eij｜i＝j(luò)，vi∈V，vj∈V}是節(jié)點(diǎn)之間的無線鏈路的集合。如果節(jié)點(diǎn)i和節(jié)點(diǎn)j之間存在鏈接，則N×N鄰階矩陣[aij]的aij＝1，否則aij＝0。

在不失一般性的前提下，假設(shè)WSN中的所有傳感器節(jié)點(diǎn)都具有同時生成和轉(zhuǎn)發(fā)數(shù)據(jù)包的能力。每個傳感器節(jié)點(diǎn)的數(shù)據(jù)處理能力取決于其緩存資源和帶寬資源。他們在每個時間單位只能處理一定數(shù)量的數(shù)據(jù)包。如果節(jié)點(diǎn)緩存中的待辦事項(xiàng)數(shù)據(jù)包超出了其數(shù)據(jù)處理能力，則在此時間單位無法處理的數(shù)據(jù)包將保留到下一個時間單位。

3.2 網(wǎng)絡(luò)負(fù)載

在無線傳感器網(wǎng)絡(luò)中大多數(shù)的傳感器節(jié)點(diǎn)具有多個鏈路，這意味著它們需要處理來自其相鄰節(jié)點(diǎn)的多路徑數(shù)據(jù)流量。根據(jù)數(shù)據(jù)流的方向可以將其分類為兩種類型:輸入數(shù)據(jù)流量和輸出數(shù)據(jù)流量。以圖4所示的流量分布圖為例，節(jié)點(diǎn)2具有1、4、5、6、7和8六個相鄰的節(jié)點(diǎn)，分別接收來自相鄰節(jié)點(diǎn)4、5、6、7和8的流量負(fù)載De24、De25、De26、De27、De28。由于這些數(shù)據(jù)流量將輸入到節(jié)點(diǎn)中2的緩存中，即定義為節(jié)點(diǎn)2的輸入數(shù)據(jù)流量。節(jié)點(diǎn)2將流量負(fù)載De12傳輸?shù)焦?jié)點(diǎn)1，并最終傳輸?shù)剿薰?jié)點(diǎn)，即流量負(fù)載De12可定義為從節(jié)點(diǎn)2到節(jié)點(diǎn)1的輸出數(shù)據(jù)流量，也可以定義為節(jié)點(diǎn)1的輸入數(shù)據(jù)流量。通常情況下，總的輸入流量負(fù)載和自身負(fù)載應(yīng)等于輸出流量負(fù)載，但是當(dāng)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)更改后，輸出流量可能會小于輸入流量負(fù)載和自身負(fù)載。在這種情況下數(shù)據(jù)包無法及時得到傳輸并會堆積在緩存中，經(jīng)過多輪數(shù)據(jù)積累后節(jié)點(diǎn)最終將過載。

為了清楚地描述WSN的級聯(lián)過程，節(jié)點(diǎn)i在時間t的負(fù)載Li(t)如式(2)~式(6)所示[13]:

3.3 網(wǎng)絡(luò)容量

節(jié)點(diǎn)的容量與初始負(fù)載呈正相關(guān)關(guān)系，如式(7)所示[14－15]:

式中，α表示過載公差系數(shù)，Li(0)表示節(jié)點(diǎn)i的初始負(fù)載。但是在WSN中該設(shè)置與實(shí)際情況相差很大，出現(xiàn)這種情況，一方面是由于大多數(shù)情況下相同傳感器網(wǎng)絡(luò)的節(jié)點(diǎn)硬件配置是相同的，另一方面是由于在部署了數(shù)百甚至數(shù)千個傳感器節(jié)點(diǎn)時無法自定義節(jié)點(diǎn)的容量。鏈路容量是影響WSN級聯(lián)過程的關(guān)鍵因素，并且現(xiàn)有的所有研究都沒有考慮WSN中鏈路容量因素的影響。本文利用方向介數(shù)來度量鏈路容量，結(jié)合式(1)和式(7)將鏈路容量UL定義為式(8)所示，其中Dejk(0)為ejk在初始時間處的方向介數(shù)；λl為鏈路公差系數(shù)。此時網(wǎng)絡(luò)的初始方向介數(shù)的負(fù)載可由初始時間處的鏈路容量表示，如式(9)所示，其中λn為節(jié)點(diǎn)公差系數(shù)；表示網(wǎng)絡(luò)初始平均程度。

從式(8)和式(9)可以看出，每個傳感器節(jié)點(diǎn)具有相同的鏈路容量和節(jié)點(diǎn)容量，且與初始方向介數(shù)的平均負(fù)載呈正相關(guān)關(guān)系。

3.4 級聯(lián)機(jī)制

現(xiàn)有級聯(lián)故障模型中，傳感器節(jié)點(diǎn)具有正常和過載兩種狀態(tài)。對于WSN而言，當(dāng)流量負(fù)載足夠大時，越來越多的數(shù)據(jù)包將無法及時傳遞，并且隨著時間的推移會在許多中央節(jié)點(diǎn)上進(jìn)行積累，從而出現(xiàn)網(wǎng)絡(luò)擁塞。網(wǎng)絡(luò)擁塞是由于網(wǎng)絡(luò)中的路由節(jié)點(diǎn)負(fù)載過度，導(dǎo)致網(wǎng)絡(luò)性能下降，并且是網(wǎng)絡(luò)處于持續(xù)過載的狀態(tài)。因?yàn)闊o線傳感器網(wǎng)絡(luò)是分組交換網(wǎng)絡(luò)，所以上述定義在無線傳感器網(wǎng)絡(luò)中也適用。如圖6所示為網(wǎng)絡(luò)擁塞圖，當(dāng)網(wǎng)絡(luò)負(fù)載較低時，網(wǎng)絡(luò)中傳輸?shù)姆纸M與網(wǎng)絡(luò)發(fā)送分組成正比，這時網(wǎng)絡(luò)時延最小。隨著網(wǎng)絡(luò)負(fù)載的增加，網(wǎng)絡(luò)中傳感器節(jié)點(diǎn)不能及時將分組轉(zhuǎn)發(fā)出去，導(dǎo)致網(wǎng)絡(luò)的丟包率增加、吞吐量下降和分組的時延變大。當(dāng)無線傳感器網(wǎng)絡(luò)的負(fù)載量超過網(wǎng)絡(luò)的處理能力時，導(dǎo)致數(shù)據(jù)包丟失、網(wǎng)絡(luò)吞吐量下降，并增加時延。和傳統(tǒng)有線網(wǎng)絡(luò)、無線網(wǎng)絡(luò)一樣，無線傳感器網(wǎng)絡(luò)發(fā)生擁塞以后也會導(dǎo)致網(wǎng)絡(luò)性能下降，無法保證無線傳感器網(wǎng)絡(luò)的服務(wù)質(zhì)量。

圖6 網(wǎng)絡(luò)擁塞圖

在本文模型中，針對WSN網(wǎng)絡(luò)擁塞，需要首先為每個傳感器節(jié)點(diǎn)定義一個擁塞函數(shù)，如式(10)所示:

式中，β是擁塞的容忍系數(shù)，表示正常狀態(tài)和擁塞狀態(tài)間的調(diào)整閾值，其值與傳感器節(jié)點(diǎn)的資源有關(guān)。

當(dāng)Li(t)<(1－β)W(i)時，該節(jié)點(diǎn)處于正常狀態(tài)，表明傳感器可以正常工作。當(dāng)Li(t)處于[(1－β)W(i)，W(i)]范圍內(nèi)時，該節(jié)點(diǎn)處于擁塞狀態(tài)，表明傳感器仍可以接收和發(fā)送數(shù)據(jù)包，但其處理能力將會相應(yīng)減弱。當(dāng)Li(t)>W(i)，該節(jié)點(diǎn)處于過載狀態(tài)，表明該節(jié)點(diǎn)暫時無法運(yùn)行。在該狀態(tài)下，節(jié)點(diǎn)將被賦予恢復(fù)時間Δt。

在Δt時間內(nèi)，該節(jié)點(diǎn)無法接收、處理和傳輸數(shù)據(jù)包，且緩存中的現(xiàn)有數(shù)據(jù)包也將被清除。當(dāng)Δt過期時，該節(jié)點(diǎn)將再次變?yōu)檎顟B(tài)。實(shí)際上，可以將t視為過載節(jié)點(diǎn)，并重新啟動所需的時間。在實(shí)際的WSN中，傳感器節(jié)點(diǎn)將在過載時重新啟動而不是永久刪除，且緩存也將被清除。重新啟動完成后，傳感器節(jié)點(diǎn)將加入網(wǎng)絡(luò)并正常運(yùn)行，對無線傳感器網(wǎng)絡(luò)的級聯(lián)過程具有重大影響。當(dāng)Δt接近0時，表明過載節(jié)點(diǎn)可以立即恢復(fù)，因此由過載引起的損害將最小化；若Δt接近∞，則所提級聯(lián)方案等效于傳統(tǒng)的永久刪除方案。若節(jié)點(diǎn)的所有鄰居都過載，即使其負(fù)載在容量范圍內(nèi)，由于該節(jié)點(diǎn)與宿節(jié)點(diǎn)之間的傳遞路徑被切斷，仍無法將數(shù)據(jù)包傳輸?shù)剿薰?jié)點(diǎn)，此時此類節(jié)點(diǎn)被稱為隔離節(jié)點(diǎn)。當(dāng)部分相鄰節(jié)點(diǎn)從過載中恢復(fù)，并且到宿節(jié)點(diǎn)的有效路徑出現(xiàn)時，隔離的節(jié)點(diǎn)可以被修復(fù)。如圖7所示，為級聯(lián)過程中傳感器節(jié)點(diǎn)的狀態(tài)轉(zhuǎn)換圖。

圖7 級聯(lián)過程中傳感器節(jié)點(diǎn)的狀態(tài)轉(zhuǎn)換

3.5 擁塞感知路由恢復(fù)機(jī)制

根據(jù)本文的級聯(lián)機(jī)制，過載的傳感器節(jié)點(diǎn)可以通過重新啟動進(jìn)行自我恢復(fù)，但是重新啟動后，如果仍然遵循最初的路由機(jī)制，它們將在一段時間后再次過載。因此有必要設(shè)計一種路由恢復(fù)機(jī)制來防止過載的節(jié)點(diǎn)不會進(jìn)入“重啟循環(huán)”狀態(tài)。為了恢復(fù)故障節(jié)點(diǎn)，傳統(tǒng)的模型通常選擇擁塞值之和最小的鏈路，這些恢復(fù)解決方案只能在節(jié)點(diǎn)具有全局擁塞狀態(tài)信息時有效。然而在無線傳感器網(wǎng)絡(luò)中，傳感器節(jié)點(diǎn)以分布式方式組織，每個傳感器節(jié)點(diǎn)不可能實(shí)時知道其他節(jié)點(diǎn)的擁塞狀態(tài)。因此本文提出了一種局部擁塞感知的路由恢復(fù)機(jī)制，即當(dāng)傳感器節(jié)點(diǎn)正常工作時，會遵循原來的路由機(jī)制，當(dāng)發(fā)生過載時，將遵循路由恢復(fù)機(jī)制。在這個機(jī)制中每個傳感器均有一個Ui(t)，表示如下:

式中，di(t)表示節(jié)點(diǎn)i在時間t的深度，當(dāng)傳感器節(jié)點(diǎn)需要轉(zhuǎn)發(fā)中繼數(shù)據(jù)包時，它將從相鄰節(jié)點(diǎn)中選擇最大的Ui(t)節(jié)點(diǎn)作為下一個躍點(diǎn)。

4 實(shí)驗(yàn)結(jié)果與分析

4.1 抗毀性指標(biāo)

本節(jié)定義的兩個指標(biāo)分別為網(wǎng)絡(luò)效率Ug(t)和正常節(jié)點(diǎn)比例Hn(t)。在現(xiàn)有的在模型中，網(wǎng)絡(luò)效率Ug定義為其中dij表示節(jié)點(diǎn)i和節(jié)點(diǎn)j之間的最短路徑。但是該定義不能正確反映出無線傳感器網(wǎng)絡(luò)的匯聚特性。由于在傳感器網(wǎng)絡(luò)中用戶更加關(guān)注普通傳感器節(jié)點(diǎn)傳遞消息的效率，通常在傳感器網(wǎng)絡(luò)中，用戶更加關(guān)注從公用傳感器節(jié)點(diǎn)到接收器的消息傳遞效率。因此，網(wǎng)絡(luò)效率Ug(t)是從任何傳感器節(jié)點(diǎn)到宿節(jié)點(diǎn)的最短路徑的效率的平均值，如式(12)所示:

式中，di(t)表示時間t內(nèi)節(jié)點(diǎn)i到宿節(jié)點(diǎn)的最短路徑數(shù)量。與大多數(shù)現(xiàn)有模型不同的是，本文所建立的方法將與宿節(jié)點(diǎn)保持有效連接的節(jié)點(diǎn)視為正常節(jié)點(diǎn)，正常節(jié)點(diǎn)的比例Hn(t)如式(13)所示:

式中，Nn(t)表示時間t內(nèi)的正常節(jié)點(diǎn)數(shù)量。在這里用Ug(∞)和Hn(∞)表示當(dāng)網(wǎng)絡(luò)發(fā)生級聯(lián)故障后達(dá)到穩(wěn)態(tài)時的網(wǎng)絡(luò)效率和正常節(jié)點(diǎn)比例。

4.2 模擬設(shè)置

在大多數(shù)級聯(lián)故障模型中，級聯(lián)故障在傳感器節(jié)點(diǎn)受到前q%的初始攻擊時會被觸發(fā)，然而與由硬件故障引起的節(jié)點(diǎn)故障相比，鏈路故障更可能是由于較少的無線傳輸引起的。

本文利用MATLAB 8.0進(jìn)行了仿真模擬，建立的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)模型中有300個傳感器節(jié)點(diǎn)，分布在300 m×300 m的區(qū)域。宿節(jié)點(diǎn)位于區(qū)域中心，無線傳輸半徑設(shè)置為30 m，初始攻擊設(shè)置為前10%的鏈路，為了確保級聯(lián)故障是由故意攻擊觸發(fā)的，攻擊之前假設(shè)初始網(wǎng)絡(luò)中的每個節(jié)點(diǎn)都是正常的。

4.3 抗毀性指標(biāo)分析

為了便于描述，分別使用GNE和GPNN表示常規(guī)網(wǎng)絡(luò)效率和常規(guī)正常節(jié)點(diǎn)比例，使用NE和PNN表示本文提出的網(wǎng)絡(luò)效率和正常節(jié)點(diǎn)比例。圖8展示了四種網(wǎng)絡(luò)拓?fù)淝樾?。情?表示初始拓?fù)浣Y(jié)構(gòu)沒有節(jié)點(diǎn)故障，其他三種情形中存在一定數(shù)量的節(jié)點(diǎn)故障，四種情形的詳細(xì)信息如表2所示。

表2 4種情形的詳細(xì)參數(shù)

從圖8(a)中可以看出，由于沒有節(jié)點(diǎn)故障第1種情形的網(wǎng)絡(luò)連接是最優(yōu)的。在圖8(b)中，由于宿節(jié)點(diǎn)周圍的節(jié)點(diǎn)發(fā)生故障，各個節(jié)點(diǎn)與宿節(jié)點(diǎn)之間的所有路徑都被中斷，導(dǎo)致傳感器節(jié)點(diǎn)無法再將數(shù)據(jù)傳遞到宿節(jié)點(diǎn)，那么可以合理地假設(shè)網(wǎng)絡(luò)完全癱瘓了。在圖8(c)中，仍然有少量節(jié)點(diǎn)可以保持與宿節(jié)點(diǎn)的有效連接。在圖8(d)中，盡管到宿節(jié)點(diǎn)的網(wǎng)絡(luò)連接不受影響，但由于部分節(jié)點(diǎn)故障導(dǎo)致路由的傳輸成本和傳輸時間增加。(虛線圓節(jié)點(diǎn)是從網(wǎng)絡(luò)中移除的節(jié)點(diǎn))

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

4.4 關(guān)鍵參數(shù)的影響

4.4.1 鏈路公差系數(shù)λl的影響

圖9表示鏈路公差系數(shù)λl變化下正常節(jié)點(diǎn)Hn(t)的比例。從圖中可以看出隨著λl的增大，Hn(t)顯著增加，當(dāng)λl＝0.5時，網(wǎng)絡(luò)在t＝5時達(dá)到穩(wěn)態(tài)，且只有22%的傳感器節(jié)點(diǎn)能夠存活。當(dāng)λl增加到2時，網(wǎng)絡(luò)在t＝1時達(dá)到穩(wěn)定狀態(tài)，83%的傳感器節(jié)點(diǎn)能夠存活。顯然λl越高，傳感器節(jié)點(diǎn)傳輸數(shù)據(jù)包的容量越大，流量負(fù)載不會堆積在緩存中，過載風(fēng)險就可以得到顯著緩解。

圖9 λl變化下正常節(jié)點(diǎn)的比例(λn＝0.5，Δt＝∞)

圖10 表示當(dāng)級聯(lián)過程達(dá)到穩(wěn)態(tài)時異常節(jié)點(diǎn)的組成。從圖中可以看出隨著λl的增大，過載節(jié)點(diǎn)的比例將顯著下降。當(dāng)λl＝0.5時，可以看到62%的節(jié)點(diǎn)因“被隔離”而不能正常工作。相比之下只有16%節(jié)點(diǎn)過載時處于故障狀態(tài)。當(dāng)λl＝2時，被隔離是導(dǎo)致節(jié)點(diǎn)故障的唯一原因。此時鏈路容量只有足夠強(qiáng)大應(yīng)對蓄意攻擊造成的流量變化時，級聯(lián)過程才不會被觸發(fā)。這也解釋了為什么當(dāng)λl＝2的網(wǎng)絡(luò)在t＝1時能夠達(dá)到穩(wěn)態(tài)，即可以得出λl有一個可使網(wǎng)絡(luò)不受級聯(lián)故障影響的閾值。

圖10 λl變化下異常節(jié)點(diǎn)的組成(λn＝0.5，Δt＝∞)

如圖11所示，隨著λl的增大，網(wǎng)絡(luò)效率Ug(t)將顯著提高。當(dāng)λl＝0.5時，Ug(t)將會穩(wěn)定在0.012左右，這意味著信息傳遞嚴(yán)重延遲。當(dāng)λl增大到2時，Ug(t)將穩(wěn)定在0.123左右。此時大多數(shù)路由都可以生存，網(wǎng)絡(luò)效率仍然可以得到保證，這是因?yàn)棣薼越高，生存節(jié)點(diǎn)越多，更多的路由被保留而不是被切斷了。

圖11 λl變化下的網(wǎng)絡(luò)效率(λn＝0.5，Δt＝∞)

4.4.2 節(jié)點(diǎn)公差系數(shù)λn的影響

圖12表示節(jié)點(diǎn)公差系數(shù)λn變化下正常節(jié)點(diǎn)Hn(t)的比例。從圖中可以看出λn的增大不能降低由級聯(lián)故障引起的損害程度，但它可以推遲級聯(lián)過程發(fā)生。當(dāng)λn＝0.5時，將在下一步攻擊之后觸發(fā)級聯(lián)過程；當(dāng)λn增大到2時，級聯(lián)過程將從t＝4開始；λn越大，緩存資源的改善越明顯，但當(dāng)輸出流量超過帶寬容量時，不能緩解數(shù)據(jù)包的堆積，當(dāng)數(shù)據(jù)包發(fā)生堆積時，節(jié)點(diǎn)將在某些一時刻產(chǎn)生過載。

圖12 λn變化下正常節(jié)點(diǎn)的比例(λn＝0.5，Δt＝∞)

如圖13所示，λn的增加只會推遲級聯(lián)過程中，不能改善級聯(lián)網(wǎng)絡(luò)故障的抗毀性。由于λn的增加無法將更多傳感器節(jié)點(diǎn)從故障狀態(tài)中解救出來，消息傳遞路徑不會加強(qiáng)，因此網(wǎng)絡(luò)效率將保持不變。

圖13 λn變化下的網(wǎng)絡(luò)效率(λn＝0.5，Δt＝∞)

本文模型中λn主要表示傳感器節(jié)點(diǎn)具有緩存資源。因此當(dāng)傳感器節(jié)點(diǎn)不能從超負(fù)荷(Δt＝∞)中恢復(fù)時，提供更多的緩存資源也無法對級聯(lián)故障產(chǎn)生有益作用。

4.4.3λn和λl之間的關(guān)系

如圖14所示，隨著λl的增加，網(wǎng)絡(luò)傳輸從低Hn(∞)階段(左側(cè))過渡到高Hn(∞)階段(右側(cè))，相變的閾值λl?大約為1.7。因此為了設(shè)計抗毀性優(yōu)異的級聯(lián)網(wǎng)絡(luò)，λl應(yīng)盡可能設(shè)置接近于閾值λl?。當(dāng)?shù)闹颠^大時將導(dǎo)致帶寬資源的浪費(fèi)，而當(dāng)λl?的值過小時級聯(lián)網(wǎng)絡(luò)的抗毀性較差。此外當(dāng)Δt＝∞時，網(wǎng)絡(luò)的抗毀性不隨λn的增加而有所改善。

圖14 [λn，λl]參數(shù)空間內(nèi)的Hn(∞)波動圖

如圖15所示，隨著λl的增大，網(wǎng)絡(luò)傳輸從低Ug(∞)階段(左側(cè))到高Ug(∞)階段(右側(cè))，相變的閾值仍為1.7。

圖15 [λn，λl]參數(shù)空間內(nèi)的Ug(∞)波動圖

4.4.4 恢復(fù)時間Δt的影響

圖16表示恢復(fù)時間Δt對正常節(jié)點(diǎn)比例的影響。從圖中可以看出，隨著時間Δt的增加，Hn(t)的推移波動加大。當(dāng)Δt＝1時，傳感器節(jié)點(diǎn)可以在下一時間從故障中恢復(fù)，因此Hn(t)波動較為平緩，當(dāng)Δt＝3時，Hn(t)波動程度高于35%，當(dāng)Δt＝∞時，傳感器節(jié)點(diǎn)失去恢復(fù)能力，Hn(t)將為一個穩(wěn)態(tài)值。

圖16 Δt變化下正常節(jié)點(diǎn)的比例(λn＝λl＝0.5)

如圖17所示，類似于Δt對Hn(t)的影響，隨著Δt的增加，Ug(t)的波動水平加大，當(dāng)Δt＝1時，Ug(t)約為0.06，當(dāng)Δt增加到3時，Ug(t)在[0.021，0.065]之間，當(dāng)Δt＝∞時，Ug(t)單調(diào)遞減穩(wěn)定在0.012左右。

圖17 Δt變化下的網(wǎng)絡(luò)效率(λn＝λl＝0.5)

4.4.5λn和Δt之間的關(guān)系

當(dāng)Δt＝∞時(即節(jié)點(diǎn)不能從過載中恢復(fù))，節(jié)點(diǎn)容忍系數(shù)λn只能延遲級聯(lián)過程發(fā)生，不能減少級聯(lián)故障造成的損失。但是如果允許過載節(jié)點(diǎn)在一定的時間內(nèi)發(fā)生延遲，λn的影響也會發(fā)生變化。

如圖18所示，當(dāng)傳感器節(jié)點(diǎn)可恢復(fù)時，λn的增加可以減少級聯(lián)故障造成的損失，降低Hn(t)的波動水平。例如，在Δt＝2時，λn＝0.5時，Hn(t)的范圍為[45%，68%]，當(dāng)λn增加到1時，Hn(t)的波動范圍縮小到[54%，67%]，如果λn繼續(xù)增加到2，可以發(fā)現(xiàn)Hn(t)趨于穩(wěn)定值67%，則可以得出λ?n存在一個閾值。根據(jù)級聯(lián)機(jī)制，對于一個傳感器節(jié)點(diǎn)，如果輸入數(shù)據(jù)流量和自身數(shù)據(jù)流量大于鏈路容量，則不是所有的數(shù)據(jù)包都能被處理，并且部分?jǐn)?shù)據(jù)將堆積在緩存中，經(jīng)過多次循環(huán)后節(jié)點(diǎn)將變?yōu)檫^載狀態(tài)。并且一個傳感器節(jié)點(diǎn)從正常狀態(tài)切換到過載狀態(tài)需要一個持續(xù)時間Δts。為了便于描述，本文定義了故障節(jié)點(diǎn)和受影響節(jié)點(diǎn)。故障節(jié)點(diǎn)指由于過載原因?qū)е碌墓?jié)點(diǎn)失效，受影響節(jié)點(diǎn)指受其他故障節(jié)點(diǎn)影響的節(jié)點(diǎn)。則如果Δts≥Δt，當(dāng)失效節(jié)點(diǎn)恢復(fù)時，受影響節(jié)點(diǎn)仍未過載，且級聯(lián)故障不會進(jìn)一步擴(kuò)散；如果Δts<Δt，受影響的節(jié)點(diǎn)將在故障節(jié)點(diǎn)恢復(fù)之前過載，級聯(lián)進(jìn)程將繼續(xù)下去，并將出現(xiàn)新一輪的級聯(lián)故障。

圖18 Δt和λn變化下正常節(jié)點(diǎn)比例

如圖19所示，隨著λn的增大，Hn(t)的波動水平趨于減小，當(dāng)λn達(dá)到某一閾值λn?時，Hn(t)達(dá)到穩(wěn)定狀態(tài)。此外，λn?隨延遲時間Δt的增加而增加，因此為了防止級聯(lián)故障擴(kuò)散，Δts需要變的更長，λn?需要更大。

圖19 Δt和λn變化下H n(t)的波動水平

4.5 對比實(shí)驗(yàn)分析

為了驗(yàn)證本文所提模型的有效性，選擇了基于介數(shù)的模型和基于度的模型與本文所構(gòu)建的模型進(jìn)行了性能對比。模型中設(shè)置λn＝λl＝0.5，Δt＝∞，由于這些模型使用不同的流量度量，觸發(fā)條件也應(yīng)該不同，為保證統(tǒng)一性，三種模型均按照前5%的節(jié)點(diǎn)攻擊進(jìn)行考慮。

如圖20所示，在基于度的模型中級聯(lián)故障造成的后果最嚴(yán)重，在t＝5時89%的傳感器節(jié)點(diǎn)進(jìn)入故障狀態(tài)。這是因?yàn)樵诨诙鹊哪Ｐ椭?，流量?fù)載使得級聯(lián)故障更容易通過相鄰節(jié)點(diǎn)進(jìn)行傳播。同時可以看出本文所構(gòu)建的模型比基于介數(shù)的模型引發(fā)的故障更嚴(yán)重，基于介數(shù)的模型中有78%的節(jié)點(diǎn)可以存活，而本文所構(gòu)建的模型中有71%的節(jié)點(diǎn)能夠存活，僅略微少于基于介數(shù)的模型。另外，本文所構(gòu)建的模型中，交通流量表示從任何傳感器節(jié)點(diǎn)到宿節(jié)點(diǎn)的最短路徑數(shù)，從而使數(shù)據(jù)流更多地集中在宿節(jié)點(diǎn)附近的關(guān)鍵節(jié)點(diǎn)上，當(dāng)這些關(guān)鍵節(jié)點(diǎn)受到攻擊時流量負(fù)載會發(fā)生變化，然后進(jìn)一步導(dǎo)致更大規(guī)模的級聯(lián)故障。

圖20 三種模型的正常節(jié)點(diǎn)比例

圖21表示當(dāng)t＝10時故障節(jié)點(diǎn)的組成。此時，三種模型的網(wǎng)絡(luò)級聯(lián)過程均能達(dá)到穩(wěn)態(tài)。本文所構(gòu)建的模型中節(jié)點(diǎn)的隔離主要由節(jié)點(diǎn)故障引起，在另外兩個模型中，過載節(jié)點(diǎn)和隔離節(jié)點(diǎn)的故障相似。這是由于本文所構(gòu)建的模型中，由于流量負(fù)載具有匯聚特性，重新分配的負(fù)載將更專注于宿節(jié)點(diǎn)附近的節(jié)點(diǎn)，一小部分過載節(jié)點(diǎn)會嚴(yán)重影響網(wǎng)絡(luò)的連通性并會引起大量的傳感器故障，從而形成隔離節(jié)點(diǎn)。

圖21 t＝10時故障節(jié)點(diǎn)的組成

4.6 路由恢復(fù)機(jī)制的性能

對于評估路由的恢復(fù)機(jī)制性能，本節(jié)設(shè)計了兩種情況:①λl＝λn＝0.5，Δt＝2；②λl＝λn＝0.5，Δt＝∞。如圖22所示，情形1中沒有恢復(fù)機(jī)制，正常節(jié)點(diǎn)比例Hn(t)將在一段時間內(nèi)減少到45%，然后在[45%，68%]之間波動。當(dāng)引入恢復(fù)機(jī)制后，Hn(t)明顯下降，并在一段時間內(nèi)恢復(fù)達(dá)到100%。情形2中通過引入恢復(fù)機(jī)制，Hn(t)在t＝5時即恢復(fù)到100%。同時從圖23中可以看出，本文所提出的路由恢復(fù)性能在網(wǎng)絡(luò)效率方面具有同樣的優(yōu)異性能。

圖22 有/無恢復(fù)機(jī)制的正常節(jié)點(diǎn)比例

圖23 有/無恢復(fù)機(jī)制的網(wǎng)絡(luò)效率

5 結(jié)論

針對當(dāng)前無線傳感器網(wǎng)絡(luò)的級聯(lián)故障模型忽略了鏈路容量影響而導(dǎo)致流量指標(biāo)無法正確的反映網(wǎng)絡(luò)匯聚特征的問題，本文建立了一種受節(jié)點(diǎn)容量和鏈路容量限制的無線傳感器網(wǎng)絡(luò)級聯(lián)故障模型。通過實(shí)驗(yàn)得到:①網(wǎng)絡(luò)的無害性與鏈路容忍系數(shù)λl正相關(guān)；②在傳感器節(jié)點(diǎn)不可恢復(fù)的情況(Δt＝∞)，節(jié)點(diǎn)容差系數(shù)λl的增加只能推遲級聯(lián)過程，而不能減少級聯(lián)故障所造成的損害；③恢復(fù)時間Δt的增加將加劇無線傳感器網(wǎng)絡(luò)中級聯(lián)過程的波動水平。