Evolutionary algorithms for time division multiple access broadcast scheduling problem in wireless multi hop networks

Abstract

Wireless multi-hop network (WMN) plays an important role in the communication industry due to the advancement in wireless communication and mobile computing technologies. In wireless ad hoc network, single-hop and multi-hop networks do not rely on a pre-existing infrastructure such as routers in wired networks or access points in wireless networks. Ad hoc network is a self-organized multi-hop wireless network, which relies neither on fixed infrastructure nor on predetermined connectivity. First, in particular, only a few algorithms concentrate remarkably on reducing the length of TDMA frame and improving the number of transmissions. Secondly, very little attention has been paid to improving the performance of algorithms in terms of execution time even while dealing with MEB problem. This study is concerned with the idea of evolutionary computation to solve BSP and MEB. The present research work includes the following contributions: (1) To define an efficient broadcast TDMA schedule with minimum length TDMA frame and maximum channel utilization in reduced computation time using evolutionary algorithms and (2) To solve the minimum energy broadcast tree problem over wireless ad hoc networks in less computation time using memetic algorithm. The research work focuses on the use of algorithms such as genetic algorithm (GA), immune genetic algorithm (IGA), memetic algorithm (MA) and harmony search using memetic algorithm (HSMA) to solve broadcast scheduling for TDMA in WMN with reduced computation time. The research work delineates the issues that arise in the context of wireless multi-hop networks. The algorithms are evaluated through extensive simulations using MATLAB simulation tool. Finally, the results are compared with recently proposed algorithms. The simulation results on numerous problem instances confirm that the algorithms discussed in this thesis significantly outperforms several heuristic and evolutionary algorithms in terms of solution quality. newline newline newline