鄭瑩，裴芳，董龍明

（1.常德職業(yè)技術(shù)學(xué)院，湖南常德415000；2.湖南機(jī)電職業(yè)技術(shù)學(xué)院，長沙410073；3.陸軍駐南京地區(qū)軍事代表室，南京210000）

新穎的冗余節(jié)點(diǎn)無線傳感網(wǎng)能量感知分簇算法*

鄭瑩1，裴芳2，董龍明3

（1.常德職業(yè)技術(shù)學(xué)院，湖南常德415000；2.湖南機(jī)電職業(yè)技術(shù)學(xué)院，長沙410073；3.陸軍駐南京地區(qū)軍事代表室，南京210000）

針對一類具有冗余節(jié)點(diǎn)的無線傳感網(wǎng)，提出了一種新穎的能量感知的動態(tài)分簇算法NEAC。它基于動態(tài)分簇路由機(jī)制，根據(jù)節(jié)點(diǎn)分布密集程度簇內(nèi)分布一定數(shù)量的休眠節(jié)點(diǎn)，在數(shù)據(jù)傳輸階段，這些休眠節(jié)點(diǎn)不感知和發(fā)送數(shù)據(jù)，當(dāng)簇首節(jié)點(diǎn)的能量消耗達(dá)到一定閾值后需要重新輪換簇首，它們被喚醒并根據(jù)休眠節(jié)點(diǎn)和簇首輪換機(jī)制實(shí)現(xiàn)快速簇首和休眠節(jié)點(diǎn)選舉以平衡節(jié)點(diǎn)間的能耗。仿真結(jié)果表明，與典型的分簇協(xié)議相比，NEAC能夠更好地平衡節(jié)點(diǎn)的能耗，獲得更長的網(wǎng)絡(luò)生存期。

節(jié)點(diǎn)冗余，無線傳感網(wǎng)，分簇算法，能量感知

0 引言

無線傳感網(wǎng)（WSN，wireless sensor network）是由分布在監(jiān)測區(qū)域內(nèi)的能夠采集環(huán)境數(shù)據(jù)、簡單數(shù)據(jù)處理和無線通信的大量傳感器節(jié)點(diǎn)通過無線通信協(xié)議構(gòu)成的無線多跳ad hoc網(wǎng)絡(luò)［1］。WSN能夠在寬闊惡劣的條件下，實(shí)時收集大量詳實(shí)可靠的一手?jǐn)?shù)據(jù)，被廣泛應(yīng)用于工業(yè)控制、環(huán)境監(jiān)測、交通管理、國防軍事等領(lǐng)域。與傳統(tǒng)網(wǎng)絡(luò)相比，WSN中的節(jié)點(diǎn)能夠協(xié)作地感知、采集、匯總和處理監(jiān)測區(qū)域的各種信息，WSN通常分布密集，節(jié)點(diǎn)數(shù)量能達(dá)到幾百至上千，傳感器節(jié)點(diǎn)體積小，采用電池供電，限制了節(jié)點(diǎn)的處理和通信能力。因此，如何高效平衡地使用節(jié)點(diǎn)的能量，最大化網(wǎng)絡(luò)生命期是無線傳感網(wǎng)面臨的主要挑戰(zhàn)，如何設(shè)計合理的無線傳感網(wǎng)數(shù)據(jù)收集協(xié)議綜合平衡節(jié)點(diǎn)的能耗，是衡量無線傳感網(wǎng)性能的重要因素。

無線傳感網(wǎng)在數(shù)據(jù)收集選擇傳輸路由算法時，通?？刹捎梅执芈酚桑?］、樹型結(jié)構(gòu)路由［3］和鏈型結(jié)構(gòu)路由［4］。分簇路由具有拓?fù)涔芾矸奖?、能量利用高效、?shù)據(jù)融合簡單的優(yōu)點(diǎn)。在分簇的數(shù)據(jù)收集協(xié)議中，網(wǎng)絡(luò)中的節(jié)點(diǎn)通常根據(jù)某種規(guī)則被劃歸為簇首節(jié)點(diǎn)和成員節(jié)點(diǎn)。簇首節(jié)點(diǎn)管理簇內(nèi)部成員節(jié)點(diǎn)，負(fù)責(zé)簇內(nèi)成員節(jié)點(diǎn)的數(shù)據(jù)收集融合處理以及簇間數(shù)據(jù)轉(zhuǎn)發(fā)。簇首節(jié)點(diǎn)承擔(dān)著主要的無線傳感網(wǎng)的任務(wù)，其失效往往影響整個簇的失效，雖然設(shè)計時可以賦予簇首節(jié)點(diǎn)高能量，但隨著時間的推移，簇首節(jié)點(diǎn)由于故障或能量急劇消耗從而導(dǎo)致整個簇失效。如何動態(tài)調(diào)整簇的規(guī)模選擇合適的簇首節(jié)點(diǎn)成為基于分簇的數(shù)據(jù)收集協(xié)議研究的熱點(diǎn)和難點(diǎn)。

國內(nèi)外研究學(xué)者針對分簇的無線傳感網(wǎng)數(shù)據(jù)收集協(xié)議相繼提出了多種典型的數(shù)據(jù)收集協(xié)議，如：LEACH算法［5］、PEGASID［6］、PEDAP協(xié)議［7］。LEACH算法隨機(jī)選取簇首，成員節(jié)點(diǎn)的數(shù)據(jù)匯聚到簇首節(jié)點(diǎn)后發(fā)送給基站，減少了與基站直接通信節(jié)點(diǎn)數(shù)據(jù)，協(xié)議在每輪隨機(jī)重新選擇簇首，理論上能夠?qū)⒛芰肯木鶆虻胤植荚谒泄?jié)點(diǎn)上，但是，算法很難保證簇首節(jié)點(diǎn)在網(wǎng)絡(luò)中的均勻分布。PEGASID協(xié)議根據(jù)節(jié)點(diǎn)的地理位置形成一條相鄰節(jié)點(diǎn)間距離最短的鏈，節(jié)點(diǎn)間的通信僅限于相鄰節(jié)點(diǎn)，可以有效地減少通信距離所消耗的能量，PEDAP協(xié)議在PEGASID協(xié)議進(jìn)一步優(yōu)化，將節(jié)點(diǎn)構(gòu)造一棵最小匯集樹，但是需要維護(hù)網(wǎng)絡(luò)全局信息，尤其是節(jié)點(diǎn)意外失效時，需要重新廣播全局信息。

本文針對一類具有大量冗余節(jié)點(diǎn)的無線傳感網(wǎng)絡(luò)，尤其是聚集在一起的節(jié)點(diǎn)同時感知同一個區(qū)域，不僅產(chǎn)生大量的冗余數(shù)據(jù)而且還增加了網(wǎng)絡(luò)的通信負(fù)載，并且消耗了節(jié)點(diǎn)的能量。通過增加大量冗余節(jié)點(diǎn)延遲無線傳感網(wǎng)生命周期在當(dāng)前分簇路由協(xié)議中沒有產(chǎn)生效果的問題。本文提出了一種新穎的冗余節(jié)點(diǎn)無線傳感網(wǎng)能量感知分簇算法（NEAC），它基于動態(tài)分簇調(diào)整機(jī)制，根據(jù)節(jié)點(diǎn)分布密集程度休眠一定數(shù)量的節(jié)點(diǎn)節(jié)約能量，在數(shù)據(jù)傳輸階段，這些休眠節(jié)點(diǎn)不感知和發(fā)送數(shù)據(jù)，當(dāng)簇首節(jié)點(diǎn)的能量消耗達(dá)到一定閾值后重新輪換簇首和休眠節(jié)點(diǎn)，以達(dá)到平衡簇內(nèi)節(jié)點(diǎn)能量的消耗，延長網(wǎng)絡(luò)生命期。

1 NEAC算法描述

本節(jié)首先給出NEAC算法的一些假設(shè)條件，然后提出節(jié)點(diǎn)調(diào)整機(jī)制，最后介紹NEAC算法的基本原理。

1.1假設(shè)條件

NEAC算法針對一類具有大量冗余節(jié)點(diǎn)的無線傳感網(wǎng)，因此，節(jié)點(diǎn)除了大量隨機(jī)分布在一個方形區(qū)域內(nèi)，并且具有下面的性質(zhì)：

①唯一的基站部署在無線網(wǎng)外部較遠(yuǎn)的距離；

②每個節(jié)點(diǎn)具有唯一的標(biāo)識ID，同質(zhì)，初始時具有相同的能量；

③傳感器節(jié)點(diǎn)部署后不再移動，且都知道自己的位置，基站BS知道節(jié)點(diǎn)的位置信息；

④鏈路是對稱的，兩個節(jié)點(diǎn)使用相同的能耗水平進(jìn)行通信；

⑤可根據(jù)節(jié)點(diǎn)距離的不同調(diào)節(jié)發(fā)射節(jié)點(diǎn)的功率，采用文獻(xiàn)［7］的能量模型。

能量衰減模型隨發(fā)送距離的遠(yuǎn)近分為自由空間模型和多路衰減模型：當(dāng)發(fā)送距離在一定閾值d0（d0為常量）內(nèi)，發(fā)送數(shù)據(jù)的功耗和距離的平方成正比；當(dāng)發(fā)送距離大于d0時，功耗和距離的四次方成正比，當(dāng)節(jié)點(diǎn)向距離d以外的另一個節(jié)點(diǎn)發(fā)送k個字節(jié)的數(shù)據(jù)時，其所消耗的能量由式（1）計算：

其中，Eelec表示收發(fā)電路所消耗的能量，Eamp表示信號放大器消耗的能量。

節(jié)點(diǎn)接受數(shù)據(jù)所消耗的能量由式（2）計算得到。

網(wǎng)絡(luò)中存在大量隨機(jī)分布的傳感器節(jié)點(diǎn)，有些區(qū)域聚集著大量的無線傳感器節(jié)點(diǎn)，如果同時檢測同一區(qū)域，會造成能量的浪費(fèi)而且產(chǎn)生大量冗余的數(shù)據(jù)，占用有限的網(wǎng)絡(luò)帶寬。本文設(shè)置休眠半徑r和分布密度ρ兩個參數(shù)控制部分聚集的節(jié)點(diǎn)休眠狀態(tài)以節(jié)約節(jié)點(diǎn)的能量。

休眠半徑r：節(jié)點(diǎn)n的休眠半徑為r，是指在節(jié)點(diǎn)n覆蓋半徑為r的區(qū)域內(nèi)，其他節(jié)點(diǎn)處于休眠狀態(tài)，不采集也不發(fā)送數(shù)據(jù)。

休眠節(jié)點(diǎn)nd：位于休眠區(qū)域內(nèi)的節(jié)點(diǎn)。

分布密度ρ：是指在節(jié)點(diǎn)n的休眠半徑r內(nèi)分布的節(jié)點(diǎn)數(shù)目。

如下頁圖1所示，節(jié)點(diǎn)n的休眠半徑為r，位于休眠區(qū)域內(nèi)的節(jié)點(diǎn)為休眠節(jié)點(diǎn)，節(jié)點(diǎn)n的分布密度為：5，休眠節(jié)點(diǎn)既不采集數(shù)據(jù)也不向簇頭發(fā)送數(shù)據(jù)。所有節(jié)點(diǎn)（除基站外）均為同質(zhì)，假設(shè)所有節(jié)點(diǎn)的休眠半徑相同。休眠半徑的大小和分布密度設(shè)定可以由網(wǎng)絡(luò)的應(yīng)用特點(diǎn)和節(jié)點(diǎn)采集特性決定。當(dāng)休眠半徑內(nèi)分布的節(jié)點(diǎn)達(dá)到一定分布密度時節(jié)點(diǎn)才處于休眠狀態(tài)。

圖1 帶有休眠節(jié)點(diǎn)的無線傳感網(wǎng)分布圖

1.2節(jié)點(diǎn)分簇

在系統(tǒng)初始化時，NEAC算法將傳感網(wǎng)絡(luò)中所有節(jié)點(diǎn)按照區(qū)域劃分成多個簇，各節(jié)點(diǎn)在簇內(nèi)廣播節(jié)點(diǎn)的位置和標(biāo)識信息，然后各節(jié)點(diǎn)接收到其他節(jié)點(diǎn)廣播的消息，得到在休眠半徑r內(nèi)節(jié)點(diǎn)的分布密度ρ（如果計算節(jié)點(diǎn)跨簇，則忽略）。

簇首節(jié)點(diǎn)采用簇間轉(zhuǎn)發(fā)方式經(jīng)過打包壓縮拆分等手段匯聚后根據(jù)簇間的路由表逐級傳輸至基站。算法每個簇首節(jié)點(diǎn)需要維護(hù)兩類信息：基本信息和簇間的路由信息。

對任意節(jié)點(diǎn)Ni，基本信息包括節(jié)點(diǎn)ID、簇首節(jié)點(diǎn)ID、剩余能量、休眠節(jié)點(diǎn)集合ND，可以用四元組表示：＜Node_ID，CH_ID，Res_Engergy，ND＞

節(jié)點(diǎn)ID是統(tǒng)一編碼，CH_ID表示簇首節(jié)點(diǎn)的ID，可以用來代表整個簇，節(jié)點(diǎn)通過CH_ID就可以在簇內(nèi)將感知到的數(shù)據(jù)傳遞給該簇首。剩余能量則是記錄節(jié)點(diǎn)當(dāng)前剩余的能量。ND描述了該節(jié)點(diǎn)休眠節(jié)點(diǎn)的集合，其集合元素個數(shù)為該節(jié)點(diǎn)的分布密度ρ。

簇間路由信息維護(hù)與本簇相鄰接監(jiān)控區(qū)域的簇首節(jié)點(diǎn)信息，可以用2個隊列表示：轉(zhuǎn)發(fā)隊列TransferQueue和區(qū)域鄰接隊列NeighAreaQueue。這2個隊列在系統(tǒng)初始化時構(gòu)建，轉(zhuǎn)發(fā)隊列記錄了該簇首節(jié)點(diǎn)可以將數(shù)據(jù)轉(zhuǎn)發(fā)下一個簇首ID，區(qū)域隊列記錄了與該簇地理相鄰的簇首ID，用來動態(tài)調(diào)整簇的大小。轉(zhuǎn)發(fā)隊列在傳感網(wǎng)節(jié)點(diǎn)分簇確定簇首節(jié)點(diǎn)后構(gòu)建，由基站廣播一則消息，通過與基站距離的遠(yuǎn)近構(gòu)建一條通往基站的鏈路，為了增強(qiáng)傳感網(wǎng)的容錯性，通往基站的鏈路可能不止一路，簇首可以選擇多個簇間首節(jié)點(diǎn)轉(zhuǎn)發(fā)數(shù)據(jù)傳遞給基站。

1.3簇首選舉及數(shù)據(jù)轉(zhuǎn)發(fā)

簇內(nèi)簇首選擇根據(jù)節(jié)點(diǎn)關(guān)于休眠半徑的分布密度大小選擇合適的節(jié)點(diǎn)作為節(jié)點(diǎn)，原則上選擇剩余能量和分布密度最大的節(jié)點(diǎn)作為簇首節(jié)點(diǎn)，可以通過計算公式w=w1*Res_Energy+w2*ρ（w1+w2=1， 0＜w1，w2，＜1）求得w最大值作為簇首節(jié)點(diǎn)，當(dāng)有多個w最大值時可以隨機(jī)選擇某個節(jié)點(diǎn)作為簇首節(jié)點(diǎn)。分布密度大說明在簇首能量不足時需要更換簇首節(jié)點(diǎn)時，可供選取替換的相鄰節(jié)點(diǎn)多。

在NEAC算法中，簇首節(jié)點(diǎn)的數(shù)據(jù)經(jīng)過轉(zhuǎn)發(fā)隊列中的簇首節(jié)點(diǎn)轉(zhuǎn)發(fā)，最后將數(shù)據(jù)轉(zhuǎn)發(fā)到基站。圖2完整地描述了NEAC算法中數(shù)據(jù)收集并傳輸?shù)交镜倪^程。首先，各簇內(nèi)節(jié)點(diǎn)將數(shù)據(jù)分布匯聚到簇首節(jié)點(diǎn)CHi、CHj和CHm中。CHi和CHj、CHj和CHm構(gòu)成了區(qū)域鄰接隊列，CHj為簇首節(jié)點(diǎn)CHi的轉(zhuǎn)發(fā)隊列，CHm為簇首節(jié)點(diǎn)CHj的轉(zhuǎn)發(fā)隊列。因此，簇首節(jié)點(diǎn)CHi將數(shù)據(jù)由簇內(nèi)數(shù)據(jù)匯聚后傳遞給簇首節(jié)點(diǎn)CHj，然后簇首節(jié)點(diǎn)CHj將接收到數(shù)據(jù)和簇內(nèi)收集的數(shù)據(jù)匯總打包一并傳輸給簇首節(jié)點(diǎn)CHm，最后，簇首節(jié)點(diǎn)CHm將匯總后的數(shù)據(jù)傳輸給基站。

圖2 簇首節(jié)點(diǎn)數(shù)據(jù)傳輸路徑

1.4簇首動態(tài)調(diào)整策略

當(dāng)無線傳感網(wǎng)運(yùn)行一點(diǎn)階段后，由于簇首節(jié)點(diǎn)承擔(dān)著大量的數(shù)據(jù)匯總和傳輸任務(wù)，造成能量急劇消耗，當(dāng)能量消耗至某個極限值時不再具備簇首節(jié)點(diǎn)和轉(zhuǎn)發(fā)數(shù)據(jù)的資格。在這種情況下，NEAC算法設(shè)置簇首動態(tài)調(diào)整策略：首先在當(dāng)前簇首節(jié)點(diǎn)的休眠節(jié)點(diǎn)集合ND選擇能量最高的節(jié)點(diǎn)被喚醒作為該簇新的簇首節(jié)點(diǎn)，如果休眠集合中節(jié)點(diǎn)能量均低于該能量極限值，則需要在簇內(nèi)重新選取能量高的和分布半徑較大的節(jié)點(diǎn)作為新的簇首，最大限度地延遲無線傳感網(wǎng)的生命周期。該算法偽代碼描述如下：

2 性能分析

2.1參數(shù)設(shè)置

本文采用基于Java的DTN仿真工具ONE（Opportunistic Network Environment）［8］進(jìn)行仿真實(shí)驗(yàn)。為了驗(yàn)證本文協(xié)議的有效性，分別對LEACH［2］、MTP［5］和NEAC 3種協(xié)議分布從能耗和網(wǎng)絡(luò)生存周期進(jìn)行對比。實(shí)驗(yàn)中各項(xiàng)參數(shù)設(shè)置如表1所示。每次輪巡節(jié)點(diǎn)是否發(fā)送數(shù)據(jù)包是隨機(jī)的，模擬真實(shí)傳感網(wǎng)環(huán)境的數(shù)據(jù)收集，網(wǎng)絡(luò)中隨機(jī)分布大量冗余的無線傳感網(wǎng)節(jié)點(diǎn)。

表1 實(shí)驗(yàn)參數(shù)列表

2.2實(shí)驗(yàn)結(jié)果及分析

無線傳感網(wǎng)絡(luò)生命期主要關(guān)心網(wǎng)絡(luò)中第1個節(jié)點(diǎn)的死亡時間和最后一個節(jié)點(diǎn)的死亡時間，為了比較3種算法的優(yōu)劣，同時關(guān)心網(wǎng)絡(luò)中第1個節(jié)點(diǎn)死亡時間和最后一個節(jié)點(diǎn)死亡時間，仿真結(jié)束時間定義在最后一個節(jié)點(diǎn)死亡時間，完整的網(wǎng)絡(luò)生命期仿真結(jié)果如圖3所示。這次選取網(wǎng)絡(luò)中節(jié)點(diǎn)個數(shù)為300。

圖3 網(wǎng)絡(luò)生命周期仿真結(jié)果

網(wǎng)絡(luò)能量的均衡性主要考慮網(wǎng)絡(luò)運(yùn)行中每輪網(wǎng)絡(luò)能量的消耗情況，圖4顯示了網(wǎng)絡(luò)能量消耗的仿真結(jié)果。

從圖4中可以看出，NEAC算法的能量消耗曲線比LEACH和MTP更加平滑，這說明NEAC算法的能量均衡性比LEACH和MTP要優(yōu)良，同時，NEAC的曲線總是位于LEACH和MTP的下方，因?yàn)镹EAC算法在每輪中總有節(jié)點(diǎn)處于休眠狀態(tài)，這樣能夠節(jié)約能量，延長網(wǎng)絡(luò)的使用壽命。

3 結(jié)論

本文提出了一種針對一類存在大量冗余節(jié)點(diǎn)的無線傳感網(wǎng)能量感知分簇算法（NEAC）。該算法針對無線傳感網(wǎng)中冗余節(jié)點(diǎn)，有選擇性地選擇聚集密集的節(jié)點(diǎn)設(shè)置為休眠狀態(tài)以節(jié)約節(jié)點(diǎn)的能量和節(jié)約網(wǎng)絡(luò)傳輸帶寬，仿真實(shí)驗(yàn)結(jié)果表示該算法能夠有效地降低節(jié)點(diǎn)的能耗和延長網(wǎng)絡(luò)生命周期。簇首節(jié)點(diǎn)的選取和簇間路由的優(yōu)化能夠提高無線傳感網(wǎng)的數(shù)據(jù)采集和數(shù)據(jù)傳輸效率，如何設(shè)計更加智能合理的簇間路由策略，使其在能耗、網(wǎng)絡(luò)生存期和數(shù)據(jù)傳輸延遲等方面具有較優(yōu)的性能是下一步研究的重點(diǎn)和方向。

［1］VIDYASAGAR P，ATIF S，ELIZABETH C.Wireless sensor networks：a survey［C］//International Conference on Advanced Information Networking and Applications Workshops. Bradford，United Kingdom，2009：636-641.

［2］鄭相全.無線自組網(wǎng)技術(shù)實(shí)用教程［M］.北京：清華大學(xué)出版社，2004.

［3］CALLAWAY E H.無線傳感器網(wǎng)絡(luò)［M］.馬偉明，王永斌，譯.北京：電子工業(yè)出版社，2007.

［4］DU K，WU J，ZHOU D.Chain-based protocols for data broadcasting and gathering in the sensor networks［C］//In：Proc.of the International Parallel and Distributed ProcessingSymposium，2003.

［5］HEINZELMANWR，KULIKJ，BALAKRISHNANH. Adaptive protocols for information dissemination in wireless sensor networks［C］//Proceeding of the 5th Annual International Conference on Mobile Computing and Networking. New York：ACM Press，2001：174-185.

［6］LINDSEY S，RAGHAVENDRA C S.Pegasis：Power-effi

cient gathering in sensor information systems［C］//Proceeding of IEEE Aerospace Conference 2002.Los Alamitos，CA： IEEE Computer Society Press，2002：1-6.

［7］HEINZELMAN W B，CHANDRAKASAN A P，BALAKRISHNAN H.An application-specific protocol architecture for wireless microsensor networks［C］//IEEE Transactions on Wireless Communications，2002，1：660-670.

［8］KERANEN A，OTT J，KARKKAINEN T.The ONE simulator for DTN protocol evaluation［C］//SIMUTools’09：Proceedings of the 2nd International Conference on Simulation Tools and Techniques，New York，NY，USA，2009.

Novel Energy-Aware Clustering Algorithm for WSN with Redundant Nodes

ZHENG Ying1，PEI Fang2，DONG Long-ming3
（1.Changde Vocational Technical College，Changde 415000，China；2.Hunan Mechanical and Electrical Polytechnic，Changsha 410073，China；3.Nanjing Military Representative Office of PLA Army，Nanjing 210000，China）

This paper proposes a novel energy-aware clustering algorithm for wireless sensor network with redundant nodes，called NEAC.It is based on clustering routing mechanism and distributes certain number of dormant nodes according to the intensive distribution of cluster nodes. These dormant nodes do not perceive and send any data during data transmission phase.When the energy consumption of cluster head nodes reaches a certain threshold and needs to be replaced，those dormant nodes around the cluster heads are waken up and then cluster head nodes and dormant nodes are rapidly elected again according to the cluster head rotating mechanism，which can balance energy consumption of WSN.Simulation results show that compared with typical clustering protocols，NEAC can balance the energy consumption of nodes better，and thus increase the lifetime of WSN.

redundant nodes，wireless sensor network，clustering algorithm，energy-aware

TP393.02

A

1002-0640（2016）11-0104-04

2015-10-09

2015-11-17

湖南省教育廳課題（13C258）；湖南省常德市科技局基金資助項(xiàng)目（2014JF11）

鄭瑩（1977-），女，湖南常德人，副教授。研究方向：網(wǎng)絡(luò)安全、無線傳感網(wǎng)。