基于剩余能量和覆蓋率感知的分簇協(xié)議

韓艷 王靜宇 譚躍生

摘 要： 保持目標(biāo)區(qū)域的覆蓋是無(wú)線(xiàn)傳感網(wǎng)絡(luò)（WSN）應(yīng)用的最根本目標(biāo)，因此，設(shè)計(jì)能量有效算法進(jìn)而最大化覆蓋時(shí)間成為大型網(wǎng)絡(luò)的核心問(wèn)題。為此，提出分布式、能量和覆蓋感知路由（DECAR）協(xié)議實(shí)現(xiàn)網(wǎng)絡(luò)覆蓋最大化的目標(biāo)。在簇頭（CH）選舉中，考慮節(jié)點(diǎn)的剩余能量和節(jié)點(diǎn)的覆蓋重疊度，使得具有較高的剩余能量節(jié)點(diǎn)、覆蓋重疊度高的節(jié)點(diǎn)有更多的機(jī)會(huì)成為CH，進(jìn)而避免了剩余能量較小的節(jié)點(diǎn)成為CH而產(chǎn)生節(jié)點(diǎn)過(guò)早失效使網(wǎng)絡(luò)壽命縮短的問(wèn)題，平衡了網(wǎng)絡(luò)能量消耗。在數(shù)據(jù)傳輸階段，構(gòu)建由CH組成的數(shù)據(jù)傳輸主干線(xiàn)，提高數(shù)據(jù)傳輸效率。仿真結(jié)果表明，與CPCP?ea，EEUC協(xié)議相比，提出的DECAR協(xié)議具有較長(zhǎng)的網(wǎng)絡(luò)壽命和良好的數(shù)據(jù)覆蓋率。

關(guān)鍵詞： 無(wú)線(xiàn)傳感網(wǎng)； 簇； 能量； 覆蓋率； 網(wǎng)絡(luò)壽命

中圖分類(lèi)號(hào)： TN915.04?34； TPT393 文獻(xiàn)標(biāo)識(shí)碼： A 文章編號(hào)： 1004?373X（2016）09?0022?05

Abstract： The most fundamental target of the wireless sensor network （WSN） application is to preserve the coverage of the target area. Therefore， the design of the energy efficient algorithm to cover the time to the maximum extent is the central problem of the large?scale network. The distributed?energy and coverage aware routing （DECAR） protocol is proposed to realize the target of maximum network coverage. The CH （cluster head） election is based on the residual energy and coverage overlapping degree of the nodes， so the node with high residual energy and high coverage overlapping degree has more opportunity to become the CH. The problem of reducing network lifetime is avoided， which is caused by the node premature failure when the node with less residual energy becomes the CH. The network energy consumption is balanced. In data transmission stage， the data transmission backbone composed of the CHs was constructed to improve the data transmission rate. The simulation results show that the proposed DECAR protocol has longer network lifetime and wider coverage rate than those of the CPCP?ea and EEUC protocols.

Keywords： wireless sensor network； cluster； energy； coverage rate； network lifetime

0 引 言

隨著現(xiàn)代電子技術(shù)的發(fā)展，無(wú)線(xiàn)傳感網(wǎng)絡(luò)（Wireless Sensor Network，WSN）在各類(lèi)應(yīng)用中廣泛使用，如康復(fù)醫(yī)療、戰(zhàn)場(chǎng)、野外環(huán)境監(jiān)測(cè)等[1]。這些應(yīng)用場(chǎng)景中均需要在目標(biāo)區(qū)域以隨機(jī)或特定方式部署傳感節(jié)點(diǎn)，然后傳感節(jié)點(diǎn)感測(cè)環(huán)境數(shù)據(jù)，并以直接或間接方式向簇頭（Cluster Head，CH）傳輸。為了能夠?qū)崟r(shí)監(jiān)測(cè)環(huán)境，目標(biāo)區(qū)域必須由傳感節(jié)點(diǎn)完全覆蓋。因此，為了保持目標(biāo)區(qū)域完全覆蓋，通常以冗余方式部署大量的傳感節(jié)點(diǎn)，以避免覆蓋空洞[2]。然而，由于傳感節(jié)點(diǎn)能量有限以及供給不足，一些傳感節(jié)點(diǎn)因能量消耗而失效，導(dǎo)致覆蓋空洞。因此，提高節(jié)點(diǎn)能量利用率、解決覆蓋空洞問(wèn)題成為無(wú)線(xiàn)傳感網(wǎng)絡(luò)的研究熱點(diǎn)。

目前研究人員已提出了不少的能量保存技術(shù)[3]。這些技術(shù)的目標(biāo)就是降低傳感節(jié)點(diǎn)的能量消耗，進(jìn)而擴(kuò)展網(wǎng)絡(luò)壽命，從而維持目標(biāo)區(qū)域的完全覆蓋。其中，基于簇的技術(shù)因其在提高能量利用率方面的優(yōu)勢(shì)被大家所熟知。在基于簇的技術(shù)中，所有傳感節(jié)點(diǎn)劃分為不同的簇，每個(gè)簇有一個(gè)CH，其他傳感節(jié)點(diǎn)為簇成員（Cluster Members，CMs）。簇頭CHs負(fù)責(zé)收集并融合CMs的感測(cè)數(shù)據(jù)，再以多跳通信方式轉(zhuǎn)發(fā)至信宿Sink。

針對(duì)無(wú)線(xiàn)傳感網(wǎng)絡(luò)，研究人員已提出了大量的簇算法[4?7]。然而，由于部分傳感節(jié)點(diǎn)的失效，這些算法并不能保證目標(biāo)區(qū)域被完全覆蓋。因此，基于簇的算法應(yīng)需能感知覆蓋區(qū)域，進(jìn)而維持傳感網(wǎng)絡(luò)的覆蓋壽命。換而言之，即使在部分傳感節(jié)點(diǎn)失效的情況下，無(wú)線(xiàn)傳感網(wǎng)絡(luò)仍應(yīng)維持最大化的覆蓋區(qū)域。文獻(xiàn)[8]已提出了覆蓋感知的簇算法，但是這些算法均忽略傳感節(jié)點(diǎn)覆蓋區(qū)域重疊問(wèn)題。

此外，文獻(xiàn)[9?11]提出了基于簇的多跳路由協(xié)議，其作為延長(zhǎng)網(wǎng)絡(luò)壽命的有效技術(shù)。在多跳通信中，CH通過(guò)其他簇頭CHs作為中間轉(zhuǎn)發(fā)節(jié)點(diǎn)向信宿傳輸數(shù)據(jù)。然而，該協(xié)議的主要問(wèn)題在于：靠近信宿的簇頭CHs承擔(dān)著更多的數(shù)據(jù)轉(zhuǎn)發(fā)任務(wù)，這加速了其能量消耗，易形成能量空洞問(wèn)題。

為此，本文提出了分布式、能量和覆蓋感知路由DECAR（Distributed?energy and Coverage Aware Routing）協(xié)議，提高網(wǎng)絡(luò)覆蓋壽命。在DECAR協(xié)議中，首先形成大小不一的簇，解決在數(shù)據(jù)傳輸過(guò)程中離信宿節(jié)點(diǎn)近的簇頭CHs能量消耗過(guò)快的問(wèn)題。然后，在每個(gè)簇內(nèi)，利用節(jié)點(diǎn)的剩余能量以及其覆蓋區(qū)域重疊度選擇CH。最后，建立由CH構(gòu)成的主干數(shù)據(jù)傳輸路徑。仿真結(jié)果表明，提出的DECAR協(xié)議能夠有效地延長(zhǎng)網(wǎng)絡(luò)壽命降低能量消耗。

1 網(wǎng)絡(luò)模型

本文考慮無(wú)線(xiàn)傳感網(wǎng)絡(luò)節(jié)點(diǎn)均是同構(gòu)的，初始能量相同。一旦部署于目標(biāo)區(qū)域就靜止不動(dòng)，即屬于靜態(tài)網(wǎng)絡(luò)。此外，傳感節(jié)點(diǎn)利用定位技術(shù)[12]能夠獲取自己的位置信息。

1.1 網(wǎng)絡(luò)時(shí)序

本文將網(wǎng)絡(luò)時(shí)序劃分為多個(gè)周期，一個(gè)周期稱(chēng)為一輪。每輪內(nèi)設(shè)有簇化和數(shù)據(jù)傳輸階段。如圖1所示。

簇化階段選擇簇頭，并形成簇；數(shù)據(jù)傳輸階段進(jìn)行數(shù)據(jù)傳輸。簇內(nèi)節(jié)點(diǎn)感測(cè)數(shù)據(jù)，并將數(shù)據(jù)發(fā)送于簇頭，收集并融合后，簇頭將數(shù)據(jù)傳輸至基站。為了避免節(jié)點(diǎn)間數(shù)據(jù)傳輸?shù)南嗷ジ蓴_，在傳輸過(guò)程中，為每個(gè)節(jié)點(diǎn)分配一個(gè)時(shí)隙，節(jié)點(diǎn)在該時(shí)隙內(nèi)進(jìn)行數(shù)據(jù)傳輸。

1.2 能量模型

此外，將DECAR協(xié)議的仿真數(shù)據(jù)同CPCP?ea[8]以及EEUC[14]協(xié)議在網(wǎng)絡(luò)壽命、覆蓋壽命以及其他性能進(jìn)行比較。其中覆蓋壽命用輪數(shù)表示，其數(shù)值等于目標(biāo)區(qū)域被完全覆蓋所持續(xù)的輪數(shù)。若在[M]輪目標(biāo)區(qū)域被完全覆蓋，而[M+1]輪目標(biāo)區(qū)域未被完全覆蓋，則覆蓋壽命為[M]輪。同理，網(wǎng)絡(luò)壽命也用輪數(shù)表示，其數(shù)值等于網(wǎng)絡(luò)內(nèi)第一節(jié)點(diǎn)失效時(shí)所發(fā)生的輪數(shù)。

3.2 網(wǎng)絡(luò)壽命及能量消耗

首先分析了DECAR方案的能量消耗以及失效簇頭數(shù)，結(jié)果如圖5所示。在同輪Round情況下，提出的DECAR方案的能量消耗少于CPCP?ea和EEUC方案。這主要是因?yàn)镃PCP?ea協(xié)議未考慮簇頭失效的情況，能量利用率低。在簇頭失效的情況下，仍向簇頭傳輸數(shù)據(jù)，浪費(fèi)了能量。而EEUC協(xié)議優(yōu)于CPCP?ea協(xié)議，原因在于EEUC協(xié)議考慮了CH的失效情況。

此外，圖5還描述了幾個(gè)協(xié)議的CH失效數(shù)。數(shù)據(jù)顯示DECAR協(xié)議的失效簇頭CHs明顯少于CPCP?ea和EEUC。

表2列舉了部分實(shí)驗(yàn)數(shù)據(jù)。從表2可知，在能量消耗了近50%時(shí)，提出的DECAR協(xié)議已運(yùn)行至1 082輪，而CPCP?ea，EEUC分別運(yùn)行了477輪、478輪。從能量消耗數(shù)據(jù)可知，DECAR協(xié)議比CPCP?ea，EEUC協(xié)議的能量消耗利用率分別提升了127.0%，126.6%。例如，在運(yùn)行1 000輪時(shí)，提出的DECAR協(xié)議僅消耗了22.0 J能量，而CPCP?ea協(xié)議，EEUC協(xié)議分別消耗了48.6 J，47.5 J。

表3列舉了實(shí)驗(yàn)中的兩項(xiàng)數(shù)據(jù)：運(yùn)行2 000輪后，活動(dòng)節(jié)點(diǎn)數(shù)；第一個(gè)失效節(jié)點(diǎn)的總運(yùn)行輪數(shù)，即網(wǎng)絡(luò)壽命。從表3可知，與CPCP?ea協(xié)議相比，提出的DECAR協(xié)議在第一個(gè)失效節(jié)點(diǎn)發(fā)生時(shí)間上提升了66.9%，比EEUC協(xié)議提升了71.9%。這些性能提升歸功于DECAR協(xié)議利用節(jié)點(diǎn)剩余能量和覆蓋重疊率選擇簇頭。

3.3 覆蓋率

圖6 繪制了三類(lèi)協(xié)議的覆蓋率變化曲線(xiàn)。從圖6可知，提出的DECAR協(xié)議的覆蓋率優(yōu)于EEUC，CPCP?ea協(xié)議。原因在于DECAR協(xié)議提高了能量利用率，降低了節(jié)點(diǎn)的能量消耗，同時(shí)，優(yōu)化了數(shù)據(jù)傳輸路徑。

4 結(jié) 語(yǔ)

針對(duì)無(wú)線(xiàn)傳感網(wǎng)絡(luò)的數(shù)據(jù)傳輸問(wèn)題，提出DEACR協(xié)議，DEACR協(xié)議引用簇技術(shù)。首先將傳感節(jié)點(diǎn)劃分為不同的簇，每個(gè)簇依據(jù)節(jié)點(diǎn)的剩余能量以及覆蓋區(qū)域的重疊度選擇CH，其余節(jié)點(diǎn)作為該簇的成員節(jié)點(diǎn)。然后，建立由CH構(gòu)成的數(shù)據(jù)傳輸主線(xiàn)。數(shù)據(jù)攜帶CH計(jì)算與鄰居各CH的成本，選擇成本大的節(jié)點(diǎn)作為下一跳數(shù)據(jù)轉(zhuǎn)發(fā)節(jié)點(diǎn)。由于成本函數(shù)蘊(yùn)含節(jié)點(diǎn)剩余能量以及路徑損耗信息，成本越大，意味著剩余能量大、路徑損耗小。這些均有利于存儲(chǔ)能量，擴(kuò)展網(wǎng)絡(luò)壽命。最后，對(duì)協(xié)議進(jìn)行仿真，分析它在網(wǎng)絡(luò)壽命、覆蓋率以及能量消耗方面的性能。仿真結(jié)果表明，提出的DEACR協(xié)議能夠降低能量消耗，擴(kuò)展網(wǎng)絡(luò)壽命，進(jìn)而提高覆蓋率。

參考文獻(xiàn)

[1] MURUGANATHAN S D， MA D C， BHASIN R I. A centra?lized energy?efficient routing protocol for wireless sensor networks [J]. IEEE radio communications， 2011， 43（3）： 8?13.

[2] 沈艷霞，薛小松.無(wú)線(xiàn)傳感網(wǎng)絡(luò)移動(dòng)信標(biāo)節(jié)點(diǎn)路徑優(yōu)化策略[J].傳感器與微系統(tǒng)，2012，31（12）：42?46.

[3] WANG S S， CHEN Z P. LCM： a link?aware clustering mechanism for energy?efficient routing in wireless sensor networks [J]. IEEE sensors journal， 2013， 13（2）： 728?736.

[4] KUILA P， GUPTA S K， JANA P K. A novel evolutionary approach for load balanced clustering problem for wireless sensor networks [J]. Swarn and evolutionary computation， 2013， 12： 48?56.

[5] NAUMAN A， WILLIAM P， WILLIAM R， et al. A multi?criterion optimization technique for energy efficient cluster formation in wireless sensor networks [J]. Information fusion， 2011， 12（3）： 202?212.

[6] AMINI N， VAHDATPOUR A， XU W， et al. Cluster size optimization in sensor networks with decentralized cluster?based protocols [J]. Computer communications， 2012， 35（2）： 207?220.

[7] AMGOTH T， JANA P K. BDCP： a backoff?based distributed clustering protocol for wireless sensor networks [C]// Procee?dings of 2013 International Conference on Advances in Compu?ting， Communication and Informatics. Mysore： IEEE， 2013： 1012?1016.

[8] TAO Y， ZHANG Y， JI Y. Flow?balanced routing for multi?hop clustered wireless sensor networks [J]. Ad Hoc networks， 2013， 11（1）： 541?554.

[9] ABDEL SALAM H S， OLARIU S. BEES： bioinspired backbone selection in wireless sensor networks [J]. IEEE transactions on parallel and distributed systems， 2012， 23（1）： 44?51.

[10] LIU Y， WANG Z. Maximizing energy utilization routing scheme in wireless sensor networks based on minimum hops algorithm [J]. Computers and electrical engineering， 2012， 38（3）： 703?721.

[11] YU Jiguo， QI Yingying， WANG Guangui， et al. A cluster?based routing protocol for wireless sensor with non?uniform node distribution [J]. International journal of electronics and communications， 2012， 66（1）： 54?61.

[12] NICULESCU D， NATH B. Ad Hoc positioning system [C]// Proceedings of 2001 IEEE Global Telecommunications Confe?rence. [S.l.]： IEEE， 2001： 2926?2931.

[13] LIU Y， SUO L， SUN D， et al. A virtual square grid?based coverage algorithm of redundant node for wireless sensor network [J]. Journal of network and computer application， 2013， 36（2）： 811?817.

[14] SORO S， HEINZELMAN W B. Cluster head election techniques for coverage preservation in wireless sensor networks [J]. Ad Hoc networks， 2009， 7（5）： 955?972.