Data Dissemination and Sharing in Mobile Computing Environments

In the first part of this thesis, we study data dissemination, i.e., how to disseminate a message to other mobile nodes reliably and timely. There are mainly three ways to disseminate a message to one or more nodes in a mobile network, namely unicast, multicast, and broadcast. In this thesis, we focus on how to use gossiping to provide reliable multicast, via building up mathematical models for gossiping to evaluate its reliability. We first investigate the fault tolerance problem of gossip-based reliable multicast protocols in mobile environments. We propose a generalized gossiping algorithm and develop a mathematical model based on generalized random graphs to evaluate the reliability of the gossiping protocol, answering questions like to what extent our proposed gossiping algorithm can tolerate node failures, while guaranteeing the specified message delivery ratio. We analytically derive the maximum ratio of failed nodes that can be tolerated without reducing the required degree of reliability.;In the second part of this thesis, we study data sharing in mobile computing environments, i.e., how to share single or multiple data items with other mobile nodes efficiently and consistently. We consider data caching as the most important technique to share data items in mobile computing environments. We focus on the cache placement problem, i.e., how to select cache nodes to minimize total access cost in a mobile network. We deal with the cache placement problem in two cases: sharing single data item and multiple data items.;First, we consider the cache placement problem for sharing single data item in a mobile ad hoc network. We propose to achieve an optimal tradeoff between caching overhead and total access delay by properly selecting a subset of wireless nodes as cache nodes. Most of the existing cache placement algorithms use hop counts to measure the total cost of a caching system, but hop delay in wireless mobile networks varies due to the contentions among nodes and the traffic load on each link. Therefore, we propose to evaluate the per-hop delay using a metric defined on the contentions detected by a wireless node. We propose two heuristic cache placement algorithms, one centralized and another distributed.;Second, we consider the cache placement problem for sharing multiple data items cooperatively in an Internet-based Mobile Ad Hoc Network (IMANET). We propose a solution named Divide-and-Rule Cooperative Caching (DRCC), which divides the cache space of each node into two components: selfish and altruistic. In the selfish component, mobile nodes cache the most frequently accessed data items according to its own preference, showing the side of selfishness of a node. In the altruistic component, mobile nodes select data items in a randomized way, showing the side of altruism of a node. Given a specific access frequency distribution, we can find a near-optimal allocation solution to allocate cache sizes for the two components, aiming at minimizing the total access cost. Simulation results show that DRCC achieves much better performance than the existing best cooperative caching strategy in MANETs in terms of average query delay, caching overheads, and query success ratio. In particular, DRCC reduces caching overheads by 40% in average.;In the third part of this thesis, we apply our studies on mathematical modeling of gossiping in cooperative caching to design a novel solution named Gossip-based Cooperative Caching (GosCC) for data access in an IMANET. GosCC solves the cache placement problem, considering the sequential relation among data items. It makes use of the progress reports of mobile nodes assessing data items and the content in mobile nodes' caches to determine whether a data item should be cached at a mobile node. GosCC applies the gossiping scheme to guarantee that mobile nodes receive the accurate and timely information for making caching decisions. Simulation results show that GosCC achieves much better performance than other cooperative caching schemes, in terms of average interruption intervals and average interruption times, while sacrificing acceptable message cost to a certain degree. (Abstract shortened by UMI.)...