What Is the Use Of Collision Detection (in Wireless Networks)?
METADATA ONLY
Loading...
Author / Producer
Date
2010-07
Publication Type
Report
ETH Bibliography
yes
Citations
Altmetric
METADATA ONLY
Data
Rights / License
Abstract
We show that the asymptotic gain in the time complexity when using collision detection depends heavily on the task by investigating three prominent problems for wireless networks, i.e. the maximal independent set (MIS), broadcasting and coloring problem. We present lower and upper bounds for all three problems for the Growth-Bounded Graph such as the Unit Disk Graph. We prove that the bene_t of collision detection ranges from an exponential improvement down to no asymptotic gain at all. In particular, for the broadcasting problem our deterministic algorithm is running in time O(Dlog n). It is an exponential im- provement over prior work, if the diameter D is polylogarithmic in the number of nodes n, i.e. D 2 O(logc n) for some constant c.
Permanent link
Publication status
published
External links
Editor
Book title
Journal / series
Volume
322
Pages / Article No.
Publisher
ETH Zurich, Computer Engineering and Networks Laboratory
Event
Edition / version
Methods
Software
Geographic location
Date collected
Date created
Subject
Organisational unit
03604 - Wattenhofer, Roger / Wattenhofer, Roger