DocumentCode :
3246438
Title :
Scalable and Efficient Graph Colouring in 3 Dimensions Using Emergence Engineering Principles
Author :
Anthony, Richard
Author_Institution :
Dept. of Comput. Sci., Univ. of Greenwich, London
fYear :
2008
fDate :
20-24 Oct. 2008
Firstpage :
370
Lastpage :
379
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-coloring problem is used as a vehicle to illustrate some novel techniques. Each node acts autonomously to color itself based only on its local view of its neighborhood, 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 algorithmpsilas 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.
Keywords :
graph colouring; radiowave propagation; wireless sensor networks; 3 dimensional topologies; communication overheads; efficient graph colouring; emergence engineering principles; radio wave propagation; wireless sensor networks; Application software; Automotive engineering; Computer science; Convergence; Nominations and elections; Robustness; Scalability; Software design; Stability; Wireless sensor networks; Emergence; Wireless sensor networks; self-organisation;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Self-Adaptive and Self-Organizing Systems, 2008. SASO '08. Second IEEE International Conference on
Conference_Location :
Venezia
Print_ISBN :
978-0-7695-3404-6
Type :
conf
DOI :
10.1109/SASO.2008.34
Filename :
4663440
Link To Document :
بازگشت