基于能量均衡的无线传感网分簇拓扑算法研究(4)
根据具体模型、具体层次不同的研究需要和研究问题的侧重点不同，分簇算法可大致分为集中式/分布式算法、基于地理位置/地理位置无关算法、确定性/随机性算法、单层/多层算法以及簇内单跳/多跳算法等。从网络协议分层上看，分簇算法可以看做是拓扑控制的一大类，位于MAC层与网络层之间。在算法设计中，需要考虑网络连通性、簇头轮转频率、簇半径优化以及节点同步等一系列问题，对这些问题的深入研究可以从跨层设计的角度，结合MAC层、网络层甚至应用层进行。
目前，分簇拓扑控制研究【5】日新月异，已经形成功率控制和层次型拓扑结构组织，在功率控制机制方面，已经提出了COMPOW等统一功率分配算法，LINT、LILT和LMN/LMA等基于节点度的算法，CBTC、LMST、RNG、DRNG和DLSS等基于邻近图的近似算法。在层次型拓扑控制方面，提出了TopDisc分簇算法，改进的GAF虚拟地理网格分簇算法，以及LEACH和HEED等自组织分簇算法。新的分簇算法有RDCA分簇算法、基于RBF的分簇算法以及Hausdorff算法等。根据近年来分簇算法的发展趋势，更精确的仿真模型、异构网络的分簇算法、QoS性能等研究方向很值得我们去努力。另外，无线传感器网络作为一种与应用高度相关的网络，引入跨层设计机制，与MAC、网络层甚至应用层实现联合优化，进一步提高网络的容错性，降低冲突与干扰，与休眠/唤醒机制相结合，与网络覆盖、数据融合等问题联合考虑等，都是分簇算法需要进一步研究的课题。
2.1 无线传感器网络分簇架构
在采用分簇结构的无线传感器网络中，网络节点被划分为若干个簇。每个簇由多个成员节点和一个簇头节点组成。成员节点只与簇头通信，簇头与簇头构成高一级的虚拟骨干网，负责簇内的数据融合和簇间数据转发。因为簇头节点的能量消耗较大，通常采用周期性选择簇头节点的方法均衡网络中节点能量的消耗。簇头的集合形成连通统治集(CDS)，因为获得最优CDS是NPC问题，因此实际提出的算法均为启发式的。图4给出了分簇结构以及簇内与簇间的数据流向。
图4 分簇结构以及簇内与簇间的数据流向
无线传感器网络采用分簇结构具有以下优点：
(1) 在满足一定约束条件情况下(例如覆盖范围与采样精度要求等)，簇成员节点可以在某些时间段内关闭通信模块，大幅度减少空闲等待状况的能量消耗，因此可节省能量。
(2) 簇头通常负责采集簇成员发送来的数据，这些数据具有较大的相关性，因此可以采用数据融合算法，在保证信息量的情况下降低数据通信量，降低数据转发的能量开销。
(3) 因为采用层次结构，簇成员只需了解到所属簇头的路由信息，簇头只需了解簇头间的路由信息，因此可降低路由协议的复杂度，减少路由表项数目，路由文护开销也随之降低。
(4) 具有较好的可扩展性能，更加适合于大规模WSN的应用场景。
2.2分簇拓扑算法分类
2.2.1 集中式/分布式算法
根据是否存在一个中心控制节点(通常是基站)负责整个网络的簇划分，分簇算法可分为集中式与分布式两类。典型的集中式算法有LEACH-C、APTEEN等。中心控制节点通常有持续的电源供应、较高的存储与计算能力，并能获得网络的全局信息，比如每个节点的位置以及剩余能量等，因此可以采用复杂的算法获得优化的分簇结果。但是由于普通无线传感器节点能量有限，计算与通信能力不强，对于大型的无线传感器网络，集中式算法在灵活性、可扩展性以及健壮性等方面存在缺陷。
分布式算法与集中式算法不同，一般只需要相邻节点之间互相交换信息，甚至不考虑相邻节点独立作出判断，这类算法简单、高效、灵活，因此更适用于大规模无线传感器网络。大部分经典的无线传感器网络分簇算法如LEACH、HEED【6】等，都属于分布式算法，新的Hausdorff算法、响应式分布分簇算法等也属于这一类。
下一篇：贝叶斯波束形成算法研究+文献综述