| Meno: | Lukáą
|
|---|
| Priezvisko: | Poláček
|
|---|
| Názov: | Broadcasting in radio networks
|
|---|
| Vedúci: | Doc. RNDr. Rastislav Královič, PhD.
|
|---|
| Rok: | 2009
|
|---|
| Blok: | INF
|
|---|
| Kµúčové slová: | Broadcasting, radio networks, distributed algorithms, approximation algorithms
|
|---|
| Abstrakt: | We consider deterministic broadcasting in radio networks, where nodes can
transmit information. A signal from a node can reach other nodes, but this
relation does not have to be symmetric -- if node $u$ can reach $v$, node $v$
does not have to be able to reach $u$. Communication is synchronous and if two
or more neighbours of a node transmit to the node in one round, collision
occurs and the node hears nothing.
Finding optimal broadcasting time for a network is known to be NP-hard. We
introduce three algorithms with different complexities that find optimal
broadcasting time for a network. The second part of the thesis focuses on
approximation algorithms in geometric radio networks. We present a global
algorithm and a distributed broadcasting algorithm where nodes have knowledge
of all nodes within a certain distance.
|
|---|