WSN中面向数据收集的网络拓扑构造算法

Network Topology Construction Algorithm Oriented to Data Collection in WSN

针对现有无线传感器网络中数据收集延迟较大的问题,提出一种优化的网络拓扑构造算法用于实现数据收集。从给定网络全连通图中找到符合条件的k个顶点的子图,使得k个顶点间的距离平方和最小化,采用Hungarian方法进行边的约简,直到得到一棵生成树,构造分布式的网络拓扑以提高适应性,从而降低控制开销。理论分析和仿真结果表明,该算法在数据收集延迟以及网络生命周期等方面均优于传统的单链、单簇2跳,以及最小生成树等数据收集算法。

Aiming at the disadvantage of larger delay in existing data gathering methods, this paper proposes an optimal construction algorithm of network topology for data collection. The k subgraphs are found from the given connected graph of network, which minimizes the distance between the vertices, and then using the Hungarian method to achieve the reduction of edges in k subgraphs until obtainning a spanning tree. In order to reduce the control overhead, this paper also proposes a distributed algorithm for constructing the network topology, which improves the adaptability of algorithm in different scenes. Theoretical analysis and experimental results show that the performance of the method is superior to the traditional algorithms such as Single Chain（SC）, Single Cluster 2-Hop（SC2H）, and Minimum Spanning Tree（MST） in terms of the data collection delay and lifetime of network.