  In geographical forwarding of packets in a large wireless sensor network
(WSN) with sleep-wake cycling nodes, we are interested in the local decision
problem faced by a node that has custody of a packet and has to choose one
among a set of next-hop relay nodes to forward the packet towards the sink.
Each relay is associated with a reward that summarizes the benefit of
forwarding the packet through that relay. We seek a solution to this local
problem, the idea being that such a solution, if adopted by every node, could
provide a reasonable heuristic for the end-to-end forwarding problem. Towards
this end, we propose a relay selection problem comprising a forwarding node and
a collection of relay nodes, with the relays waking up sequentially at random
times. At each relay wake-up instant the forwarder can choose to probe a relay
to learn its reward value, based on which the forwarder can then decide whether
to stop (and forward its packet to the chosen relay) or to continue to wait for
further relays to wake-up. The forwarder's objective is to select a relay so as
to minimize a combination of waiting-delay, reward and probing cost. Our
problem can be considered as a variant of the asset selling problem studied in
the operations research literature. We formulate our relay selection problem as
a Markov decision process (MDP) and obtain some interesting structural results
on the optimal policy (namely, the threshold and the stage-independence
properties). We also conduct simulation experiments and gain valuable insights
into the performance of our local forwarding-solution.
