2. 武汉理工大学 信息工程学院, 武汉 430070
2. School of Information Engineering, Wuhan University of Technology, Wuhan Hubei 430070, China
近年来,网络化的传感和控制系统在许多应用领域中发挥着重要的作用,例如高精度的导弹的设计、生物栖息地的监控、火灾监测、流量监控等[1-2]。在这些应用中,低功耗传感器节点部署的地点都是较大的区域,并且通过自适应的协作传输组成一个网络。由于传感器节点通常被部署在电池能量有限的环境中[3],能源资源优化被认为是一个重要的性能指标,而无线传感器网络的发送和接收数据过程的能量消耗量最大。为了降低传感器节点的能耗,必须使用一些新的高能效技术来最大限度地提高无线传感器网络的能量利用效率[4-5]。由于无线传感器网络在其节点感测能力的覆盖范围内执行数据采集任务,当两个节点间的感测范围出现覆盖重叠面积时,意味两个节点采集到了部分相同的环境数据,这使得网络的能量利用效率降低[6]。在本文算法中,簇头间距的优化以及簇内成员数量的控制使得网络节点的覆盖重叠率降低,使网络能量的利用率提升。
在无线传感器网络能量效率的优化上,单立群等[7]提出一种无线传感器网络中最大化网络寿命的数据聚合路由,将网络最大寿命与流量模型相结合设计了一组混合整数规划代价函数,并获得了近似最优的中继传输速率和路由,该算法可以均衡各个节点的能量消耗并延长网络寿命。蔡宗吟等[8]提出无线传感器网络的一种高性能数据融合算法,路由方面应用流量分布加权算法最大化网络的生命周期,并且采用信誉度评价机制对网络的整体性能进行分析,该算法可以降低节点能量的消耗。Zheng等[9]提出传感器网络子模块效用最大化的约束化数据采集算法,考虑到传感器网络调用的资源约束性质,通过单调子模块的类的实用函数定义节点的子集,更好地考虑到了数据传输量与通信开销之间的权衡。Sutagundar等[10]提出一个基于多Agent的同质态数据汇聚和路由方案,
通过基于节点拓扑结构采用一组静态和动态的Agent,根据节点通信能量消耗情况提出聚合时间和聚合比率的概念,实现高效的数据聚合;但该算法过分关注簇头的数据融合效率,每个簇内有较多节点,一个簇头要承担较多的数据融合任务,能量负载较多,会相应缩减簇头节点寿命。Guo等[11]提出无线传感器网络能量优化的自适应数据汇聚路由策略,先采用一种改进的离散粒子群优化(Discrete Particle Swarm Optimization,DPSO)算法来节约节点的能量成本,接着,以平衡网络负载为目标设计了一种自适应的路由算法;但该算法为了尽量减少节点用于转发数据所消耗的能量而采用了较多的簇头,虽然这种方式能有效均衡簇头的能量,并减少簇内节点的传输能耗,但从能量的角度来说数据融合过程无法得到优化,用于簇头选举以及数据融合上的能量就相应增多,在减少网络总能量消耗上的贡献有限。因此,文献[10-11]算法都不能保证簇头的期望数量,这样很难兼顾到节点的能量效率和能量均衡问题,而本文基于时间跨度变换优化的分簇机制,提出了一种传感器网络分簇时间跨度优化(Clustering Time Span Optimization,CTSO)聚类算法。CTSO聚类算法能优化簇头选举的轮数,减少选举过程中需要的广播能耗,从而在减少能量消耗的同时尽可能地实现能量均衡。
1 相关工作低能量自适应聚类分层型(Low Energy Adaptive Clustering Hierarchy,LEACH)协议是无线传感器网络第一个也是应用最多的聚类算法,其中采用分布式算法来组成网络的簇结构[12]。在LEACH算法中,时间跨度被划分为相同大小的轮,然后每个节点在每一轮开始选择0~1的随机数,当一个节点的数小于给定的阈值,则该节点被允许当选为簇头:
${{T}_{i}}=\left\{ \begin{matrix} \frac{g}{1-\left( R\bmod \frac{1}{g} \right)}, & i\in D \\ 0, & AAAAA \\ \end{matrix} \right.$ | (1) |
其中:g表示簇头节点的所需百分比,即簇头数量与网络中所有节点数量的比值;R表示当前的轮数;D表示在最后的1/g轮不能成为簇头的节点集合。g的表达公式如下:
$g=\frac{{{n}_{head}}}{{{n}_{head}}+{{n}_{\text{regular}}}}$ | (2) |
其中:nhead表示簇头数量;nregular表示网络中常规节点的数量。
虽然这种算法是最流行的聚类算法之一,并被广泛使用,但算法所表现出的性能效果一般,因为簇头的选择完全概率化[13],不能保证在每一轮选择的簇头的期望数目,因此有许多研究学者提出了新的无线传感器聚类方法。
LEACH-B算法[14]的目的是保持每一轮中簇头数量固定,在簇头建立阶段中通过降低或增加簇头的数量以达到网络中所需的数量。如果选择的簇头数目小于所需要数量,每个普通节点就会广播自己来作为一个簇头的候选,并根据特定标准从候选中选出簇头;另一方面,如果选择的簇头的数目大于所需要数量,则算法将清除一些较低能量的簇头。不过该算法存在一个主要的缺陷,即过多的信息需要通过网络来遍历,以实现在每一轮中所选的簇头的正确数目,这样会给网络带来更多的能量损耗。为此,文献[15]提出了一种更低能量的自适应聚类(LEACH-C)算法,基站充当控制器,用于选择簇头。根据节点的位置以及与每个节点相关联的残余能量来作为簇头的选择标准。该方法虽然可以减少能量消耗,但增加了计算负担。
2 本文CTSO算法 2.1 算法特点CTSO聚类算法具有以下特点:1) 以任务执行周期大小作为一个时间跨度,在每个时间跨度中通过考虑网络节点数量、定义簇头间距约束阈值和计算节点当前能量来选择最佳的簇头,而其他大多数的簇头选择算法只考虑节点剩余能量以及簇头与汇聚点的情况来选择簇头,忽略了对簇内成员和簇头间距的研究,当簇头覆盖区域重叠时会浪费能量,而本文算法考虑到这一问题并在簇头的选择上进行了优化。2) 对于簇头的能量问题进行研究,大多研究主要关注簇头的数据融合以及数据转发能耗,而较少关注簇头选举上的能量,然而在每个时间跨度开始时都需要进行簇头的选择,这使得节点的信息需要在每一个轮中被发送出去,这个过程会消耗大量的能量。本文算法针对这一问题将时间跨度变换为多个轮,通过最小化簇头选择的轮数,从而减少用于选择簇头而花费在信息传递上的能量。3) 当簇头的选择轮数固定时,通过确定最佳的周期大小,来确定每个周期的期望簇头数量,在满足能量均衡要求的同时提升簇头的能量效率。
2.2 算法模型对于本文提出的CTSO算法,假设所处的传感器网络环境具有以下条件[16-17]:
1) 基站是固定的,并且位于远离传感器节点的位置;
2) 网络中所有传感器节点都是相同的并且能量有限;
3) 所有的传感器节点在部署之后是固定的;
4) 节点之间的通信是对称的;
5) 节点能够通过测量接收信号的强度来估计来自其他节点的距离;
6) 所有传感器节点以固定的速率监测环境,并且发送数据到基站。
在本文中所使用的能源消耗公式为一阶无线电模型,在一般情况下,与每个节点相关联的发送和接收数据所消耗的能量如下:
1) 一个接收节点接收和处理一个k位的消息所消耗的能量为:
${{E}_{rece}}=k{{E}_{e}}$ | (3) |
其中Ee表示处理1比特位的数据所需要消耗的能量。
2) 发射机节点处理并发射k比特位的数据到相隔距离为d的另一端所需要消耗的能量:
${{E}_{trans}}=k{{E}_{e}}+k\zeta {{d}^{\eta }}$ | (4) |
表 1为部分参数说明表。
本文的聚类算法分为两个阶段:设置阶段和稳态阶段。为了获得更高效节能的聚类算法,应考虑这两方面的互相作用。在设置阶段,由于多数分布式簇头选择算法并不能保证簇头的适当位置以及簇头的期望数量,因此本文提出一个新的方法来进行无线传感器网络簇头的选择。
在无线传感器网络中,当簇头数比所期望的数量要少时,则一些节点必须发送它们的数据到簇头的覆盖范围之外,这使得网络中用于数据传输的能耗较多,而当簇头数比所期望的数量要多时,就会形成更多的簇,由于各个簇头会聚合簇内节点的数据并传输给下一跳,这无疑增加了网络的传输能耗。从减小能耗的角度来说数据融合过程无法得到优化。在该算法中,基站作为一个主要管理者,为当前周期选择最合适的簇头。一个时间跨度被分为几个相同大小的轮,并且一个周期由一个或多个轮组成。
根据假设,在网络的生命周期内可以获取在第一轮中的节点的位置有关信息,然而,关于这些节点的剩余能量信息则必须在每个簇头的选择阶段开始时被发送出去。簇头选择的变换函数被定义为:
$G_{i}^{t}=\frac{{{y}_{c}}R_{i}^{t}+{{y}_{d}}M_{i}^{t}}{2}+\sqrt{{{y}_{c}}^{2}+{{y}_{d}}^{2}}$ | (5) |
其中: yc和yd分别表示对应于Rit和Mit的权值因子;i表示节点唯一的标识号;t表示当前时间。
$R_{i}^{t}=\frac{2{{e}^{\frac{E_{i}^{t}}{{{E}_{C}}}}}-1}{2}\left[ \frac{1}{{{E}_{C}}-E_{i}^{t}} \right]$ | (6) |
其中:EC表示初始能量;Eit表示节点i的当前能量。
$M_{i}^{t}=\frac{\sqrt{2}\lg \left( \frac{UN_{i}^{t}}{eUNN_{i}^{t}}+1 \right)}{3}$ | (7) |
其中:UNit表示在半径R内传感器节点i的邻居中传感器节点数目;UNNit表示在时间t内的所有节点中邻居节点的最大数目。
采用式(5)进行簇头选择时,会定义一个簇头间的距离约束阈值dCluster,即当选的簇头需要与邻居簇头的间隔大于dCluster,否则将重新选举簇头。采用距离约束可以防止基站选择了属于相同覆盖区域的簇头。一旦簇头被确定,该基站广播该簇头的ID至网络中,根据这些信息,节点会发现自己最近的簇头并发送自身的感测数据。
在稳态阶段中,本文会确定一个选取最佳周期大小的方法。对于一个给定周期大小的情况,本文将其作为一个时间跨度,分为多个轮。在簇头和簇成员数量保持不变的情况下,在多个轮中保留对最佳簇头的选择能够延长网络的生命周期。在大多数先前提出的传感器网络聚类算法中,在每个回合开始时都需要进行簇头的选择,这使得节点的信息需要在每一个轮中被发送出去,这个过程会消耗大量的能量,然而簇头选择时的能耗问题在许多能量优化算法中没有被提出来。为了实现找到最佳周期大小的目的,需要将不同的能量消耗量与每个轮进行相关联分析,即相关联的能量消耗包括了普通节点、簇头和簇头的变换。
在每一轮中,一个普通节点从周围环境感测到数据,并将其发送到簇头。根据Heinzelman一阶无线电模型,在任何一轮期间每个普通节点的能量消耗量为:
${{E}_{n}}=l{{E}_{e}}+l{\zeta }'{{d}_{C}}^{\prime }$ | (8) |
其中:l表示每个感测到的数据消息中的比特数;d′C是从常规节点到簇头的距离。
${{E}_{C}}=\left( l{{E}_{e}}{{N}_{r}} \right)+\left( l{{E}_{G}}\left( {{N}_{r}}+1 \right) \right)+\left( \eta l{{E}_{e}}\left( {{N}_{r}}+1 \right) \right)+\left( \eta l\zeta {{d}_{B}}^{4} \right)$ | (9) |
其中:Nr表示簇成员数量;EG表示用于数据聚集的必需能量;η表示聚合因子,显示由于数据冗余和聚集导致的数据量减少;dB表示簇头节点到基站的距离。最后,可以得到该簇头改变时能量消耗量的计算方法如下:
在每个簇头的变化过程中,每个簇头发送一个广播消息至其覆盖区域内的固定节点。这个过程后,一个普通节点根据该节点和不同簇头之间的距离选择一个合适的簇头并发送加入请求消息到所选择的簇头。其结果是,与一个簇头变化相关联的能量消耗量为:
${{E}_{CC}}=2{{l}_{C}}{{N}_{r}}{{E}_{e}}+{{l}_{C}}{{N}_{r}}{\zeta }'{{d}_{N}}$ | (10) |
其中:lC表示在每个广播或加入请求消息的比特数;dN表示簇头与及其相应的簇成员之间的平均距离。
从能量消耗的观点来看,它显示了当一个节点成为簇头,该节点会尽可能长时间地在轮数的约束下仍担任簇头的工作,并且该簇头不会超过周期的大小。因为在网络的生命周期中所述节点消耗的总能量不能超过该节点的初始能量,因此可以写为:
${{r}_{CH}}{{E}_{C}}+{{r}_{r}}{{E}_{r}}+{{M}_{c}}{{E}_{CC}}\le {{E}_{T}}$ | (11) |
其中:rCH表示簇头周期大小;rr表示一个在网络的生命周期内一个节点作为一个普通节点的轮数;Mc表示一个节点在作为一个普通节点和一个簇头之间交替的次数。对于最小化能量消耗量来说Mc=1时是最好的情况,更进一步,式(11)可以改写为:
${{r}_{r}}\le {{E}_{T}}-{{r}_{CH}}{{E}_{C}}-{{E}_{CC}}/{{E}_{r}}$ | (12) |
$s.t.{{r}_{r}}\le {{r}_{CH}}/g$ | (13) |
理想的情况是当一个节点仅在一轮成为一个簇头且在其他轮作为普通节点;然而由于必须满足式(12),因此一定数目的簇头必须存在于每个轮中。约束条件(13)必须在任何时候都被满足。
考虑到上述所有情况,应该清楚的是最佳的周期大小应满足式(14):
$\left( {{E}_{T}}-{{r}_{CH}}{{E}_{C}}-{{E}_{CC}} \right)/{{E}_{r}}\le {{r}_{CH}}/g$ | (14) |
最后,最佳的簇头周期大小是数目大于rCH的最小的整数。所提出的簇头选择周期优化算法的流程如图 1所示。在网络的初始阶段,节点将位置信息及剩余能量信息发送给基站,基站为网络选择簇头。当节点满足条件当选为簇头时,会将信息广播出去,满足距离阈值条件的邻居节点会加入到该簇中,而当没有节点满足簇头的选择条件时,程序结束。设置当选的簇头节点的初始计数器=0,当该节点的计数器小于最佳的簇头周期大小(即该节点当选簇头的最佳轮数)时,该节点在该轮中继续充当簇头,执行簇头的工作,并且计数器+1,在下一轮中计数器仍小于周期,则继续充当簇头,当计数器大于簇头周期时,则网络为该簇重新选择簇头。
为了评估该算法的性能,采用Matlab 7.1仿真软件进行仿真实验,并且将结果与现有的算法进行了比较。性能通过定量指标,例如系统寿命、平均能量消耗量和基站成功接收的总感测数据消息量来进行算法性能评价。
3.1 网络模型在用于仿真实验的模型中,假设n个传感器节点分布在一个100 m×100 m的区域内,在整个簇面积节点分布的密度均匀,且具有如下属性:
1) 传感器节点均匀分布;
2) 基站位于一定的高度且坐标为(50,150)的位置;
3) 所有传感器节点的初始能量为1 J;
4) 节点的部署数量为50;
5) 节点的感测范围为50 m;
6) 汇聚节点的坐标为(20,50);
7) 每个数据包大小为500 B,每轮传输的数据包为20个。
距离公式为欧几里得距离公式:
${{d}_{12}}=\sqrt{\left( {{x}_{1}}^{2}-{{x}_{2}}^{2} \right)+\left( {{y}_{1}}^{2}-{{y}_{2}}^{2} \right)}$ | (15) |
为了更有效地评价CTSO算法,以Sutagundar算法[10]和Guo算法[11]作为对比算法。Sutagundar算法具有很好的数据聚合效果,能够减少数据聚合能耗;Guo算法利用了粒子群寻优的策略,使得数据汇聚向最好的簇头,得到近似最优解。
仿真时间以轮数为单位,共2000轮,观察在仿真过程中的数据变化,并将数据结果以曲线形式进行表示。对于网络的系统寿命,本文通过存活节点的数量占总节点数量的比值来作为系统寿命的度量。从图 2可看出,在仿真实验结束后CTSO算法的存活节点比值为51%,
Sutagundar算法的存活节点比值为34%,Guo算法的存活节点比值为42%。从数据上看,采用CTSO算法的网络系统寿命更长,这是由于Sutagundar算法和Guo算法只关注簇头的选举方法,通过最佳的簇头位置来节省网络能量,而CTSO算法不仅关注簇头的选举方法,对簇头的期望数量也进行了重点研究,使得不会因为簇头数量过少而给簇头节点带来过大的负担,也使得有一些节点不得不发送数据给较远的簇头节点,消耗更多的能量,也防止了由于簇头数量过多而带来更多的能量消耗。
图 3为基站接收到的数据包数量,在仿真过程中基站接收到的数据包数量越多,说明算法的数据汇聚效率越高。从图 3可看出:CTSO算法的数据包汇聚数量超过了Sutagundar算法和Guo算法,这与CTSO算法的簇头选举机制有关,而且CTSO算法对簇头选举过程的周期大小进行了讨论,使得在尽可能短的时间内选择最佳的簇头,保证了簇头的及时更换并缩短了簇头选举的操作时间,提高了数据聚合效率。
图 4显示了在仿真过程中的节点平均能量剩余情况,节点的平均能量剩余情况能够体现网络的节能性能。从图 4可看出:CTSO算法与另外两种算法在节能上各占优势,首先在仿真时间为800轮前,Sutagundar算法和Guo算法的节能情况要比CTSO算法好,而在800轮至2000轮,CTSO算法的节能优势开始体现,效果优于Sutagundar算法和Guo算法。Sutagundar算法在第一轮通信之后就开始根据簇头节点的通信能耗情况对数据聚合时间及聚合数据量大小进行限制,以提高节点的能量利用效率;Guo算法采用离散粒子群优化算法使得在分簇上算法具有较好的全局收敛性,并且初次迭代后基于剩余能量的粒子寻优方法使得簇头能量得到有效均衡;由于CTSO算法在寻找最佳簇头选择周期时,需要将簇头选举过程的不同能耗量与每个轮进行相关联分析,在仿真的初始阶段无法实现能量最优,但在该聚类算法的稳态阶段执行结束后,簇头选举的操作时间开始变短,并且每一轮中簇头数量的优化使得网络的平均能耗得到了控制。
本文提出的CTSO算法共分为两个阶段:在第一阶段考虑网络节点数量、定义簇头间距约束阈值、计算节点当前能量,用来选择最合适的候选者作为簇头;在第二阶段中,簇头选举的时间跨度概念被引入,通过更短的簇头选举周期来延长网络的生命周期,并且使得在有限的数据采集过程中可以接收到更多的数据流量。仿真实验中以系统寿命、平均能量消耗量和基站成功接收的总感测数据消息量作为定量指标来对算法进行评价,并采用了对比分析的方法。对比结果表明,本文提出的CTSO算法在这些定量指标上比对比算法体现出了更好的效果。
[1] | KARIM L, NASSER N, SHELTAMI T. A fault-tolerant energy-efficient clustering protocol of a wireless sensor network[J]. Wireless Communications and Mobile Computing, 2014, 14 (2) : 175-185. doi: 10.1002/wcm.v14.2 (0) |
[2] | LEU J S, CHIANG T H, YU M C, et al. Energy efficient clustering scheme for prolonging the lifetime of wireless sensor network with isolated nodes[J]. IEEE Communications Letters, 2015, 19 (2) : 259-262. doi: 10.1109/LCOMM.2014.2379715 (0) |
[3] | NIKOLIDAKIS S A, KANDRIS D, VERGADOS D D, et al. Energy efficient routing in wireless sensor networks through balanced clustering[J]. Algorithms, 2013, 6 (1) : 29-42. doi: 10.3390/a6010029 (0) |
[4] | PEIRAVI A, MASHHADI H R, JAVADI S H. An optimal energy-efficient clustering method in wireless sensor networks using multi-objective genetic algorithm[J]. International Journal of Communication Systems, 2013, 26 (1) : 114-126. doi: 10.1002/dac.v26.1 (0) |
[5] | PAN T S, NGUYEN T T, DAO T K, et al. An optimal clustering formation for wireless sensor network based on compact genetic algorithm[C]//Proceedings of the Third International Conference on Robot, Vision and Signal Processing. Piscataway, NJ: IEEE, 2015:294-299. (0) |
[6] | AGHBARI Z A, KAMEL I, ELBARONI W. Energy-efficient distributed wireless sensor network scheme for cluster detection[J]. International Journal of Parallel, Emergent and Distributed Systems, 2013, 28 (1) : 1-28. doi: 10.1080/17445760.2012.729584 (0) |
[7] | 单立群, 汪晋宽, 刘志刚, 等. 无线传感器网络中最大化网络寿命的数据聚合路由[J]. 控制与决策, 2013, 28 (4) : 609-612. ( SHAN L Q, WANG J K, LIU Z G, et al. Maximum lifetime routing with data aggregation in wireless sensor networks[J]. Control and Decision, 2013, 28 (4) : 609-612. ) (0) |
[8] | 蔡宗吟, 刘才铭, 刘毅, 等. 一种高性能数据融合算法在无线传感器网络中的应用[J]. 青岛科技大学学报(自然科学版), 2013, 34 (3) : 309-314. ( CAI Z Y, LIU C M, LIU Y, et al. Application of high performance data fusion algorithm in wireless sensor network[J]. Journal of Qingdao University of Science and Technology (Natural Science Edition), 2013, 34 (3) : 309-314. ) (0) |
[9] | ZHENG Z, SHROFF N B. Submodular utility maximization for deadline constrained data collection in sensor networks[J]. IEEE Transactions on Automatic Control, 2014, 59 (9) : 2400-2412. doi: 10.1109/TAC.2014.2321683 (0) |
[10] | SUTAGUNDAR A V, MANVI S S. Fish bone structure based data aggregation and routing in wireless sensor network: multi-Agent based approach[J]. Telecommunication Systems, 2014, 56 (4) : 493-508. doi: 10.1007/s11235-013-9769-z (0) |
[11] | GUO W, HONG W, ZHANG B, et al. Reliable adaptive data aggregation route strategy for a trade-off between energy and lifetime in WSNs[J]. Sensors, 2014, 14 (9) : 16972-16993. doi: 10.3390/s140916972 (0) |
[12] | ZAWAIDEH F, SALAMAH M, BISHER A. Adaptive balanced clustering for wireless sensor network energy optimization[J]. Network and Complex Systems, 2014, 4 (4) : 20-29. (0) |
[13] | CHEN H, WU X, WANG Y, et al. A dynamic underwater sensor network architecture based on physical clustering and intra-cluster autonomy[C]//CWSN 2013: Proceedings of the 7th China Conference on Advances in Wireless Sensor Networks. Berlin: Springer, 2014: 82-92. (0) |
[14] | AWWAD S A B, NG C K, NOORDIN N K, et al. Cluster based routing protocol for mobile nodes in wireless sensor network[J]. Wireless Personal Communications, 2011, 61 (2) : 251-281. doi: 10.1007/s11277-010-0022-8 (0) |
[15] | MURUGANATHAN S D, MA D C F, BHASIN R I. A centralized energy-efficient routing protocol for wireless sensor networks[J]. IEEE Communications Magazine, 2005, 43 (3) : 8-13. doi: 10.1109/MCOM.2005.1404580 (0) |
[16] | ASLAM N, PHILLIPS W, ROBERTSON W, et al. A multi-criterion optimization technique for energy efficient cluster formation in wireless sensor networks[J]. Information Fusion, 2011, 12 (3) : 202-212. doi: 10.1016/j.inffus.2009.12.005 (0) |
[17] | MARAIYA K, KANT K, GUPTA N. Efficient cluster head selection scheme for data aggregation in wireless sensor network[J]. International Journal of Computer Applications, 2011, 23 (9) : 10-18. doi: 10.5120/ijca (0) |