Order Distance Based Localization and Boundary Detection for Wireless Ad Hoc Networks
Date Issued
2012
Date
2012
Author(s)
Chen, Yen-Hsu
Abstract
In wireless ad hoc networks, the multi-dimensional scaling (MDS) based algorithm named
MDS-MAP and hop-size based algorithm named DV-Hop have been proposed for the sensor
localizations. Two major types of distance estimation methods, the range-free and the range-based,
are applied in the localization schemes. In the range-free scheme, the connectivity is the only
information available, and therefore its distance estimation is inaccurate. We propose a novel distance
estimation method to improve the accuracy of distance estimation called order distance. Besides the
range-free distance estimation, our approach incorporates the range-based distance estimation with
the distance inequality property, such as the monotonic RSS-Distance relationship. In our approach, a
node ranks the orders of its neighbors through exchanging neighbor information. The order
information achieves better accuracy of distance estimation than mere connectivity does. The
complexity of a node to obtain all order distances of its neighbors is O(n*log(n)). Moreover, the
analysis shows the order distance estimation converges rapidly with the growth of the node density. In
the simulations, our scheme achieves better accuracy than the original MDS-MAP and DV-Hop. The
results also demonstrate better robustness in our order-based localization scheme than the MDS-MAP
under the noisy environment.
The property of connectivity among the nodes is widely utilized to reason the information
required by the algorithms, so the connectivity of two nodes is an important and fundamental feature
in the wireless sensor networks. The accuracy of connectivity is dominated by the distance estimation
between two nodes under noisy channel. In this dissertation, we propose novel algorithms to improve
the accuracy of the connectivity calculation under noisy channels. By using the feature of Poisson
point process and one-hop information of the nodes, a node constructs the core nodes and calculates
the number of common nodes between neighboring nodes. By using the two metrics, a node obtains
the more accurate connectivity with neighboring nodes. The simulation results demonstrate that the
accuracy of the connection is improved significantly in both low-noise and high-noise channels. In
addition, the results show that the false negative and false positive rates decrease with the growth of
the node density. Besides, the nodes near the boundaries of the networks have poor performance in
many distributed algorithm. Due to the inefficient neighboring nodes and partial information, the
nodes near the boundary have worse performance, such as localization. Hence, the boundary
recognition is an important issue in the ad hoc networks. By the statistical approach in high node
density networks, Fekete’s pioneer work identified the boundary node by number of neighboring
nodes and a specific threshold. By exploiting the number of nodes in the two-hop region, our
proposed algorithm has significant improvement of boundary recognition as opposed to the Fekete’s
algorithm in the low-density network. Given the information topology and the cost function, the analyses provide a framework to obtain the optimal threshold for boundary recognition. Besides, the
simulation results reveal the proposed algorithm has greater than 90% detection rate and lower than
10% false alarm rate.
Subjects
ad hoc networks
localization
order distance estimation
boundary recognition
and decision fusion
Type
thesis
File(s)![Thumbnail Image]()
Loading...
Name
ntu-101-D94921020-1.pdf
Size
23.32 KB
Format
Adobe PDF
Checksum
(MD5):035558386dc56105f7c259bc3e84d5d4