无线传感器网络多汇聚节点分簇算法
周伟
摘 要： 为解决大规模无线传感器网络的节点通信效率问题，提出无线传感器网络的一种多汇聚节点分簇算法，针对拥有多个汇聚节点的监控区域，对网络进行层次化管理。算法通过对多种参数的综合考虑后产生簇头，并将传感器节点分配到相应的簇，由此可以有效降低节点的非均匀能耗，减少因能耗较大节点的能量过度衰竭而造成网络可用率下降。仿真结果显示，该算法可以延缓首个死亡节点的发生时间，并能有效延长无线传感器网络的整体可用率。
关键词： 无线传感器网络； 汇聚节点； 分簇算法； 能耗降低
中图分类号： TN711?34； TP393 文献标识码： A 文章编号： 1004?373X（2017）13?0026?04
Abstract： In order to solve the problem of node communication efficiency for large?scale wireless sensor network， a multiple sink nodes based clustering algorithm for wireless sensor network is presented. Aiming at the monitoring area with multiple sink nodes， the hierarchical management is performed for the network. The various parameters are considered comprehensively in the algorithm to generate the cluster head， and sensor nodes are distributed to the corresponding clusters to reduce the uneven energy consumption of the nodes， and avoid the network availability decline caused by the excessive energy exhaustion of the nodes with large energy consumption. The simulation results show that the algorithm can delay the occurrence time of the first death node， and prolong the overall availability of the wireless sensor network effectively.
Keywords： wireless sensor network； sink node； clustering algorithm； energy consumption reduction
0 引 言
无线传感器网络是通信网络与传感器技术的融合产物，广泛应用于工业、农业、军事、医疗等多种领域[1]。随着现代科技的不断进步，传感器的集成度越来越高，尺寸越来越小，成本也不断降低[2]，这也为大规模、低成本地使用传感器进行组网应用带来了契机。
大规模无线传感器网络[3]的使用带来了一些新的问题。例如，如何管理大片区域的大量传感器节点[4]，如何避免某些区域的传感器因能量消耗过大而提早失去功能[5]，如何实现有效的动态路由选择等。采用分簇算法对网络进行分层管理可以有效解决上述问题[6]，并提升整个无线传感器网络的性能。
早期较为成熟的无线传感器网络分簇算法是LEACH算法[7]。该算法随机产生簇头，并将各个传感器节点按照距离因素分配到邻近簇头，并周期性进行簇头资格轮换，从而实现良好的分簇效果。HEED算法[8]是对LEACH算法的改进。该算法以节点的剩余能量为依据，按照一定概率产生簇头。此外，还有一些算法在此基础上做了进一步的优化[9]，或者采用以地理位置等多种因素进行分簇的方法[10]。
上述这些算法绝大部分都是以单个汇聚节点为基础，实现有中央控制的层次型网络管理。在实际应用中，当网络规模较大，覆盖面积也较广时，采取多个汇聚节点对网络进行控制和管理[11]，是一种有效的手段。多匯聚节点下的无线传感器网络的管理，不应该简单采用将单汇聚节点网络进行拼接的方式。因为这样做会造成区域之间的割裂；同时，区域的地理特性往往与无线通信环境并不完全一致，地理分区对无线通信的效率分配缺乏帮助；而在网络拓扑结构动态变化的情况下，简单分区无法对这一变化进行适应和调整。
基于多汇聚节点的算法设计，就是为了解决在大规模网络中使用单汇聚节点算法的不足。RDF算法[12]使用以节点位置为区分依据的栅格来划分传感器节点与汇聚节点的对应关系；HLBR算法[13]采用综合节点剩余能量和到汇聚节点距离因素的负载均衡算法来解决到汇聚节点的路径。然而这些算法的模型比较简单，适应于较少汇聚节点情况下的网络通信以及传感器节点动态变化情况较小的场景。
本文提出一种多汇聚节点环境下的无线传感器网络分簇算法，针对大规模无线传感器网络的特点实施层次化的网络管理。
1 多汇聚节点模型
对于大规模的无线传感器网络，使用多个汇聚节点，可以降低对单个汇聚节点发射功率的要求，也可解决因到单一汇聚节点的路由不可达[14]而导致的网络崩溃问题。
1.1 汇聚节点的位置
多个汇聚节点一般应分散放置，以起到有效缓解大规模网络的分散控制和汇聚节点有效冗余的作用。根据汇聚节点的布放位置和影响程度来考虑，主要有以下几种：
（1） 相邻关系。两个汇聚节点位于监控区域一侧的相邻区域，在这两个汇聚节点之间区域的传感器节点都可以收到这两个汇聚节点之间的信号，它们会根据特定的算法选择汇聚节点。这类汇聚节点的位置安排，主要考虑到汇聚节点的冗余性，以及到汇聚节点路由的主备用安排。
摘 要： 为解决大规模无线传感器网络的节点通信效率问题，提出无线传感器网络的一种多汇聚节点分簇算法，针对拥有多个汇聚节点的监控区域，对网络进行层次化管理。算法通过对多种参数的综合考虑后产生簇头，并将传感器节点分配到相应的簇，由此可以有效降低节点的非均匀能耗，减少因能耗较大节点的能量过度衰竭而造成网络可用率下降。仿真结果显示，该算法可以延缓首个死亡节点的发生时间，并能有效延长无线传感器网络的整体可用率。
关键词： 无线传感器网络； 汇聚节点； 分簇算法； 能耗降低
中图分类号： TN711?34； TP393 文献标识码： A 文章编号： 1004?373X（2017）13?0026?04
Abstract： In order to solve the problem of node communication efficiency for large?scale wireless sensor network， a multiple sink nodes based clustering algorithm for wireless sensor network is presented. Aiming at the monitoring area with multiple sink nodes， the hierarchical management is performed for the network. The various parameters are considered comprehensively in the algorithm to generate the cluster head， and sensor nodes are distributed to the corresponding clusters to reduce the uneven energy consumption of the nodes， and avoid the network availability decline caused by the excessive energy exhaustion of the nodes with large energy consumption. The simulation results show that the algorithm can delay the occurrence time of the first death node， and prolong the overall availability of the wireless sensor network effectively.
Keywords： wireless sensor network； sink node； clustering algorithm； energy consumption reduction
0 引 言
无线传感器网络是通信网络与传感器技术的融合产物，广泛应用于工业、农业、军事、医疗等多种领域[1]。随着现代科技的不断进步，传感器的集成度越来越高，尺寸越来越小，成本也不断降低[2]，这也为大规模、低成本地使用传感器进行组网应用带来了契机。
大规模无线传感器网络[3]的使用带来了一些新的问题。例如，如何管理大片区域的大量传感器节点[4]，如何避免某些区域的传感器因能量消耗过大而提早失去功能[5]，如何实现有效的动态路由选择等。采用分簇算法对网络进行分层管理可以有效解决上述问题[6]，并提升整个无线传感器网络的性能。
早期较为成熟的无线传感器网络分簇算法是LEACH算法[7]。该算法随机产生簇头，并将各个传感器节点按照距离因素分配到邻近簇头，并周期性进行簇头资格轮换，从而实现良好的分簇效果。HEED算法[8]是对LEACH算法的改进。该算法以节点的剩余能量为依据，按照一定概率产生簇头。此外，还有一些算法在此基础上做了进一步的优化[9]，或者采用以地理位置等多种因素进行分簇的方法[10]。
上述这些算法绝大部分都是以单个汇聚节点为基础，实现有中央控制的层次型网络管理。在实际应用中，当网络规模较大，覆盖面积也较广时，采取多个汇聚节点对网络进行控制和管理[11]，是一种有效的手段。多匯聚节点下的无线传感器网络的管理，不应该简单采用将单汇聚节点网络进行拼接的方式。因为这样做会造成区域之间的割裂；同时，区域的地理特性往往与无线通信环境并不完全一致，地理分区对无线通信的效率分配缺乏帮助；而在网络拓扑结构动态变化的情况下，简单分区无法对这一变化进行适应和调整。
基于多汇聚节点的算法设计，就是为了解决在大规模网络中使用单汇聚节点算法的不足。RDF算法[12]使用以节点位置为区分依据的栅格来划分传感器节点与汇聚节点的对应关系；HLBR算法[13]采用综合节点剩余能量和到汇聚节点距离因素的负载均衡算法来解决到汇聚节点的路径。然而这些算法的模型比较简单，适应于较少汇聚节点情况下的网络通信以及传感器节点动态变化情况较小的场景。
本文提出一种多汇聚节点环境下的无线传感器网络分簇算法，针对大规模无线传感器网络的特点实施层次化的网络管理。
1 多汇聚节点模型
对于大规模的无线传感器网络，使用多个汇聚节点，可以降低对单个汇聚节点发射功率的要求，也可解决因到单一汇聚节点的路由不可达[14]而导致的网络崩溃问题。
1.1 汇聚节点的位置
多个汇聚节点一般应分散放置，以起到有效缓解大规模网络的分散控制和汇聚节点有效冗余的作用。根据汇聚节点的布放位置和影响程度来考虑，主要有以下几种：
（1） 相邻关系。两个汇聚节点位于监控区域一侧的相邻区域，在这两个汇聚节点之间区域的传感器节点都可以收到这两个汇聚节点之间的信号，它们会根据特定的算法选择汇聚节点。这类汇聚节点的位置安排，主要考虑到汇聚节点的冗余性，以及到汇聚节点路由的主备用安排。
