Bi-criteria Gateway Placement Problem in Wireless Sensor Networks

• Autorzy: Czajko M. M. , Wojciechowski J. M.
• Języki publikacji: EN

Abstrakty

EN

Over the last few years, wireless sensor networks (WSNs) have started to play more and more important role in civil and military applications. A typical sensor network consists of resource-constrained sensing nodes, which monitor environment and send the data to more powerful gateway nodes. The goal of gateway nodes is to aggregate, process and send the data to other gateways or directly to sink nodes. The proper placement of nodes is needed to provide good network operation. Sensing nodes are often placed in a random manner unlike gateways. Gateways, due to their role and cost, are installed rather in a controlled way. In this paper, a bi-criteria gateway placement problem is introduced. The problem is shown to be NP-hard. We formulate it as a linear programming problem, then we develop the Multi-criteria Simulated Allocation (MSAL) heuristic algorithm, for the purpose of cost-effective gateway deployment and power-effective wireless connection management. Finally, we evaluate the efficiency of the algorithm by comparison with the exact method.

Słowa kluczowe

EN

wireless sensor network; bi-criteria optimization; heuristics

• Wydawca: Polish Academy of Sciences, Committee of Electronics and Telecommunication
• Czasopismo: International Journal of Electronics and Telecommunications
• Rocznik: 2010
• Tom: Vol. 56, No. 3
• Strony: 215--221
• Opis fizyczny: Bibliogr. 14 poz., wykr.

Twórcy

autor

Czajko M. M.

autor

Wojciechowski J. M.

• Orange Labs Poland, Telekomunikacja Polska S.A., Obrzeżna 7, 02-691 Warsaw, Poland,

Bibliografia

• [1] K. Akkaya, M. Younis, “COLA: a coverage and latency aware actor placement for wireless sensor and actor networks,” in Proc. of the IEEE Vehicular Technology Conference, Montreal, 2006, pp. 1-6.
• [2] A. Bogdanov, E. Maneva, S. Riesenfeld, “Power-aware base station positioning for sensor networks,” in Proc. of the 23rd International Annual Joint Conference of the IEEE Computer and Communications Societies, Hong-Kong, 2004, pp. 575-585.
• [3] J.-Y. Choi, S.-M. Jung, Y.-J. Han, T.-M. Chung, “Advanced concentric-clustering routing scheme adapted to large-scale sensor networks,” in Proc. of the 2nd International Conference on Sensor Technologies and Applications, Cap Esterel, 2008, pp. 366-371.
• [4] M. Czajko, J. Wojciechowski, “Centralized traffic management of large-scale wireless sensor networks for rapid land phenomena monitoring”, in Proc. of the Workshop on Sensor Networks for Earth and Space Science Applications, in conjunction with the 8th ACM/IEEE International Conference on Information Processing in Sensor Networks, San Francisco, 2009, pp. 49-57.
• [5] M. Czajko, J. Wojciechowski, “MGRASP and MSAL algorithms for centralized traffic management of large wireless sensor networks”, in Proc. of Evolutionary Computation and Global Optimization, Zawoja, 2009, pp. 43-50.
• [6] A. S. Da Cunha, A. Lucena, “Algorithms for the degree-constrained minimum spanning tree problem,” Electronic Notes in Discrete Mathematics, vol. 19, pp. 403-409, Jun. 2005.
• [7] P. Gajowniczek, “Design of telecommunication networks by Simulated Allocation,” Ph.D. dissertation, Institute of Telecommunication, Warsaw University of Technology, Warsaw, Poland, 2001.
• [8] S. R. Gandham, M. Dawande, R. Prakash, S. Venkatesan, “Energy efficient schemes for wireless sensor networks with multiple mobile base stations,” in Proc. of the IEEE Global Telecommunications Conference, San Francisco, 2003, pp. 377-381.
• [9] L. Gouveia, “Multicommodity flow models for spanning trees with hop constraints,” European Journal of Operational Research, vol. 95, pp. 178-190, Nov. 1996.
• [10] W. B. Heinzelman, A. P. Chandrakasan, H. Balakrishnan, “An application-specific protocol architecture for wireless microsensor networks,” IEEE Transactions on Wireless Communications, vol. 1, pp. 660-670, Oct. 2002.
• [11] E. I. Oyman, C. Ersoy, “Multiple sink network design problem in large scale wireless sensor networks,” in Proc. of the IEEE International Conference on Communications, Paris, 2004, pp. 3663-3667.
• [12] M. Pióro, D. Medhi, Routing, flow, and capacity design in communication and computer networks. San Francisco: Morgan Publishers, 2004.
• [13] W. Youssef, M. Younis, “Intelligent estimation of gateways count for reduced data latency in wireless sensor networks,” in Proc. of the IEEE Global Telecommunications Conference, Washington, 2007, pp. 903-907.
• [14] W. Youssef, M. Younis, “Intelligent gateways placement for reduced data latency in wireless sensor networks,” in Proc. of the IEEE International Conference on Communications, Glasgow, 2007, pp. 3805-3810.