Abstract:

We consider deterministic broadcasting in geometric radio networks
(GRN) whose nodes know only a limited part of the network. Nodes of a 
GRN (sensors, stations) are situated in the plane and each of them is 
equipped with a transmitter of some range r. A signal from this node 
can reach all nodes at distance at most r from it but if a node u is 
situated within the range of two nodes transmitting simultaneously, 
then a collision occurs at u and u cannot get any message. Each node 
knows the part of the network within knowledge radius s from it, i.e., 
it knows the positions, labels and ranges of all nodes at distance at most s. 
We study the impact of knowledge radius s on the time of deterministic 
broadcasting in a GRN with n nodes and eccentricity D of the source.
Our results show sharp contrasts between the efficiency of broadcasting 
in geometric radio networks as compared to broadcasting in arbitrary graphs.
They also show quantitatively the impact of various types of knowledge
available to nodes on broadcasting time in GRN. In the important case of
radio networks modeled as unit disc graphs (UDG), in which every node 
knows only its own position, we show a strict difference in complexity between 
two seemingly similar tasks:
broadcasting and activating the network from a single source.