Study Group report 2005: graph colouring (BAE Systems)
This is the final report on graph colouring for office blocks, brought to ESGI53 by BAE Systems. Click on the link at the bottom to download the full report as a pdf document.

Report authors
David Allwright (Smith Institute)
Tim Gould (Lancaster University)
Jens Gravesen (Technical University of Denmark)
Robert Leese (Smith Institute)
Henrik Petersen (University of Southern Denmark)

Introduction

The use of Wireless Local Area Networks (WLANs) is increasing, but raises numerous problems of security. BAE Systems, working for OFCOM has recently demonstrated a technology (unhelpfully dubbed ‘Stealthy Wallpaper’) that could address some of these problems. The technology is an application of adaptive or active Frequency Selective Surfaces (FSS) which for the purposes of this discussion may be considered as thin planar tunable band-pass filters.

Consider for example a large office complex with space rented to numerous independent organisations. WLANs operating on any frequencies could be used with total security provided electromagnetic screening of over 100dB was implemented around each organisation’s territory. This is impractical both on the grounds of expense and inflexibility as organisations grow, shrink, die, or are initiated. Additionally mobile ’phone communication across boundaries would be precluded, which would have safety and other implications.

However, it would not be prohibitively expensive to build or retro-fit moderate screening (say 55–75 dB) between each office, and include small (about 0.3 sq.m.) windows of ‘stealthy wallpaper’ which can be switched by a central ‘controller’ to pass specified frequencies of WLAN channels or to be opaque to all such frequencies. (They could be designed to simultaneously pass mobile ’phone frequencies.)

This degree of screening would not be sufficient to guarantee blocking of WLAN channels between adjacent offices, but it would be enough to guarantee blocking across two boundaries. We are therefore interested in forcing adjacent territories to be on different WLAN channels. (Consider territories as adjacent if and only if they share an area of wall floor or ceiling. Territories ‘meeting’ at a line or point need not be considered adjacent.) This gives rise to the following graph colouring problems.

Mathematical Problem

The set of possible allocations of office space in a multi-storey office complex is an (as-yet) ill-defined subset of the set of all possible arrangements of touching bounded volumes. Atria, stairwells, and lift shafts need to be considered. We would like to know several things:

1. Can the class of adjacency graphs produced by arrangements of office territories be described mathematically?
2. What is the maximum chromatic number of this class of adjacency graphs?
3. If not (1), then can a ‘layman-interpretable’ restriction be placed on the allowable configurations of office territory in order to yield a class of adjacency graphs with known maximum chromatic number (or a reasonably tight upper bound U for the maximum chromatic number). The restriction should be as weak as possible, i.e. ideally only rule out extreme or unlikely allocations. The chromatic number (upper bound) should be as small as possible. There will be a trade-off between the strength of the restriction and the maximum chromatic number, which may be worth investigating.
4. Is there an algorithm to produce a colouring using U colours or fewer for any given adjacency graph in the class? The efficiency of this algorithm is not usually of great concern, but may get problematic when the number of nodes get large. For practical purposes assume the number of nodes to be 100 or fewer. As a guide, the algorithm should sort out the colouring in a day or less on a modern PC.

Use the link below to view the full report.

Download 'BAE-report.pdf' (143 Kb).