Many-to-Many Communication in Radio Networks |
| |
Authors: | Bogdan S Chlebus Dariusz R Kowalski Tomasz Radzik |
| |
Affiliation: | (1) Department of Computer Science and Engineering, University of Colorado Denver, Denver, CO 80217, USA;(2) Department of Computer Science, University of Liverpool, Liverpool, L69 3BX, UK;(3) Department of Computer Science, King’s College London, London, WC2R 2LS, UK |
| |
Abstract: | Radio networks model wireless data communication when the bandwidth is limited to one wave frequency. The key restriction
of such networks is mutual interference of packets arriving simultaneously at a node. The many-to-many (m2m) communication
primitive involves p participant nodes from among n nodes in the network, where the distance between any pair of participants is at most d. The task is to have all the participants get to know all the input messages. We consider three cases of the m2m communication
problem. In the ad-hoc case, each participant knows only its name and the values of n, p and d. In the partially centralized case, each participant knows the topology of the network and the values of p and d, but does not know the names of the other participants. In the centralized case, each participant knows the topology of the
network and the names of all the participants. For the centralized m2m problem, we give deterministic protocols, for both
undirected and directed networks, working in
time, which is provably optimal. For the partially centralized m2m problem, we give a randomized protocol for undirected networks
working in
time with high probability (whp), and we show that any deterministic protocol requires
time. For the ad-hoc m2m problem, we develop a randomized protocol for undirected networks that works in
time whp. We show two lower bounds for the ad-hoc m2m problem. One lower bound states that any randomized protocol for the
m2m ad hoc problem requires
expected time. Another lower bound states that for any deterministic protocol for the m2m ad hoc problem, there is a network
on which the protocol requires
time when n−p(n)=Ω(n) and d>1, and that it requires Ω(n) time when n−p(n)=o(n).
The results of this paper appeared in a preliminary form in “On many-to-many communication in packet radio networks” in Proceedings
of the 10th Conference on Principles of Distributed Systems (OPODIS), Bordeaux, France, 2006, Lecture Notes in Computer Science
4305, Springer, Heidelberg, pp. 258–272.
The work of B.S. Chlebus was supported by NSF Grant 0310503. |
| |
Keywords: | Radio network Many-to-many communication Broadcast Gossiping Centralized protocol Distributed protocol Randomization |
本文献已被 SpringerLink 等数据库收录! |
|