Int J Performability Eng ›› 2007, Vol. 3 ›› Issue (2): 267-279.doi: 10.23940/ijpe.07.2.p267.mag

• Original articles • Previous Articles     Next Articles

On Computing Reliability and Expected Hop Count of Wireless Communication Networks


  1. 1Department of Computing, Curtin University of Technology, Perth, Western Australia.
    2Department of Electrical and Computer Engineering, Louisiana State University, Baton Rouge,
    3Holcombe Department of Electrical and Computer Engineering, Clemson University, SC, USA


The (s,t) expected-hop-count (EHC) in a wireless communication network (WCN), modeled as a graph with probabilistic node failures, is the expected number of operational nodes that a message must traverse from a node s to reach its destination node t. A typical solution for the problem uses factoring theorem to compute the EHC of WCN. Instead, this paper proposes a 2-step approach that utilizes the sum-of-disjoint-product (SDP) technique. First, we provide an efficient technique to generate all (s,t) simple paths considering only the nodes of the WCN. We also propose an efficient algorithm to enumerate all (s,t) simple paths of an interval-graph. Second, we propose using the SDP technique over the paths to compute the reliability and EHC. We show (conjecture) that our SDP-based technique solves the reliability measures in polynomial time (pseudo-polynomial) for WCN containing all disjoint-paths (forming an interval graph). Simulations on several WCN under various conditions show that the SDP-based technique computes the reliability and EHC in several orders of magnitude faster than the existing factoring-based algorithm. The paper also discusses some application of the reliability measures.
Received on February 21, 2006
References: 16