4th International ICST Symposium on Modeling and Optimization in Mobile, Ad Hoc, and Wireless Networks

Research Article

Color-Based Broadcasting for Ad Hoc Networks

  • @INPROCEEDINGS{10.1109/WIOPT.2006.1666475,
        author={Alireza  Keshavarz-Haddad and Vinay  Ribeiro and Rudolf  Riedi},
        title={Color-Based Broadcasting for Ad Hoc Networks},
        proceedings={4th International ICST Symposium on Modeling and Optimization in Mobile, Ad Hoc, and Wireless Networks},
  • Alireza Keshavarz-Haddad
    Vinay Ribeiro
    Rudolf Riedi
    Year: 2006
    Color-Based Broadcasting for Ad Hoc Networks
    DOI: 10.1109/WIOPT.2006.1666475
Alireza Keshavarz-Haddad1,2, Vinay Ribeiro1,2, Rudolf Riedi1,2
  • 1: Department of Electrical and Computer Engineering† and Department of Statistics
  • 2: Rice University, 6100 Main Street, Houston, TX 77005, USA


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 back-bones 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.