田 勇， 唐 祯 安

（1.大连理工大学 电子科学与技术学院，辽宁 大连 116024；2.大连东软信息学院 嵌入式系统工程系，辽宁 大连 116024）

0 引 言

分簇路由协议是目前无线传感器网络（wireless sensor network，WSN）研究的热点之一，这类协议首先根据某种规则把WSN节点集划分为多个子集，每个子集成为一个簇，具有一个簇头[1].分簇路由协议中如何选取簇头是最关键问题之一，根据簇头选取方式的不同，可以把分簇路由协议分为分布式和集中式两种[2].分布式路由协议包括两类：一类是节点根据某个阈值决定是 否 当 选 为 簇 头，如 LEACH （low－energy adaptive clustering hierarchy）协议[3]就是这类分布式协议，它是由节点根据随机数自主决定是否当选为簇头，每轮产生的簇头没有确定的数量和位置；另一类是通过节点之间的信息交互产生簇头，如 HEED（hybrid energy－efficient distributed clustering）协议[4]和 HEED－M 协议[5].HEED协议将节点最大剩余能量和平均最小可达能量作为选择簇头的参数，以便簇内通信代价达到最小，但是此协议为了达到簇内通信代价最小的目的可能多次进行消息迭代，使得通信开销显著增加.HEED－M协议与HEED协议的唯一区别就是HEED协议使用单跳通信的方式，而HEED－M协议使用多跳通信的方式.集中式路由协议是指由基站基于整个网络信息进行簇拓扑结构的划分，被建模为带有特定限制的图形划分问题，现已证明是NP问题[6].文献[7]提出了一种集中式路由协议LEACH－C（LEACH－centralized）.这类协议的主要缺点是每个节点必须向基站传送地理位置和剩余能量信息，增加了额外的能量开销.

近年来，随着 WSN路由协议……