Graduation Semester and Year

2010

Language

English

Document Type

Dissertation

Degree Name

Doctor of Philosophy in Computer Science

Department

Computer Science and Engineering

First Advisor

Mohan Kumar

Abstract

Devices in pervasive systems are generally resource constrained, heterogeneous, personal, and mobile. These constraints limit the services and quality of service offered by the devices. For example, execution of such tasks as video and audio processing might not be possible or successful on cell phones, PDAs and sensors. Hence interactions between devices are exploited to perform collaborative task execution. Devices with better resource levels perform tasks on behalf of other devices. This dissertation provides algorithms for cooperative service executions in pervasive environments. The major contributions of this dissertation are: (1) Cluster Based Scheduling (CBS) algorithm that performs service scheduling in smart spaces. (2) Decentralized Grading Autonomous Selection (DGAS) algorithm that performs fault tolerant service execution in Mobile Ad hoc Networks. (3) Mutual Exclusion for Opportunistic Networks (MEOP) algorithm that facilitates exclusive access to shared resources in opportunistic networks (OPNET). (4) Middleware architecture for devices in OPNETs. (5) An algorithm for performing service composition in OPNETs. The main advantages of CBS over existing schemes are - reduced communication and storage overhead, and support for usage of multiple task scheduling algorithms. CBS factors such challenges as device heterogeneity, service availability and device mobility into the scheduling algorithm. DGAS provides fault tolerance by replicating service execution onto multiple devices. Decision about participation of devices in service executions are taken autonomously by each device. DGAS avoids usage of any central entity. When multiple devices need exclusive access to a shared resource, middleware installed on the devices should facilitate the access. MEOP is a token requesting algorithm that provides exclusive access to resources in OPNETs. MEOP has lower communication overhead as compared to token ring, permission based and centralized algorithms. A middleware architecture is proposed for devices in OPNETs. The middleware is modular. Each device can implement any subset of modules. This dissertation also presents service composition algorithms for OPNETs. Analysis of success probability of task execution and the length of compositions is presented and verified. A prototype of the service composition algorithms is implemented on Bluetooth enabled devices carried by students at the University of Texas at Arlington.

Disciplines

Computer Sciences | Physical Sciences and Mathematics

Comments

Degree granted by The University of Texas at Arlington

Share

COinS