Title: An optimal algorithm for small group multicast in wireless sensor networks

Authors: Weizhong Luo; Jianxin Wang; Zhaoquan Cai; Gang Peng; Jiong Guo; Shigeng Zhang

Addresses: Department of Computer Science, Huizhou University, Huizhou 516007, China ' School of Information Science and Engineering, Central South University, Changsha 410083, China ' Department of Computer Science, Huizhou University, Huizhou 516007, China ' Department of Computer Science, Huizhou University, Huizhou 516007, China ' School of Computer Science and Technology, Shandong University, Jinan 250100, China ' School of Information Science and Engineering, Central South University, Changsha 410083, China

Abstract: We propose an optimal algorithm to construct a delay-bounded minimum energy routing tree for multicast in wireless sensor networks. Finding the minimum energy multicast tree with constrained delay has been proved to be a NP-hard problem. Existing works mainly focus on developing approximation or heuristic algorithms to find approximate solutions. We formally define the Min-power h-Multicast problem - to find a minimum energy multicast tree in which the path from the source to every destination node is less than h hops - and translate it into a minimum Steiner tree problem. We then develop a dynamic programming algorithm to get an optimal solution to the problem with a running time that is exponential exclusively with respect to the size of the multicast group. Simulation results show that, compared with existing algorithms, our algorithm saves energy consumption by factors between 19% and 42% with comparable running time for small group multicast.

Keywords: delay-bounded multicast; energy consumption optimisation; FPT; fixed parameter tractable; NP-hard.

DOI: 10.1504/IJAHUC.2018.092883

International Journal of Ad Hoc and Ubiquitous Computing, 2018 Vol.28 No.3, pp.168 - 179

Received: 09 Jul 2015
Accepted: 03 May 2016
Published online: 02 Jul 2018 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article