ABSTRACT
Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 214
In this chapter, we discuss location identification algorithms for computing the loca-
tion of a node in an ad hoc network. We start with a small percentage of nodes known
as reference nodes which are assumed to know their locations with high precision,
either through GPS or some other means. Starting from these reference nodes, loca-
tions of other nodes are successively computed. A beacon node is a reference node
or a node whose location has been computed with the help of location information
of its neighbors. We assume errors exist in the advertised locations of all beacon
nodes, including the reference nodes. ± denotes the maximum possible error in the advertised coordinates of a beacon node along either axis of a two-dimensional co-
ordinate system. ±δ is the maximum possible error along either axis in a measured range between a node and a beacon. We first present an intelligent beacon selection
algorithm proposed by [11] such that the error in the computed location of a node
is within a bound of ±[3(1 + √2) + 2δ] to ±(3 + 2δ) along one axis and within ±[2δ(1 + √2) + 3] to ±(3 + 2δ) along its orthogonal axis. Authors in [11] also derived a general expression for computing the bounds on an error that can be in-
troduced in the computed location of a node and the conditions that must be met
in selecting the beacon nodes to keep the error in the computed location of a node
within these bounds.
