User:CheChe/Sandbox

An illustration of a multiaccess channel with 5 users. When only one user transmits a signal (is active) the message gets through. When there is more than one active user, only noise is received at the other end.

A multiaccess channel is a communication channel that connects many users at once. Every user can listen and transmit on the channel, but if more than one user transmits at the same time, the signals collide, and are reduced to unintelligible noise. Multiaccess channels have been used in distributed communication systems since the 1980s, including more recently, wireless computer networks and phone networks.

The problem is thus: how can we assign transmission times to the users so that their messages do not collide? A simple method is to give each user their own time slot in which to transmit, requiring $n$ slots. (This is called time division multiplexing, or TDM.) However, this is very inefficient, since we usually assume that only a few users will want to transmit at any given time – otherwise a multiaccess channel is not practical in the first place.

Group testing

In the context of group testing, this problem is usually tackled by dividing time into 'epochs'. We say that an user is active if they have a message at the start of an epoch. (If a message is generated during an epoch, the user only becomes active at the start of the next one.) An epoch ends when every active user has successfully transmitted their message. The problem is now to find all the active users in a given epoch, and schedule a time for them to transmit (if they have not already done so successfully). This is then a group testing problem where the query asks a set of users to attempt a transmission if they are active. The outcomes are $\{0,1,2^{+}\}$, corresponding respectively to the possible results of a query: no active users, exactly one active user (message successful) or more than one active user (message collision).

Combinatorial testing

Most of the literature on this problem focuses on the probabilistic model, but we will start by outlining a simple combinatorial algorithm, $C$. The most basic form of this algorithm, for when $n=2^{k}$ for some $k$, is to perform a repeated binary splitting (starting with the whole set of users), stopping whenever a test returns either $0$ or $1$. As shown in , the number of tests this requires (as a function of $d$) can be computed, giving the following theorem.

Theorem

When $d$ is unknown, $C$ requires $T$ tests where $T=2\left\lfloor {\frac {d}{2}}\right\rfloor k-2\left\lfloor {\frac {d}{2}}\right\rfloor (D-1)+2^{D}-1$ and $D=\lceil \log _{2}d\rceil$.

When $d$ is known we instead start by testing groups of size $2^{k}/2^{l}$ where $l$ is approximately $1+\log _{2}(d/\ln 2)$. For this modified algorithm, $C^{\prime }$, derived the following.

Theorem

$C^{\prime }$ requires $T^{\prime }$ tests where $T$ is as in the previous theorem and $T^{\prime }\approx T-d(2-\log _{2}\ln 2-1/\ln 2)+1$.

Further improvements can be made to this algorithm. As detailed in , we can extend the method to deal with $n$ (or group sizes) not a power of two, and we can save some tests using the extra information from a $2^{+}$ result. also goes into detail on non-adaptive solutions in the combinatorial model.\newline

Probabilistic testing

On the probabilistic side of things, Pippenger produced a bound on the effectiveness of group-testing algorithms for multiaccess channels. Let $\nu$ be the expected number of active users in a epoch, and $\sigma$ be the expected number of queries needs to transmit their messages. Pippenger showed that $\sigma \geq \nu /\xi$ where $\xi =0.7444\dots$.

For explicit details on probabilistic algorithms, the reader is encouraged to consult \cite{berger}, which defines an algorithm that performs close to optimally across most prevalence rates, $\nu$.

External links

See for a general overview. (ref 1)