The mobile ad hoc network has recently been recognized as an attractive network architecture for wireless communication. Reliable broadcast is an important operation in MANET (e.g., giving orders, searching routes, and notifying important signals). However, using a naive flooding to achieve reliable broadcasting may be very costly, causing a lot of contention, collision, and congestion, to which we refer as the broadcast storm problem. This paper proposes an efficient reliable broadcasting protocol by taking care of the potential broadcast storm problem that could occur in the medium-access level. Existing protocols are either unreliable or reliable but based on a too costly approach. Our protocol differs from existing protocols by adopting a low-cost broadcast, which does not guarantee reliability, as a basic operation. The reliability is ensured by additional acknowledgement and handshaking. Simulation results do justify the efficiency of the proposed protocol. 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. We will use a model that takes into account that nodes have different transmission and interference ranges, and we propose algorithms in this model that achieve a high time and work-efficiency. We present algorithms for broadcasting a single or multiple message(s), and for information gathering. Our algorithms have the advantage that they are very simple and self-stabilizing, and would therefore even work in a dynamic environment. Also, our algorithms require only a constant amount of storage at any host.
Index Terms - Wireless ad hoc networks, flooding, broadcasting, localized algorithms.
In this paper we consider the problem of broadcasting and gathering messages in wireless ad-hoc networks. Broadcasting is a basic communication primitive for wireless networks, and it has therefore been heavily studied both in the systems and in the theory community. Though broadcasting itself appears to be an easy problem, it is actually quite hard to realize in an efficient and reliable way in a mobile ad-hoc network. The main problem concerning theoretical investigations is that mobile ad-hoc networks have many features that are hard to model in a clean way. Major challenges are how to model wireless communication and how to model mobility. Here, theoretical work is still rare. So far, people in the theory area have mostly looked at static wireless systems (i.e. the wireless units are always available and do not move).Wireless communication is usually modeled using the packet radio network model. In this model, the wireless units, or nodes, are represented by a graph, and two nodes are connected by an edge if they are within transmission range of each other. Transmissions of messages interfere at a node if at least two of its neighbors transmit a message at the same time. A node can only receive a message if it does not interfere with any other message(s). The packet radio network model is a simple and clean model that allows one to design and analyze broadcast algorithms with a reasonable amount of effort. However, since it is a high-level model, it does have some serious problems with certain scenarios in practice. For example, in reality it is not true that the transmission range of a node is the same as its interference range. Instead, the interference range of a node is usually at least twice as large as its transmission range. Not taking this into account may result in broadcasting algorithms that cannot handle certain scenarios well although efficient on paper. In fact, it is not difficult to construct examples (see ), where most existing protocols for broadcasting require Î©(n) rounds even in expectation when we consider the situation that the interference range is bigger than the transmission range. Thus it is necessary that algorithms for broadcasting in wireless networks consider problems due to interference. There is a limited number of papers that use a model that differentiates between the transmission range and interference range [1, 7, 8], but they assume that nodes are distributed in an ideal space so that the transmission range and interference range of every node can be specified in terms of Euclidean distance. Another serious limitation in most of the existing algorithms is the assumption that the size of the network, or at least a linear estimate of the size of the network, is available to all of the nodes in the network.
We will use a much more general wireless communication model that recently appeared in . In this work we present self-stabilizing algorithms for broadcasting and information gathering in wireless overlay networks. To keep this paper at a reasonable length, we do not give a detailed motivation for the model adopted but instead refer the interested reader to .
II. RELATED WORK
Broadcasting in wireless ad-hoc networks has been extensively studied in the literature, especially in the more applied ad-hoc networking community. See  for a survey.
To the best of our knowledge, our paper is the first work that formally develops and analyzes broadcast algorithms under a model with separate transmission and interference ranges. All of the work on the broadcast problem cited below assumes a static network scenario where the transmission and interference ranges of a node are the same. In an early work, Chlamtac and Weinstein  presented a deterministic centralized broadcast protocol which assumes complete knowledge of the network topology and which runs in O(D log2 n) time, where n is the number of nodes and D is diameter of the network. Bar-Yehuda et al.  were the first to present a distributed algorithm for the broadcasting problem in ad-hoc wireless networks without assuming any topological knowledge, except immediate neighborhood, of the network. Their algorithm had expected O(D log n + log2 n) time. In  a lower bound of Î©(Dlog (n/D)) is shown for any randomized broadcast protocol. In [13, 4] randomized protocols with expected runtime of O(D log (n/D) + log2 n) are presented in  the underlying topology is assumed to be symmetric, while in  this assumption is dropped. Adler and Scheideler  present approximation algorithms for the unicast problem in wireless ad-hoc networks under the assumption that the transmission and interference ranges are not the same. However they still assume a simplified disk model based on Euclidean distances. Moreover, their unicast algorithm does not translate directly into an efficient broadcasting algorithm.
The problem of information gathering in wireless networks is studied mostly in the context of wireless sensor networks. The authors of  construct a tree on which gathering and aggregation can be performed. However, they do not deal with inherent problems such as channel contention and interference and also do not provide theoretical bounds on time and work. Information gathering and aggregation have also been studied in [5, 12, 15, 19, 9] but a rigorous formal analysis for wireless ad hoc networks has not been performed prior to this work.
III. SYSTEM MODEL
Our system model is very similar to that used by Liu et al. . We assume that all nodes are located in a 2D plane and have a transmission range of R. Therefore, the topology of the network can be represented by a unit disk graph. We assume that the network is connected. Two nodes are considered neighbors if they are in the transmission range of each other. We suppose that each node knows its location via a localization technique such as Global Positioning System (GPS) or the lightweight techniques summarized in . Each node periodically broadcasts a very short Hello message, which includes its ID and position. Thus, each node gets the position of its neighbors as well. In the medium access control (MAC) layer, we assume that scheduling is done according to the p-persistent CSMA/CA protocol, which is based on IEEE 802.11 in the broadcast mode. In the p-persistent CSMA/CA protocol, when a node has a message to transmit, it initiates a defer timer by a random number and starts listening to the channel. If the channel is busy, it continues to listen until the channel becomes idle. When the channel is idle, it starts decrementing the defer timer at the end of each time unit. The message is broadcast when the timer expires.
IV. AN EFFICIENT SENDER-BASED BROADCASTING ALGORITHM
4.1 ALGORITHM STRUCTURE
Our first proposed broadcasting algorithm is a senderbased algorithm, i.e., each sender selects a subset of nodes to forward the message. Each message can be identified by its source ID and a sequence number incremented for each message at the source node. Algorithm 1 is a general sender-based broadcasting algorithm and indicates the structure of our proposed sender-based broadcasting algorithm. Upon expiration of the timer, the algorithm requests the MAC layer to schedule a broadcast. The message scheduled in the MAC layer is buffered and then broadcast with a probability p. This adds another delay (i.e., the MAC-layer delay) in broadcasting the message. The MAC-layer delay in IEEE 802.11 is a function of several factors including the network traffic. Note that there is a chance that a node changes its decision (regarding the selected nodes or regarding whether to broadcast) during the MAC-layer delay due to receiving other copies of the message. This chance is not negligible when the delay in the MAC layer is comparable to the average value of the timer set in the broadcasting algorithm. As stated in , one solution to this problem is a cross-layer design in which the network layer is given the ability to modify or remove packets that are present in the MAC-layer queue. This solution allows the broadcasting algorithms to perform close to their ideal performance even for very small average timer values . In the entire paper, we assume that either the MAC-layer delay is negligible compared to the average delay set by the algorithm or the network layer (hence, the algorithm) is able to modify or remove packets buffered in the MAC-layer queue (in this case, the algorithm does not require to set a defer timer).
The sender-based broadcasting algorithms can be divided into two subclasses. In the first subclass, each node decides whether or not to broadcast solely based on the first received message and drops the rest of the same messages that it receives later. Liu et al.'s algorithm falls in this subclass and achieves local optimality by selecting the minimum number of forwarding nodes in the lowest computational time complexity.
4.2 REDUCING THE NUMBER OF FORWARDING NODES
In the sender-based broadcasting algorithms, each broadcasting node attaches a list of its selected forwarding nodes to the message before broadcasting it. This procedure will increase the bandwidth and power required to broadcast the message. As shown earlier, our proposed slice-based selection algorithm reduces the number of selected forwarding nodes to 11 in the worst case. In this section, we show how to further reduce the number of selected nodes.
4.3 MAXIMIZING THE MINIMUM NODE WEIGHT OF B-COVERAGE SET
Suppose node NA assigns a weight to each of its neighbors. The weight can represent the neighbor's battery lifetime, its distance to NA, the average delay of the node, the level of trust, or a combination of them. In some scenarios, we may desire to find a B-coverage set such that its minimum node weight is the maximum or its maximum node weight is the minimum among that of all B-coverage sets. For example, assume that the weight of each node represents its battery lifetime in a wireless network. It may be desirable to select the nodes with a higher battery lifetime to forward the message in order to keep the nodes with a lower battery lifetime alive. Algorithm 3 shows how to find a B-coverage set such that its minimum node weight is the maximum among that of all B-coverage sets. A similar approach can be used to find a B-coverage set such that its maximum node weight is the minimum.
4.4 SIMILARITY WITH A TOPOLOGY CONTROL ALGORITHM
In  and , the authors proposed a cone-based topology control algorithm, where each node makes local decisions about its transmission power. The objective of the algorithm is to minimize the transmission power of each node without violating the network connectivity. In order to do that, each node NA transmits with the minimum power P such that in every nonempty cone of degree around NA, there is some node that NA can reach with power P. A cone is nonempty if there is at least a node in the cone that NA can reach using its maximum power.
4.5 A HIGHLY EFFICIENT RECEIVER-BASED BROADCASTING ALGORITHM
In this section, we propose a novel receiver-based broadcasting algorithm that can significantly reduce redundant broadcasts in the network. As mentioned earlier, in receiver-based broadcasting algorithms, the receiver of the message decides whether or not to broadcast the message. Therefore, a potential advantage of receiver-based broadcasting algorithms over sender-based ones is that they do not increase the size of the message by adding a list of forwarding nodes.
V. ALGORITHM STRUCTURE
Algorithm 4 shows a general approach used in several receiver-based broadcasting algorithms , . Our proposed receiver-based broadcasting algorithm employs this approach. Clearly, the main design challenge of Algorithm 4 is to determine whether or not to broadcast a received message. A trivial algorithm is to refrain broadcasting if and only if all the neighbors have received the message during the defer period.
5.1 RESPONSIBILITY-BASED SCHEME
Algorithm 5 shows the proposed RBS. The main idea of Algorithm 5 is that a node avoids broadcasting if it is not responsible for any of its neighbors. A node NA is not responsible for a neighbor NB if NB has received the message or if there is another neighbor NC such that NC has received the message and NB is closer to NC than it is to NA. Suppose NA stores IDs of all its neighbors that have broadcast the message during the defer period.
5.2 A PROPERTY OF THE PROPOSED RBS
In the simulation section, we show that the proposed RBS can significantly reduce the number of broadcasts in the network. In particular, our simulation shows that using RBS, the average number of broadcasts is less than one of the best known approximations for the minimum number of required broadcasts. To justify this, we prove a property of the proposed RBS.
5.3 RELAXING SOME SYSTEM MODEL ASSUMPTIONS
We assumed in Section 2 that the nodes are placed in a 2D plane. However, this assumption is not used in the proof of Theorem 6. Therefore, the proposed receiver-based algorithm can also achieve full delivery when the nodes are distributed in a 3D space. Note that in this case, RBS uses 3D node positions. We can also relax the assumption that all the nodes have the same transmission range R. When the nodes' transmission ranges are different, the topology graph should be defined as a directed graph for which there is a link from NA to NB if NB is in the transmission range of NA. Suppose G is an undirected graph obtained by removing unidirectional links of the topology graph. We assume that G is connected and define two nodes as neighbors if there is a link between them in G (i.e., they are in the transmission range of each other). Note that many wireless MAC protocols such as IEEE 802.11 require bidirectional links. Let us assume that nodes put not only their ID and position but also their transmission range into the hello messages that they periodically broadcast. Therefore, the neighbors of a node know both its position and transmission range. In this case, nodes can use Algorithm 6 to decide whether or not to broadcast.
5.4 PERFORMANCE OF PROPOSED SENDER-BASED AND RECEIVER-BASED ALGORITHMS
The main objective of efficient broadcasting algorithms is to reduce the number of broadcasts. Therefore, we considered the ratio of broadcasting nodes over the total number of nodes as the metric to evaluate the performance of the proposed broadcasting algorithms. Using the ns-2 simulator, we evaluated this metric against two parameters: transmission range and node density.
We repeated the simulation to consider a few more scenarios. In the first scenario, we changed the node distribution from a uniform to a 2D Gaussian distribution. Both the center and the variance of the Gaussian distribution were randomly selected for each run. The variance was selected from the range 200-400 to avoid a very dense population of nodes around the center of the distribution. As shown in Fig. 17, the number of broadcasting nodes decreases for all the broadcasting algorithms when a Gaussian distribution is used to distribute the nodes in the region. The simulation results indicate that the RBS algorithm still performs significantly better than other broadcasting algorithms considered in this work.
In this paper, we use the realistic model for wireless communication of  to design algorithms for broadcasting and information gathering in wireless ad-hoc networks. The natural next steps would be to directly address node mobility and node faults, and to study more complex communication tasks such as anycasting, we proposed a forwardingnode selection algorithm that selects at most 11 nodes in O(n), where n is the number of neighbors. This limited number of nodes is an improvement over Liu et al.'s algorithm, which selects n nodes in the worst case and has time complexity O(n) log n. Moreover, we showed that our proposed forwarding-node selection algorithm results in fewer broadcasts in the network. In the second part of the paper, we proposed an efficient receiver-based algorithm and showed why it significantly reduces the number of forwarding nodes in the network. We also relaxed some system model assumptions that are typically used in the broadcasting algorithms. Interestingly, the 2-hop-based version of our proposed receiver-based algorithm can guarantee constant approximation to the optimal solution (minimum CDS). As far as the authors know, this is the first broadcasting algorithm that constructs a CDS "on the fly" and can guarantee both full delivery and a constant approximation ratio to the optimal solution. As part of our future work, we will investigate the necessary conditions to guarantee both full delivery and constant approximation ratio to the minimum CDS.
 C. Perkins, Ad Hoc on Demand Distance Vector (AODV) Routing, IETF Internet draft, work in progress, 1997.
 D. Johnson and D. Maltz, "Dynamic Source Routing in Ad Hoc Wireless Networks," Mobile Computing, T. Imielinski and H.F. Korth, eds., Kluwer Academic Publishers, 1996.
 S. Ni, Y. Tseng, Y. Chen, and J. Sheu, "The Broadcast Storm Problem in a Mobile Ad Hoc Network," Proc. ACM MobiCom '99, pp. 151-162, 1999.
 M. Garey and D. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman, 1990.  B. Clark, C. Colbourn, and D. Johnson, "Unit Disk Graphs," Discrete Math., vol. 86, pp. 165-177, 1990.
 P. Wan, K. Alzoubi, and O. Frieder, "Distributed Construction of Connected Dominating Set in Wireless Ad Hoc Networks," Proc. IEEE INFOCOM '02, vol. 3, pp. 1597-1604, 2002.
 S. Funke, A. Kesselman, U. Meyer, and M. Segal, "A Simple Improved Distributed Algorithm for Minimum CDS in Unit Disk Graphs," ACM Trans. Sensor Networks, vol. 2, no. 3, pp. 444-453, 2006.
 H. Liu, P. Wan, X. Jia, X. Liu, and F. Yao, "Efficient Flooding Scheme Based on 1-Hop Information in Mobile Ad Hoc Networks," Proc. IEEE INFOCOM, 2006.
 Y. Tseng, S. Ni, and E. Shih, "Adaptive Approaches to Relieving Broadcast Storms in a Wireless Multihop Mobile Ad Hoc Networks," Proc. 21st Int'l Conf. Distributed Computing Systems (ICDCS '01), pp. 481-488, 2001.
 Y. Sasson, D. Cavin, and A. Schiper, "Probabilistic Broadcast for Flooding in Wireless Mobile Ad Hoc Networks," Proc. IEEE Wireless Comm. and Networking Conf. (WCNC '03), pp. 1124-1130, 2003.
 W. Lou and J. Wu, "Double-Covered Broadcast (DCB): A Simple Reliable Broadcast Algorithm in Manets," Proc. IEEE INFOCOM '04, pp. 2084-2095, 2004.
 J. Wu and F. Dai, "Broadcasting in Ad Hoc Networks Based on Self-Pruning," Proc. IEEE INFOCOM '03, pp. 2240-2250, 2003.
 W. Peng and X. Lu, "On the Reduction of Broadcast Redundancy in Mobile Ad Hoc Networks," Proc. ACM MobiHoc '00, pp. 129-130, 2000.
 T. He, C. Huang, B. Blum, J. Stankovic, and T. Abdelzaher, "Range-Free Localization Schemes in Large Scale Sensor Networks," Proc. ACM MobiCom '03, pp. 81-95, 2003.
 A. Keshavarz-Haddad, V. Ribeiro, and R. Riedi, "DRB and DCCB: Efficient and Robust Dynamic Broadcast for Ad Hoc and Sensor Networks," Proc. Fourth Ann. IEEE Conf. Sensor, Mesh and Ad Hoc Comm. and Networks (SECON '07), June 2007.
 R. Wattenhofer, L. Li, P. Bahl, and Y. Wang, "Distributed Topology Control for Power Efficient Operation in Multihop Wireless Ad Hoc Networks," Proc. IEEE INFOCOM '01, pp. 1388-1397, 2001.
 L. Li, J. Halpern, P. Bahl, Y. Wang, and R. Wattenhofer, "A Cone- Based Distributed Topology-Control Algorithm for Wireless Multi-Hop Networks," IEEE/ACM Trans. Networking, vol. 13, pp. 147-159, 2005.
 M. Sun, W. Feng, and T. Lai, "Broadcasting in Ad Hoc Networks Based on Self-Pruning," Proc. IEEE Global Telecomm. Conf. (GLOBECOM '01), pp. 2842-2846, 2001.
 A. Papoulis, Probability and Statistics. Prentice Hall, 1990.
 R. Chang and R. Lee, "On the Average Length of Delaunay Triangulations," BIT Numerical Math., vol. 24, pp. 269-273, 1984.