APICe » Theses » Heuristic Multicast Routing Algorithms in WSNs with Incomplete Network Knowledge

Heuristic Multicast Routing Algorithms in WSNs with Incomplete Network Knowledge 

Valeri Katerinchuk


This PhD Thesis explores alternative algorithms for multicast routing in wireless sensor networks, where nodes have limited knowledge of the overall network. A number of alternative algorithms have been proposed to achieve different, possibly competing, objectives, and their performance is compared in terms of these objectives. Limited network knowledge can lead to severe temporal and energy penalties when applying traditional methods of multicast routing in networks, such as local search, as nodes are unable to calculate the appropriate route to destinations without sending messages through the network. There exist a large variety of algorithms attempting to improve the results of multicast within this complex problem space, including several guided broadcast methodologies. However, due to the number of possible variations in the problem formulation it is challenging to understand what kind of approach is most effective in achieving any one of a number of goals for a specific permutation of variables. This is especially true for wireless sensor networks where energy conservation is often a paramount concern.

In this thesis we investigate the effects of various routing strategies on the performance of consecutive multicast routing requests against a number of objectives in a large space of problem permutations with the expectation of understanding the impact of strategies and variable settings on these goals and deriving guidelines for future algorithms. We undertake this investigation by means of Monte Carlo simulation, comparing the performance of different algorithms on multiple criteria over selected network topologies.


Peter McBurney (Supervisor)