Performance Analysis of the Hierarchical Layer Graph for Wireless Networks
- 422 Downloads
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.
KeywordsWireless Network Transmission Range Topology Control Leader Election Unit Disk Graph
Unable to display preview. Download preview PDF.
- 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
- 3.Haykin, S., Moher, M.: Modern Wireless Communications. Prentice-Hall, Englewood Cliffs (2004)Google Scholar
- 5.Leighton, F.T.: Introduction to Parallel Algorithms and Architectures Arrays, Trees, Hypercubes. Morgan Kaufmann Publishers, Inc., San Mateo (1992)Google Scholar
- 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.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.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.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.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.Rajaraman, R.: Topology Control and Routing in Ad hoc Networks: A Survey. In: SIGACT News, pp. 60–73 (June 2002)Google Scholar
- 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
- 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