Heuristic algorithms for scheduling multiple timeslots and channels in industrial wireless sensor networks

This dissertation focuses on Medium Access Control (MAC) protocol that provides guaranteed end-to-end delay for industrial applications, and two heuristic scheduling algorithms: one involving metaheuristics, i.e., Simulated Annealing (SA) and Particle Swarm Optimization (PSO), and the other involving a greedy heuristic for wireless industrial sensor networks with multi-channel and multi-timeslot that can achieve a guaranteed end-to-end delay. First, we study one of the new MAC protocols in IEEE 802.15.4e standard called Deterministic and Synchronous Multichannel Extension (DSME) mode. DSME enhances the existing IEEE 802.15.4 GTS (Guaranteed Time Slot) to provide robust and timely data delivery for industrial wireless mesh sensor networks. DSME also provides two channel diversity techniques, namely channel hopping and channel adaptation, to cope with dynamic channel conditions. Second, we implement the two metaheuristic algorithms, namely the SA and the PSO, to schedule multiple channels and timeslots in a multi-hop wireless sensor network. Timely communication in wireless multi-hop sensor networks requires high throughput and low delay, both of which can be achieved by effectively exploiting multiple channels and timeslots. Efficient scheduling becomes indispensable if multiple channels and timeslots are utilized. Optimum scheduling of multiple channels and timeslots in multi-hop networks is an NP-complete problem. We apply metaheuristic approaches to solve the scheduling problem because of the fact that the solution we are seeking is not the global optimal and that a sub-optimal solution would suffice to guarantee a given end-to-end delay bound. Third, we introduce a novel scheduling algorithm using multi-channel and multi-timeslot with the objective of minimizing the end-to-end delay in a tree topology-based wireless sensor network. In a tree topology, the data traffic always flows from a child (transmitter) to a parent (receiver) towards the coordinator. Since interference occurs at the receiver end, i.e., the parent, in order to cope with interference, the channel of each parent node that experiences interference is scheduled starting with the parent with the most number of interfering nodes. The algorithm exploits a staggered sequential timeslot allocation in terms of end-to-end paths to minimize end-to-end delay rather than minimizing the total number of the timeslots required by the network in terms of individual branches.