基于分布式聚类的无线传感器网络数据传输方法研究

丁忠祥 杨彦红

(北京印刷学院信息工程学院,北京 102600)

无线传感器网络(Wireless Sensor Network,WSN)是由大量静止或移动的传感器以自组织和多跳的方式构成的无线网络,以协作地感知、采集、处理和传输网络覆盖地理区域内被感知对象的信息,并最终把这些信息发送给网络的所有者[1]。无线传感器节点通常部署在一些危险的或者人们不能轻易抵达的地方,执行环境监测任务,例如化工厂的管道状态监测,森林中的环境监控等,都有着广泛的应用前景[2]。

由于无线传感器节点存储能力、计算能力和传输能力受限,且通常是用微型电池提供能量,面对电池能量有限且运行在恶劣甚至危险的自然环境中能量难以补充的问题,怎样提高网络中节点能量的有效利用率,延长无线传感器网络的生命周期,是非常重要的问题。另外网络中的节点受各种因素的影响,集中式算法往往需要较长的时间去获取网络状态,而分布式的算法具有更好的适应性和可扩展性,因此研究一种分布式的聚类方法,使得节点聚类成簇,减少网络的无线通信次数,兼顾数据传输低延迟的要求,使得网络中传感器节点能耗均衡,达到延长整个网络的生命周期的目的。

LEACH协议是无线传感器网络中经典的聚类协议,在节点内部生成一个随机数与当前的阈值进行比较,实现网络中簇头节点的选择[3]。若随机数小于阈值,则节点成为簇头节点;非簇头节点选择最近的一个簇头节点作为自身簇头;阈值随网络的聚类次数不断变化。在LEACH协议的基础上,Manjeshwar等人提出了TEEN协议[4]。当节点将采集的数据大于设置的Hard Threshold和Soft Threshold时,数据才会被发送出去,大大减少了网络中需要传输的数据。Lindsey等人提出了PEGASIS协议,根据部署节点间的距离,产生一条数据传输链,随机选择链中的一个节点作为簇头节点[5]。Quan Wang等人提出了EECSR压缩感知算法,通过备份簇头降低转换簇头的开销,从而降低网络电量消耗[6]。Xiang等人提出了一种利用压缩传感数据的方法实现任意无线传感器能量效率和恢复保真度的数据聚集方案[7]。

1 数据传输理论模型

无线传感器网络部署按照随机概率散布在一个范围确定的区域内,除基站外,所有节点都是对等的,通过自组织(Ad-hoc)的方式形成一个网络的拓扑结构。节点的发送功率决定了节点传输的范围,在本文中假定所有节点都可以通过增大电量的方式和基站进行直接通信,但是为了降低功耗采用了聚类传输模型来提高网络的性能,以下将从传输模型、电量消耗模型和性能评价指标进行表述。

1.1 无线传感器网络聚类传输模型

假定网络中的所有传感器节点都直接向基站发送数据,当网络中节点数量较大时,将会产生信道争用的情况,大量的信息传输会发生碰撞从而使网络无法正常地工作。因此采用聚类的方式,将节点划分为不同的区域,如图1所示,每个节点是一个小圆点,将网络范围划分成若干区域,在图中用虚线划分不同的区域,使得每个区域的节点数尽可能相同。每个区域内选取一个簇头节点,在图1中以黑色的小圆点表示。簇头节点负责收集自己区域内节点产生的数据,在节点内部将采集的数据进行数据的聚合,然后通过簇头节点直接发送给基站(图中左下角黑色小方块)。簇内节点进行通信时,可以降低发送功率,减少簇与簇之间的干扰,同时还可以增加节点工作寿命。

图1 聚类传输模型示意图

1.2 电量消耗模型

传感器节点在感测、接收和传输数据时消耗能量。不同的运行方式对传感器节点的能耗影响较大。一般来说,传感器节点有四种模式,即空闲、发送、接收和休眠模式。然而,大部分能量消耗在传输和接收数据上。Shih等人在2002年的Mobicom会议上指出,传感器的大部分能量消耗在通信模块中,而在睡眠模式下的能量消耗通常可以忽略不计[8]。因此,在降低通信成本的前提下,可以大大提高能源利用率。

本文采用一阶无线传输模型[3,6]来描述节点传输的能耗,即向距离为d的节点传输一个k-bit大小的数据包需要消耗的能量为:

接收这个数据需要消耗的能量为:

其中,Eelec是节点无线通讯消耗的能量,εamp是信号放大器消耗的能量。

由于在测试的过程中,各个算法依据初始条件的设置,所发送的数据包的大小的差异并不大,因此在本论文的仿真过程中假定k为固定值。当簇头节点向基站发送数据时,距离是能量消耗的主要影响的变量。

1.3 性能评价指标

在传感器网络中,网络的性能包括低延迟,抗干扰、低功耗等,存在不同的计算公式和评价指标。在本文中将采用以下性能评价指标并给出计算依据。

(1)存活节点数量

存活节点数量(Number of Available Nodes)是统计网络中可以运行的节点的数量。在网络运行的时刻t,节点v的电池电量vele大于正常工作的电池电量最小阈值Emin,则认为该节点v是存活的。

(2)网络生命周期

网络生命周期(Network Lifetime)是表示网络从开始运行到结束的周期。网络开始运行开始记为时刻t1。当节点中所有的节点不是存活状态或以一定比例存活节点数量的时刻为t2。网络生命周期则是t1和t2的差值。

(3)平均最大数据延迟

平均最大数据延迟(AverageMaximumData Delay)是表示网络中所有节点数据达到基站的平均最大延迟。一个节点v周期性产生数据包p1,p2,…,pn。产生这些数据包的时间分别为Gp1,Gp2, … ,Gpn。这些数据包达到基站的时间分别为Rp1, Rp2, … ,Rpn,则节点的最大数据延迟vdelay是时间差值的最大值。

对于全网来说就是所有节点的最大数据延迟的平均值为:

2 基于分布式聚类的数据传输方法

本文提出了一种基于分布式聚类的数据传输方法,无线传感器网络周期性的进行工作,每个周期分为节点聚类阶段和稳定传输阶段。在节点聚类阶段,传感器节点采用剩余电量聚类算法(Residual Electricity Clustering Algorithm, RECA)选取合适的簇头节点,使得网络中的节点被划分成各个分簇中;在稳定传输阶段,簇内节点将采集到的数据发送给簇头节点,簇头节点再将接收到的数据传输到基站中。

2.1 节点聚类过程

节点进入聚类阶段时,产生一个广播随机数定时器,触发时间事件后,节点广播自己的节点信息,其中节点信息不限于自己的剩余电量。其他时隙节点处于接收状态,接收其它节点的广播信息,以获取周围节点的最新状态。再等待广播消息一段时间后,节点将按照下一节中描述的RECA过程,先对周围邻居节点的状态进行分析,从中选择一个合适的节点作为自身的簇头节点。当一个节点成为簇头节点或者簇内节点数量发生变化时,节点需要重新广播自己簇内节点信息。

节点聚类周期结束后,网络中所有的节点被划分在各个分簇当中。每个分簇中的非簇头节点在感知周围的环境信息后,将信息发送给簇头节点;簇头节点将自身的感知信息与接收到的其他节点的感知信息进行聚合,并发送给基站。

2.2 剩余电量聚类算法

剩余电量聚类算法是一种节点根据周围邻居节点的状态信息(包括是否为簇头节点、剩余电量、簇内节点数量等信息),从中选取出一个簇头节点,完成聚类的方法。节点开始聚类时,周围邻居节点有以下两种状态:

(1)邻居节点中没有簇头节点

如图2中a所示,节点A的邻居节点中没有簇头节点,则建立新的簇,并比较节点A与周围邻居节点的剩余电量。假设节点A的剩余电量最多,则节点A改变自身状态,成为新分簇的簇头节点,广播自己新的状态信息,如图2中b所示。假设邻居节点B的剩余电量最多,则节点A向节点B发送入簇请求包;节点B在收到请求包后,改变自身状态,成为新分簇的簇头节点,广播自己新的状态信息,将节点A加入自己的簇内,并回复应答包;节点A收到应答包后,确认加入分簇成功后,将节点B设为自己的簇头节点,如图2中c所示。

图2 簇头形成的过程类别情况

(2)邻居节点中有簇头节点

如图3中a所示,节点A的邻居节点中有簇头节点,分别为簇头节点B、C、D、E。节点A依次向周围分簇的簇头节点发送入簇请求包,直到成功加入一个分簇。簇头节点在收到入簇请求包后,若簇内节点个数未达到最大值,则入簇成功,簇头节点将节点A加入簇内;若簇内节点个数达到最大值,则入簇失败。簇头节点向节点A发送应答包,告知其入簇结果。假设节点A向簇头节点D发出入簇请求后加入分簇成功,则节点A将簇头节点D设为自己的簇头节点,如图3中b所示。

图3 节点加入周围簇过程

RECA伪代码如算法1所示。算法的输入为node、neighbor、maxMembers,分别代表的是进行聚类的节点编号、周围邻居节点的集合和簇内最大成员数。算法的输出为true,即聚类完成。首先,将节点node设为当前剩余电量最多的节点(行2、3)。随后开始对所有邻居节点进行遍历(行4),若i所代表的邻居节点是簇头节点且簇内的节点数量小于簇内最大成员数(行5、6),则节点node将其i所代表的节点设为簇头节点(行8),i所代表的节点的簇内节点个数加一(行9),节点node聚类完成(行9);若i所代表的邻居节点不是簇头节点(行11),则将其剩余电量与当前最大剩余电量对比,如果i所代表的邻居节点的剩余电量大于当前剩余电量最多的节点(行12),则i所代表的邻居节点被视为当前剩余电量最多的节点(行13、14)。若遍历完所有邻居节点后,未能完成聚类,则将当前剩余电量最多的节点设为的簇头节点,其簇内节点数加一(行18、19),节点node将其设置自身的簇头节点(行20),聚类完成(行21)。

算法1 分布式节点聚类方法输入:node节点号,neighbor邻居节点集合,maxMembers簇内最大成员数输出:聚类结果1: function selectClusterHead(node,neighbor,maxMembers)2: maxEnergy ← node.energy 3: maxEnergyNode ← node 4: for each i ∈neighbor do 5: if i.isClusterHead then 6: if i.membersNum < maxMembers then 7: node.clusterHead ← i 8: i.membersNum++9: return true 10: end if 11: else 12: if i.energy > maxEnergy then 13: maxEnergy ← i.energy 14: maxEnergyNode ← i 15: end if 16: end if 17: end for 18: maxEnergyNode.isClusterHead ← true 19: maxEnergyNode. membersNum++20: node.clusterHead ← maxEnergyNode 21: return true 22: end function

3 算法测试验证

3.1 测试环境描述

为了将RECA和其他算法进行比较,使用java实现了RECA、LEACH、TEEN和PEGASIS。表1给出了在仿真测试时,网络的相关参数。网络范围是指节点散布的平面空间范围,这里全部的算法都是100*100。网络节点个数是网络中初始化的节点个数,这里假设节点个数是100。从这两个条件可以看出,网络基本上是属于一种稀疏状态,因此在广播邻居信息、节点信息和簇信息时,发生碰撞的概率并不大,可以依靠重传机制予以避免。数据生成周期是节点每隔一定时间就获取一次传感的数据,这里假定所有算法的模拟测试中都是每隔30个时隙产生一个数据。节点聚类周期设置的都是1000个时隙,也就是1000个时隙之后要重新选取簇头。簇内最大节点数限制了一个簇内所拥有的簇内成员,RECA中规定不超过5个。LEACH和TEEN都需要设置网络簇头节点的百分比,这里我们设定的是0.2,在RECA中簇头节点的百分比也近似是这个比例。初始能量是节点在网络运行前的最大电量,随着发送和接收,能量值逐渐降低。

表1 网络运行参数

3.2 测试结果与分析

本文对所有协议进行100次的仿真实验,TEEN协议采用的是hard模式。结果如下:

图4为各协议在仿真时,节点存活数量随时间变化情况对比图。在存活节点数量为100的时候,RECA的生命周期最长。LEACH协议在进行簇头节点选择的时候,依赖于节点生成的随机数,存在有簇头节点数量过多或过少、簇头节点分布不均匀的问题,导致一些节点能量消耗较快而过早死亡。TEEN协议在LEACH的基础上增加了Hard Threshold和Soft Threshold,减少了节点发送的数据量,但仍然存在同样的问题。PEGASIS协议将所有节点连成一条链,位于链的中间区域的节点需要进行大量的数据转发工作,加剧了节点的死亡。

图4 存活节点数量对比

图5为各协议在仿真时,基站收到的信息量随时间变化情况对比图。图中可以看出,在网络运行相同时间的情况下,采用RECA时,基站接收的信息量最大。LEACH协议在网络运行前期与RECA的信息发送量大致相同,但随着网络中存活节点的减少,需要发送信息的也在减少。TEEN协议主要是通过减少信息的发送来延长网络的生命,因此基站接收的信息量较少。PEGASIS协议同样由于节点的大量死亡,信息发送量减少。

图5 基站接收的信息量对比

图6为各协议在仿真时,网络平均最大数据延迟对比图。RECA相比于其他聚类协议,有着较低的平均最大数据延迟,节点的感知数据能较快发送到基站中。LEACH协议的平均最大数据延迟达到2000以上,PEGASIS的延迟更大。因此,RECA具有高效的传输性能。

图6 平均最大数据延迟对比

4 总结

无线传感器网络的分布式数据高效传输一直以来都影响大规模网络部署应用。本论文在以剩余电量作为重要的指标在聚类阶段完成选取簇头和形成簇的过程,提出了基于分布式聚类的数据传输方法。通过仿真测试,该方法数据延迟非常低,网络生命周期达平均水平,网络整体电池消耗速率均匀,能够高效地进行数据传输。