Virtual coordinate based techniques for wireless sensor networks: a simulation tool and localization & planarization algorithms
Date
2013
Authors
Shah, Pritam, author
Jayasumana, Anura P., advisor
Pasricha, Sudeep, committee member
Malaiya, Yashwant K., committee member
Journal Title
Journal ISSN
Volume Title
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.