Distributed Navigation

Collins, Andrew ORCID: 0000-0003-0507-6912
(2013) Distributed Navigation. PhD thesis, University of Liverpool.

[img] PDF
Thesis.pdf - Submitted version
Access to this file is embargoed until Unspecified.
Available under License Creative Commons Attribution No Derivatives.

Download (7MB)
[img] PDF
CollinsAnd_July2013_12415.pdf - Author Accepted Manuscript
Available under License Creative Commons Attribution No Derivatives.

Download (7MB)


In this thesis, a number of problems are looked at predominately in the area of mobile agent communication protocols. Particularly, with the recent uptake of unstructured, large and dynamic networks there is a demand for cheap, ubiquitous and reliable protocols that will assist in the support of the network through tasks such as information dissemination, information search and retrieval, and network monitoring. One of the exciting new possible solutions to this is in the area of mobile agents where by a team of dedicated agents (physical or purely virtual) act independently or within a team on the network in the goal of solving simple, yet highly valuable, tasks. Independent agents may work within the bounds of their environment and without influence from their colleagues to solve simple or potentially complex tasks. Further, the agents may also act independently but in actuality work as a very complex team with simple underlying principles allowing for large scale networks and problems to be handled autonomously. In this work, two problems are investigated in detail, the Rendezvous Problem and Network Patrolling. In the rendezvous problem, the goal is to identify algorithms that will permit two agents to rendezvous within some known or unknown environment. This problem, while at first can feel trivial, it can be incredibly difficult when it is realised that all agents are expected to be identical at wake-up time, and that methods must be found that allow for the breaking of symmetry. This thesis provides an investigation into a number of models and environments and tries to provide optimal algorithms for allow rendezvous to occur. Secondly in the area of network patrolling, this work investigates the problem where there exists an environment, in which parts of it are viewed as being vital to network integrity and as such must be monitored. When there are less agents than vital regions the challenge of identifying traversal routes that minimise idle time becomes apparent. In this work an algorithm is presented that minimises this in the ring environment. Finally, this work also looks at other problems in distributed computing and provides exploratory foundation work that could provide alternative models for routing problems, distributed processing, community identification, and presents a number of open problems.

Item Type: Thesis (PhD)
Additional Information: Date: 2013-07 (completed)
Subjects: ?? QA75 ??
Divisions: Faculty of Science and Engineering > School of Electrical Engineering, Electronics and Computer Science
Depositing User: Symplectic Admin
Date Deposited: 05 Feb 2014 16:50
Last Modified: 16 Dec 2022 04:39
DOI: 10.17638/00012415
URI: https://livrepository.liverpool.ac.uk/id/eprint/12415