一种基于正六边形分簇的WSN拓扑控制研究

邹汪平

（池州职业技术学院，安徽池州 247000）

低成本的小型嵌入式设备构成的WSN中传感器由电池供电且节点运算和通讯能力受其限制。良好的网络拓扑结构不仅可以提高路由协议的效率，还可以为时间的同步、目标的定位以及数据的融合提供良好的保障，从而延长网络的生命周期[1]。

1 研究背景

路由算法因WSN的特殊性结构和其管理的逻辑结构的不同而有所不同。从现有的平面路由和层次路来看，前者可均匀分布网络流量，易于算法的实现，但其由于扩展性问题制约了网络规模，而后者因为扩展性好而具有更佳的通信效果。

传统的LEACH算法是通过更均匀的分簇、更合理的簇首节点以及中继节点的设置来达到增强WSN的通信能力的目的[2]。在此基础上提出LEACH-H，一种基于正六边形分簇的WSN拓扑控制研究的算法。该算法旨在基于正六边形分簇提出一种WSN拓扑控制机制，从而使得分簇均匀，簇首节点在选择上更接近簇中心以及剩余能量更多的节点，转发数据的节点能够独立与簇首节点以及簇内其他节点进行远距离通信，在能量利用率方面得到明显的改善，网络的生命周期得到延续，网络的吞吐量得到提高。

2 算法改进

使用正六边形分簇在同一矩形检测区域上进行划分与使用等面积长正方形分簇以及等面积圆形分簇相比较发现，功率覆盖上正六边形分簇与圆形分簇最接近但却不存在缝隙和重叠，分簇产生的子区域个数上正六边形分簇比正方形分簇要少得多。因此，采用正六边形分簇，在传感器节点传输距离确定的前提条件下，可以使用比其他分簇方式更少的传感器节点来覆盖整个监测区域，因此在等面积的正六边形分簇与正方形分簇相比，簇内通讯能耗更低。

考虑到正六边形分簇区域内节点分布均匀并且这些节点的能耗与簇首节点的距离存在正比例关系，所以正六边形中心即为簇首节点的位置，并且这个中心位置设计不断变化才能够使得通讯能耗尽可能低。因此，可以将BS节点（基站节点）的坐标位置(Xbs,Ybs)修改成(Xbs+offset_x，Ybs+offsset_y)，使得中心在不断地随机变化，而offset_x和offset_y是0-正六边形半径r之间的随机数。这种设置有利于整个网络的负载均衡。分簇后的区域中心节点距离任意簇内节点P(x,y)的距离为dp，则：

由此可知，在传感器节点坐标、BS节点坐标、随机的偏移量值以及分簇后的子区域边长这4个因素确定的情况下就可以得到传感器节点隶属的簇、簇的中心节点坐标以及该节点与中心节点的距离。

在LEACH-H的簇首节点的选择机制设计中，若任意节点i与簇中心相距di，初始能量和生育能量分别为Emax和Eremain，区域中心与节点的最大距离为r，则可以得到一般节点能够成为簇首节点的优先权Pi是：

簇首节点的位置和能量由公式中p的取值决定，根据经验为0.68[3]。

在拓扑结构的建立过程中首先考虑的就是筛选簇首节点。在此过程中，剩余能量较大且距离分簇的中心节点较近的节点都需要优先考虑。在筛选时固定的分簇中心致使能够被筛选为簇首节点的节点总是位于分簇中心，这样单一的生成方式导致整个网络负载不均衡，因此考虑分簇中心应该在偏移量的作用下不断发生改变。由于偏移量在每个簇首节点的生命周期开始时均随机生成并通过BS节点以广播的方式发送到分簇内的每一个节点，因此接收到该广播的偏移量信息后，每个节点都可以根据以上描述的机制生成自身所属分簇以及自身被筛选为簇首节点和中继节点的优先权值。利用LEACH-H算法可以在所有网络节点计算出自身所属分簇时向该分簇以广播形式发送其被筛选为簇首节点和中继节点的优先权值。在分簇子区域较小的前提条件下，各节点广播的能耗也较小，在分簇内部那些距离分簇中心越近能量越大的节点很快就能被确定下来。如果在同一分簇内的某节点接收到其他节点的广播后发现自身的优先权值更大，则需要再次以广播的形式告知簇内其他节点，该步骤一直循环直到不再有节点广播为止，这时簇首节点被确定，该节点具备的能量最大，距离分簇中心最近的特点。一旦分簇内的簇首节点生成，分簇内的其他节点便会同时向簇首节点发出信息以加入该簇。在分簇内的那些距离上与BS节点越近且剩余能量越大的节点成为簇内中继节点的优先权限越大，被筛选为中继节点的可能性越高。簇首节点在接收完所有剩余节点的入簇信息后可以直接判定出能够筛选出优先权限最高的节点为中继节点。一旦簇首节点与中继节点被筛选出来，整个分簇网络也就进入了相对稳定的传输阶段。

在LEACH-H算法中由于引入了中继节点，因此分簇内的成员节点在中继节点的作用下以多跳方式将数据信息传递给BS节点之后最终到达簇首节点。该算法与经典的LEACH算法相比，由于簇首节点通信距离更近能耗更低生命周期更长的特点，使得在大范围WSN中可以更明显地延长整个网络的生命周期。

3 仿真及分析

将LEACH-H算法与LEACH算法从网络生命周期、节点总能耗和网络吞吐量3个方面在仿真环境NS2中进行仿真比较与分析。设计实验环境：簇的区域边长r设定为200，在400*400的区域内部署400个传感器节点，并设置BS节点的坐标为(65,485)，实验结果如下：

图1 生存节点随时间变化曲线

图2 节点的总能耗随时间变化曲线

图3 网络总吞吐量随时间变化曲线

实验结果表明，LEACH-H算法开始产生死亡节点的时间比LEACH算法更晚，并由于中继节点的作用使得簇首节点的通信负荷得以减轻，与此同时考虑各节点的剩余能量以均衡整个网络负载。网络生命周期上LEACH-H也占有明显优势。LEACH-H算法下网络的节点的总能耗与LEACH算法相比大幅降低，从而使得LEACH-H算法下网络的吞吐量也得到相应的提高。

4 结语

LEACH-H算法通过使用正六边形的分簇形式使得分簇更均匀，簇首节点的生成机制同时得以改进并引入中继节点降低通信负荷。在NS2仿真环境下实验证明，通过使用LEACH-H算法可充分降低节点能耗，延长网络生命周期和提高网络吞吐量。笔者认为LEACH-H算法不仅提出了一种新的分簇方式，为实际研究工作提供有力的数据支持，也为以后的研究工作提供数据参考。

[1]刘运杰,金明录,崔承毅.基于RSSI的无线传感器网络修正加权质心定位算法[J].传感技术学报,2010(5):717-721.

[2]朱智辉.网络化测试中WSN的设计与路由协议的研究[D].秦皇岛:燕山大学,2011.

[3]李德英,陈文萍,霍瑞龙,等.无线传感器网络能量高效综述[J].计算机科学,2008(11):8-12,35.