移动Ad Hoc网络由一组带有无线通信收发装置的移动终端节点组成、网络中每个终端可以自由移动、地位相等,是一个多跳、临时、无中心网络,不需要现有信息基础网络设施的支持,可在任何时候、任何地点快速构建。由于移动Ad Hoc网络可以在没有固定基础设施支持的条件下提供方便、灵活的通信,这大大拓宽了移动通信的应用领域,因此,该技术具有广阔的发展前景。移动Ad Hoc网络的拓扑结构可以分为平面结构和分层结构。在用户较多,特别是在移动性强的情况下,平面结构的移动Ad Hoc网络存在处理能力弱,控制开销大,路由经常出现中断等缺点,并且随着共享网络资源的用户个数不断增加,每个用户获得的吞吐量将急剧下降。为了降低网络成本,提供灵活可靠的通信并提高移动Ad Hoc网络的可扩展性,通常移动Ad Hoc网络采用分层结构。在分层结构中,网络通常被划分为簇。所谓簇,就是具有某种关联的网络节点集合。一个簇通常包含一个簇头节点与若干簇成员节点。分簇算法性能的优劣将对整个移动Ad Hoc网络的性能产生显著影响。首先,本文介绍了移动Ad Hoc网络的概念、特点和拓扑结构,概述了分簇结构与平面结构各自的优缺点,分类研究了几种典型的移动Ad Hoc网络分簇算法,论述了各种算法的优点和弊端。其次,详细介绍了涌现算法的概念和特征,随后分析了涌现算法在分簇和路由领域的应用,这些是本文研究工作的灵感源泉。最后,针对涌现分簇算法ACE迭代中存在的问题,本文引入概率机制,提出了基于概率机制的新分簇算法PACE。PACE算法根据节点竞争簇头概率最高的局部信息,创建全局分簇网络,在概率相同的情况下,根据节点标识符来仲裁簇头选举,同时,实现了单节点簇合并和失效恢复。理论分析和仿真结果表明,PACE算法收敛时间短,能够创建稳定且更优化的分簇结构,具备失效恢复能力。