A communication network is called a radio network if its nodes exchange messages in the following restricted way. First, a send operation performed by a node delivers copies of the same message to all directly reachable nodes. Secondly, a node can successfully receive an incoming message only if exactly one of its neighbors sent a message in that step. It is this semantics of how ports at nodes send and receive messages that defines the networks rather than the fact that only radio waves are used as a medium of communication; but if that is the case then just a single frequency is used. We discuss algorithmic aspects of exchanging information in such networks, concentrating on distributed randomized protocols. Specific problems and solutions depend a lot on the topology of the underlying reachability graph and how much the nodes know about it. In single-hop networks each pair of nodes can communicate directly. This kind of networks is also known as the multiple access channel. Popular broadcasting protocols used on such channels are Aloha and the exponential backoff. Multi-hop networks may have arbitrary topology and packets need to be routed hopping through a sequence of adjacent nodes. Distributed protocols run by such networks are usually robust enough not to expect the nodes to know their neighbors. These ad-hoc networks and protocols model the situation when nodes are mobile and do not rely on a fixed infrastructure.
The following are some results on centralized off-line algorithms computing broadcast schedules, the networks are known then, and are inputs to such sequential algorithms. Chlamtac and Weinstein @cite_33 developed a deterministic algorithm which finds in polynomial time a schedule giving broadcasting time @math . Gaber and Mansour @cite_82 showed that for any packet radio network there is a schedule of broadcasting giving time @math , and that it can be found by a deterministic polynomial algorithm. Chlamtac and Kutten @cite_26 and Sen and Hun @cite_10 showed the NP-completeness of finding optimal broadcasting schedules in packet radio networks, in particular it was shown in @cite_10 that the problem remains NP-complete even if the nodes are points in the plane and the reachability is determined by distances. Kirousis, Kranakis, Krizanc and Pelc @cite_102 studied the problem of assigning transmission ranges to nodes located on a line so as to minimize the total power consumption and preserve strong connectedness. This was later extended by Clementi, Ferreira, Penna, Perennes and Silvestri @cite_27 . Chlamtac and Kutten @cite_76 showed the NP-completeness of minimizing the average time per node during broadcasting when nodes are blocked from hearing messages other than those resulting from a broadcast algorithm.
@cite_26 @cite_33 @cite_102 @cite_27 @cite_76 @cite_10 @cite_82
2148190105 2129846535 1491256424 2147312555 1976276966 2115314281 2140432415
In this paper we develop a graph-oriented model for dealing with broadcasting in radio networks. Using this model, optimality in broadcasting protocols is defined, and it is shown that the problem of finding an optimal protocol is NP-hard. A polynomial time algorithm is proposed under which a channel is assigned to nodes from global, multiple-source broadcasting considerations. In particular, nodes participating in the broadcast do not interfere with each other's transmissions, but otherwise simultaneous channel reuse is permitted. Protocol implementations of this approach by frequency division and by time division are given. It is shown that, using these protocols, bounded delay for broadcasted messages can be guaranteed. An algorithm for efficient communication between neighbours in multihop radio networks is proposed. The algorithm guarantees a bound on the transmission efficiency in a radio channel for arbitrary topology. The algorithm can be embedded in protocols for solving basic network problems such as broadcast, multicast, leader election, or finding shortest paths. The problem of bounded-time broadcasting utilizing the proposed algorithm is addressed. A polynomial solution in which the process of spreading information over the network is viewed as the expansion of a wave caused by a point of disturbance is presented. The broadcast originates at a source node and is accomplished in repeated transmission periods, emulating a wave progressing away from the source. The algorithm is used to select a subset of potential transmitters in each period, so that a tightly bound proportion of potential receivers receive the transmission without collisions, guaranteeing a high level of spatial reuse in the broadcast process. > In this paper we study the problem of assigning transmission ranges to the nodes of a multi-hop packet radio network so as to minimize the total power consumed under the constraint that adequate power is provided to the nodes to ensure that the network is strongly connected (i.e., each node can communicate along some path in the network to every other node). Such assignment of transmission ranges is called complete. We also consider the problem of achieving strongly connected bounded diameter networks. Given a set S of radio stations located on a line and an integer h (1 ≤ h ≤ |S| - 1), the Min Assignment problem is to find a range assignment of minimum power consumption provided that any pair of stations can communicate in at most h hops. Previous positive results for this problem were known only when h = |S| - 1 (i.e. the unbounded case) or when the stations are equally spaced (i.e. the uniform chain). In particular, Kirousis, Kranakis, Krizanc and Pelc (1997) provided an efficient exact solution for the unbounded case and efficient approximated solutions for the uniform chain, respectively. This paper presents the first polynomial time, approximation algorithm for the Min Assignment problem. The algorithm guarantees an approximation ratio of 2 and runs in time O(hn3). We also prove that, for constant h and for "well spread" instances (a broad generalization of the uniform chain case), we can find a solution in time O(hn3) whose cost is at most an (1 + Ɛ(n)) factor from the optimum, where Ɛ(n) = o(1) and n is the number of stations. This result significantly improves the approximability result by on uniform chains. Both of our approximation results are obtained by new algorithms that exactly solves two natural variants of the Min Assignment problem that might have independent interest: the All-To-One problem (in which every station must reach a fixed one in at most h hops) and the Base Location problem (in which the goal is to select a set of Basis among the stations and all the other stations must reach one of them in at most h -1 hops). Finally, we show that for h = 2 the Min Assignment problem can be solved in O(n3)-time. This paper considers the issue of broadcasting protocols in multihop radio networks. The objective of a broadcasting protocol is to deliver the broadcasted message to all network nodes. To efficiently achieve this objective the broad- casting protocol in this paper utilizes two basic properties of the multihop radio network. One is the broadcast nature of the radio which allows every single trasmission to reach all nodes that are in line of sight and within range of the transmitting node. The other, spatial reuse of the radio channel, which due to the multihop nature of the network allows multiple simultaneous transmissions to be received correctly. The proposed protocol incorporates these properties to obtain a collision free forwarding of the broadcasted message on a tree. Centralized and distributed algorithms for the tree construction are presented. The obtained trees are unique in incorporating radio oriented time ordering as part of their definition. In this way multiple copies of one or more broadcasted messages can be transmitted simultaneously without collision, requiring only a small number of message transmissions. Consequently, the protocol not only guarantees that the broadcasted message reaches all network nodes in bounded time, but also ensures that the broadcasting activity will use only limited channel bandwidth and node memory. The proposed broadcast protocol thus possesses the advantages of TDM solutions while allowing the channel bandwidth to be shared, concurrently with the broadcast, with other transmission activities as dictated, for instance, by data link protocols. Some NP-completeness proofs are also given. Packet radio networks are modeled as arbitrary graphs by most researchers. We show that an arbitrary graph is an inaccurate model of the radio networks. This is true because there exists a large class of graphs which will not model the radio networks. Radio networks can be modeled accurately by a restricted class of graphs called the planar point graphs. Since the radio networks can accurately be modeled only by a restricted class of graphs, the NP-completeness results for scheduling using an arbitrary graph as the model, do not correctly reflect the complexity of the problem. We study the broadcast scheduling problem using the restricted class as the model. We show that the problem remains NP-complete even in this restricted domain. We give an O(nlogn) algorithm when all the transceivers are located on a line. We restrict our attention to static allocation in general and TDMA in particular. However, it may be noted that the results presented are also valid for other static allocation schemes. We show that for any radio network there exists a schedule of a broadcast whose time is O (D +log5 n), where D is the diameter and n is the number of nodes. (This result implies an optimal broadcast to networks with D =Ω(log5 n).) We present a centralized randomized polynomial time algorithm that given a network and a source, outputs a schedule for broadcasting the message from the source to the rest of the network.