Umair Sadiq

Graduation Semester and Year

2013

Language

English

Document Type

Dissertation

Degree Name

Doctor of Philosophy in Computer Science

Department

Computer Science and Engineering

First Advisor

Mohan Kumar

Abstract

Opportunistic networks formed by users' mobile devices have the potential to exploit a rich set of distributed service components that can be composed to provide each user with a multitude of application level services. In opportunistic networks, tasks such as content sharing and service execution among remote devices are facilitated by intermediate devices capable of short–range wireless connectivity, also called relays that receive, move around, and forward the data.To enable effective collaboration in such an environment, we make three novel contributions: (i) an adaptive forwarding scheme, ProxiMol, to select suitable relays for data transfer; (ii) a distributed mechanism to select services that can be composed; and (iii) an incentive–compatible credit scheme, CRISP, to promote participation of relays to forward data. These contributions resolve key challenges in opportunistic networks as in existing works, data transfer is not adaptive to changing user behavior, services composition is not performed on remote devices in the absence of a connected path, and rewards are not incentive–compatible( i.e. rewards do not promote honest behavior of users).ProxiMol is a novel forwarding scheme leveraging two simple facets of users in opportunistic networks – some users have better likelihood of message delivery due to higher mobility, while others do due to their locations proximity to destination. Key contributions to the design of ProxiMol include: (i) a model to infer users location over time from diffusion (a measure of mobility); (ii) an analytical result to estimate distance between users; and (iii) an empirical method to estimate diffusion of a user. ProxiMol improves delivery ratios (10–20%) and reduces delays by up to 50%, when compared against previously proposed algorithms.The proposed service composition algorithm derives efficiency and effectiveness by taking into account the estimated load at service providers and expected time to opportunistically route information between devices. Based on this information the algorithm decides the best composition to obtain a required service. It is shown that using only local knowledge collected in a distributed manner, performance close to a real–time centralized system can be achieved. Scope and applicability of the service composition algorithm in a range of mobility characteristics are established through extensive simulations on real/synthetic mobility traces.CRISP (Collusion–Resistant Incentive–ComPatible routing and forwarding) is the first credit scheme in which both routing and forwarding are designed to be incentive compatible in opportunistic networks, i.e., honest behavior of users maximizes their profit. Data transfer and loss in opportunistic networks are modeled as a linear generalized flow network where flow maximization leads to optimal relay behavior. This optimal behavior is made incentive compatible by requiring a relay to make a specific payment upon receiving the data and earn reward for forwarding the data. Simulations on real and synthetic mobility traces validate our analysis, showing a significant gain in throughput when compared with the existing credit schemes that are not incentive compatible.

Disciplines

Computer Sciences | Physical Sciences and Mathematics

Comments

Degree granted by The University of Texas at Arlington

Download

Share

COinS