Optimization of LZ78 compression algorithm in tracing location of mobile communication users
Subject Areas : electrical and computer engineeringM.R. mirsarraf 1 * , movaghar movaghar 2 , Mohammad Hakkak 3
1 -
2 -
3 - Tarbiat Modares University
Abstract :
For location updating of mobile users, two compression algorithms, namely, LZ78 and proposed compression algorithm (modified LZ78) are introduced in this paper to be used in PCS networks. Some problems related to using these algorithm are the usage of memory of dictionary in mobile users and HLR data base as well as the ambiguity about the last location of mobile users due to delay in location updating caused by the compression algorithm. The advantage of these algorithms is reduction at the number of location updatings for a mobile user. With some modifications in the LZ78 algorithm, its problems in implementation are reduced and its usage for PCS networks is enhanced. These changes result from combining this algorithm with distance based location updating algorithm and sending symbols corresponding to some limited neighborhoods identity instead of cell number by compression algorithm For comparison between LZ78 and proposed modified algorithm, we use simulation technique. The simulation program have two structures for PCS network, namely, square cells and hexagon cell networks. For mobile users, we considered two movement pattern: one is directional and the other is omnidirectional movement pattern. The outputs of the simulation program are the number of location updating, the maximum ambiguity of user location and size of dictionary for compression algorithms. Comparing the two algorithms by simulation, we observe that in the modified LZ78 algorithm the parameters of location updating number, maximum user ambiguity and size of dictionary are lower than those in the LZ78 algorithm. At the end of the article, cost of location management of mobile user versus call to mobility ratio (the average number of call toward user to the average number of its movement) is calculated. By comparing location management for LZ78 algorithm, modified LZ78 and distance based location updating algorithm, we observe that the cost of location management is reduced for modified LZ78 compression algorithm.
[1] A. D. Malyan, L. J. Ng, V. C. M. Leung, and R. W. Donaldson, "Network architecture and signalling for Wireless personal Communications," IEEE J. Selected Area Commun., vol. 11, no. 6, pp. 830-841, Aug. 1993.
[2] Y. B. Lin, "Determining the user locations for personal communication networks," IEEE Trans. Veh. Technol., vol. 43, no. 3, pp. 466-473, Aug. 1994.
[3] A. Aabutaleb and V. O. K. Li, "Paging strategy optimization in personal communication system," ACM/Baltzer J. Wireless Networks, vol. 3, no. 3, pp. 195-204, Aug. 1997.
[4] I. F. Akyildiz, J. McNair, J. S. M. Ho, H. Vzunalioglu, and W. Wang, "Mobility management in next generation wireless systems," Proc. IEEE, vol. 87, no. 8, pp. 1348-1358, Aug. 1999.
[5] I. F. Akyildiz, J. S. M. Ho, and Y. -B. Lin, "Movement-Based location update and selective paging for PCS networks," IEEE/ACM Trans. Networking, vol. 4, no. 4, pp. 629-638, Aug. 1996.
[6] A. Bar-Noy, I Kessler, and M. Sidi, "Mobile users: to update or not to update," ACM/Baltzer J-Wireless Networks, vol. 1, no. 2, pp. 175-186, Jul. 1995.
[7] J. S. M. Ho, and I. F Akyildiz, "Mobile user location update and paging under delay constraints," ACM/Baltzer J. Wireless Networks, vol. 1, no. 4, pp. 413-425, Dec. 1995.
[8] U. Madhow, M. Honig, and K. Steiglitz, "Optimization of wireless resource for personal communications mobility tracking," IEEE/ACM Trans. Networking, vol. 3, no. 6, pp. 698-707, Dec. 1995.
[9] C. Rose, "Minimizing the average cost of paging and registration: A timer-based method," ACM/Baltzer J. Wireless Networks, vol. 2, no 2, pp. 109-116, Jun. 1996.
[10] V. W. Wang and V. C. M. Leung, "An adaptive distance-based location update algorithm for next-generation PCS networks," IEEE J. Selected Areas in Comm. , vol. 19, no.10, pp. 1942-1952, Oct.2001.
[11] S. K. Sen, A. Bhattacharya, and S. K. Das, "A selective location update strategy for PCS users, " ACM/Baltzer J. Wireless Networks, vol. 5, no. 5, pp. 313-326, Sep. 1999.
[12] C. Rose, "State-based paging/registration: a greedy technique," IEEE Trans. Vehicular Technology, vol. 48, no. 1, pp. 1666-173, Jan. 1999.
[13] Z. Noar, "Tracing mobile users with uncertain parameters," in Proc. ACM/IEEE Mobicomm’00, pp.110-119, 2000.
[14] T. X. Grown, and S. Mohan, "Mobility management for personal communications systems," IEEE Trans. Vehicular Technology, vol. 46, no. 2, pp. 269-278, May 1997.
[15] A. Bhaltlacharya, and S. K. Das, "LeZi_update: an information_theoric framework for personal mobility tracking in PCS networks," ACM Wireless Network, vol. 8, no. 2-3,pp. 121-135, Mar./May 2002.
[16] T. A. Welch, "A technique for high performance data compression," IEEE Computer Magazine, vol. 17, no. 6, pp. 8-19, Jun. 1984.
[17] I. -R. Chen, and B. Gu, "Qualitive analysis of a hybrid replication with forwarding strategy for efficient and uniform location management in mobile wireless networks," IEEE Trans. on Mobile Computing, vol. 2, no. 1, pp. 3-15, Jan./Mar. 2003.