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

李振美，王翠平

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

1 引言

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

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

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

(1)

(2)

其中，l為鏈路；p為信號(hào)傳遞路徑，每一個(gè)信號(hào)傳遞路徑都可以看做是一組鏈路的集合；sl與sp依次為l與p的狀態(tài)。在式(2)的映射關(guān)系內(nèi)，0對(duì)應(yīng)正常狀態(tài)，1對(duì)應(yīng)故障狀態(tài)。當(dāng)WSNs中包含的測(cè)試信號(hào)路徑與鏈路數(shù)量分別為m與n時(shí)，向量映射關(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)路由鏈路包含在測(cè)試路徑內(nèi)，Z的相應(yīng)元素為1，否則為0。對(duì)于既定網(wǎng)絡(luò)而言，p與路由矩陣是已知的，待確定的是l。根據(jù)向量映射計(jì)算l，可能存在多解情況，但是實(shí)際上鏈路故障應(yīng)該是求解發(fā)生故障的鏈路最小值。本文據(jù)此將其轉(zhuǎn)化成最小故障鏈路搜索問(wèn)題。此時(shí)問(wèn)題可以表示為

(4)

(5)

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

(6)

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

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

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

(7)

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

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

(8)

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

(9)

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

(10)

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

(11)

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

(12)

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

(13)

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

4.1 實(shí)驗(yàn)環(huán)境配置

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

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

4.2 實(shí)驗(yàn)及結(jié)果分析

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

(14)

(15)

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

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

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

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

圖3 PDR參數(shù)曲線

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

Precision=TP/(TP+FP)

(16)

Recall=TP/(TP+FN)

(17)

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

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

圖4 鏈路故障檢測(cè)Precision曲線

圖5 鏈路故障檢測(cè)Recall曲線

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

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

5 結(jié)束語(yǔ)

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

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

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