Type
Text
Type
Dissertation
Advisor
Tang, Wendy | Robertazzi, Thomas | Gamboa, Carlos | Liu, Yanni | Noel, Eric
Date
2012-12-01
Keywords
Electrical engineering--Computer engineering | Borel Cayley Graph, Fault-tolerant Routing, Interconnection Networking, Topology Control, Wireless Sensor Network
Department
Department of Electrical Engineering
Language
en_US
Source
This work is sponsored by the Stony Brook University Graduate School in compliance with the requirements for completion of degree.
Identifier
http://hdl.handle.net/11401/71395
Publisher
The Graduate School, Stony Brook University: Stony Brook, NY.
Format
application/pdf
Abstract
In dense wireless sensor networks, a sensor node may have several neighbor nodes within radio range. In this case, efficient network design is more challenging than with sparse networks. Researches on efficient network design for dense networks are often based on random networks and include comprehensive network performance analysis. Random networks have many advantages for wireless sensor networks, such as short-distance radio range, flexibility for nodes to join or leave the network, and self-organization. However, there are also disadvantages inherent to random networks such as difficulty to guarantee global properties such as diameter and connectivity. On the other hand, there have not been a lot of research on the use of structured graphs for wireless sensor networks. This observation motivated us to investigate the benefits and limitation of applying structured graphs on wireless sensor networks and to take advantage of such graphs' guaranteed global properties. We focus on Borel Cayley graphs (BCG) as a family of structured graph, which have been shown to be an efficient candidate as a logical topology for sensor networks. BCGs are known to have small diameters and average path lengths. Also, BCGs are symmetric graphs, a property that enables distributed routing. Even though BCGs have these favorable properties, there are practical limitations in applying BCGs to wireless sensor networks. One of them is the possible existence of long-distance communication edges between logically connected sensors since BCG connections are not based on nodes' geographical positions. Connections of BCGs look like pseudo-random connections. It is this pseudorandomness that enables BCGs to have a small diameter and a short average path length between nodes. However, when overlaying a BCG on a sensor network, such pseudo-randomness makes it possible to produce long-distance connections. Another practical limitation is the lack of fault-tolerant routing algorithms: existing BCG routing algorithms do not account for node or communication link failures. In this dissertation, we present results on the practical realization of BCGs as structured graphs for wireless sensor networks. In particular, we present node ID assignment algorithms that allow topology construction of BCGs with consideration of the nodes' geographical distribution; and also present a fault tolerant routing algorithm, accounting for node or communication link failures. Our node ID assignment algorithms assign node IDs to a wireless sensor network based on a pre-defined BCG connection rule. The goal of our algorithms is either to (1) reduce the average physical communication distance based on the geographical positions of the network nodes, assuming all nodes are within communication distance of each other; or (2) to assign IDs that enables the network topology to represent most but not necessarily a complete representation of the BCG due to out of range nodes. With our fault tolerant routing algorithm, the routing tables of nodes are updated distributively in response to node/link failures. We quantify the performance of the routing algorithm by considering packet reachability and End-to-End delay for different levels of communication link failures and packet generation. From our research, we show that with our proposed node ID assignment and fault tolerant routing algorithm, BCGs are good candidates as structured graph topologies for wireless sensor networks. | 101 pages
Recommended Citation
Ryu, Jung hun, "Design and Analysis of Structured Graph based Wireless Sensor Networks" (2012). Stony Brook Theses and Dissertations Collection, 2006-2020 (closed to submissions). 601.
https://commons.library.stonybrook.edu/stony-brook-theses-and-dissertations-collection/601