The Complexity of Minimizing Receiver-Based and SINR Edge Interference

Topology control has been used to minimize interference or to reduce power consumption while maintaining connectivity in wireless ad hoc and sensor networks (WSNs)(which are represented as undirected graphs). In the graph model, the interference experienced by an edge in a WSN has been defined in at least two different ways: the sender-based and receiver-based interference models. These models have been extensively studied in the literature although the receiver-based model has received more attention. Recently, several researchers have started investigating interference in the more realistic physical model which is known as the Signal-to-Interference-Noise-Ratio (SINR) model. The SINR model better reflects the real environment than the receiver-based or sender-based graph models. In this paper, we study the problem of assigning power to nodes in the plane to yield a connected network of minimum edge interference in the receiver-based (RB-MEI) as well as the SINR models (SINR-MEI). We show that RB-MEI is NP- complete for geometric graphs. For SINR-MEI, NP- completeness holds for planar geometric graphs. We also propose some simple greedy heuristics based on the minimum spanning tree approach, and study their performance through simulation.