Minimum Energy Broadcast and Disk Cover in Grid Wireless Networks

(Extended Abstract)
  • Tiziana Calamoneri
  • Andrea E. F. Clementi
  • Miriam Di Ianni
  • Massimo Lauria
  • Angelo Monti
  • Riccardo Silvestri
Conference paper
Part of the Lecture Notes in Computer Science book series (LNCS, volume 4056)


The Minimum Energy Broadcast problem consists in finding the minimum-energy range assignment for a given set S of n stations of an ad hoc wireless network that allows a source station to perform broadcast operations over S.

We prove a nearly tight asymptotical bound on the optimal cost for the Minimum Energy Broadcast problem on square grids. We emphasize that finding tight bounds for this problem restriction is far to be easy: it involves the Gauss’s Circle problem and the Apollonian Circle Packing. We also derive near-tight bounds for the Bounded-Hop version of this problem. Our results imply that the best-known heuristic, the MST-based one, for the Minimum Energy Broadcast problem is far to achieve optimal solutions (even) on very regular, well-spread instances: its worst-case approximation ratio is about π and it yields \(\Omega(\sqrt{n})\) hops.

As a by product, we get nearly tight bounds for the Minimum Disk Cover problem and for its restriction in which the allowed disks must have non-constant radius.

Finally, we emphasize that our upper bounds are obtained via polynomial time constructions.


Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.


  1. 1.
    Ambühl, C.: An optimal bound for the MST algorithm to compute energy efficient broadcast trees in wireless networks. In: Caires, L., Italiano, G.F., Monteiro, L., Palamidessi, C., Yung, M. (eds.) ICALP 2005. LNCS, vol. 3580, pp. 1139–1150. Springer, Heidelberg (2005)CrossRefGoogle Scholar
  2. 2.
    Balakrishnan, A., Altinkemer, K.: Using a hop-constrained model to generate alternative communication network design. ORSA Journal of Computing 4, 147–159 (1992)Google Scholar
  3. 3.
    Calamoneri, T., Clementi, A., Di Ianni, M., Lauria, M., Monti, A., Silvestri, R.: Minimum Energy Broadcast and Disk Cover in Grid Wireless Networks (Full Version), available at
  4. 4.
    Cǎlinescu, G., Li, X.Y., Frieder, O., Wan, P.J.: Minimum-Energy Broadcast Routing in Static Ad Hoc Wireless Networks. In: Proc. of 20th IEEE INFOCOM, pp. 1162–1171 (April 2001)Google Scholar
  5. 5.
    Clementi, A., Crescenzi, P., Penna, P., Rossi, G., Vocca, P.: On the Complexity of Computing Minimum Energy Consumption Broadcast Subgraphs. In: Ferreira, A., Reichel, H. (eds.) STACS 2001. LNCS, vol. 2010, pp. 121–131. Springer, Heidelberg (2001)CrossRefGoogle Scholar
  6. 6.
    Clementi, A., Huiban, G., Penna, P., Rossi, G., Verhoeven, Y.C.: On the Approximation Ratio of the MST-based Heuristic for the Energy-Efficient Broadcast Problem in Static Ad-Hoc Radio Networks. In: Proc. of 3rd IEEE Intern. Workshop on Wireless, Mobile and Ad Hoc Networks (WMAN 2003) (2003)Google Scholar
  7. 7.
    Clementi, A., Huiban, G., Penna, P., Rossi, G., Verhoeven, Y.: Some Recent Theoretical Advances and Open Questions on Energy Consumption in Static Ad-Hoc in Wireless Networks. In: Proc. of 3rd Int. Workshop ARACNE, Carleton Scientific, pp. 23–38 (2002)Google Scholar
  8. 8.
    Clementi, A., Penna, P., Silvestri, R.: On the Power Assignment Problem in Radio Networks. Mobile Networks and Applications (MONET) 9, 125–140 (2004)CrossRefGoogle Scholar
  9. 9.
    Crescenzi, P., Kann, V.: A Compendium of NP Optimization Problems,
  10. 10.
    Ephremides, A., Nguyen, G.D., Wieselthier, J.E.: On the Construction of Energy-Efficient Broadcast and Multicast Trees in Wireless Networks. In: Proc. of 19th IEEE INFOCOM, pp. 585–594 (2000)Google Scholar
  11. 11.
    Flammini, M., Navarra, A., Pérénnes, S.: The “Real” Approximation Factor of the MST Heuristic for the Minimum Energy Broadcasting. In: Nikoletseas, S.E. (ed.) WEA 2005. LNCS, vol. 3503, pp. 22–31. Springer, Heidelberg (2005)CrossRefGoogle Scholar
  12. 12.
    Gouveia, L.: Using the Miller-Tucker-Zemlin constraints to formulate a minimal spanning tree problem with hop-constraint. European Journal of Operational Research 95, 170–190 (2001)Google Scholar
  13. 13.
    Graham, R.L., Lagarias, J.C., Mallows, C.L., Wilks, A.R., Yan, C.H.: Apollonian Circle Packings: Number Theory. J. Number Theory 100, 1–45 (2003)zbMATHCrossRefMathSciNetGoogle Scholar
  14. 14.
    Haenggi, M.: Twelve Reasons not to Route over Many Short Hops. In: Proc. of IEEE Vehicular Technology Conference (VTC 2004 Fall) (5), pp. 3130–3134 (2004)Google Scholar
  15. 15.
    Hilbert, D., Cohn-Vossen, S.: Geometry and the Immagination, Chelsea, pp. 33–35 (1999)Google Scholar
  16. 16.
    Hochbaum, D.S., Maass, W.: Approximation Schemes for Covering and Packing problems in Image Processing and VLSI. Journal of ACM 32, 130–136 (1985)zbMATHCrossRefMathSciNetGoogle Scholar
  17. 17.
    Huxley, M.N.: Exponential sums and lattice points. Proc. London Math. Soc. 60, 471–502 (1990)zbMATHCrossRefMathSciNetGoogle Scholar
  18. 18.
    Kirousis, L.M., Kranakis, E., Krizanc, D., Pelc, A.: Power Consumption in Packet Radio Networks. Theoretical Computer Science 243, 289–305 (2000)zbMATHCrossRefMathSciNetGoogle Scholar
  19. 19.
    Kranakis, E., Krizanc, D., Pelc, A.: Fault-tolerant broadcasting in radio networks. Journal of Algorithms 39, 47–67 (2001)zbMATHCrossRefMathSciNetGoogle Scholar
  20. 20.
    Pahlavan, K., Levesque, A.: Wireless Information Networks. Wiley-Interscience, Chichester (1995)Google Scholar
  21. 21.
    Söderberg, B.: Apollonian Tiling, the Lorentz Group, and Regular Trees. Physical Review A 46, 1859–1866 (1992)CrossRefMathSciNetGoogle Scholar
  22. 22.
    Voss, S.: The steiner tree problem with hop constraint. Annals of Operations Research 86, 321–345 (1999)zbMATHCrossRefMathSciNetGoogle Scholar

Copyright information

© Springer-Verlag Berlin Heidelberg 2006

Authors and Affiliations

  • Tiziana Calamoneri
    • 2
  • Andrea E. F. Clementi
    • 1
  • Miriam Di Ianni
    • 1
  • Massimo Lauria
    • 2
  • Angelo Monti
    • 2
  • Riccardo Silvestri
    • 2
  1. 1.Dipartimento di MatematicaUniversità degli Studi di Roma“Tor Vergata” 
  2. 2.Dipartimento di InformaticaUniversità degli Studi di Roma “La Sapienza” 

Personalised recommendations