Article

The K-Neigh Protocol for Symmetric Topology Control in Ad Hoc Networks

Authors:

Douglas M. Blough,

Mauro Leoncini,

Giovanni Resta,

Paolo SantiAuthors Info & Claims

MobiHoc '03: Proceedings of the 4th ACM international symposium on Mobile ad hoc networking & computing

Pages 141 - 152

https://doi.org/10.1145/778415.778433

Published: 01 June 2003 Publication History

Abstract

We propose an approach to topology control based on the principle of maintaining the number of neighbors of every node equal to or slightly below a specific value k. The approach enforces symmetry on the resulting communication graph, thereby easing the operation of higher layer protocols. To evaluate the performance of our approach, we estimate the value of k that guarantees connectivity of the communication graph with high probability. We then define k-Neigh, a fully distributed, asynchronous, and localized protocol that follows the above approach and uses distance estimation. We prove that k-Neigh terminates at every node after a total of 2n messages have been exchanged (with n nodes in the network) and within strictly bounded time. Finally, we present simulations results which show that our approach is about 20% more energy-efficient than a widely-studied existing protocol.

References

[1]

M. Bahramgiri, M. Hajiaghayi, V.S. Mirrokni, "Fault-tolerant ad 3-Dimensional Distributed Topology Control Algorithms in Wireless Multi-hop Networks", Proc. IEEE Int. Conference on Computer Communications and Networks, pp. 392--397, 2002.

[2]

L. Bao, J.J.Garcia-Luna-Aceves, "Channel Access Scheduling in Ad Hoc Networks with Unidirectional Links", Proc. DIALM 01, pp. 9--18, 2001.

Digital Library

[3]

D.M. Blough, M. Leoncini, G. Resta, P. Santi, "On the Symmetric Range Assignment Problem in Wireless Ad Hoc Networks", Proc. IFIP Conf. on Theoretical Computer Science, pp. 71--82, 2002.

Digital Library

[4]

D.M. Blough, M. Leoncini, G. Resta, P. Santi, "The k-Neighbors Protocol for Symmetric Topology Control in Ad Hoc Networks", Tech. Rep. IIT-TR-23/2002, Istituto di Informatica e Telematica, Pisa -- Italy, Dec. 2002.

[5]

S.A. Borbash, E.H. Jennings, "Distributed Topology Control Algorithm for Multihop Wireless Networks", Proc. IEEE Int. Joint Conference on Neural Networks, pp. 355--360, 2002.

[6]

J. Bruck, M. Franceschetti, L. Schulman, "Microcellular Systems, Random Walks, and Wave Propagation", Proc. IEEE Symposium on Antennas and Propagation, pp. 220--223, 2002.

[7]

J. Chang, L. Tassiulas, "Energy Conserving Routing in Wireless Ad Hoc Networks", Proc. IEEE INFOCOM 2000, pp. 22--31, 2000.

[8]

A.E.F. Clementi, P. Penna, R. Silvestri, "Hardness Results for the Power Range Assignment Problem in Packet Radio Networks", Proc. 2nd International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (RANDOM/APPROX '99), LNCS (1671), pp. 197--208, 1999.

Digital Library

[9]

L. Girod, D. Estrin, "Robust Range Estimation Using Acoustic and Multimodal Sensing", IEEE/RSJ International Conference on Intelligent Robots and Systems, 2001.

[10]

P. Gupta, P.R. Kumar, "Critical Power for Asymptotic Connectivity in Wireless Networks", Stochastic Analysis, Control, Optimization and Applications, Birkhauser, Boston, pp. 547--566, 1998.

[11]

Z. Huang, C. Shen, C. Srisathapornphat, C. Jaikaeo, "Topology Control for Ad Hoc Networks with Directional Antennas", Proc. IEEE Int. Conference on Computer Communications and Networks, pp. 16--21, 2002.

[12]

E. Jung, N.H. Vaidya, "A Power Control MAC Protocol for Ad Hoc Networks", Proc. ACM Mobicom 02, pp. 36--47, 2002.

Digital Library

[13]

V. Kawadia, P.R. Kumar, "Power Control and Clustering in Ad Hoc Networks", to appear in Proc. IEEE Infocom 03, 2003.

[14]

L.M. Kirousis, E. Kranakis, D. Krizanc, A. Pelc, "Power Consumption in Packet Radio Networks", Theoretical Computer Science, Vol. 243, pp. 289--305, 2000.

Digital Library

[15]

R. Krashinsky, H. Balakrishnan, "Minimizing Energy for Wireless Web Access with Bounded Slowdown", Proc. ACM Mobicom 02, pp. 119--130, 2002.

Digital Library

[16]

L. Li, J.H. Halpern, P. Bahl, Y. Wang, R. Wattenhofer, "Analysis of a Cone-Based Distributed Topology Control Algorithm for Wireless Multi-hop Networks", Proc. ACM PODC 2001, pp. 264--273, 2001.

Digital Library

[17]

J. Liu, B. Li, "MobileGrid: Capacity-aware Topology Control in Mobile Ad Hoc Networks", Proc. IEEE Int. Conference on Computer Communications and Networks, pp. 570--574, 2002.

[18]

M.K. Marina, S.R. Das, "Routing Performance in the Presence of Unidirectional Links in Multihop Wireless Networks", Proc. ACM MobiHoc 02, pp. 12--23, 2002.

Digital Library

[19]

S. Narayanaswamy, V. Kawadia, R.S. Sreenivas, P.R. Kumar, "Power Control in Ad Hoc Networks: Theory, Architecture, Algorithm and Implementation of the COMPOW Protocol", Proc. European Wireless 2002, pp. 156--162, 2002.

[20]

K. Pahlavan, A. Levesque,Wireless Information Networks, John Wiley and Sons, New York, 1995.

Digital Library

[21]

M.R. Pearlman, Z.J. Haas, B.P. Manvell, "Using Multi-Hop Acknowledgements to Discover and Reliably Communicate over Unidirectional Links in Ad Hoc Networks", Proc. Wireless Communications and Networking Conference (WCNC), pp. 532--537, 2000.

[22]

R. Prakash, "A Routing Algorithm for Wireless Ad Hoc Networks with Unidirectional Links", ACM/Kluwer Wireless Networks, Vol.7, n. 6, pp. 617--625, 2001.

Digital Library

[23]

R. Ramanathan, R. Rosales-Hain, "Topology Control of Multihop Wireless Networks using Transmit Power Adjustment", Proc. IEEE Infocom 2000, pp. 404--413, 2000.

[24]

V. Ramasubramanian, R. Chandra, D. Mosse, "Providing a Bidirectional Abstraction for Unidirectional Ad Hoc Networks", Proc. IEEE Infocom 02, pp. 1258--1267, 2002.

[25]

V. Rodoplu, T.H. Meng, "Minimum Energy Mobile Wireless Networks", IEEE Journal Selected Areas in Comm., Vol. 17, n. 8, pp. 1333--1344, 1999.

Digital Library

[26]

M. Sanchez, P. Manzoni, Z.J. Haas, "Determination of Critical Transmitting Range in Ad Hoc Networks", Proc. Multiaccess, Mobility and Teletraffic for Wireless Communications Conference, 1999.

[27]

P. Santi, D.M. Blough,"The Critical Transmitting Range for Connectivity in Sparse Wireless Ad Hoc Networks", IEEE Transactions on Mobile Computing, Vol. 2, n. 1, pp. 1--15, January-March 2003.

Digital Library

[28]

A. Savvides, C. Han, M. Srivastava, "Dynamic Fine-Grained Localization in Ad Hoc Networks of Sensors", Proc. ACM Mobicom 01, pp. 166--179, 2001.

Digital Library

[29]

S. Slijepcevic, S. Megerian, M. Potkonjak, "Location Errors in Wireless Embedded Sensor Networks: Sources, Models, and Effect on Applications", Mobile Computing and Communications Review, Vol. 6, n. 3, pp. 67--78, 2002.

Digital Library

[30]

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

[31]

F. Xue, P.R. Kumar, "The Number of Neighbors Needed for Connectivity of Wireless Networks", internet draft, available at http://decision.csl.uiuc.edu/prkumar/postscript_files.html#Wireless%20Networks.

Cited By

Liu CWang MZeng QHuangfu W(2020)Leader-following flocking for unmanned aerial vehicle swarm with distributed topology controlScience China Information Sciences10.1007/s11432-019-2763-563:4Online publication date: 9-Mar-2020
https://doi.org/10.1007/s11432-019-2763-5
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
Abid BMessai SSeba H(2019)Energy-Based Connected Dominating Set for Data Aggregation for Intelligent Wireless Sensor NetworksMachine Learning for Networking10.1007/978-3-030-19945-6_13(193-211)Online publication date: 10-May-2019
https://doi.org/10.1007/978-3-030-19945-6_13
Show More Cited By

Index Terms

The K-Neigh Protocol for Symmetric Topology Control in Ad Hoc Networks
1. Networks
  1. Network types
    1. Mobile networks
    2. Wireless access networks

Recommendations

Topology control in wireless ad hoc and sensor networks

Topology Control (TC) is one of the most important techniques used in wireless ad hoc and sensor networks to reduce energy consumption (which is essential to extend the network operational time) and radio interference (with a positive effect on the ...
Mobility-Sensitive Topology Control in Mobile Ad Hoc Networks

In most existing localized topology control protocols for mobile ad hoc networks (MANETs), each node selects a few logical neighbors based on location information and uses a small transmission range to cover those logical neighbors. Transmission range ...
The k-Neighbors Approach to Interference Bounded and Symmetric Topology Control in Ad Hoc Networks

Topology control, wherein nodes adjust their transmission ranges to conserve energy and reduce interference, is an important feature in wireless ad hoc networks. Contrary to most of the literature on topology control which focuses on reducing energy ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

MobiHoc '03: Proceedings of the 4th ACM international symposium on Mobile ad hoc networking & computing

June 2003

324 pages

ISBN:1581136846

DOI:10.1145/778415

General Chair:
Mario Gerla
University of California, Los Angeles
,
Program Chairs:
Anthony Ephremides
University of Maryland, College Park
,
Mani Srivastava
University of California, Los Angeles

Copyright © 2003 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

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 June 2003

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

MobiHoc03

Sponsor:

MobiHoc03: Fourth ACM Symposium on Mobile Ad Hoc Networking and Computing

June 1 - 3, 2003

Maryland, Annapolis, USA

Acceptance Rates

MobiHoc '03 Paper Acceptance Rate 27 of 192 submissions, 14%;

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

Upcoming Conference

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

91
Total Citations
View Citations
1,474
Total Downloads

Downloads (Last 12 months)11
Downloads (Last 6 weeks)0

Reflects downloads up to 02 Oct 2024

Other Metrics

View Author Metrics

Citations

Cited By

Liu CWang MZeng QHuangfu W(2020)Leader-following flocking for unmanned aerial vehicle swarm with distributed topology controlScience China Information Sciences10.1007/s11432-019-2763-563:4Online publication date: 9-Mar-2020
https://doi.org/10.1007/s11432-019-2763-5
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
Abid BMessai SSeba H(2019)Energy-Based Connected Dominating Set for Data Aggregation for Intelligent Wireless Sensor NetworksMachine Learning for Networking10.1007/978-3-030-19945-6_13(193-211)Online publication date: 10-May-2019
https://doi.org/10.1007/978-3-030-19945-6_13
Rahmani PJavadi HBakhshi HHosseinzadeh M(2018)TCLABJournal of Network and Systems Management10.1007/s10922-017-9422-326:2(426-462)Online publication date: 1-Apr-2018
https://dl.acm.org/doi/10.1007/s10922-017-9422-3
Mahapatra RShet N(2018)Topology Control in Wireless Sensor Networks: A SurveyInnovations in Electronics and Communication Engineering10.1007/978-981-10-8204-7_34(335-346)Online publication date: 29-Aug-2018
https://doi.org/10.1007/978-981-10-8204-7_34
Nayak MTripathy GRath A(2018)A Distributed Transmission Power Efficient Fault-Tolerant Topology Management Mechanism for Nonhomogeneous Wireless Sensor NetworkProgress in Advanced Computing and Intelligent Engineering10.1007/978-981-10-6872-0_45(481-493)Online publication date: 9-Feb-2018
https://doi.org/10.1007/978-981-10-6872-0_45
Huang JDuan QXing CWang H(2017)Topology Control for Building a Large-Scale and Energy-Efficient Internet of ThingsIEEE Wireless Communications10.1109/MWC.2017.1600193WC24:1(67-73)Online publication date: 1-Feb-2017
https://dl.acm.org/doi/10.1109/MWC.2017.1600193WC
Mir ZKo Y(2017)Collaborative Topology Control for Many-to-One Communications in Wireless Sensor NetworksIEEE Access10.1109/ACCESS.2017.27223795(15927-15941)Online publication date: 2017
https://doi.org/10.1109/ACCESS.2017.2722379
Guo DWu YCao LWang MWang B(2016)Prolonging network lifetime and balancing network energy in multi-domain WSNsInternational Journal of Sensor Networks10.1504/IJSNET.2016.07672520:4(209-218)Online publication date: 1-May-2016
https://dl.acm.org/doi/10.1504/IJSNET.2016.076725
Lin SMiao FZhang JZhou GGu LHe TStankovic JSon SPappas G(2016)ATPCACM Transactions on Sensor Networks10.1145/274634212:1(1-31)Online publication date: 10-Mar-2016
https://dl.acm.org/doi/10.1145/2746342
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