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.

Súbory diplomovej práce: