|Názov:||Broadcasting in radio networks
|Vedúci:||Doc. RNDr. Rastislav Královič, PhD.
|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.