WSN中基于树的负载均衡的数据收集算法*

刘正波,朱 亮

(1.石家庄邮电职业技术学院电信工程系移动通信教研室,石家庄 050000;2.河北大学数学与计算机学院,河北 保定 071002)

WSN中基于树的负载均衡的数据收集算法*

刘正波1*,朱 亮2

(1.石家庄邮电职业技术学院电信工程系移动通信教研室,石家庄 050000;2.河北大学数学与计算机学院,河北 保定 071002)

部署无线传感网络WSNs(Wireless Sensor Networks)的根本目的在于数据收集。然而,节点能量有限特性给具有低能耗的数据收集算法的设计提出了挑战。为此,提出基于树的负载均衡的数据收集TLBDG(Tree-based Load Balanced Data Gathering)算法。TLBDG算法构建了一棵以基站为根的负载均衡的数据收集树,并以最小跳数路径转发数据包。TLBDG算法具体思想为:先依据节点离基站的跳数形成层次结构,然后再生成以基站为根的树型数据传输路道。实验结果表明,提出的TLBDG算法能够均衡负载,并延长生命周期。

网络;数据收集;树;负载均衡;跳数

近期,无线传感网络WSNs(Wireless Sensor Networks)已成为国内外关注的热点。通过融合传感器技术、通信技术和分布式信息处理技术,WSNs能实时感测数据环境数据,达到监测环境的目的[1]。

WSNs由海量的微型、低功耗的传感节点组成,这些节点具有感测、传输数据能力。当传感节点感测数据后,就将数据向基站(Sink)传输,即Sink收集数据。

因此,数据收集是无线传感网络的重点工作。每个传感节点周期感测数据,然后以多跳方式传输至基站,这一过程称为数据收集(data gathering)。现有的数据收集算法有基于簇、基于链路和基于树3种收集算法。

基于簇的数据收集算法是指将网络内节点依据某些指标,如距离、能量,划分为多个群(簇)。每个簇内产生一个簇头,由它负责将簇内信息传输至基站,典型的算法有:LEACH[2]、HEED[3]和CEDA[4]等。而基于链的数据收集算法是将网络内所有节点构成一条链,并在链上产生一个节点与基站通信,典型的算法有:CCS[5]、DRAEM[6]。

而基于树的数据收集算法是将所有节点构成一棵生成树,并由基站作为根节点。节点将数据传输至父节点。每个节点均依据这一原则转发数据,最终基站将接收到网络内所有数据。与基于簇和基于链的拓扑结构相比,基于树的拓扑结构具有最小图的连通图,并具有高的连通性和可靠性,已被广泛应用。

典型的基于树的数据收集算法,有PEDAP[7]、MLDGA[8]、MNL[9]和MAXLAT[10]。PEDAP算法先生成只含有基站的树,然后以节点权值为标准,据此选择节点加入树,进而构成一棵树。而PEDAP-AP算法在构成树是考虑了节点本身的剩余能量。尽管如此,但PEDAP和PEDAP-AP两个算法所生成的树中,各子树节点数不均匀,使它们的能耗不平衡。

而文献[8]提出了基于PEDAP的改进算法MLDGA。MLDGA算法改进了PEDAP的权值,该权值融入了树的生命周期。但是,MLDGA算法生成树仍不均衡,而且需要频繁更换树结构,增加网络开销。

文献[11]提出MNL算法,MNL算法是以节点剩余能量为指标,构造生成树,它的思路与MLDGA类似。而MAXLAT算法是最大化生命周期为目标构造树,同时避开了能量瓶颈节点。但是该算法需要将网络内所有信息集中到基站,这增加了通信开销。

为此,本文提出基于树的负载均衡的数据收集算法TLBDG(Tree-based Load Balanced Data Gathering)。TLBDG通过选择最小跳数,构建负载均衡的生成树。实验数据表明,提出的TLBDG算法能够有效地通过平衡负载,降低能耗,延长网络的生命周期。

1 网络模型及问题描述

现有的数据收集算法是针对单跳网络。单跳网络中的节点都能以直接通信方式与其他节点传输消息,这有利于平衡网络能耗。然而,在实际的大型网络中,由于节点能量受限,节点不可能与网络内所有的其他节点能够直接通信,通常需要多跳通信才能将数据传输至基站,这就是多跳网络。为此,本文以多跳无线传感网络为研究对象。

1.1 网络模型

假定n个节点和一个基站节点随机分布于M×M区域。整个网络形成了一个无向的连通图G(V,E),其中V={1,2,…,i,…,n,S0}为节点集合,而S0表示基站。而E表示边集。若两个节点互处于通信半径内,则它们存在边。此外,网络还具有如下性质:①考虑静态的连通网络,网络一旦部署后,节点就不再移动;②考虑同构网络,即所有节点的初始能量相同,且能量耗尽后,不能补充,即失效;③基站不受能量限制。

定义1轮(round) 指基站从所有节点收集一次数据的过程。可能每一轮持续时间不同,但每个节点在每一轮只产生固定比特的感应数据。

定义2生命周期(LifeTime) 对于单个节点而言,节点的生命周期就是节点能存活的轮数,而网络的生命周期等于网络内节点的最小生命周期。

此外,引用文献[11]的能量消耗模型。传输距离d、k比特数据包所消耗的能量Etr(k,d),如式(1)所示:

(1)

式中:Eelec、εfs和εmp为能量消耗参数,它们典型取值分别为50 nJ/bit、10 pJ/(bitm2)和0.001 3 pJ(bit/m4)。而d0=75 m。

而接收单位距离的k比特数据包的所消耗的能量Erx(k)为:

Erx(k)=k×Eelec

(2)

1.2 问题描述

由于传感节点能量受限,并且无线传感网络常部署于危险或偏远的环境,更换失效或能量殆尽的传感节点是不可能。一旦失效,这些节点就无法感测数据和传输数据,必然形成覆盖空洞。为此,研究人员试图通过改进数据收集算法,提高节点能效,进而延长传感节点的工作时间。

现有的数据收集算法难以保证数据传输的高效,并且通常以增加投入传感节点数的方式改善数据传输的连通性,但节点数的增加必然会加大网络流量,增加了能耗。如线性路由拓扑结构[12],如图1所示。图1中每个节点数据包都进行2次收发,形成了18次收/发过程,造成能量浪费。

图1 线性路由拓扑结构

为此,本文不采用线性路由拓扑结构,而是基于树型拓扑结构,进而提高数据收集的效率。

2 TLBDG算法

TLBDG算法是通过节点跳数以及负载构建数据收集树。

2.1 最优候选转发集

对于任意节点i,它离基站节点的跳数表示为hi。它首先通过网络的初始知识,建立一跳邻居集N1-hop(i),其定义如式(3)所示:

N1-hop(i)={j|dij≤R}

(3)

式中:dij表示传感节点i与j的欧式距离,而R表示传感节点的通信半径。

然后,基于一跳邻居集N1-hop(i),把它拆分为两个子集S(hi-1)和S(hi+1),且N1-hop(i)=S(hi-1)∪S(hi+1)。S(hi-1)内的节点离基站的跳数为hi-1,而S(hi+1)内的节点离基站的跳数为hi+1。

节点i就是从S(hi-1)内选择一个节点作为数据转发节点,将其称为路由节点。为此,节点建立最优候选转发集Option_list(i),其S(hi-1)构成,并包含S(hi-1)内每个节点ID号和它们子节点数,即:

Option_list(i)←{node_id,number of children}
i∈S(hi-1)

(4)

2.2 路由节点的选择

当节点i启动路由节点选择过程开始前,先判断比它跳数更高的节点是不是已经完成了路由节点next-node(i)选择阶段。若完成了,则节点i启动路由节点的选择过程。为此,引入集count(i),其表示S(hi+1)内需要选择路由节点的节点数。这一过程的形式表述如下:

if count(i)==φ then
tigger next-node-selection algorithm

(5)

当count(i)为空时,就启动路由节点选择阶段。如果hi大于1,则表示自己不是基站节点的一跳邻居,就广播请求消息REQ,否则,就广播消息Selected,表示路由节点就是基站,这一过程的形式化表述如下:

if count(i)==φ then
ifhi>1 then
broadcasts REQ message
else
broadcasts Selected message with next-node(i)=Sink

(6)

图2 传输REQ和Replay消息的示意图

当节点i收到来自上一跳节点发送的REQ消息时,就回复Replay消息。Replay消息包含节点i需要转发的数据包数,且表示为Q(i),和count(i)信息,如图2所示。

传输REQ和Replay消息的形式化表述如式(7)所示:

if receives REQ(j)message fromj∈S(hi+1) then

sends Replay(Qi,count(i))message toj

(7)

当节点i从下一跳节点收到Replay消息后,从中构建Option_list(i),并从中选择子节点最小的节点作为路由节点next-node(i),如图3所示。

图3 节点i接收Replay消息的示意图

节点i收到多条Replay消息后,就构建Option_list(i),并选择具有最小转发消息数的节点作为路由节点,最后广播Selected消息,通告已选择的路由节点。这个过程形式化表述如式(6)所示:

if receives Reply message fromj∈S(hi-1)then
Option_list(i)←Option_list(i)∪{j,Qj};
selects next-node(i)=kwith minimum(Qk);
Broadcasts Selected message with next-node(i)

(8)

2.3Q集的更新

每当节点i收到Selected消息,就意味着S(hi+1)内有一个节点已成功找到路由节点。此时,应将count(i)减1。同时,就将Q(i)+1,更新过程如式(9)所示:

if receives Selected message fromj∈S(hi+1)then

ifhj=hi+1 then

S(hi+1)←S(hi+1)j

count(i)=count(i)-1

ifi=next-node(i)then

Qi←Qi+1

(9)

3 性能分析

3.1 仿真参数

利用VISUAL C++模拟TLBDG算法,并分析它的性能。在100 m×100 m区域内随机分布了100个节点和一个基站节点。所有节点最大传输范围为80 m,初始能量为10 J。每次实验独立重复50次,取平均值作为最终的实验数据。

3.2 实验数据

3.2.1 基站位置和通信半径对网络生命周期的影响

本次实验着重考查基站位置对生命周期的影响,因此,实验中考虑了两种情况:基站位于边界中点和基站位于区域中心。

图4比较将基站位于仿真区域中心和边界中点两种情况下,通信半径对网络生命周期的影响。从图4可知,在通信半径较小阶段,基站位于区域中心情况所消耗的能量小,所以生命周期大。但随着通信半径的增加,基站位于区域中心时所消耗的能量过多,其生命周期下降。此外,从图4可知,这两种情况下,当通信半径约为25 m时,它们的生命周期达到最大。

图4 网络生命周期随通信半径变化关系

图 5 同类算法的生命周期对比

3.2.2 生命周期

为了更好地分析TLBDG算法性能,选择同类算法PEDAP-PA 、MLDGA、MNL和MAXLAT进行比较。同时考虑两种场景:100节点和200节点。即分析网络密度对网络生命周期的影响,且基站位于区域中心,实验数据分别如图5(a)、图5(b)所示。

从图5可知,在两种场景下,TLBDG算法的网络生命周期最高,均高于PEDAP-PA 、MLDGA、MNL和MAXLAT。与场景一(100节点)相比,场景二情况下,TLBDG算法的生命周期下降了约24.5%。而PEDAP-PA 、MLDGA、MNL也下降了约50%。但是MAXLAT并没有下降。这主要是因为:MAXLAT生成的树节点分布均匀。而PEDAP-PA 、MLDGA、MNL所生成的树节点分布不均匀。从这些数据可知,节点密度对网络生命周期存在不小的影响。

而TLBDG算法通过以最小负载原则,生成树,并完成数据传输,能够有效地节省能量,降低能耗,从而提高了网络生命周期。

3.2.3 能量消耗

本次实验分析TLBDG算法和PEDAP-PA 、MLDGA、MNL和MAXLAT的能耗问题。节点数为200个。实验数据如表1所示。

表1 网络能量消耗至50%的运行轮数

从表1可知,在网络整体能量下降至50%,TLBDG算法已经运行了1082轮,而PEDAP-PA、MNL只运行了477轮、478轮。

4 总结

高效能量的数据收集是制约无线传感网络发展的关键因素之一。为此,本文研究了WSNs中基于树的收集问题,并提出基于树的负载均衡的数据收集算法TLBDG。TLBDG算法通过节点离基站的最小跳数构建树,形成以根节点为树型数据传输网络。实验数据表明,TLBDG算法通过平衡负载,提高了网络的生命周期。

[1] 黄媛. 无线传感器网络中一种基于可靠性的数据收集算法[J]. 计算机工程,2015,41(2):85-92.

[2] 李硕,樊建席,王成. 一种新型无线传感器网络数据收集生成树[J]. 小型微型计算机系统,2012,33(6):1238-1242.

[3] Younis O,Fahmy S. HEED:A Hybrid Energy Efficient Distributed Clustering Approach for Ad Hoc Sensor Networks[J]. IEEE Trans on Mobile Computing,2014,3(4):366-379.

[4] Taherkordi A,Mohammadi R,Eliassen F. A Communication Efficient Distributed Clustering Algorithm for Sensor Networks[C]//Proc of the 22nd IEEE Conference on Advanced Information Networking and Applications,Atlanta,USA 2013:634-638.

[5] Jung S M,Han Y J,Chung T M. The Concentric Clustering Scheme for Efficient Energy Consumption in the PEGASIS[C]//Proc of the 12th IEEE Conference on Advanced Communication Technology,Shanghai,China,2013:260-265.

[6] Lindsey S,Raghavendra C,Sivalingam K M. Data Gathering Algorithms in Sensor Networks Using Energy Metrics[J]. IEEE Trans on Parallel and Distributed Systems,2012,13(9):924-935.

[7] Tan H O,Korgeoglu I. Power Efficient Data Gathering and Aggregation in Wireless Sensor Networks[J]. SIGMOD Record,2013,32(4):66-71.

[8] Zhang Q,Xie Z P,Ling B. A Maximum Lifetime Data Gathering Algorithm for Wireless Sensor Networks[J]. Journal of Software,2015,16(11):1946-1957.

[9] Liang W F,Liu Y Z. Online Data Gathering for Maximizing Network Lifetime in Sensor Networks[J]. IEEE Trans on Mobile Computing,2013,6(1):2-11.

[10] Liang J B,Wang J X,Li T S. Maximum Lifetime Algorithm for Precise Data Gathering Based on Tree in Wireless Sensor Networks[J]. Journal of Software,2013,21(9):2289-2303.

[11] Heinzelman W B,Chandrakasan A P,Balakrishnan H. An Application-Specific Protocol Architecture for Wireless Microsensor Networks[J]. IEEE Trans on Wireless Communications,2012,1(4):660-670.

[12] 刘卉,李泽军. 基于投影矢量的双组播树高效路由数据收集[J]. 传感技术学报,2013,26(4):570-577.

刘正波(1971-),男,讲师,主要研究领域移动通信,lzhengb@163.com。

Tree-BasedLoadBalancedDataGatheringAlgorithminWirelessSensorNetworks*

LIUZhengbo1*,ZHULiang2

(1.Department of Mobile Communications,Telecommunications Engineering,Shijiazhuang Posts and Telecommunications Technical College, Shijiazhuang 050000,China;2.School of Mathematics and Computer Science,Hebei University,Baoding Hebei 071002)

Data gathering is a fundamental task in Wireless Sensor Networks(WSNs). The sensor nodes are highly resource constrained,and how to design a low energy consumption data gathering is a great challenge. Therefore,Tree-based Load Balanced Data Gathering(TLBDG)algorithm was proposed in this paper. TLBDG algorithm has construct a load-balanced data gathering tree rooted at the Sink node to forward packets via minimum hops. In TLBDG,firstly the hierarchical structure was established based on the minimum hops from each sensor node to the base station,secondly,a tree transmission path whose root was the base station is got. Simulation result shows that the proposed TLBDG can achieve load balanced,and long lifetime.

wireless sensor networks,data gathering,tree,load balanced;Hop

项目来源:河北省自然科学基金项目(F2011201146);保定市科学技术研究与发展指导计划项目(13ZR058)

2017-03-13修改日期:2017-05-23

TP393

:A

:1004-1699(2017)09-1417-05

10.3969/j.issn.1004-1699.2017.09.020