An Algorithm for Constructing Virtual Backbone Network under Routing Cost Constraint for Heterogeneous Wireless Sensor Networks

In order to avoid broadcast storms in wireless sensor networks and improve the efficiency of information transmission, virtual backbone networks have been widely introduced into network information transmission. In order to combine the practical development needs, this paper devotes to the optimization research on the construction of virtual backbone network, optimizes the three aspects of routing path length, backbone size and fault tolerance respectively, introduces the GOC-CDS construction strategy and the <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\alpha \text{MOC-SCDAS}$</tex> construction strategy, and designs an approximation algorithm for the construction of the virtual backbone network based on the two strategies. Through theoretical analysis, the algorithm can obtain a <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$(72\rho^{2} + 24\rho + m + 1)(2\rho + 1)^{2}$</tex>-approximate optimal solution, where <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\rho = \frac{r_{max}}{r_{min}}$</tex>. After comparative experiments, it is verified that the can maintain a smaller routing path length of the network and a better fault tolerance of the virtual backbone network, and at the same time, it can ensure that the size of the backbone network is as small as possible.