Minimizing interference in ad hoc and sensor networks

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.]]
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.]]
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.]]
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.]]
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.]]
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.]]
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.]]
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.]]
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.]]
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).]]
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.]]

Index Terms

• Mathematics of computing

  • Discrete mathematics

    • Graph theory

      • Graph algorithms

      • Network flows

• Theory of computation

  • Design and analysis of algorithms

    • Graph algorithms analysis

      • Network flows

  • Randomness, geometry and discrete structures