随着微电子技术、低功耗嵌入式技术、无线通信技术以及分布式信息处理技术的飞速发展,无线传感器网络(WSN,Wireless Sensor Network)成为了当今科技的热点,被誉为第三次技术革命。无线传感器网络具有以下特点：有限的节点能量、无线自组织网络、低功耗低成本部署、以数据为中心和应用相关性。因此,针对不同的应用需求,开发相应的通信协议成为了当前研究的热点和难点。无线传感器网络路由协议大致分为平面路由协议和层次路由协议两种。本文通过分析几种经典的路由协议,如SPIN、LEACH和HEED等,归纳了它们的不足之处,提出了一种基于连通图的分簇路由协议CRPCG(Clustenng Routing Protocol Based on Connected Graph)。CRPCG协议主要是针对基于树结构的簇间多跳路由协议的不足而提出的。其基本思想是：在分簇协议的簇头选举、簇的形成和簇的路由等三个方面分别优化,最终形成一个由基站和所有簇头构成的连通图,利用图论中的相关优秀算法,均衡节点的能量和延长网络生存周期,同时保证整个网络的连通性和可靠性,提高了链路质量。协议在以下三个阶段做了改进：(1)在簇头选举和成员入簇阶段,综合考虑了节点的剩余能量、节点的密集度和通信代价,使簇头分布更加均匀,均衡了簇的规模和能量消耗;(2)在簇的形成阶段,由基站和所有簇头形成连通图,解决了树结构的局限性和本质上的缺陷,而又不失采用树结构时数据传输的高效性,即使局部簇头失效,仍然可以保证其它簇头和基站的连通性;(3)在数据传输阶段,由于构成连通图时的巧妙设计,保证了簇内和簇间数据传输基本上采用自用空间能量模型,有效地降低了传输时能量的损耗,可以基于实际需求选择不同的传输路径到基站,保证了数据传输的可靠性,同时进一步均衡簇头间的能量消耗。仿真实验表明,CRPCG协议相比LEACH协议可以明显的延长网络生存时间,均衡网络节点的能量。尤其是在簇间数据传输时,提高了数据传输的可靠性和时效性,还可以防止网络局部失效,显著地克服了Leach和簇间树路由结构上的缺陷。