We consider a network of wireless routers. The routers that are close together can interfere if they transmit simultaneously. So schedules need to avoid such collisions. We want each each wireless node to achieve a transmission rates that equals its arrival rate. One might want to implement a policy like MaxWeight or simply estimate the vector of arrival rates and accordingly choose the correct transmission rate. However, this is complicated by the fact that the routers do not know the arrival and transmission rates of their neighbors; all they can do is sense if their neighbors are transmitting or not.
We outline a clever and surprising result that shows that despite these limitations, there are algorithms that a stabilizing throughput is achievable for the maximum possible set of arrival rates. The model is as follows
- We consider a graph , where indexes a set of nodes and each edge indicates that the nodes and cannot transmit simultaneously. Thus the set of admissible schedules is given by the set
Note the schedules are the independent sets of the graph .
- As we saw with MaxWeight, the maximal region the node sizes can be stabilized for the set of arrival rates in the convex hull of , which we denote by .
Now, parameterized by , we consider a Markov chain model of this system.
- With each node we associate a rate . If is not transmitting all its neightbours are not sending (i.e. and , for all ) then after an exponential distributed time with rate the node will start to transmit.
- If is transmitting, then after an exponentially distributed time of rate 1, the node will stop transmitting.
Notice the Markov chain above does not consider the queueing dynamics of the system, it is just interested in the states of the nodes, whether they are sending or not.
The following is a fairly straight-forward calculation for our Markov chain
Proposition: The stationary distribution, , of the Markov chain just described has the form
for . Hence, the throughput a node under this stationary distribution is
The process is reversible and so above proposition is a straight-forward check of the detailed balance equations.
We now study the following function of and
This intuition behind is as follows. If we want to achieve a rate then, since it belongs to the convex hull of , there exist a probability distribution such that
The function is upto a constant the relative entropy between and (which measures the distance between these two distributions):
Here , the entropy of , is a constant in .
The relative entropy is minimized when is equal to , so as a result we want to choose parameters to solve
The following proposition helps achieve this task:
Proposition: The function has with derivative
Moreover is a strictly concave function of for and is maximize at satisfying
Proof: Notice that
To confirm the strict concavity of we analyse its Hessian. Observe
where is a random variable with distribution . Thus the Hessian of is , where , so concavity is immedidiate from negative semi-definiateness of the Hessian. If it were not negative definate we would have , thus with probability one. Since for each unit vector the event occus with positive probability, so, . In otherwords, for all . But occurs also, so . So these last two observations imply for all and thus, is negative definate.
By differentiability if there is an optimum then it must satisfy the condition , for all . Note that
The above limit shows that the optimum must be achieved finitely, since solutions diverge away from zero. The limit to zero above holds (uniformly) as since for an open ball around , for some , so .
If we want to determine rates so that the output distribution of our network equals the input rate then we we should try optimize . In particular a gradient decent algorithm will achieve this task
The most most important observation is that the parameters and are estimatable from local information at each node . I.e., node does need to know the load or the parameter at other nodes inorder to observe and yet still it can reach a rate .
This gives the main idea of this line of work. However, there are many details required to deal with the recurssion . First, and must be estimated and inparticular should be a good estimate of the stationary distribution of the Markov process with fixed. This involves taking increasingly time steps between interations in whose length are determined by the mixing time of the Markov chain towards . Second, we donât consider queueing dynamics on top of these access rates. We might want to prove stability of the corresponding queueing process. Third, we might be interested in adapting the algorithm towards a different optimal choice of . This is also possible with some tweaking of the the algorithm.