Abstract
D.Phil.
A modern day N-P complete problem is the assigning of frequencies to transmitters in a
cellular network in such a manner that, ideally, no two transmitters in the same cell or
neighbouring cells use the same frequency. Considering that an average cellular network
provider has over 29 000 transmitters and only 55 frequencies, choosing these
frequencies in an optimal way is a very difficult computational problem. Swarm
intelligence allows the acceptable minimization and optimization of the frequency
assignment problem (FAP).
Swarm intelligence is a concept modelling the processes in natural systems such as ant
colonies, beehives, human immune systems and the human brain. These systems are selforganizational
and display high efficiency in the execution of their tasks. A number of
simple automated agents interacting with each other and the environment form a
collective. Specifically, there is no "central agent" directing the others. A collective can
display surprising intelligence which emerges out of the interaction of the individual
agents. This collective intelligence, referred to as swarm intelligence, is displayed in ant
colonies when ants build elaborate nests, regulate nest temperature and efficiently search
for food in very complex environments. In this thesis a proposal is made to utilize swarm intelligence to build a swarm automatic
frequency planner (swarm AFP). The swarm AFP produces frequency plans that are
better, or on par with existing frequency planning tools, and in a fraction of the time. A
swarm AFP is presented through an in-depth investigation into complex adaptive
systems, agent architectures and emergence. Based on an understanding of these
concepts, a swarm intelligence model called ACEUS is constructed. ACEUS forms the
platform of the swarm AFP. It is a contribution to multi-agent technology as it is a new
multi-agent framework that exhibits swarm intelligence and complex distributed
computation. What differentiates ACEUS from other multi-agent technologies is that
ACEUS works on the basis that the tasks or constructions that have been created by the agents actually guide the agents in their endeavours. There is no centralised agent
controlling or guiding the process. The agents in ACEUS receive information and
stimulation from their tasks or constructions in the environment. As these constructions
or tasks alter the environment, the agents receive stimulus from the changing
environment and then react to the changing environment. The changing environment acts
as an emergent guiding force to the agents. This is the important contribution that
stigmergy contributes to ACEUS. Utilizing this concept, ACEUS is used to create a
swarm AFP. The swarm AFP is benchmarked against the COST 259 Siemens
benchmarks. In all the COST 259 Siemens scenarios the swarm AFP produced the best
results in the shortest time. The swarm AFP was also tested in a real cellular network and
the resulting statistics before and after the swarm AFP implementation are presented.