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 NPhard. 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.

