Minimum power multicast algorithms for wireless networks with a Lagrangian relaxation approach

作者：Wen Yean Fu; Liao Wanjiun^*

来源：Wireless Networks, 2011, 17(6): 1401-1421.

DOI：10.1007/s11276-011-0344-9

• Broadcast
• Energy efficiency
• Mobility
• Multicast
• Lagrangian Relaxation
• Optimization
• Wireless ad hoc networks

Energy efficiency is crucial to the implementation of broadcast and multicast services in wireless ad hoc and sensor networks. This paper proposes a path-based power-efficient approach that minimizes energy consumption in the network by optimizing the transmission ranges of all nodes. Unlike existing link-based and node-based solutions, the proposed approach, which is applicable to both static and mobile wireless networks, constructs minimum-power broadcast trees. This study uses Lagrangian Relaxation (LR) to decompose the tree-construction problem, which is NP-complete, into multiple independently solvable sub-problems. The resulting Lagrange dual solution ensures a lower bound on the objective function value. The proposed approximation heuristic solves the primal problem by obtaining the upper bound of the objective value based on the information from the set of Lagrange multipliers. This study develops a decentralized, near-optimal algorithm to solve the problem. Simulation results show that in randomly generated networks, the proposed method outperforms the existing Minimum Shortest Path Tree (MSPT) algorithm, Prim's Minimum Spanning Tree (PMST) algorithm, and the Broadcast Incremental Power (BIP) algorithm by 30, 10, and 5%, respectively.

• 出版日期2011-8