| dc.identifier.uri | http://hdl.handle.net/1951/59575 | |
| dc.identifier.uri | http://hdl.handle.net/11401/71152 | |
| dc.description.sponsorship | This work is sponsored by the Stony Brook University Graduate School in compliance with the requirements for completion of degree. | en_US |
| dc.format | Monograph | |
| dc.format.medium | Electronic Resource | en_US |
| dc.language.iso | en_US | |
| dc.publisher | The Graduate School, Stony Brook University: Stony Brook, NY. | |
| dc.type | Dissertation | |
| dcterms.abstract | Scalable point-to-point routing on a wireless sensor
network has been an active research topic for the past ten years. The major challenge comes from the fundamental
resource limitation of sensor nodes, in terms of storage size and communication bandwidth. The solution that requires
a node to acquire the entire network topology does not scale well. In the past few years there have been a number of
innovative proposals on scalable routing schemes where each node only keeps local information and a routing path can
be discovered by iteratively applying greedy routing decisions. Such work has mainly focused on issues such as
guaranteed delivery and low path stretch, and has been relatively successful in that regard. The goal of this
dissertation is to move on with greedy routing techniques and explore more advanced communication primitives. The
first challenge comes from load balancing in sensor networks. In large scale sensor networks it is critical to
balance out work load on different sensors, to prolong network lifetime and prevent immature node failures or network
disconnection. We propose two different techniques to balance out traffic load in the case of uniform network traffic
pattern. Given a sensor network densely deployed on a simply connected domain omega, we apply area-preserving map
to transform omega to a disk D, then use load balanced routing on the virtual coordinates of the sensor nodes on
the disk D. Another technique we propose applies on a 3-connected sensor network deployed on a domain possibly with
holes inside, we use discrete Ricci flow to compute the circle packing of the spherical embedding of the 3-connected
planar subgraph, and apply a heuristic algorithm by Mobius transformation to optimize load balancing across the
sensor nodes. The second issue is exploring the path space in sensor networks. In a sensor network there could exist
multiple disjoint paths between a source and a destination, an efficient method to explore and navigate in the `path
space' can help many important routing objectives, e.g., high network throughput, low latency and fast recovery
on network failures. We present distributed algorithms based on Mobius transformation on circular domains. The
algorithms use local information and limited global information to generate disjoint multi-paths for a given source
destination pair or switch to a different path 'on the fly' when transmission failure is encountered. This
method compares favorably in terms of performance and cost metrics with centralized solutions of using flow
algorithms or random walk based decentralized solutions in generating alternative paths. Thirdly, greedy routing
could suffer from a wormhole attack, in which the adversary places two radio transceivers connected by a high
capacity link and retransmits wireless signals from one antenna to the other. This creates a set of shortcut paths in
the network, and may attract a lot of traffic to the wormhole link. We introduce a wormhole detection and removal
algorithm based on local connectivity tests. The algorithm uses purely local connectivity information, handles
multiple wormhole attacks and generalizes to wireless networks deployed in 3D. It does not suffer from typical
limitations in previous work such as the requirements of special hardware, communication models, synchronization,
node density etc, and guarantees to detect and remove the wormholes. Last but not the least, greedy routing can be
extended to routing on a general graph due to its simplicity and efficiency, especially for navigation in real-world
complex networks. We systematically investigate the conjecture made in earlier small world navigation studies that
many real-world complex networks are navigable. That is, it is possible to discover a hidden metric space purely from
the network connectivity information alone that permits greedy routing on the coordinates in the hidden space to
discover extremely short paths for a majority of node pairs. We confirm the conjecture, delivering packages in a
majority of cases in each of our five empirical networks, from a diverse set of application scenarios. | |
| dcterms.available | 2013-05-22T17:34:08Z | |
| dcterms.available | 2015-04-24T14:46:12Z | |
| dcterms.contributor | Gu, Xianfeng | en_US |
| dcterms.contributor | Gao, Jie , Mitchell, Joseph | en_US |
| dcterms.creator | Ban, Xiaomeng | |
| dcterms.dateAccepted | 2013-05-22T17:34:08Z | |
| dcterms.dateAccepted | 2015-04-24T14:46:12Z | |
| dcterms.dateSubmitted | 2013-05-22T17:34:08Z | |
| dcterms.dateSubmitted | 2015-04-24T14:46:12Z | |
| dcterms.description | Department of Computer Science | en_US |
| dcterms.extent | 195 pg. | en_US |
| dcterms.format | Monograph | |
| dcterms.format | Application/PDF | en_US |
| dcterms.identifier | http://hdl.handle.net/1951/59575 | |
| dcterms.identifier | Ban_grad.sunysb_0771E_11233 | en_US |
| dcterms.identifier | http://hdl.handle.net/11401/71152 | |
| dcterms.issued | 2012-12-01 | |
| dcterms.language | en_US | |
| dcterms.provenance | Made available in DSpace on 2013-05-22T17:34:08Z (GMT). No. of bitstreams: 1
Ban_grad.sunysb_0771E_11233.pdf: 54714727 bytes, checksum: e87fb71a3f735c09e3521d141e255c27 (MD5)
Previous issue date: 1 | en |
| dcterms.provenance | Made available in DSpace on 2015-04-24T14:46:12Z (GMT). No. of bitstreams: 3
Ban_grad.sunysb_0771E_11233.pdf.jpg: 1894 bytes, checksum: a6009c46e6ec8251b348085684cba80d (MD5)
Ban_grad.sunysb_0771E_11233.pdf.txt: 346356 bytes, checksum: 70bac2e4b6ece5a597800eaef2e1c5c0 (MD5)
Ban_grad.sunysb_0771E_11233.pdf: 54714727 bytes, checksum: e87fb71a3f735c09e3521d141e255c27 (MD5)
Previous issue date: 1 | en |
| dcterms.publisher | The Graduate School, Stony Brook University: Stony Brook, NY. | |
| dcterms.subject | dense curve, load balance, multipath, routing, sensor network,
wormhole | |
| dcterms.subject | Computer
science | |
| dcterms.title | Exploring Advanced Communication Primitives Using Greedy
Routing in Sensor Networks and Other Complex Networks | |
| dcterms.type | Dissertation | |
