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