Data Allocation in a Mobile Computing Network with Minimized Response Time and Communication Cost

Shaheen Ayyub and Sanjeev Jain

Computer Science & Engineering, LNCT, Bhopal (India).

ABSTRACT:

In this paper, we devise data allocation algorithms that can utilize the knowledge of user moving patterns for proper global data allocation in a mobile computing system. By employing the data allocation algorithms devised, the occurrences of costly remote accesses can be minimized and the performance of a mobile computing system is thus improved. The issue we addressed here is to allocate right data at right location while minimizing communication cost and response time of the network.

KEYWORDS: User Moving Patterns; Mobile Computing; Global Data Allocation; Mobile Databases

Copy the following to cite this article: Ayyub S, Jain S. Data Allocation in a Mobile Computing Network with Minimized Response Time and Communication Cost. Orient. J. Comp. Sci. and Technol;2(2)

Copy the following to cite this URL: Ayyub S, Jain S. Data Allocation in a Mobile Computing Network with Minimized Response Time and Communication Cost. Orient. J. Comp. Sci. and Technol;2(2). Available from: http://www.computerscijournal.org/?p=2141

Introduction

Recently, the number of mobile users has increased explosively worldwide, owing to the technological advances of mobile devices and wireless data networking. Mobile users can access a great deal of information though wireless communications such as mobile phones in mobile computing systems. Mobile communications are influencing our everyday lives tremendously from both economic and social perspective. One of the most important issues in designing a mobile computing system is data replication, because mobile devices still have a shortage of computing capability and limited storage. Therefore, mobile computing systems rely on distributed server systems. The system performance can be improved by replicating data and allocating these data at servers. However, how many copies of data we need? And how these data will be allocated at servers? And at which server should we allocate the data? How many sub servers are connected to a server at which the data is allocated? These issues are correlated with each other and affect the performance of the network.

In the past several data allocation schemes have been proposed. These schemes can be classified as personal data allocation and global data allocation. In both type of algorithm the cost is still too much and we have no idea of what data the user really wants. After these algorithms four other algorithms have also been proposed four proper data allocation. These algorithms focus on different views like average hit ratio, average response time, average communication cost. Each algorithm give best results in their specific criteria. No one is suitable for all. Here we proposed an algorithm which gives approximately improved results for all. We have taken into consideration both response time and communication cost to develop the data allocation scheme, and this feature distinguishes our scheme from others.

System Architecture

In a mobile environment there are many RNCs(radio network controller) and Base stations as shown in fig. whenever a user sends a request to a base station it is sent back to the corresponding RNC and then RNC allocate the requested data at the base station.

The problem here is that, How base stations are connected to RNCs? and what data we will allocate to RNCs, in order to get the requested data mostly from local RNC, but not from remote RNC.

Allocation

Base Station Allocation

To allocate base stations to RNCs we have considered the distance between all the base stations and the RNC. And then applied Dijikstra’s algorithm to find the shortest path from a particular RNC.

Data Allocation

For allocating data at RNCs we have considered user request patterns and user moving patterns. And we are also having subordinacy between base stations and RNCs. By using all these information we can make RNC frequency matrix,in which frequency of users for each RNC is given. which means that how frequently a user can access a RNC.

Algorithm

Input

user request patterns(in the form of matrix)

RNC frequency matrix (“)

Cost of data Communication(“)

Response Time(“)

Output

Right data allocated at right location with minimized response time and communication cost

Begin

´ Allocate base station to RNCs according to the distances between them to get RNC frequency matrix

´ Multiply user request patterns with RNC frequency matrix to get RNC data matrix

´ Apply all pair shortest path algorithm to Communication Cost matrix in order to get minimum Communication Cost

´ Apply all pair shortest path algorithm to Response time matrix to get minimized response time.

´ Now from both of the matrices above find out the minimum of the two to get a new matrix called MRC matrix(minimum of Response time and communication Cost). Each value in this matrix represent the

minimum of the two i.e.

for i = 1 to n              n>=3

for j= 1 to n

minimum value (MRC) = min(CCij,RTij)

end

´ Now column wise multiply MRC matrix with the RNC data matrix to get the data allocated at RNCs.

´ End

Figure 1: RNCs in mobile environment Click here to View figure

 

Performance Analysis

Figure 2: Comparison with the previous algorithms based on response time Click here to View figure

 

Figure 3: Comparison with the previous algorithms based on Communication Cos Click here to View figure

 

References

1. D. Barbara, “Mobile Computing and Databases-A Survey,” IEEE Trans. Knowledge and Data Eng., 11(1): 108-117(1999).
2. B. Bruegge and B. Bennington, “Applications of Mobile Computing and Communication,” IEEE Personal Comm., 64-71 (1996).
3. K. Buchanan, R. Fudge, D. McFarlane, T. Phillips, A.A. Sasaki, and H. Xia, “IMT-2000: Service Provider’s Perspective,” IEEE Personal Comm., 4(4): 8-13 (1997).
4. IEEE Transactions On Parallel and Distributed Systems, Shared Data Allocation in a Mobile Computing System: Exploring Local and Global Optimization Wen-Chih Peng and Ming-Syan Chen, Fellow, IEEE 16(4): (2005).
5. Allocation of Shared Data based on Mobile User Movement Wen-Chih Peng and Ming-Syan Chen Department of Electrical Engineering National Taiwan University Taipei, Taiwan, ROC E-mail: {mschen@cc.ee. ntu.edu.tw, wcpeng@arbor.ee.ntu.edu.tw}
6. Vertex-based Shared Data Allocation in a Mobile Computing System Jin-Woo Song41, Kwang-Jo Lee 2, Jung-Suk Han 3, Sung-Bong Yang4 ‘1-4 Department ofComputer Science, Yonsei-University Seoul, 120-749 Korea
7. Margaret H. Dunham, Vijay Kumar: Impact of Mobility on Transaction Management. MobiDE 14-21 (1999).
8. Serrano-Alvarado P., Roncancio C., Adiba M., “Analyzing Mobile Transactions Support for DBMS”, Int. Workshop on Mobility in Databases and Distributed Systems (in DEXA) (2001).
9. Global data allocation based on user behaviors in mobile computing environments, Yin-Fu Haung and Kun-Hao-Lin, Institute of Electronic and Information Engineering, National Yunlin University of Science and Technology, Taiwan
10. Fragment Allocation in Distributed Database Design YIN-FU HUANG AND JYH-HER CHEN Institute of Electronics and Information Engineering National Yunlin University of Science and Technology Yunlin, Taiwan 640, R.O.C.
11. Data Allocation In Distributed Database Systems Performed By Mobile Intelligent Agents by Horea Grebla, Grigor Moldovan, Sergiu Adrian Darabant, Alina Câmpan.

---

This work is licensed under a Creative Commons Attribution 4.0 International License.