A genetic algorithm based on extended sequence and topology encoding for the multicast protocol in two-tiered WSN

摘要

With the rapid evolution of some application technologies in two-tiered wireless sensor network (WSNs), more and more new communication services are emerging quickly, such as multicast video conferencing, retrieval systems and video-on demand, which need the multimedia communication services in multicast mode. Multicast routing is thereby an effective way to communicate among multiple cluster head nodes (CNs) in the network. However, severe energy constraints, Limited link and path constraints make the multicast routing protocol design particularly challenging in WSNs. A fundamental challenge in WSNs is how to maximize network lifetime with regard to a given multicast mission and a certain amount of initial energy provisioning. In this paper, we propose a novel genetic algorithm (GA) based on extended sequence and topology encoding (GAEST) for the multicast protocol in two-tiered WSN. We design power and energy model for GAEST to reasonably adjust CN’s Euclid distance according to transmission power calculated by fitness function. To take residual battery energy of CNs and energy balance between CNs into consideration, extended sequence and topology encoding not only holds the T chromosomes which represents the gene topology and records position index of CN’s father node, but adds a crucial information for each gene in S chromosomes: the number of CN’s children. S-chromosomes crossover of GAEST can change the multicast tree structure drastically and give genetic algorithm the ability of global search to leap from a point in the solution space to a far away point. GAEST improves the mutation process according to Mutation-Replace model, which reasonably swaps the leaf node holding maximum residual energy node with the non-leaf one with the minimum. Simulation results show that GAEST prolongs the lifetime of multicast service compared with Directed Diffused protocol, and increases the packet delivery ratio and fitness value in comparison with GAP, and still obtains the optimal convergence speed from different crossover or mutation probabilities.