基于代数连通度的虚拟骨干网构造方法

Virtual Backbone Network Construction Based on Algebraic Connectivity

随着无线传感器网络的大量运用,通过分级将网络规模缩小显得十分必要。与已有的一些无线传感器网络的分簇算法不同,本文旨在构造一个健壮的、稳定的虚拟骨干网。通过引入图论中的代数连通度,并考虑无线传感器网络的信道特性,使用基于连接概率的代数连通度来表征虚拟骨干网的健壮性。同时提出度量参数网络质量,结合考虑骨干网的健壮性与代价,通过调节参数因子进行健壮性与代价因素之间的权衡。对该网络优化问题,提出集中式算法进行求解,并通过仿真得到健壮的虚拟骨干网。

With the development of Wireless Sensor Networks（WSN）, it is necessary to diminish the network scale by using hierarchical cluster networks. This paper aims to construct a robust and stable virtual backbone network in WSN, which is different from other previous clustering algorithms. The algebraic connectivity from graph theory is introduced, meanwhile the wireless channel characteristics in WSN are considered. The algebraic connectivity based on connection probability is used as metric of graph connectivity. A new metric called network quality is proposed as well, which includes the factors of network robustness and network cost. And there is a tradeoff between the two factors by weight factors configuration. Based on the network quality, a centralized algorithm is put forward to solve the network optimization problem. Some satisfactory results have been obtained by simulation.