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

0 引  言

     无线传感器网络(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采用反比于节点之间距离的转发延时机制。理想情况下，节点的覆盖范围是半径为无线电发射半径的圆。于是，单个节点所能够覆盖的节点数目正比于其覆盖面积和局部节点部署密度。对于一个正在转发拓扑发现请求的节点，它所能够覆盖的新节点(还没有被任何节点覆盖)则正比于它的覆盖面积与已经覆盖的面积之差。

2.2 四色法

为了增大簇之间的间隔，减少重叠区域，TopDisc算法还提出了四色法。节点可以处于四种不同的状态，分别用白色、黑色、灰色和深灰色表示。前三种颜色代表的含义与三色法相同，增加的深灰色表示节点收到过拓扑发现请求，但不被任何标记为黑色的节点覆盖。

在初始阶段，所有节点被标记为白色，算法由一个初始节点发起，算法结束后所有节点都将被标记为黑色或灰色(假设整个网络拓扑是连通的，注意最终没有标记为深灰色的节点)。详细过程描述如下：

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

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

(3)当白色节点收到来自灰色节点的拓扑发现请求时，将标记为深灰色并继续广播拓扑发现请求，然后等待一段时间tWG(同样与距离成反比)。如果在等待期间收到来自黑色节点的拓扑发现请求时，则改变为灰色，否则它自己成为黑色；

(4)当白色节点收到来自深灰色节点的拓扑发现请求时，等待一段时间(同样与距离成反比)。如果在等待期间，收到来自黑色节点的拓扑发现请求时，则改变为灰色，否则它自己变为黑色，并广播拓扑发现请求；

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

与三色法相比，四色法形成的簇数目更少，簇与簇之间的重叠区域也更小。但是可能形成一些孤立的标记为黑色的节点不覆盖任何灰色节点。虽然三色法和四色法形成的黑色节点数目相当，但四色法中传输的数据量要少一些。

TopDisc算法利用图论中的经典算法，提出了一种有效方法来构建网络的近似拓扑，是分簇算法中的经典算法。它是一种只需要利用局部信息，且完全分布时可扩展的网络拓扑控制算法。但也存在需要改进的地方，如算法开销偏大；没有考虑节点剩余电量的信息。

3 Power-balanced TopDisc算法

WSN中节点转发数据的耗能模型如下所述。

传感器节点发射r比特数据包所消耗的能量为：

Pt(r，d)=r(a1+a2dn)    (1)

式中：d为两节点之间的距离；a1是与距离无关的量，包括发射电路所耗能量等；a2是与距离有关的量；n为路径损耗指数，通常取2～4之间。

传感器节点接收r比特数据包所消耗的能量为：

Pr(r)=rβ    (2)

式中：β卢为接收能量系数。

传感器节点将2个数据流r1和r2融合成一个数据包r的耗能为：

Pa(r1+r2，r)=r(r1+r2-r)    (3)

式中：r为数据融合系数。

从式(1)～式(3)可以看出，若剩余能量较少的节点仍然承担着较重的转发任务，那么就很可能导致该节点过早死亡，从而影响网络生命时间的延续。所以，在构建无线传感器网络拓扑时，节点应选择剩余能量多的节点作为数据转发的主要节点，而剩余能量较少的节点作为数据源节点，这样将有效解决由于负载过大而过早死亡的问题。

为便于描述和分析，作如下假设：

(1)每个节点都具有相同的最大发射功率，其覆盖范围是半径为R的圆形区域，且可通过调节发射功率以适应其覆盖范围内不同距离节点的通信；

(2)每个节点都能够获得自身的剩余能量，有一定的存储空间来存放邻居节点信息；

(3)忽略真实环境中存在障碍物等影响通信质量的因素，确保所有的数据包都能够可靠传输。

考虑节点电量均衡因素，在TopDisc四色法的步骤(3)中，对tWG进行修正，公式为：

twG=a1／d+a2／p    (4)

式中：d为节点之间的距离；p为当前节点剩余的电量；a1和a2为预设参数。对tWG进行修正后得到Power-balanced TopDise算法。

Power-balanced TopDise算法的合理性可以由图1说明。图1(a)为TopDisc算法的分簇结果；图1(b)为Power-balanced TopDise算法的分簇结果。其中，电量为80的节点为初始节点。初始节点发出拓扑发现请求到电量为20的节点变为灰色，并继续广播拓扑发现请求。电量为30和90的节点同时收到拓扑发现请求。在Power-balanced TopDisc算法中，电量为90的节点先于电量为30的节点变为黑色，即成为骨干节点(簇头节点)。

经过上述基于电量均衡的Power-balanced TopDisc算法处理后，剩余能量较少的节点将不再担当骨干节点，有利于延长网络的生命周期，从而实现均衡耗能。

4 性能分析和实验

为评估Power-balanced TopDise算法的性能，采用软件进行多次仿真试验，以所获得的分簇结构作为主要性能指标，并与TopDisc算法进行比较。

仿真模拟配置如下：假设有400个节点随机地部署在一个400×400的正方形平面区域内；每个节点的剩余能量为1～100的随机值。由TopDisc算法和Power-balanced TopDisc算法所生成的分簇结构分别如图2和图3所示。

对于该WSN，TopDisc算法得到的分簇结果是骨干节点平均电量为51；Power-balanced TopDisc算法得到的分簇结果是骨干节点平均电量为56。由于Power-balanced TopDisc算法生成的分簇结构考虑了节点的剩余电量，因而它使得剩余能量较少的节点成为普通节点，节省了担当骨干节点耗费的能量，从而延长了整个网络的生命周期。

5  结  语

在此，提出一种基于电量均衡的Power-balancedTopDisc算法，该算法考虑了节点中剩余电量的多少，对节点赋予一定的约束，让剩余能量较多的节点担当骨干节点，承担数据转发任务，保证了低电量节点不会因转发过多数据而过早失效，从而延长整个网络的生命期，实验结果证明了该算法的有效性。