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

拓扑发现请求时，将被标记为灰色，并在延时时间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)为