Skip navigation

Scalable and efficient graph colouring in 3 dimensions using emergence engineering principles

Scalable and efficient graph colouring in 3 dimensions using emergence engineering principles

Anthony, Richard (2008) Scalable and efficient graph colouring in 3 dimensions using emergence engineering principles. In: Proceedings. Second IEEE International Conference on Self-Adaptive and Self-Organizing Systems. SASO 2008. IEEE Computer Society, Los Alamitos, CA, USA, pp. 370-379. ISBN 9780769534046 (doi:10.1109/SASO.2008.34)

Full text not available from this repository.

Abstract

This paper describes ways in which emergence engineering principles can be applied to the development of distributed applications. A distributed solution to the graph-colouring problem is used as a vehicle to illustrate some novel techniques. Each node acts autonomously to colour itself based only on its local view of its neighbourhood, and following a simple set of carefully tuned rules. Randomness breaks symmetry and thus enhances stability. The algorithm has been developed to enable self-configuration in wireless sensor networks, and to reflect real-world configurations the algorithm operates with 3 dimensional topologies (reflecting the propagation of radio waves and the placement of sensors in buildings, bridge structures etc.). The algorithm’s performance is evaluated and results presented. It is shown to be simultaneously highly stable and scalable whilst achieving low convergence times. The use of eavesdropping gives rise to low interaction complexity and high efficiency in terms of the communication
overheads.

Item Type: Conference Proceedings
Title of Proceedings: Proceedings. Second IEEE International Conference on Self-Adaptive and Self-Organizing Systems. SASO 2008
Additional Information: [1] First published: 2008 [2] Published as: Anthony, Richard (2008) Scalable and efficient graph colouring in 3 dimensions using emergence engineering principles. In: Proceedings. Second IEEE International Conference on Self-Adaptive and Self-Organizing Systems. SASO 2008. IEEE Computer Society, Los Alamitos, CA, USA, pp. 370-379. [3] This paper was first presented at the Second IEEE International Conference on Self-Adaptive and Self-Organizing Systems (SASO 2008), held from 20-24 October 2008 in Venice, Italy. [4] INSPEC Accession Number: 10392273.
Uncontrolled Keywords: emergence, wireless sensor networks, self-organisation
Subjects: Q Science > QA Mathematics > QA75 Electronic computers. Computer science
Pre-2014 Departments: School of Computing & Mathematical Sciences
Related URLs:
Last Modified: 14 Oct 2016 09:03
Selected for GREAT 2016: None
Selected for GREAT 2017: None
Selected for GREAT 2018: None
URI: http://gala.gre.ac.uk/id/eprint/1263

Actions (login required)

View Item View Item