A distributed adaptive opportunistic routing scheme for multi hop wireless ad-hoc networks is proposed. The proposed scheme utilizes a reinforcement learning framework to opportunistically route the packets even in the absence of reliable knowledge about channel statistics and network model. This scheme is shown to be optimal with respect to an expected average per packet reward criterion. The proposed routing scheme jointly addresses the issues of learning and routing in an opportunistic context, where the network structure is characterized by the transmission success probabilities. In particular, this learning framework leads to a stochastic routing scheme which optimally “explores” and “exploits” the opportunities in the network.
Such fixed path schemes fail to take advantages of broadcast nature and opportunities provided by the wireless medium and result in unnecessary packet retransmissions. The opportunistic routing decisions, in contrast, are made in an online manner by choosing the next relay based on the actual transmission outcomes as well as a rank ordering of neighboring nodes. Opportunistic routing mitigates the impact of poor wireless links by exploiting the broadcast nature of wireless transmissions and the path diversity.
We investigate the problem of opportunistically routing packets in a wireless multi-hop network when zero or erroneous knowledge of transmission success probabilities and network topology is available. Using a reinforcement learning framework, we propose an adaptive opportunistic routing algorithm which minimizes the expected average per packet cost for routing a packet from a source node to a destination.
Our proposed reinforcement learning framework allows for a low complexity, low overhead, distributed asynchronous implementation. The most significant characteristics of the proposed solution are:
It is oblivious to the initial knowledge of network.
It is distributed; each node makes decisions based on its belief using the information obtained from its neighbors.
It is asynchronous; at any time any subset of nodes can update their corresponding beliefs.
- Initialization Stage
- Transmission Stage
- Acknowledgement Message Passing
- Relay Stage