Title: Improved PSOR algorithm for minimum power multicast tree problem in wireless ad hoc networks

Authors: Manki Min, Austin F. O'Brien, Sung Y. Shin

Addresses: Department of EECS, South Dakota State University, Brookings, SD 57007, USA. ' Department of Mathematics and Statistics, South Dakota State University, Brookings, SD 57007, USA. ' Department of EECS, South Dakota State University, Brookings, SD 57007, USA

Abstract: In this paper, we introduce the application of partitioning-based SOR (PSOR) algorithm to the minimum energy multicast tree problem in wireless ad hoc networks. PSOR for broadcast was proposed in our previous work and it can be applied to the multicast tree problem with small modification. PSOR for multicast maintains the same theoretical bound for the approximation ratio and computational running time as PSOR for broadcast. The computational results show improvement in the solution quality (in terms of the sum of the transmission powers). PSOR outperforms the other algorithms and it shows better results compared to ISOR (iterated version of SOR). In this paper, we used the results of the corrected version of SOR for the comparisons. In addition, we present an improved version of PSOR based on simplified partition recovery method. The simulation results show significant reduction of computation time by the improved version.

Keywords: minimum power; multicast tree; wireless ad hoc networks; wireless networks; partitioning-based SOR; PSOR; partition recovery; simulation.

DOI: 10.1504/IJSNET.2010.036194

International Journal of Sensor Networks, 2010 Vol.8 No.3/4, pp.193 - 201

Published online: 27 Oct 2010 *

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