The number of nodes of a network, called its size, is one of the most important network parameters. A radio network is a collection of stations, called nodes, with wireless transmission and receiving capabilities. It is modeled as a simple connected undirected graph whose nodes communicate in synchronous rounds. In each round, a node can either transmit a message to all its neighbors, or stay silent and listen. At the receiving end, a node @math hears a message from a neighbor @math in a given round, if @math listens in this round, and if @math is its only neighbor that transmits in this round. If @math listens in a round, and two or more neighbors of @math transmit in this round, a collision occurs at @math . Two scenarios are considered in the literature: if nodes can distinguish collision from silence (the latter occurs when no neighbor transmits), we say that the network has the collision detection capability, otherwise there is no collision detection. We consider the task of size discovery: finding the size of an unknown radio network with collision detection. All nodes have to output the size of the network, using a deterministic algorithm. Nodes have labels which are (not necessarily distinct) binary strings. The length of a labeling scheme is the largest length of a label. Our main result states that the minimum length of a labeling scheme permitting size discovery in the class of networks of maximum degree Delta is Theta( Delta).
Algorithmic problems in radio networks modeled as graphs were studied for such distributed tasks as broadcasting @cite_3 @cite_5 , gossiping @cite_3 @cite_16 and leader election @cite_15 @cite_11 . In some cases @cite_3 @cite_16 , the model without collision detection was used, in others @cite_19 @cite_11 , the collision detection capability was assumed.
@cite_3 @cite_19 @cite_5 @cite_15 @cite_16 @cite_11
2003002196 1981696935 2167242526 2048655757
Abstract We address the fundamental distributed problem of leader election in ad hoc radio networks modeled as undirected graphs. A signal from a transmitting node reaches all neighbors but a message is received successfully by a node, if and only if exactly one of its neighbors transmits in this round. If two neighbors of a node transmit simultaneously in a given round, we say that a collision occurred at this node. Collision detection is the ability of nodes to distinguish a collision from silence. We show that collision detection speeds up leader election in arbitrary radio networks. Our main result is a deterministic leader election algorithm working in time O ( n ) in all n -node networks, if collision detection is available, while it is known that deterministic leader election requires time Ω ( n log n ) , even for complete networks, if there is no collision detection. We consider broadcasting in radio networks, modeled as undirected graphs, whose nodes know only their own label and labels of their neighbors. In every step every node acts either as a transmitter or as a receiver. A node acting as a transmitter sends a message which can potentially reach all of its neighbors. A node acting as a receiver in a given step gets a message if and only if exactly one of its neighbors transmits in this step. Bar-Yehuda, Goldreich, and Itai [J. Comput. System Sci., 45 (1992), pp. 104--126] considered broadcasting in this model. They claimed a linear lower bound on the time of deterministic broadcasting in such radio networks of diameter 3. This claim turns out to be incorrect in this model (although it is valid in a more pessimistic model [R. Bar-Yehuda, O. Goldreich, and A. Itai, Errata Regarding "On the time complexity of broadcast in radio networks: An exponential gap between determinism and randomization," http: www.wisdom.weizmann.ac.il mathusers oded p .html, 2002]). We construct an algorithm that broadcasts in logarithmic time on all graphs from the Bar-Yehuda, Goldreich, and Itai paper (BGI). Moreover, we show how to broadcast in sublinear time on all n-node graphs of diameter @math . On the other hand, we construct a class of graphs of diameter 4, such that every broadcasting algorithm requires time @math on these graphs. In view of the randomized algorithm from BGI, running in expected time @math on all @math -node graphs of diameter D (cf. also a recent @math -time algorithm from [D. Kowalski and A. Pelc, Proceedings of the 22nd Annual ACM Symposium on Principles of Distributed Computing, Boston, 2003, pp. 73--82; A. Czumaj and W. Rytter, Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, Cambridge, MA, 2003, pp. 492--501]), our lower bound gives the first correct proof of an exponential gap between determinism and randomization in the time of radio broadcasting, under the considered model of radio communication. We consider broadcasting in radio networks: one node of the network knows a message that needs to be learned by all the remaining nodes. We seek distributed deterministic algorithms to perform this task. Radio networks are modeled as directed graphs. They are unknown, in the sense that nodes are not assumed to know their neighbors, nor the size of the network, they are aware only of their individual identifying numbers. If more than one message is delivered to a node in a step then the node cannot hear any of them. Nodes cannot distinguish between such collisions and the case when no messages have been delivered in a step. The fastest previously known deterministic algorithm for deterministic distributed broadcasting in unknown radio networks was presented in [6], it worked in time O(n11 6). We develop three new deterministic distributed algorithms. Algorithm A develops further the ideas of [6] and operates in time O(n1:77291) = O(n9 5), for general networks, and in time O(n1+a+H(a)+o(1)) for sparse networks with in-degrees O(na) fora < 1=2; here H is the entropy function. Algorithm B uses a new approach and works in time O(n3 2 log1 2 n) for general networks or O(n1+a+o(1)) for sparse networks. Algorithm C further improves the performance for general networks running in time O(n3 2). The unstructured multi-hop radio network model, with asynchronous wake-up, no collision detection and little knowledge on the network topology, is proposed for capturing the particularly harsh characteristics of initially deployed wireless adhoc and sensor networks. In this paper, assuming such a practical model, we study a fundamental problem of both theoretical and practical interests--the local broadcasting problem. Given a set of nodes V where each node wants to broadcast a message to all its neighbors that are within a certain local broadcasting range R, the problem is to schedule all these requests in the fewest timeslots. By adopting the physical interference mode land without any knowledge on neighborhood, we give a new randomized distributed approximation algorithm for the local broadcasting problem with approximation ratio O (log n) where nis the number of nodes. This distributed approximation algorithm improves the state-of-the-art result in [22] by a logarithmic factor.