Tackling the Contention Resolution Problem
-
This work aims to solve the single access contention resolution problem. The problem consists of computing a symmetric policy that allows a set of nodes to access a shared resource without exchange of information among them.
- Assumptions:
- If two or more nodes attempt to access the resource simultaneously, they lock each other out and none can access the resource during the discrete time slot.
- Each node needs to access the resource only once.
-
We modeled the problem as a partially observable Markov decision process (POMDP).
-
We computed approximate solutions to the POMDP using Alpha-vectors and Deep Q-Learning.
-
We designed a greedy algorithm, GOAL-CR, that exploits the particular structure of the POMDP to compute optimal solutions in polynomial time.
- We show how to adapt the greedy algorithm to scenarios where there is uncertainty in the initial number of nodes, to scenarios where nodes have very limited memory, and to scenarios where nodes join the network asynchronously.
Take away
-
The contention resolution problem is particularly relevant in the context of Wireless Sensor Networks (WSNs). Routing in a WSN is complicated because sensors have energy constraints and they can be randomly deployed. For such scenarios, the network is periodically organized into clusters that enable hierarchical communication. Each time the clusters are reorganized, the network runs a set-up phase in which each sensor contends to send a single packet through a broadcast communication channel.
-
The canonical strategy to solve the problem is to let the nodes attempt to access the resource using a fixed probability of transmission. GOAL-CR substantially outperforms this strategy by making optimal use of the shared communication channel.
-
We formally proved that GOAL-CR computes access policies that minimize the expected contention resolution time.
-
According to experiments, the performance of the greedy policies is close to that of a protocol with complete information about the exact number of nodes that have not yet accessed the resource.
Why it matters?
- Minimizing the contention resolution time of the set-up phase of WSNs not only impacts metrics like channel utilization, throughput, and energy consumption, it also impacts critical metrics such as the response time of the network to catastrophes like wildfires or earthquakes