Approximation Algorithm for Wireless Network Interference Minimization
Abstract
Interference minimization problem in wireless sensor and ad-hoc networks are considered. That is to assign a transmission radius to each node of network, to make it connected and at the same time to minimize the maximum number of overlapping transmission ranges on each node of network. Additional means of topology control besides the connectivity is blocking the long line connections at the receiver level. We propose a polynomial time approximation algorithm which finds connected network with at most O((opt log n)2 ) interference where opt is the minimal interference of the given network, and n is the number of network nodes. The lower bound for this problem, where a general distance function is considered, has been proven to be O(log n) . The algorithm is known which finds a network where maximum interference is bounded by O( n) .
References
P. von Rickenbach, S. Schmid, R. Wattenhofer and A. Zollinger, “A robust interference model for wireless Ad-Hoc networks”, Proceedings of Parallel and Distributed Processing Symposium, vol. 13, pp. 239a, 2005.
M. M. Halldorsson and T. Tokuyama, “Minimizing interference of a wireless ad-hoc network in a plane”, Theoretical Computer Science, vol. 402, issue 1, pp. 29-42, 2006.
D. Bil`o and G. Proietti, “On the complexity of minimizing interference in ad-hoc and sensor networks”, Proc. 2nd International Workshop on Algorithmic Aspects of Wireless Sensor Networks, ALGOSENSORS 2006, in: LNCS, vol. 4240, pp. 13–24, 2006.
F. Kuhn, P. von Rickenbach, R. Wattenhofer, E. Welzl, and A. Zollinger, “Interference in cellular networks: The minimum membership set cover problem”, Proc. 11th COCOON, volume 3595 of LNCS, pp. 188–198. Springer, 2005.
K. Moaveni-Nejad and X.Y. Li, “Low-Interference Topology Control for Wireless Adhoc Networks”, Ad Hoc & Sensor Wireless Networks: An International Journal 1(1-2) (2005).
T. Johansson and L. Carr-Motyckova, “Reducing Interference in Ad hoc Networks through Topology Control”, Proc of the 3 rd ACM Joint Workshop on Foundations of Mobile Computing (DIALM-POMC), ACM Press, pp. 17-23, 2005.
M. Benkert, J. Gudmundsson, H. Haverkort and A. Wolff, “Constructing Minimum- Interference Networks”, Computational Geometry: vol. 40, issue 3, pp. 179-194, 2008.
M. Fussen, R. Wattenhofer and A. Zollinger, “Interference Arises at the Receiver”, Proc. of the Int. Conf. on Wireless Networks, Communications, and Mobile Computing (WIRELESSCOM), pp. 1-6, 2005.
D. Johnson, “Approximation algorithms for combinatorial problems”, Journal of Computer and System Sciences, pp. 256–278, 1974.
U. Feige, “A Threshold of ln n for Approximating Set Cover”, Journal of the ACM (JACM), 45(4), pp. 634–652, 1998.
E. D. Demaine, M. T. Hajiaghayi, U. Feige, and M. R. Salavatipour, “Combination can be hard: approximability of the unique coverage problem”, Proc. 17th SODA, pp. 162–171, ACM Press, 2006.
N. Garg, V. V. Vazirani, and M. Yannakakis, “Primal-dual approximation algorithms for integral flow and multicut in trees”, Algorithmica, 18(1), pp. 3–20, 1997.
J. Guo and R. Niedermeier, “Exact algorithms and applications for Tree-like Weighted Set Cover”, Journal of Discrete Algorithms, vol. 4, issue 4, pp. 608-622, 2006.
S. Mecke and D. Wagner, “Solving geometric covering problems by data reduction”, Proc. 12th ESA, vol. 3221 of LNCS, pp. 760–771. Springer, 2004.
N. Ruf and A. Schöbel, “Set covering with almost consecutive ones property”, Discrete Optimization, 1(2), pp. 215–228, 2004.
H. Aslanyan, “Greedy set cover estimations”, Int. Conference “Computer Science and Information Technologies”, Yerevan, pp. 143-144, 2003.
S. Meguerdichian, F. Koushanfar, M. Potkonjak, and M. Srivastava, “Coverage Problem in Wireless Ad-Hoc Sensor Networks”, IEEE INFOCOM, pp. 1380–1387, 2001.
H. Breu and D. G. Kirkpatrick, “Unit disk graph recognition is NP-hard”, Computational Geometry: Theory and Applications, 9(1-2), pp. 3–24, 1998.
J.N. Al-Karaki and A.E. Kamal, “Routing techniques in wireless sensor networks: A survey”, IEEE Wireless Communications, 11(6), pp. 6-28, 2004.
K. Pahlavan and A. H. Levesque, “Wireless information networks”, John Wiley & Sons, New York, NY, USA, 1995.
Downloads
Published
How to Cite
Issue
Section
License
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
