异构无线传感器网络节点部署算法研究

黄诠,刘浩,梁平元

(湖南人文科技学院 信息学院，湖南 娄底，417000)



异构无线传感器网络节点部署算法研究

黄诠,刘浩,梁平元

(湖南人文科技学院 信息学院，湖南 娄底，417000)

无线传感器节点将收集到的数据传输到簇头，簇头将数据包聚合后再发送到基站.离基站较远的簇头在发送数据过程中会因为能源消耗过高而提前死亡从而导致出现能量空洞的问题.为此，本文对异构传感器网络的节点部署进行研究，将网络监控区域划分成圆环，提出一种传感器簇头最大化生命周期模型.该模型以传感器簇头能耗均衡为基础并通过分析每层圆环传感器节点能量消耗情况计算出每层圆环的宽度，提出一种基于圆环的非均匀节点部署算法，得出了节点部署的密度函数.使用MATLAB对节点均匀部署、非均匀部署和随机部署进行了模拟仿真实验，通过对实验结果分析，该算法能在延长传感器网络的生命周期方面有着比较明显的优势.

传感器网络；节点部署；网络生命周期

传感器网络是由许多在空间上分布的自动装置组成的一种可进行数据采集与处理、数据通信的计算机网络，被广泛应用于在军事、环境与生态监测、健康监护等领域.网络中的节点可以根据感测能力、计算能力、通信能力和能量等分为不同的种类.异构传感器网络是指由不同类型的节点组成的网络，一般将二级异构传感器网络中的节点划分为两类，即高级节点与普通节点，这两类节点具有不同的功能和初始能量，高级节点的初始能量远大于普通节点，它们通常作为簇头来使用.

在传感器网络设计中影响其网络生命周期和质量的一个重要因素是节点部署.目前大多节点部署算法在考虑均衡节点能耗时基本采用传感器节点随机均匀部署的方法.该方法有着其自身无法回避的缺陷，若在节点与基站之间采用多跳通信方式进行数据通信时，由于传送的数据较多会导致离基站较近的节点提前死亡，反之若采用单跳通信进行数据通信，离基站较远传感器节点会因为在传送数据时所需的能耗太高导致能量消耗过快而死亡，严重影响网络的生命周期[1]，已有研究表面，在节点部署时若采用非均匀的节点部署方法比均匀部署方法更能有效均衡整个网络中不同位置节点的能耗，更能有效的延长网络的生命周期[2].

文献[3]采用泊松分布的方法将网络节点在单位面积的二维平面上进行部署，设计了一种新的异构传感器网络.该网络以概率p为衡量因子在节点中选择出相应的高级节点并将其作为簇头节点.在计算出所有节点在数据收集周期中所需消耗的能量期望值后以全部能量最小值的前提下确定p的最优解.文献[4]设计的网络模型则以基站到所有簇头进行数据通信总体代价为目标.网络中高级节点与基站直接进行数据通信，普通节点则采用多跳模式与高级节点进行数据通信.为了避免能量会展空洞的形成，延长网络寿命，文献[5]提出一种以最优化工作节点数、中继节点部署方法和节点间传送距离作为约束条件的节点部署算法，以最大网络效率为优化目标进行研究.文献[6]研究了异构无线传感器网络中簇头的优化部署策略，由高能力节点担任簇头来实现节能并改善网络性能，把簇头的优化部署问题形式化为一个整数规划问题，提出一种基于K-平均和模拟退火混合算法的KMSA算法，对簇头节点进行有策略的部署.文献[7]提出密度控制算法(DCA)则以优化异构传感器网络中节点闲时能量开销为目地，DCA能寻找到一个闲时能量开销近似最小化的连通覆盖集合，将该节点最终映谢为活动节点集合来延长网络的生命周期.

本文在文献[4]和文献[7]基础上展开工作，给出了基于能耗均衡的最大化网络生命周期模型，利用文献[8]中的密度控制算法来调度网络中各区间内的休眠节点.但与文献[3,6]研究所不同的是，高级节点采用非均匀部署方法，在监控区域的不同位置，高级节点成为簇头的概率并不相同.

1 系统模型设计与问题描述

1.1 能耗模型设计

对于无线传感器网络而言，其节点的能耗大部分用于数据的通信，节点捕获外部数据与计算数据所消耗的能量只占整个能耗极小的一部分，基本可以忽略不计.本文在设计能耗模型时采用了与文献[9]相同模型，模型事先设定阀值d0，接收节点与发送节点两者之间的距离如果小于阀值d0，则数据传输的能量消耗与数据传输的距离平方成正比，反之与传输距离的四次方成正比，这两种模型被称之为自由空间能量模型和多路能量衰减模型.本文在设计模型时指定普通节点与高级节点之间的数据通信采用自由空间能量模型；基站与高级节点之间的数据通信采用多路衰减能量模型.当节点之间数据通信距离为d时，发送节点发送len比特数据所消耗的能量可以下式计算：

接收节点接收数据所消耗的能量为

Erx(len)=lenEelec

(2)

在(2)式中，Eelec表示收发电路的能量所消耗，Eamp表示放大器的能量消耗.d0取值87m，Eelec取值50nJ/bit，Eamp1取值10pJ/bit/m2，Eamp2取值0.0013pJ/bit/m4.在后面的仿真实验中，我们采用了上述参数.

1.2 网络模型

本文假定普通节点采用均匀部署方法、高级节点采用非均匀部署方法，监控区域为边长为W的正方形，基站部署于区域中心位置，整个传感网络部署完毕后，节点位置不再发生变化.在传感器网络的数据收集过程中，普通节点将探测到数据传输到高级节点，高级节点将数据融合后再传输到基站.

以基站所在的位置O为圆心，以普通节点数据传输的有效长度r为宽度，将整个监视区域划分为多个同心等宽圆环并分别标记为p1,p2,p3…pk，网络模型结构如图1所示.

图1 异构传感器网络模型Fig.1 The model of heterogeneous sensor network

1.3 问题描述

设网络中节点的初始能量值为Einit，节点在一轮数据收集中的平均能耗为Eround，则节点i的生命周期为Ti=Einit/Eround.网络的生命周期为所有节点生命周期的最小值，即

Tnet=min{Ti}

(3)

为实现网络生命周期的最大化，应尽量使所有节点的生命周期相等.最大化网络生命周期问题模型定义为

其中Einit-advanced为高级节点的初始能量，Einit-normal为普通节点的初始能量，Enormal为普通节点在一轮数据收集中的平均能耗，Eadvanced(i) 为第i层圆环中高级节点的平均能耗，kopt为最优划分时的圆环层数.

2 非均匀部署算法

在本节中，通过分析节点的能耗计算圆环的宽度，在此基础上，提出一种非均匀的节点部署算法.

2.1 圆环的宽度

我们通过如图2所示的两个传感器节点源节点S和目标节点D之间的多跳通信模型来计算圆环的宽度.

图2 多跳通信模型Fig.2 The model of multi-hop communications

若节点探测到的数据包长度为len比特，设两个节点间的距离为正方形的边长W，那么数据从点S到点D之间需经过k跳来实现传输.通过分析可知，数据在传输过程中如果每跳的距离相等则在传输过程中总的能耗最小.假设每跳距离为r=W/k，那么数据在传输路径上经过k跳后节点总的发送和接收能耗为

(5)

若要节点在传输路径上总能耗最少，对Emulti求导数并使其结果为0，可求出k的最优解为

(6)

普通节点每跳的间距为

(7)

2.2 非均匀的节点部署算法

设每个数据包的长度为len比特，普通节点均匀分布在监控区域中，并按簇半径r组织成簇.

在一次数据收集中，将数据传输到高级节点的平均能耗为

Enormal=len(Eelec+Eamp1r2)

(8)

普通节点的生命周期为

Tnormal=Einit-normal/Enormal

(9)

下面计算处于第i层圆环中的高级节点的能耗.第i个圆环中普通节点的个数为Nnormal(i)=π((ir)2-((i-1)r)2)N/W2

(10)

圆环中处于活动的高级节点的个数为

NC(i)=((ir)2-((i-1)r)2)/r2

(11)

圆环中高级节点的总能耗为

Eadvanced(i)=lenNnormal(i)Eelec+

lenNC(Eelec+Eamp2(ir)4)

(12)

设部署在第i层圆环中的高级节点数为N(i),则高级节点的生命周期为Tadvanced(i)=N(i)×Einit_advanced/Eadvanced(i)(13)

为实现网络生命周期的最大化，所有节点的生命周期应该相等，令

Tnormal=Tadvanced(i)

(14)

由式(14)得出部署在第i层圆环中的高级节点个数为

(15)

部署在监控区域的高级节点总数为

(16)

为了调度网络中冗余节点的个数，以便于控制“活跃”高级数目，本文采用与文献[8]所类似的密度控制算法来完成网络节点的调度.当整个网络规划部署完毕后，处于第i层高级节点成为簇头的概率可由基站根据Pi=Nc/Ni计算得出.本文在进行仿真实验时，将选择高级节点成为候选簇头的概率设置为2Pi，便于在候选簇头中选择更加适合当任簇头的高级点节.

3 仿真实验

实验中，我们假定数据包的长度len为2048比特，高级节点的初始能量为2J，普通节点的初始能量为0.5J.分别将10、40、90、160、250、360、490、640、810、1000个普通节点部署在边长为25、45、65、85、105、125、145、165、185、205m的正方形监视区域内，以确保处于网络中的普通节点密度一致.高级节点分别采用均匀部署(Uniform)、随机部署(Random)和非均匀部署(Non-uniform)进行对比实验.下面的每个实验结果都是100次实验的平均值.

在实验中为了更好的对比三种部署方案的网络生命周期，将网络中超过5%的节点因能量耗尽而死亡时网络已工作的轮数定义为网络的生命周期.其生命周期对比情况如图3所示.

图3 三种部署方案网络生命周期对比Fig.3 Comparison of network life cycles of three deployment scenarios

对图3分析可以得知，在三种节点部署方案中，采用非均匀的节点部署算法其网络的生命周期大于其它两种部署算法.当网络规模变大时，若采用均匀部署和随机部署算法来部署网络，可以发现网络中各圆环内的高级节点分布密度并没有随着网络规模的变大而有较明显的变化，但离基站较远的外层圆环中的高级节点会因为通信距离的增加而导致其能耗增大，使得部分节点提早死亡,从而使整个网络的生命周期下降比较明显.虽然整个网络规模进行了扩大，但由于节点采用了非均匀部署算法进行部署，因此各圆环内的高级节点密度也随之增大，相对而言，高级节点与基站之间的通信决对距离并没有发生很大变化，各圆环节的节点能耗基本相等，整个网络中节点的生命周期呈略微下降的趋势.

为了分析当三种不同方案来部署网络节点其整个网络生命周期结束时系统剩余能量情况，本文将网络剩余能量与网络初始时能量做了一个比较，其结果如图4所示.

图4 三种部署方案网络剩余能量对比Fig.4 Comparison of network residual energy of three deployment scenarios

对图4分析可知，当采用均匀部署和随机部署两种方案来部署节点时，外层节点由于能耗过高而提前死亡，虽然系统剩余的能量较多但整个网络的生命周期被严重缩短.而采用非均匀部署方案时由于不同环内的节点能耗比较平均，高级节点的生存周期得到了保障，因此整个系统的生命周期相对其它两种方案得到了较大的延长.

4 结语

延长网络的生命周期是传感器网络设计的主要目标.本文通过研究异构传感器网络中节点的能量消耗，提出一种非均匀的节点部署算法，得出了一个部署节点的密度函数，在远离基站的区域部署较多的节点，使得不同区域内的节点尽可能同时消耗完自身的能量.应该指出，实际的传感器网络是非常复杂的，本文的研究背景是一个特定的正方形监控区域.如何建立更具普适性的节点部署算法，是作者要进一步研究的课题.

[1]LIUY,LUN R N H,and NI L M.Power-aware node deployment in wireless sensor networks[C]//Aal,konstantin.Proceedings of International Conference on Sensor Networks,Ubiquitous,and Trustworthy Computing,Taiwan:IEEE Computer Society,2006,128-135.

[2]陆克中,黄刘生,万颖渝.无线传感器网络中传感器节点的布置[J].小型微型计算机系统,2006,27(11):2003-2006.

[3]BANDYOPADHYAYS,COYLEE.An energye fficient hierarchical clustering algorithm for wireless sensor networks[C]//Fred Bauer.Proceedings of the 22nd Annual Joint Conference of the IEEE Computer and communications Societies.San Franscisco California:IEEE Computer Society,2003:1713-1723.

[4]MHATREVP,ROSENBERGC,KOFMAND,et al.A minimum cost heterogeneous sensor network with a lifetime constraint[J].IEEE Transaction on Mobile Computing,2005,4(1):4-15.

[5]颜文胜.无线传感器网络节点部署算法的优化研究[J].计算机仿真,2011,28(4):126-129.

[6]刘琳,于海斌.异构无线传感器网络中簇首的优化部署策略[J].通信学报,2010,31(10):229-237.

[7]刘林峰,邹志强,张登银.异构传感器网络中基于闲时能量开销优化的密度控制算法研究[J].通信学报,2010,31(4):72-79.

[8]YE F,ZHONG G,LU S.PEAS:A robust energy conserving protocol for long-lived sensor networks[C]//Aakula,Rajesh.Proceeding of 23rd International Conference on Distributed Computing Systems.Providence:IEEE Computer Society,2003:1025-1028.

[9]HEINZELMAN WR.An application-specific protocol architecture for wirelessmicrosensor networks[J].IEEE Trans.on Wireless Communications,2002,1(4):660-670.

Study on node deployment algorithm of heterogeneous wireless sensor networks

HUANG Quan1，LIU Hao1，LIANG Pingyuan1

(Department of Information Science and Engineering,Hunan University of Humanities,Science and Technology,Loudi 417000,China)

Sensor nodes transmit their collect data to designated cluster heads,cluster heads aggregate the data packets and send them to the base station.Cluster heads further from the base station will die much more quickly than those closer to the base station and leads to the energy hole problem.To address the problem,based on the research on node deployment of heterogeneous sensor networks,the network monitoring area is divided into a number of rings,and a maximizing lifetime model of square heterogeneous sensor networks is presented.In this model,based on the energy balance of sensor cluster head,we compute cirque width and propose a non-uniform node deployment algorithm based on cirque upon analysis of sensor nodes energy consumption.Then a density function based on node deployment is presented.We designed simulation experiment for network lifetime of uniform deployment,non-uniform deployment and random deployment using MATLAB.Simulation results show that non-uniform deployment algorithm is effective for prolonging the network lifetime.

sensor network;node deployment;network lifetime

1672-7010(2016)02-0046-06

2016-04-08

湖南省教育厅科研优秀青年项目(15B125)；湖南省教育厅科研项目(12C0743)；2016年娄底市科技计划项目；湖南人文科技学院“信号与信息处理”重点学科资助

黄诠 (1977-),男,湖南娄底人,硕士,实验师，从事数据挖掘、无线传感器网络研究；E-mail:hnldhq@126.com

TP393

A