Algorithmic models of interference in wireless ad hoc and sensor networks

ABSTRACT

Among the most critical issues of wireless ad hoc and sensor networks are energy consumption in general and interfer-ence in particular. The reduction of interference is consequently considered one of the foremost goals of topology control. Almost all of the related work however considers this issue implicitly: Low interference is often claimed to be a consequence of sparseness or low degree of the constructed topologies. This paper, in contrast, studies explicit definitions of interference. Various models of in-terference--both from a sender-centric and a receiver-centric per-spective--are proposed, compared, and analyzed with respect to their algorithmic properties and complexities.

REFERENCES

• 1: Martin Burkhart , Pascal von Rickenbach , Roger Wattenhofer , Aaron Zollinger, Does topology control reduce interference?, Proceedings of the 5th ACM international symposium on Mobile ad hoc networking and computing, May 24-26, 2004, Roppongi Hills, Tokyo, Japan [doi>10.1145/989459.989462]
• 2: M. Fussen, R. Wattenhofer, and A. Zollinger, "Interference arises at the receiver," presented at the Int. Conf. Wireless Networks, Commu-nications, and Mobile Computing (WirelessCom 2005), Maui, HI, Jun. 2005.
• 3: T. Hou and V. Li, "Transmission range control in multihop packet radio networks," IEEE Trans. Commun., vol. 34, no. 1, pp. 38-44, Jan. 1986.
• 4: H. Takagi and L. Kleinrock, "Optimal transmission ranges for ran-domly distributed packet radio terminals," IEEE Trans. Commun., vol. 32, no. 3, pp. 246-257, Mar. 1984.
• 5: L. Hu, "Topology control for multihop packet radio networks," IEEE Trans. Commun., vol. 41, no. 10, pp. 1474-1481, Oct. 1993.
• 6: R. Ramanathan and R. Rosales-Hain, "Topology control of multihop wireless networks using transmit power adjustment," in Proc. IEEE INFOCOM, 2000, vol. 2, pp. 404-413.
• 7: S. Borbash and E. Jennings, "Distributed topology control algorithm for multihop wireless networks," in Proc. 2002 Int. Joint Conf. Neural Networks (IJCNN), May 2002, vol. 1, pp. 355-360.
• 8: V. Rodoplu and T. H. Meng, "Minimum energy mobile wireless net-works," IEEE J. Sel. Areas Commun., vol. 17, no. 8, pp. 1333-1344, Aug. 1999.
• 9: E. Kranakis, H. Singh, and J. Urrutia, "Compass routing on geometric networks," in Proc. 11th Canadian Conf. Computational Geometry, Vancouver, Canada, Aug. 1999, pp. 51-54 [Online]. Available: urlcite-seer.nj.nec.com/kranakis99compass.html
• 10: 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]
• 11: 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]
• 12: A. Zollinger, "Networking unleashed: Geographic routing and topology control in Ad Hoc and sensor networks," Ph.D. dissertation, ETH, Zurich, Switzerland, 2005, diss. ETH 16025.
• 13: R. Wattenhofer, L. Li, P. Bahl, and Y.-M. Wang, "Distributed topology control for power efficient operation in multihop wireless ad hoc net-works," in Proc. IEEE INFOCOM, 2001, pp. 1388-1397.
• 14: X.-Y. Li, G. Calinescu, and P.-J. Wan, "Distributed construction of planar spanner and routing for ad hoc wireless networks," in Proc. IEEE INFOCOM, 2002, vol. 3, pp. 1268-1277.
• 15: N. Li, C.-J. Hou, and L. Sha, "Design and analysis of an MST-based topology control algorithm," in Proc. IEEE INFOCOM, 2003, vol. 3, pp. 1702-1712.
• 16: 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]
• 17: Xiang-Yang Li , Wen-Zhan Song , Weizhao Wang, A unified energy-efficient topology for unicast and broadcast, Proceedings of the 11th annual international conference on Mobile computing and networking, August 28-September 02, 2005, Cologne, Germany [doi>10.1145/1080829.1080831]
• 18: R. Wattenhofer and A. Zollinger, "XTC: A practical topology control algorithm for ad hoc networks," presented at the 4th Int. Workshop on Algorithms for Wireless, Mobile, Ad Hoc and Sensor Networks (WMAN), Santa Fe, NM, Apr. 2004.
• 19: Douglas M. Blough , Mauro Leoncini , Giovanni Resta , Paolo Santi, The 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]
• 20: Jie Gao , Leonidas Guibas , John Hershberger , Li Zhang , An Zhu, Discrete mobile centers, Proceedings of the seventeenth annual symposium on Computational geometry, p.188-196, June 2001, Medford, Massachusetts, United States [doi>10.1145/378583.378666]
• 21: Jie Gao , Leonidas J. Guibas , John Hershberger , Li Zhang , An Zhu, Geometric spanner for routing in mobile networks, Proceedings of the 2nd ACM international symposium on Mobile ad hoc networking & computing, October 04-05, 2001, Long Beach, CA, USA [doi>10.1145/501422.501424]
• 22: L. Jia, R. Rajaraman, and R. Suel, "An efficient distributed algorithm for constructing small dominating sets," in Proc. 20th ACM Symp. Prin-ciples of Distributed Computing (PODC), 2001, pp. 33-42.
• 23: 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]
• 24: Hai Huang , Andréa W. Richa , Michael Segal, Approximation algorithms for the mobile piercing set problem with applications to clustering in ad-hoc networks, Proceedings of the 6th international workshop on Discrete algorithms and methods for mobile computing and communications, September 28-28, 2002, Atlanta, Georgia, USA [doi>10.1145/570810.570818]
• 25: Yu Wang , Xiang-Yang Li, Geometric Spanners for Wireless Ad Hoc Networks, Proceedings of the 22 nd International Conference on Distributed Computing Systems (ICDCS'02), p.171, July 02-05, 2002
• 26: 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]
• 27: Fabian Kuhn , Tim Nieberg , Thomas Moscibroda , Roger Wattenhofer, Local approximation schemes for ad hoc and sensor networks, Proceedings of the 2005 joint workshop on Foundations of mobile computing, September 02-02, 2005, Cologne, Germany [doi>10.1145/1080810.1080827]
• 28: V. Kawadia and P. Kumar, "Power control and clustering in ad hoc networks," presented at the 22nd IEEE INFOCOM, San Francisco, CA, 2003.
• 29: P. Santi, Topology Control in Wireless Ad Hoc and Sensor Networks. New York: Wiley, 2005.
• 30: 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]
• 31: National Research Council Staff, Embedded Everywhere: A Research Agenda for Networked Systems of Embedded Computers, National Academy Press, Washington, DC, 2001
• 32: I. F. Akyildiz , W. Su , Y. Sankarasubramaniam , E. Cayirci, Wireless sensor networks: a survey, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.38 n.4, p.393-422, 15 March 2002 [doi>10.1016/S1389-1286(01)00302-4]
• 33: C.-Y. Chong and S. P. Kumar, "Sensor networks: Evolution, oppor-tunities, and challenges," Proc. IEEE, vol. 91, no. 8, pp. 1247-1256, Aug. 2003.
• 34: Ashish Goel , Deborah Estrin, Simultaneous optimization for concave costs: single sink aggregation or single source buy-at-bulk, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
• 35: J. Chou, D. Petrovic, and K. Ramchandran, "A distributed and adaptive signal processing approach to reducing energy consumption in sensor networks," presented at the 22nd IEEE INFOCOM, San Francisco, CA, 2003.
• 36: Pascal von Rickenbach , Roger Wattenhofer, Gathering correlated data in sensor networks, Proceedings of the 2004 joint workshop on Foundations of mobile computing, October 01-01, 2004, Philadelphia, PA, USA [doi>10.1145/1022630.1022640]
• 37: P. von Rickenbach, S. Schmid, R. Wattenhofer, and A. Zollinger, "A robust interference model for wireless ad hoc networks," presented at the 5th Int. Workshop on Algorithms for Wireless, Mobile, Ad Hoc and Sensor Networks (WMAN), Denver, CO, Apr. 2005.
• 38: K. Moaveni-Nejad and X.-Y. Li, "Low-interference topology control for wireless ad hoc networks," presented at the 2nd IEEE Communica-tions Society Conf. Sensor and Ad Hoc Communications and Networks (SECON), Santa Clara, CA, 2005.
• 39: Thomas Moscibroda , Roger Wattenhofer, Minimizing interference in ad hoc and sensor networks, Proceedings of the 2005 joint workshop on Foundations of mobile computing, September 02-02, 2005, Cologne, Germany [doi>10.1145/1080810.1080816]
• 40: M. Halldórsson and T. Tokuyama, "Minimizing interference of a wire-less ad hoc network in a plane," presented at the Int. Workshop on Al-gorithmic Aspects of Wireless Sensor Networks (ALGOSENSORS), Venice, Italy, Jul. 2006.
• 41: T. Moscibroda and R. Wattenhofer, "The complexity of connectivity in wireless networks," presented at the 25th IEEE INFOCOM, Barcelona, Spain, Apr. 2006.
• 42: Thomas Moscibroda , Roger Wattenhofer , Aaron Zollinger, Topology control meets SINR: the scheduling complexity of arbitrary topologies, Proceedings of the 7th ACM international symposium on Mobile ad hoc networking and computing, May 22-25, 2006, Florence, Italy [doi>10.1145/1132905.1132939]
• 43: 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]
• 44: David Peleg, Distributed computing: a locality-sensitive approach, Society for Industrial and Applied Mathematics, Philadelphia, PA, 2000

INDEX TERMS

Primary Classification:
  E. Data
  E.4 CODING AND INFORMATION THEORY

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Network topology; Wireless communication
      C.2.3 Network Operations
          Subjects: Network management

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.0 General
          Subjects: Numerical algorithms

  I. Computing Methodologies
  I.6 SIMULATION AND MODELING
      I.6.5 Model Development
          Subjects: Modeling methodologies

General Terms:
Algorithms, Design, Management, Theory

Keywords:
algorithmic analysis, interference, modeling, network connectivity, network spanners, topology control