Search algorithms for path planning problems in harsh wireless sensor network environment

This dissertation presents three heuristic search algorithms which all of them descended from the origin Dijkstra’s algorithm that solve multiple different problems arise from path planning in WSN environment. The three addressed problems are 1) long initial computation delay in dynamic environment, 2) slow reaction towards rapid change of goal points and massive number of node depending on single source of computational power, and 3) tradeoffs between optimality and computational effort to achieve optimality in TSP path planning problem. Literatures are reviewed, restructured in chronological form, and discussed. Open issues of reviewed algorithms had been briefed in this dissertation. In order to solve the addressed problem, this dissertation proposed three algorithms which are Enhanced D*, Natural Behaviour Navigation (NBN), and Frothing Waypoint Navigation (FWN). Each algorithm solves its respective problem with Enhanced D* solving long initial delay in dynamic environment, NBN solves harsh conditions with limited computational power, and FWN optimized the result of TSP path planning problem with minimal computational effort. Experiments have been done for each algorithm by comparing with other suitable algorithms. Multiple performance metrics have been defined and discussed for all experiments. The metrics included but not limited to the few following: Average Path Length, Initial Delay, Computational Time, Cell Visit, and so on. Finally, conclusion is drawn from the results of all experiments at the end of the dissertation and future works are proposed along.

Text FSKTM 2017 67 IR.pdf Download (1MB)

Actions (login required)

View Item