Question 4 of 5: WiFi and Bluetooth

Question 4: WiFi and Bluetooth (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) — Frequency hopping in a Bluetooth piconet (10 marks)

Frequency-hopping spread spectrum spreads a narrowband signal over a wide band by moving it, rapidly and pseudo-randomly, from one narrow carrier to another. Bluetooth divides the 2.4 GHz ISM band into 79 channels of 1 MHz, from 2402 MHz to 2480 MHz, and hops among them 1600 times per second, so a transmission dwells on any one carrier for a single 625 µs slot before moving on. The instantaneous signal is narrowband and the average spectrum is spread across 79 MHz.

How the medium is shared inside one piconet. A piconet is one master and up to seven active slaves. The master's 48-bit device address and its free-running clock are the two inputs to a deterministic hop-selection kernel that produces the pseudo-random channel sequence; when a slave joins, it receives that address and a clock offset, so every member computes the identical sequence and they hop in lockstep. The hop sequence therefore does not need to be transmitted — it is derived — which is what makes joining cheap and eavesdropping harder.

On top of the hopping, the piconet uses time-division duplex polling. Slots are numbered, the master transmits only in even-numbered slots and a slave only in the odd slot immediately following, and a slave may transmit only if the master addressed it in the preceding slot. There is thus no contention at all inside a piconet: the master's polling schedule is the medium-access protocol, and the hop sequence merely determines where each slot happens in frequency.

A worked example. Suppose the kernel yields the carrier sequence $f_{23},\,f_{7},\,f_{56},\,f_{41},\,f_{12},\,\ldots$ Then:

Each 625 µs slot carries one packet on one carrier; a longer three- or five-slot packet stays on the carrier it started on and the piconet then resumes the sequence at the slot it would have reached, so synchronisation is never lost.

Why hopping is the right choice for this band. The 2.4 GHz ISM band is unlicensed and crowded — WiFi, microwave ovens, cordless telephones and other piconets all occupy it. Three benefits follow directly. Interference is averaged, not suffered: a narrowband interferer wipes out only the slots that happen to land on its channel, roughly one in 79, and those packets are simply retransmitted on the next hop; Bluetooth 1.2 added Adaptive Frequency Hopping, which detects persistently bad channels (typically the 22 MHz occupied by a nearby WiFi network) and removes them from the sequence. Multiple piconets coexist without coordination: two piconets with different masters derive uncorrelated sequences and collide only when they land on the same carrier in the same slot, which part (b) quantifies. Fading is decorrelated: a deep multipath null is frequency-selective, so a packet lost in a null is very likely to succeed on the next hop, 20 or 30 MHz away.

Part (b) — Collision probability between two piconets (5 marks)

Given. Two independent piconets, each hopping over $N = 79$ carriers with an equally likely, uncorrelated choice in each frame.

Find. The probability that both occupy the same carrier in a given frame.

Approach. Condition on the first piconet's choice and count the fraction of the second piconet's equally likely choices that coincide with it.

1. Fix the first piconet's carrier. Whatever carrier piconet A selects — there is no need to say which — there is exactly one carrier out of 79 that piconet B could pick to collide with it.
2. Count B's outcomes. B's hop sequence is derived from a different master address and clock, so its choice is independent and uniform over the same 79 carriers: $P(\text{same carrier}) = \dfrac{1}{N}$.
3. Evaluate. $$P_{\text{collision}} = \frac{1}{79} = \boxed{0.01266 \approx 1.27\ \text{per cent}}$$ — about one frame in 79.

Two qualifications belong with the number. The figure is per frame and the frames are essentially independent, so collisions are rare but recurring: the probability that ten consecutive frames are all clean is $(1 - 1/79)^{10} = 0.880$, i.e. a piconet pair suffers at least one collision in any ten-frame window about 12 per cent of the time. And a collision is not fatal — both packets are usually lost, but Bluetooth's automatic repeat request retransmits on the next hop, which is a different carrier, so the cost is one slot of latency rather than a broken link. If $M$ piconets share the band, the probability that a given piconet's frame is clean is $(1 - 1/79)^{M-1}$, which is why the band tolerates perhaps ten co-located piconets before throughput visibly suffers.

Part (c) — Services of the BSS and the ESS (5 marks)

IEEE 802.11 builds a wireless LAN in two tiers, and the standard assigns a distinct set of services to each.

The Basic Service Set is the fundamental building block: a set of stations coordinated by a single access point (an infrastructure BSS) or by the stations themselves (an independent BSS, or ad-hoc network). It covers one basic service area — a single radio cell — and provides the station services, the ones that must exist wherever a station transmits:

• Authentication and de-authentication — establishing and revoking a station's identity before it is allowed to associate.
• Privacy (confidentiality) — encryption of the frame body, historically WEP, now WPA2/WPA3 with CCMP or GCMP.
• MSDU delivery — carrying a data unit between two stations in the same BSS.
• Medium access coordination — the DCF (and optionally the PCF/HCF) described in part (d), plus the beacon that carries timing, the SSID and the supported rates.
• Power management — the access point buffers frames for dozing stations and advertises them in the traffic indication map.
• Data confidentiality and integrity within the cell, and in an infrastructure BSS the relaying of frames between two associated stations, which never talk directly.

The Extended Service Set is two or more BSSs interconnected by a distribution system — usually a wired Ethernet backbone — and advertised under a single SSID so that the whole collection looks to the logical link layer like one IEEE 802 LAN. Its services are the ones that only make sense across cells:

• Distribution — delivering a frame whose destination is in a different BSS, by handing it to the distribution system for forwarding to the right access point.
• Integration — translating between 802.11 frames and the frame format of a non-802.11 LAN, so the wireless stations appear as ordinary hosts on the wired network.
• Association, re-association and disassociation — registering which access point currently holds a station, updating that registration as the station moves, and clearing it on departure. Re-association is the mechanism of roaming: a station moving between cells keeps its IP address and its transport connections because only its point of attachment changes.

Put briefly: the BSS provides everything needed to move a frame within one radio cell; the ESS provides everything needed to move it between cells and to the wired world, and to let a station move without losing its connections.

Part (d) — Medium access sharing and inter-frame spacing (5 marks)

WiFi's default access method is the Distributed Coordination Function, a form of CSMA/CA — carrier sense multiple access with collision avoidance. Collision detection, as used by wired Ethernet, is impossible on radio, because a station's own transmission is many orders of magnitude stronger at its antenna than any incoming signal, so a station cannot listen while it talks. Avoidance replaces it, and the timing is built entirely out of inter-frame spaces: fixed idle intervals a station must observe before it may transmit.

The procedure for a station with a frame to send is:

1. Sense the medium. Physical carrier sense plus the network allocation vector — a virtual carrier-sense timer loaded from the duration field of any overheard frame — determine whether the channel is busy.
2. Wait a DIFS. If the medium has been idle for a full DIFS (DCF inter-frame space), the station may proceed; in 802.11b, $\text{DIFS} = \text{SIFS} + 2 \times \text{slot} = 10 + 2(20) = 50\ \mu\text{s}$.
3. Back off randomly. If the medium was busy, the station draws a backoff counter uniformly from $[0, CW]$ with $CW = 31$ initially, and decrements it one slot time per idle slot, freezing whenever the medium goes busy. The mean backoff is $\tfrac{31}{2}\times 20\ \mu\text{s} = 310\ \mu\text{s}$, so the mean total wait is about $360\ \mu\text{s}$. Randomising the wait is what prevents every deferred station from transmitting simultaneously the instant the channel clears.
4. Transmit, then wait for the acknowledgment. The receiver checks the FCS and returns an ACK after only a SIFS ($10\ \mu\text{s}$). Because SIFS is shorter than DIFS, the acknowledgment always seizes the medium before any new contender can start, which is the whole design principle of the IFS hierarchy: a shorter inter-frame space confers higher priority.
5. On failure, double the window. No ACK means a collision (or a corrupted frame); the station doubles $CW$ — 31, 63, 127, up to 1023 — and retries, which is binary exponential backoff.

The full ordering is $\text{SIFS} < \text{PIFS} < \text{DIFS} < \text{EIFS}$: SIFS for ACKs, CTS frames and the continuation of a fragment burst; PIFS ($\text{SIFS} + 1$ slot $= 30\ \mu\text{s}$) for the access point to start a contention-free period under the point coordination function; DIFS for ordinary contention-based data; and EIFS, the longest, imposed after receiving a frame with a bad checksum so that a station which could not read a duration field does not disturb an exchange it cannot hear. Optionally, the RTS/CTS handshake — each separated by a SIFS — reserves the medium before a long frame and is the standard mitigation for the hidden-terminal problem, in which two stations that cannot hear one another can both hear, and both collide at, the access point. The later 802.11e enhanced distributed channel access generalises the same idea by giving each traffic class its own arbitration inter-frame space, so voice waits less than best-effort data.