22-Elec-B4 Information Technology Networks · May 2018

Question 4 of 5: WiFi and Bluetooth — Piconets, Frequency Hopping and Medium Access

Nivaar worked solution (AI-drafted; not reviewed by a licensed engineer)

Question 4: WiFi and Bluetooth — Piconets, Frequency Hopping and Medium Access (25 marks)

Question text not reproduced: the examination questions are © Engineers and Geoscientists BC. Open the official past paper (linked at the top of this page) to read the question, then follow the worked solution below.

Part (a) — Structure of a Bluetooth piconet (5 marks)

A piconet is the elementary Bluetooth network and its topology is a star. Exactly one device is the master; every other device in the piconet is a slave, and all traffic passes through the master — two slaves never talk to each other directly. The master's role is not a matter of capability but of timing: it owns the piconet's clock and its device address, and those two quantities together generate the frequency-hopping sequence and the slot boundaries that every member follows. Mastership is assigned when the piconet forms (the device that initiates the connection normally becomes master) and can be exchanged by a role-switch procedure.

At most seven slaves may be active at one time. The limit is architectural rather than arbitrary: an active slave is identified in the packet header by a three-bit active member address (AM_ADDR), of which the all-zeros value is reserved for broadcast, leaving $2^3-1 = 7$ usable addresses. Active slaves are polled by the master and may transmit only in the slot immediately following a packet addressed to them.

Additional devices may remain associated with the piconet in the parked state. A parked device gives up its active member address — which is what frees the slot for another slave — but stays synchronised to the master's clock and hopping sequence, waking periodically at beacon instants to listen for an unpark message. It is identified instead by an eight-bit parked member address (PM_ADDR), so up to 255 devices may be parked. Because re-activation only requires the exchange of an unpark message rather than a fresh inquiry and paging procedure, the parked state gives a piconet an effective membership of 263 devices with a switching latency of milliseconds. (Two further low-power states, hold and sniff, retain the active address but reduce the duty cycle; they are not counted against either limit.) Finally, a device may belong to more than one piconet, bridging them into a scatternet, in which case it time-shares between the two hopping sequences and may be master of one piconet and slave of another — but it can be master of only one.

Part (b) — Frequency-hopping spread spectrum in a piconet (5 marks)

Bluetooth divides the 2.4 GHz ISM band into 79 carriers of 1 MHz each and, instead of occupying one of them permanently, moves the whole piconet from carrier to carrier 1600 times per second. Each dwell is one time slot of 625 µs. The transmitted signal therefore occupies only 1 MHz at any instant but is spread over the full 79 MHz when averaged over time, which is the defining property of frequency-hopping spread spectrum.

The hop sequence is not random but pseudo-random and, crucially, is shared. It is computed by a fixed algorithm whose inputs are the master's 48-bit device address (specifically the lower address part, which selects the sequence) and the master's native clock (which selects the position within it). Every slave learns both quantities during paging and runs the identical computation, so all members of a piconet know which carrier will be used in each slot without any further signalling. This is what makes the hopping a medium-sharing mechanism rather than merely an interference-avoidance mechanism: the members of one piconet are never on different carriers at the same moment, while two piconets, having different masters, follow statistically independent sequences and so occupy the same carrier only occasionally — the probability computed in part (c).

Within the piconet the medium is shared in time rather than in frequency, by time-division duplex slaved to the hopping. The master transmits only in even-numbered slots and a slave only in the odd slot immediately following a packet addressed to it, so the master polls and the slaves answer; there is no contention and hence no collision inside a piconet. A single packet may occupy one, three or five consecutive slots, during which the carrier is held constant and the hop counter continues to advance, so the piconet rejoins its sequence at the correct carrier when the packet ends. Two further benefits follow from hopping and are worth naming: robustness, because a narrowband interferer or a frequency-selective fade damages only the small fraction of slots that land on the affected carrier, and coexistence, since Bluetooth version 1.2 onwards adds adaptive frequency hopping, which detects carriers occupied by Wi-Fi and removes them from the sequence.

Part (c) — Collision probability between two synchronised piconets (5 marks)

Given. Two independent Bluetooth piconets operating simultaneously with their hops synchronised, so that both change carrier at the same slot boundaries. Bluetooth uses $M = 79$ hop carriers of 1 MHz each, and each piconet's sequence is pseudo-random and independent of the other's, so in any given slot each piconet occupies a carrier drawn uniformly from the 79 and the two draws are independent.

Find. The probability that the two piconets occupy the same carrier — that is, that a collision occurs — in a given slot.

Approach. Condition on the carrier chosen by the first piconet; a collision occurs precisely when the second piconet independently chooses that same carrier out of 79 equally likely ones.

1. Model one slot. Let $f_1$ and $f_2$ be the carriers used by piconets 1 and 2 in the slot. Both are uniform on $\{1,\ldots,M\}$ with $M=79$ and are independent, so every ordered pair is equally likely: $$\Pr[f_1 = a,\ f_2 = b] = \frac{1}{M}\cdot\frac{1}{M} = \frac{1}{79^2} = \frac{1}{6241}$$
2. Count the colliding outcomes. A collision means $f_1 = f_2$, and there are exactly $M = 79$ such pairs out of the $M^2 = 6241$ equally likely ones. Equivalently, condition on $f_1$: whatever carrier the first piconet lands on, the second lands on it with probability $1/79$. Both routes give $$\Pr[\text{collision}] = \frac{M}{M^{2}} = \frac{1}{M} = \frac{1}{79}$$ $$\boxed{\,\Pr[\text{collision in a given slot}] = \tfrac{1}{79} = 0.01266 \approx 1.27\,\%\,}$$
3. Interpret the number. At 1600 hops per second the two piconets share a carrier about $1600/79 \approx 20.3$ times each second. Because Bluetooth packets are short and are protected by CRC and ARQ, a collided slot costs one retransmission rather than a lost connection, which is why the two piconets coexist comfortably. The interference is only partial in any case: a collision requires the two piconets to be within radio range of one another as well as on the same carrier.

A useful extension, since examiners frequently ask it as a follow-up, is the case of $k$ simultaneous piconets. The probability that all $k$ choose distinct carriers is $M(M-1)\cdots(M-k+1)/M^{k}$, so the probability that at least two collide in a slot is $1-\prod_{i=1}^{k-1}(1-i/M)\approx k(k-1)/(2M)$ for small $k$. With ten piconets that is about 55 %, which is why adaptive frequency hopping and short packets matter in dense environments.

Part (d) — Services of the Basic and Extended Service Sets (5 marks)

The IEEE 802.11 architecture is built from service sets, and the two named in the question sit at different scales.

A Basic Service Set is the elementary building block: a group of stations that are mutually reachable over one radio medium and coordinated as a single unit. In the usual infrastructure configuration one station is an access point and every other station associates with it; all traffic within the BSS passes through the access point, whose coverage area defines the basic service area. The services provided at this level are those needed to make one radio cell behave like a shared LAN segment: association, by which a station registers with a particular access point and becomes reachable through it; authentication and de-authentication, which establish whether a station may join at all; disassociation; privacy, the encryption of frames over the air; and MSDU delivery together with the distributed coordination of medium access described in part (e). An independent BSS, with no access point, is the ad-hoc case in which stations communicate directly and only the basic delivery and access services are available.

An Extended Service Set is two or more basic service sets whose access points are joined by a distribution system — in practice a wired Ethernet backbone, though the standard does not require it. The extended service set exists to make that collection look like a single logical network to everything above the link layer: all its access points advertise a common SSID, and stations in different basic service sets can address one another as though they were on one LAN. The services added at this level are the ones a single cell cannot provide: distribution, the forwarding of a frame from the access point that received it to the one serving the destination; integration, the translation of frames passing through a portal to and from a non-802.11 LAN; and above all mobility, through the re-association service that transfers a station's association from one access point to another as it moves — a BSS-transition handover — so that a session survives the crossing of a cell boundary.

The distinction in one line is therefore that the BSS provides access to the medium within one cell, while the ESS provides continuity across cells: a single logical LAN with roaming and with a bridge to the wired world.

Part (e) — Medium access sharing in WiFi and inter-frame spacing (5 marks)

Wi-Fi shares the medium with carrier-sense multiple access with collision avoidance, CSMA/CA, implemented as the distributed coordination function. Collision detection, which Ethernet relies on, is impossible on a radio: a station cannot hear the medium while its own transmitter is running, and the transmitted signal at its own antenna would swamp any colliding one in any case. The protocol therefore tries to avoid collisions instead, and every element of it — the random backoff, the positive acknowledgement, the graded inter-frame spaces — exists to compensate for that missing feedback.

A station with a frame to send first senses the medium, both physically (energy and preamble detection) and virtually, through the network allocation vector, a timer loaded from the duration field of any overheard frame. If the medium has been idle for at least a DIFS it may transmit; if the medium is busy, or has only just become free, it defers and then draws a random backoff counter uniformly from the contention window $[0, CW-1]$. The counter decrements once per idle slot and freezes whenever the medium becomes busy, so a station that has already waited keeps its accumulated credit. When the counter reaches zero the station transmits. Because the receiver cannot signal failure, success is confirmed by a positive acknowledgement; if none arrives, the sender doubles its contention window — binary exponential backoff, from $CW_{\min}=15$ up to $CW_{\max}=1023$ — and retries. For hidden terminals an optional RTS/CTS exchange reserves the medium first, since the CTS is heard by stations near the receiver that cannot hear the sender.

The inter-frame spaces are how the protocol assigns priority without any central arbiter: a station that is required to wait a shorter idle interval always seizes the medium before one required to wait longer, because the longer waiter will still be counting when the medium becomes busy again. In increasing order they are:

• SIFS (short inter-frame space, 10 µs in 802.11b DSSS) — the shortest, used for the responses that must not be interrupted: the ACK, the CTS answering an RTS, the next fragment of a fragment burst, and a polled station's reply. Nothing else may start within a SIFS, so a frame exchange runs to completion atomically.
• PIFS (point coordination inter-frame space, SIFS + one slot) — used by the access point to start a contention-free period under the point coordination function, so that centrally scheduled traffic outranks ordinary contention but not an outstanding acknowledgement.
• DIFS (distributed inter-frame space, SIFS + two slots = 50 µs in the same system) — the interval an ordinary station must observe before contending for the medium under the DCF.
• EIFS (extended inter-frame space) — a much longer interval used after receiving a frame whose frame check sequence failed, on the reasoning that the station may have missed a duration field and must not disturb an exchange it cannot see.

The scheme in 802.11e generalises this into four access categories with different values of the arbitration inter-frame space and of $CW_{\min}$, which is how Wi-Fi Multimedia gives voice and video statistical priority over best-effort traffic. The underlying principle is unchanged: on a shared radio with no collision detection, priority is expressed as a difference in patience.