Graduate Exam Abstract

Yi Jiang

M.S. Final
October 1, 2013, 1:00pm--3:30pm
Mechanical Engineering Conference Room
Virtual and Topological Coordinate Based Routing, Mobility Tracking and Prediction in 2D and 3D Wireless Sensor Networks

Abstract: A Virtual Coordinate System (VCS) for Wireless Sensor Networks (WSNs) characterizes each sensor node’s location using the minimum number of hops to a specific set of sensor nodes called anchors. A VCS does not require geographic localization hardware such as Global Positioning System (GPS), or localization algorithms based on Received Signal Strength Indication (RSSI) measurements. Topological Coordinates (TCs) are derived from Virtual Coordinates (VCs) of networks using Singular Value Decomposition (SVD). Topology Preserving Maps (TPMs) based on TCs contain 2D or 3D network topology and directional information that are lost in VCs. This thesis extends the scope of VC and TC based techniques to 3D sensor networks and networks with mobile nodes. Specifically, we present 3D Extreme Node Search (3D-ENS) for anchor placement. 3D Geo-Logical Routing (3D-GLR), a routing algorithm for 3D sensor networks that alternates between VC and TC domains is evaluated. VC and TC based methods have hitherto been used only in static networks. We develop methods to use VCs in mobile networks, including the generation of coordinates, for mobile sensors without having to regenerate VCs every time the topology changes. 2D and 3D Topological Coordinate based Tracking and Prediction (2D-TCTP and 3D-TCTP) are novel algorithms developed for mobility tracking and prediction in sensor networks without the need for physical distance measurements. Most existing 2D sensor networking algorithms fail or perform poorly in 3D networks. Developing VC and TC based algorithms for 3D sensor networks is crucial to benefit from the scalability, adjustability and flexibility of VCs as well as to overcome the many disadvantages associated with geographic coordinate systems. Existing Extreme Node Search (ENS) for 2D sensor networks plays a key role in providing a good anchor placement, but is not able to generate effective anchors to cover all possible planes in a 3D network. We propose 3D-ENS, that uses two independent pairs of initial anchors and thereby increases the coverage of ENS anchors in 3D networks. Existing Geo-Logical Routing (GLR) algorithm demonstrates very good routing performance by switching between greedy forwarding in virtual and topological domains in 2D sensor networks. Proposed 3D-GLR extends the algorithm to 3D networks by replacing 2D TCs with 3D TCs in TC distance calculation. Simulation results show that the 3D-GLR algorithm with 3D-ENS anchor placement can achieve more than 90% successful delivery rate in 3D networks, thereby significantly outperforming current Geographic Coordinates (GCs) based 3D Greedy Distributed Spanning Tree Routing (3D-GDSTR) algorithm. This demonstrates the effectiveness of 3D-ENS algorithm and 3D-GLR algorithm in 3D sensor networks. Tracking and communicating with mobile sensors has so far required the use of localization or geographic information. This thesis presents a novel approach to achieve tracking and communication without geographic information, thus significantly reducing the hardware cost and energy consumption. Mobility of sensors in WSNs is considered under two scenarios: dynamic deployment and continuous movement. An efficient VC generation scheme, which uses the average of neighboring sensors’ VCs, is proposed for newly deployed sensors to get coordinates without flooding based VC generation. For the second scenario, a prediction and tracking algorithm called 2D-TCTP for continuously moving sensors is developed for 2D sensor networks. Predicted location of a mobile sensor at a future time is calculated based on current sampled velocity and direction in topological domain. The set of sensors inside an ellipse-shaped detection area around the predicted future location is alerted for the arrival of mobile sensor for communication or detection purposes. Using TPMs as a 2D guide map, tracking and prediction performances can be achieved similar to those based on GCs. A simple modification for TPMs generation is proposed, which considers radial information contained in the first principle component from SVD. This modification improves the compression or folding at the edges that has been observed in TPMs, and thus the accuracy of tracking. 3D-TCTP uses a detection area in the shape of a 3D sphere. 3D- TCTP simulation results are similar to 2D-TCTP and show competence comparable to the same algorithms based on GCs although without any 3D geographic information.

Adviser: Dr. Anura Jayasumana
Co-Adviser: N/A
Non-ECE Member: Dr. Indrakshi Ray, CS
Member 3: Dr. Rockey Luo, ECE
Addional Members: N/A

Y. Jiang, D. C. Dhanapala and A. P. Jayasumana, "Tracking and Prediction of Mobility without Physical Distance Measurements in Sensor Networks," In Proceedings of IEEE International Conference on Communications (ICC), Jun. 2013.

Program of Study:
ECE 456
ECE 513
ECE 514
ECE 531
ECE 561
ECE 658
ECE 699