Article

Minimizing interference in ad hoc and sensor networks

Authors:

Thomas Moscibroda,

Rogert WattenhoferAuthors Info & Claims

DIALM-POMC '05: Proceedings of the 2005 joint workshop on Foundations of mobile computing

Pages 24 - 33

https://doi.org/10.1145/1080810.1080816

Published: 02 September 2005 Publication History

Abstract

Reducing interference is one of the main challenges in wireless communication, and particularly in ad hoc networks. The amount of interference experienced by a node v corresponds to the number of other nodes whose transmission range covers v. At the cost of communication links being dropped, interference can be reduced by decreasing the node's transmission power. In this paper, we study the problem of minimizing the average interference while still maintaining desired network properties, such as connectivity, point-to-point connections, or multicast trees. In particular, we present a greedy algorithm that computes an O(log n) approximation to the interference problem with connectivity requirement, where n is the number of nodes in the network. We then show the algorithm to be asymptotically optimal by proving a corresponding Ω(log n) lower bound that holds even in a more restricted interference model. Finally, we show how the algorithm can be generalized towards solving the interference problem for network properties that can be formulated as a 0-1 proper function.

References

[1]

P. Bose, P. Morin, I. Stojmenovic and J. Urrutia. Routing with Guaranteed Delivery in Ad Hoc Wireless Networks. In Proceedings of the 3rd International Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications (DIALM), pages 48--55, 1999.]]

Digital Library

[2]

M. Burkhart, P. von Rickenbach, R. Wattenhofer, and A. Zollinger. Does Topology Control Reduce Interference. In Proc. of the 5th ACM Int. Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc), 2004.]]

Digital Library

[3]

G. Calinescu, S. Kapoor, A. Olshevsky, and A. Zelikovsky. Network Lifetime and Power Assignment in Ad Hoc Wireless Networks. In Proceedings of 11th European Symposium on Algorithms (ESA), pages 114--126, 2003.]]

[4]

I. Caragiannis, C. Kaklamanis, and P. Kanellopolous. Energy-Efficient Wireless Network Design. To appear in Theory of Computing Systems, 2005.]]

Digital Library

[5]

M. Chlebåk and J. Chlebåková. Approximation Hardness of Dominating Set Problems. In Proceedings of 12th European Symposium on Algorithms (ESA), pages 192--203, 2004.]]

[6]

U. Feige. A Threshold of ln n for Approximating Set Cover. Journal of the ACM, 45(4):634--652, 1998.]]

Digital Library

[7]

M. Fussen, R. Wattenhofer, and A. Zollinger. Interference Arises at the Receiver. In Proceedings of Int. Conference on Wireless Networks, Communications, and Mobile Computing (WIRELESSCOM), 2005.]]

[8]

M. X. Goemans and D. P. Williamson. A General Approximation Technique for Constrained Forest Problems. SIAM Journal of Computing, 24(2):296--317, 1995.]]

Digital Library

[9]

L. Jia, R. Rajaraman, and C. Scheideler. On Local Algorithms for Topology Control and Routing in Ad Hoc Networks. In Proc. 15th Symposium on Parallel Algorithms and Architectures (SPAA), pages 220--229, 2003.]]

Digital Library

[10]

P. Klein and R. Ravi. A Nearly Best-Possible Approximation Algorithm for Node-Weighted Steiner Trees. Journal of Algorithms, 19(1):104--115, 1995.]]

Digital Library

[11]

F. T. Leighton and S. Rao. An Approximate Max-Flow Min-Cut Theorem for Uniform Multicommodity Flow Problems with Applications to Approximation Algorithms. In Proceedings of the 29th IEEE Symposium on the Foundations of Computer Science (FOCS), pages 422--431, 1988.]]

Digital Library

[12]

L. Li, J. Y. Halpern, P. Bahl, Y.-M. Wang, and R. Wattenhofer. Analysis of a Cone-Based Distributed Topology Control Algorithm for Wireless Multi-Hop Networks. In Proc. 20th Symp. on Principles of Distributed Computing (PODC), pages 264--273, 2001.]]

Digital Library

[13]

N. Li, J. Hou, and L. Sha. Design and Analysis of an MST-based Topology Control Algorithm. In Proceedings of INFOCOM, pages 1702--1712, 2003.]]

[14]

X.-Y. Li, G. Calinescu, and P.-J. Wan. Distributed Construction of Planar Spanner and Routing for Ad Hoc Networks. In Proceedings of INFOCOM, 2002.]]

[15]

C. Lund and M. Yannakakis. On the Hardness of Approximating Minimization Problems. Journal of the ACM, 41(5).]]

Digital Library

[16]

K. Moaveni-Nejad and X. Y. Li. Low-Interference Topology Control for Wireless Ad Hoc Networks. In Proceedings of the 2nd IEEE Conference on Sensor and Ad Hoc Communications and Networks (SECON), 2005.]]

[17]

R. Ramanathan and R. Hain. Topology Control of Multihop Wireless Networks using Transmit Power Adjustment. In Proceedings of INFOCOM, pages 404--413, 2000.]]

[18]

P. von Rickenbach, S. Schmid, R. Wattenhofer, and A. Zollinger. A Robust Interference Model for Wireless Ad Hoc Networks. In Proc. 5th IEEE International Workshop on Algorithms for Wireless, Mobile, Ad-Hoc and Sensor Networks (WMAN), 2005.]]

Digital Library

Cited By

Moraes RSilva YMartins FSilva JRocha H(2024)Joint Interference and Power Minimization for Fault-Tolerant Topology in Sensor NetworksIEEE Access10.1109/ACCESS.2024.342086912(120198-120218)Online publication date: 2024
https://doi.org/10.1109/ACCESS.2024.3420869
Pham HPham MTrinh VNguyen PNguyen T(2023)A Q-Learning-based Energy Efficiency Optimization in LoRa NetworksProceedings of the 12th International Symposium on Information and Communication Technology10.1145/3628797.3629015(312-318)Online publication date: 7-Dec-2023
https://dl.acm.org/doi/10.1145/3628797.3629015
Karim Abu-Affash ACarmi PKatz M(2021)Minimizing total interference in asymmetric sensor networksTheoretical Computer Science10.1016/j.tcs.2021.08.003Online publication date: Aug-2021
https://doi.org/10.1016/j.tcs.2021.08.003
Show More Cited By

Index Terms

Minimizing interference in ad hoc and sensor networks
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
      1. Graph algorithms
      2. Network flows
2. Theory of computation
  1. Design and analysis of algorithms
    1. Graph algorithms analysis
      1. Network flows
  2. Randomness, geometry and discrete structures

Recommendations

Multi-geocast Algorithms for Wireless Sparse or Dense Ad Hoc Sensor Networks
ICNS '08: Proceedings of the Fourth International Conference on Networking and Services

Multi-Geocasting in wireless sensor network and Ad Hoc network is the delivery of packets from a source (or sink) to all the nodes located in several geographic areas. The objectives of a multi-geocasting protocol are guaranteed message delivery and low ...
Reliable data transmission in mobile ad hoc sensor networks

In this paper, we introduce a new routing scheme for mobile ad hoc sensor networks, which effectively transports the information from source to sink by curbing the energy requirements, both at node and system level. The proposed approach, termed as ...
Transmitting to colocated users in wireless ad hoc and sensor networks

We consider wireless ad hoc networks and sensor networks where a remotely located source is transmitting information to a destined user embedded within a group of K densely packed physically colocated users enjoying favorable signal-to-noise ratio (SNR) ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

DIALM-POMC '05: Proceedings of the 2005 joint workshop on Foundations of mobile computing

September 2005

120 pages

ISBN:1595930922

DOI:10.1145/1080810

Program Chairs:
Suman Banerjee
University of Wisconsin-Madison
,
Samrat Ganguly
NEC Laboratories America

Copyright © 2005 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: 02 September 2005

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

Dial M - POMC 05

Sponsor:

Dial M - POMC 05: Joint Workshop on Foundations of Mobile Computing 2005

September 2, 2005

Cologne, Germany

Acceptance Rates

Overall Acceptance Rate 21 of 68 submissions, 31%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

51
Total Citations
View Citations
681
Total Downloads

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

Reflects downloads up to 18 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Moraes RSilva YMartins FSilva JRocha H(2024)Joint Interference and Power Minimization for Fault-Tolerant Topology in Sensor NetworksIEEE Access10.1109/ACCESS.2024.342086912(120198-120218)Online publication date: 2024
https://doi.org/10.1109/ACCESS.2024.3420869
Pham HPham MTrinh VNguyen PNguyen T(2023)A Q-Learning-based Energy Efficiency Optimization in LoRa NetworksProceedings of the 12th International Symposium on Information and Communication Technology10.1145/3628797.3629015(312-318)Online publication date: 7-Dec-2023
https://dl.acm.org/doi/10.1145/3628797.3629015
Karim Abu-Affash ACarmi PKatz M(2021)Minimizing total interference in asymmetric sensor networksTheoretical Computer Science10.1016/j.tcs.2021.08.003Online publication date: Aug-2021
https://doi.org/10.1016/j.tcs.2021.08.003
Kavra RGupta AKansal S(2021)Interval graph based energy efficient routing scheme for a connected topology in wireless sensor networksWireless Networks10.1007/s11276-021-02782-0Online publication date: 21-Sep-2021
https://doi.org/10.1007/s11276-021-02782-0
Abu-Affash ACarmi PKatz M(2020)Minimizing Total Interference in Asymmetric Sensor NetworksAlgorithms for Sensor Systems10.1007/978-3-030-62401-9_1(1-16)Online publication date: 28-Oct-2020
https://doi.org/10.1007/978-3-030-62401-9_1
alkhayyat AThabit AAli A(2019)WBAN health care-based: Modeling Signal to Interference ratio with Different MAC Protocols2019 2nd International Conference on Engineering Technology and its Applications (IICETA)10.1109/IICETA47481.2019.9012969(138-143)Online publication date: Aug-2019
https://doi.org/10.1109/IICETA47481.2019.9012969
Kapelko R(2018)On the Maximum Movement of Random Sensors for Coverage and Interference on a LineProceedings of the 19th International Conference on Distributed Computing and Networking10.1145/3154273.3154330(1-10)Online publication date: 4-Jan-2018
https://dl.acm.org/doi/10.1145/3154273.3154330
Carrabs FCerrone CD’Ambrosio CRaiconi A(2017)Column Generation Embedding Carousel Greedy for the Maximum Network Lifetime Problem with Interference ConstraintsOptimization and Decision Science: Methodologies and Applications10.1007/978-3-319-67308-0_16(151-159)Online publication date: 5-Nov-2017
https://doi.org/10.1007/978-3-319-67308-0_16
Carrabs FCerulli RD’Ambrosio CRaiconi A(2017)Prolonging Lifetime in Wireless Sensor Networks with Interference ConstraintsGreen, Pervasive, and Cloud Computing10.1007/978-3-319-57186-7_22(285-297)Online publication date: 13-Apr-2017
https://doi.org/10.1007/978-3-319-57186-7_22
Moraes RRibeiro CRibeiro G(2016) Exact formulations for the minimum interference problem in k ‐connected ad hoc wireless networks International Transactions in Operational Research10.1111/itor.1232723:6(1113-1139)Online publication date: 8-Jul-2016
https://doi.org/10.1111/itor.12327
Show More Cited By

View Options

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.

Figures

Tables

Media

View Table of Conten