CaltechAUTHORS
  A Caltech Library Service

Covering Algorithms, Continuum Percolation, and the Geometry of Wireless Networks.

Booth, Lorna and Bruck, Jehoshua and Franceschetti, Massimo and Meester, Ronald (2001) Covering Algorithms, Continuum Percolation, and the Geometry of Wireless Networks. California Institute of Technology . (Unpublished) http://resolver.caltech.edu/CaltechPARADISE:2001.ETR037

[img]
Preview
PDF (Adobe PDF (3.5MB))
See Usage Policy.

3443Kb
[img]
Preview
Postscript
See Usage Policy.

518Kb

Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechPARADISE:2001.ETR037

Abstract

Continuum percolation models where each point of a two-dimensional Poisson point process is the center of a disc of given (or random) radius r, have been extensively studied. In this paper, we consider the generalization in which a deterministic algorithm (given the points of the point process) places the discs on the plane, in such a way that each disc covers at least one point of the point process and that each point is covered by at least one disc. This gives a model for wireless communication networks, which was the original motivation to study this class of problems. We look at the percolation properties of this generalized model, showing the almost sure non-existence of an unbounded connected component of discs for small values of the density lambda of the Poisson point process, for any covering algorithm. In general, it turns out not to be true that unbounded connected components arise when lambda is taken sufficiently high. However, we identify some large families of covering algorithms, for which such an unbounded component does arise for large values of lambda. We show how a simple scaling operation can change the percolation properties of the model, leading to the almost sure existence of an unbounded connected component for large values of lambda, for any covering algorithm. Finally, we show that a large class of covering algorithms, that arise in many practical applications, can get arbitrarily close to achieving a minimal density of covering discs. We also show (constructively) the existence of algorithms that achieve this minimal density.


Item Type:Report or Paper (Technical Report)
Related URLs:
URLURL TypeDescription
http://www.paradise.caltech.edu/papers/etr037.psPublisherUNSPECIFIED
Group:Parallel and Distributed Systems Group
Record Number:CaltechPARADISE:2001.ETR037
Persistent URL:http://resolver.caltech.edu/CaltechPARADISE:2001.ETR037
Usage Policy:You are granted permission for individual, educational, research and non-commercial reproduction, distribution, display and performance of this work in any format.
ID Code:26037
Collection:CaltechPARADISE
Deposited By: Imported from CaltechPARADISE
Deposited On:03 Sep 2002
Last Modified:26 Dec 2012 13:51

Repository Staff Only: item control page