Geographic Dijkstra-Based Multicast Algorithm for Wireless Sensor Networks

• Autorzy: Musznicki B , Tomczak M. , Zwierzykowski P.

Identyfikatory

DOI

10.2478/v10248-012-0013-3

• Języki publikacji: EN

Abstrakty

EN

Limited resources in Wireless Sensor Networks (WSNs) are the key concern that needs to be given a careful consideration when studying virtually any aspect of a sensor network. Therefore, energy demands and radio bandwidth utilization should be addressed, especially in one-to-many communication. It is evident that a need for centralized networkwide topology knowledge can jeopardize scarce energy resources of a sensor network. Thus, localized geographic multicast relies solely on locally available information about the position of current node, other nodes within the radio range and the location of destination group members. Greedy multicast routing procedures often transport messages along paths that may be far from being optimal. Therefore, Dijkstrabased Localized Energy-Efficient Multicast Algorithm (DLEMA) is presented, described with pseudocode, and discussed. DLEMA focuses on discovering energy shortest paths leading through nodes that provide the maximum geographical advance towards desired destinations. Local routes are followed owing to the use of a source routing technique. Additionally, the algorithm takes advantage of the broadcast nature of omnidirectional radio communication and utilizes perimeter routing to find a solution for local optimum situations. The analysis of the simulation results confirms interesting characteristics of the proposed algorithm.

Słowa kluczowe

EN

WSNs; multicast network quality; DLEMA; TTL; sensor networks

• Wydawca: Instytut Telekomunikacji i Informatyki Uniwersytetu Technologiczno-Przyrodniczego w Bydgoszczy
• Czasopismo: Image Processing & Communications
• Rocznik: 2012
• Tom: Vol. 17, no. 1-2
• Strony: 33--46
• Opis fizyczny: Bibliogr. 24 poz., rys.

Twórcy

autor

Musznicki B

• Poznań University of Technology, Faculty of Electronics and Telecommunications, Chair of Communications and Computer Networks, Polanka 3, 60-965 Poznań, Poland

autor

Tomczak M.

• Poznań University of Technology, Faculty of Electronics and Telecommunications, Chair of Communications and Computer Networks, Polanka 3, 60-965 Poznań, Poland

autor

Zwierzykowski P.

• Poznań University of Technology, Faculty of Electronics and Telecommunications, Chair of Communications and Computer Networks, Polanka 3, 60-965 Poznań, Poland

Bibliografia

• [1] C. Garrozi and A. Araujo, Multiobjective Generic Algorithm for Multicast Routing, in Proc. of IEEE Congress on Evolutionary Computation, Vancouver, BC, Canada, July 2006, pp. 2513-2520.
• [2] B. Musznicki, M. Tomczak and P. Zwierzykowski, Dijkstra-based Localized Multicast Routing in Wireless Sensor Networks, in Proc. of CSNDSP 2012, 8th IEEE, IET Int. Symposium on Communication Systems, Networks and Digital Signal Processing, Pozna´n, Poland, Aug. 2012.
• [3] B. Musznicki and P. Zwierzykowski, The Factors Influencing Energy Efficiency of Flooding Algorithms for Wireless Sensor Networks, in Information Systems Architecture and Technology, Networks and Networks’ Services. Wrocław, Poland: Oficyna Wydawnicza Politechniki Wrocławskiej, 2010, pp. 211-222.
• [4] H. Chen, P. Huang, H. C. So, and K. Sezaki, Mobility-Assisted Position Estimation in Wireless Sensor Networks, in Proc. of 14th IEEE International Conference on Parallel and Distributed Systems, Melbourne, Australia, Dec. 2008, pp. 607-614.
• [5] Y. Yu, R. Govindan, and D. Estrin, Geographical and energy aware routing: a recursive data dissemination protocol for wireless sensor networks, University of California, Los Angeles, Tech. Rep.,2001.
• [6] K. Seada and A. Helmy, Efficient and robust geocasting protocols for sensor networks, Computer Communications, pp. 151-161, 2006.
• [7] W. Zhang, X. Jia, C. Huangand, and Y. Yang, Energy-aware location-aided multicast routing in sensor networks, in Proc. of International Conference on Wireless Communications, Networking and Mobile Computing, Wuhan, China, Sept. 2005, pp. 901-904.
• [8] J. A. Sanchez, P. M. Ruiz, J. Liu, and I. Stojmenovic, Bandwidth-Efficient Geographic Multicast Routing Protocol for Wireless Sensor Networks, IEEE Sensors Journal, pp. 627-636, Sept. 2007.
• [9] J. A. Sanchez and P. M. Ruiz, LEMA: Localized Energy-Efficient Multicast Algorithm based on Geographic Routing, in Proc. of 31st IEEE Conference on Local Computer Networks, Tampa, USA, Nov. 2006, pp. 3-12.
• [10] J. E. Wieselthier, G. D. Nguyen, and A. Ephremides, Energy-Efficient Broadcast and Multicast Trees in Wireless Networks, Mobile Networks and Applications, vol. 7, no. 6, pp. 481-492, Dec. 2002.
• [11] E. Kranakis, H. Singh, and J. Urrutia, Compass Routing on Geometric Networks, in Proc. of 11th Canadian Conference on Computational Geometry, Vancouver, Canada, Aug. 1999, pp. 51-54.
• [12] D. Koutsonikolas, S. Das, Y. C. Hu, and I. Stojmenovic, Hierarchical Geographic Multicast Routing for Wireless Sensor Networks, in Proc. of International Conference on Sensor Technologies and Applications, Valencia, Spain, Oct. 2007, pp. 347-354.
• [13] S. M. Das, H. Pucha, and Y. C. Hu, Distributed Hashing for Scalable Multicast in Wireless Ad Hoc Networks, IEEE Transactions on Parallel and Distributed Systems, vol. 19, no. 3, pp. 347-362, March 2008.
• [14] J. B. Kruskal, On the shortest spanning subtree of a graph and the traveling salesman problem, Proc. of the American Mathematical Society, vol. 7, no. 1, pp. 48-50, Feb. 1956.
• [15] B. Karp and H. T. Kung, GPSR: Greedy Perimeter Stateless Routing forWireless Networks, in Proc. of 6th Annual ACM/IEEE International Conference on Mobile Computing and Networking, Boston, USA, Aug. 2000, pp. 243-254.
• [16] K. J. Supowit, The Relative Neighborhood Graph, with an Application to Minimum Spanning Trees, J. ACM, vol. 30, pp. 428-448, July 1983.
• [17] E. W. Dijkstra, A note on two problems in connexion with graphs, Numerische Mathematik, vol. 1, pp. 269-271, 1959.
• [18] J. A. Sanchez and P. M. Ruiz, Exploiting Local Knowledge to Enhance Energy-Efficient Geographic Routing, in Proc. of MSN 2006, Second International Conference on Mobile Ad-hoc and Sensor Networks, Hong Kong, China, Dec. 2006, pp. 567-578.
• [19] M. Piechowiak and P. Zwierzykowski, The Influence of Network Topology on the Efficiency of Multicast Heuristic Algorithms, in Proc. of 5th International Symposium on Communication Systems, Networks and Digital Signal Processing, Patras, Greece, July 2006, pp. 115-119.
• [20] P. Santi, Topology Control in Wireless Ad Hoc and Sensor Networks, ACM Computing Surveys, vol. 33, no. 2, pp. 164-194, June 2005.
• [21] M. Piechowiak, M. Stasiak, and P. Zwierzykowski, The Influence of Group Members Arrangement on the Multicast Tree Cost, International Journal on Advances in Systems and Measurements, vol. 2, no. 2-3, pp. 248-257, 2009.
• [22] J. A. Sanchez and P. M. Ruiz, Energy-efficient Geographic Multicast Routing for Error-prone Wireless Sensor Networks, in Proc. of IEEE Radio and Wireless Symposium, Long Beach, USA, Jan. 2007, pp. 443-446.
• [23] Y.-M. Song, S.-H. Lee, and Y.-B. Ko, FERMA: An Efficient Geocasting Protocol for Wireless Sensor Networks with Multiple Target Regions, in Proc. of EUC Workshops 2005, Nagasaki, Japan, Dec. 2005, pp. 1138-1147.
• [24] H. Park, J. Lee, S. Park, S. Oh, and S.-H. Kim, Multicast Protocol for Real-Time Data Dissemination in Wireless Sensor Networks, IEEE Communications Letters, vol. 15, no. 12, pp. 1291-1293, Dec. 2011.