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

EasyChair Preprint 15290

Abstract

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 αMOC-SCDAS 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 (72ρ²+24ρ+m+1)(2ρ+1)² -approximate optimal solution, where ρ=r_max/r_min. After comparative experiments, it is verified that the algorithm 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.

Keyphrases: Routing cost constraint, Wireless Sensor Network, connected dominating set, fault tolerance

@booklet{EasyChair:15290,
  author    = {Yuetao Wang and Chunyan Liu and Yunlong Zhao and Yang Li},
  title     = {An Algorithm for Constructing Virtual Backbone Network Under Routing Cost Constraint for Heterogeneous Wireless Sensor Networks},
  howpublished = {EasyChair Preprint 15290},
  year      = {EasyChair, 2024}}