  We are motivated by the need, in some applications, for impromptu or
as-you-go deployment of wireless sensor networks. A person walks along a line,
making link quality measurements with the previous relay at equally spaced
locations, and deploys relays at some of these locations, so as to connect a
sensor placed on the line with a sink at the start of the line. In this paper,
we extend our earlier work on the problem (see [1]) to incorporate two new
aspects: (i) inclusion of path outage in the deployment objective, and (ii)
permitting the deployment agent to make measurements over several consecutive
steps before selecting a placement location among them (which we call
backtracking). We consider a light traffic regime, and formulate the problem as
a Markov decision process. Placement algorithms are obtained for two cases: (i)
the distance to the source is geometrically distributed with known mean, and
(ii) the average cost per step case. We motivate the per-step cost function in
terms of several known forwarding protocols for sleep-wake cycling wireless
sensor networks. We obtain the structures of the optimal policies for the
various formulations, and provide some sensitivity results about the policies
and the optimal values. We then provide a numerical study of the algorithms,
thus providing insights into the advantage of backtracking, and a comparison
with simple heuristic placement policies.
