Walter Scott, Jr. College of Engineering

Graduate Exam Abstract

gunjan mahindre
M.S. Final
Aug 28, 2014, 11:00 AM
Dean's Conference Room (B214 Engineering)
Coordinate Repair and Medial Axis Detection in Virtual Coordinate Based Sensor Networks

Wireless Sensor Networks (WSNs) perform several
operations like routing, topology extraction, data
storage and data processing that depend on the
efficiency of the localization scheme deployed in
the network. Thus, WSNs need to be equipped with a
good localization scheme as the addressing scheme
affects the performance of the system as a whole.
There are geographical as well as Virtual
Coordinate Systems (VCS) for WSN localization.
Although Virtual Coordinate (VC) based algorithms
work well after system establishment, they are
hampered by events such as node failure and link
failure which are unpredictable and inevitable in
WSNs where sensor nodes can have only a limited
amount of energy to be used. This degrades the
performance of algorithms and reduces the overall
life of the network. WSNs, today, need a method to
recover from such node failures at its foundation
level and maintain its performance of various
functions despite node failure events. The main
focus of this thesis is preserving performance of
virtual coordinate based algorithms in the
presence of node failures.
WSNs are subject to changes even during their
operation. This implies that topology of the
sensor networks can change dynamically throughout
its life time. Knowing the shape, size and
variations in the network topology helps to repair
the algorithm better. Being centrally located in
the network, medial nodes of a network provide
information such as width of the network at a
particular cross-section and distance of network
nodes from boundary nodes. This information can be
used as a foundation for applications such as
network segmentation, VC system implementation,
routing scheme implementation, topology extraction
and efficient data storage and recovery. We
propose a new approach for medial axis extraction
in sensor networks. This distributed algorithm is
very flexible with respect to the network shape
and size. The main advantage of the algorithm is
that, unlike existing algorithms, it works for
networks with low node degrees.
An algorithm for repairing VCS when
network nodes fail is presented, that eliminates
the need for VC regeneration. This helps maintain
efficient performance for all network sizes. The
system performance degrades at higher node failure
percentages with respect to the network size but
the degradation is not abrupt and the system
maintains a graceful degradation despite sudden
node failure patterns. A hierarchical virtual
coordinate system is proposed and evaluated for
its response to network events like routing and
node failures. We were also able to extract medial
axis for various networks with the presented
medial axis detection scheme. The networks used
for testing fall under a range of shapes and an
average node degree from 3 to 8. We evaluate the scope
and limitations for VCS repair algorithm and
medial axis detection scheme. Performance of the
VC repair algorithm in a WSN is evaluated over
various conditions simulated to represent a
practical node failure events to gauge the system
response through routing percentage and average
hop count over the network. We compare the results
obtained through our medial axis detection scheme
with existing state-of-the-art algorithm. The
results show that this scheme overcomes the
shortcomings of the medial axis detection schemes.
The proposed medial axis detection technique
enables us to extract the information held by a
medial axis of a sensor network. The VC repair
algorithm and the new medial axis extraction
scheme perform very efficiently to make a WSN
tolerant of node failure events.
Adviser: Dr. Anura Jayasumana
Co-Adviser: N/A
Non-ECE Member: Yashwant Malaiya
Member 3: Rockey Luo
Addional Members: N/A
in process
Program of Study:
ECE 421
ECE 501
ECE 516
ECE 531
ECE 658
STAT 511
MATH 532