Efficient computation of maximal independent sets in unstructured multi-hop radio networks

When being deployed, ad-hoc and sensor networks are unstructured and lack an efficient and reliable communication scheme. Hence, the organization of a MAC layer is the primary goal during and immediately after the deployment of such networks. Computing a good initial clustering facilitates this task...

Full description

Saved in:
Bibliographic Details
Main Authors: Moscibroda, T., Wattenhofer, R.
Format: Conference Proceeding
Language:English
Subjects:
Computer network reliability
Computer networks
Intelligent networks
Interference
Laboratories
Radio network
Radio networks
Reliability engineering
Spread spectrum communication
Wireless sensor networks
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:When being deployed, ad-hoc and sensor networks are unstructured and lack an efficient and reliable communication scheme. Hence, the organization of a MAC layer is the primary goal during and immediately after the deployment of such networks. Computing a good initial clustering facilitates this task and is therefore a vital part of the initialization process. A clustering based on a maximal independent set provides several highly desirable properties. Besides yielding a dominating set of good quality, such a clustering avoids interference between clusterheads, thus allowing efficient communication. We propose a novel algorithm that works under a model capturing the characteristics of the initialization phase of unstructured radio networks, i.e., asynchronous wake-up, scarce knowledge about the topology of the network graph, no collision detection, and the hidden terminal problem. We show that even under these hard conditions, the algorithm computes a maximal independent set in polylogarithmic time.
DOI:10.1109/MAHSS.2004.1392071