Performance Analysis of the Hierarchical Layer Graph for Wireless Networks

  • Stefan Rührup
  • Christian Schindelhauer
  • Klaus Volbert
Conference paper
Part of the Lecture Notes in Computer Science book series (LNCS, volume 3738)


The Hierarchical Layer Graph (HL graph) is a promising network topology for wireless networks with variable transmission ranges. It was introduced and analyzed by Meyer auf der Heide et al. 2004. In this paper we present a distributed, localized and resource-efficient algorithm for constructing this graph. The qualtiy of the HL graph depends on the domination radius and the publication radius, which affect the amount of interference in the network. These parameters also determine whether the HL graph is a c-spanner, which implies an energy-efficient topology. We investigate the performance on randomly distributed node sets and show that the restrictions on these parameters derived from a worst case analysis are not so tight using realistic settings. Here, we present the results of our extensive experimental evaluation, measuring congestion, dilation and energy. Congestion includes the load that is induced by interfering edges. We distinguish between congestion and realistic congestion where we also take the signal-to-interference ratio into account. Our experiments show that the HL graph contains energy-efficient paths as well as paths with a few number of hops while preserving a low congestion.


Wireless Network Transmission Range Topology Control Leader Election Unit Disk Graph 
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.


Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.


  1. 1.
    Clementi, A.E.F., Penna, P., Silvestri, R.: On the power assignment problem in radio networks. Electronic Colloquium on Computational Complexity, ECCC 2000 (2000)Google Scholar
  2. 2.
    Grünewald, M., Lukovszki, T., Schindelhauer, C., Volbert, K.: Distributed Maintenance of Resource Efficient Wireless Network Topologies (Ext. Abstract). In: Monien, B., Feldmann, R.L. (eds.) Euro-Par 2002. LNCS, vol. 2400, pp. 935–946. Springer, Heidelberg (2002)CrossRefGoogle Scholar
  3. 3.
    Haykin, S., Moher, M.: Modern Wireless Communications. Prentice-Hall, Englewood Cliffs (2004)Google Scholar
  4. 4.
    Kirousis, L.M., Kranakis, E., Krizanc, D., Pelc, A.: Power consumption in packet radio networks. Theoretical Computer Science 243(1-2), 289–305 (2000)zbMATHCrossRefMathSciNetGoogle Scholar
  5. 5.
    Leighton, F.T.: Introduction to Parallel Algorithms and Architectures Arrays, Trees, Hypercubes. Morgan Kaufmann Publishers, Inc., San Mateo (1992)Google Scholar
  6. 6.
    Li, X.-Y.: Applications of Computational Geometry in Wireless Ad Hoc Networks. In: Cheng, X.Z., Huang, X., Du, D.-Z. (eds.) Ad Hoc Wireless Networking. Kluwer, Dordrecht (2003)Google Scholar
  7. 7.
    Li, X.-Y.: Topology Control in Wireless Ad Hoc Networks. In: Basagni, S., Conti, M., Giordano, S., Stojmenovic, I. (eds.) Ad Hoc Networking. IEEE Press, Los Alamitos (2003)Google Scholar
  8. 8.
    Li, X.-Y.: Wireless Sensor Networks and Computational Geometry. In: Ilyas, M., et al. (eds.) Sensor Networks. CRC Press, Boca Raton (2003)Google Scholar
  9. 9.
    Meyer auf der Heide, F., Schindelhauer, C., Volbert, K., Grünewald, M.: Energy, Congestion and Dilation in Radio Networks. In: 14th ACM Symposium on Parallel Algorithms and Architectures (SPAA 2002), pp. 230–237 (2002)Google Scholar
  10. 10.
    Meyer auf der Heide, F., Schindelhauer, C., Volbert, K., Grünewald, M.: Congestion, Dilation, and Energy in Radio Networks. In: Theory of Computing Systems (TOCS 2004), vol. 37(3), pp. 343–370 (2004)Google Scholar
  11. 11.
    Rajaraman, R.: Topology Control and Routing in Ad hoc Networks: A Survey. In: SIGACT News, pp. 60–73 (June 2002)Google Scholar
  12. 12.
    Rührup, S., Schindelhauer, C., Volbert, K., Grünewald, M.: Performance of Distributed Algorithms for Topology Control in Wireless Networks. In: 17th Int. Parallel and Distributed Processing Symposium (IPDPS 2003), pp. 28.2 (2003)Google Scholar
  13. 13.
    Schindelhauer, C., Volbert, K., Ziegler, M.: Spanners, Weak Spanners, and Power Spanners for Wireless Networks. In: Fleischer, R., Trippen, G. (eds.) ISAAC 2004. LNCS, vol. 3341, pp. 805–821. Springer, Heidelberg (2004)CrossRefGoogle Scholar
  14. 14.
    Volbert, K.: A Simulation Environment for Ad Hoc Networks Using Sector Subdivision. In: 10th Euromicro Workshop on Parallel, Distributed and Network-based Processing (PDP 2002), pp. 419–426 (2002)Google Scholar

Copyright information

© Springer-Verlag Berlin Heidelberg 2005

Authors and Affiliations

  • Stefan Rührup
    • 1
  • Christian Schindelhauer
    • 1
  • Klaus Volbert
    • 1
  1. 1.Heinz Nixdorf InstituteUniversity of PaderbornGermany

Personalised recommendations