TY - GEN
T1 - A near-optimal multicast scheme for mobile ad hoc networks using a hybrid genetic algorithm
AU - Liu, Chien Hung
AU - Chiang, Tzu Chiang
AU - Huang, Yueh Min
PY - 2006/11/22
Y1 - 2006/11/22
N2 - Multicast routing is an effective way to communicate among multiple hosts in a network. It outperforms the basic broadcast strategy by sharing resources along general links, while sending information to a set of predefined multiple destinations concurrently. However, it is vulnerable to component failure in ad hoc network due to the lack of redundancy, multiple paths and multicast tree structure. Tree graph optimization problems (GOP) are usually difficult and time consuming NP-hard or NP-complete problems. Genetic algorithms (GA) have been proven to be an efficient technique for solving the GOP, in which well-designed chromosomes and appropriate operators are key factors that determine the performance of the GAs. Limited link, path constraints, and mobility of network hosts make the multicast routing protocol design particularly challenging in wireless ad hoc networks. Encoding trees is a critical scheme in GAs for solving these problems because each code should represent a tree. Prüfer number is the most representative method of vertex encoding, which is a string of n-2 integers and can be transformed to an n-node tree. However, genetic algorithm based on Prüfer encoding (GAP) does not preserve locality, while changing one element of its vector causes dramatically change in its corresponding tree topology. In this paper, we propose a novel GA based on Sequence and Topology encoding (GAST) for multicast protocol is introduced for multicast routing in wireless ad hoc networks and generalizes the GOP of tree-based multicast protocol as well as three associated operators. It has revealed an efficient method of the reconstruction of multicast tree topology and the experimental results demonstrated the effectiveness of GAST compare to GAP technique.
AB - Multicast routing is an effective way to communicate among multiple hosts in a network. It outperforms the basic broadcast strategy by sharing resources along general links, while sending information to a set of predefined multiple destinations concurrently. However, it is vulnerable to component failure in ad hoc network due to the lack of redundancy, multiple paths and multicast tree structure. Tree graph optimization problems (GOP) are usually difficult and time consuming NP-hard or NP-complete problems. Genetic algorithms (GA) have been proven to be an efficient technique for solving the GOP, in which well-designed chromosomes and appropriate operators are key factors that determine the performance of the GAs. Limited link, path constraints, and mobility of network hosts make the multicast routing protocol design particularly challenging in wireless ad hoc networks. Encoding trees is a critical scheme in GAs for solving these problems because each code should represent a tree. Prüfer number is the most representative method of vertex encoding, which is a string of n-2 integers and can be transformed to an n-node tree. However, genetic algorithm based on Prüfer encoding (GAP) does not preserve locality, while changing one element of its vector causes dramatically change in its corresponding tree topology. In this paper, we propose a novel GA based on Sequence and Topology encoding (GAST) for multicast protocol is introduced for multicast routing in wireless ad hoc networks and generalizes the GOP of tree-based multicast protocol as well as three associated operators. It has revealed an efficient method of the reconstruction of multicast tree topology and the experimental results demonstrated the effectiveness of GAST compare to GAP technique.
UR - http://www.scopus.com/inward/record.url?scp=33751094618&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=33751094618&partnerID=8YFLogxK
U2 - 10.1109/AINA.2006.39
DO - 10.1109/AINA.2006.39
M3 - Conference contribution
AN - SCOPUS:33751094618
SN - 0769524664
SN - 9780769524665
T3 - Proceedings - International Conference on Advanced Information Networking and Applications, AINA
SP - 465
EP - 470
BT - Proceedings - 20th International Conference on Advanced Information Networking and Applications
T2 - 20th International Conference on Advanced Information Networking and Applications
Y2 - 18 April 2006 through 20 April 2006
ER -