无线传感器网络(Wireless sensor network WSN)综合了多种前沿技术,有很多其他网络系统没有的优点：自组织性强,抗毁能力强以及灵巧便捷等。本文首先对无线传感器网络的基本知识给予介绍,关于无线传感器网络的概念、特点、体系结构以及一些主要的技术等；然后对一些现有的协议进行了分析对比,着重介绍关于图论的分簇式路由协议,分析了基于图论的分簇式路由协议的基本性能及其优点。本文提出了一种新的基于梯度的分簇式路由算法,该算法是在EAMCT_G (Energy-Aware Multilevel Clustering Tree with Gateway)算法基础上进行的改进。文中首先分析了EAMCT_G算法,该算法在选择簇头时,仅仅考虑以剩余能量作为依据,这样容易造成节点能量利用上的不均衡,以及簇头节点分布的不合理,使得某些节点过早的死亡而造成网络的利用率降低。文中以新的权值计算方式作为选择簇头的方法,并通过仿真验证改进后的权值在分簇上的优势。在运用图论中的极大独立集(MIS, minimal independent set)和极小支配集(MDS,minimal dominating set)进行分簇的基础上,在网络中加入了感知梯度,使得整个网络的路由更具有方向性和较高的效率,文中详细的描述了该算法的路由。本文运用NS2作为仿真工具对改进后的路由算法进行了性能上的仿真,与EAMCT G路由算法进行对比,在网络延时、丢包率、生命周期以及吞吐量上都有所改善。