三维无线网络最小虚拟骨干近似算法ST-CDS

"本文提出了一种在三维无线自组织网络中构建最小虚拟骨干的近似算法ST-CDS，该算法基于单位球图（Unit Ball Graph, UBG）并优化连通控制集（Connected Dominating Set, CDS）。通过构造最小斯坦纳节点的斯坦纳树方法，ST-CDS算法旨在减少网络路由开销，提高网络性能。算法的性能比达到11.8080+ln11，为目前该领域最佳结果。文章还给出了单位球图中独立节点数目的最优上界，并利用此上界改进CDS的性能。此外，ST-CDS算法经过仿真验证了其可行性，并受到多项基金支持，包括国家自然科学基金和广西壮族自治区科学基金。通信作者为梁家荣教授。" 在无线自组织网络（Wireless Ad Hoc Network, WSN）中，虚拟骨干（Virtual Backbone, VB）是网络结构的重要组成部分，它对于网络的稳定性和效率起着关键作用。VB的大小直接影响网络的路由效率和能量消耗。当VB较小，路由开销降低，网络的整体性能提升。因此，寻找最小虚拟骨干（Minimum Virtual Backbone, MVB）成为了网络设计的关键问题。 MVB的求解可以转化为最小连通控制集问题（Minimum Connected Dominating Set, MCDS），即找到网络中最小的节点集合，使得这些节点覆盖整个网络并且它们之间相互连接。在二维无线自组织网络中，通常使用单位圆盘图（Unit Disk Graph, UDG）来抽象网络拓扑。然而，UDG并不总是能准确反映实际三维环境中的无线传播特性。因此，该文引入了单位球图（Unit Ball Graph, UBG）作为更精确的模型，尤其是在三维网络中。 ST-CDS算法是为了解决UBG中的MCDS问题而设计的。算法的核心思想是通过构建最小斯坦纳树（Steiner Tree with Minimum Number of Steiner Nodes）来优化节点间的连接，以达到最小化CDS的目的。斯坦纳树是一种特殊的树形结构，用于连接图中的一组特定节点（终端节点），同时尽可能减少额外添加的中间节点（斯坦纳节点）的数量。 该算法首先确定一个最优上界来限制独立节点的数量，然后利用这个上界来构建CDS，从而改进网络性能。据分析，ST-CDS算法的性能比达到了11.8080+ln11，这是目前文献中报道的最好结果。此外，通过仿真验证，ST-CDS算法不仅理论上有效，而且在实际应用中也表现出良好的效果。 这项工作得到了国家自然科学基金和广西壮族自治区科学基金的资助，通信作者梁家荣教授是研究团队的负责人。该研究对于优化三维无线自组织网络的性能，特别是减少路由开销和提高网络效率具有重要的理论和实践意义。