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.