基于电量均衡的无线传感器网络分簇算法

　　引  言

　　无线传感器网络(Wireless Sensor Networks，WSN)是由任意散落在被监测区域内大量传感器节点以自组织形式构成的网络，并通过网络将监测数据传送到接收站进行处理。通过随机投放的方式，众多传感器节点被密集部署于监控区域。这些传感器节点集成有传感器、数据处理单元和通信模块，它们通过无线信道相连，自组织地构成网络系统。传感器节点间有良好的协作能力，通过局部的数据交换来完成全局任务。通过网关、传感器网络还可以连接到现有的网络设施上(如Internet、移动通信网络等)，从而将采集到的信息传回给远程的终端用户使用。随着微电子技术、通信技术和计算机技术的飞速发展，WSN在军事和民用各个领域都得到广泛应用，其应用潜力巨大，已成为目前通信领域的研究热点。

　　1 无线传感器网络的拓扑控制

　　WSN网络拓扑控制主要研究的问题是：在保证网络覆盖度和联通性的前提下，设置或调整节点的发射功率，并按照一定的原则选择合适的节点成为骨干节点，参与网络中数据的处理和传输，达到优化网络拓扑结构的目的，其首要的设计目标是通过高效使用能量使网络生命期最大化。

　　WSN中拓扑控制可以分为两个研究方向：功率控制和层次拓扑结构控制。功率控制机制调整网络中每个节点的发射功率，保证网络连通，在均衡节点中直接邻居数目(单跳可达邻居数目)的同时，降低节点之间的通信干扰。层次拓扑控制是利用分簇思想，使网络中的部分节点处于激活状态，成为簇头节点。由这些簇头节点构建一个连通的网络来处理和传输网络中的数据，并定期或不定期地重新选择簇头节点，以均衡网络中节点的能量消耗。

　　WSN中，节点的无线通信模块处于发送状态下功耗最高，接收状态和空闲状态下功耗次之，休眠状态下功耗最低。例如，目前用于WSN的主流传感器Berkeley Motes，其通信模块处于发送状态的功耗为60 mW，接收状态和空闲状态的功耗均为12 mW，休眠状态的功耗为0.03 mW，其功耗比达到2 000：400：1，因此降低能耗的关键是降低网络内的通信流量，使更多的节点在更长时间段处于休眠状态。为了大幅度降低无线通信模块的能量消耗，可以考虑依据一定的机制选择部分节点作为骨干节点，这些节点的通信模块处于打开状态，而其他非骨干节点的通信模块处于关闭。在这种机制下，节点被分为骨干节点和非骨干节点两类，骨干节点对非骨干节点进行管辖。这类算法将网络分为相连的区域，称为分簇算法。

　　在层次拓扑控制方面，已经提出的算法有Deb的TopDisc(Topology Discory)拓扑发现算法、Santi的改进GAF(Geographical Adaptive Fidelity)分簇算法、Heinzelman的LEACH(LOW Energy AdaptiveChlstering Hierarchy)算法和Younis的HEED算法等。

　　在此，以经典的基于最小支配集理论TopDisc算法为研究对象。通过考虑节点电量的剩余情况，得到Power-balanced TopDisc算法。该算法将节点剩余能量作为分簇结构的构建依据，对剩余能量较少的节点赋予一定的约束，使之成为普通节点，从而均衡网络电量负载，解决网络中部分低电量节点担任骨干节点而导致的能耗问题，有效延长网络生命期。仿真实验结果证明了该算法的有效性。

　　2  TopDisc算法

　　在TopDisc算法中，首先由初始节点发出拓扑发现请求，通过广播该请求消息来确定网络中的骨干节点，并结合这些骨干节点中邻居节点的信息形成网络拓扑的近似拓扑。在这个近似拓扑形成以后，为了减小算法本身引起的网络通信量，只有骨干节点才对初始节点的拓扑发现请求作出相应的响应。

　　为了确定网络中的骨干节点，TopDisc算法采用的是贪婪算法。具体分为两种类型：三色法和四色法。
　
　　2.1 三色法

　　在三色算法中，节点可以处于三种不同状态。在TopDisc算法中，分别用白色、黑色、灰色三种颜色表示：

　　(1)白色是尚未被发现的节点，或者说是没有接收到任何拓扑发现请求的节点；

　　(2)黑色是骨干节点(簇头节点)，负责响应拓扑发现请求；

　　(3)灰色是普通节点，至少被一个标记为黑色的节点覆盖，即黑色节点的邻居节点。

　　在开始阶段，所有节点都被标记为白色，算法由一个初始节点发起，算法结束后所有节点都将被标记为黑色或者灰色(假设整个网络拓扑是连通的)。Top-Disc使用两种启发式方法，使得每个新的黑色节点都尽可能多地覆盖还没有被覆盖到的节点：一种是节点颜色标记方法；另一种是节点转发拓扑发现请求时会故意延时一段时间，延时时间的长度反比于该节点与发送拓扑发现请求到该节点之间的距离。具体算法过程如下：

　　(1)初始节点被标记为黑色，并向网络广播拓扑发现请求；

　　(2)当白色节点收到来自黑色节点的拓扑发现请求时，将被标记为灰色，并在延时时间tWB后继续广播拓扑发现请求。tWB反比于它与黑色节点之间的距离。

　　(3)当白色节点收到来自灰色节点的拓扑发现请求时，将在等待时间tWG后标记为黑色，但如果在等待期间，又收到来自黑色节点的拓扑发现请求时，则优先标记为灰色；同样，等待时间反比于该白色节点与灰色节点之间的距离。不管节点被标记为灰色还是黑色，都将在完成颜色标记之后继续广播拓扑发现请求；

　　(4)所有已经被标记为黑色或者灰色的节点，都将忽略其他节点的拓扑发现请求。

　　为了使每个新的黑色节点都尽可能多地覆盖还没有被覆盖的节点，TopDisc采用反比于节点之间距离的转发延时机制。理想情况下，节点的覆盖范围是半径为无线电发射半径的圆。于是，单个节点所能够覆盖的节点数目正比于其覆盖面积和局部节点部署密度。对于一个正在转发拓扑发现请求的节点，它所能够覆盖的新节点(还没有被任何节点覆盖)则正比于它的覆盖面积与已经覆盖的面积之差。