网络拓扑控制是无线传感器网络的关键技术之一,用图论中的最小连通支配集思想在网络中组织一个虚拟的层次型骨干网络是实现拓扑控制一种常用的方式。而图论中的最小连通支配集问题是NP完全问题。在简单无向图上,求解最小连通支配集问题等效于求解最大叶节点生成树问题。本论文以邻近图结构为基础,提出一种基于环路上节点最小度的近似最大叶节点生成树MDRST(Minimum-Degree Related Spanning Tree)构建算法。该算法以节点度为邻居判定依据,通过删除原图中每条环路上最小度节点所在的一条边来构建多叶节点生成树。MDRST是集中式构建算法,其时间复杂性为O(N~2)。为实现分布式构建算法,论文在MDRST的基础上提出一种基于三角形和四边形环路上节点最小度的MDRSG(Minimum-Degree Related Spanning Graph)结构。MDRSG同样以节点度为邻居判定依据,但不消除原图中所有的环路,而只删除三角形和四边形环路上度最小节点所在的一条边。MDRSG需要节点一跳邻居的邻接表和二跳邻居节点度的信息,可以用具有多项式时间复杂度的分布式算法构建。论文将MDRSG应用于传感器网络的拓扑控制。为了克服MDRSG非平面性和没有考虑节点间边的权值的弱点,将MDRSG和相关邻居图RNG结合使用,实现了一种具有骨干网络的拓扑控制方法。方法首先用MDRSG生成连通支配集,再用RNG将支配集中的节点组成平面型骨干网络,而被支配节点选择离自己最近的支配点连接到骨干网络。这种拓扑结构既是层次型,又有平面性的特点,并具有局部调整性。