  We use information theoretic achievable rate formulas for the multi-relay
channel to study the problem of optimal placement of relay nodes along the
straight line joining a source node and a sink node. The achievable rate
formulas that we use are for full-duplex radios at the relays and decode-
and-forward relaying. For the single relay case, and individual power
constraints at the source node and the relay node, we provide explicit formulas
for the optimal relay location and the optimal power allocation to the
source-relay channel, for the exponential and the power-law path-loss channel
models. For the multiple relay case, we consider exponential path-loss and a
total power constraint over the source and the relays, and derive an
optimization problem, the solution of which provides the optimal relay
locations. Numerical results suggest that at low attenuation the relays are
mostly clustered close to the source in order to be able to cooperate among
themselves, whereas at high attenuation they are uniformly placed and work as
repeaters.
  The structure of the optimal power allocation for a given placement of the
nodes, then motivates us to formulate the problem of impromptu ("as-you-go")
placement of relays along a line of exponentially distributed length, with
exponential path- loss, so as to minimize a cost function that is additive over
hops. The hop cost trades off a capacity limiting term, motivated from the
optimal power allocation solution, against the cost of adding a relay node. We
formulate the problem as a total cost Markov decision process, for which we
prove results for the value function, and provide insights into the placement
policy via numerical exploration.
