Efficient data sharing in mobile computing systems : replicated server allocation algorithms and peer-to-peer file sharing systems

다국어 초록 (Multilingual Abstract)

Nowadays, mobile device users get various services from telecommunication companies that seemed to be rather almost impossible about a decade ago. Such services are possible thanks to the advances in mobile and cellular communications technologies. Although we are enjoying the benefits from the technological advances, the current mobile devices still have insufficient computing capability and storage; because users ever demand smaller size devices with more added functionality and enhanced system performance. In general, mobile computing systems rely on decentralized server systems for efficient mobile services. Data sharing is a key problem to provide faster accessibility towards shared data for users by reducing costly accesses to the online servers.
This dissertation addresses three kinds of data sharing systems in mobile computing systems for speeding up data accesses; they are the shared data allocation system in mobile networks, the cost-based shared data allocation system in mobile networks, and the peer-to-peer file sharing systems in mobile ad-hoc networks.
The first system distributes replicated servers into a mobile network to speed up data accesses for uses. It is obviously profitable to allocate replicated servers at the cells where a lot of mobile users visit. For the first system we propose various replicated server allocation algorithms which exploit users’ moving patterns as well as data access patterns. Some of them are greedy algorithms and the rest are global search algorithms.
The second system distributes replicated servers into a mobile network with considering the communication costs. The first system focused on the placement of replicated servers along with the moving paths of mobile users to maximize the hit ratios. When a mobile user wants to access some data in the area at which a replicated server is not located, the user fails to get the data and a miss is said to be occurred. Therefore, we suggest a solution to take care of such a miss by sending the file request to a replicated server nearby in the mobile network. That is, the users are allowed to request nearest replicated servers for their demands. However, such allowance does give rise to communication costs. The second system distributes replicated servers into a mobile network with considering the communication costs. In this system we propose several algorithms that allocate available replicated servers in the network so as to minimize the communication costs.
In the third system some mobile devices themselves serve as replicated servers. Faster data communications among mobile devices such as cell phones and PDAs are always welcomed by mobile device users for exchanging data likes favorite movies, music, images, and text files. Thus mobile devices should be efficiently connected to construct a peer-to-peer file sharing system in a mobile ad-hoc network. In this system we propose three different file sharing systems that have double-layered topology. The double-layered topology not only enables fast data sharing among mobile users but also prevents multi-broadcast.
The experimental results showed that the proposed algorithms for data sharing systems provide better performance than previous researches. In the first system the proposed algorithms showed better average hit ratios than the previous best algorithm by 2.7% ~ 4.5%. The vertex-based activity count algorithm, the simulated annealing algorithm, and the genetic algorithm showed the near optimal hit ratios. In the second system the proposed algorithms showed less average communication cost than the edge based replicated server allocation algorithms by 8.7% ~ 36.4%. The simulated annealing algorithm and the genetic algorithm allocated replicated servers with near optimal communication costs. In the third system the proposed systems improved the performance in terms of the average number of messages to find target files with respect to a previously known comparable system, ORION. Such improvement was possible because they could reduce the network traffics successfully by forcing super-peers to communicate among themselves instead of multi-broadcasting. The reduced MIS system showed the best performance and improved the performance by 48.9% over ORION.
Moreover, we propose an enhanced double-layered P2P system in which super-peers are selected based on their mobility. Also, we propose two reliability improvement schemes, the avoidance scheme and the role changing scheme. They are applied to the proposed system to enhance the reliability of the system. Most of the previous P2P systems are evaluated under the `static' mobile P2P environment in which the number of peers is fixed and there are no dynamic joins and leaves. Moreover, there are many systems that do not even consider the mobility of peers. In mobile networks, the reliability that guarantees communication among peers is one of the crucial factors to be considered.
The experimental results show that the proposed system with the two schemes improved the reliability over other double-layered systems in terms of the failure rate by up to 25 %, while increasing the network traffic marginally.
There are five main contributions of this dissertation. First, we have proposed replicated server allocation algorithms for the first system which increased the hit ratios up to near optimal values. The proposed algorithms utilized the occurrence counts on vertices instead of on edges. Second, we modified the first system to allow the users to access the shared data through the replicated servers nearby in the mobile network, rather than through the online server. Therefore, the second system takes care of a miss by sending the file request to a replicated server nearby in the network. Third, we have proposed replicated server allocation algorithms for the second system which decreased the communication cost up to near optimal values. Fourth, we have proposed a few mobile P2P file sharing systems that have double layered topology for the third system. The proposed mobile P2P file sharing systems showed quite smaller average number of messages than ORION. Finally, we have proposed an enhanced double-layered mobile P2P system for reliability in the dynamic mobile environment.