Graduate Exam Abstract
Pritam Shah
M.S. Final
December 19, 2012, 1pm
Eddy 104
Virtual Coordinate based Techniques for Wireless Sensor Networks: A Simulation Tool and Localization & Planarization Algorithms
Abstract: Wireless sensor Networks (WSNs) are deployments of smart sensor devices for
monitoring environmental or physical phenomena. These sensors have the ability to communicate with other sensors within communication range or with a base station. Each sensor, at a minimum, comprises of sensing, processing, transmission, and power units. This thesis focuses on virtual coordinate based techniques in WSNs. Virtual Coordinates (VCs) characterize each node in a network with the minimum hop distances to a set of anchor nodes, as its coordinates. It provides a compelling alternative to some of the localization applications such as
routing.
Building a WSN testbed is often infeasible and costly. Running real experiments on
WSNs testbeds is time consuming, difficult and sometimes not feasible given the scope and size
of applications. Simulation is, therefore, the most common approach for developing and testing
new protocols and techniques for sensor networks. Though many general and wireless sensor
network specific simulation tools are available, no available tool currently provides an intuitive
interface or a tool for virtual coordinate based simulations. A simulator called VCSIM is
presented which focuses specifically on Virtual Coordinate Space (VCS) in WSNs. With this
simulator, a user can easily create WSNs networks of different sizes, shapes, and distributions.
Its graphical user interface (GUI) facilitates placement of anchors and generation of VCs.
Localization in WSNs is important for several reasons including identification and
correlation of gathered data, node addressing, evaluation of nodes’ density and coverage,
geographic routing, object tracking, and other geographic algorithms. But due to many
constraints, such as limited battery power, processing capabilities, hardware costs, and
measurement errors, localization still remains a hard problem in WSNs. In certain applications,
such as security sensors for intrusion detection, agriculture, land monitoring, and fire alarm
sensors in a building, the sensor nodes are always deployed in an orderly fashion, in contrast to
random deployments. In this thesis, a novel transformation is presented to obtain position of
nodes from VCs in rectangular, hexagonal and triangular grid topologies. It is shown that with
certain specific anchor placements, a location of a node can be accurately approximated, if the
length of a shortest path in given topology between a node and anchors is equal to length of a
shortest path in full topology (i.e. a topology without any voids) between the same node and
anchors. These positions are obtained without the need of any extra localization hardware. The
results show that more than 90% nodes were able to identify their position in randomly deployed
networks of 80% and 85% node density. These positions can then be used for deterministic
routing which seems to have better avg. path length compared to geographic routing scheme
called “Greedy Perimeter Stateless Routing (GPSR)”.
In many real world applications, manual deployment is not possible in exact regular
rectangular, triangular or hexagonal grids. Due to placement constraint, nodes are often placed
with some deviation from ideal grid positions. Because of placement tolerance and due to non-isotropic radio patterns nodes may communicate with more or less number of neighbors than
needed and may form cross-links causing non-planar topologies. Extracting planar graph from
network topologies is known as network planarization. Network planarization has been an
important technique in numerous sensor network protocols—such as GPSR for efficient routing,
topology discovery, localization and data-centric storage. Most of the present planarization
algorithms are based on location information. In this thesis, a novel network planarization
algorithm is presented for rectangular, hexagonal and triangular topologies which do not use
location information. The results presented in this thesis show that with placement errors of up to
30%, 45%, and 30% in rectangular, triangular and hexagonal topologies respectively we can
obtain good planar topologies without the need of location information. It is also shown that with
obtained planar topology more nodes acquire unique VCs.
Adviser: Anura Jayasumana
Co-Adviser: N/A
Non-ECE Member: Yashwant Malaiya
Member 3: Sudeep Pasricha
Addional Members: N/A
Publications:
N/A
Program of Study:
CS457
CS556
ECE513
ECE561
ECE658
GRAD510
ECE699
N/A
