Abstract
The advancement of wireless technologies and range of innovative applications made wireless ad hoc and sensor networks (WASN) a very popular research area. This dissertation considers an interesting research problem of construction and maintenance of an overlay structure in WASN. An overlay is a logical topology built on top of a physical network to connect a set of nodes in a certain structure. The logical links of an overlay structure can pass through number of intermediate nodes in the network. In WASN, researchers have studied various overlay structures, such as tree, mesh, clusters overlay, for performing applications such as flooding, gathering, multicasting and lookups. An overlay acts as an abstraction to hide the complexity, irregularity, and dynamics in the underlying network from the applications running on top of it. In overlay construction, we study an innovative technique for constructing ringlike overlays on static wireless ad hoc and sensor networks. A ring-like overlay is a ring structure that connects a group of nodes in the network, as in Hamiltonian cycle. Building a Hamiltonian cycle over a random graph is very difficult. We consider practical problems such as reliable file transfer, mutual exclusion, and clock synchronization, and find that a relaxed ring structure is sufficient to solve these problems. Our proposed ring-like overlay supports multiple nodes appearances, i.e., the overlay path can pass through a node more than once. It also allows side-paths and loops in its structure. A ring-like overlay allows conflict-free two-way communications, supports node ordering, and provides cost-free status feedbacks of operations. We discuss a number of distributed construction algorithms for ring-like overlays, which optimizes a different aspect of the overlay. In overlay maintenance, we consider the design space of the resources maintenance problem in a cluster-based mobile ad hoc network (MANET). On one end, we consider the strategy of using cluster heads for maintaining resources of the clusters, referred as Cluster-Based With Head Overlay (CWHO). To address the problem associated with the head nodes, such as single point failure, hot-spot, excess power consumption, we investigate the other extreme of the design space and propose a fully distributed strategy for resource maintenance, referred as Cluster-Based WithOut Head Overlay (CWOHO). In CWOHO, we distribute the resources to all nodes in the cluster, so that every node can play the role of the cluster heads. Both CWHO and CWOHO deals with total maintenance, i.e., every cluster maintains the resource information of all other clusters in the network, which can be essential for the delay constrained or multimedia applications. In the middle of the two extremes, we investigate a third maintenance strategy, referred as Clusters with Neighbor Information (CNI). The performance of the three strategies is evaluated and compared.