tradeoffs between knowledge and time of communication in geometric radio networks
We consider deterministic broadcasting in geometric radio networks (GRN) whose nodes know only a limited part of the network Nodes of a GRN 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 is situated within range of two nodes transmitting simultaneously it 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 . The aim of this paper is to investigate tradeoffs between knowledge radius s and time of deterministic broadcasting in a GRN with n nodes and eccentricity D of the source. For s exceeding the largest range, or s exceeding the largest distance between any two nodes, we design an (optimal) broadcasting algorithm working in time O ( D ), while for any positive s we show how to broadcast in time &Ogr; ( D (1+log( n / D ))). For s = 0, i.e., when knowledge of each node is limited to itself, broadcasting can always be performed in time &Ogr; ( n ) and cannot be improved even for some symmetric GRN of constant diameter. In contrast to the upper bound &Ogr; ( n ) which assumes that each node knows its own position, we show a surprising result that broadcasting requires time &OHgr;( n log n ) for some GRN whose nodes do not have this knowledge. If the collision detection capability is additionally assumed, we show that optimal broadcasting time in symmetric GRN is &THgr;( D + log n ). These 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. The type of knowledge influencing efficiency of broadcasting includes knowledge radius, knowledge of individual positions when knowledge radius is zero, and awareness of collisions.
knowledge radio network deterministic broadcasting distributed