基于布爾方程與數(shù)據(jù)分析的WSNs鏈路故障恢復(fù)

李振美，王翠平

(1. 濟(jì)寧學(xué)院計算機(jī)科學(xué)系，山東 曲阜 273155；2. 青島大學(xué)電子信息學(xué)院，山東 青島 266071)

1 引言

WSNs包含大量自組織節(jié)點，通過相互感知而實現(xiàn)自主配置[1]。當(dāng)網(wǎng)絡(luò)中發(fā)生鏈路故障，將會對網(wǎng)絡(luò)可用性、可靠性、以及均衡性等產(chǎn)生嚴(yán)重影響[2]。因此，對WSNs鏈路故障的研究至關(guān)重要，其中重點是WSNs鏈路故障的檢測[3]，它是實現(xiàn)故障恢復(fù)的前提保證。文獻(xiàn)[4]根據(jù)WSNs構(gòu)建苯環(huán)模型，并設(shè)計了ALFD-H方法，利用中心節(jié)點的數(shù)據(jù)傳輸完成檢測任務(wù)。該方法有利于降低網(wǎng)絡(luò)能效，但是只能用于完成單向檢測。文獻(xiàn)[5]根據(jù)冗余協(xié)議，將網(wǎng)絡(luò)內(nèi)所有節(jié)點依次作為中心節(jié)點，從而確定鏈路故障位置，這種方法能夠可靠檢測到鏈路與節(jié)點的故障，并進(jìn)行恢復(fù)，但是故障檢測與修復(fù)性能仍有待提高。文獻(xiàn)[6]引入數(shù)據(jù)挖掘，通過對鏈路數(shù)據(jù)的大量分析確定故障。該方法沒有提到鏈路數(shù)據(jù)挖掘時的具體參數(shù)，對于不同協(xié)議與規(guī)模的網(wǎng)絡(luò)將會產(chǎn)生不同的檢測效果。文獻(xiàn)[7]融合直接與間接鏈路分析策略，對具有移動節(jié)點的WSNs進(jìn)行檢測，并通過數(shù)據(jù)分析提高故障識別的準(zhǔn)確度與完整度。由于導(dǎo)致WSNs鏈路故障的原因不只是物理鏈路的問題，還有可能是路由協(xié)議出錯產(chǎn)生的[8]，因此，當(dāng)前研究在鏈路故障判斷時存在一定的誤差。于是，本文首先針對網(wǎng)絡(luò)內(nèi)部節(jié)點的協(xié)作關(guān)系，根據(jù)節(jié)點間彼此的測試信號與參數(shù)構(gòu)建布爾方程模型。考慮到鏈路故障點的精確定位，進(jìn)一步設(shè)計了WSNs鏈路的數(shù)據(jù)分析模型，利用WSNs鏈路結(jié)構(gòu)與參數(shù)計算發(fā)送數(shù)據(jù)量，進(jìn)而求得故障定位，在獲得精確的故障點后，依托故障的準(zhǔn)確檢測對其采取有效恢復(fù)策略。

2 基于布爾方程的WSNs鏈路故障模型

構(gòu)建WSNs鏈路模型，將WSNs中部署的節(jié)點集表示為N，當(dāng)部署方式為圓盤布爾時，對應(yīng)的鏈路表示為VN×L，利用WSNs的節(jié)點與鏈路構(gòu)造無向圖G=(N，V)。在鏈路故障判斷時，所有節(jié)點彼此進(jìn)行測試通信，根據(jù)測試信號的傳遞情況確定鏈路是否存在故障。對于任意節(jié)點u∈N，其路由坐標(biāo)可以描述為(xu，yu)。在路由發(fā)生動態(tài)變化的過程中，需要自動完成鏈路故障的判斷。而對于WSNs而言，由于混合網(wǎng)絡(luò)的發(fā)展，內(nèi)部節(jié)點之間存在不同程度的差異，并導(dǎo)致鏈路特性不一致。因此，根據(jù)能量特征確定節(jié)點通信頻率

(1)

(2)

其中，l為鏈路；p為信號傳遞路徑，每一個信號傳遞路徑都可以看做是一組鏈路的集合；sl與sp依次為l與p的狀態(tài)。在式(2)的映射關(guān)系內(nèi)，0對應(yīng)正常狀態(tài)，1對應(yīng)故障狀態(tài)。當(dāng)WSNs中包含的測試信號路徑與鏈路數(shù)量分別為m與n時，向量映射關(guān)系可以表示為

(p1，p2，…，pm)T=Z⊙(l1，l2，…，ln)T

(3)

(p1，p2，…，pm)T與(l1，l2，…，ln)T分別是路徑與鏈路的布爾狀態(tài)向量；Z是m×n階的布爾矩陣。當(dāng)路由鏈路包含在測試路徑內(nèi)，Z的相應(yīng)元素為1，否則為0。對于既定網(wǎng)絡(luò)而言，p與路由矩陣是已知的，待確定的是l。根據(jù)向量映射計算l，可能存在多解情況，但是實際上鏈路故障應(yīng)該是求解發(fā)生故障的鏈路最小值。本文據(jù)此將其轉(zhuǎn)化成最小故障鏈路搜索問題。此時問題可以表示為

(4)

(5)

s.t.z0l=0，zel≥spi，li∈{0，1}

(6)

3 基于數(shù)據(jù)分析的WSNs鏈路故障模型

WSNs鏈路結(jié)構(gòu)如圖1所示，在利用布爾方程判斷出鏈路故障后，需要進(jìn)一步確定故障點。S、D、F依次是a、c、f層對應(yīng)的重要參數(shù)。其中，S是節(jié)點總數(shù)；D是全部節(jié)點的散布因子；F是動態(tài)故障回饋。它們之間的關(guān)系描述如下

圖1 鏈路多層結(jié)構(gòu)

(7)

其中，β是緩存層的連接參量。

假定載入層的輸入標(biāo)記為Il，對應(yīng)的加權(quán)向量表示成w=[w1，w2，…，wk]。當(dāng)鏈路層內(nèi)交互正常時，w內(nèi)相應(yīng)元素的回饋參數(shù)置0，否則置1。此時，c層節(jié)點j發(fā)送數(shù)據(jù)量表示如下

(8)

wij是c和j層節(jié)點的連接權(quán)重。與此類似，鏈路中任意節(jié)點發(fā)送數(shù)據(jù)量描述如下

(9)

wiv是c內(nèi)定位點和故障點的連通加權(quán)；εv是活動因子。如果f層最終發(fā)送數(shù)據(jù)量的加權(quán)為o=[o1，o2，…，oF]，則可以得到發(fā)送數(shù)據(jù)量差值為

(10)

將故障定位的目標(biāo)描述為

(11)

利用梯度降維[9]，求解出故障點的位置如下

(12)

wij與wiv依次代表了橫軸與縱軸的坐標(biāo)位置；λ1與λ2均代表靜態(tài)變量。

(13)

4 仿真與結(jié)果分析

4.1 實驗環(huán)境配置

表1列出了仿真環(huán)境的基本配置。基于Eclipse平臺與java語言實現(xiàn)鏈路故障測試、定位、恢復(fù)，以及相應(yīng)算法功能。在WSNs中，先將Enode采取平均方式部署，再將Snode采取隨機(jī)方式部署于Enode周邊。

表1 環(huán)境和參數(shù)配置

4.2 實驗及結(jié)果分析

為了模擬真實的WSNs環(huán)境，在網(wǎng)絡(luò)中摻雜高斯白噪聲。令a∈[1，10]，從WSNs的所有節(jié)點中任意抽取2a個作為故障點，并以5s的間隔時間對WSNs進(jìn)行鏈路故障測試與修復(fù)。實驗采取Nakagami分布[10]衡量傳輸信號強(qiáng)度，具體如下

(14)

(15)

d表示收發(fā)兩節(jié)點的距離；Gr與Gt分別表示收發(fā)節(jié)點的天線增益；hr與ht分別表示收發(fā)節(jié)點的天線加權(quán)；ξ表示損耗系數(shù)。實驗過程中，設(shè)置傳輸功率的門限為0.75，Gt=Gr=1，ht=hr=0.5，ξ=0.5。當(dāng)發(fā)現(xiàn)信號功率不超過門限值，便判定為接收失敗。

根據(jù)Nakagami分布，仿真得到網(wǎng)絡(luò)可用性分布曲線，結(jié)果如圖2所示。橫坐標(biāo)代表網(wǎng)絡(luò)可用性；縱坐標(biāo)代表分布情況。當(dāng)端對端的可用性介于0.1～0.9之間時，實際的分布概率隨可用性增長而增長，測得本文方法的分布概率基本符合實際情況，分布誤差始終維持在0.1以內(nèi)，可用性均值達(dá)到0.81，表明能夠準(zhǔn)確描述網(wǎng)絡(luò)真實狀態(tài)，利用本文方法可以有效得到鏈路可用性情況。

圖2 網(wǎng)絡(luò)可用性-分布曲線

仿真得到PDR參數(shù)曲線，結(jié)果如圖3所示。PDR用于描述數(shù)據(jù)被成功傳輸?shù)母怕?，能夠體現(xiàn)網(wǎng)絡(luò)數(shù)據(jù)的傳輸效率。從曲線對比可以看出，由于網(wǎng)絡(luò)噪聲與鏈路的動態(tài)改變，方法的PDR始終處于波動狀態(tài)，但是本文方法的PDR基本圍繞著0.79上下變化，相比文獻(xiàn)[6]和文獻(xiàn)[7]分別高出了0.09和0.08，表明其具有更好的數(shù)據(jù)傳輸效率。

圖3 PDR參數(shù)曲線

在驗證WSNs鏈路故障時，采用檢測精度(Precision)和召回率(Recall)來衡量本文方法的實際效果。關(guān)于Precision與Recall的計算公式表示如下

Precision=TP/(TP+FP)

(16)

Recall=TP/(TP+FN)

(17)

Precision用于描述在對所有鏈路檢測過程中，故障鏈路被正確檢測出的概率；Recall用于描述在對真實故障鏈路檢測過程中，故障鏈路被正確檢測出的概率。TP表示故障鏈路被正確判斷出來的數(shù)量；FP表示非故障鏈路被錯誤判斷成故障鏈路的數(shù)量；FN表示故障鏈路被錯誤判斷成非故障鏈路的數(shù)量。

實驗過程中通過改變鏈路故障比例，得到WSNs鏈路故障檢測的各項指標(biāo)，并與文獻(xiàn)[6]和文獻(xiàn)[7]進(jìn)行比較，結(jié)果如圖4和圖5所示。從檢測精度曲線分析可知，在故障比例升高時，故障鏈路模型將隨之變復(fù)雜，從而影響故障鏈路的檢測定位，所以Precision值隨之逐漸下降，但是本文方法的Precision指標(biāo)顯然更好，在故障比例為15%之后才出現(xiàn)明顯下降，且下降速度更緩慢。從召回率曲線分析可知，本文方法的Recall指標(biāo)也優(yōu)于文獻(xiàn)方法。說明基于布爾方程與數(shù)據(jù)分析模型有效提升了鏈路故障的判斷和定位精度，更善于處理鏈路龐大復(fù)雜的情況，適用于大規(guī)模WSNs中。

圖4 鏈路故障檢測Precision曲線

圖5 鏈路故障檢測Recall曲線

表1列出了10次實驗對應(yīng)的鏈路故障恢復(fù)結(jié)果，并與文獻(xiàn)[5]的故障恢復(fù)性能進(jìn)行對比。根據(jù)數(shù)據(jù)分析，本文方法的WSNs鏈路故障恢復(fù)率最高達(dá)到99.8%，平均值為99.3%，兩項指標(biāo)分別比文獻(xiàn)方法高出了3.5%和6.4%。這種優(yōu)勢是由于本文首先采用了布爾方程對故障鏈路進(jìn)行分析，然后對鏈路故障點采取準(zhǔn)確定位，增加了鏈路故障的搜索準(zhǔn)確性與全面性，最后根據(jù)信道參數(shù)恢復(fù)鏈路故障，提高了WSNs鏈路故障的恢復(fù)性能。

表2 故障恢復(fù)率結(jié)果

5 結(jié)束語

為了精準(zhǔn)定位大規(guī)模WSNs網(wǎng)絡(luò)中的鏈路故障，本文首先采用布爾方程求解發(fā)生故障的鏈路最小值，然后根據(jù)鏈路數(shù)據(jù)量等參數(shù)分析確定故障點，并基于信道參數(shù)恢復(fù)故障鏈路。最后通過模擬真實的WSNs環(huán)境，得到結(jié)論如下：

1)網(wǎng)絡(luò)可用性均值為0.81，可用性分布誤差小于0.1，PDR參數(shù)較對比方法分別提高了0.09和0.08，表明方法能夠維持良好的網(wǎng)絡(luò)可用性，網(wǎng)絡(luò)數(shù)據(jù)被成功傳輸?shù)母怕矢摺?/p>

2) 故障比例超過15%之后才對Precision與Recall指標(biāo)產(chǎn)生明顯影響，故障恢復(fù)率的最大值與平均值分別達(dá)到99.8%和99.3%，表明方法對于大規(guī)模WSNs鏈路故障的檢測更為準(zhǔn)確全面，鏈路故障恢復(fù)率明顯提升。