On Computing Reliability and Expected Hop Count of Wireless Communication Networks
Volume 3, Number 2, April 2007 - Paper 7 - pp. 267 - 279
SIETENG SOH1, WILLIAM LAU1, SURESH RAI2, and RICHARD R. BROOKS31Department 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
(Received on February 21, 2006)
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.
Click here to download the paper.
Please note : You will need Adobe Acrobat viewer to view the full articles.