| dc.description.abstract | Mobile ad hoc networks consist of potentially moving, computing nodes that
communicate via radio and do not have access to any fixed infrastructure. The knowl-
edge about nearby nodes is a fundamental requirement and is part of many of the
known solutions to problems in mobile and wireless networks including routing, broad-
casting, distributed token circulation, etc. The existing solutions for this problem of
knowing about neighbors are probabilistic.
In this thesis, we give a first step towards a distributed, deterministic algorithm
for finding out about the neighboring nodes. In particular, we focus on the problem
of maintaining information about neighboring nodes in a one dimensional mobile
and wireless ad hoc environment. Under some simplifying assumptions, we give an
algorithm for the problem and a proof of correctness for the algorithm. We deal with
efficiency in terms of both time and space. We prove a tight bound on the speed of
propagation of the message when the nodes are sufficiently dense. We also consider
the case when multiple clusters merge together. Our algorithm is space efficient in
that the nodes do not include information about all the nodes they know in their
broadcast message at all times. Nodes also store only the information about relevant
nodes in their local store and purge information about nodes that have moved out of
range.
Our work shows that it is possible to solve the problem deterministically, and with
reasonable values of the parameters, under some simplifying assumptions. Numerous interesting open questions remain in the area regarding how to relax the assumptions
to make the approach more practical. | en |
