Display Full Text | Download Full Text
2.95 MB PDF file

Degree

Doctor of Philosophy, Ohio State University, Computer and Information Science, 2006.

Abstract

The lack of a basic understanding of its essential components has been an obstacle for reliable, efficient, and reusable messaging services in sensornets. To address this problem, this dissertation identifies the basic components of sensornet messaging and studies the related algorithmic design issues. More specifically, we propose the messaging architecture SMA that consists of three components: traffic-adaptive link estimation and routing (TLR), application-adaptive structuring (AST), and application-adaptive scheduling (ASC). TLR deals with dynamic wireless links as well as the impact of application traffic patterns on link dynamics; AST and ASC control the spatial and temporal flow of data packets to support application-specific in-network processing and QoS requirements. To provide an instance of TLR, we propose the routing protocol Learn-on-the-Fly that solves the problem of precisely estimating wireless link properties in the presence of varying network conditions. Then, we study ASC from the perspective of in-network processing and QoS provisioning. Taking packet packing as an example of in-network processing, we study the problem of scheduling packet transmissions to improve messaging efficiency. For the basic problem of reliable and real-time data transport in event-detection sensornets, we propose the protocol Reliable-Bursty-Convergecast that innovates the window-less block acknowledgment scheme and the retransmission-aware differentiated contention control. The architecture SMA provides a framework for sensornet messaging, and the study of TLR and ASC provides algorithmic references for instantiating SMA. This part of the dissertation work has also provided dependable messaging services for several real-world sensornet systems. The second part of this dissertation addresses the challenges that complex faults and large system scale bring to the design of fault-tolerant protocols. To this end, we propose the concept of “local stabilization“. In a locally-stabilizing system, fault impact is locally contained around where the fault has occurred, and the time taken for the system to stabilize depends only on the size of the fault-perturbed region instead of the system size. For shortest path routing, a basic problem in messaging, we propose a locally-stabilizing protocol LSRP. The concept of local stabilization and the algorithmic approach of LSRP are generically applicable to other networking and distributed computing problems.

Subject Headings

Computer Science

Keywords

wireless sensor networks; messaging; wireless communication; resource constraints; application diversity; routing; data-driven link estimation and routing; transport; reliable and real-time data transport; in-network processing; scalable dependability

Advisor

Anish Arora

Pages

208p.

Document number: osu1155607973
Permalink: http://rave.ohiolink.edu/etdc/view?acc_num=osu1155607973

This ETD has been downloaded 708 times (through March 2013)