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.

An extended connected dominating set (ECDS) in a wireless network with cooperative communication (CC) is a subset of nodes such that its induced subgraph is connected and each node outside the ECDS is covered by either one neighbor or several quasineighbors in the ECDS. Traditionality, the size of virtual backbone (VB) is the only factor considered in the problem of CDS construction. However, diameter is also an important factor to evaluate VB. In this paper we consider the problem of constructing quality ECDSs in unit disk graphs under CC with both of these two factors. We propose a two-phase centralized algorithm BD-ECDS to construct an ECDS for a given UDG with CC, which has a constant performance ratio (PR) and diameter. To obtain the PR of this two-phase centralized algorithm, we first give an upper bound of the EDS and use this upper bound to prove that the size of the ECDS under CC generated by the centralized algorithm is no greater than 120 | E C D S o p t | − 2 , where E C D S o p t is the size of the minimum ECDS. Furthermore, our theoretical analysis and simulation results show that our algorithm BD-ECDS is superior to previous approaches.

Frequently, unit disk graphs (UDGs) are used to model homogeneous wireless sensor networks (WSNs), in which each node has the same transmission radius. In some applications, however, different nodes in a WSN have different transmission radii, meaning that a UDG cannot accurately model the WSN. In this case, a disk graph with bidirectional links (DGB) can be used in place of a UDG. Nevertheless, most results reported to date concern the problem of finding minimum fault-tolerant CDSs in UDGs. In this paper, we investigate the minimum fault-tolerant CDS problem for DGBs by reconstructing CDSs for DGBs with faulty nodes. We present a centralized approximation algorithm for CDS reconstruction to address the minimum fault-tolerant CDS problem in given DGBs. The performance ratio (PR) of the presented algorithm is the same as that of the algorithm used to generate the input CDS${C}$. Furthermore, we present a distributed version, which not only can be easily implemented in real situations but also considers CDS size to reduce the network cost. Theoretical analysis shows that the PR of our proposed algorithm is lower than those of other state-of-the-art algorithms for the minimum fault-tolerant CDS problem in given DGBs. In addition, numerical experiments objectively demonstrate that the performance of our algorithm is superior on average to that of its competitors in terms of CDS size, run time and application rate.

The strategy of constructing a virtual backbone (VB) to perform routing tasks is considered a mature method for addressing the broadcast storm problem in wireless sensor networks (WSNs). A WSN can be regarded as a unit disk graph (UDG), and its VBs can be regarded as connected dominating sets (CDSs) in the UDG. The smaller the VB is, the less overhead and wireless signal collision and interference there are in the process of communication via the VB. Therefore, when a VB is designed in a WSN, its size is naturally an important factor to be considered. In addition, other factors that are often ignored by researchers, such as the routing cost of the VB, should be considered. In this article, we focus on how to construct a VB with a small size and routing cost in a WSN. We propose two centralized approximation algorithms: one is an algorithm for constructing a VB with a guaranteed routing cost, called RCC-CDS, and the other is an algorithm for constructing a VB with a bounded diameter, called BD-CDS. The performance ratio (PR) of RCC-CDS is 142.758, and that of BD-CDS is 13.596. We compare these two algorithms with previous works though theoretical analysis and simulation experiments on the basis of algorithm performance. The results obtained show that our algorithms have better performance.

In the context of wireless sensor networks (WSNs), the problem of virtual backbones (VBs) for undertaking routing tasks to alleviate broadcast storms has been extensively studied. In practical applications, different nodes in a WSN may have different transmission ranges because of differences in power control or functionality, among other reasons. In such a situation, a disk graph (DG) can be used as a mathematical model of the WSN, and a strongly connected dominating and absorbent set (SCDAS) in the DG can be treated as a VB in the corresponding WSN. In a WSN with faulty nodes, a fault-tolerant VB is superior to a traditional one. Thus, it is desirable to construct a $ k$ -strongly connected $ m$ -dominating and absorbent set ( $ (k,m)$ -SCDAS) in the DG to serve as a fault-tolerant VB in the corresponding WSN. In this article, to enable the construction of a high-quality $ (k,m)$ -SCDAS in a DG, a constant approximation algorithm with a performance ratio of $(2k(5^{k-1}-1)+1)(R+m+4(\frac{R}{m}+1))$ is proposed, where $ k$ and $ m$ are constants ( $ 2 \;\leqslant\; k \;\leqslant\; m$ ) and $ R$ is the maximum number of independent nodes within the transmission range of a node in the DG. A theoretical analysis and simulation results show that our work is superior to previous approaches.

A connected dominating set (CDS) can act as a virtual backbone (VB) in a wireless sensor network (WSN). The overhead in a WSN is usually determined by the size of the corresponding VB. However, the construction of minimum CDSs (MCDSs) has been proven to be an NP-hard problem. Thus, most researchers use approximation algorithms to find smaller CDSs. In certain applications, the transmission radii of some nodes in the network are unstable due to certain environmental factors such as obstacles, signal interference and node movement. Thus, the robustness of VBs in WSNs should be considered. In this paper, we propose the concept of a d-robust CDS and corresponding algorithms to construct d-robust CDSs in WSNs with unstable transmission ranges. We propose algorithms for a d-robust CDS that is bounded by [40.68/(1 - d)2+ 10.17] · opt + [31.32/(1 - d)2+ 7.83], where opt is the size of the MCDS and d ∈ [0, 1). Through simulations, we show the relationship between the size of the d-robust CDS and the value of d and compare our algorithms with existing algorithms in terms of the robustness degree of the CDS. The results show that the CDSs produced by our algorithms exhibit better robustness.

Summary Matching composition network is a family of interconnection networks, including the BC network and the hyper Petersen network, etc. In this paper, we prove that the local diagnosability of an MCN can be obtained by adding one to that of the component with some structural restrictions. Additionally, we obtain a sufficient condition for verifying that an MCN with fault‐free edges (faulty edges, respectively) has strong local diagnostic properties. By applying these results, the BC network BCn and the hyper Petersen network HPn are nl‐diagnosable at each node belonging to them, for n ⩾ 3. These interconnection networks with fault‐free edges (faulty edges, respectively) possess the strong local diagnosability property.

We usually use a digraph to represent a wireless network (WN). Correspondingly, a connected dominating set (CDS) of the digraph is usually used to denote a virtual backbone (VB) of the corresponding WN. In this article, focusing on the problem of a minimum strongly connected dominating and absorbing set (MSCDAS) with a bounded diameter (or guaranteed routing cost) for a digraph, which is strongly connected, we introduce two algorithms. One is called the guaranteed routing cost strongly connected dominating and absorbing set (GOC-SCDAS), which can generate a strongly connected dominating and absorbing set (SCDAS) with a performance ratio 14.4k+1/22 in respect of the optimal solution. Another is called the α guaranteed routing cost strongly connected bidirectional dominating and absorbing set ( α -GOC-SCBDAS), which can generate a strongly connected bidirectional dominating and absorbing set (SCBDAS) with a performance ratio 8.8443k+1/22k+1/22 in respect of the optimal solution and a better routing cost, where k=rmax/rmin and rmin,rmax is the transmission range of nodes in the network. Through the simulation experiments, we obtain the conclusion that in terms of the diameter and average routing path length (ARPL) of CDS, the outputs of our algorithms are better than those of the algorithm in (Du et al. 2006).

Summary The topology of interconnection networks plays an important role in the performance of parallel and distributed computing systems. In this paper, we propose a new interconnection network called twisted crossed cube (TCQn) and investigate its basic network properties in terms of the regularity, connectivity, fault tolerance, recursiveness, hamiltonicity and ability to simulate other architectures, and so on. Then, we develop an effective routing algorithm Route (u, v) for TCQn that takes no more than d(u, v) + 1 steps for any two nodes (u, v) to communicate with each other, and the routing process shows that the diameter, wide diameter, and fault‐tolerant diameter of TCQn are about half of the corresponding diameters of the equivalent hypercube with the same dimension. In the end, by combining TCQn with crossed cube (CQn), we propose a preferable dynamic network structure, that is, the dynamic crossed cube, which has the same network diameter as TCQn/CQn and better properties in other respects, for example, its connection complexity is half of that of TCQn/CQn when the network scale is large enough, and the number of its average routing steps is also much smaller than that in TCQn/CQn. Copyright © 2015 John Wiley & Sons, Ltd.