Files in this item



application/pdf9812572.pdf (9MB)Restricted to U of Illinois
(no description provided)PDF


Title:Spanning Tree Algorithms for Connectivity and Routing in Communication Networks
Author(s):Das, Bevan Narayan
Doctoral Committee Chair(s):Loui, Michael C.
Department / Program:Electrical Engineering
Discipline:Electrical Engineering
Degree Granting Institution:University of Illinois at Urbana-Champaign
Subject(s):Computer Science
Abstract:Finally, we present a family of routing algorithms for ad hoc networks that use a spine infrastructure to coordinate routing and topology updates. The spine is an approximate minimum connected dominating set. The family of routing algorithms includes a basic algorithm, in which each spine node has a local copy of G; a hierarchical algorithm, which scales well with network size; and a partial-information algorithm, which explores the tradeoff of route optimality versus the amount of overhead. We present worst-case analyses and simulation results that show how well the spine routing algorithms maintain shortest-path or near-shortest-path routes with reasonable overhead, even when nodes move frequently.
Issue Date:1997
Description:173 p.
Thesis (Ph.D.)--University of Illinois at Urbana-Champaign, 1997.
Other Identifier(s):(MiAaPQ)AAI9812572
Date Available in IDEALS:2015-09-25
Date Deposited:1997

This item appears in the following Collection(s)

Item Statistics