无线传感器网络（Wireless Sensor Network,WSN）已广泛应用于工业、农业、科研、医药、军事等领域,构建自动化信息系统,有效实现实时采集数据,为用户提供有效真实的信息。WSN由大量微型无线传感器组成,具有传感器体积小,监控范围广、电池供电、自组织等特点。WSN节点部署环境复杂导致人工更换电池困难,若通信路由协议不合理,容易产生“热区”,“热区”内的节点能耗高,易产生“能量空洞”现象,最终严重缩短网络寿命,因此研究节能可靠的WSN路由协议,延长网络寿命,对WSN的应用和发展具有重要的理论和实践意义。本文针对WSN的“能量空洞”问题,将图论中的覆盖度、连通度应用到网络中,通过非均匀部署传感器节点,利用生成树模型描述网络及路由协议,提出2个非均匀分簇路由协议模型,采用启发式的A*算法寻找最优簇间路由,旨在延长网络寿命,均衡能耗。论文主要工作与创新如下:（1）研究了WSN及其相关路由协议,基于图论的相关知识,提出连通度和覆盖度的概念及其计算方式,并应用到路由协议的评价指标当中,设计了基于图论的非均匀网络部署模型;将图论中的生成树概念应用到网络中,在簇内建立末端树模型,在簇间建立主干树模型。（2）基于图论提出了一种面向小规模网络能耗均衡的启发式SHEBUC（Heuristic Energy Balance Uneven Clustering Protocol for Small-scale WSN）路由协议。根据非均匀网络部署模型部署节点,合理划分簇群位置,提出了自适应分区算法,根据实际节点分布情况划分簇群,控制通信能耗;选举簇首时提出了能量密度质心的概念,竞争函数包括候选簇首剩余能量、与能量密度质心距离、与簇内节点距离之和、与基站的距离4种要素,用末端树模型描述簇群结构,实现CH最优选择;在簇间选择中继节点时选用启发式的A*算法,以到达基站距离和最短为启发,寻找最优的中继节点。实验表明,本文提出的SHEBUC协议比AEBUC协议的网络寿命延长了17%,比EEUC协议延长了43%;能量均方差比AEBUC协议降低了20%,比EEUC协议降低了70%;有效延长了网络寿命,缓解了“热区”现象。（3）基于图论提出了一种面向大规模网络的LHEBUC（Heuristic Energy Balance Uneven Clustering Protocol for Large-scale WSN）协议。大规模网络相对于小规模网络节点通信距离大、节点密集、拓扑结构复杂,SHEBUC协议需进一步改进。采用非均匀部署节点,根据节点的最大通信距离确定分层数范围,通过实验仿真确定最优分层数,控制簇内通信能耗;在簇首选举算法和簇间路由选择算法中,将竞争函数中的物理距离优化为广义距离;在簇间路由选择阶段构建主干树模型,优化启发式A*算法,在代价函数中加入了候选中继节点的剩余能量及其所在簇群节点数。实验证明,LHEBUC协议的网络寿命相比SHEBUC协议延长了34%,比AEBUC协议延长了36%,比EEUC协议延长了94%,延长了网络寿命,均衡了节点能耗,实现了高连通、高覆盖。本论文有图50幅,表12个,参考文献82篇。