Construction of Virtual Backbones With Edge Fault Tolerance in Wireless Networks With Multiple Communication Modes

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 <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$ k $ </tex-math></inline-formula>-edge-connected <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$ m $ </tex-math></inline-formula>-edge-dominated set (in short, <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$ (k,m) $ </tex-math></inline-formula>-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 <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$ (k,m) $ </tex-math></inline-formula>-ECDS, we design an approximation algorithm with a performance ratio of <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$ 5^{(k-1)}*(m+2)*max\{5p/m,1\} $ </tex-math></inline-formula> for the minimum <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$ (k,m) $ </tex-math></inline-formula>-ECDS problem in <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$ p $ </tex-math></inline-formula>-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.