Construction of Virtual Backbones With Edge Fault Tolerance in Wireless Networks With Multiple Communication Modes
Xinyu Liang, Jiarong Liang, Weiguang Zhang · IEEE Transactions on Communications · 2024
Over the years, wireless networks (WNs) with multiple communication modes, such as hybrid WNs, have attracted much attention. Generally, a WN with a single communication mode can be abstracted as a unit disk graph (UDG). For a WN with multiple communication modes, there may exist two or more communication modes between two different nodes, and a UDG may not be able to abstract such a WN accurately. This paper proposes a new model called a p-quasi disk graph (p-QDG) to abstract such WNs with multiple communication modes and investigates the problem of edge fault tolerance in p-QDGs. In this paper, we introduce the concept of a$ k $-edge-connected$ m $-edge-dominated set (in short,$ (k,m) $-ECDS) in a p-QDG, which can be used to abstract virtual backbones (VBs) with link fault tolerance in WNs abstracted by p-QDGs. Using the concept of a$ (k,m) $-ECDS, we design an approximation algorithm with a performance ratio of$ 5^{(k-1)}*(m+2)*max\{5p/m,1\} $for the minimum$ (k,m) $-ECDS problem in$ p $-QDGs. Our simulations show that our proposed algorithm is better than the existing related algorithms in terms of CDS size, running time and success rate.