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

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算法处理后，剩余能量较少的节点将不再担当骨干节点，有利于延长网络的生命周期，从而实现均衡耗能。