Author_Institution :
Dept. of Electr. & Comput. Eng., Univ. of British Columbia, Vancouver, BC, Canada
Abstract :
A mobile, autonomous searcher is tasked with finding the source node of a broadcast message in a randomly deployed network of location-agnostic wireless sensor nodes. Messages are assumed to propagate by flooding, with random node-to-node delays. In networks of this type, the hop count of the broadcast message, given the distance from the source node, can be approximated by a simple parametric distribution. The mobile searcher can interrogate a nearby sensor node to obtain, with a given success probability, the hop count of the broadcast message. We model the search as an infinite-horizon, undiscounted cost, online POMDP and solve it approximately through policy rollout. The cost-to-go at the rollout horizon is approximated by a heuristic based on an optimal search plan in which path constraints and assumptions about future information gain are relaxed. This cost can be computed efficiently, which is essential for the application of Monte Carlo methods, such as rollout, to stochastic planning problems. Finally, we demonstrate that our rollout approach outperforms a popular method of target search based on a myopic, mutual information utility.
Keywords :
Markov processes; Monte Carlo methods; mobile communication; probability; synchronisation; telecommunication network planning; wireless sensor networks; Monte Carlo methods; broadcast message; information gain; location-agnostic wireless sensor nodes; mobile autonomous searcher; myopic mutual information utility; node-to-node delays; online POMDP; parametric distribution; partially observable Markov decision process; path constraints; policy rollout; rollout algorithm; source node; stochastic planning problems; target search; wireless sensor network; Delays; Mobile communication; Mutual information; Search problems; Stochastic processes; Uncertainty; Wireless sensor networks;
