移动自组网(MANET, Mobile Ad Hoc Networks)是由一组带有无线收发装置的移动节点组成的一个多跳的临时性无中心网络。MANET的网络层所涉及到的难题包括:拓扑控制(topology control),数据通信(data communication)和服务访问(service access)。路由是MANET数据通信的难题之一,主要涉及路径发现(route discovery)和包转发(packet forwarding)。 基于连通支配集(CDS, Connected Dominating Sets)的路由策略,是一个分层路由方法,可以将MANET的路由简化到CDS生成的较小的子网中,从而减少通信路径上的节点数目,提高路由效率并降低路径失效的概率,提高整个网络的性能。目前基于CDS的路由策略已经成为国际上的研究热点。 本文对MANET的路由策略进行研究,着重研究构造MANET的CDS并对其进行优化,提出了两个算法:支持双向链路(bi-directional link)的最小支配集构造算法和支持单向链路(unidirectional link)的最小支配集构造算法。上述算法充分考虑各节点的能耗并优先选择储能大的节点担任网关节点,以有效减小通信路径失效的概率,降低数据包的转发时延,降低网络管理的代价。实验结果表明:算法均能有效地将MANET简化到一个较小的CDS。