Efficient Broadcasting and Gathering in Wireless Ad-Hoc Networks

This paper considers the problem of broadcasting and information gathering in wireless ad-hoc networks, i.e. in wireless networks without any infrastructure in addition to the mobile hosts. Broadcasting is the problem of sending a packet from a source node in the network to all other nodes in the network. Information gathering is the problem of sending one packet each from a subset of the nodes to a single sink node in the network. Most of the proposed theoretical wireless network models oversimplify wireless communication properties. They present algorithms for broadcasting a single or multiple message(s), and for information gathering. Their algorithms have the advantage that they are very simple and self-stabilizing, and would therefore even work in a dynamic environment.