一種無線傳感器網(wǎng)絡(luò)故障節(jié)點(diǎn)檢測(cè)算法*

徐磊磊，徐保國

(輕工過程先進(jìn)控制教育部重點(diǎn)實(shí)驗(yàn)室 江南大學(xué)，江蘇 無錫214122)

0 引 言

無線傳感器網(wǎng)絡(luò)(wireless sensor networks，WSNs)中的節(jié)點(diǎn)可能會(huì)遇到兩種類型的故障，從而降低網(wǎng)絡(luò)性能［1，2］。一種是功能故障，這將導(dǎo)致個(gè)別節(jié)點(diǎn)崩潰、包損失、路由故障［3］;另一種是數(shù)據(jù)故障，除了它的檢測(cè)結(jié)果錯(cuò)誤，其它可以正常工作［4］。故障節(jié)點(diǎn)的存在對(duì)系統(tǒng)有很大影響，因此，檢測(cè)這些故障節(jié)點(diǎn)并將其剔除是非常重要的［5］。

本文提出一種檢測(cè)故障節(jié)點(diǎn)的方法，該方法提供了一個(gè)包含所有的故障節(jié)點(diǎn)的黑名單，無需事件或模型假設(shè)，根據(jù)特定事件節(jié)點(diǎn)的讀數(shù)排列順序，通過識(shí)別節(jié)點(diǎn)序列中違反排名的節(jié)點(diǎn)，將故障節(jié)點(diǎn)加入黑名單。算法對(duì)實(shí)際應(yīng)用中的噪聲環(huán)境和子序列估計(jì)問題分別提出了相應(yīng)的解決方法。仿真實(shí)驗(yàn)表明:在不同的網(wǎng)絡(luò)設(shè)置下，漏檢率和誤檢率均較低，算法具有良好的性能。

1 故障節(jié)點(diǎn)檢測(cè)設(shè)計(jì)

1.1 區(qū)域劃分

如圖1 所示，區(qū)域內(nèi)所有節(jié)點(diǎn)間的垂直平分線將區(qū)域劃分為若干個(gè)子區(qū)域［6］，每個(gè)子區(qū)域可以通過子區(qū)域和所有的節(jié)點(diǎn)距離關(guān)系的唯一的距離序列來標(biāo)識(shí)。由于故障節(jié)點(diǎn)和噪聲影響，有故障讀數(shù)的檢測(cè)序列會(huì)違反距離序列的幾何約束，可能是所有N!個(gè)節(jié)點(diǎn)序列中的任意一個(gè)。因此，給定事件的檢測(cè)序列后，需估計(jì)事件發(fā)生的子區(qū)域。這實(shí)質(zhì)上是將檢測(cè)序列與距離序列進(jìn)行有效映射。

圖1 區(qū)域劃分舉例Fig 1 Examples of region division

1.2 檢測(cè)序列映射

令N 個(gè)節(jié)點(diǎn)將平面分成M 個(gè)子區(qū)域，用距離序列集V={s1，s2，…，sM}表示。設(shè)是單個(gè)事件的檢測(cè)序列，s 為事件發(fā)生的子區(qū)域的距離序列。s 為樣本空間V 的隨機(jī)變量，用{A1，A2，…，AM}表示M 個(gè)子區(qū)域的大小，則s 的先驗(yàn)分布為

通過最大后驗(yàn)(MAP)估計(jì)法來估計(jì)

接下來要找出一個(gè)距離序列si∈V 使式(2)最大化。對(duì)于任意si∈V，Pr(si)式(1)已經(jīng)給出，唯一未解決的問題是如何計(jì)算

設(shè)α 為傳感器節(jié)點(diǎn)的次品率。ˉs［k］和si［k］分別表示N 個(gè)節(jié)點(diǎn)序列和si中第k 個(gè)節(jié)點(diǎn)。當(dāng)所有的1≤k≤N，均成立，有兩種可能:一種是所有節(jié)點(diǎn)均正常，另一種是有w 個(gè)故障節(jié)點(diǎn)，但在這種特殊的情況下，這些節(jié)點(diǎn)沒有改變序列，可能性為

第二種:ˉs 中第k 個(gè)節(jié)點(diǎn)是正常節(jié)點(diǎn)，在這種情況下從k+1到l 必有故障節(jié)點(diǎn)，圖2 中若節(jié)點(diǎn)6 正常，節(jié)點(diǎn)3，4，5中必有故障節(jié)點(diǎn)，從原始序列中去除這些節(jié)點(diǎn)獲得新的序列s″i和，均為1－2－6－7－8－9，這種情況下，原來的條件概率)取決于新的條件概率正常下的條件概率為

最終條件概率的公式為

式(6)是遞歸的，遞歸過程一直進(jìn)行到兩個(gè)序列完全相同。通過式(6)計(jì)算任意si∈V 下的條件概率，再由式(2)可以MAP 估計(jì)。

圖2 條件概率計(jì)算Fig 2 Conditional probability computation

1.3 排序差檢測(cè)

1.3.1 平均排序差

設(shè)ˉsi對(duì)應(yīng)的樣本估計(jì)為n 為樣本大小，定義樣本i中節(jié)點(diǎn)k 排序差di(k)為

式中 R(*，k)為節(jié)點(diǎn)k 在序列*中的排序，則在n 個(gè)樣本中節(jié)點(diǎn)k 的平均排序差D(k)為

定理:如果節(jié)點(diǎn)q 故障，那么，它的平均排序差D(q)要比界B 大

式中 N 為網(wǎng)絡(luò)中節(jié)點(diǎn)總數(shù)，Ne為故障節(jié)點(diǎn)的個(gè)數(shù)，μe為故障節(jié)點(diǎn)平均排序差的算術(shù)平均值。

證明:設(shè)1～Ne為故障節(jié)點(diǎn)，剩余為正常節(jié)點(diǎn)。當(dāng)只有一個(gè)故障節(jié)點(diǎn)時(shí)，觀察到對(duì)于單一的故障節(jié)點(diǎn)k，其排序差為d(k)，至多讓d(k)個(gè)節(jié)點(diǎn)的排序相差1。如圖3(a)所示，故障節(jié)點(diǎn)4 向左移動(dòng)兩位使得2 個(gè)節(jié)點(diǎn)(2 和3)的順序改變了1，與排序差d(4)=2 相等。

圖3 故障節(jié)點(diǎn)對(duì)排序差的影響Fig 3 Effect of fault nodes on ranking differences

當(dāng)其余Ne－1 個(gè)故障節(jié)點(diǎn)出現(xiàn)時(shí)，一個(gè)故障節(jié)點(diǎn)最終排序會(huì)被其余故障節(jié)點(diǎn)影響。圖3(b)中節(jié)點(diǎn)2 和3 的排序差為3，這是由于3 個(gè)故障節(jié)點(diǎn)導(dǎo)致的，雖然最終的d(4)=0，但其影響仍然存在。因此，被節(jié)點(diǎn)4 影響的節(jié)點(diǎn)數(shù)為開始的d'(4)=2。給定任意的節(jié)點(diǎn)k 的最終排序差d(k)，原始移動(dòng)d'(k)最大可能值為d(k)+Ne－1，即最多影響d(k)+Ne－1 個(gè)節(jié)點(diǎn)。

正常節(jié)點(diǎn)不會(huì)改變其他節(jié)點(diǎn)的排名順序，給定的d(k)，一個(gè)正常節(jié)點(diǎn)p 被節(jié)點(diǎn)k 影響的預(yù)期排序差為dk(p)

等式兩邊取期望

一個(gè)正常節(jié)點(diǎn)p 被所有故障節(jié)點(diǎn)影響的預(yù)期排序差的上限為

其中，μe為受所有故障節(jié)點(diǎn)的影響的平均排序差的平均值

式(12)不等號(hào)成立的條件為Ne個(gè)故障節(jié)點(diǎn)對(duì)節(jié)點(diǎn)p的影響均向同一個(gè)方向。當(dāng)樣本足夠大時(shí)，用期望替代樣本平均值，式(12)變?yōu)?/p>

令B 等于上述不等式右邊的部分，則任意正常節(jié)點(diǎn)的平均排序差的上限為B，如果一個(gè)節(jié)點(diǎn)的平均排序差大于B，那么，它必然為故障節(jié)點(diǎn)。

1.3.2 檢測(cè)算法

由于故障節(jié)點(diǎn)Ne預(yù)先不知道，需要估計(jì)Ne的大小，其基本思想是找到所有平均排名差高于B 的節(jié)點(diǎn)，給定有序節(jié)點(diǎn)序列n1－n2…－nN，找到分割點(diǎn)k，使得{n1，n2，…，－nk}為故障節(jié)點(diǎn)估計(jì)。檢測(cè)算法偽代碼如下

首先，初始化，從平均排名差最大的節(jié)點(diǎn)n1開始，依次檢驗(yàn)排序差，將大于B 的節(jié)點(diǎn)加入到黑名單中。更新Ne，μe，B。當(dāng)循環(huán)在節(jié)點(diǎn)nk+1時(shí)被打破，得到黑名單{n1，n2，…，nk}。

2 算法應(yīng)用問題解決方法

2.1 噪聲環(huán)境

在強(qiáng)噪聲環(huán)境，普通節(jié)點(diǎn)有時(shí)會(huì)表現(xiàn)為故障節(jié)點(diǎn)，為了解決該問題，使用統(tǒng)計(jì)方法在序列{n1，n2，…，nk}中篩選出可能的正常節(jié)點(diǎn)。給定故障節(jié)點(diǎn)估計(jì){n1，n2，…，nk}，其余的點(diǎn){nk+1，…，nN}被認(rèn)為是正常節(jié)點(diǎn)，那么，正常節(jié)點(diǎn)的樣本平均值μ 和排序差的樣本方差σ2可計(jì)算出。將節(jié)點(diǎn)排序差不大于^μ+3^σ 從黑名單序列中移除。

2.2 子序列估計(jì)

實(shí)際中單個(gè)事件檢測(cè)序列ˉs 的長度要比N 小很多。設(shè)L 為檢測(cè)序列長度的上界。給定ˉs，其相應(yīng)的si也被截?cái)?，選擇si的截?cái)嚅L度為2L。對(duì)于子序列來說，存在兩個(gè)問題，首先，開始時(shí)兩個(gè)序列的長度不相等，因此，多數(shù)情況下ˉs 和si不相同。其次，由于si也被截?cái)啵荒艽_保存在si［l］使得ˉs［k］=si［l］。因此，在遞歸計(jì)算Pr(ˉs|si)做出如下改進(jìn):1)遞歸終止條件放寬到si從后面開始移除若干個(gè)節(jié)點(diǎn)后被ˉs 截?cái)唷?)對(duì)于每對(duì)不匹配的節(jié)點(diǎn)ˉs［k］≠si［k］，如果ˉs(k)在si中不存在，若正常則說明至少有L 個(gè)故障節(jié)點(diǎn)，這種情況可忽略，因此，直接被認(rèn)為是故障節(jié)點(diǎn)。

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

仿真實(shí)驗(yàn)中將100 個(gè)傳感器節(jié)點(diǎn)隨機(jī)部署在250 m×250 m 區(qū)域內(nèi)，通信半徑25 m 和事件數(shù)目為50，節(jié)點(diǎn)和事件隨機(jī)生成。L 設(shè)為10，采用最常用的對(duì)數(shù)衰減模型。隨機(jī)噪聲服從分布，σX缺省值是4。所有仿真結(jié)果取20 次平均值。設(shè)α 準(zhǔn)確，則排序差前αN 個(gè)節(jié)點(diǎn)被視為故障節(jié)點(diǎn)，這是一種理想情況，記為α 檢測(cè)。當(dāng)α 不準(zhǔn)確，用檢測(cè)算法得到故障節(jié)點(diǎn)數(shù)，記為B 檢測(cè)。

兩個(gè)指標(biāo)用于評(píng)估算法性能:漏檢率和誤檢率。前者定義為故障節(jié)點(diǎn)檢測(cè)為正常的比率，后者為正常節(jié)點(diǎn)檢測(cè)為故障的比率。

3.1 α 檢測(cè)與B 檢測(cè)性能比較

圖4 反映了α 檢測(cè)和B 檢測(cè)分別在有噪聲和無噪聲環(huán)境下的漏檢率?？梢钥闯?1)兩種檢測(cè)漏檢率均在10%以下，當(dāng)節(jié)點(diǎn)缺陷率α 低于10%時(shí)漏檢率低于4%。因此，兩種檢測(cè)均可以有效檢測(cè)出故障節(jié)點(diǎn)。2)α 檢測(cè)總是比B檢測(cè)漏檢率低，這是因?yàn)棣?檢測(cè)可以直接根據(jù)平均排序差選擇前αN 個(gè)節(jié)點(diǎn)作為故障節(jié)點(diǎn)，而B 檢測(cè)要采用檢測(cè)算法找出故障節(jié)點(diǎn)數(shù)目。因而α 檢測(cè)具有更好的性能。3)由于噪聲的存在，α 檢測(cè)與B 檢測(cè)漏檢率略微增加，但仍可以檢測(cè)出超過90%的故障節(jié)點(diǎn)。圖5 對(duì)應(yīng)于上述4 個(gè)場(chǎng)景中的誤檢率，可以看到大部分的誤檢率是1%左右，意味著正常的節(jié)點(diǎn)只有極少部分被誤判，因此，該算法性能良好。

圖4 兩種檢測(cè)漏檢率比較Fig 4 Comparison of two kinds of miss detection rate

圖5 兩種檢測(cè)誤檢率比較Fig 5 Comparison of two kinds of false detection rate

3.2 不同網(wǎng)絡(luò)密度的影響

將網(wǎng)絡(luò)區(qū)域邊長從150 m 增加到350 m，節(jié)點(diǎn)數(shù)目保持不變。圖6、圖7 曲線反映了B 檢測(cè)在不同網(wǎng)絡(luò)密度下的性能:1)區(qū)域邊長從300 m 增加到350 m，漏檢率增加5%左右;區(qū)域邊長從250 m 增加到300 m，誤檢率也增加了。這是因?yàn)檩^低的密度，事件通信半徑內(nèi)的節(jié)點(diǎn)的數(shù)量變小，節(jié)點(diǎn)序列變短，信息較少，估算序列較不準(zhǔn)確。2)區(qū)域邊長從200 m 下降到150 m，誤檢率沒有下降。這是因?yàn)楫?dāng)密度越高，更多的節(jié)點(diǎn)在檢測(cè)范圍內(nèi)，距離事件具有相似距離。加上噪聲的存在更多的節(jié)點(diǎn)具有類似的讀數(shù)。因此，誤檢率最低的是中等密度的網(wǎng)絡(luò)，誤檢率多為2%左右。

4 結(jié) 論

本文提出一種無線傳感器網(wǎng)絡(luò)故障節(jié)點(diǎn)的檢測(cè)方法，提供了一個(gè)包含所有的故障節(jié)點(diǎn)的黑名單，無需事件或模型假設(shè)，通過識(shí)別節(jié)點(diǎn)序列中違反排名的節(jié)點(diǎn)，找到故障節(jié)點(diǎn)。從理論上證明檢測(cè)序列和估計(jì)序列的平均排序差可作為故障節(jié)點(diǎn)的判斷指標(biāo)，并對(duì)算法在實(shí)際應(yīng)用中噪聲環(huán)境和子序列估計(jì)問題分別提出了相應(yīng)的解決方法。仿真實(shí)驗(yàn)表明:在不同的網(wǎng)絡(luò)設(shè)置下，漏檢率和誤檢率均較低，因而，算法具有良好的性能。

圖6 網(wǎng)絡(luò)密度對(duì)B 檢驗(yàn)漏檢率的影響Fig 6 Effect of network density on B-detection miss rate

圖7 網(wǎng)絡(luò)密度對(duì)B 檢驗(yàn)誤檢率的影響Fig 7 Effect of network density on B-detection false rate

［1］ Ju Hailing，Miao Yong，Li Tianpu，et al.Overview of wireless sensor networks［J］.Computer Research and Development，2005，42(1):163－174.

［2］ 孫利民，李建中，陳 渝，等.無線傳感器網(wǎng)絡(luò)［M］.北京:清華大學(xué)出版社，2005.

［3］ Cullar D，Estrin D，Strvastava M.Overview of sensor network［J］.Computer，2004，37(8):41－49.

［4］ 趙亞鳳，任洪娥.基于無線傳感器網(wǎng)絡(luò)的同時(shí)定位與跟蹤［J］.傳感器與微系統(tǒng)，2014，33(5):55－58.

［5］ Jia Z X，Wu C D，.Zhang Y Z，et al.Distributed grid location estimation scheme based on euclidean distance［C］∥IEEE 3rd Conference on Industrial Electronics and Applications，2008:1128－1132.

［6］ Joo G L，Rao S V.A grid－based location estimation scheme using hop counts for multi－h(huán)op wireless sensor networks［C］∥International Workshop on Wireless Ad－Hoc Networks，2004:330－334.

［7］ De Berg M，Van Kreveld M，Overmars M，et al.Computational geometry［M］.3rd ed.Berlin/Heidelberg:Springer，2008.