无线传感器网络基于多元簇首的分簇数据收集算法

胡升泽 包卫东 王 博 乐 俊 葛 斌

①(国防科学技术大学信息系统工程重点实验室 长沙 410073)

②(北京信息技术研究所 北京 100094)

③(西南电子电信技术研究所 成都 610041)

1 引言

无线传感器网络(Wireless Sensor Networks,WSN)能够获取网络分布区域内的各种环境或监测对象的信息并传送给用户，使人们获得大量详实而可靠的信息[1,2]。WSN 集成了传感器、微机电系统和网络三大技术，在军事和民用领域都有着广阔的应用前景[1-4]。数据收集是WSN应用的一项基本工作，分簇数据收集算法具有简单、灵活、易扩展等特点，是 WSN数据收集算法研究的重点和热点[5-8]。

在很多WSN应用中，节点容易因为自然条件、电磁环境等原因而失效[9]。在使用分簇数据收集算法收集数据时，如果某个簇首失效，相关簇成员的数据收集就可能受到影响，从而使数据收集的可靠性降低。另外，很多 WSN的节点通常只能配备能量有限的电源，网络生命周期受限。因此，如何提高数据收集可靠性和延长网络生命周期，就成为分簇数据收集算法亟待解决的两个关键问题。

LEACH(Low-Energy Adaptive Clustering Hierarchy)[10,11]是一种经典的分簇数据收集算法，之后的很多分簇数据收集算法都是在其基础上改进得到的[12]。该算法以轮为单位周期性运行，每轮包括设置和稳定两个阶段，前者执行选择簇首和构建簇的任务，后者完成收集数据的工作。周期性运行机制能够避免因为某个簇首失效而长时间数据收集。但是，在该算法和很多其它分簇数据收集算法中，每个簇成员只从属于一个簇首，如果某个簇首失效，其所在簇中所有节点的数据都将无法收集。因此，为了提高数据收集可靠性，就必须降低簇成员对单个簇首的依赖程度。目前，已经有学者进行了相关研究，具有代表性的算法主要有 REED(Robust Energy Efficient Distributed clustering)[13,14],O-LEACH(Overlapping LEACH)[15]和 DED(Distributed, Energy-efficient and Dual-homed clustering)[16]。

REED将网络虚拟成多层覆盖网，每层覆盖网都包括所有节点，每轮分别在各层覆盖网中选择簇首和构建簇，从而使每个簇成员都能够同时从属于多个簇首。O-LEACH是LEACH的改进版本，在每轮的设置阶段，每个普通节点首先选择接收信号强度最大的簇首作为主簇首，然后，再以主簇首接收信号强度的X%(0＜X≤100)为标准，选择接受信号强度大于该标准的所有簇首，并加入主簇首和这些簇首所在的簇，从而使每个簇成员都能够从属于多个簇首。在收集数据的时候，REED和O-LEACH的各个簇成员都将数据同时发送至多个簇首。DED在分簇完成之后，由每个簇成员从除自己簇首之外的邻近节点中选择一个节点作为备份节点，在收集数据的时候，如果某个簇成员自己的簇首失效，则该簇成员可以将数据发送至备份节点。

上述算法都可以提高数据收集的可靠性，但也都存在一定的不足。REED在每层覆盖网中都分簇，增加了能量开销。O-LEACH中每个簇成员的簇首数目是不确定的，算法在提高数据收集可靠性方面也具有不确定性。此外，在REED和O-LEACH中，如果某个簇成员的簇首中有多个正常簇首，则这些正常簇首都会收集该簇成员的数据，出现重复收集数据的现象，增加了不必要的能量开销。而在DED中，如果某个节点的备份节点也是簇成员，在收集的过程中，该节点的数据需要被转发的次数就会增加，成功收集该节点数据的概率也会随之降低，所以，该算法能够提高的数据收集可靠性有限，文献[16]中的对比实验结果也表明，在数据收集可靠性方面，DED的性能比REED差。

本文提出基于多元簇首的分簇数据收集算法(Clustering data gathering algorithm based on Multiple Cluster Heads, CMCH)，期望既可以提高数据收集可靠性，又能够延长网络生命周期。

2 基础模型

CMCH的网络模型设定部署区域是一个边长为M的正方形区域，基站位于部署区域之外的某个位置，N个节点随机均匀分布在部署区域内，每个节点都有一个唯一的整型ID，此外，网络还具有如下性质：(1)基站和节点的位置不变而且位置信息可知；(2)各节点以及基站之间时间同步；(3)节点之间同构；(4)节点的能量有限；(5)节点能够根据通信距离调整发射功率。

CMCH采用同类算法常用的能耗模型，统计节点发送、接收和融合数据的能耗[11]。节点在发送数据时，如果发送距离小于阈值d0，采用自由空间模型，否则，采用多路径衰减模型。节点发送和接收长度为lbit数据的能耗计算公式分别为式(1)和式(2)，其中，d是数据发送距离，Ee是无线收发电路发送或接收单位长度数据的电路能耗，εfs和εmp分别是自由空间模型和多路径衰减模型的放大器能耗参数。

3 CMCH算法介绍

CMCH也按轮周期性运行，每轮包括设置阶段和稳定阶段，并在首轮之前设有初始化阶段。为了避免混淆，首先界定以下几类节点：存活节点指能量未耗尽的节点，死亡节点指能量已经耗尽的节点，失效节点指能量未耗尽但是无法正常工作的节点，正常节点指能量未耗尽而且可以正常工作的节点。

3.1 初始化阶段

不失一般性，假设在2维坐标系中，部署区域的横边与横坐标轴平行，基站位于部署区域沿纵坐标轴的上方，坐标为(BSx,BSy)。将部署区域的左下角顶点作为部署区域的起始点，设其坐标为(Ox,Oy)。

首先，根据节点失效概率确定每个栅格预期的簇首数目K。设节点失效概率为P，则每个栅格中正常簇首的期望数目为(1-P)K。一般情况下，栅格预期簇首数目越大，数据收集可靠性就越高，但是能量开销也会越多。因此，可以选择使栅格预期簇首数目不小于1的最小自然数作为K的值，即

根据预期能量消耗和K的值确定栅格划分的标准，也就是确定栅格的数目G和栅格的边长B。算法采用固定分簇的方法，所以，簇的数目和栅格的数目相等，也为G。算法采用与文献[11]类似的方法确定G的最佳取值。假设簇首向基站发送数据时采用多路径衰减模型，则簇首的能耗为

此外，还应当使每个栅格中预期分布的节点数目不小于栅格预期簇首数目。由于节点随机均匀分布在部署区域中，每个栅格中预期分布的节点数目为N/G，因此，栅格数目应满足条件：

在实际应用中，可以根据式(14)和式(15)确定适当的栅格数目。如果无法同时满足，在侧重能耗指标的应用中，应优先满足式(14)，在侧重数据收集可靠性的应用中，应优先满足式(15)。

栅格的数目为G，则每一行或每一列的栅格的数目均为，可以得到栅格的边长B为

另外，由于算法在簇成员和簇首之间采用单跳的方式连接，而簇首在栅格中的节点之间轮换，要求栅格中任意两个节点都能够实现单跳连接。设节点的最大通信距离为R，则栅格的边长B还必须满足：

然后，由基站向所有节点广播BS_MSG((Ox,Oy), (BSx,BSy),M,K,G,B)消息。最后，各个节点从消息中获取并保存相关信息，根据自己的位置坐标确定自己属于哪个栅格。算法用二元组(Gx,Gy)作为栅格ID，其中，Gx是栅格横标识，Gy是栅格纵标识，规定左下角栅格的ID为(1, 1)，右上角栅格的ID为ID为(Gx,Gy)的栅格的覆盖范围为

坐标为(x,y)的节点根据式(20)和式(21)计算所属栅格的栅格横标识和栅格纵标识。

3.2 设置阶段

初始化阶段完成之后，网络便可以开始按轮运行，每轮首先进入设置阶段。在设置阶段，每个栅格根据节点的剩余能量分别选择多个簇首，并由簇首基于时分复用的方式为栅格中的节点分配通信时隙。

首轮中，各个栅格的簇首分别由栅格内的节点协作选出。首先，每个节点通过组播的方式向所属栅格的其它节点发送节点信息消息，消息中包括节点的ID，坐标，所属栅格ID和剩余能量。所属栅格ID为(Gx,Gy)，坐标为(x,y)的节点按照如表1所示的过程，计算与所属栅格4个顶点距离的最大值dmax，并以此为标准确定消息的传输距离。

节点根据接收的其它节点的信息和节点自身的信息，按照剩余能量从大到小，对所有节点进行排序。在排序的过程中，如果出现多个节点剩余能量相同的情况，则按照节点ID从小到大确定它们的顺序。然后，选择排序靠前的K个节点作为栅格的簇首。接着，节点检查自己是否包括在这些簇首之中，如果是，则节点将自己设置为簇首，否则，节点就将自己设置为簇成员。最后，每个簇首根据排序位置确定自己的优先级，排序越靠前则簇首的优先级越高。

表1 节点计算dmax的过程

簇首选择完成后，各个簇首为本栅格所有节点分配通信时隙，并通过组播的方式向本栅格的其它节点发送通信时隙消息。通信时隙消息由栅格中的簇首按照优先级的顺序发送，如果簇首已经收到本栅格优先级较高簇首发送的通信时隙消息，则该簇首放弃发送通信时隙消息，从而避免重复发送。

将首轮之后的任意一轮称为非首轮。为了完成非首轮设置阶段的工作，在每一轮稳定阶段最后一次数据收集时，每个节点将自己的剩余能量等信息通过捎带的方式附加在数据消息中发送给簇首，簇首也通过捎带的方式将所收集的节点信息附加在数据消息中发送至基站。在非首轮的设置阶段，首先由基站向所有节点广播其在上一轮最后一次数据收集时所收集的各个栅格的节点信息。如果某些节点在上一轮中失效，则广播消息中没有这些节点的信息。因此，节点从广播消息中获取和保存本栅格的节点信息后，需要检查该消息中是否有自己的信息，如果没有，则节点采取与首轮设置阶段相同的方法向所属栅格的其它节点发送自己的节点信息。这样，每个节点就能够收集到所属栅格其它节点的信息，然后再按照与首轮设置阶段相同的方法选择簇首、确定簇首的优先级、分配通信时隙和发送通信时隙消息。

3.3 稳定阶段

稳定阶段完成数据收集的工作。首先，包括簇首在内的每个节点在自己的通信时隙内，通过组播的方式向本栅格的簇首发送数据消息。然后，簇首将收集的数据和自己的数据进行融合处理。最后，由簇首向基站发送数据消息。为了避免栅格中多个簇首重复发送消息，各个栅格中的簇首按照优先级的顺序向基站发送消息，如果优先级较高的簇首已经发送，则其它簇首不再发送。

如果当前是本轮最后一次数据收集，每个节点将自己的剩余能量等信息通过捎带的方式附加在数据消息中发送至簇首，簇首也通过捎带的方式将收集的节点信息附加在数据消息中发送至基站。

4 CMCH算法分析

在数据收集可靠性方面，CMCH使簇成员同时从属于多个簇首，各个簇首也从属于所属栅格的其它簇首。只要栅格中还有正常簇首，则该簇首就可以收集栅格中所有正常节点的数据，从而完成该栅格的数据收集任务。因此，算法能够有效降低簇成员对单个簇首的依赖，可以提高数据收集可靠性。

在网络生命周期方面，CMCH采取了一系列降低能量开销的措施，提高了能量使用效率，能够延长网络的生命周期。首先，算法采用固定分簇方法，每轮只需要重新选择簇首，降低了分簇过程中的能耗。其次，算法采用捎带的方式将选择簇首所需的节点信息附加在数据消息中传输，并由基站广播节点信息，降低了选择簇首所需的能耗。再次，各个栅格中的簇首根据优先级向节点发送通信时隙消息和向基站发送数据消息，能够避免重复发送，从而可以节约能量。最后，算法将消息的发送距离和接收节点限定在适当的范围之内，也能够降低能量开销。

5 仿真实验

本文在 MATLAB平台上进行仿真实验，并将CMCH与REED和O-LEACH进行对比。实验中，节点总数为400，每个节点的初始能量都为0.5 J，控制消息和数据消息的长度分别为800 bit和1600 bit，其它实验参数如表2所示。根据式(14)可以确定CMCH最佳栅格数目的范围为1.93

表2 实验参数

表3 P以及相应的K和N/K的值

在所有节点失效概率下都满足式(14)和式(15)，而且可以作为栅格数目的选项有4, 9, 16, 25和36，各选项下的栅格边长均满足式(17)。本文将CMCH栅格数目设置为大小适中的16，将REED每层覆盖网每轮预期选择簇首数目以及O-LEACH每轮预期选择簇首数目也都设置为16，另外，REED覆盖网为K层，O-LEACH的参数X设置为50。

首先，通过仿真实验对比各个算法的数据收集可靠性。将因为簇首失效而无法对其数据进行收集的有效节点称为连带失效节点。那么，在节点失效概率相等的情况下，算法的连带失效节点越少，就表明算法具有更高的数据收集可靠性。统计仿真实验中各个算法在出现死亡节点之前每轮连带失效节点的平均数，如图1所示。可以看出，CMCH的连带失效节点平均数都少于 REED，表明 CMCH的数据收集可靠性高于 REED。在大多数情况下，CMCH的连带失效节点平均数也都少于 OLEACH，因此，从总体上看，CMCH在数据收集可靠性方面的性能也优于O-LEACH。

接着，比较各个算法在网络生命周期方面的性能。以网络开始运行到出现第1个死亡节点前所经历的轮数作为网络生命周期，仿真实验中，3种算法的网络生命周期如图 2所示。在相同条件下，CMCH的网络生命周期都要远远长于O-LEACH和REED，证明CMCH能够显著延长网络生命周期。

最后，通过仿真实验考察栅格数目G对CMCH性能的影响。在G的取值分别为4, 9, 16, 25和36的情况下，CMCH的连带失效节点平均数和网络生命周期分别如图3和图4所示。总体上看，在数据收集可靠性方面，栅格数目越多，算法的性能越好，而在网络生命周期方面，随着栅格数目由少到多，算法的性能呈现先升后降的态势。

图1 各算法的连带失效节点平均数

图2 各算法的网络生命周期

图3 不同栅格数目的连带失效节点平均数

图4 不同栅格数目的网络生命周期

6 结束语

提高数据收集可靠性和延长网络生命周期是分簇数据收集算法亟待解决的两个关键问题。为了解决上述问题，本文提出了CMCH算法。仿真实验结果表明，与现有的REED和O-LEACH算法相比，该算法具有较高的数据收集可靠性，并显著延长了网络的生命周期。下一步工作将研究如何应对栅格中全部簇首节点都失效的情况，以及簇首采用多跳方式向基站发送数据的应用，并放宽算法的前提条件，以扩展算法的适用范围，还将对算法的时延性能进行分析和考察。

[1] 李建中, 高宏. 无线传感器网络的研究进展[J]. 计算机研究与发展, 2008, 45(1): 1-15.Li Jian-zhong and Gao Hong. Survey on sensor network research[J].Journal of Computer Research and Development,2008, 45(1): 1-15.

[2] Liu W, Chen H, and Chen M. A survey of wireless sensor networks[C]. Proceedings of the World Automation Congress,Puerto Vallarta, Mexico, 2012: 305-307.

[3] 任丰原, 黄海宁, 林闯. 无线传感器网络[J]. 软件学报, 2003,14(7): 1282-1291.Ren Feng-yuan, Huang Hai-ning, and Lin Chuang. Wireless sensor networks[J].Journal of Software, 2003, 14(7):1282-1291.

[4] Sakthidharan G R and Chitra S. A survey on wireless sensor network: an application perspective[C]. Proceedings of the International Conference on Computer Communication and Informatics, Coimbatore, India, 2012: 1-5.

[5] Abbasi A A and Younis M. A survey on clustering algorithms for wireless sensor networks[J].Computer Communications,2007, 30(14/15): 2826-2841.

[6] Boyinbode O, Le H, Mbogho A,et al.. A survey on clustering algorithms for wireless sensor networks[C]. Proceedings of the International Conference on Network-Based Information Systems, Gifu, Japan, 2010: 358-364.

[7] Kumar V, Jain S, and Tiwari S. Energy efficient clustering algorithms in wireless sensor networks: a survey[J].International Journal of Computer Science Issues, 2011, 8(5):259-268.

[8] Tuah N, Ismail M, and Jumari K. An energy-efficient node-clustering algorithm in heterogeneous wireless sensor networks: a survey[J].Journal of Applied Sciences, 2012,12(13): 1332-1344.

[9] Yick J, Mukherjee B, and Ghosal D. Wireless sensor network survey[J].Computer Networks, 2008, 52(12): 2292-2330.

[10] Heinzelman W, Chandrakasan A, and Balakrishnan H.Energy-efficient communication protocol for wireless microsensor networks[C]. Proceedings of the International Conference on System Sciences. Hawaii, USA, 2000:3005-3014.

[11] Heinzelman W, Chandrakasan A, and Balakrishnan H. An application-specific protocol architecture for wireless microsensor networks[J].IEEE Transactions on Wireless Communications, 2002, 1(4): 660-670.

[12] Aslam M, Javaid N, Rahim A,et al.. Survey of extended LEACH-based clustering routing protocols for wireless sensor networks[C]. Proceedings of the International Conference on High Performance Computing and Communications,Liverpool, United Kingdom, 2012: 1232-1238.

[13] Younis O, Fahmy S, and Santi P. Robust communications for sensor networks in hostile environments[C]. Proceedings of the International Workshop on Quality of Service, Montreal,Canada, 2004: 10-19.

[14] Younis O, Fahmy S, and Santi P. An architecture for robust sensor network communications[J].International Journal of Distributed Sensor Networks, 2005, 1(3-5): 305-327.

[15] Suharjono A, Wirawan, and Hendrantoro G. Dynamic overlapping clustering algorithm for wireless sensor networks[C]. Proceedings of the International Conference on Electrical Engineering and Informatics, Bandung, Indonesia,2011: 1-6.

[16] Mohammad M H and Jason P J. Survivable self-organization for prolonged lifetime in wireless sensor networks[J].International Journal of Distributed Sensor Networks, 2011,2011(1): 1-11.