WSN中基于5色标记的分簇路由研究

    1 引言

    无线传感器网络中分簇路由协议将节点分成不同的等级，具有某种关联的网络节点组成簇，每个簇由一个簇头和多个簇内成员组成，低一级网络的簇头是高一级网络中的簇内成员，由最高层的簇头与基站BS 通信。国内外学者从不同的角度对分簇协议进行了研究[1-5]。从这些文献里可以看出传感器网络中的分簇协议都是围绕如何选择簇头、如何成簇、如何传输数据来考虑设计的。现有的大多数算法都只是在某一方面表现出较好的特性，例如有的算法能够较快地产生簇头和形成簇，有些算法支持节点的移动，有些算法具有较好的健壮性和扩展性。但还没有一种算法在各方面都平衡得很好，为此提出一种基于五色标记的分簇路由CRBFCL(Cluster Routing Based on Five Colors Label)。

　　2 五色标记成簇算法

    2.1 相关定义设无线传感器网络为 G=，是无向连通图，其中V 是节点集合，E 是边的集合，将传感器网络分为两种情形：初始状态(initial state)和成簇状态(cluster state)。用5 种颜色来描述网络中的节点状态，定义如下：

　　红色节点(red)：簇头节点(cluster header node)，若一个节点为某一个簇的簇头，则为红色节点。

　　粉红色节点(pink)：候选簇头节点(candidate cluster header node)，若节点是某个簇的候选簇头节点，则为粉红色节点。

　　绿色节点(green)：簇发言人(cluster spokesman node)，可以同时和两个或两个以上的簇交流信息的节点，则为绿色节点。

　　灰色节点(grey)：候选簇发言人(candidate cluster spokesman node)，可以同时和两个或两个以上的簇交流信息，但在本轮中没有被选为簇发言人的节点，则为灰色节点。

　　白色节点(white)：普通节点(general node)，某个簇里的一般节点，是除簇头、候选簇头、簇发言人、候选发言人以外的节点，用白色表示。

　　设节点的通信半径为 rc，感知半径为rs。为了说明成簇算法，定义如下：定义 1 邻居节点：若节点vi 在节点vj 的通信半径范围内，则节点vi 是节点vj 的邻居节点。记为： ( ) { | ( , ) } j i j i c adj v =v d v v ?r ，其中( , ) j i d v v 是节点vi和节点vj的距离。

　　定义 2 节点的度：节点vi的邻居节点数，称为节点vi的度。记为：deg( ) ( ) i i v =Uadj v 。

　　定义 3 最大度的节点：在某个范围内度数最大的节点。

　　定义 4 忠诚节点：只属于一个簇的节点，称为忠诚节点。

　　定义 5 覆盖与划分：若把一个集合A 分成若干个叫做分块的非空子集，使得A 中每个元素至少属于一个分块，那么这些分块的全体构成的集合叫做A 的一个覆盖。如果A 中每个元素属于且仅属于一个分块，那么这些分块的全体构成的集合称为A 的一个划分。i i ?2.2 选择簇头网络初始，所有节点均为白色节点，当有查询任务的时候，sink 节点向自己的邻居节点发出建簇消息CFM(cluster formation message)，消息中包含本轮中能够成为簇头节点的最低能量阈值Ethreshold，邻居节点根据自己的剩余能量Eresidual 和自己的度决定是否可以成为簇头：