{"id":{"repo_id":"mit","oai_identifier":"oai:dspace.mit.edu:1721.1/37907"},"canonical_url":"https://search.dev.ndltd.org/etd/mit/oai:dspace.mit.edu:1721.1/37907","repository":{"repo_id":"mit","name":"MIT","base_url":"https://dspace.mit.edu/oai/request"},"display":{"title":"New techniques for geographic routing","abstract":"As wireless sensor networks continue to grow in size, we are faced with the prospect of emerging wireless networks with hundreds or thousands of nodes. Geographic routing algorithms are a promising alternative to tradition ad hoc routing algorithms in this new domain for point-to-point routing, but deployments of such algorithms are currently uncommon because of some practical difficulties. This dissertation explores techniques that address two major issues in the deployment of geographic routing algorithms: (i) the costs associated with distributed planarization and (ii) the unavailability of location information. We present and evaluate two new algorithms for geographic routing: Greedy Distributed Spanning Tree Routing (GDSTR) and Greedy Embedding Spring Coordinates (GSpring). Unlike previous geographic routing algorithms which require the planarization of the network connectivity graph, GDSTR switches to routing on a spanning tree instead of a planar graph when packets end up at dead ends during greedy forwarding. To choose a direction on the tree that is most likely to make progress towards the destination, each GDSTR node maintains a summary of the area covered by the subtree below each of its tree neighbors using convex hulls.","abstract_html":"As wireless sensor networks continue to grow in size, we are faced with the prospect of emerging wireless networks with hundreds or thousands of nodes. Geographic routing algorithms are a promising alternative to tradition ad hoc routing algorithms in this new domain for point-to-point routing, but deployments of such algorithms are currently uncommon because of some practical difficulties. This dissertation explores techniques that address two major issues in the deployment of geographic routing algorithms: (i) the costs associated with distributed planarization and (ii) the unavailability of location information. We present and evaluate two new algorithms for geographic routing: Greedy Distributed Spanning Tree Routing (GDSTR) and Greedy Embedding Spring Coordinates (GSpring). Unlike previous geographic routing algorithms which require the planarization of the network connectivity graph, GDSTR switches to routing on a spanning tree instead of a planar graph when packets end up at dead ends during greedy forwarding. To choose a direction on the tree that is most likely to make progress towards the destination, each GDSTR node maintains a summary of the area covered by the subtree below each of its tree neighbors using convex hulls.","abstract_has_math":false,"creators":["Leong, Ben Wing Lup"],"institution":"Massachusetts Institute of Technology","degree_name":null,"degree_level":null,"degree_discipline":null,"degree_department":"Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science.","school":null,"contributors":[],"advisors":["Barbara Liskov."],"committee_chairs":[],"committee_members":[],"year":2006,"date_issued":"2006","date_published":"2006","updated_at":"2026-07-22T22:22:13Z","subjects":["Electrical Engineering and Computer Science."],"languages":["eng"],"rights":["M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission."],"rights_urls":["http://dspace.mit.edu/handle/1721.1/7582"],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/1721.1/37907","outbound_label":"Handle","outbound_source":"dc:identifier.uri"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor.advisor","label":"Advisor","values":["Barbara Liskov."]},{"key":"dc:contributor.department","label":"Department","values":["Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science."]},{"key":"dc:contributor.other","label":"Dc Contributor Other","values":["Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science."]},{"key":"dc:creator","label":"Author","values":["Leong, Ben Wing Lup"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.accessioned","label":"Dc Date Accessioned","values":["2007-07-18T13:08:00Z"]},{"key":"dc:date.available","label":"Dc Date Available","values":["2007-07-18T13:08:00Z"]},{"key":"dc:date.issued","label":"Date","values":["2006"]},{"key":"dc:publisher","label":"Institution","values":["Massachusetts Institute of Technology"]},{"key":"dc:type","label":"Dc Type","values":["Thesis"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Electrical Engineering and Computer Science."]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language.iso","label":"Language (ISO)","values":["eng"]},{"key":"dc:rights","label":"Dc Rights","values":["M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission."]},{"key":"dc:rights.uri","label":"Rights URI","values":["http://dspace.mit.edu/handle/1721.1/7582"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier.uri","label":"Identifier URI","values":["http://hdl.handle.net/1721.1/37907"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2006.","Includes bibliographical references (p. 141-148)."]},{"key":"dc:description.abstract","label":"Abstract","values":["As wireless sensor networks continue to grow in size, we are faced with the prospect of emerging wireless networks with hundreds or thousands of nodes. Geographic routing algorithms are a promising alternative to tradition ad hoc routing algorithms in this new domain for point-to-point routing, but deployments of such algorithms are currently uncommon because of some practical difficulties. This dissertation explores techniques that address two major issues in the deployment of geographic routing algorithms: (i) the costs associated with distributed planarization and (ii) the unavailability of location information. We present and evaluate two new algorithms for geographic routing: Greedy Distributed Spanning Tree Routing (GDSTR) and Greedy Embedding Spring Coordinates (GSpring). Unlike previous geographic routing algorithms which require the planarization of the network connectivity graph, GDSTR switches to routing on a spanning tree instead of a planar graph when packets end up at dead ends during greedy forwarding. To choose a direction on the tree that is most likely to make progress towards the destination, each GDSTR node maintains a summary of the area covered by the subtree below each of its tree neighbors using convex hulls.","(cont.) This distributed data structure is called a hull tree. GDSTR not only requires an order of magnitude less bandwidth to maintain these hull trees than CLDP, the only distributed planarization algorithm that is known to work with practical radio networks, it often achieves better routing performance than previous planarization-based geographic routing algorithms. GSpring is a new virtual coordinate assignment algorithm that derives good coordinates for geographic routing when location information is not available. Starting from a set of initial coordinates for a set of elected perimeter nodes, GSpring uses a modified spring relaxation algorithm to incrementally adjust virtual coordinates to increase the convexity of voids in the virtual routing topology. This reduces the probability that packets will end up in dead ends during greedy forwarding, and improves the routing performance of existing geographic routing algorithms. The coordinates derived by GSpring yield comparable routing performance to that for actual physical coordinates and significantly better performance than that for NoGeo, the best existing algorithm for deriving virtual coordinates for geographic routing. Furthermore, GSpring is the first known algorithm that is able to derive coordinates that achieve better geographic routing performance than actual physical coordinates for networks with obstacles."]},{"key":"dc:description.degree","label":"Dc Description Degree","values":["Ph.D."]},{"key":"dc:title","label":"Title","values":["New techniques for geographic routing"]}]}],"canonical_facts":{"dc:contributor.advisor":["Barbara Liskov."],"dc:contributor.department":["Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science."],"dc:contributor.other":["Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science."],"dc:creator":["Leong, Ben Wing Lup"],"dc:date.accessioned":["2007-07-18T13:08:00Z"],"dc:date.available":["2007-07-18T13:08:00Z"],"dc:date.issued":["2006"],"dc:description":["Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2006.","Includes bibliographical references (p. 141-148)."],"dc:description.abstract":["As wireless sensor networks continue to grow in size, we are faced with the prospect of emerging wireless networks with hundreds or thousands of nodes. Geographic routing algorithms are a promising alternative to tradition ad hoc routing algorithms in this new domain for point-to-point routing, but deployments of such algorithms are currently uncommon because of some practical difficulties. This dissertation explores techniques that address two major issues in the deployment of geographic routing algorithms: (i) the costs associated with distributed planarization and (ii) the unavailability of location information. We present and evaluate two new algorithms for geographic routing: Greedy Distributed Spanning Tree Routing (GDSTR) and Greedy Embedding Spring Coordinates (GSpring). Unlike previous geographic routing algorithms which require the planarization of the network connectivity graph, GDSTR switches to routing on a spanning tree instead of a planar graph when packets end up at dead ends during greedy forwarding. To choose a direction on the tree that is most likely to make progress towards the destination, each GDSTR node maintains a summary of the area covered by the subtree below each of its tree neighbors using convex hulls.","(cont.) This distributed data structure is called a hull tree. GDSTR not only requires an order of magnitude less bandwidth to maintain these hull trees than CLDP, the only distributed planarization algorithm that is known to work with practical radio networks, it often achieves better routing performance than previous planarization-based geographic routing algorithms. GSpring is a new virtual coordinate assignment algorithm that derives good coordinates for geographic routing when location information is not available. Starting from a set of initial coordinates for a set of elected perimeter nodes, GSpring uses a modified spring relaxation algorithm to incrementally adjust virtual coordinates to increase the convexity of voids in the virtual routing topology. This reduces the probability that packets will end up in dead ends during greedy forwarding, and improves the routing performance of existing geographic routing algorithms. The coordinates derived by GSpring yield comparable routing performance to that for actual physical coordinates and significantly better performance than that for NoGeo, the best existing algorithm for deriving virtual coordinates for geographic routing. Furthermore, GSpring is the first known algorithm that is able to derive coordinates that achieve better geographic routing performance than actual physical coordinates for networks with obstacles."],"dc:description.degree":["Ph.D."],"dc:identifier.uri":["http://hdl.handle.net/1721.1/37907"],"dc:language.iso":["eng"],"dc:publisher":["Massachusetts Institute of Technology"],"dc:rights":["M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission."],"dc:rights.uri":["http://dspace.mit.edu/handle/1721.1/7582"],"dc:subject":["Electrical Engineering and Computer Science."],"dc:title":["New techniques for geographic routing"],"dc:type":["Thesis"]},"updated_at":"2026-07-22T22:22:13Z"}