基于企鵝過(guò)冬行為的提高網(wǎng)絡(luò)壽命算法性能分析

陳中良，程　磊

（黃淮學(xué)院，河南駐馬店463000）

?

基于企鵝過(guò)冬行為的提高網(wǎng)絡(luò)壽命算法性能分析

陳中良，程磊

（黃淮學(xué)院，河南駐馬店463000）

摘要：由于傳感節(jié)點(diǎn)能量供應(yīng)受限，為延長(zhǎng)無(wú)線傳感網(wǎng)絡(luò)（wireless sensor networks，WSNs）壽命，提出基于能量消耗率的節(jié)點(diǎn)位置對(duì)調(diào)（energy consumption ratio-based node rotation，ECRNR）方案。ECRNR方案將能量消耗率高的傳感節(jié)點(diǎn)位置由多個(gè)傳感節(jié)點(diǎn)輪流駐守，即由多個(gè)傳感節(jié)點(diǎn)一起分擔(dān)任務(wù)，避免由單一傳感節(jié)點(diǎn)獨(dú)自承擔(dān)繁重任務(wù)而能量過(guò)早耗盡。仿真結(jié)果表明：提出的ECRNR方案能夠有效提高網(wǎng)絡(luò)壽命，與傳統(tǒng)的方案相比，網(wǎng)絡(luò)壽命得到有效提高。

關(guān)鍵詞：網(wǎng)絡(luò)壽命；能量消耗；移動(dòng)；無(wú)線傳感網(wǎng)絡(luò)

0　引言

無(wú)線傳感網(wǎng)絡(luò)（wireless sensor networks，WSNs）在棲息地監(jiān)控[1]、環(huán)境監(jiān)控[2-3]以及監(jiān)視系統(tǒng)[4]（surveillance systems）等領(lǐng)域應(yīng)用廣泛。這些應(yīng)用需要收集大量數(shù)據(jù)，并向信宿Sink傳輸，因此需長(zhǎng)期保持工作狀態(tài)。然而，WSNs內(nèi)節(jié)點(diǎn)是基于有限能量供應(yīng)，如電池，并且WSNs部署于野外環(huán)境，極難第2次充電或替換電池。一旦能量消耗，傳感節(jié)點(diǎn)就無(wú)法工作，影響整個(gè)WSNs工作時(shí)間，即縮短了網(wǎng)絡(luò)壽命（network lifetime）。在這種情況下，為了延長(zhǎng)網(wǎng)絡(luò)壽命，只能合理地利用傳感節(jié)點(diǎn)的能量。為此，WSNs應(yīng)用的最大挑戰(zhàn)就是：如何有效地管理節(jié)點(diǎn)能量消耗，以最大化整個(gè)網(wǎng)絡(luò)壽命。

研究證實(shí)，限制傳感節(jié)點(diǎn)移動(dòng)，即受控移動(dòng)（controlled mobility）方案能夠有效地提高WSNs能量消耗效率，如調(diào)整移動(dòng)節(jié)點(diǎn)位置[5-8]、調(diào)整網(wǎng)絡(luò)通信拓?fù)浣Y(jié)構(gòu)[8-11]。

企鵝常處于-45℃低溫環(huán)境，為了能共同抵御寒冷，需抱成一團(tuán)，體弱的小的在中間，大的、體質(zhì)好的在外圈，并且輪流互換位置。通過(guò)這種方式共同承擔(dān)防御寒風(fēng)的任務(wù)。同樣地，在WSNs中，處于不同位置的傳感節(jié)點(diǎn)承受的任務(wù)不同，相應(yīng)傳感節(jié)點(diǎn)的能量消耗率不一，有些傳感節(jié)點(diǎn)能量消耗率快、有些慢。如靠近Sink節(jié)點(diǎn)承擔(dān)更多的轉(zhuǎn)發(fā)數(shù)據(jù)任務(wù)，相應(yīng)地，其能量消耗率較快。能量消耗快的位置，類(lèi)似企鵝蜷縮一團(tuán)的外圍。受企鵝行為的啟發(fā)，本文提出一種新的傳感節(jié)點(diǎn)控制方案，由多個(gè)傳感節(jié)點(diǎn)輪流駐守能量消耗快的位置，共同分擔(dān)繁重的任務(wù)，保存?zhèn)鞲泄?jié)點(diǎn)能量，最終實(shí)現(xiàn)提高網(wǎng)絡(luò)壽命的目標(biāo)。

如圖1所示，傳感節(jié)點(diǎn)s1、s2和s3能量消耗比其他的傳感節(jié)點(diǎn)能量消耗率更高。節(jié)點(diǎn)s1、s2消耗了大量的能量，因?yàn)樗鼈冇写罅康淖庸?jié)點(diǎn)（descendants），這些子節(jié)點(diǎn)需要節(jié)點(diǎn)s1、s2向Sink節(jié)點(diǎn)轉(zhuǎn)發(fā)數(shù)據(jù)。節(jié)點(diǎn)s3消耗了大量的能量，由于其遠(yuǎn)離父節(jié)點(diǎn)s1，遠(yuǎn)距離傳輸數(shù)據(jù)能量消耗大。針對(duì)這種情況，可利用調(diào)整移動(dòng)位置，即將不同的節(jié)點(diǎn)輪流移動(dòng)到能量消耗高位置上。例如，將s1所在的位置與s8互換、s2所在的位置與s7互換、s3所在的位置與s5互換。這樣的話，能量消耗高的位置由兩節(jié)點(diǎn)而不是一個(gè)節(jié)點(diǎn)承擔(dān)，以提高網(wǎng)絡(luò)壽命。

為此，提出基于能量消耗率的節(jié)點(diǎn)位置對(duì)調(diào)（energy consumption ratio-based node rotation，ECRNR）方案。ECRNR方案規(guī)定何時(shí)移動(dòng)、哪些節(jié)點(diǎn)移動(dòng)以及每個(gè)節(jié)點(diǎn)向何地移動(dòng)，依據(jù)傳感節(jié)點(diǎn)的能量消耗率進(jìn)行節(jié)點(diǎn)位置移動(dòng)。任務(wù)繁重位置由多個(gè)傳感節(jié)點(diǎn)輪流駐守、共同分擔(dān)任務(wù)，從而合理有利用傳感節(jié)點(diǎn)能量，提高網(wǎng)絡(luò)壽命。

1　問(wèn)題描述

假定網(wǎng)絡(luò)內(nèi)有N個(gè)傳感節(jié)點(diǎn)si，i=1，2，…，N。傳感節(jié)點(diǎn)si的位置為pi，i=1，2，…，N。假定每個(gè)傳感節(jié)點(diǎn)初始能量為E。傳感節(jié)點(diǎn)si的電量壽命為t（si），整個(gè)網(wǎng)絡(luò)壽命為T(mén)。網(wǎng)絡(luò)壽命T等于網(wǎng)絡(luò)內(nèi)傳感節(jié)點(diǎn)電量壽命最小的值：

WSNs中位于不同位置的傳感節(jié)點(diǎn)承擔(dān)的任務(wù)不同，如圖1所示，相比其他傳感節(jié)點(diǎn)，s1承擔(dān)s2、s3、s6以及s7、s8向Sink傳輸數(shù)據(jù)的任務(wù)，因此，其能量消耗速度快，即能量消耗率高。而傳感節(jié)點(diǎn)s6、s7、s8的任務(wù)比較輕，相應(yīng)地，能量消耗速度慢，能量消耗率低。假定s1的電量壽命t（s1）=30h，而s8的電量壽命t（s8）=100h。若不采取合理措施，整個(gè)網(wǎng)絡(luò)壽命只有T=30h。

由于傳感節(jié)點(diǎn)的能量是一定的，要延長(zhǎng)電量壽命，只能合理、高效地利用傳感節(jié)點(diǎn)的有限能量。因此，在不影響傳感節(jié)點(diǎn)完成任務(wù)（收集數(shù)據(jù)、檢測(cè)異常情況）的情況下，只能將任務(wù)繁重的位置由多個(gè)傳感節(jié)點(diǎn)來(lái)完成，即由多個(gè)傳感節(jié)點(diǎn)輪流分擔(dān)任務(wù)，從而避免某個(gè)節(jié)點(diǎn)電量提前耗盡，以延長(zhǎng)整個(gè)網(wǎng)絡(luò)壽命。

假定在時(shí)間t，設(shè)定L1（si，sj，t）為節(jié)點(diǎn)si與sj未交換位置的網(wǎng)絡(luò)壽命，如果節(jié)點(diǎn)si與sj交換位置后，網(wǎng)絡(luò)壽命為L(zhǎng)2（si，sj，t）。若L2（si，sj，t）＞L1（si，sj，t），則認(rèn)為可以將節(jié)點(diǎn)si與sj的位置交換，提高網(wǎng)絡(luò)壽命。

圖1　調(diào)整傳感節(jié)點(diǎn)位置示意圖

2　ECRNR方案

ECRNR方案的核心思想：能量消耗率高的位置由多個(gè)節(jié)點(diǎn)輪流駐守。

2.1臨界節(jié)點(diǎn)集

ECRNR方案中，首先計(jì)算臨界節(jié)點(diǎn)（critical nodes）。所謂臨界節(jié)點(diǎn)就是指其能量消息率（energy consumption rate，ECR）高于門(mén)限值lcr的節(jié)點(diǎn)，其位置需要調(diào)整。設(shè)Lcr為臨界節(jié)點(diǎn)集。信宿Sink收集其他節(jié)點(diǎn)的能量以及位置信息，并計(jì)算初始臨界節(jié)點(diǎn)集Lcr：

式中：λi——傳感節(jié)點(diǎn)si的能量消耗率；

lcr——判斷臨界能量消耗率的門(mén)限值。

由式（2）可知，只要傳感節(jié)點(diǎn)si的能量消耗率λi高于門(mén)限值，就納入Lcr集。計(jì)算門(mén)限值lcr采取平均化原則：其等網(wǎng)絡(luò)內(nèi)最小的能量消耗率lmin和最大能量消耗率lmax的均值，即lcr=（lmin+lmax）/2。

2.2對(duì)調(diào)合作節(jié)點(diǎn)的選取

ECRNR方案采取多輪對(duì)調(diào)位置。假定每輪對(duì)調(diào)傳感節(jié)點(diǎn)位置的時(shí)長(zhǎng)為rs。在進(jìn)行對(duì)調(diào)位置前，先選擇符合條件的對(duì)調(diào)合作節(jié)點(diǎn)（swap partner）。所謂對(duì)調(diào)合作節(jié)點(diǎn)就是指被選中與臨界節(jié)點(diǎn)對(duì)調(diào)位置的傳感節(jié)點(diǎn)。如圖1所示，s1為臨界節(jié)點(diǎn)，s8是其swap partner。

在每一輪對(duì)調(diào)位置中，每個(gè)傳感節(jié)點(diǎn)s執(zhí)行以下算法：

若節(jié)點(diǎn)s的ECR大于門(mén)限值lcr，為臨界節(jié)點(diǎn)，即s∈Lcr。首先，計(jì)算子節(jié)點(diǎn)集Ds，并要從Ds集中選擇一個(gè)節(jié)點(diǎn)與其位置進(jìn)行交換。那么子節(jié)點(diǎn)s′∈Ds能夠被選中的條件如下：

1）在每輪中子節(jié)點(diǎn)s′沒(méi)有承諾與其他節(jié)點(diǎn)對(duì)調(diào)位置；

2）子節(jié)點(diǎn)s′離節(jié)點(diǎn)s最多有h跳的距離，h為門(mén)限值，單位為跳（hop）。

滿(mǎn)足上述兩條件的子節(jié)點(diǎn)成為候選節(jié)點(diǎn)（candidate nodes）。將候選節(jié)點(diǎn)納入候選節(jié)點(diǎn)集Cs。候選節(jié)點(diǎn)再將自己的信息，包括位置、能量消耗率ECR，發(fā)送給節(jié)點(diǎn)s。節(jié)點(diǎn)s依據(jù)這些信息，選擇一個(gè)節(jié)點(diǎn)，假定為s*。若s*滿(mǎn)足式（3）或式（4），便可成為節(jié)點(diǎn)s的swap partner。

或者：

式中：e、e*——節(jié)點(diǎn)s、s*的初始能量；

λ、λ*——節(jié)點(diǎn)s、s*的能量消耗率，并且λ＞λ*；

k——將節(jié)點(diǎn)從一個(gè)位置移到另一個(gè)位置所消耗的能量。

若候選節(jié)點(diǎn)中沒(méi)有合適的節(jié)點(diǎn)成為swap partner，那么節(jié)點(diǎn)s在本輪中不進(jìn)行位置調(diào)整，選擇swap partner的算法流程如圖2所示。

2.3位置對(duì)調(diào)

已選擇了swap partner的節(jié)點(diǎn)進(jìn)行位置調(diào)整，經(jīng)過(guò)一輪調(diào)整后，以類(lèi)似的方式，開(kāi)始新一輪。這種分布式選舉swap partner的方式降低了時(shí)鐘同步的要求。每個(gè)節(jié)點(diǎn)只需要知道能量消耗率ECR以及路由樹(shù)中的父節(jié)點(diǎn)以及門(mén)限值lcr。

最初，節(jié)點(diǎn)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)如圖3（a）所示，節(jié)點(diǎn)a，b，c位于樹(shù)的根上，能量消耗率高，納入Lcr集，成為臨界節(jié)點(diǎn)。為了延長(zhǎng)網(wǎng)絡(luò)壽命，基于“順根摸藤”原則，需尋找swap partner與它們進(jìn)行位置對(duì)調(diào)。如尋找節(jié)點(diǎn)a的swap partner時(shí)，首先找到以節(jié)點(diǎn)a為根的樹(shù)，然后沿著該樹(shù)找到其子節(jié)點(diǎn)e，若節(jié)點(diǎn)e?Lcr，將節(jié)點(diǎn)e作為節(jié)點(diǎn)a的swap partner。依據(jù)同樣的方法，分別找到節(jié)點(diǎn)b，c的swap partner，分別為j，k，并交換位置，如圖3（b）所示。隨后，準(zhǔn)備第2輪對(duì)調(diào)位置，將節(jié)點(diǎn)e與節(jié)點(diǎn)i交換、節(jié)點(diǎn)j與節(jié)點(diǎn)q交換、節(jié)點(diǎn)k與節(jié)點(diǎn)m交換，如圖3（c）所示。

圖2　選擇swap partner的算法流程圖

3　數(shù)值仿真

為了評(píng)估ECRNR方案延長(zhǎng)網(wǎng)絡(luò)壽命的性能，利用Matlab軟件建立仿真平臺(tái)，仿真區(qū)域?yàn)?00m× 100m，傳感節(jié)點(diǎn)傳輸范圍為25 m。分別考察傳感節(jié)點(diǎn)數(shù)、初始電量E對(duì)網(wǎng)絡(luò)壽命的影響。

1）首先分析ECRNR方案中每輪對(duì)調(diào)傳感節(jié)點(diǎn)位置的時(shí)長(zhǎng)r及門(mén)限值h參數(shù)的選取。先定義壽命提高率R：

仿真結(jié)果如圖4所示，ECRNR方案的壽命提高率隨r的增長(zhǎng)而增長(zhǎng)，當(dāng)r增長(zhǎng)到60 s時(shí)，趨于飽和狀態(tài)。再增長(zhǎng)r，反而導(dǎo)致壽命提高率的下降。此外，h對(duì)壽命提高率也存在不少的影響，由圖可知，h=2hop時(shí)，壽命提高率達(dá)到最大。這是因?yàn)閔小（h= 1hop），離臨界節(jié)點(diǎn)近，其能量消耗也比較大，而h大（h=3 hop），距離比較遠(yuǎn)，長(zhǎng)距離移動(dòng)節(jié)點(diǎn)本身消耗能量也比較大。因此，在仿真中選取r=60s、h=2hop。

圖3　基于能量消耗率的節(jié)點(diǎn)交換位置示意圖

將ECRNR方案與文獻(xiàn)[12]提出的EASR（energyaware sink relocation）方案以及文獻(xiàn)[13]提出了JMR （joint sink mobility and routing strategy）方案進(jìn)行比較。

2）傳感節(jié)點(diǎn)數(shù)對(duì)網(wǎng)絡(luò)壽命的影響。電量E=1000J，傳感節(jié)點(diǎn)數(shù)在50，75，125，150變化。仿真結(jié)果如圖5所示。

由圖可知，在整個(gè)傳感節(jié)點(diǎn)變化范圍內(nèi)，本文提出的ECRNR方案的性能優(yōu)于JMR和EASR。JMR方案的性能最差。這是因?yàn)镴MR方案僅考慮Sink節(jié)點(diǎn)移動(dòng)，并且移動(dòng)軌跡單一。此外，EASR方案優(yōu)于JMR方案，盡管EASR方案也僅移動(dòng)Sink節(jié)點(diǎn)，但是移動(dòng)軌跡不再是單一的，而是依據(jù)傳感節(jié)點(diǎn)能量變化。

圖4　ECRNR方案的壽命提高率隨r、h的變化情況

圖5　網(wǎng)絡(luò)壽命隨傳感節(jié)點(diǎn)數(shù)的變化情況

圖6　網(wǎng)絡(luò)壽命隨初始電量的變化情況

3）電量E對(duì)網(wǎng)絡(luò)壽命的影響。傳感節(jié)點(diǎn)數(shù)為100，電量E在500，750，1250，1500 J變化。仿真結(jié)果如圖6所示。

由圖可知，網(wǎng)絡(luò)壽命隨傳感節(jié)點(diǎn)的初始電量E的增加而上升。與JMR和EASR方案相比，本文提出的ECRNR方案性能最優(yōu)，并且隨著初始電量的增加，性能優(yōu)勢(shì)越明顯。其原因在于：ECRNR方案全局考慮網(wǎng)絡(luò)內(nèi)的傳感節(jié)點(diǎn)的能量消耗狀態(tài)，有針對(duì)性將能量消耗高的節(jié)點(diǎn)進(jìn)行移動(dòng)，使其不再承擔(dān)繁重的數(shù)據(jù)轉(zhuǎn)發(fā)，保存電池能量。

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

本文針對(duì)WSNs網(wǎng)絡(luò)壽命問(wèn)題，展開(kāi)分析，提出了基于能量消耗率的節(jié)點(diǎn)位置對(duì)調(diào)ECRNR方案。ECRNR方案受企鵝蜷縮和旋轉(zhuǎn)的過(guò)冬行為的啟發(fā)，將工作負(fù)擔(dān)重的位置由多個(gè)傳感節(jié)點(diǎn)輪流承擔(dān)，而不是由某一個(gè)節(jié)點(diǎn)承擔(dān)，從而提高整個(gè)網(wǎng)絡(luò)的傳感節(jié)點(diǎn)電量使用時(shí)間。ECRNR方案首先依據(jù)傳感節(jié)點(diǎn)的能量消耗率，其大于門(mén)限值的節(jié)點(diǎn)納入臨界節(jié)點(diǎn)集Lcr。Lcr內(nèi)的傳感節(jié)點(diǎn)，依據(jù)選擇swap partner的算法選擇自己的swap partner，并與其對(duì)調(diào)位置。仿真結(jié)果表明，提出的ECRNR方案有效地提高網(wǎng)絡(luò)壽命。

參考文獻(xiàn)

[1] SZEWCZYK R，MAINWARING A P. An analysis of a large scale habitat monitoring application[C]∥International Conference on Embedded Networked Sensor Systems. Association for Computing Machinery. Baltimore，2004：214-226.

[2] SUZUKI M，SARUWATARI S，KURATA N. A highdensity earthquake monitoring systemusing wireless sensor networks[C]∥Proceedings of the 5th international conference on Embedded networked sensor systems Association for Computing Machinery Sydney NSW Australia，2007：373-374.

[3] FILIPPONI L，SANTINI S，VITALETTI A.Data collection in wireless sensor networks for noise pollution monitoring[C] ∥Distributed Computing in Sensor Systems. 4th IEEE International Conference.Springer-Verlag.Santorini Island, 2008：492-497.

[4]胡峻峰，曹軍.基于Bete信譽(yù)系統(tǒng)的魯棒安全定位算法[J].計(jì)算機(jī)工程，2014，40（8）：116-122.

[5] ZITTERBART D，WIENECKE B，BUTLER J. Coordinated movements prevent jamming in an emperor penguin huddle[J]. PLoS，2011，6（6）：202-216.

[6] XU H，HUANG L，ZHANG Y，et al. Energy-efficient cooperative data aggregation for wireless sensor networks[J]. J. Parallel Distrib. Comput，2010，70（9）：953-961.

[7] WANGP，DAI RM，AKYILDIZ I F. Collaborative data compression using clustered source coding for wirelessmultimediasensornetworks[C]∥IEEE INFOCOM 2010 -IEEE Conference on Computer Com munications IEEE. San Diego，2010：2106-2114.

[8] LUO H，WANG J，SUN Y，et al. Adaptive sampling and diversity reception in multi -hop wireless audio sensornetworks [C]∥2010 IEEE 30th International Conference on Distributed Computing Systems. Genova：IEEE，2010：378-387.

[9] MOUKADDEM F，TORNG E，XING G. Maximizing data gather ing capacity of wireless sensor networks using mobilerelays [C]∥2010IEEE7thInternational Conference on Mobile Adhoc and Sensor Systems. IEEE Computer Society.San Francisco，2010：312-321.

[10] SHA M，XING G，ZHOU G. C -mac：Modeldriven concurrent medium access control for wireless sensor networks[J]IEEE Technology，2009，3（5）：1845-1853.

[11] LIU Y，LUO Z，XU K. A reliable clustering algorithm base on leach protocol in wireless mobile sensor networks[C]∥2010 2nd International Conference on Mechanical and Electrical Technology. IEEE Piscataway，2010：692-696.

[12] WANG C，SHIH J，PAN B. A Network lifetime enhancement method for sink relocation and its analysis in wireless sensor networks [J]. IEEE Technology，2013，45 （5）：45-52.

[13] DANTU K，RAHIMI M，SHAH H. Robomote: enabling mobility insensor networks[C]∥FourthInternational SymposiumonInformationProcessinginSensor Networks IEEE. Los Angeles：IEEE，2005：404-409.

（編輯：莫婕）

Penguin wintering behavior-based improved network lifetime algorithm performance

CHEN Zhongliang，CHENG Lei
（Huanghuai University，Zhumadian 463000，China）

Abstract:Limited energy supplies have made the extension of network lifetime one of the technical challenges for wireless sensor networks（WSNs）. Therefore，an energy consumption ratio-based node rotation（ECRNR）scheme has been proposed in this paper. The purpose of this scheme is to allocate more sensor nodes at the positions of high energy consumption in turns，that is to say，the relay information is shared by more than one sensor nodes to avoid early energy consumption. Simulation results show that the scheme has prolonged the lifetime of networks a lot compared with traditional schemes.

Keywords:network lifetime；energy consumption；rotation；wireless sensor networks

作者簡(jiǎn)介：陳中良（1980-），男，河南方城縣人，實(shí)驗(yàn)師，碩士，研究方向?yàn)檐浖こ獭⒂?jì)算機(jī)應(yīng)用。

基金項(xiàng)目：河南省科技發(fā)展計(jì)劃項(xiàng)目（132102210463）

收稿日期：2015-05-04；收到修改稿日期：2015-06-23

doi：10.11857/j.issn.1674-5124.2016.02.031

文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1674-5124（2016）02-0136-05