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

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

项目编号： No.61202024

项目类型： 青年科学基金项目

立项/批准年度： 2013

项目学科： 计算机科学学科

项目作者： 高晓沨

作者单位： 上海交通大学

项目金额： 23万元

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

中文关键词： 无线自组织网络；虚拟骨干网；连通支配集；优化理论；

英文摘要： 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 s

英文关键词： wireless ad hoc network；virtual backbone；connected domineting set；optimization theory；