Abstract: Wireless sensor network is a densely deployed
smart sensor nodes which can self-organize, adapt
and collaborate to facilitate distributed
monitoring and actuation over large areas.
However, due to the resources such as, memory, and
energy within the limited capabilities like,
communication range and computational power
algorithm designing for example, for the
information exchange among nodes in these WSNs is
a challenge. In general the size of a WSN may vary
from hundreds of nodes to thousands in number.
Thus, when sensors are deployed, for instance
dropped by an air craft, they are clueless about
the environment. The only information available to
nodes is the number of neighbors and their IDs.
But for 2D and 3D sensor network examples, such as
Target tracking, habitat monitoring, underground
plume tracking, underwater sensor networks,
military applications, surveillance applications
and health care applications benefit from self-
awareness and the network-awareness of the
network. GPS, and RSSI based localization schemes
are available in literature but facilitating nodes
by a GPS is costly and infeasibility for some
applications. WSN limitations such as memory,
energy and cost constraints are some restrictions
against using GPS in WSNs. If a high cost is spent
in the organization phase, network will die-out
before it performs its actual signed service. Thus
investigating energy efficient algorithms and
techniques to structure WSN is essential. Other
than localization based structuring schemes,
clustering algorithms are used for structuring
WSNs. Again high initial cost as well as
exhausting subset of nodes which called cluster
heads shortens the life span of the network.
Another available algorithm is Virtual Coordinate
Systems (VCSs). VCS is a WSN friendly approach of
each node characterizing by a coordinate vector of
size M, consisting of distances to each of a set
of M anchors. This coordinate system is a higher
dimension representation of the actual network.
Hop distance based coordinate generation capture
the connectivity information of the network while
losing the sense of directionality (cardinal or
egocentric directions) of the neighborhood. VCS
based network structuring schemes will be
explored. Network nodes are oblivious. Our aim is
to make nodes aware of its neighborhood and its
position is the network. Thus exact positioning it
not required as far as neighborhood is preserved.
Developing techniques and algorithms to achieve
reliable and efficient information exchange via
self organization of large WSNs in order to
achieve node awareness ultimately is the main goal
of this proposal. Node awareness is that node
knows its neighborhood, position in the network,
its own capabilities, limitations, application it
is serving and the network wide status of the
sensed phenomena. When node awareness is combined
with the node mobility, one can envision the
future WSNs as, catering more than single
application, with dynamically adaptive network
structuring based on node’s local decisions to
provide better service optimizing resource usage.
Advantages of nodes becoming network aware are
enormous. Without having any additional hardware
just learning from the information disseminated in
the network achieving network awareness is not
straight forward. Initially properties of VCS,
novelty analysis of each anchor, dimension
reduction and a transformation to regain the lost
directionality will be investigated. Then topology
preserving map generation without using any
localization scheme will be proposed. Based on the
topology preserving maps a novel method of static
or dynamic boundary detection scheme will be
proposed. Starting from densely deployed
oblivious sensor nodes, achieving network
awareness from the packets that traverse in the
network is also among the contribution of the
proposal.
Completed work can be summarized as below. A
method of evaluating the amount of novel
information contained in an ordinate, i.e., in an
anchor, on the coordinate space created by the
rest of the anchors will be proposed. This method
can be used to identify unnecessary or inefficient
anchors as well as good anchor locations, and thus
help lower overhead and power consumption in
routing. Second, a method for reducing the VCS
dimensionality is presented. This Singular Value
Decomposition (SVD) based method preserves the
routability achieved in original coordinate space
with lower dimensions. Centralized and online
realizations of the proposed algorithm are
explained. Then for the first time a novel method
of obtaining a topology preserving map from
virtual coordinates of a sensor network is
presented. 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, and
obtaining the physical topology has not been
possible up to now. A novel technique, based on
Singular Value Decomposition, is presented to
extract a topology preserving map from VCS. Then
extending the topology preserving map generation
in 2D to 3D, A method of generating topology
preserving maps of networks deployed on 3-D
surfaces, based on the VCS, is presented.
Proposed method is applicable to wireless sensor
networks as well as emerging nano-network
applications where nodes are deployed on 3-D
surfaces. A topology preserving map of a network
of nodes in effect is an identification of the
correct embedding out of all the possible
embeddings in the higher dimensional virtual
domain, which facilitates the identification of
network internal and external boundaries without
the need for physical location information. A
novel boundary identification technique based on
the topology preserving maps is presented and
evaluated for deployment of network nodes over 2-D
and 3D surfaces. Boundary detection scheme
presented is simple, not computationally
intensive, energy efficient and can be used with
physical coordinates as well. After that, a novel
technique that combines the advantages of
geographic and logical routing called Geo-Logical
Routing (GLR), to achieve higher routability at a
lower cost is designed. It uses topology domain
coordinates, derived solely from virtual
coordinates (VCs), as a better alternative for
physical location information. By switching
between geographic routing and logical routing,
GLR overcomes local minima in the respective
domains. Next, a novel concept of achieving
network awareness at individual nodes in large
scale Wireless Sensor Networks (WSNs) is
described. With traditional methods, achieving
such network awareness requires costly
localization integrated with global distribution
of location information. In contrast, the proposed
scheme achieves network awareness by resorting to
passive listening at individual nodes of normal
messages associated with applications. Finally, a
Directional Virtual Coordinate System (DVCS) is
proposed based on a novel transformation that
restores the lost directionality information in a
Virtual Coordinate System (VCS). The virtual
directionality introduced, alleviates the local
minima issue present in original VCS. Properties
of this virtual directional domain are discussed.
With these directional properties, it is possible,
for the first time, to consider deterministic
algorithms in the virtual domain, as illustrated
with a constrained tree network example. A novel
routing scheme called Directional Virtual
Coordinate Routing (DVCR), which illustrates the
effectiveness of the Directional Virtual
Coordinate domain, is proposed.
VCS based topology map generation in different
parts of the network then patching each map
together will provide better maps is under
investigation. Directional Virtual Coordinate
System based topology preserving map generation by
selecting nearly orthogonal virtual directions and
anchor placement strategy will be addressed. Fault
tolerant analysis of the proposed network-
awareness for oblivious nodes will be analyzed.
Adviser: Prof. Anura P. Jayasumana Co-Adviser: N/A Non-ECE Member: Prof. Indrakshi Ray,Department of Computer Science Member 3: Prof. Ali Pezeshki,Department of Electrical & Computer Engineering Addional Members: Prof. Michael Kirby,Department of Mathematics & Department of Computer Science.
Publications: Journal Papers
1. D.C. Dhanapala and A.P. Jayasumana, “Convex Subspace Routing (CSR): Routing via Anchor-Based Convex Virtual Subspaces in Sensor Networks,” Computer Communications. Jan. 2011.
2. 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. Nov. 2010
Conference Proceedings:
1. D.C. Dhanapala and A.P. Jayasumana,” Clueless Sensors to Network-Cognizant Smart Sensors: Topology Awareness Via Self-learning in Wireless Sensor Networks” ACM SIGCOMM 2011, Toronto, Ontario, Canada, Aug. 15-19, 2011 (in review)
2. 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.(in review)
3. D.C. Dhanapala, S. Mehta and A.P. Jayasumana, “On Topology Mapping and Boundary Detection of Sensor and Nanonetworks Deployed on 2-D and 3-D Surfaces,” Proc. 8th Annual IEEE Communications Society Conference on Sensor, Mesh and Ad Hoc Communications and Networks (SECON), June 2011. (in review)
4. D.C. Dhanapala and A.P. Jayasumana, “Directional Virtual Coordinate System for Wireless Sensor Networks,” Proc. IEEE International Conference on Communications (ICC 2011), June 2011. (accepted)
5. D.C. Dhanapala and A.P. Jayasumana, “Dimension Reduction of Virtual Coordinate Systems in Wireless Sensor Networks,” Proc. IEEE global communications conference (GLOBECOM 2010), Dec. 2010.
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 2010), Oct. 2010. (Best paper award)
7. D.C. Dhanapala and A.P. Jayasumana, “CSR: Convex Subspace Routing Protocol for WSNs,” Proc. 34th IEEE Conference on Local Computer Networks (LCN 2009), Oct. 2009.
8. D.C. Dhanapala, A.P. Jayasumana and Q. Han, “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.
9. 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.
10. E.M.N. Ekanayake, D.A.D.C. Dhanapala and M.B Dissanayake, “EGC Diversity Reception of CPSK Signals in Nakagami Fading,” Proc. IEEE Int. Conference on Industrial and Information Systems (ICIIS 2006), 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 Conference organized by 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 Conference organized by IEE young members section Sri Lanka, Aug. 20, 2005.
Program of Study: ECE614 ECE514 MATH532 ECE658 ECE554 ECE520 ECE516 ECE681A1
