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 和自己的度决定是否可以成为簇头：
①节点的剩余能量若小于能量阈值(Eresidual②节点的剩余能量大于等于能量阈值(Eresidual>=Ethreshold)，则将自己变为粉红色，即表示是候选簇头，此时可能会有多个节点成为候选簇头节点，以最大度的粉红色节点作为簇头节点，则具有最大度的节点将自己变为红色，其他粉红色节点保持不变，依然是候选簇头节点。
具体过程是粉红色节点集中的任一节点v Set( pink) k i "?+向自己的邻居广播成为候选簇头的消息，在节点vk+i 通信范围rc 内的所有节点(包括其他粉红色节点)给出应答消息，粉红色节点vk+i 根据应答消息计算出自己节点的度deg( ) k i v +，若deg(v ) max{degv | v Set( pink)} k i x x =?+，则该节点vk+i 将自己变为红色，记下其他粉红色节点的度，并向邻居节点宣布正式成为簇头，簇头向邻居节点广播成簇消息Request，消息中包含簇的编号CID(Cluster ID)，收到消息的邻居节点加入该簇，并记下簇头的编号CID，其他粉红色节点保持自己的颜色，为接替现有簇头做准备，则此时簇中的成员有三种颜色：红色的簇头、粉红色的候选簇头、白色的一般成员节点。假设节点vi 收到了CFM 消息，则根据下面的算法来决定是否可以成为簇头。产生簇头的算法描叙：
If (Eresidual>=Ethreshold)节点vi 变成粉红色;计算 deg(vi);If (deg(vi)是最大度){ 节点vi 变成红色;宣布成为正式簇头}
Else {节点vi 依然粉红色，成为候选簇头}
endifElse (Eresidual{节点vi 保持白色不变}
Endif2.3 产生簇发言人CFM 消息继续扩散，用同样的算法产生下一个簇头，当该簇头向自己的邻居节点广播成簇消息Request，收到此消息的节点分两种情况来讨论：
① 该邻居节点是第一次收到 Request，则选择加入到该簇，并记下簇编号CID;若该节点的邻居节点中的某个或者某几节点是另外簇的簇成员，则该节点将自己变为灰色节点，表示自己是候选簇发言人，否则保持白色不变。
② 该邻居已经收到过成簇消息 Request，是另外某个簇中的白色节点，拒绝加入该簇，但将自己变为灰色节点，成为候选簇发言人。
定义 6 绿色节点对：同一路径上的绿色节点，即同一路径上的簇发言人，称为绿色节点对。如图1 所示，节点A 和节点B 就是绿色节点对。定义 7 灰色节点对：同一路径上的灰色节点，即同一路径上的候选簇发言人，称为灰色节点对。
簇头根据灰色节点距离自己的远近(可以根据信号的强弱来判断)，选取其中距离自己最近的某个灰色节点作为自己的发言人，将其变为绿色，绿色节点向自己的邻居宣布正式成为发言人的消息CSNMsg (cluster speaker node message),消息中包含自己的CID 号，能收到绿色节点消息的邻居分为三类：红色节点、灰色节点、绿色节点。
若是红色节点，则为簇头节点，此簇头节点记下该绿色节点的相关信息;若是绿色节点，则该绿色节点和它的邻居节点构成绿色节点对，则记下该节点的信息;若是灰色节点，表示两个簇头选择的发言人不是绿色节点对，则灰色节点会比较自己的CID 和绿色节点的CID，若绿色节点的CID 大于灰色节点的CID，灰色节点保持不变;若绿色节点的CID 小于灰色节点的CID，则灰色节点将自己变成绿色，同时将该消息通知给自己的簇头节点，若该簇中没有其他的绿色节点，则簇头记下该绿色节点的信息，若该簇内已产生绿色节点，绿色节点查看自己的邻居节点是否也有绿色节点，也就是能否构成绿色节点对，若有，则保持绿色，否则变为灰色。
2.4 算法成簇状态分析按 CRBFCL 算法成簇，得到的簇是三种形式，分别如图2(a),2(b), 2(c)所示，其中X 是红色节点间的距离，即为簇头间的距离，由图可见，所形成的簇无交叉，这样形成的簇数量不是很大，并且簇头均匀。CRBFCL 算法在成簇时，一旦簇头确定，加入到该簇中的节点均为簇头通信范围内的节点，一个节点如果已加入某个簇，即使它也在另一个簇头的通信范围内，也不会响应另一簇头的请求。所以，簇内的节点具有100%的忠诚度，则两个簇，或两个以上的簇之间没有交叉重叠的节点，两个簇头间的最近距离如图2(a)中所示是2rc，两个簇头间的最大距离是图2(c)所示的3rc，一般簇头之间的距离为2rc定理 1 CRBFCL 算法得到的分簇是对传感器网络的覆盖也是划分。
证明：根据前面的假设，传感器网络G=，|V|=n，若CRBFCL 将传感器网络分为非空的S个簇，S S S S m n按CRBFCL 的成簇方式，任意节点或者是簇头，或者是簇成员，因为分簇前的网络是连通的，分簇后每个节点依然与自己的邻居节点保持着分簇前的邻居关系，所以不存在孤立节点，没有一个节点既不是簇头节点也不是簇成员节点。
即： v V v S v S v V i n j m，则每个节点必属于某个簇，所以S V，则簇集合S 是节点集合V 的覆盖。
又因为 CRBFCL 中节点对簇头的忠诚度是100%，没有一个节点同时是两个或两个以上簇的簇成员节点，任意两个簇都没有交集，即S S , (i j) i j ?=f?，所以簇集合S是节点集合V 的划分。则CRBFCL 算法得到的分簇是对传感器网络的覆盖也是划分。证毕。定理 2 CRBFCL 算法得到的分簇不改变网络的连通性。
证明：由图2 可见，CRBFCL 算法得到的簇之间有三种位置关系，无论那种位置关系，簇头之间都可以通过一个或者两个簇发言人进行通信，簇成员节点都可以与自己的簇头节点进行通信，故网络仍然是连通的。证毕。
因为 CRBFCL 算法得到的簇覆盖传感器网络的所有节点，且分簇后的网络依然连通，所以在数据查询中的数据分发和查询结果的收集中没有盲点，也无盲区;又因簇与簇之间没有交叉重叠的节点，每一个簇都最大地覆盖感知区域的节点，所以对节点的数据转发进行了很好的抑制，从而可以大大地节省能量。
3 结论
CRBFCL 协议选择满足条件的最大度的节点作为簇头，可以最大限度
