Approximation Algorithm for Wireless Network Interference Minimization

Authors

  • Hakob L. Aslanyan University of Geneva, Switzerland

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

Author Biography

Hakob L. Aslanyan, University of Geneva, Switzerland

Department of Informatics, University of Geneva, Switzerland

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

2021-12-10

How to Cite

Aslanyan, H. L. . (2021). Approximation Algorithm for Wireless Network Interference Minimization. Mathematical Problems of Computer Science, 33, 162–171. Retrieved from http://mpcs.sci.am/index.php/mpcs/article/view/345