Minimizing the Maximum Interference is Hard

Abstract

We consider the following interference model for wireless sensor and ad hoc networks: the receiver interference of a node is the number of transmission ranges it lies in. We model transmission ranges as disks. For this case we show that choosing transmission radii which minimize the maximum interference while maintaining a connected symmetric communication graph is NP-complete.

4 pages, 1 figure

Cited by in corpus (5)

• A Tight Bound on the Maximum Interference of Random Sensors in the Highway Model
• Minimizing interference in ad-hoc networks with bounded communication radius
• Interference Minimization in Asymmetric Sensor Networks
• Bounding Interference in Wireless Ad Hoc Networks with Nodes in Random Position
• Improved Interference in Wireless Sensor Networks