  Our work is motivated by the need for impromptu (or "as-you-go") deployment
of relay nodes (for establishing a packet communication path with a control
centre) by fire-men/commandos while operating in an unknown environment. We
consider a model, where a deployment operative steps along a random lattice
path whose evolution is Markov. At each step, the path can randomly either
continue in the same direction or take a turn "North" or "East," or come to an
end, at which point a data source (e.g., a temperature sensor) has to be placed
that will send packets to a control centre at the origin of the path. A
decision has to be made at each step whether or not to place a wireless relay
node. Assuming that the packet generation rate by the source is very low, and
simple link-by-link scheduling, we consider the problem of relay placement so
as to minimize the expectation of an end-to-end cost metric (a linear
combination of the sum of convex hop costs and the number of relays placed).
This impromptu relay placement problem is formulated as a total cost Markov
decision process. First, we derive the optimal policy in terms of an optimal
placement set and show that this set is characterized by a boundary beyond
which it is optimal to place. Next, based on a simpler alternative
one-step-look-ahead characterization of the optimal policy, we propose an
algorithm which is proved to converge to the optimal placement set in a finite
number of steps and which is faster than the traditional value iteration. We
show by simulations that the distance based heuristic, usually assumed in the
literature, is close to the optimal provided that the threshold distance is
carefully chosen.
