  We study the problem of optimal sequential ("as-you-go") deployment of
wireless relay nodes as a person walks along a line of random length (with a
known distribution). The objective is to create an impromptu multihop wireless
network for connecting a packet source to be placed at the end of the line with
a sink node located at the starting point, to operate in the light traffic
regime. As the deployment person walks along the line from the sink towards the
source, at every step, he measures the channel quality to one (or more)
previously placed relays, and places the relay nodes based on these
measurements, so as to minimize either the sum power or the maximum power from
the source to the sink node in the resultant network, subject to a constraint
on the expected number of relays placed. For each of these two objectives, two
different relay selection strategies are considered: (i) each relay
communicates with the sink via its immediate previous relay, (ii) the
communication path can skip some of the deployed relays. With appropriate
modeling assumptions, we formulate each of these problems as a Markov decision
process (MDP). We provide the optimal policy structures for all these cases,
and provide illustrations, via numerical results, for some typical parameters.
