GIT-CERCS-05-17
ElMoustapha Ould-Ahmed-Vall, Douglas M. Blough, Bonnie S. Heck, George F. Riley,
Distributed Global Identification for Sensor Networks
A sensor network consists of a set of battery-powered nodes, which collaborate
to perform sensing tasks in a given environment. It may contain one or more
base stations
to collect sensed data and possibly relay it to a central
processing and storage system. These networks are characterized by scarcity of
resources,
in particular the available energy.
We present a distributed algorithm to solve the unique ID assignment problem.
The proposed solution starts by assigning long unique IDs and organizing nodes
in a tree structure.
This tree structure is used to compute the size of the network. Then, unique
IDs are
assigned using the minimum number of bytes.
Globally unique IDs are useful in providing many network functions, e.g.
configuration,
monitoring of individual nodes, and various security mechanisms.
Theoretical and simulation analysis of the proposed solution have been
preformed.
The results demonstrate that a high percentage of nodes (more than
99%) are assigned globally unique IDs at the termination of the algorithm when
the algorithm
parameters
are set properly. Furthermore, the algorithm
terminates in a relatively short time that scales well with the network size.
For example, the algorithm
terminates in about 5 minutes for a network of 1,000 nodes.