k-terminal network reliability is the probability that k terminal vertices are connected given that edges in the network fail independently while vertices do not fail. It depends on the distribution of these terminal vertices as well as network topology. The problem of computing k-terminal reliability is NP-hard. Previous literature mainly focus on designing efficient algorithms to compute it in different graphs, but are lacking in the analysis for optimal distribution of k terminal vertices in sparse graphs, within which those with n nodes and m edges, where m ≤ n + 1, are most basic classes. Hence, it is of great significance to investigate the optimal distribution of terminal vertices in these classes of graphs before considering general cases. In this paper, we prove that k-terminal network reliability obtains the maximum if k terminal vertices induce a connected subgraph. Further, we give equations of maximum reliability for all possible graphs in the above classes. The experiments illustrate the variation, with several parameters and according to our theoretical results, of maximal k-terminal reliability, and provide observations for graphs with any number of edges.

Multistate two-terminal reliability is the probability that d units of flow can be transmitted from the source nodes to the sink node t. It is an important index fora flow network, and its value is based on minpaths or mincuts. However, the enumeration of all minpaths is not feasible in large networks. Hence, designing an approximation algorithm is valuable for the reliability of multistate flow networks. In this paper, we model a multistate flow network as an acyclic directed graph and find that the contribution of minpaths to the reliability changes with their lengths, so we consider the approximation solution of multistate two-terminal reliability by constraining diameter of the network. Furthermore, we give a sufficient and necessary condition to detect irrelevant arcs and propose an approximation algorithm by controlling the value of diameter constraint. In the meantime, the reliability with diameter constraint is also a parameter to partially reflect the performance of network. The experiments demonstrate the effectiveness and efficiency of the algorithm.

A cyber-physical system consists of two interacting networks, where the cyber network overlays the physical network. Due to the interdependence, node failures in one network may lead to failures of the other network and result in cascading failures of the whole system. One of the reasons for this phenomena is attributed to the connectivity of the interdependent system, which hinges heavily on the operation probability (or equivalently reliability) of networks in the light of node reliability. In this paper, we present the model of k-reliability, define cascading failures based on k-reliability, and propose an algorithm to calculate k-reliability for estimation of potential cascading failures. The proposed k-reliability, defined as the probability that at least k surviving nodes span an operating subnetwork, explains the operation probability of the system and reflects the connectivity of nodes in networks. In particular, we find that the network with regular interlink allocation strategy is homogeneous to the network with maximum k-reliability in class of graphs with 2n nodes and 2d edges when the information of intratopology is unknown. That is, regardless of the information of each individual network, the strategy that all nodes in the system are allotted the same number of bidirectional interlinks yields better performance on k- reliability than all other possible strategies both analytically and experimentally.

ABSTRACT In flat wireless sensor networks, one fundamental issue is region coverage, which usually addresses whether the given region is sufficiently covered by sensing disks of sensor nodes or not. Although numerous research works have been carried out on region coverage, it still lacks in‐depth understanding on the relations between region coverage and sensing topology defined with the intersections of sensing areas of sensor nodes. In this paper, we consider the region coverage problem by using the sensing topology proposed in our previous work. Based on the notion of sensing topology, we prove that the given region can be partitioned into a number of the smallest cells, each of which is defined by sensing links among sensor nodes. Then, we investigate the sufficient and necessary conditions for the existence of coverage holes for the specific polygon graph residing in the partitioned cells. Further, two polynomial time algorithms are presented for dividing the given region covered by the whole network and detecting the coverage holes existing in the interior area of the partitioned cells, respectively. The experiment results show that our proposed algorithms are effective for detecting the coverage holes. Copyright © 2014 John Wiley & Sons, Ltd.

ABSTRACT Energy‐efficient routing becomes one of the most critical technologies for sustaining the overall network lifetime of wireless sensor networks. In this paper, we propose a novel data transmission scheme between a number of specified source nodes and the single sink, which can efficiently restrict the usage frequency of each relay node, measured by the number of source nodes using it for data transmission. On the basis of the importance of source nodes that is closely related to deployed location, they form a descending sequence such that each node finds the minimum energy path earlier than the succeeding one. Then, the energy‐efficient multiple path algorithm with the computational complexity ofO(n3) is developed for deriving the minimum energy paths, wherenis the number of nodes in the network. Also, a polynomial algorithm is presented for deriving the range of the feasible values ofN0serving as the threshold of the usage frequency of relay nodes, in which each can guarantee the existence of the solution. Further, we theoretically investigate the existence of the solution and the tree‐structured solution usingm‐ary tree. Extensive simulation results show that our proposed scheme can achieve significant performance enhancement. Copyright © 2012 John Wiley & Sons, Ltd.

In this paper, we study the system reliability optimization of distributed access networks subject to a constraint on the total cost. We first formulate the cost-constrained system reliability optimization problem as a searching process in a combinatorial tree, which enumerates all the possible solutions to the problem. Because the calculation of each possible solution for the reliability problem is extremely time-consuming, a novel algorithm, the Shrinking & Searching Algorithm (SSA), is proposed to speed up the searching process. SSA jointly considers the upper bound of the system reliability for each branch in the combinatorial tree, and the cost constraint on the possible solutions. It avoids most of the redundant calculations in the searching process by gradually shrinking the difference between lower & upper bounds of the length of a path in the corresponding combinatorial tree, which represents a feasible solution. Case study & simulation results are presented to demonstrate the performance of the SSA.