Decentralised learning MACs for collision-free access in WLANs

By combining the features of CSMA and TDMA, fully decentralised WLAN MAC schemes have recently been proposed that converge to collision-free schedules. In this paper we describe a MAC with optimal long-run throughput that is almost decentralised. We then design two schemes that are practically realisable, decentralised approximations of this optimal scheme and operate with different amounts of sensing information. We achieve this by (1) introducing learning algorithms that can substantially speed up convergence to collision free operation; (2) developing a decentralised schedule length adaptation scheme that provides long-run fair (uniform) access to the medium while maintaining collision-free access for arbitrary numbers of stations.

1. In previous sections we presented convergence in terms of the number of schedules used by the algorithm, rather than real time. These will be related by the mean slot length during the convergence phase.

Work supported by SFI Grant 07/SK/I1216a, the European Community’s 7th Framework Programme (FP7-ICT-2009-5) under grant agreement n. 257263 (FLAVIA project) and HEA's Network Maths Grant.

Authors and Affiliations

1. Hamilton Institute, NUI Maynooth, Kildare, Ireland

   Minyu Fang, David Malone, Ken R. Duffy & Douglas J. Leith

Corresponding author

Correspondence to David Malone.

Appendix: Analysis

In this section we give the details of the analysis of L-ZC and L-MAC used earlier in the paper.

1.1 Detailed analysis of L-ZC

We begin with the proof of Theorem 1.

Proof

The number of colliding stations in next schedule only depends on current number of colliding stations and the slots they collide on, hence we build a Markov chain model to study this stochastic process. We have N stations in the same channel without hidden nodes, and \(C \geqslant N\) per schedule to ensure a collision-free schedule exists. We let N _(C) be the number of stations experiencing a collision in a given schedule, n _C be the number of slots with collisions, and then n _I  = C − N + N _(C) − n _C is the number of idle slots. We can immediately establish our result by noting that the probability that N _(C) > 0 decreases is lower bounded by (1 − γ)γ^N-1/C, the probability that one station jumps to an idle slot, but all others remain fixed.

However, we can give a more refined analysis that enables us to determine the optimal learning parameter. For each N _(C) different configurations of collisions are possible, so we label these by a sequence \(S_{(N_{(C)},i)}=(I_{1},I_{2},\ldots,I_{n_C})\) where i indexes the different states and I _j is the number of stations transmitting in slot j. By relabelling the slots, we only need to consider the case where \(I_{j-1}\leqslant I_{j}\) and we omit slots which have no collision (i.e. I _j  < 2). For example, for two colliding stations, the only possible state is S _(2,1) = (2). When N _(C) = 5, there are two possible states S _(5,1) = (5), S _(5,2) = (2, 3). We denote \(\overline{S}_{N_{(C)}} := \{ S_{(N_{(C)},i)} : i\}\) and \(\overline{S} := \bigcup\nolimits_{N_{(C)}=2}^{N}\overline{S}_{N_{(C)}}\). These sets can be identified by combinatorial search.

These sequences, \(S_{(N_{(C)},i)}\), are the states of our Markov chain. We add an initial state IS (N stations start to transmit) and an absorbing state 0 representing collision-free schedules. Note that in this discrete-time Markov chain \(S_{(N_{(C)},i)}\) has non-zero probability to transition to state S _(k,j) if \(k \leqslant N_{(C)}\) and the state IS has positive probability to transfer to all states except itself.

Note that the transition probability from \(S_{(N_{(C)},i)}\) to S _(k,i) is zero if k > N _(C), because N _(C) is non-increasing in the next schedule by design. Assume that \(G_{N_{(C)}}\) is a \(|\overline{S}_{N_{(C)}}|\times |\overline{S}_{N_{(C)}}|\) matrix of transition probabilities among states in \(\overline{S}_{N_{(C)}}\) with the same number of colliding stations. Considering the state IS and the absorbing state, we obtain the \((|\overline{S}|+2)\times (|\overline{S}|+2)\) full transition matrix \(\Uppi\) in upper-triangular block form,

The initial probability measure for all states \(\Upphi_{(0)} := [1,0,\ldots,0]\), at the n’th schedule \(\Upphi_{(n)}=\Uppi^{n}\Upphi_{(0)}\), and stationary measure is \([0,\ldots,0,1]\) due to the absorbing state 0. The convergence speed depends on the second largest eigenvalue \(\lambda^{\ast}\) of the transition matrix: the smaller \(\lambda^{\ast}\), the quicker convergence speed. As \(\Uppi\) is a upper triangular matrix, the determinant of \(\lambda I-\Uppi\) is the product of determinants of its diagonal entries, (4).

It is evident that λ₀ = 0 and \(\lambda_{2+|\overline{S}|}=1\). In order to get the rest eigenvalues λ, we will evaluate the transition matrix \(G_{N_C}\), and obtain the largest eigenvalue of those matrices which is second largest eigenvalue \(\lambda^{\ast}\) of \(\Uppi\).

Let \(\pi_{kl}^{N_{(C)}}\) be the entry of \(G_{N_{(C)}}\) corresponding to the probability of moving from the state \(S_{(N_{(C)},k)}=(K_{1}, \ldots)\) to state \(S_{(N_{(C)},l)}=(L_{1}, \ldots)\). Let n ^k _C and n ^l _C be the number of slots experiencing a collision in these states respectively. Consider colliding stations that choose to remain fixed in the same slot. Since other stations will have seen that slot as busy, no additional stations will be able to move into this slot. This if some of the K _j stations remain fixed, they must correspond to a slot \(j^{\prime}\) with \(L_{j^{\prime}} \leq K_{j}\). Let \(\Upomega \subset \{1, \ldots, n_{C}^{k}\}\) represent slots that will have some fixed station and let

Note that \(M(\Upomega)\) may be empty. Let \(\{j_1, j_2, \ldots\} := \{1, \ldots, n_{C}^{l}\} \backslash \sigma(\Upomega)\) be the indices of collision slots not arising from fixed stations. The number of stations moving to previously idle slots to produce these collision slots will be

and the number of ways we can choose the idle slots will be

So, we may write the transition probability as

where R is the number of permutations of the sequence \(S_{(N_{(C)},l)}\) that result in the same state. For particular \(N_{(C)}\in[2,N]\) and \(\gamma\in(0,1)\), we can obtain the full set of states \(\overline{S}_{N_{(C)}}\), obtain the transition matrix \(G_{N_{(C)}}\) based on equation (6), and then calculate the largest eigenvalue \(\lambda_{(N_{(C)})}^{\ast}\) of \(G_{N_{(C)}}\). Then the second largest eigenvalue will be

Based on this analysis, Fig. 16 (a) and (b) show the largest eigenvalue of matrix at different N _(C) when \(N\leqslant C\). In numerical tests over a range of γ values, we have always observed largest eigenvalue \(\lambda^{\ast}\) is achieved at N _(C) = 2. Under this assumption we obtain

Hence, we expect that the minimum \(\lambda^{\ast}\) is obtained by setting \(\gamma=\frac{1}{C-N+2}\). When N = C,   γ is set at 0.5 for the faster convergence speed for L-ZC.

Largest eigenvalue versus N _(C) for L-ZC, various γ values, numerical results

Full size image

Using this Markov chain, we can also predict the number of schedules until collision-free schedule is obtained, assuming that all stations start to transmit at the same time. Let \(\Uppi_{T}\) be the transition matrix between all transient states. We have already obtained the diagonal, \(G_{N_{(C)}}\) in equation (6) and may obtain most other transitions in a similar way. We do have to calculate the first row of \(\Uppi_T\), representing transition probabilities from IS into other states \(S_{(N_{(C)},i)}\). If N − N _(C) stations choose their own successful N _(C) slots, and n _C slots are chosen from rest C − N + N _(C) slots to obtain the same collision case as \(S_{(N_{(C)},i)}\) and the probability of choosing each slot is initially \(\frac{1}{C}\). Thus we get the transition probability from IS to \(S_{(N_{(C)},i)}\) is

where again, R is number of permutations of \(S_{(N_{(C)},i)}\) that result in the same collision state.

Let \(\kappa_{(S_{(N_{(C)}),i})}\) denote the number of schedules elapsed before the network reaching collision-free schedule given the initial state \(S_{(N_{(C)},i)}\), and κ_(IS) denote the number of schedules elapsed from state IS. Using standard Markov chain results, the mean number of convergence schedules from initial state IS is obtained as

Predictions are shown in Fig. 3. \(\square\)

1.2 Detailed analysis of L-MAC

Now we present the proof of Theorem 2.

Proof

Adapting ideas from a previous proof [9], we will show that from any state in any two steps of the algorithm, there is a probability of convergence that is bounded away from zero. The probability of selecting a slot can become arbitrarily small if the station has been colliding on the same slot for many schedules, so we must construct a sequence of events that avoids this possibility.

Suppose the WLAN consists of N stations. Define \({\bf p}^{(i)}(n)\in[0,1]^{C}\) to be station i’s probability distribution in the n’th schedule and \(s^{(i)}(n)\in\{1,2,\ldots,C\}\) to be its slot chosen for transmission.

If we have \(s^{(i)}(n)\neq s^{(j)}(n),\, \forall i\neq j\in\{1,\ldots,N\}\), then the network has already found a collision-free schedule and there is nothing to prove. If, at schedule n, there was at least one collision, then as C ≥ N, there must be some slot \(i^{\ast}\), which has been selected by none of the stations. At schedule n + 1, for any station k colliding at slot \(i \neq i^{\ast}\) in schedule n, the probabilities of moving to \(i^{\ast}\) is

Thus the probability that all the stations that collided in schedule n then, in schedule n + 1, choose \(i^{\ast}\) is at least ((1 − β)/(C − 1))^N.

In schedule n + 2, the probability a station k that collides in schedule n + 1 now picks any slot j is bounded by below by

Since there is at least one non-colliding configuration, the probability of jumping to this is at least

In summary, no matter what the slot-selection conditions for stations are in schedule n, the probability of schedule n + 2 being collision-free, \(P({\bf p}(n+2)\in A)\), is bounded below by:

Let τ be the first time a collision-free schedule is found, we want to show \(P(\tau<\infty)=1\). At time 2n, the probability of arriving at collision-free schedule for the first time is:

Thus, as \(n \rightarrow \infty\) for any \((1-K)\in(0,1)\), this equation implies:

and so \(P(\tau<\infty)=1\). Note that equation (11) upper bounds the stopping time τ by a geometric distribution and, therefore, all of this stopping time’s moments (mean, variance, etc.) are finite. \(\square\)

Reprints and permissions