Two WiFi access points on the same channel with overlapping coverage contend for airtime, and both lose throughput. If I know where the APs are and how far each one reaches, picking channels so that no two overlapping APs share one is vertex coloring on an interference graph. The planner builds that graph from a floorplan, colors it, and draws the signal field on the same picture so I can see the coverage and the conflicts together.
The interference graph
One vertex per AP. Two APs get an edge when their distance is less than the sum of their coverage radii. On one floor that's the planar distance. Across floors I add the vertical offset (ceiling heights plus slab thicknesses between them) as a third coordinate. Each edge carries an overlap fraction:
\[\operatorname{overlap}(u, v) = \min\!\left(1,\; \frac{r_u + r_v - d(u,v)}{\min(r_u, r_v)}\right)\]It's 0 when the circles barely touch. The clamp kicks in once \(d\) drops to the larger radius, which is when the smaller AP sits on the edge of the bigger one's circle. Full containment would score 2 without the clamp, so a 1 doesn't mean one circle is inside the other.
Before coloring I compute the attenuated signal between each pair: inverse quartic in the 3D distance, then wall or slab loss as \(10^{-L/10}\) with \(L\) in dB. Pairs below 0.005 lose their edge. Each band (2.4, 5, and 6 GHz) is its own subgraph with its own channel pool, since signals on different bands don't interfere.
Coloring it
Finding the chromatic number is NP-hard, so the default solver is DSatur (Brelaz, 1979). Pick the uncolored vertex whose neighbors already use the most distinct colors, break ties by degree and then by index, and give it the lowest channel none of its neighbors has. It's exact on bipartite graphs and does well on the sparse, near-planar graphs a floorplan produces. When every channel is taken by some neighbor, it falls back to the channel the fewest neighbors use. That count ignores the overlap fractions, which only decide which edges survive pruning and feed the throughput estimate later.
Welsh-Powell and plain greedy are there for comparison. The exact solver is backtracking with MRV branching and forward checking. It picks the vertex with the smallest remaining domain, tries each color, deletes that color from the domains of uncolored neighbors, and backs out if any domain empties. It tries \(k = 1, 2, \ldots\) up to the greedy count and gives up after 5 seconds. There's no arc consistency. Forward checking was enough for the graph sizes a building produces.
.svg){kind=link}
The heatmap
Signal at distance \(d\) from an AP with coverage radius \(r\) is
\[S(d) = \frac{1}{1 + \left(\frac{d}{r}\right)^4}\]The quartic is the indoor path loss exponent \(n = 4\). I get \(r\) from the link budget, \(r = 10^{(P_{\mathrm{tx}} - \mathrm{PL}_0 - P_{\mathrm{rx}}) / (10n)}\), with the 1 m reference loss \(\mathrm{PL}_0\) at 40, 47, and 49 dB for the three bands from ITU-R P.1238 and a receiver sensitivity of -85 dBm.
Walls come from a ray march through the wall mask. I step from the AP to the pixel with DDA and add dB for every step that lands in wall material, at a per-meter rate for each of six materials (drywall is 25 dB/m, concrete 60, metal 120). The heatmap then scales the signal by \(10^{-L_{\mathrm{wall}}/20}\). That should be \(10^{-L/10}\) for a power loss in dB, which is what the interference graph uses, so the heatmap and the optimizer halve the wall loss and draw walls more transparent than the graph thinks they are.
A full ray march per pixel is too slow for dragging an AP around. Instead I precompute a polar attenuation field per AP: 720 angular slices of half a degree each, with cumulative dB stored every 3 world units of radius. Each pixel then costs an atan2 and a table read. The Cartesian grid I replaced needed about 20 million DDA steps per AP. The polar field needs about 360 thousand. During a drag it drops to 360 slices and coarser buckets.
Placing the APs
Given \(k\) APs and a floorplan, where should they go? I sample the interior, weighted by device density when rooms are labeled (a conference room pulls harder than a stairwell).
The first pass is signal-weighted Lloyd's algorithm, seeded with k-means++. Each sample goes to the AP with the strongest signal at that point. The optimizer uses a tighter, steeper falloff than the heatmap here, \(\max(0, (1 - d/1.5r)^2)\) times the wall factor. Each AP moves to the weighted centroid of its samples, with weight \((1 + 3\,\mathrm{deficit}) \times \mathrm{density}\) where deficit is one minus the best signal at that sample. The factor of 3 pulls APs toward dead zones. Centroids snap to the nearest interior pixel, and it stops when no AP moves more than 1 px.
Lloyd's gets stuck in whatever basin the wall geometry puts it in, so a particle swarm of 20 particles then explores around it for 60 iterations. Inertia decays linearly from 0.9 to 0.4, and both the cognitive and social coefficients are 1.5. Positions are clamped to the interior. Last, coordinate descent tries each AP in 8 directions at a step of 5 px, halving down to 0.5 px, and keeps any move that improves coverage.
All three passes read one wall attenuation cache, a Float32Array of dB loss from each source grid cell to each sample point. When an AP moves, only its column is invalidated. The optimizer evaluates tens of thousands of candidate positions against it.
Throughput
For each AP I estimate
\[T_{\mathrm{eff}} = \frac{R_{\mathrm{phy}} \cdot \eta}{1 + \displaystyle\sum_{j \in \mathcal{N}_c(i)} s_{ij}}\]where \(R_{\mathrm{phy}}\) is the PHY rate for the AP's standard, stream count, and channel width, \(\eta = 0.5\) covers MAC overhead, and \(s_{ij}\) is the attenuated signal between AP \(i\) and each AP \(j\) on the same channel. The denominator is the effective number of contending transmitters. Three co-channel APs at full overlap each get a third of the airtime. The \(s_{ij}\) are the same numbers the graph pruning uses.
Wall detection from a floorplan image runs Tesseract.js to mask out text labels, then adaptive thresholding, morphological closing, and a flood fill. There's a database of 101 AP models from 14 vendors with per-band transmit power and MIMO streams, which is where \(P_{\mathrm{tx}}\) comes from. The solver, optimizer, and heatmap each run in a Web Worker so the canvas keeps responding while they work.