Microsoft Word - tpel.doc Mathematical Problems of Computer Science 33, 162--171, 2010. 162 Approximation Algorithm for Wireless Network Interference Minimization Hakob L. Aslanyan Department of Informatics, University of Geneva, Switzerland e-mail: hakob.aslanyan@unige.ch 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 ))log(( 2noptO  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 )(log nO . The algorithm is known which finds a network where maximum interference is bounded by )( nO . References [1] 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. [2] 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. [3] 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. [4] 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. [5] 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). [6] 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. [7] M. Benkert, J. Gudmundsson, H. Haverkort and A. Wolff, “Constructing Minimum- Interference Networks”, Computational Geometry: vol. 40, issue 3, pp. 179-194, 2008. H. Aslanyan 163 [8] 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. [9] D. Johnson, “Approximation algorithms for combinatorial problems”, Journal of Computer and System Sciences, pp. 256–278, 1974. [10] U. Feige, “A Threshold of ln n for Approximating Set Cover”, Journal of the ACM (JACM), 45(4), pp. 634–652, 1998. [11] 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. [12] 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. [13] 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. [14] S. Mecke and D. Wagner, “Solving geometric covering problems by data reduction”, Proc. 12th ESA, vol. 3221 of LNCS, pp. 760–771. Springer, 2004. [15] N. Ruf and A. Schöbel, “Set covering with almost consecutive ones property”, Discrete Optimization, 1(2), pp. 215–228, 2004. [16] H. Aslanyan, “Greedy set cover estimations”, Int. Conference “Computer Science and Information Technologies”, Yerevan, pp. 143-144, 2003. [17] S. Meguerdichian, F. Koushanfar, M. Potkonjak, and M. Srivastava, “Coverage Problem in Wirelss Ad-Hoc Sensor Networks”, IEEE INFOCOM, pp. 1380–1387, 2001. [18] 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. [19] 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. [20] K. Pahlavan and A. H. Levesque, “Wireless information networks”, John Wiley & Sons, New York, NY, USA, 1995. ²Ýɳñ ó³Ýó»ñáõÙ ÇÝï»ñý»ñ»ÝëÇ ÙÇÝÇÙǽ³óÙ³Ý Ùáï³íáñ ³É·áñÇÃÙ Ð. ²ëɳÝÛ³Ý ²Ù÷á÷áõÙ ¸Çï³ñÏí»É ¿ ³Ýɳñ ó³Ýó»ñáõÙ ÇÝï»ñý»ñ»ÝëÇ ÙÇÝÇÙǽ³óÙ³Ý ËݹÇñÁ, áñÁ Ñ»ï¨Û³ÉÝ ¿. ó³ÝóÇ Ûáõñ³ù³ÝãÛáõñ ѳݷáõÛóÇÝ í»ñ³·ñ»É ѳÕáñ¹³ÏóÙ³Ý ß³é³íÇÕ ³ÛÝå»ë, áñ ó³ÝóÁ ÉÇÝÇ Ï³å³Ïóí³Í ¨ ÙǨÝáõÛÝ Å³Ù³Ý³Ï ó³ÝóáõÙ Ù³ùëÇÙ³É ÇÝï»ñý»ñ»Ýë áõÝ»óáÕ Ñ³Ý·áõÛóÇ ÇÝï»ñý»ñ»ÝëÁ (ѳݷáõÛóÝ Áݹ·ñÏáÕ Ñ³Õáñ¹³ÏóÙ³Ý ßñç³ÝÝ»ñÇ ù³Ý³ÏÁ) ÉÇÝÇ ÙÇÝÇÙ³É: ²Ûë ËݹñÇ Ñ³Ù³ñ ³é³ç³ñÏíáõÙ ¿ µ³½Ù³Ý¹³Ù³ÛÇÝ Å³Ù³Ý³ÏáõÙ ³ß˳ïáÕ Ùáï³íáñ ³É·áñÇÃÙ, áñÁ ·ïÝáõÙ ¿ ϳå³Ïóí³Í ó³Ýó, áñáõÙ Ûáõñ³ù³ÝãÛáõñ ѳݷáõÛóÇ ÇÝï»ñý»ñ»ÝëÁ ãÇ ·»ñ³½³ÝóáõÙ ))log(( 2noptO  -Ý: ²Ûëï»Õ opt -Á ïñí³Í n ѳݷáõÛóÝ»ñáí ó³ÝóÇ ÙÇÝÇÙ³É ÇÝï»ñý»ñ»ÝëÝ ¿: гÛïÝÇ ¿, áñ ËݹÇñÁ Ù»ïñÇÏ³Ï³Ý ï³ñ³ÍáõÃÛáõÝáõÙ ¹Çï³ñÏ»Éáõ ¹»åùáõÙ (áñÁ ³ß˳ï³ÝùáõÙ ¹Çï³ñÏí³Í ¹»åùÝ ¿), )(log nO -Á Ùáï³ñÏÙ³Ý ëïáñÇÝ ë³ÑÙ³ÝÝ ¿: гÛïÝÇ ¿ ݳ¨ µ³½Ù³Ý¹³Ù³ÛÇÝ ³É·áñÇÃÙ, áñÁ ·ïÝáõÙ ¿ ϳå³Ïóí³Í ó³Ýó ³é³í»É³·áõÛÝÁ )( nO ÇÝï»ñý»ñ»Ýëáí: