用于大規(guī)模無(wú)線傳感器網(wǎng)絡(luò)突發(fā)事件監(jiān)測(cè)的路由策略

吳玉成，付紅玉

（重慶大學(xué) 通信工程學(xué)院，重慶 400044）

0 引 言

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

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

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

1 網(wǎng)絡(luò)模型和能量消耗模型

鑒于大規(guī)模WSN突發(fā)事件監(jiān)測(cè)場(chǎng)景，本文對(duì)網(wǎng)絡(luò)模型做如下假設(shè):

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

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

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

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

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

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

將N個(gè)長(zhǎng)度為k bit的數(shù)據(jù)包進(jìn)行數(shù)據(jù)融合處理所消耗的能量為

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

2 路由策略描述

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

2.1 時(shí)延梯度路徑樹(shù)的建立

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

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

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

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

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

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

2.2 簇頭選舉及成簇

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

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

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

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

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

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

（1）各相關(guān)節(jié)點(diǎn)生成包含ID和PCH0信息的簇頭選舉消息MCH0，并根據(jù)PCH0大小等待一個(gè)時(shí)間段Ti，其中Ti＝ （1－PCHi）×T0，i為節(jié)點(diǎn)ID，T0為一個(gè)常數(shù)?？梢?jiàn)，機(jī)率越小的節(jié)點(diǎn)等待的時(shí)間越長(zhǎng)。

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

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

（4）TN時(shí)段結(jié)束后，節(jié)點(diǎn)保存的MCH0即為當(dāng)前事件的簇頭節(jié)點(diǎn)信息。

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

2.3 路由選擇

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

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

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

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

2.4 路由維護(hù)

時(shí)延梯度路徑樹(shù)建立于網(wǎng)絡(luò)部署初期，隨著時(shí)間推移，節(jié)點(diǎn)可能因?yàn)橐馔馇闆r或能耗過(guò)度而失效，導(dǎo)致數(shù)據(jù)無(wú)法及時(shí)可靠地傳回Sink節(jié)點(diǎn)。因此，需要對(duì)路由信息表采取必要的維護(hù)措施:

（1）節(jié)點(diǎn)應(yīng)及時(shí)廣播自身剩余能量更新消息，其子節(jié)點(diǎn)根據(jù)消息更新路由信息表。

（2）當(dāng)某節(jié)點(diǎn)剩余能量低于一定閾值時(shí)，廣播失效預(yù)警消息，避免成為中繼節(jié)點(diǎn)。

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

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

3 仿真及性能分析

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

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

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

圖2 網(wǎng)絡(luò)剩余能量比較Fig.2 Contrast of residual energy of network

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

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

圖3 網(wǎng)絡(luò)存活節(jié)點(diǎn)數(shù)比較Fig.3 Contrast of number of node alive in the network

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

圖4 首個(gè)節(jié)點(diǎn)死亡時(shí)間比較Fig.4 Contrast of time of first node dead

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

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

針對(duì)大規(guī)模WSN突發(fā)事件監(jiān)測(cè)應(yīng)用場(chǎng)景，提出了一種基于事件驅(qū)動(dòng)成簇機(jī)制的路由策略。該策略在進(jìn)行簇頭選舉時(shí)，不僅考慮了節(jié)點(diǎn)剩余能量信息，還考慮其距離Sink節(jié)點(diǎn)的跳數(shù)、與鄰居節(jié)點(diǎn)的連通性以及父節(jié)點(diǎn)數(shù)目等因素，從而達(dá)到節(jié)省和均衡網(wǎng)絡(luò)能量消耗的目的。同時(shí)，利用時(shí)延梯度路徑樹(shù)的建立為數(shù)據(jù)回傳提供最短時(shí)延路徑和多條備用路徑選擇，保障了數(shù)據(jù)傳輸?shù)膶?shí)時(shí)性和可靠性。仿真結(jié)果表明:本文策略在節(jié)省和均衡網(wǎng)絡(luò)能量方面優(yōu)于LEACH、AEEC以及ARPEES算法，使網(wǎng)絡(luò)生命周期比LEACH算法、AEEC算法分別提高2倍和1.4倍，較ARPEES算法延長(zhǎng)了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:一種基于分簇的無(wú)線傳感器網(wǎng)絡(luò)路由控制算法［J］.電子與信息學(xué)報(bào)，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］官健，孫大洋，王愛(ài)民，等.無(wú)線傳感器網(wǎng)絡(luò)中基于廣播坐標(biāo)的靜態(tài)鏈簇路由算法［J］.吉林大學(xué)學(xué)報(bào):工學(xué)版，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.