Ad hoc网络是由一组具有无线收发装置的移动节点组成的一个多跳临时性自治系统。网络中的每个移动终端是主机也是路由器,并根据路由算法参与路由的建立和分组转发工作。作为一种无中心、自组织的无线移动通信网络,由于其高效的自组织性,以及动态变换的网络拓扑结构和多跳转发技术,已被广泛运用于军事战场、事故突发现场等紧急环境。早期的Ad hoc网络由于规模较小,大多基于平面结构。其优点是结构简单,不需要维护,但同时也限制了网络规模的发展。为了提高网络的可扩展性,大型Ad hoc网络通常采用分级结构。网络被划分成若干个簇,每个簇由一个簇头和多个普通节点组成。分级结构的网络规模将不受限制,路由和控制开销较小。目前,寻求合理的分簇算法来减少维护簇结构所需的开销,保持簇结构的稳定性,已经成为分簇算法研究的热点。为了将分簇算法更好的应用于Ad hoc网络,本文将网络区域划分为网格,在网格基础上结合地理定位和网格分区策略提出了一种基于网格分区策略的多簇头Ad hoc网络分簇算法。其思想是根据地理位置信息将网络划分成网格,若干个网格为一个簇。规定网格中的某区域为簇头生成区,每个簇生成多个簇头。本文提出了一种新的分级结构的路由协议CBGP(Cluster Based on Grid)。CBGP主要由簇头的选举和节点的路由查找两方面构成。簇头的选举采用了传统的加权组合算法,选取了移动性小,节点的连接度大和剩余能量比较多的节点来担任簇头。路由查找方面,确定以源节点和目的节点为顶点的矩形区域为路由查找范围,并将路由查找分为簇内查找和簇间查找两种。这种基于分区的多簇头分簇算法,有效地避免了簇与簇之间的节点重叠,延长了网络的生存时间,减少了分簇的开销。本文将这种分簇算法与CBRP(Cluster Based on Routing Protocol)协议中的最小ID分簇算法进行了比较。数值仿真表明本文提出的基于分区策略的多簇头分簇算法比最小ID分簇算法在分簇的控制开销上要小。在此基础上,运用NS2仿真平台,构建了网络仿真环境,利用随机生成的移动节点在网络中进行分簇和路由转发。通过仿真分析,得出了CBGP的分簇开销和簇的生存时间优于CBRP。最后,本文给出了该算法中有待解决的问题和改进建议。