Question 4 of 5: WiFi and Bluetooth wireless protocols (25 marks)

Question 4 — WiFi and Bluetooth wireless protocols (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.

Given. Bluetooth as specified by the Bluetooth Core Specification and IEEE 802.15.1, and WiFi as specified by IEEE Std 802.11. The normative constants used below are:

Find. The membership rules of a piconet and the count of each device type; a mechanism-level account of frequency hopping and of how it shares the medium; the services a BSS and an ESS respectively provide; and how inter-frame spacing arbitrates access in WiFi.

Part (a) — Structure of a Bluetooth piconet

Part (a) — the structure. A piconet is the smallest Bluetooth network and is strictly star-shaped: exactly one device is the Master and every other device is a Slave of that master. Slaves never communicate directly with one another; all traffic passes through the master. The role is not a property of the hardware — whichever device initiates the connection becomes master, and the roles can be swapped afterwards — but while the piconet exists the master owns two things that define it: its 48-bit device address BD_ADDR and its free-running native clock, which together generate the hopping sequence and the slot timing that every member follows.

Membership counts follow directly from the width of the address fields, which is the reasoning the marks are for:

So a piconet carries at most $1 + 7 = 8$ simultaneously active devices. A parked device is still a member: it has released its AM_ADDR and cannot exchange data, but it remains synchronised to the master's clock and hopping sequence and wakes periodically to listen on the beacon train, so it can be unparked into an active slot in milliseconds rather than repeating the multi-second inquiry and paging procedure. Two further low-power states exist for completeness — hold and sniff — in which a device keeps its AM_ADDR but reduces its listening duty cycle. A device may also belong to two piconets at once, acting as slave in both or as master in one and slave in the other, which links them into a scatternet; it cannot be master of two, because the master defines the hop sequence.

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

Part (b) — the hopping mechanism. Bluetooth divides the 2.4 GHz ISM band into 79 RF channels of 1 MHz, running from 2402 MHz to 2480 MHz:

$$f_k = 2402 + k\ \text{MHz}, \qquad k = 0, 1, \ldots, 78 \quad\Longrightarrow\quad f_{78} = 2480\ \text{MHz}$$

Rather than staying on one channel, the piconet changes carrier 1600 times per second, so it dwells on each channel for

$$T_{\text{slot}} = \frac{1}{1600\ \text{hops/s}} = 625\ \mu\text{s}$$

The sequence of channels is not random but pseudo-random and shared. A hop-selection kernel in every device takes two inputs: the master's 48-bit BD_ADDR (specifically the lower address part and the upper address part) and the master's native clock. On joining the piconet, each slave receives the master's address and an offset that aligns its own clock to the master's, so every member computes the same channel index for the same slot number. That is the whole trick: no channel has to be negotiated, because all members derive the identical sequence from information they already share.

How this shares the medium within a piconet. Hopping alone does not separate the eight devices from one another — they all sit on the same carrier at the same instant. The sharing is done by time-division duplex layered on top of the hopping, as drawn in Figure 4.2. Slots are numbered by the master's clock; the master transmits only in even-numbered slots and a slave transmits only in the odd slot immediately following a packet addressed to it. A slave that has not been polled stays silent. The medium is therefore shared by polled TDMA, with the master as the scheduler, and one master-plus-slave exchange occupies $2 \times 625 = 1250$ µs. Long packets may span 3 or 5 slots (1.875 ms or 3.125 ms); the carrier is then frozen for the duration of the packet and the sequence resumes at the channel belonging to the slot in which the packet ends, so the piconet never loses synchronisation.

How this shares the medium between piconets, and with other users of the band. Different piconets have different masters, hence different BD_ADDRs and clocks, hence statistically independent hop sequences. Two co-located piconets interfere only when they happen to select the same 1 MHz channel in the same 625 µs slot, which for independent sequences occurs with probability

$$P_{\text{collision}} = \frac{1}{79} = 0.0127 = 1.27\%$$

per slot — and even that costs only one retransmitted packet, because the next slot is on a different channel. This is what lets many piconets share the same room without any coordination, and it is the defining advantage of frequency hopping over a fixed-channel scheme. The same argument applies to interference from outside: a WiFi network occupying 22 MHz of the band can corrupt at most 22 of the 79 hops, so roughly 72 per cent of Bluetooth packets get through unaided, and adaptive frequency hopping (introduced in Bluetooth 1.2) improves on that by measuring channel quality and removing the occupied channels from the sequence altogether. Spreading the transmission across the whole band also delivers the two classic spread-spectrum benefits: robustness to narrow-band interference and to frequency-selective fading, since a deep fade at one carrier affects only one slot.

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

Part (c) — the BSS is the basic building block of an 802.11 network: a set of stations that have successfully associated with one another and are synchronised to a common timing reference. In infrastructure mode a BSS is one access point together with the stations associated to it, identified by a BSSID that is normally the AP's MAC address; in the independent (ad hoc) case, an IBSS is a set of stations with no AP at all. Everything that happens inside a single cell is a BSS service, and IEEE 802.11 names them station services: authentication and deauthentication, which control whether a station may associate at all; privacy, meaning the confidentiality and integrity protection of frames; MSDU delivery, the actual carriage of data between stations; and, since 802.11e, transmit power control and channel selection. One structural consequence is worth stating for the mark: in an infrastructure BSS every frame between two associated stations traverses the AP, so a station-to-station transfer consumes the medium twice.

The ESS is two or more BSSs joined by a distribution system — typically a wired Ethernet backbone — and sharing one SSID, so that the whole collection appears to the logical link control layer above as a single IEEE 802 network. Its services are the ones that only make sense across cells, and 802.11 calls them distribution system services: association, which registers a station with an AP so the DS knows where to deliver its frames; reassociation, which moves that registration to a new AP and is the mechanism of roaming; disassociation; distribution, the delivery of a frame to the right AP; and integration, the translation between 802.11 and a non-802.11 LAN at the portal. The two services that justify building an ESS at all are extended coverage — an area larger than any one radio cell — and transparent mobility, since a station that reassociates keeps its IP address and its open transport connections.

Part (d) — Medium access sharing in WiFi and inter-frame spacing

Part (d) — the access method. WiFi's mandatory access method is the Distributed Coordination Function, which is CSMA with collision avoidance. Collision detection is impossible on a radio link, because a half-duplex transceiver cannot hear a weak distant signal while its own transmitter is on, so 802.11 spends its effort avoiding collisions instead of detecting them. A station with a frame to send senses the medium physically and also consults its NAV; if the medium has been idle for a full DIFS it may transmit immediately, and otherwise it waits for the medium to go idle, waits a DIFS, then counts down a random backoff drawn uniformly from $[0, \text{CW}]$ slots, freezing the counter whenever the medium becomes busy and resuming after the next DIFS. The receiver waits only a SIFS and returns an acknowledgement; the absence of an ACK is what a sender interprets as a collision, whereupon it doubles CW and retries.

The role of inter-frame spacing. The inter-frame spaces are the priority mechanism. Because every station must wait its own IFS after the medium goes idle, and because a station that starts sooner makes the medium busy for everyone else, a shorter IFS is unconditionally higher priority. For the 802.11b DSSS physical layer, with a slot time of 20 µs and a SIFS of 10 µs:

so that

$$\boxed{\text{SIFS} = 10\ \mu\text{s} \;<\; \text{PIFS} = 30\ \mu\text{s} \;<\; \text{DIFS} = 50\ \mu\text{s} \;<\; \text{EIFS}}$$

An in-progress exchange therefore always completes before a new one can start: the ACK is sent after a SIFS, 40 µs before any DCF station is even allowed to look. The backoff draw on top of DIFS is what separates the stations that are at the same priority: with CWmin = 31 slots the mean initial backoff is

$$\overline{T}_{\text{backoff}} = \frac{\text{CWmin}}{2} \times \text{slot} = 15.5 \times 20\ \mu\text{s} = 310\ \mu\text{s}$$

and CW doubles on each failure — 31, 63, 127, 255, 511, 1023 — which is five doublings to CWmax, spreading the retries of a colliding population further apart each time. Finally, because the counter is frozen rather than redrawn when the medium goes busy, a station that has already waited keeps its credit, which gives DCF its approximate long-run fairness.