Graduate Exam Abstract
April 20, 2012, 11:00 am
Anchor Centric Virtual Coordinate Systems in Wireless Sensor Networks: From Self-Organization to Network Awareness
Abstract: Future Wireless Sensor Networks (WSNs) will be collections of thousands to millions of sensor nodes, automated to self-organize, adapt, and collaborate to facilitate distributed monitoring and actuation. They may even be deployed over harsh geographical terrains and 3D structures. Low cost sensor nodes that facilitate such massive scale networks have stringent resource constraints (e.g., in memory and energy), and limited capabilities (e.g., in communication range and computational power). Economic constraints exclude the use of expensive hardware such as Global Positioning System (GPS) for network organization/structuring in many WSN applications. Alternatives that depend on signal strength measurements are highly sensitive to noise and fading, and thus often are not pragmatic for network organization. Robust, scalable, and efficient algorithms for network organization and reliable information exchange that overcome the above limitations without degrading the networks lifespan are vital for facilitating future large-scale WSN networks. <br> This research develops fundamental algorithms and techniques targeting self-organization, data dissemination, and discovery of physical properties such as boundaries of large scale WSNs without the need for costly physical position information. Our approach is based on Anchor Centric Virtual Coordinate Systems, commonly called Virtual Coordinate Systems (VCSs), in which each node is characterized by a coordinate vector of shortest path hop distances to a set of anchor nodes. We develop and evaluate algorithms and techniques for the following tasks associated with use of VCSs in WSNs: (a) Novelty analysis of each anchor coordinate and compressed representation of VCSs, (b) Regaining lost directionality and identifying a good set of anchors, (c) Generating topology preserving maps (TPMs), (d) Efficient and reliable data dissemination, and boundary identification without physical information, and (f) Achieving network awareness at individual nodes. <br> After investigating properties and issues related to VCS, a Directional VCS (DVCS) is proposed based on a novel transformation that restores the lost directionality information in VCS. Extreme Node Search (ENS), a novel and efficient anchor placement scheme, starts with two randomly placed anchors and then uses this directional transformation to identify the number and placement of anchors in a completely distributed manner. Furthermore, a novelty-filtering based approach for identifying a set of good anchors that reduces the overhead and power consumption in routing is discussed. Physical layout information such as physical voids and even relative physical positions of sensor nodes with respect to X-Y directions are absent in a VCS description. Obtaining such information independent of physical information or signal strength measurements has not been possible until now. Two novel techniques to extract a Topology Preserving Maps (TPMs) from VCS, based on Singular Value Decomposition (SVD) and DVCS are presented. A TPM is a distorted version of the layout of the network, but one that preserves the neighborhood information of the network. The generalized SVD based TPM scheme for 3D networks provides TPM even in situations where obtaining accurate physical information is not possible. The ability to restore directionality and topology-based Cartesian coordinates makes VCS competitive, and in many cases a better alternative to geographic coordinates. This is demonstrated using two novel routing schemes in VC domain that outperforms the well-known physical information based routing schemes. The first scheme, DVC Routing (DVCR) uses the directionality recovered by DVCS. Geo-Logical Routing (GLR) is a technique that combines the advantages of geographic and logical routing to achieve higher routability at a lower cost by alternating between topology and virtual coordinate spaces to overcome local minima in the two domains. GLR uses topology domain coordinates derived solely from VCS as a better alternative for physical location information. A boundary detection scheme is also proposed, that is capable of identifying physical boundaries even for 3D surfaces. <br> Network awareness is a nodes cognition of its neighborhood, its position in the network, and the network-wide status of the sensed phenomena. A novel technique is presented whereby a node achieves network awareness by passive listening to routine messages associated with applications in large scale WSNs. With the knowledge of the network topology and phenomena distribution, every node is capable of making solo decisions that are more sensible and intelligent, thereby improving overall network performance, efficiency and lifespan. <br> In essence, this research has laid a firm foundation for use of Anchor Centric Virtual Coordinate Systems in WSN applications, without the need for physical coordinates. Topology coordinates, derived from virtual coordinates, provide a novel, economical, and in many cases, a better alternative to physical coordinates. A novel concept of network awareness at nodes is demonstrated.
Adviser: Dr. Anura Jayasumana
Non-ECE Member: Dr. Inrakshi Ray, Computer Science
Member 3: Dr. Ali Pezeshki, Electrical & Computer Engineering
Addional Members: Dr. Michael Kirby, Mathematics
1. D.C. Dhanapala and A.P. Jayasumana, "Clueless Nodes to Network-Cognizant Smart Nodes: Achieving Network Awareness in Wireless Sensor Networks" Proc. IEEE Consumer Communications and Networking Conference (CCNC),Jan 2012.
2. D.C. Dhanapala, S. Mehta and A.P. Jayasumana, "Boundary Detection of Sensor and Nanonetworks Deployed on 2-D and 3-D Surfaces," Proc. IEEE Globecom - Ad-hoc and Sensor Networking Symposium,2011.
3. D.C. Dhanapala and A.P. Jayasumana, "Anchor Selection and Topology Preserving Maps in WSNs - a Directional Virtual Coordinate Based Approach," Proc. 36th Annual IEEE Conference on Local Computer Networks (LCN), Oct 2011.
4. D.C. Dhanapala and A.P. Jayasumana, "Geo-Logical Routing in Wireless Sensor Networks," Proc. 8th Annual IEEE Communications Society Conference on Sensor, Mesh and Ad Hoc Communications and Networks (SECON), June 2011.
5. D.C. Dhanapala and A.P. Jayasumana, "Directional Virtual Coordinate System for Wireless Sensor Networks," Proc. IEEE International Conference on Communications (ICC), 2011.
6. D.C. Dhanapala and A.P. Jayasumana, "Topology Preserving Maps From Virtual Coordinates for Wireless Sensor Networks," Proc. 35th Annual IEEE Conference on Local Computer Networks (LCN), Oct. 2010 (Best paper 2010).
7. D.C. Dhanapala and A.P. Jayasumana, "Dimension Reduction of Virtual Coordinate Systems in Wireless Sensor Networks," Proc. IEEE Globecom - Ad-hoc and Sensor Networking Symposium, 2010.
8. D.C. Dhanapala and A.P. Jayasumana, "CSR: Convex Subspace Routing Protocol for WSNs," Proc. 34th IEEE Conference on Local Computer Networks (LCN), Oct. 2009.
9. D.C. Dhanapala, Q. Han and A.P. Jayasumana, "Performance of Random Routing on Grid-Based Sensor Networks," Proc. IEEE Consumer Communications and Networking Conference (CCNC) - Personal Ad Hoc and Sensor Networks, Jan. 10 -13, 2009.
10. E.M.N. Ekanayake, D.A.D.C. Dhanapala and M.B Dissanayake, "EGC Diversity Reception of CPSK Signals in Nakagami Fading," Proc. Int. Conference on Industrial and Information Systems (ICIIS 2006) Technical Cosponsor IEEE, Aug. 08 -12, 2006.
11. D.A.D.C. Dhanapala, M.P.B. Ekanayake, S.S. Gunawardane, A.M. Jayathileke and D.M.D. Jayawickrama; "PC based General Purpose Controller Application Board," Annual Technical Conf. IEE young members section Sri Lanka, Aug. 20, 2005.
12. D. Dhanapala and M. Dissanayake, "Symbol Error Probability Analysis of Nakagami-m Distributed Channel Using Rayleigh Distributed Channel," Annual Technical Conf. IEE young members section Sri Lanka, Aug. 20, 2005.
1. D.C. Dhanapala, and A.P. Jayasumana, "Topology Preserving Maps - Extraction of Layout Maps of Wireless Sensor Networks from Virtual Coordinates", IEEE/ACM Transaction on Networking. (In review)
2. D.C. Dhanapala, and A.P. Jayasumana, "Network-Awareness via Self-Learning at Wireless Sensor Nodes", IEEE Transactions on Parallel and Distributed Systems. (In review)
3. D.C. Dhanapala, A.P. Jayasumana and Q. Han, "On Random Routing in Wireless Sensor Grids: A Mathematical Model for Rendezvous Probability and Performance Optimization," Journal of Parallel and Distributed Computing.
4. D.C. Dhanapala, and A.P. Jayasumana, " Convex Subspace Routing (CSR): Routing via Anchor-Based Convex Virtual Subspaces in Sensor Networks ," Computer Communications Journal.
5. E.M.N. Ekanayake, M.B. Dissanayake and D.A.D.C. Dhanapala, "MRC Diversity Reception of M-ary DPSK signals in slow Nakagami fading channel," IEE Electronic Letters, Vol. 42 No. 4, Feb. 16, 2006
6. Dulanjalie C. Dhanapala and Anura P. Jayasumana, "Geo-Logical Routing:Unified Virtual and Topological Space Routing". (To be submitted)
7. Dulanjalie C. Dhanapala and Anura P. Jayasumana, "Directional Virtual Coordinate System for Wireless Sensor Networks - Properties and Applications". (To be submitted)
8. Dulanjalie C. Dhanapala and Anura P. Jayasumana, "Survey on Virtual Addressing and Routing in Wireless Sensor Networks". (To be submitted)
9. Dulanjalie C. Dhanapala, Vidarshana W. Bandara, Ali Pezeshki, Anura P. Jayasumana, "Generalized Bounds for Compressive Sensing Based Recovery". (To be submitted)
Program of Study:
ECE681A1 Algrbraic Coding