{"@context":"http://iiif.io/api/presentation/2/context.json","@id":"https://repo.library.stonybrook.edu/cantaloupe/iiif/2/manifest.json","@type":"sc:Manifest","label":"Exploring Advanced Communication Primitives Using Greedy \nRouting in Sensor Networks and Other Complex Networks","metadata":[{"label":"dc.description.sponsorship","value":"This work is sponsored by the Stony Brook University Graduate School in compliance with the requirements for completion of degree."},{"label":"dc.format","value":"Monograph"},{"label":"dc.format.medium","value":"Electronic Resource"},{"label":"dc.identifier.uri","value":"http://hdl.handle.net/11401/71152"},{"label":"dc.language.iso","value":"en_US"},{"label":"dc.publisher","value":"The Graduate School, Stony Brook University: Stony Brook, NY."},{"label":"dcterms.abstract","value":"Scalable point-to-point routing on a wireless sensor \nnetwork has been an active research topic for the past ten years. The major challenge comes from the fundamental \nresource limitation of sensor nodes, in terms of storage size and communication bandwidth. The solution that requires \na node to acquire the entire network topology does not scale well. In the past few years there have been a number of \ninnovative proposals on scalable routing schemes where each node only keeps local information and a routing path can \nbe discovered by iteratively applying greedy routing decisions. Such work has mainly focused on issues such as \nguaranteed delivery and low path stretch, and has been relatively successful in that regard. The goal of this \ndissertation is to move on with greedy routing techniques and explore more advanced communication primitives. The \nfirst challenge comes from load balancing in sensor networks. In large scale sensor networks it is critical to \nbalance out work load on different sensors, to prolong network lifetime and prevent immature node failures or network \ndisconnection. We propose two different techniques to balance out traffic load in the case of uniform network traffic \npattern. Given a sensor network densely deployed on a simply connected domain omega, we apply area-preserving map \nto transform omega to a disk D, then use load balanced routing on the virtual coordinates of the sensor nodes on \nthe disk D. Another technique we propose applies on a 3-connected sensor network deployed on a domain possibly with \nholes inside, we use discrete Ricci flow to compute the circle packing of the spherical embedding of the 3-connected \nplanar subgraph, and apply a heuristic algorithm by Mobius transformation to optimize load balancing across the \nsensor nodes. The second issue is exploring the path space in sensor networks. In a sensor network there could exist \nmultiple disjoint paths between a source and a destination, an efficient method to explore and navigate in the `path \nspace' can help many important routing objectives, e.g., high network throughput, low latency and fast recovery \non network failures. We present distributed algorithms based on Mobius transformation on circular domains. The \nalgorithms use local information and limited global information to generate disjoint multi-paths for a given source \ndestination pair or switch to a different path 'on the fly' when transmission failure is encountered. This \nmethod compares favorably in terms of performance and cost metrics with centralized solutions of using flow \nalgorithms or random walk based decentralized solutions in generating alternative paths. Thirdly, greedy routing \ncould suffer from a wormhole attack, in which the adversary places two radio transceivers connected by a high \ncapacity link and retransmits wireless signals from one antenna to the other. This creates a set of shortcut paths in \nthe network, and may attract a lot of traffic to the wormhole link. We introduce a wormhole detection and removal \nalgorithm based on local connectivity tests. The algorithm uses purely local connectivity information, handles \nmultiple wormhole attacks and generalizes to wireless networks deployed in 3D. It does not suffer from typical \nlimitations in previous work such as the requirements of special hardware, communication models, synchronization, \nnode density etc, and guarantees to detect and remove the wormholes. Last but not the least, greedy routing can be \nextended to routing on a general graph due to its simplicity and efficiency, especially for navigation in real-world \ncomplex networks. We systematically investigate the conjecture made in earlier small world navigation studies that \nmany real-world complex networks are navigable. That is, it is possible to discover a hidden metric space purely from \nthe network connectivity information alone that permits greedy routing on the coordinates in the hidden space to \ndiscover extremely short paths for a majority of node pairs. We confirm the conjecture, delivering packages in a \nmajority of cases in each of our five empirical networks, from a diverse set of application scenarios."},{"label":"dcterms.available","value":"2015-04-24T14:46:12Z"},{"label":"dcterms.contributor","value":"Gu, Xianfeng"},{"label":"dcterms.creator","value":"Ban, Xiaomeng"},{"label":"dcterms.dateAccepted","value":"2013-05-22T17:34:08Z"},{"label":"dcterms.dateSubmitted","value":"2013-05-22T17:34:08Z"},{"label":"dcterms.description","value":"Department of Computer Science"},{"label":"dcterms.extent","value":"195 pg."},{"label":"dcterms.format","value":"Monograph"},{"label":"dcterms.identifier","value":"http://hdl.handle.net/1951/59575"},{"label":"dcterms.issued","value":"2012-12-01"},{"label":"dcterms.language","value":"en_US"},{"label":"dcterms.provenance","value":"Made available in DSpace on 2015-04-24T14:46:12Z (GMT). No. of bitstreams: 3\nBan_grad.sunysb_0771E_11233.pdf.jpg: 1894 bytes, checksum: a6009c46e6ec8251b348085684cba80d (MD5)\nBan_grad.sunysb_0771E_11233.pdf.txt: 346356 bytes, checksum: 70bac2e4b6ece5a597800eaef2e1c5c0 (MD5)\nBan_grad.sunysb_0771E_11233.pdf: 54714727 bytes, checksum: e87fb71a3f735c09e3521d141e255c27 (MD5)\n  Previous issue date:    1"},{"label":"dcterms.publisher","value":"The Graduate School, Stony Brook University: Stony Brook, NY."},{"label":"dcterms.subject","value":"Computer \nscience"},{"label":"dcterms.title","value":"Exploring Advanced Communication Primitives Using Greedy \nRouting in Sensor Networks and Other Complex Networks"},{"label":"dcterms.type","value":"Dissertation"},{"label":"dc.type","value":"Dissertation"}],"description":"This manifest was generated dynamically","viewingDirection":"left-to-right","sequences":[{"@type":"sc:Sequence","canvases":[{"@id":"https://repo.library.stonybrook.edu/cantaloupe/iiif/2/canvas/page-1.json","@type":"sc:Canvas","label":"Page 1","height":1650,"width":1275,"images":[{"@type":"oa:Annotation","motivation":"sc:painting","resource":{"@id":"https://repo.library.stonybrook.edu/cantaloupe/iiif/2/40%2F61%2F28%2F40612880467014407666025594704023553323/full/full/0/default.jpg","@type":"dctypes:Image","format":"image/jpeg","height":1650,"width":1275,"service":{"@context":"http://iiif.io/api/image/2/context.json","@id":"https://repo.library.stonybrook.edu/cantaloupe/iiif/2/40%2F61%2F28%2F40612880467014407666025594704023553323","profile":"http://iiif.io/api/image/2/level2.json"}},"on":"https://repo.library.stonybrook.edu/cantaloupe/iiif/2/canvas/page-1.json"}]}]}]}