Graph colouring for office blocks

Allwright, David and Gould, Tim and Gravesen, Jens and Leese, Robert and Petersen, Henrik (2006) Graph colouring for office blocks. European Study Group with Industry > 53rd ESGI [Manchester 21/3/2005 - 24/3/2005].

Full text available as:

PDF - Requires Adobe Acrobat Reader or other PDF viewer.

Abstract/Summary

The increasing prevalence of WLAN (wireless networks) introduces the potential of electronic information leakage from one company's territory in an office block, to others due to the long-ranged nature of such communications. BAE Systems have developed a system ('stealthy wallpaper') which can block a single frequency range from being transmitted through a treated wall or ceiling to the neighbour. The problem posed to the Study Group was to investigate the maximum number of frequencies ensure the building is secure. The Study group found that this upper bound does not exist, so they were asked to find what are "good design-rules" so that an upper limit exists.

Item Type:	Study Group Report
Study Group:	European Study Group with Industry > 53rd ESGI [Manchester 21/3/2005 - 24/3/2005]
Company Name:	BAE SYSTEMS ATC, Filton
Industrial Sector:	None/Other Aerospace and defence Information and communication technology
Additional Contributors:	Rafiey, Arash and Wilson, Eddie and Toft, Bjarne
ID Code:	66
Deposited By:	Gordon White
Deposited On:	19 June 2006

Problem Statement

In most modern office complexes, many different companies can be working in the same building, sharing walls, ceilings, halls and other public spaces with others. The increasing prevalence of WLAN (wireless networks) introduces the potential of electronic information leakage from one company’s territory to others due to the long-ranged nature of such communications. BAE SYSTEMS have developed a system (‘stealthy wallpaper’) which can block a single frequency range from being transmitted through a treated wall or ceiling to a neighbour on the other side of that wall/ceiling. As such, a solution to this problem could be to apply this wallpaper to any boundary shared by two companies and to assign different frequency bands to each of these neighbour. BAE SYSTEMS would like to know the maximum number of frequencies required to ensure that any building is secure, and if this cannot be answered, what a good ‘design-rule’ would be to provide an upper limit. Mathematically, this corresponds to finding the maximum chromatic number of colouring on a 3D lattice which is known to have no simple upper bound. As such, we have come up with an heuristic approach to finding an upper bound, as well as giving a few design rules to minimise this heuristic upper bound.

Archive Staff Only: edit this record