An algorithm for joint location, coverage and routing in wireless sensor networks

• Autorzy: Jagusiak S. , Józefczyk J.
• Języki publikacji: EN

Abstrakty

EN

This paper deals with selected joint problem of location, coverage and routing in a class of wireless sensor networks. The minimization of the total cost of data collection and transmission as well as sensors and sinks location is considered. Its NP-hardness is justified and a heuristic solution algorithm based on the result of the circulation problem in a directed graph is proposed. The quality of the algorithm has been assessed during numerical experiments, and the examples of corresponding results are presented.

Słowa kluczowe

EN

location; coverage; routing; wireless sensor networks; circulation

• Wydawca: Komisja Informatyki Polskiej Akademii Nauk, Oddział w Gdańsku
• Czasopismo: Journal of Theoretical and Applied Computer Science
• Rocznik: 2013
• Tom: Vol. 7, nr 3
• Strony: 61--71
• Opis fizyczny: Bibliogr. 27 poz., rys., tab.

Twórcy

autor

Jagusiak S.

• Faculty of Computer Science and Management, Wroclaw University of Technology, Wroclaw, Poland

autor

Józefczyk J.

• Faculty of Computer Science and Management, Wroclaw University of Technology, Wroclaw, Poland

Bibliografia

• [1] Abbasi A.A. and Younis M. A survey on clustering algorithms for wireless sensor networks. Computer Communications, 30, 2826-2841, 2007.
• [2] Bashar S. and Ding Z. Admission control and resource allocation in a heterogeneous OFDMA wireless network. IEEE Transactions onWireless Communications Archive, 8, 4200-4210, 2009.
• [3] Ben-Daya M., As’ad R., Seliman M. An integrated production inventory model with raw material replenishment considerations in a three layer supply chain. International Journal of Production Economics, 143, 53-61, 2010.
• [4] Bin W., Wenxin L., Liu L. A survey of energy conservation, routing and coverage in wireless sensor networks. In: Proceedings of 7th International Conference on Active Media Technology, Springer-Verlag, Berlin Heidelberg, 6890, 5970, 2011.
• [5] Byrka J. and Aardal K. An optimal bifactor approximation algorithm for the metric uncapacitated facility location problem. SIAM Journal on Computing, 39, 2212-2231, 2010.
• [6] Chuan Z., Chunlin Z., Lei S., Guangjie H. A survey on coverage and connectivity issues in wireless sensor networks. Journal of Network and Computer Applications, 35, 619 - 632, 2012.
• [7] Coelho L.C., Cordeau J.-F., Laporte G. The inventory-routing problem with transshipment. Computers & Operations Research, 39, 11, 2537-2548, 2012.
• [8] Drezner Z., Scott C., Song J.-S. The central warehouse location problem revisited. IMA Journal of Management Mathematics, 14, 321-336, 2003.
• [9] Filcek G. and Józefczyk J. Managing production and transportation in balanced supply networks. Systems Science, 35, 49-59. 2009.
• [10] Guney E., Aras N., Altnel I.K., Ersoy C. Efficient solution techniques for the integrated coverage, sink location and routing problem in wireless sensor networks. Computers & Operations Research, 39, 1530 - 1539, 2012.
• [11] Hamacher H.W. and Hennes H. Integrated scheduling and location models: single machine makespan problems. Studies in Locational Analysis, 16, 77-90, 2007.
• [12] Hoffman A. J. Some recent applications of the theory of linear inequalities to extremal combinatorial analysis. In: Proceedings of Symposium in Applied Mathematics, Amer. Math. Soc, 113-127, 1960.
• [13] Józefczyk J. Selected decison-making problems for complex operation systems (in Polish). Wroclaw Universty of Technology Press, Wroclaw, 2001.
• [14] Józefczyk J. Scheduling tasks on moving executors to minimize the maximum lateness. European Journal of Operational Research, 131, 171-187, 2001.
• [15] Kalsch M.T. and Drezner Z. Solving scheduling and location problems in the plane simultaneously. Computerts & Operations Research, 37, 256-264, 2010.
• [16] Korsvik J. E., Fagerholt K., Laporte G. A large neighbourhood search heuristic for ship routing and scheduling with split loads. Computers & Operations Research, 38, 474-483, 2011.
• [17] Kulkarini R.V., Fox Andrster A., Venayagamoorthy G.K. Computational intelligence in wireless sensor networks:A survey. Communications Surveys Tutorials, 13, 68-96, 2011.
• [18] Li J., Chen H., Chu F. Performance evaluation of distribution strategies for the inventory routing problem. European Journal of Operational Research, 202, 412-419, 2010.
• [19] Luo J., Rosenberg C., Girard A. Engineering wireless mesh networks: joint scheduling, routing, power control, and rate adaptation. IEEE/ACM Transactions on Networking, 18, 1387-1400, 2010.
• [20] Moin N.H. and Salhi S. Inventory routing problems: a logistical overview. Journal of the Operational Research Society, 58, 1185-1194, 2007.
• [21] Metters R.D. Interdependent transportation and production activity at the United States postal service. Journal of the Operational Research Society, 47, 27-37, 1996.
• [22] Nagy G. and Salhi S. Location-routing: Issues, models and methods. European Journal of Operational Research, 177, 649-672, 2007.
• [23] Niculescu D. Positioning in ad hoc sensor networks. Network, IEEE, 18, 24-29, 2004.
• [24] Prodhon C.A Hybrid evolutionary algorithm for the periodic location-routing problem. European Journal of Operational Research, 210, 204-212, 2004.
• [25] Shankarananda B.M., and Saxena, A. Energy efficient localized routing algorithm for wireless sensor networks. In: Proceedings of 3rd International Conference on Electronics Computer Technology (ICECT), 72-75, 2011.
• [26] Wang Y. and Huang Z. Coverability of Wireless Sensor Networks. Tsinghua Science & Technology, 6, 622-631, 2011.
• [27] Zou L., Lu M., Xiong Z. A distributed algorithm for the dead end problem of location based routing in sensor networks. IEEE Transactions on Vehicular Technology, 54, 1509-1522, 2005