无线多跳网络K中心问题研究及其拓展

Aiming at the problem of network performance degradation due to the increase of number of network hops in wireless multi-hop networks, the goal of this project is to optimize network topology structure by studying the key network node deployment method and topology optimization theory. The problem is abstracted as a basic K-centre science problem based on hops count. For the wireless multi-hop geometric K-center problem, a theory and method of equivalent network construction based on topology segmentation and maximum candidate subset is proposed,and the completeness of the theory is proved.The ubset of the candidate regions is identified by the arc scanning method, and the maximum candidate subsets are abstracted nodes and added to the original network to form the equivalent vertex K-center virtual network. For the virtual network, we propose the topology-based substitution theory and the multi-stage substitution algorithm, and eliminate some nodes that do not participate in the optimal solution competition, so as to obtain the smaller network size solution space equivalent to the original network. Then, the two problems of geometry K-center problem and vertex K-center problem are unified, and the unified framework and algorithm of problem solving are constructed. Finally, we put forward the preliminary idea and algorithm of parallel implementation of large-scale network for the proposed theory. The theory and method proposed in this project are suitable for other similar multi-hop network topology structure optimization, and can be extended to three-dimensional space, and can be used to guide the planning and deployment of smart city.

针对无线多跳网络中由于网络跳数增加导致网络性能下降问题，通过研究网络中关键节点部署方法和拓扑优化理论，以达到优化网络拓扑结构的目标。本项目将该问题抽象为基于跳数距离的K中心基础科学问题。对于无线多跳网络几何K中心问题，提出一种基于拓扑分割和极大备选区子集的等价网络构建理论和方法，并证明该理论完备性。通过弧线扫描方法识别和归并备选区子集，将极大备选区子集抽象为节点加入到原始网络中，形成等价的节点K中心虚拟网络；对于虚拟网络，本项目提出基于拓扑学的替代原理和多阶替代算法，剔除一些不参与最优解竞争的节点，从而获得与原网络等价的更小网络规模问题求解空间；然后构建几何K中心和节点K中心两个问题统一的求解框架和算法；最后对所提理论和算法在大规模网络进行并行实现和验证提出初步设想。本项目所提理论和方法适用于类似的多跳网络拓扑结构优化，同时可以拓展到三维空间，并可用于指导智慧城市规划和建设。

针对无线多跳网络中由于网络跳数增加导致网络性能下降问题，通过研究网络中关键节点部署方法和拓扑优化理论，以达到优化网络拓扑结构的目标。本项目将该问题抽象为基础的科学问题：基于网络跳数的K中心问题。对于无线多跳网络无线几何K中心问题，本项目提出一种基于拓扑分割和极大备选区子集的等价网络构建理论和方法，并证明该理论完备性。通过弧线扫描方法识别和归并备选区子集，将极大备选区子集抽象为节点加入到原始网络中，形成等价的节点K中心虚拟网络；对于节点K中心虚拟网络或原始节点K中心网络，本项目提出基于拓扑学的替代原理和多阶替代算法，可以剔除一些不参与最优解竞争的节点，从而获得与原网络等价的更小网络规模问题求解空间；然后构建几何 K 中心和节点 K 中心两个问题统一的求解框架和算法；并对所提理论和算法在规模网络进行并行实现和验证提出初步设想。在此基础上进一步研究面向拓扑优化的智能算法理论和方法，提出改进的遗传算法、粒子群优化算法和差分进化算法。最后研究如何将这些方法应用在无线通信，传感器网络及物联网上,并且取得较好的效果。