Article

Algorithmic aspects of topology control problems for ad hoc networks

Authors:

Errol L. Lloyd,

Madhav V. Marathe,

Ram Ramanathan,

S. S. RaviAuthors Info & Claims

MobiHoc '02: Proceedings of the 3rd ACM international symposium on Mobile ad hoc networking & computing

Pages 123 - 134

https://doi.org/10.1145/513800.513816

Published: 09 June 2002 Publication History

Abstract

Topology control problems are concerned with the assignment of power values to the nodes of an ad hoc network so that the power assignment leads to a graph topology satisfying some specified properties. This paper considers such problems under several optimization objectives, including minimizing the maximum power and minimizing the total power. A general approach leading to a polynomial algorithm is presented for minimizing maximum power for a class of graph properties called textbf monotone properties. The difficulty of generalizing the approach to properties that are not monotone is discussed. Problems involving the minimization of total power are known to be bf NP -complete even for simple graph properties. A general approach that leads to an approximation algorithm for minimizing the total power for some monotone properties is presented. Using this approach, a new approximation algorithm for the problem of minimizing the total power for obtaining a 2-node-connected graph is obtained. It is shown that this algorithm provides a constant performance guarantee. Experimental results from an implementation of the approximation algorithm are also presented.

References

[1]

W. Chen and N. Huang. "The Strongly Connecting Problem on Multihop Packet Radio Networks", IEEE Trans. Communication, Vol. 37, No. 3, Mar. 1989.]]

[2]

A. E. F. Clementi, P. Penna and R. Silvestri. "Hardness Results for the Power Range Assignment Problem in Packet Radio Networks", Proc. Third International Workshop on Randomization and Approximation in Computer Science (APPROX 1999), Lecture Notes in Computer Science Vol. 1671, Springer-Verlag, July 1999, pp. 195--208.]]

Digital Library

[3]

A. E. F. Clementi, P. Penna and R. Silvestri. "The Power Range Assignment Problem in Packet Radio Networks in the Plane", Proc. 17th Annual Symposium on Theoretical Aspects of Computer Science (STACS 2000), Feb. 2000.]]

Digital Library

[4]

T. Cormen, C. Leiserson, R. Rivest and C. Stein. Introduction to Algorithms (second edition), MIT Press and McGraw-Hill, Cambridge, MA, 2001.]]

Digital Library

[5]

G. A. Dirac. "Minimally 2-Connected Graphs", J. für Reine und Angewandte Mathematik, Vol. 228, 1967, pp. 204--216.]]

[6]

M. R. Garey and D. S. Johnson. Computers and Intractability: A Guide to the Theory of NP-completeness, W. H. Freeman and Co., San Francisco, CA, 1979.]]

Digital Library

[7]

L. Hu. "Topology Control for Multi-hop Packet Radio Networks", IEEE. Trans. Communications, 41(10), 1993, pp. 1474--1481.]]

[8]

S. Khuller and B. Raghavachari. "Improved Approximation Algorithms for Uniform Connectivity]]

[9]

S. Khuller and U. Vishkin, "Biconnectivity Approximations and Graph Carvings", J. ACM, Vol. 41, 1994, pp. 214--235.]]

Digital Library

[10]

L. M. Kirousis, E. Kranakis, D. Krizanc and A. Pelc. "Power Consumption in Packet Radio Networks", Proc. 14th Annual Symposium on Theoretical Aspects of Computer Science (STACS 97), Lecture Notes in Computer Science Vol. 1200, Springer-Verlag, Feb. 1997, pp. 363--374.]]

Digital Library

[11]

L. Li and J. Y. Halpern, "Minimum Energy Mobile Wireless Networks Revisited", Proc. IEEE Conference on Communications (ICC'01), June 2001, pp. 278--283.]]

[12]

L. Li, J. Y. Halpern, P. Bahl, Y. Wang and R. Wattenhofer, "Analysis of Cone-Based Distributed Topology Control Algorithm for Wireless Multi-hop Networks", Proc. ACM Principles of Distributed Computing Conference (PODC'01), Aug. 2001.]]

Digital Library

[13]

M. D. Plummer. "On Minimal Blocks", Trans. AMS, Vol. 134, Oct.-Dec. 1968, pp. 85--94.]]

[14]

V. Radoplu and T. H. Meng. "Minimum Energy Mobile Wireless Networks", IEEE J. Selected Areas in Communications, 17(8), Aug. 1999, pp. 1333--1344.]]

Digital Library

[15]

R. Ramanathan and R. Rosales-Hain. "Topology Control of Multihop Wireless Networks Using Transmit Power Adjustment", Proc. IEEE INFOCOM 2000, Tel Aviv, Israel, March 2000, pp. 404--413.]]

[16]

T. S. Rappaport. Wireless Communications: Principles and Practice, Prentice-Hall, Inc., Englewood Cliffs, NJ, 1996.]]

Digital Library

[17]

R. Ravi and D. P. Williamson, "An Approximation Algorithm for Minimum-Cost Vertex-Connectivity Problems", Algorithmica, 18: 21--43, 1997.]]

Digital Library

[18]

E. M. Royer, P. Melliar-Smith and L. Moser, "An Analysis of the Optimum Node Density for Ad hoc Mobile Networks", Proc. IEEE Intl. Conf. on Communication (ICC'01), Helsinki, Finland, June 2001.]]

[19]

E. M. Royer and C. Perkins, "Transmission Range Effects on AODV Multicast Communication", To appear in ACM Mobile Networks and Applications (special issue on Multipoint Communication in Wireless Networks).]]

Digital Library

[20]

H. Takagi, and L. Kleinrock. "Optimal Transmission Ranges for Randomly Distributed Packet Radio Terminals", IEEE Transactions on Communications, Vol. COM-32, No. 3, pp. 246--257, March 1984. Also appears in Multiple Access Communications, Foundations for Emerging Technologies, Norman Abramson (Ed.), IEEE Press, pp.342--353, 1992.]]

[21]

J. van Leeuwen. "Graph Algorithms", Chapter 10 in Handbook of Theoretical Computer Science, Vol. A, Edited by J. van Leeuwen, MIT Press and Elsevier, Cambridge, MA, 1990.]]

Digital Library

[22]

R. Wattenhofer, L. Li, P. Bahl and Y. Wang. "Distributed Topology Control for Power Efficient Operation in Multihop Wireless Ad Hoc Networks", Proc. IEEE INFOCOM 2001, Anchorage, Alaska, April 2001, pp. 1388--1397.]]

[23]

D. B. West. Introduction to Graph Theory, Prentice-Hall, Inc., Englewood Cliffs, NJ, 1996.]]

Cited By

Tripathy BJena SBera PDas S(2019)A New Mobility Control Approach for Improved Route Availability in Mobile Ad Hoc NetworksArabian Journal for Science and Engineering10.1007/s13369-019-03899-344:11(9627-9639)Online publication date: 23-May-2019
https://doi.org/10.1007/s13369-019-03899-3
(2017)Cooperative topology control for low interference in wireless ad hoc networksInternational Journal of Ad Hoc and Ubiquitous Computing10.1504/IJAHUC.2017.08284624:4(213-224)Online publication date: 1-Jan-2017
https://dl.acm.org/doi/10.1504/IJAHUC.2017.082846
Wang D(2016)Cluster subdivision towards power savings for randomly deployed WSNs — An analysis using 2-D spatial poisson process2016 7th International Conference on Information and Communication Systems (ICICS)10.1109/IACS.2016.7476103(156-161)Online publication date: Apr-2016
https://doi.org/10.1109/IACS.2016.7476103
Show More Cited By

Index Terms

Algorithmic aspects of topology control problems for ad hoc networks
1. Networks
  1. Network architectures
2. Theory of computation
  1. Design and analysis of algorithms

Recommendations

Power optimization in fault-tolerant topology control algorithms for wireless multi-hop networks
MobiCom '03: Proceedings of the 9th annual international conference on Mobile computing and networking

In ad hoc wireless networks, it is crucial to minimize power consumption while maintaining key network properties. This work studies power assignments of wireless devices that minimize power while maintaining k-fault tolerance. Specifically, we require ...
Power optimization in fault-tolerant topology control algorithms for wireless multi-hop networks

In ad hoc wireless networks, it is crucial to minimize power consumption while maintaining key network properties. This work studies power assignments of wireless devices that minimize power while maintaining k-fault tolerance. Specifically, we require ...
Topology control in constant rate mobile ad hoc networks

Topology control is the problem of assigning power levels to the nodes of an ad hoc network so as to create a specified network topology while minimizing the energy consumed by the network nodes. While considerable theoretical attention has been given ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

MobiHoc '02: Proceedings of the 3rd ACM international symposium on Mobile ad hoc networking & computing

June 2002

246 pages

ISBN:1581135017

DOI:10.1145/513800

General Chair:
Jean-Pierre Hubaux
EPFL (CH)
,
Program Chairs:
J. J. Garcia-Luna-Aceves
University of California at Santa Cruz (USA)
,
David B. Johnson
Rice University (USA)

Copyright © 2002 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGMOBILE: ACM Special Interest Group on Mobility of Systems, Users, Data and Computing

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 09 June 2002

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

MobiHoc02

Sponsor:

SIGMOBILE

MobiHoc02: ACM Symposium on Mobile Ad Hoc Networking and Networking

June 9 - 11, 2002

Lausanne, Switzerland

Acceptance Rates

MobiHoc '02 Paper Acceptance Rate 22 of 134 submissions, 16%;

Overall Acceptance Rate 296 of 1,843 submissions, 16%

Upcoming Conference

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

139
Total Citations
View Citations
757
Total Downloads

Downloads (Last 12 months)15
Downloads (Last 6 weeks)1

Reflects downloads up to 02 Oct 2024

Other Metrics

View Author Metrics

Citations

Cited By

Tripathy BJena SBera PDas S(2019)A New Mobility Control Approach for Improved Route Availability in Mobile Ad Hoc NetworksArabian Journal for Science and Engineering10.1007/s13369-019-03899-344:11(9627-9639)Online publication date: 23-May-2019
https://doi.org/10.1007/s13369-019-03899-3
(2017)Cooperative topology control for low interference in wireless ad hoc networksInternational Journal of Ad Hoc and Ubiquitous Computing10.1504/IJAHUC.2017.08284624:4(213-224)Online publication date: 1-Jan-2017
https://dl.acm.org/doi/10.1504/IJAHUC.2017.082846
Wang D(2016)Cluster subdivision towards power savings for randomly deployed WSNs — An analysis using 2-D spatial poisson process2016 7th International Conference on Information and Communication Systems (ICICS)10.1109/IACS.2016.7476103(156-161)Online publication date: Apr-2016
https://doi.org/10.1109/IACS.2016.7476103
Mansour MJarray F(2015)An Iterative Solution for the Coverage and Connectivity Problem in Wireless Sensor NetworkProcedia Computer Science10.1016/j.procs.2015.08.37463(494-498)Online publication date: 2015
https://doi.org/10.1016/j.procs.2015.08.374
Gundry SZou JUyar MSahin CKusyk J(2015)Differential evolution-based autonomous and disruption tolerant vehicular self-organization in MANETsAd Hoc Networks10.1016/j.adhoc.2014.08.00625:PB(454-471)Online publication date: 1-Feb-2015
https://dl.acm.org/doi/10.1016/j.adhoc.2014.08.006
Yadav AYadav RSingh RSingh A(2014)Efficient topology control scheme for wireless ad-hoc networksInternational Journal of Computational Intelligence Studies10.1504/IJCISTUDIES.2014.0586513:1(94-109)Online publication date: 1-Jan-2014
https://dl.acm.org/doi/10.1504/IJCISTUDIES.2014.058651
Xu HHuang LQiao CWang XSun Y(2013)Topology Control with vMIMO Communication in Wireless Sensor NetworksIEEE Transactions on Wireless Communications10.1109/TWC.2013.110413.13044412:12(6328-6339)Online publication date: Dec-2013
https://doi.org/10.1109/TWC.2013.110413.130444
Zarifzadeh SYazdani N(2013)Neighbor Selection Game in Wireless Ad Hoc NetworksWireless Personal Communications: An International Journal10.1007/s11277-012-0711-670:2(617-640)Online publication date: 1-May-2013
https://dl.acm.org/doi/10.1007/s11277-012-0711-6
Wang Y(2013)Three-Dimensional Wireless Sensor Networks: Geometric Approaches for Topology and Routing DesignThe Art of Wireless Sensor Networks10.1007/978-3-642-40066-7_10(367-409)Online publication date: 18-Dec-2013
https://doi.org/10.1007/978-3-642-40066-7_10
Li FChen ZWang Y(2012)Localized geometric topologies with bounded node degree for three-dimensional wireless sensor networksEURASIP Journal on Wireless Communications and Networking10.1186/1687-1499-2012-1572012:1Online publication date: 1-May-2012
https://doi.org/10.1186/1687-1499-2012-157
Show More Cited By

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents