  We are motivated by the problem of impromptu or as- you-go deployment of
wireless sensor networks. As an application example, a person, starting from a
sink node, walks along a forest trail, makes link quality measurements (with
the previously placed nodes) at equally spaced locations, and deploys relays at
some of these locations, so as to connect a sensor placed at some a priori
unknown point on the trail with the sink node. In this paper, we report our
experimental experiences with some as-you-go deployment algorithms. Two
algorithms are based on Markov decision process (MDP) formulations; these
require a radio propagation model. We also study purely measurement based
strategies: one heuristic that is motivated by our MDP formulations, one
asymptotically optimal learning algorithm, and one inspired by a popular
heuristic. We extract a statistical model of the propagation along a forest
trail from raw measurement data, implement the algorithms experimentally in the
forest, and compare them. The results provide useful insights regarding the
choice of the deployment algorithm and its parameters, and also demonstrate the
necessity of a proper theoretical formulation.
