Does topology control reduce interference?

ABSTRACT

Topology control in ad-hoc networks tries to lower node energy consumption by reducing transmission power and by confining interference, collisions and consequently retransmissions. Commonly low interference is claimed to be a consequence to sparseness of the resulting topology. In this paper we disprove this implication. In contrast to most of the related work claiming to solve the interference issue by graph sparseness without providing clear argumentation or proofs, we provide a concise and intuitive definition of interference. Based on this definition we show that most currently proposed topology control algorithms do not effectively constrain interference. Furthermore we propose connectivity-preserving an spanner constructions that are interference-minimal.

REFERENCES

• 1: Khaled M. Alzoubi , Peng-Jun Wan , Ophir Frieder, Message-optimal connected dominating sets in mobile ad hoc networks, Proceedings of the 3rd ACM international symposium on Mobile ad hoc networking & computing, June 09-11, 2002, Lausanne, Switzerland [doi>10.1145/513800.513820]
• 2: Lichun Bao , J. J. Garcia-Luna-Aceves, Topology management in ad hoc networks, Proceedings of the 4th ACM international symposium on Mobile ad hoc networking & computing, June 01-03, 2003, Annapolis, Maryland, USA [doi>10.1145/778415.778432]
• 3: Douglas M. Blough , Mauro Leoncini , Giovanni Resta , Paolo Santi, The lit K-neigh protocol for symmetric topology control in ad hoc networks, Proceedings of the 4th ACM international symposium on Mobile ad hoc networking & computing, June 01-03, 2003, Annapolis, Maryland, USA [doi>10.1145/778415.778433]
• 4: Prosenjit Bose , Pat Morin , Ivan Stojmenović , Jorge Urrutia, Routing with guaranteed delivery in ad hoc wireless networks, Proceedings of the 3rd international workshop on Discrete algorithms and methods for mobile computing and communications, p.48-55, August 20-20, 1999, Seattle, Washington, United States [doi>10.1145/313239.313282]
• 5: Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
• 6: K. Gabriel and R. Sokal. A New Statistical Approach to Geographic Variation Analysis. Systematic Zoology, 18:259--278, 1969.
• 7: T. Hou and V. Li. Transmission Range Control in Multihop Packet Radio Networks. IEEE Transactions on Communications, 34(1):38--44, 1986.
• 8: L. Hu. Topology Control for Multihop Packet Radio Networks. IEEE Trans. on Communications, 41(10), 1993.
• 9: L. Jia, R. Rajaraman, and R. Suel. An Efficient Distributed Algorithm for Constructing Small Dominating Sets. In Proc. of the 20th ACM Symposium on Principles of Distributed Computing (PODC), pages 33--42, 2001.
• 10: Brad Karp , H. T. Kung, GPSR: greedy perimeter stateless routing for wireless networks, Proceedings of the 6th annual international conference on Mobile computing and networking, p.243-254, August 06-11, 2000, Boston, Massachusetts, United States [doi>10.1145/345910.345953]
• 11: V. Kawadia and P. Kumar. Power Control and Clustering in Ad Hoc Networks. In Proc. of the 22nd Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM), 2003.
• 12: Fabian Kuhn , Roger Wattenhofer, Constant-time distributed dominating set approximation, Proceedings of the twenty-second annual symposium on Principles of distributed computing, p.25-32, July 13-16, 2003, Boston, Massachusetts [doi>10.1145/872035.872040]
• 13: Fabian Kuhn , Roger Wattenhofer , Yan Zhang , Aaron Zollinger, Geometric ad-hoc routing: of theory and practice, Proceedings of the twenty-second annual symposium on Principles of distributed computing, p.63-72, July 13-16, 2003, Boston, Massachusetts [doi>10.1145/872035.872044]
• 14: N. Li, C.-J. Hou, and L. Sha. Design and Analysis of an MST-Based Topology Control Algorithm. In Proc. of the 22nd Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM), 2003.
• 15: X.-Y. Li, G. Calinescu, and P.-J. Wan. Distributed Construction of Planar Spanner and Routing for Ad Hoc Wireless Networks. In Proc. of the 21st Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM), 2002.
• 16: Friedhelm Meyer auf de Heide , Christian Schindelhauer , Klaus Volbert , Matthias Grünewald, Energy, congestion and dilation in radio networks, Proceedings of the fourteenth annual ACM symposium on Parallel algorithms and architectures, August 10-13, 2002, Winnipeg, Manitoba, Canada [doi>10.1145/564870.564910]
• 17: David Peleg, Distributed computing: a locality-sensitive approach, Society for Industrial and Applied Mathematics, Philadelphia, PA, 2000
• 18: Ravi Prakash, Unidirectional links prove costly in wireless ad hoc networks, Proceedings of the 3rd international workshop on Discrete algorithms and methods for mobile computing and communications, p.15-22, August 20-20, 1999, Seattle, Washington, United States [doi>10.1145/313239.313263]
• 19: R. Ramanathan and R. Rosales-Hain. Topology Control of Multihop Wireless Networks Using Transmit Power Adjustment. In Proc. of the 19th Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM), 2000.
• 20: V. Rodoplu and T. H. Meng. Minimum energy mobile wireless networks. IEEE J. Selected Areas in Communications, 17(8), 1999.
• 21: H. Takagi and L. Kleinrock. Optimal Transmission Ranges for Randomly Distributed Packet Radio Terminals. IEEE Transactions on Communications, 32(3):246--257, 1984.
• 22: G. Toussaint. The Relative Neighborhood Graph of a Finite Planar Set. Pattern Recognition, 12(4):261--268, 1980.
• 23: Yu Wang , Xiang-Yang Li, Localized construction of bounded degree and planar spanner for wireless ad hoc networks, Proceedings of the 2003 joint workshop on Foundations of mobile computing, p.59-68, September 19, 2003, San Diego, CA, USA [doi>10.1145/941079.941088]
• 24: R. Wattenhofer, L. Li, P. Bahl, and Y.-M. Wang. Distributed Topology Control for Power Efficient Operation in Multihop Wireless Ad Hoc Networks. In Proc. of the 20th Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM), pages 1388--1397, 2001.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Wireless communication

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

General Terms:
Algorithms, Theory

Keywords:
ad-hoc networks, interference, network connectivity, network spanners, topology control