复杂环境下基于连通支配集的无线虚拟骨干网构建研究

Wireless Virtual Backbone (WVB) is composed by a subset of communication nodes from a given Wireless Ad-Hoc Network. It takes charge of the global connectivity, routing, broadcasting, and packet forwarding of the whole network, in order to reduce the energy consumption and amount of forwarding nodes of the network. Applying WVB design, we can establish a powerful hierarchical infrastructure to wireless ad-hoc network to lower the possibility of congestion and interference, decrease maintenance cost, and improve the network performance. Many previous studies show that the Connected Dominating Set (CDS) is a best choice to construct a WVB. However, how to select an optimal CDS from a given network effectively is an NP-hard problem. In this project, we will study the WVB construction based on CDS in complicated environments with various new constraints (e.g., network with obstacles, shortest path constraints, and complex physical environment). Firstly, we will formulate the communication model and topology structure according to various service requests and different network environments, and then figure out the objective function. Secondly, we will design distributed polynomial time approximation algorithms, with performance analysis and approximation ratio discussions, and then provide numerical experiments and simulations to investigate the efficiency of our designs. Finally, we will summarize our mathematical model and algorithm designs, to induce a universal theory of virtual backbone construction which is applicable to most of the real-world applications. The results of this project will have important technological innovation and significant theoretical consultations to enhance the performance of the next generation wireless communication networks.

无线虚拟骨干网(WVB)是由给定无线自组织网络中的部分节点组成的骨干网络，负责全局连通、路由广播与分组转发，以此减少其余节点转发次数与网络耗能。通过这种机制可以对网络建立有效的层次拓扑结构，降低网络拥塞干扰、维护成本，并提高网络性能。研究表明，连通支配集（CDS）常为构建WVB的第一选择，然而如何快速选择最优CDS通常是NP难问题。本项目旨在讨论复杂环境下基于CDS的WVB构建（如多干扰、短步跳、复杂地貌等）。首先针对不同环境和用户需求设定抽象模型与拓扑结构，并制定目标函数；其次设计分布式多项式时间近似算法，分析算法的近似比与性能，并仿真试验对比结果；最后根据问题性质，将算法设计与网络模型进行归纳分类，最终形成一套适用于各种实际应用场景的普适性无线自组织网络虚拟骨干网构建理论，保证网络的高效运行，对新一代无线通信网络的虚拟骨干网构建有重要技术指导与理论参考价值。

近年来，无线自组织网络受到学术界和工业界的广泛关注，是计算机科学的研究热点和活跃领域。然而，无线自组织网络由于自身无基础设施、临时组网、平面式结构、动态网络拓扑等特点，在组网与通信时面临着诸如节点分布不合理、路由开销大、信息冲突严重、节点能量有限、网络寿命短等问题。为了解决这些问题，参照有线网络基础设施具有层次性、分级控制等特点，研究者们提出可以在无线自组织网络中构建无线虚拟骨干网（Wireless Virtual Backbone Network）,由此建立有效的层次拓扑结构，制订恰当的管理策略，在保持网络正常连通的条件下减少转发节点的数目和数据传输总量，降低拥塞和干扰的可能性，以提高网络性能、降低管理维护代价，达到快速路由和低能耗的效果。大量研究表明，网络图的连通支配集（Connected Dominating Set，CDS）通常是构建虚拟骨干网的第一选择。..本项目旨在针对复杂环境（如不同应用场景、不同网络构架、不同硬件设施）的无线自组织网络选择有效虚拟骨干网构建，以此帮助网络用户降低节点能耗，减少网络拥塞干扰，控制维护管理成本，提高网络性能，加速路由传输速度，并提供高质量的网络连通性覆盖，对保障网络高效稳定的运行有着重要理论与实践意义。通过对本项目所摄问题的探索和研究，根据问题性质将算法设计与网络模型进行归纳分类，最终可以形成一套适用于各种实际应用场景的无线自组织网络普适性虚拟骨干网构建理论。..本项目侧重理论分析，着眼点在于网络优化问题的模型构建与算法设计分析，力图自组织网络中的优化问题并提出有效解决方案，尤其对很多经典问题首次给出带有近似比的近似算法设计，对问题难度和算法效率给出有效科学评估，本项目的研究成果对求解无线自组织网络相关优化问题有重要理论指导意义与技术参考价值，促进组合优化与无线网络领域的学科交叉，能够为相关领域的工作者提供有效科学与技术工具。..项目执行期间共发表署国家自然科学基金资助论文35篇。研究成果在无线自组织网络分簇覆盖、分布式索引与数据获取方面取得突破性进展，在无线网络领域CCF A类期刊IEEE Transactions on Computers发表标注受本项目资助论文1篇；在理论计算机、数据工程领域国际著名期刊Theoretical Computer Science、GeoInformatica上发表标注本项目资助论文2篇。