These
project suggestions were drawn up quickly as extra options
for masters students, and are presented ‘as is’ without any
editing to harmonise with the others. They may give some
ideas, and less would be expected of undergraduate
projects.
Cellular Automata
Cellular
Automata (CA) were initially introduced by von Neumann in
the 1940’s as a simple model of logical computation; then
popularised within computer science as Conways Game of Life
in the 1970’s mirroring simple population dynamics
including predator-prey relationships, and more recently
(2002) popularised by Wolfram in his popular science work
‘A New Kind of Science’ after his considerable
contributions to theoretical physics over 20 years,
involving CA among other things. Although the basics are
deceptively simple, and consequently their computation is
extremely efficient, they can model surprisingly complex
behaviour, where the processes (or their mathematical
descriptions) are not yet fully characterised, understood,
or tractable. This is especially true of complex dynamical
systems, with widespread applications in every area of
human endeavour, whose proper comprehension and effective
control is increasingly important for reasons of
efficiency. Such applications range from modelling the
dynamics of discrete sparse entities (e.g. population
dynamics, predator prey relationships, socio-political
models, and epidemics) through to continuum dynamics (fluid
dynamics, flood, avalanches).
Cellular Automata are discrete (in state, space and time)
entities with no centralised control, whose individual
responses are governed by simple state dependent transition
rules. However, states and consequent state transitions may
also involve influences from the external environment such
as neighbours, which in a homogenous environment (identical
entities if in a single population setting) can result in
fairly complex group behaviour, such as flocking, which
seemingly emulates central control, but with an appropriate
choice of rules and interaction pathways.
Consequently they are well suited to simulating dynamical
systems consisting of networks of discrete systems with
known interactions through various mechanisms which may be
represented through signalling channels or nodes. This
would seem appealing in modelling computer networks in
general and mobile networks in particular, given that
location is also easily modelled, and a number of projects
readily suggest themselves.
Ad hoc mobile wireless nets provide an interesting and
highly relevant topic for cellular automata based
simulation studies, since the latter provides a simple
platform for evaluation of fully distributed dynamic
routing and management strategies, based solely on simple
nearest neighbour rules and interactions. The aim is to
maximise utility whilst minimising cost overheads. Issues
to consider are routing and broadcast algorithms
constrained by varying delivery windows and fixed bandwidth
whilst avoiding unprofitable traffic, all on a potentially
limited battery life between recharging with a requirement
for inclusion or exclusion in the event of nodes entering
and leaving the system.
These
generally involving simulation using cellular automata (or
any other convenient method) to model & evaluate a
range of topics and applications:-
•
traffic,
protocol & routing issues of ad-hoc (or static) nets
•
mobile
code applications: spread of virus, or utility
(availability, throughput, QoS etc.) of agents or 'mobile
distributed processing' separately or in conjunction with
aspects in the point above
•
load-balancing,
revenue models & power related issues.
Several
variations can support a range of projects whilst catering
for individual flair and preferences !-) Some general
references follow, whilst more specific references are
given below with project suggestions. For those interested,
other references can be given or simple models can be built
with some advice, insight and application from the general
references.
http://portal.acm.org/citation.cfm?id=1050766
http://portal.acm.org/citation.cfm?id=584499
http://portal.acm.org/citation.cfm?id=383763
http://portal.acm.org/citation.cfm?id=501439
Applications
are limited only by the imagination and enthusiasm of
participants; but could be used to simulate:
1. JD1 - protocols, topologies and routing strategies
–
•
model
for optimal data traffic flow (or lack) initially in a
static computer network, allowing for extension to dynamic
ad hoc nets as outlined below;
•
similar
to above, except for vehicular (or pedestrian) traffic flow
(or lack) in transport networks;
•
combine
the above into a mobile ad hoc wireless networks with
dynamic connections between mobile nodes accompanying
vehicles or people. Possibility of route selection based on
recent popularity of route using ‘ant’ algorithms; which
can also be simulated using CA.;
http://www.comp.glam.ac.uk/ASMTA2005/Proc/pdf/h-1026.pdf
http://portal.acm.org/citation.cfm?id=1068034
http://portal.acm.org/citation.cfm?id=1080761
http://portal.acm.org/citation.cfm?id=774758
http://portal.acm.org/citation.cfm?id=1080768
2.
JD2 - distributed control (load
balancing, resource allocation, scheduling, protocols)
algorithms in distributed processing or communications
networks ; e.g. grid computing, ad hoc radio networks, (or
within a multiple functional pipelined CPU unit - even!);
http://portal.acm.org/citation.cfm?id=1071521
3.
JD3 - automated mobile ad hoc wireless networks for traffic
control (fully
distributed control) using ad hoc wireless nets between
people, vehicles or indeed aircraft equipped with suitable
transponders such as current collision avoidance systems –
and compare with current control systems, whether localized
or centralized at vehicle and aircraft level; e.g. imagine
all vehicle control at any well known intersection,
roundabout or airport were governed by ad hoc peer to peer
networks. Possibility of route selection based on recent
popularity of route using ‘ant’ algorithms; which can also
be simulated using CA. Can be extended to war games below.
http://portal.acm.org/citation.cfm?id=1050765
4.
JD4 - mobile code & agent modelling – in
terms of some measure of utility such as useful work or
throughput, availability, QoS etc. vs. cost. Intitially,
these may be ‘charge-free’ but not ‘cost-free’ since all
distribution incurs extra resources such as compute load,
time & energy of peers, extra co-ordination overheads
etc.;
5.
JD5 - virus & intrusion detection – model
as a special case of mobile
code & agent modelling by
looking for patterns in the characteristic spread of
traffic, load and utilities used on net, with the option of
traceback for subsequent analysis & prevention;
http://portal.acm.org/citation.cfm?id=1070176
http://portal.acm.org/citation.cfm?id=986877
6.
JD6 - Commercial P2P Mobile Ad hoc Network (MANET)
-
extend mobile
code & agent modelling to cater
for co-operative commercial credit or charging schemes,
e.g. where an ad hoc P2P scheme is used to compute,
transfer data or provide VoIP in place of traditional
telecoms. What level of use and market penetration would
make it attractive for mobile unit manufacturers to provide
such facilities in their phones rather than get tied into
strict licensing agreements with service providers?
http://portal.acm.org/citation.cfm?id=986546
7.
JD7 - intelligent auction or bidding strategies
-
generate and model these for Commercial
P2P MANET above,
this is verging on game theory, but initally a simple
approach could be adopted such as, retaining a mimium
reserve battery power for anticipated personal or unknown
emergency needs.
8.
JD8 - Multi-player Games on the
net. Model any particular requirements of games/audio/video
applications on the net, such as low-latency, fast
communications & rendering for visualisation etc.
Really only a variation on 1.
protocols, topologies and routing strategies
and
2.
distributed control with
elements of 4.
mobile code & agent modeling for
downloadable games
9.
JD9 - Real (War!?)
Games with MANETS – model
the utility of competing teams using entirely separate and
secret MANETS for optimal effective spatial & temporal
distribution during real competitive games. Really only a
few sets of mutually exclusive automated
mobile ad hoc wireless networks for traffic
control in
conflict or competition.
10.
JD10 - Location management -
investigate the need & utility of a number of
(relatively!?) fixed location nodes relevant to any of the
models above.
For
projects JD1-10, contact Dr. James Doherty,
j.doherty@cs.ucc.ie