Abstract-This paper develops a novel color-based broadcast scheme for wireless ad hoc networks where each forwarding of the broadcast message is assigned a color from a given pool of colors. A node only forwards the message if it can assign it a color from the pool which it has not already overheard after a random time. In the closely related counter-based broadcast scheme a node simply counts the number of broadcasts not the colors overheard. The forwarding nodes form a so-called backbone, which is determined by the random timers and, thus, is random itself. Notably, any counter-generated backbone could result from pruning a color-generated backbone; the typical color-generated backbone, however, exhibits a connectivity graph richer than the counter-based ones. As a particular advantage, the colors reveal simple geometric properties of the backbones which we exploit to prove that the size of both, color-and counter-generated backbones are within a small constant factor of the optimum. We also propose two techniques, boosting and edge-growing, that improve the performance of color-and counter-based broadcast in terms of reachability and number of rebroadcasts. Experiments reveal that the powerful boosting method is considerably more effective with the color-based schemes. In ad hoc networks, broadcast plays a crucial role, relaying a message generated by one node to all other nodes. Several unicast routing protocols such Dynamic Source Routing (DSR), Ad Hoc On Demand Distance Vector (AODV), Zone Routing Protocol (ZRP), and Location Aided Routing (LAR), as well as multicast protocols employ broadcasting to detect and maintain routes in an ever changing environment. The simplest approach for broadcasting is flooding, where each node rebroadcasts a message as soon as it receives it for the first time. While ensuring a high success rate in reaching all nodes, flooding produces redundant broadcast messages. This redundancy can become overwhelming in dense wireless networks, leading to a loss of precious bandwidth and battery power and to a dramatic degradation of performance, a situation called "broadcast storm" [1] . Several broadcast schemes have been developed that avoid broadcast storms. The performance of these schemes is measured in terms of reachability, that is the fraction of the total nodes that receive the broadcast message, the number of rebroadcasts, that is the number of nodes that forward the message, and the latency, that is the time between the first and last instant that the broadcast message is transmitted. The set of nodes which forward the broadcast message form the socalled backbone. Good broadcast schemes ensure reachability close to 1 and simultaneously a small backbone. Broadcast Probabilistic schemes, in contrast, rebuild a backbone from scratch during each broadcast. Nodes make instantaneous local decisions about whether to broadcast a message or not using information derived only from overheard broadcast messages. Consequently these schemes incur a smaller overhead and demonstrate superior adaptivity in changing environments when compared to deterministic schemes [13] . However, they typically must sacrifice in terms of reachability as a trade-off against overhead. The probabilistic schemes that have been proposed so far are probability-based, counter-based, distance-based and location-based schemes [1], [14] , [15] . In probability-based schemes every node that receives the message rebroadcast it with probability P thr . In the other schemes, when a node hears a broadcast message for the first time, it starts a timer of random duration. At the instant this timer expires the node rebroadcasts the message if and only if a "rebroadcast condition" is satisfied. This rebroadcast condition is defined by the different schemes as follows: the node received strictly less than η copies of the message (counter-based), the node did not receive the message from another node at a geographic distance less than d thr (distance-based) the geographical area within the node's range that is yet to be covered by the broadcast exceeds a thr (location-based). There have been several efforts to develop improved probabilistic schemes that choose appropriate thresholds and combine the above mentioned schemes [16]-[18]. The literature hitherto, however, contains very little theoretical analysis of probabilistic schemes. The first contribution of this paper consists of a novel coloring paradigm for broadcast. Using this paradigm we construct and study an efficient probabilistic scheme called color-based broadcast. Notably, the coloring paradigm imprints a structure on the backbones which facilitates a rigorous approach of issues regarding the optimality of the afore mentioned schemes. Having such a powerful and general analytical framework at the researcher's disposal marks an important step forward in this field where analytical work has been hindered to some extent by the complexity of the space of probabilistic backbones. 0-7803-9550-6/06/$20.00
The color-based scheme has been recently proposed in REF .
Color-Based Broadcasting for Ad Hoc Networks
2006 4th International Symposium on Modeling and Optimization in Mobile, Ad Hoc and Wireless Networks
2006 4th International Symposium on Modeling and Optimization in Mobile, Ad Hoc and Wireless Networks
Computer Science