徐磊磊，徐保國

(輕工過程先進控制教育部重點實驗室 江南大學，江蘇 無錫214122)

0 引 言

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

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

1 故障節(jié)點檢測設計

1.1 區(qū)域劃分

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

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

1.2 檢測序列映射

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

通過最大后驗(MAP)估計法來估計

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

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

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

最終條件概率的公式為

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

圖2 條件概率計算Fig 2 Conditional probability computation

1.3 排序差檢測

1.3.1 平均排序差

設ˉsi對應的樣本估計為n 為樣本大小，定義樣本i中節(jié)點k 排序差di(k)為

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

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

式中 N 為網絡中節(jié)點總數，Ne為故障節(jié)點的個數，μe為故障節(jié)點平均排序差的算術平均值。

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

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

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

正常節(jié)點不會改變其他節(jié)點的排名順序，給定的d(k)，一個正常節(jié)點p 被節(jié)點k 影響的預期排序差為dk(p)

等式兩邊取期望

一個正常節(jié)點p 被所有故障節(jié)點影響的預期排序差的上限為

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

式(12)不等號成立的條件為Ne個故障節(jié)點對節(jié)點p的影響均向同一個方向。當樣本足夠大時，用期望替代樣本平均值，式(12)變?yōu)?/p>

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

1.3.2 檢測算法

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

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

2 算法應用問題解決方法

2.1 噪聲環(huán)境

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

2.2 子序列估計

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

3 仿真與結果分析

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

兩個指標用于評估算法性能:漏檢率和誤檢率。前者定義為故障節(jié)點檢測為正常的比率，后者為正常節(jié)點檢測為故障的比率。

3.1 α 檢測與B 檢測性能比較

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

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

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

3.2 不同網絡密度的影響

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

4 結 論

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

圖6 網絡密度對B 檢驗漏檢率的影響Fig 6 Effect of network density on B-detection miss rate

圖7 網絡密度對B 檢驗誤檢率的影響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］ 孫利民，李建中，陳 渝，等.無線傳感器網絡［M］.北京:清華大學出版社，2005.

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

［4］ 趙亞鳳，任洪娥.基于無線傳感器網絡的同時定位與跟蹤［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.