SALAM: A SCALABLE ANCHOR-FREE LOCALIZATION ALGORITHM FOR WIRELESS SENSOR NETWORKS
SALAM: A SCALABLE ANCHOR-FREE LOCALIZATION ALGORITHM FOR WIRELESS SENSOR NETWORKS
Files
Publication or External Link
Date
2006-04-26
Authors
Youssef, Adel Amin Abdel Azim
Advisor
Agrawala, Ashok K
Citation
DRUM DOI
Abstract
In this dissertation, we present SALAM, a scalable anchor-free protocol for localization
in wireless sensor networks. SALAM can determine the positions of sensor nodes
without any infrastructure support. We assume that each node has the capability to estimate
distances to its corresponding neighbors, that are within its transmission range.
SALAM allows to trade the accuracy of the estimated position against node transmission
range and/or computational power. The application layer can choose from a whole range
of different options, to estimate the sensor node's positions with different accuracy while
conserving battery power.
Scalability is achieved by dividing the network into overlapping multi-hop clusters
each with its own cluster head node. Each cluster head is responsible for building a local
relative map corresponding to its cluster using intra-cluster node's range measurements.
To obtain the global relative topology of the network, the cluster head nodes collaboratively
combine their local maps using simple matrix transformations.
In order for two cluster heads to perform a matrix transformation, there must be at
least three boundary nodes that belongs to both clusters (i.e. the two clusters are overlapping
with degree 3). We formulate the overlapping multi-hop clustering problem and
present a randomized distributed heuristic algorithm for solving the problem. We evaluate
the performance of the proposed algorithm through analytical analysis and simulation.
A major problem with multi-hop relative location estimation is the error accumulated
in the node position as it becomes multi-hop away from the cluster head node. We
analyze different sources of error and develop techniques to avoid these errors. We also
show how the local coordinate system (LCS) affects the accuracy and propose different
heuristics to select the LCS.
Simulation results show that SALAM achieves precise localization of sensors. We
show that our approach is scalable in terms of communication overhead regardless of the
network size. In addition, we capture the impact of different parameters on the accuracy
of the estimated node's positions. The results also show that SALAM is able to achieve
accuracy better than the current ad-hoc localization algorithms.