A Novel QoS Provisioning Algorithm for Optimal Multicast Routing in WMNs
Open Access
- 1 August 2016
- journal article
- research article
- Published by MDPI AG in Future Internet
- Vol. 8 (3) , 38
Abstract
The problem of optimal multicast routing in Wireless Mess Networks (WMNs) with Quality-of-Service (QoS) provisioning, which is Non-Deterministic Polynomial (NP)-complete, is studied in this paper. The existing algorithms are not very efficient or effective. In order to find an approximation optimal solution for WMNs in feasible time from source to the set of destination nodes, combining the previous deterministic algorithm with the well-known Minimum Path Cost Heuristic (MPH) algorithm, a novel multicast heuristic approximation (NMHA) algorithm with QoS provisioning is proposed in this paper to deal with it. The theoretical validations for the proposed algorithm are presented to show its performance and efficiency. After that, the random static networks with different destination nodes are evaluated. Simulations in these networks show that the proposed algorithm can achieve the approximate optimal solution with the approximation factor of 2(1 + ε)(1 − 1/q) and the time complexity of O(qmn2τK−1).Keywords
Funding Information
- the Science and Technology Program of Guangzhou, China (No. 201510010192)
- the Public Welfare Fund and Ability Construction Project of Guangdong Province, China (No. 2016A010101040)
This publication has 34 references indexed in Scilit:
- Physarum Optimization: A Biology-Inspired Algorithm for the Steiner Tree Problem in NetworksIEEE Transactions on Computers, 2015
- QoS routing algorithm with multi-dimensions for overlay networksChina Communications, 2013
- Joint Topology-Transparent Scheduling and QoS Routing in Ad Hoc NetworksIEEE Transactions on Vehicular Technology, 2013
- Design QoS-Aware Multi-Path Provisioning Strategies for Efficient Cloud-Assisted SVC Video Streaming to Heterogeneous ClientsIEEE Transactions on Multimedia, 2013
- Genetic Algorithm for Energy-Efficient QoS Multicast RoutingIEEE Communications Letters, 2012
- MAP: Multiconstrained Anypath Routing in Wireless Mesh NetworksIEEE Transactions on Mobile Computing, 2012
- Routing with multiple quality-of-services constraints: An approximation perspectiveJournal of Network and Computer Applications, 2012
- Computing a Most Probable Delay Constrained Path: NP-Hardness and Approximation SchemesIEEE Transactions on Computers, 2011
- MOEAQ: A QoS-Aware Multicast Routing algorithm for MANETExpert Systems with Applications, 2010
- Two Techniques for Fast Computation of Constrained Shortest PathsIEEE/ACM Transactions on Networking, 2008