吳玉成，付紅玉

（重慶大學 通信工程學院，重慶 400044）

0 引 言

事件監(jiān)測是無線傳感器網絡（Wireless sensor networks，WSN）主要應用之一［1］，具有監(jiān)測范圍廣、監(jiān)測對象隨機性大、對數(shù)據傳輸實時性和可靠性要求高等特點。而傳感器節(jié)點能量和功能的有限性制約了該應用的有效開展，設計能量高效的路由策略以延長無線傳感器網絡生命周期十分必要。

分層式路由協(xié)議能夠有效地降低和均衡網絡能耗，特別適用于大規(guī)模 WSN 應用場景［2］。LEACH （Low－energy adaptive clustering hierarchy）［3］是最早提出的分層式路由協(xié)議，但存在簇頭選擇未考慮節(jié)點剩余能量、簇的數(shù)量和大小分布過于隨機、單跳通信使節(jié)點能量消耗過快等不足。諸如CM－EDR（Continuous monitoring based on an event－driven reporting）［4］、AEEC（Adaptive and energy efficient clustering algorithm）［5］、SAHRC （Self－adaptive hybrid routing control）［6］、SCTC（Static chain－cluster routing protocol）［7］等改進算法在一定程度上克服了LEACH算法的不足，但應用于突發(fā)事件監(jiān)測場景仍然存在缺陷，如:不相關節(jié)點參與成簇產生不必要的能量消耗；成簇區(qū)域和事件區(qū)域不吻合降低了數(shù)據融合的有效性等。文獻［8］提出的事 件 驅 動 成 簇 EDC（Event－driven clustering routing algorithm）算法，保證成簇區(qū)域與事件區(qū)域的一致吻合性，克服了上述缺陷。但該算法需要借助基站和網關節(jié)點的作用，增加了網絡節(jié)點的復雜度。ARPEES（Adaptive routing protocol with energy efficiency and event clustering for wireless sensor networks）算法［9］通過事件驅動成簇和多跳中繼機制來提高網絡能量效率，但中繼路由采用實時選擇方式，增大了傳輸時延；且僅將節(jié)點剩余能量和數(shù)據采集信息量作為簇頭選舉條件，并未考慮距離Sink節(jié)點遠近等因素。

針對現(xiàn)有路由協(xié)議應用于大規(guī)模WSN突發(fā)事件監(jiān)測場景的不足，本文提出了一種基于事件驅動成簇機制的路由策略。該策略在簇頭選舉時綜合考慮了節(jié)點剩余能量、距離Sink節(jié)點的跳數(shù)、與鄰居節(jié)點的連通性以及父節(jié)點數(shù)目等因素以節(jié)省和均衡網絡能耗。在數(shù)據傳輸階段，簇頭和Sink節(jié)點間通過時延梯度路徑樹進行多路徑選擇和多跳中繼通信，進一步均衡網絡能耗，并為數(shù)據的及時和可靠傳輸提供了保障。

1 網絡模型和能量消耗模型

鑒于大規(guī)模WSN突發(fā)事件監(jiān)測場景，本文對網絡模型做如下假設:

（1）N個傳感器節(jié)點隨機分布于M ×M 的正方形區(qū)域內，各節(jié)點在網絡中的地位平等，具有唯一ID，網絡部署后節(jié)點位置不再變化。

（2）各節(jié)點具有相同的初始能量以及數(shù)據處理和通信能力，包括存儲轉發(fā)、數(shù)據融合、自適應功率控制等。

（3）Sink節(jié)點唯一，靜置于監(jiān)測區(qū)域中心且不受能量和功能的限制。

基于文獻［3］給出的WSN能量消耗模型，節(jié)點發(fā)射k bit數(shù)據到距離d處所消耗的能量為

式中:ETX－elec為發(fā)射數(shù)據時電路消耗的能量；ETX－amp為將需發(fā)射的數(shù)據放大到一定的信噪比所消耗的能量；Eelec為電路運算和處理每比特數(shù)據的能耗；εfs為自由空間模型參數(shù)；εmp為多徑衰落模型參數(shù)；d0為傳輸模型選擇門限:

節(jié)點接收k bit數(shù)據消耗的能量為

將N個長度為k bit的數(shù)據包進行數(shù)據融合處理所消耗的能量為

式中:Edata為融合處理1bit數(shù)據消耗的能量。

2 路由策略描述

本文策略由時延梯度路徑樹的建立、簇頭選舉及成簇、路由選擇和路由維護4個部分組成。在網絡布置初期，通過時延梯度路徑樹的建立使監(jiān)測區(qū)域內所有節(jié)點以樹的形式構成一個監(jiān)測網絡，同時各節(jié)點完善自身路由表信息，為簇頭選舉和成簇以及路由選擇和維護提供必要的參考信息。節(jié)點監(jiān)測到突發(fā)事件時，根據自身剩余能量、距離Sink節(jié)點的跳數(shù)、與鄰居節(jié)點的連通度以及回傳路徑選擇度等信息參與簇頭競選；所有相關節(jié)點以選舉出的簇頭為首構成事件簇。簇頭負責收集簇內相關節(jié)點的監(jiān)測數(shù)據并進行融合處理，然后根據路由信息表中信息選擇合理的路由將處理后的有效數(shù)據傳送回Sink節(jié)點。

2.1 時延梯度路徑樹的建立

鑒于突發(fā)事件監(jiān)測應用對數(shù)據傳輸?shù)膶崟r性和可靠性要求，本策略做了兩點設計:首先，建立以Sink節(jié)點為首的時延梯度路徑樹并以此完善節(jié)點路由信息表；其次，路由信息表中記錄了多條備用路徑選擇以保證數(shù)據傳輸?shù)目煽啃?。時延梯度路徑樹建立步驟如下。

（1）節(jié)點初始化:Sink節(jié)點跳數(shù)為0，剩余能量和有效父節(jié)點數(shù)均為∞；普通節(jié)點跳數(shù)為∞，剩余能量為E0，有效父節(jié)點數(shù)為0。所有節(jié)點初始化功率半徑均為R0。

（2）Sink節(jié)點以初始化功率半徑廣播生成樹消息，該消息包含節(jié)點的ID、距離Sink節(jié)點的跳數(shù)以及剩余能量等信息。

（3）收到生成樹消息的節(jié)點標記為樹成員，若自身跳數(shù)L0小于消息中跳數(shù)Lm值加1，則丟棄該消息；否則，在路由信息表中記錄該消息。同時更新自身跳數(shù)為Lm＋1，生成包含自身信息的生成樹消息，并廣播。

（4）在初始化功率半徑情況下的孤立節(jié)點可通過適當增大發(fā)生功率，選擇距離自己最近，且比自身距離Sink節(jié)點近的有效節(jié)點作為自己的父節(jié)點，相應地更新自身跳數(shù)和路由表信息。

通過時延梯度路徑樹的建立，網絡中所有節(jié)點都加入到該樹型網絡中，且各節(jié)點的路由信息表中根據到達Sink節(jié)點的時延按照從小到大的順序依次記錄了若干父節(jié)點的相關信息，為數(shù)據回傳提供了最短時延路徑和若干備用路徑選擇，為數(shù)據回傳的及時性和可靠性提供了保障。

2.2 簇頭選舉及成簇

為了節(jié)省和均衡網絡能量消耗，避免單個節(jié)點因能量耗盡過早死亡而降低網絡的連通性，本文在選擇簇頭時不僅考慮了節(jié)點的剩余能量信息，同時考慮了節(jié)點跳數(shù)、與鄰居節(jié)點的連通度以及父節(jié)點數(shù)目等因素。

節(jié)點監(jiān)測到異常事件發(fā)生，立即根據式（5）計算自身競選簇頭節(jié)點的機率PCH0。機率最大的節(jié)點成為簇頭節(jié)點。若Sink節(jié)點在事件區(qū)域內，則直接由Sink節(jié)點擔任簇頭節(jié)點。

式中:Eres、E0分別為節(jié)點剩余能量和初始化能量；L0為節(jié)點距離Sink節(jié)點的跳數(shù)；Nnbs、Npar分別為該節(jié)點的鄰居節(jié)點數(shù)目和有效父節(jié)點數(shù)目；N 為總節(jié)點數(shù)目；αi（i＝1，2，3，4）為各影響因素的比重系數(shù)，αi＞0且∑αi＝1。

簇頭選舉流程如圖1所示。

圖1 簇頭選舉流程圖Fig.1 Flow chart of cluster head selecting

簇頭選舉算法步驟描述如下:

（1）各相關節(jié)點生成包含ID和PCH0信息的簇頭選舉消息MCH0，并根據PCH0大小等待一個時間段Ti，其中Ti＝ （1－PCHi）×T0，i為節(jié)點ID，T0為一個常數(shù)。可見，機率越小的節(jié)點等待的時間越長。

（2）在等待時段內，若收到來自其他節(jié)點的簇頭選舉消息（MCHm），則將其保存為MCH0并廣播；否則，在Ti結束時廣播自身簇頭選舉消息MCH0。簇頭選舉消息包含了生成該消息的節(jié)點的ID和競選簇頭的機率。可見，機率最大的節(jié)點最先廣播自身簇頭選舉消息，機率小的節(jié)點可避免不必要的廣播自身簇頭選舉消息，從而減少了能量消耗和碰撞機率。

（3）在TN（TN＞T0）時間段內，節(jié)點若收到其他簇頭選舉消息MCHm，將當前MCH0中的PCH0與MCHm中的PCHm進行比較，若PCH0＞PCHm，則丟棄該MCHm，否則，將MCHm保存為MCH0并廣播。

（4）TN時段結束后，節(jié)點保存的MCH0即為當前事件的簇頭節(jié)點信息。

經過上述流程，當前事件所有相關節(jié)點都記錄了簇頭節(jié)點的ID，各節(jié)點采用CSMA協(xié)議將自身監(jiān)測數(shù)據直接或通過其他相關節(jié)點中繼傳送給簇頭節(jié)點。簇頭節(jié)點進行數(shù)據融合處理得到有效監(jiān)測數(shù)據。為了盡可能地減少節(jié)點能量消耗，各簇內節(jié)點監(jiān)測數(shù)據在逐跳返回簇頭節(jié)點的過程中，也可以進行必要的融合處理。

2.3 路由選擇

節(jié)點根據路由信息表提供的父節(jié)點信息來選擇數(shù)據回傳路由，路由信息表中的多路徑選擇為數(shù)據的可靠性傳輸提供了必要的保障。數(shù)據回傳路由選擇按照以下原則進行:

（1）若Sink節(jié)點在當前節(jié)點路由信息表中，直接選擇Sink節(jié)點作為下一跳路由節(jié)點。

（2）否則，當前節(jié)點應綜合考慮有效父節(jié)點的剩余能量、中繼跳數(shù)和傳輸時延等因素，盡可能選擇剩余能量高、中繼跳數(shù)少的節(jié)點作為下一跳路由以均衡和節(jié)省網絡能量消耗。

（3）對時延要求高的數(shù)據信息，選擇路由信息表中靠前的節(jié)點作為下一跳路由，以保證實時性。

2.4 路由維護

時延梯度路徑樹建立于網絡部署初期，隨著時間推移，節(jié)點可能因為意外情況或能耗過度而失效，導致數(shù)據無法及時可靠地傳回Sink節(jié)點。因此，需要對路由信息表采取必要的維護措施:

（1）節(jié)點應及時廣播自身剩余能量更新消息，其子節(jié)點根據消息更新路由信息表。

（2）當某節(jié)點剩余能量低于一定閾值時，廣播失效預警消息，避免成為中繼節(jié)點。

（3）節(jié)點路由信息表中父節(jié)點全部失效時，應適當增大發(fā)射功率，尋找新的有效父節(jié)點信息。

（4）新節(jié)點加入時只需廣播包含自身ID的加入請求消息。接收到該消息的鄰居節(jié)點發(fā)送生成樹消息作為應答。新節(jié)點按照生成樹的建立方法相應地更新自身跳數(shù)和路由表信息，并廣播包含自身信息的生成樹消息。鄰居節(jié)點根據此消息相應地調整路由表信息。

3 仿真及性能分析

為了評價本文算法的性能，在 Matlab環(huán)境下，對大規(guī)模WSN突發(fā)事件監(jiān)測場景進行了模擬實現(xiàn)，將本文算法（仿真圖中簡寫為ET）與LEACH［3］、AEEC［5］、ARPEES［9］算法進行對比驗證。仿真參數(shù)設置如表1所示。

表1 仿真參數(shù)Table 1 Simulation parameters

圖2為每輪事件結束后網絡剩余能量比較。采用LEACH算法時網絡能量消耗速率最快，AEEC算法次之，ARPEES算法能量消耗較緩，本文算法最優(yōu)，說明在節(jié)省和均衡能量消耗方面本文算法優(yōu)于其他幾種算法。

圖2 網絡剩余能量比較Fig.2 Contrast of residual energy of network

圖3為每輪事件結束后存活節(jié)點的數(shù)目比較。從圖中可以看出:網絡有效工作期內的任何時刻采用本文算法的存活節(jié)點數(shù)都多于其他幾種算法。

由圖2和圖3可以得出:在網絡生命周期方面，本文算法比LEACH、AEEC算法分別提高2倍和1.4倍，較ARPEES算法提高了15%。相對于傳統(tǒng)的預成簇算法（如LEACH算法和AEEC算法），事件驅動成簇算法（如ARPEES和本文算法）在節(jié)省網絡能量方面具有明顯優(yōu)勢。原因主要在于事件驅動成簇算法中與事件不相關的節(jié)點不參與簇頭競選和成簇，避免了不必要的能量消耗。同時，本文算法采用的簇頭選舉算法、自適應功率調整、控制消息延遲轉發(fā)等機制進一步節(jié)省和均衡了網絡能量消耗，使得本文算法優(yōu)于ARPEES算法。

圖3 網絡存活節(jié)點數(shù)比較Fig.3 Contrast of number of node alive in the network

本文進行了100次重復試驗以克服仿真隨機性影響，得到網絡中發(fā)生首個節(jié)點死亡和死亡節(jié)點數(shù)目達到一半的時間，如圖4和圖5所示。由圖可見:LEACH算法通常在第1000輪事件左右出現(xiàn)首個死亡節(jié)點，約3500輪事件后死亡節(jié)點數(shù)達到一半。AEEC、ARPEES以及本文算法的首個節(jié)點死亡通常發(fā)生在第6000輪事件左右。AEEC和ARPEES算法半數(shù)節(jié)點死亡分別發(fā)生在6500和10500輪事件左右，而本文算法在13000輪事件左右死亡節(jié)點數(shù)目才達一半。表明本文算法能夠更好地保證網絡的有效工作期。

圖4 首個節(jié)點死亡時間比較Fig.4 Contrast of time of first node dead

圖5 半數(shù)節(jié)點死亡時間比較Fig.5 Contrast of time of half node dead

4 結束語

針對大規(guī)模WSN突發(fā)事件監(jiān)測應用場景，提出了一種基于事件驅動成簇機制的路由策略。該策略在進行簇頭選舉時，不僅考慮了節(jié)點剩余能量信息，還考慮其距離Sink節(jié)點的跳數(shù)、與鄰居節(jié)點的連通性以及父節(jié)點數(shù)目等因素，從而達到節(jié)省和均衡網絡能量消耗的目的。同時，利用時延梯度路徑樹的建立為數(shù)據回傳提供最短時延路徑和多條備用路徑選擇，保障了數(shù)據傳輸?shù)膶崟r性和可靠性。仿真結果表明:本文策略在節(jié)省和均衡網絡能量方面優(yōu)于LEACH、AEEC以及ARPEES算法，使網絡生命周期比LEACH算法、AEEC算法分別提高2倍和1.4倍，較ARPEES算法延長了15%。

［1］Prabhu S R B，Sophia S.A survey of adaptive distributed clustering algorithms for wireless sensor networks［J］.International Journal of Computer Science and Engineering，2011，2（4）:165－176.

［2］Li Chang－le，Zhang Han－xiao，Hao Bin－bin，et al.A survey on routing protocols for large－scale wireless sensor networks［J］.Sensors，2011，11（4）:3498－3526.

［3］Heinzelman W R，Chandrakasan A P，Balakrishnan H.An application－specific protocol architecture for wireless microsensor networks［J］.IEEE Transactions on Wireless Communications，2002，1（4）:660－670.

［4］Bouabdallah N，Rivero－Angeles M E，Sericola B.Continuous monitoring using event－driven reporting for cluster－based wireless sensor networks［J］.IEEE Transactions on Vehicular Technology，2009，58（7）:3460－3479.

［5］Buyanjargal O，Kwon Y.Adaptive and energy efficient clustering algorithm for event－driven application in wireless sensor networks（AEEC）［J］.Networks，2010，5（8）:904－911.

［6］張小波，程良倫，Zhu Quan－min.SAHRC:一種基于分簇的無線傳感器網絡路由控制算法［J］.電子與信息學報，2011，33（8）:2013－2017.Zhang Xiao－bo，Cheng Liang－lun，Zhu Quan－min.SAHRC:a cluster－based routing control protocol for wireless sensor network［J］.Journal of Electronics＆Information Technology，2011，33（8）:2013－2017.

［7］官健，孫大洋，王愛民，等.無線傳感器網絡中基于廣播坐標的靜態(tài)鏈簇路由算法［J］.吉林大學學報:工學版，2012，42（2）:412－417.Guan Jian，Sun Da－yang，Wang Ai－min，et al.Static chain－cluster routing algorithm based on transmitting coordinate for wireless sensor network［J］.Journal of Jilin University（Engineering and Technology Edition），2012，42（2）:412－417.

［8］Zheng Zeng－wei，Wu Zhao－h(huán)ui，Lin Huai－zhong.An event－driven clustering routing algorithm for wireless sensor networks［C］∥Proceeding of IEEE／RSJ International Conference on Intelligent Robots and Systems，Sendai，2004:1802－1806.

［9］Quang V T，Miyoshi T.Adaptive routing protocol with energy efficiency and event clustering for wireless sensor networks［J］.IEICE Transactions on Communications，2008，91（9）:2795－2805.