Ad Hoc传感器网络是一种具有大规模性、自组织性、无基础设施支持等特点的网络,能够应用于各个领域,具有重要的现实意义。该网络利用连通支配集作为虚拟网络骨干,以此来进行数据聚合和网络节点通信,实现网络的广播和路由。本文针对在Ad Hoc传感器网络中构建最小连通支配集进行了如下研究,通过分析现有算法,得出目前效果较好的求解连通支配集的方法是基于二阶段的方法,因此本文针对其求解过程的两个阶段提出了三种改进的算法。针对第一阶段——求解MIS(极大独立集)阶段,本文分析了现有的基于协同覆盖的最小连通支配集算法。该类算法的协同覆盖思想虽然可以使问题接近最优解,但也降低了覆盖效率。本文对此进行改进,采用新的支配点选择方案,优先从当前支配节点的三跳邻居中选择下一个支配节点,如果不存在,则从当前支配节点的两跳邻居中选择下一个支配节点,使覆盖尽可能少的存在交集,增大覆盖效率。针对第二阶段——斯坦纳树构建阶段,多数算法均采用贪心方式寻找斯坦纳节点,该类算法简单但容易陷入局部最优解。本文对此进行改进,在斯坦纳节点的选择上了进行了相应的权值处理同时加入了检测处理阶段,即检测是否存在冗余的节点。提出了两种改进的斯坦纳树构建算法——IK-ST算法和ML-ST算法。进一步降低了支配集的规模。仿真实验中,首先对比了IC-MIS算法和Rajiv Misra提出的算法,通过比较所求得的MIS的节点数目来衡量算法的优劣,接着通过IK-ST和ML-ST算法优化Rajiv Misra算法的斯坦纳树构建阶段,然后与其进行比较,通过比较得到的斯坦纳节点数目来衡量算法的优劣。结果显示本文提出的算法较先前的算法在优化支配集规模上有了很大的改善。