Graph colouring using phase coupled oscillators
- Publication Type:
- Thesis
- Issue Date:
- 2011
Closed Access
| Filename | Description | Size | |||
|---|---|---|---|---|---|
 | 01Front.pdf | contents and abstract | 11.06 MB | ||
 | 02Whole.pdf | thesis | 132.17 MB |
Copyright Clearance Process
- Recently Added
- In Progress
- Closed Access
This item is closed access and not available.
NO FULL TEXT AVAILABLE. This thesis contains 3rd party copyright material. ----- An oscillator is a simple unit or object that has a periodic behaviour over time. Phase coupled oscillators are connected oscillators or a network of oscillators where the interactions between the oscillators involve the phase, resulting in the network exhibiting some forms of order or synchronisation between the oscillators.
The computational capabilities of a network of phase coupled oscillators have been widely researched and published in many journals. Some examples of these include the use of the synchronisation of the phase coupled oscillators in developing network protocols for routing, solving time-synchronisation in ad hoc sensor networks, coordinating activities in a massive network of tiny robots (or processors) and colour determination in a ring network. However, these studies employ in-phase synchronisation where all units synchronise into the same phase, thus they do not necessarily represent all aspects of the computational characteristics of a network of phase coupled oscillators.
Another form of oscillator synchronisation is antiphase synchronisation, where oscillators in a network settle into the opposite phase. Antiphase synchronisation can be observed in many highly coordinated and intelligent activities, for example the motor neuron behaviour of lampreys and even in the way humans walk. This form of synchronisation can be used to solve graph colouring problem (Wu, 2002).
The computational aim of graph colouring is to assign a colour to each vertex in a graph such that the vertices sharing the same edge do not have the same colour. Finding the minimum number of colours required to colour a graph is computationally NP-Complete.
Existing studies of the computational capabilities of antiphase synchronisation, particularly when applied to graph colouring are limited to solving 2-colouring problem. This limitation is primarily due to the "hard-wiring" in existing models such as the network of Resistor, Inductor (L) and Capacitor (RLC) circuit (Wu, 2002) and the Hysteresis Neural Networks (HNN) (Nakaguchi, Jin'no & Tanaka, 2001).
The main objective of this thesis is to overcome this limitation. That is, to develop a model capable of performing >2-colouring problems. This thesis also explores the computational aspects of the approach, thus aiming to provide a different view of the computational behaviours of a network of phase coupled oscillators and not necessarily to find the most efficient graph colouring algorithm.
In this thesis, this problem is solved by developing models consisting of differential equations allowing oscillators in the network to synchronise into multiple phases while satisfying the constraints of the graph colouring problem.
Using the graph colouring problem in this study is important, not only because of the natural affinity of networks of phase coupled oscillators to the graph colouring problem but also because the simple, well defined nature and the NP completeness of the graph colouring problem makes it a suitable benchmark (for the highly combinatorial nature). Arguably, only with this kind of hard-prerequisite, can one understand the true characteristics of an algorithm or a model.
The contributions of this thesis are:
1. Simulation of the theoretical antiphase model of Aihara et al. (2006) and application of the model in solving the Ising spin problem in the 2D plane and torus. The limit cycle behaviour of the network was discovered when applying the antiphase model to solve the 2D Ising spin problem.
2. Generalisation of the antiphase model by Aihara et al. into a model capable of synchronising into multiple phases and benchmarking of the multiphase model using k-partite graphs, tessellation on the 2D plane and platonic solids.
3. The finding that a synchronisation of a network of phase coupled oscillators does not necessarily translate to optimality in the target/goal of the optimisation.
4. Development of a k-Phase Oscillator Synchronisation model which enhances the colouring performance of the generalised model.
5. Taxonomy of computational characteristics of a network of phase coupled oscillators when applied to graph colouring problem.
6. Formalisation of a general model of computation for a multiphase oscillator synchronisation.
7. Development of a Discrete k-Phase model for performing distributed graph colouring.
The significance of this study is the direct applicability of the method in solving graph colouring problems in a distributed system or network where global control over each unit in the system is prohibitive. For example, coordination of activities/task allocation in a distributed wireless sensor network (note that task allocation in this example can be mapped to a distributed graph colouring problem).
In general, multiphase synchronisation of a network of oscillators has a potential for modelling many computational phenomena, particularly, the multiphase interactions among neurons in biological neural networks, human social interactions and many other aspects of a network and its applications.
Please use this identifier to cite or link to this item: