Wireless sensor network aided search and rescue in trails

Abstract

In recent years, wireless sensor networks have been used in applications of data gathering and target localization across large geographical areas. In this thesis, we study the issues involved in applying wireless sensor networks to search and rescue of lost hikers in trails and focus on the optimal placement of sensors and access points such that the cost of search and rescue is minimized. Particularly, we address two problems: a) how to identify the lost hiker position as accurately as possible, i.e., obtain a small search region containing the lost hiker; and (b) how to search efficiently in search regions for different trail topologies and search agent capabilities. We study the problem of achieving smaller search regions with different problem attributes. For simpler trail topologies, we propose theoretical models that consider both efficiency and accuracy criteria and present analytical results. For complicated graph topologies, we develop efficient heuristic algorithms with various heuristics. In addition, we analyze the difference of single hiker and multiple hiker scenarios with different hiking dynamics. After access point deployment is decided, the actual cost of search in individual search regions can be computed. We analyze four different types of search and rescue agents, present algorithms to find the optimal search pathes for each one of them, and compute their search costs. The algorithms are developed based on solving Chinese Postman problems. Next, we present extensive experimental results to compare the performances of different methods and examine the accuracy of the mathematical models. A very fast heuristic method, divide-merge, is shown to outperform all others and finds near-optimal solutions. We also shows the effects of the graph topologies and number of access points on the solution qualities. Generally speaking, more access points lead to smaller search regions. Further improvement by moving the access points from vertices to edges is easily achieved when the number of access points is large or/and the average degree of vertices is small. Finally, we extend our results by relaxing the assumption of the uniform distribution of the hiker missing probability. We analyze the problem complexity and present a general solution.