3rd International ICST Symposium on Modeling and Optimization in Mobile, Ad Hoc, and Wireless Networks

Research Article

On range matrices and wireless networks in d dimensions

  • @INPROCEEDINGS{10.1109/WIOPT.2005.33,
        author={M.  Desai and  D.  Manjunath},
        title={On range matrices and wireless networks in d dimensions},
        proceedings={3rd International ICST Symposium on Modeling and Optimization in Mobile, Ad Hoc, and Wireless Networks},
        publisher={IEEE},
        proceedings_a={WIOPT},
        year={2005},
        month={4},
        keywords={},
        doi={10.1109/WIOPT.2005.33}
    }
    
  • M. Desai
    D. Manjunath
    Year: 2005
    On range matrices and wireless networks in d dimensions
    WIOPT
    IEEE
    DOI: 10.1109/WIOPT.2005.33
M. Desai1, D. Manjunath1
  • 1: Dept. of Electr. Eng., Indian Inst. of Technol., Bombay, India

Abstract

Suppose that V = {v1, v2, ...vn} is a set of nodes randomly (uniformly) distributed in the d dimensional cube [0, x0]d, and W = {w(i, j) > 0 : 1 ≤ i, j ≤ n} is a set of numbers chosen so that w(i, j) = w(j, i) = w(j, i). Construct a graph Gn,d,W whose vertex set is V, and whose edge set consists of all pairs {ui, uj} with || ui - uj || ≤ w(i, j). In the wireless network context, the set V is a set of labeled nodes in the network and W represents the maximum distances between the node pairs for them to be connected. We essentially address the following question: "if G is a graph with vertex set V, what is the probability that G appears as a subgraph in Gn,d,W?" Our main contribution is a closed form expression for this probability under the l∞ norm for any dimension d and a suitably defined probability density function. As a corollary to the above answer, we also answer the question, "what is the probability that Qn,d,W is connected?".