文獻(xiàn)標(biāo)識(shí)碼： A
DOI：10.16157/j.issn.0258-7998.2015.07.032
中文引用格式： 敬明旻，肖莉，楊傳書(shū). 基于最大似然估計(jì)與樸素貝葉斯的WSN故障檢測(cè)[J].電子技術(shù)應(yīng)用，2015，41(7)：114-117.
英文引用格式： Jing Mingmin，Xiao Li，Yang Chuanshu. Maximum likelihood estimation and Naive Bayes classifier based fault detection in WSN[J].Application of Electronic Technique，2015，41(7)：114-117.
0 引言
傳感器網(wǎng)絡(luò)通常分布于變化劇烈、地勢(shì)復(fù)雜的環(huán)境之中。可能由于能量耗盡、外界損壞等因素導(dǎo)致傳感器節(jié)點(diǎn)出現(xiàn)故障，而故障節(jié)點(diǎn)的出現(xiàn)會(huì)導(dǎo)致路由的中斷、采集數(shù)據(jù)不完整等，因此故障節(jié)點(diǎn)的檢測(cè)極為重要[1]。
已有的故障檢測(cè)算法大多較為復(fù)雜[2]，基于神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)[3]、Kruskal算法[4]等，此類(lèi)算法均可獲得較好的檢測(cè)率，但計(jì)算冗余較高，同時(shí)需傳感節(jié)點(diǎn)消耗大量的能量[5]。
本文提出了一種基于樸素貝葉斯與最大似然估計(jì)的大型傳感器網(wǎng)絡(luò)故障節(jié)點(diǎn)檢查算法，算法具有如下優(yōu)點(diǎn)：(1)所有檢測(cè)計(jì)算在sink節(jié)點(diǎn)中進(jìn)行，從而無(wú)需消耗普通節(jié)點(diǎn)的能量；(2)從協(xié)議數(shù)據(jù)包中獲取端到端延遲值，從而降低節(jié)點(diǎn)檢測(cè)的能耗；(3)使用樸素貝葉斯分類(lèi)器與最大似然估計(jì)，其計(jì)算效率較高、魯棒性好，對(duì)于大型網(wǎng)絡(luò)，其分類(lèi)準(zhǔn)確率好于一些復(fù)雜的分類(lèi)算法。
1 樸素貝葉斯分類(lèi)器與最大似然估計(jì)
1.1 故障節(jié)點(diǎn)引起的后果
圖1所示為ZigBee規(guī)范下故障節(jié)點(diǎn)導(dǎo)致路由變換的兩種情況，ZigBee規(guī)范規(guī)定所有節(jié)點(diǎn)選擇最短路徑，將數(shù)據(jù)傳遞至Sink節(jié)點(diǎn)。從圖中可看出，故障節(jié)點(diǎn)導(dǎo)致了能耗的增加以及端到端傳遞時(shí)間的延長(zhǎng)。
1.2 樸素貝葉斯模型
可在訓(xùn)練階段使用最大似然估計(jì)(MLE)求得后驗(yàn)分布，待檢測(cè)參數(shù)的值收集完畢之后，使用式(2)將其分類(lèi)。
1.3 最大似然估計(jì)
一個(gè)典型WSN中一般具有大量的傳感節(jié)點(diǎn)，網(wǎng)絡(luò)中出現(xiàn)故障或錯(cuò)誤的場(chǎng)景極多，因此，不可能通過(guò)大量的訓(xùn)練樣本來(lái)計(jì)算所有故障場(chǎng)景的條件概率。本文使用MLE在利用適量的訓(xùn)練樣本前提下，估算條件概率密度函數(shù)(PDF)。假設(shè)訓(xùn)練屬性值集合為S={s1，s2，…，sk}，將其密度表示如下：
式中S為獨(dú)立同分布。對(duì)式(4)求導(dǎo)可估算最大似然估計(jì)
2 中心型樸素貝葉斯檢測(cè)算法
基于WSN的運(yùn)行特點(diǎn)，假設(shè)數(shù)據(jù)包傳輸時(shí)間屬于指數(shù)級(jí)PDF，使用MLE估算訓(xùn)練階段的條件概率。
圖2為算法的總體流程。
下面對(duì)程序各步驟進(jìn)行詳細(xì)解釋。
步驟1：對(duì)于訓(xùn)練階段與檢測(cè)階段，僅分析簡(jiǎn)單的數(shù)據(jù)包的信息，如端到端數(shù)據(jù)包傳輸時(shí)間、源節(jié)點(diǎn)ID等。網(wǎng)絡(luò)狀態(tài)可能是正?；蛴绣e(cuò)，若類(lèi)標(biāo)簽是正常，網(wǎng)絡(luò)中則無(wú)故障傳感器；若類(lèi)標(biāo)簽是有錯(cuò)，則網(wǎng)絡(luò)中含有一個(gè)以上的故障傳感器。
訓(xùn)練階段：
步驟2.1：從正常類(lèi)中獲取數(shù)據(jù)并開(kāi)始訓(xùn)練過(guò)程。當(dāng)正常類(lèi)數(shù)據(jù)被處理之后，提取每個(gè)節(jié)點(diǎn)的最小時(shí)間值作為一個(gè)異常檢測(cè)閾值。在典型的WSN拓?fù)浣Y(jié)構(gòu)中，各節(jié)點(diǎn)將若干個(gè)數(shù)據(jù)包匯聚至sink，換句話(huà)說(shuō)，故障節(jié)點(diǎn)對(duì)傳輸?shù)挠绊懸蕾?lài)于故障傳感器在拓?fù)渲械奈恢谩Ｈ艄收瞎?jié)點(diǎn)是一個(gè)葉節(jié)點(diǎn)，則無(wú)法選擇其信號(hào)。若故障節(jié)點(diǎn)在通往sink節(jié)點(diǎn)的唯一路徑中，則該分支的節(jié)點(diǎn)均無(wú)法傳輸數(shù)據(jù)。
步驟2.2：根據(jù)訓(xùn)練數(shù)據(jù)集的類(lèi)標(biāo)簽估算兩個(gè)類(lèi)(正常類(lèi)和有錯(cuò)類(lèi))的邊際概率。
步驟3：基于步驟2.1與2.2獲得的條件概率與邊際概率建立樸素貝葉斯分類(lèi)器，步驟8使用該分類(lèi)器決定網(wǎng)絡(luò)的狀態(tài)。
檢測(cè)階段：
步驟3：sink節(jié)點(diǎn)將接收的數(shù)據(jù)包分批分析(1 000個(gè)數(shù)據(jù)包分為1批)。一批中根據(jù)所有數(shù)據(jù)包的端到端傳輸時(shí)間進(jìn)行分組。將所有分組傳給步驟5來(lái)檢查傳輸路徑中是否含有故障節(jié)點(diǎn)。
步驟4：在數(shù)據(jù)包傳遞過(guò)程中，擁塞是正常情況，其端到端傳輸時(shí)間可能高于無(wú)擁塞網(wǎng)絡(luò)情況(其中不含有故障節(jié)點(diǎn))。為了不混淆擁塞與故障節(jié)點(diǎn)兩種情況，將每個(gè)數(shù)據(jù)包組與其異常閾值比較。若組中所有的端到端傳輸時(shí)間均低于異常閾值，則認(rèn)為路徑中至少含有一個(gè)故障傳感器，或者說(shuō)，若只有一個(gè)傳輸時(shí)間值低于異常閾值，則認(rèn)為是擁塞導(dǎo)致，而不是故障節(jié)點(diǎn)。
步驟5：數(shù)據(jù)包分組中可能包含不同的端到端傳輸時(shí)間值。將傳輸時(shí)間的模式值用于進(jìn)一步的分析，計(jì)算每個(gè)分組中正常與故障模式值的條件概率，并與訓(xùn)練PDF比較。
步驟6：如果模式值的故障條件概率高于正常模式值的條件概率，則該網(wǎng)絡(luò)可能有錯(cuò)，否則，認(rèn)為該網(wǎng)絡(luò)正常。
步驟7：由于錯(cuò)誤設(shè)定的模式值也可能導(dǎo)致?lián)砣?并非故障節(jié)點(diǎn))，因此需對(duì)模式值作進(jìn)一步分析。為了確定網(wǎng)絡(luò)狀態(tài)，將最后的5個(gè)傳輸時(shí)間使用樸素貝葉斯分類(lèi)器分析。若5個(gè)時(shí)間值均較低，則使用所有的時(shí)間值來(lái)估算。由此獲得的分類(lèi)器結(jié)果代替步驟7的原結(jié)果。
步驟8：如果數(shù)據(jù)包被分組定義為一個(gè)有錯(cuò)網(wǎng)絡(luò)，對(duì)應(yīng)的源節(jié)點(diǎn)則將被定義為可疑故障節(jié)點(diǎn)，然后更新該可疑故障節(jié)點(diǎn)。
步驟9：重復(fù)步驟5～9，直至完成所有數(shù)據(jù)包的分析。
步驟10：統(tǒng)計(jì)網(wǎng)絡(luò)狀態(tài)和可疑故障節(jié)點(diǎn)列表根據(jù)測(cè)試場(chǎng)景進(jìn)行報(bào)告。
3 試驗(yàn)結(jié)果與分析
3.1 仿真與試驗(yàn)環(huán)境
試驗(yàn)采用ZigBee系統(tǒng)建立WSN網(wǎng)絡(luò)模型，使用鄰接矩陣(傳輸成本范圍為1~200)隨機(jī)生成100個(gè)節(jié)點(diǎn)的網(wǎng)絡(luò)拓?fù)洹＞W(wǎng)絡(luò)中僅設(shè)置一個(gè)sink節(jié)點(diǎn)，將sink節(jié)點(diǎn)的能量設(shè)為無(wú)限。各節(jié)點(diǎn)隨機(jī)地采集數(shù)據(jù)，然后將數(shù)據(jù)包傳遞至sink節(jié)點(diǎn)。試驗(yàn)中設(shè)置兩個(gè)重要的網(wǎng)絡(luò)場(chǎng)景：(1)流量擁塞等級(jí)(3個(gè)流量擁塞等級(jí))：無(wú)擁塞、輕度擁塞、重度擁塞。(2)按網(wǎng)絡(luò)中是否有故障節(jié)點(diǎn)分為：故障網(wǎng)絡(luò)、正常網(wǎng)絡(luò)。試驗(yàn)中將故障節(jié)點(diǎn)數(shù)量設(shè)為1~5個(gè)。對(duì)于100個(gè)節(jié)點(diǎn)的拓?fù)洌?~5個(gè)故障節(jié)點(diǎn)，則分別有100、4 950、161 700、3 921 225、75 287 520個(gè)故障節(jié)點(diǎn)的位置組合，顯然，故障節(jié)點(diǎn)的分布情況很多，由于試驗(yàn)條件限制，試驗(yàn)中將故障節(jié)點(diǎn)組合的上限設(shè)為5 000個(gè)，因此，每個(gè)流量擁塞等級(jí)的總場(chǎng)景數(shù)量為20 050，3個(gè)擁塞等級(jí)則共有60 150個(gè)故障場(chǎng)景，每個(gè)場(chǎng)景傳感器共隨機(jī)產(chǎn)生2 000個(gè)數(shù)據(jù)包。
將本算法與其他兩個(gè)廣泛應(yīng)用的性能評(píng)價(jià)算法比較：邊緣故障檢測(cè)(MFD)、歷史故障檢測(cè)(HFD)。MFD利用每個(gè)節(jié)點(diǎn)的正常數(shù)據(jù)，對(duì)其訓(xùn)練并獲得測(cè)試數(shù)據(jù)的閾值，當(dāng)擁塞導(dǎo)致傳輸時(shí)間變化時(shí)，選擇最小值作為閾值。若較多的新數(shù)據(jù)高于閾值，則將該傳輸路徑分類(lèi)為故障路徑，將對(duì)應(yīng)的源節(jié)點(diǎn)記為可疑節(jié)點(diǎn)。
MFD使用所有正常數(shù)據(jù)訓(xùn)練獲得其閾值，而HFD與本算法則使用60%左右的故障數(shù)據(jù)訓(xùn)練，剩下40%故障數(shù)據(jù)用于方法驗(yàn)證。在相同的流量擁塞等級(jí)下，HFD為每個(gè)源節(jié)點(diǎn)記錄正常與故障兩個(gè)場(chǎng)景的傳輸時(shí)間，若在其正常場(chǎng)景與故障場(chǎng)景中發(fā)現(xiàn)相同的傳輸時(shí)間，則將該網(wǎng)絡(luò)與源節(jié)點(diǎn)分別分類(lèi)為故障網(wǎng)絡(luò)與可疑節(jié)點(diǎn)。圖3所示為正常傳輸時(shí)間與故障傳輸時(shí)間下指數(shù)分布MLE獲得的概率密度函數(shù)。圖3(a)中，比較了單個(gè)節(jié)點(diǎn)的故障場(chǎng)景與正常場(chǎng)景的PDF，圖3(b)對(duì)整個(gè)網(wǎng)絡(luò)的全部故障場(chǎng)景與正常場(chǎng)景的PDF進(jìn)行了比較，可看出故障場(chǎng)景下，長(zhǎng)傳輸時(shí)間的概率高于正常場(chǎng)景。
3.2 場(chǎng)景檢測(cè)率
本文為三個(gè)不同流量條件共產(chǎn)生6 015個(gè)場(chǎng)景。場(chǎng)景檢測(cè)率表示本算法檢測(cè)的可疑節(jié)點(diǎn)與理論故障節(jié)點(diǎn)匹配的數(shù)量與總場(chǎng)景數(shù)量的比例。圖4所示為不同流量條件下，MFD、HFD與本算法三種方法的場(chǎng)景檢測(cè)率。在擁塞情況下，本算法的場(chǎng)景檢測(cè)率最高，而其他兩種算法在輕度與重度兩種擁塞下性能不佳，因?yàn)楣收系膱?chǎng)景眾多，MFD與HFD從其數(shù)據(jù)庫(kù)中無(wú)法獲得足夠的信息來(lái)判斷傳輸時(shí)間較長(zhǎng)的原因(因?yàn)閾砣蚴且驗(yàn)榫W(wǎng)絡(luò)故障)。對(duì)于故障場(chǎng)景，輕度擁塞的一個(gè)故障節(jié)點(diǎn)情況下，本算法的檢測(cè)性能不佳，原因在于：一個(gè)故障節(jié)點(diǎn)時(shí)，故障場(chǎng)景有限，此時(shí)，樸素貝葉斯分類(lèi)器的訓(xùn)練數(shù)據(jù)不足，導(dǎo)致條件概率訓(xùn)練不夠準(zhǔn)確。而對(duì)于故障場(chǎng)景的其他情況，本算法的檢測(cè)率均高于60%，原因在于：其他情況下，利用較多的故障數(shù)據(jù)建立了條件概率，因此獲得了較高的樸素貝葉斯分類(lèi)正確率。
4 結(jié)論
本文通過(guò)貝葉斯分類(lèi)器與最大似然估計(jì)實(shí)現(xiàn)了有效的傳感器網(wǎng)絡(luò)故障檢測(cè)，在保持與傳統(tǒng)算法虛警率接近的條件下，大幅度提高了故障檢測(cè)的場(chǎng)景檢測(cè)率。此技術(shù)在隨鉆數(shù)據(jù)測(cè)量與風(fēng)險(xiǎn)監(jiān)測(cè)方面具有廣泛應(yīng)用和前景。
參考文獻(xiàn)
[1] 馬峻巖，周興社，李士寧，等.基于異常任務(wù)運(yùn)行記錄的WSN故障檢測(cè)[J].計(jì)算機(jī)工程，2012，38(1)：93-95.
[2] 李洪兵，熊慶宇，石為人，等.無(wú)線(xiàn)傳感器網(wǎng)絡(luò)中網(wǎng)絡(luò)層故障容錯(cuò)技術(shù)研究進(jìn)展[J].計(jì)算機(jī)應(yīng)用研究，2013，30(7)：1921-1928.
[3] 謝迎新，陳祥光，余向明，等.基于VPRS和RBF神經(jīng)網(wǎng)絡(luò)的WSN節(jié)點(diǎn)故障診斷[J].北京理工大學(xué)學(xué)報(bào)，2010，30(7)：807-811.
[4] 李文璟，袁野，喻鵬，等.基于改進(jìn)Kruskal算法的WSN故障節(jié)點(diǎn)檢測(cè)方法[J].北京郵電大學(xué)學(xué)報(bào)，2014，37(4)：103-107.
[5] LEE M H，CHOI Y H.Fault detection of wireless sensor networks[J].Computer Communications，2008，31(14)：3469-3475.
[6] YOUN E，JEONG M K.Class dependent feature scaling method using Naive Bayes classifier for text datamining[J].Pattern Recognition Letters，2009，30(5)：477-485.