國立臺灣師範大學博碩士論文全文系統

簡易檢索 / 詳目顯示

回結果列表

研究生：	楊明正 Ming-Jeng Yang
論文名稱：	Quorum系統在行動網路進行容錯位置追蹤之研究 Fault-Tolerant Location Tracking in Mobile Networks with Quorum System
指導教授：	葉耀明
學位類別：	博士 Doctor
系所名稱：	資訊教育研究所 Graduate Institute of Information and Computer Education
論文出版年：	2005
畢業學年度：	93
語文別：	英文
論文頁數：	123
中文關鍵詞：	行動網路、位置追蹤
論文種類：	學術論文
相關次數：	點閱：211 下載：0
分享至:	分享至facebook 分享至twitter

查詢本校圖書館目錄查詢臺灣博碩士論文知識加值系統勘誤回報

本論文提出一些在行動網路之位置追蹤之容錯策略，包含分散式及中央式的容錯策略。首先我們提出Legion結構理論，它能用來建構分散式的應用策略，例如位置追蹤、資料分散等。從Legion結構理論，我們也發展出了一個新的LegRing策略，它具有最佳的 quorum大小。將LegRing策略應用在行動網路之位置追蹤之容錯，我們因此提出了新的行動網路之位置追蹤之容錯演算法。我們的新演算法能提供容錯及較佳的服務品質，實驗數據顯示，我們的演算法有不錯的效率。

This dissertation presents some schemes for fault-tolerant location tracking in the mobile networks. One of the key issues in the design of the mobile systems is the efficient management of location information. The current IS-41 and GSM schemes use a two-tier system of home location register (HLR) and visitor location register (VLR) databases. In a two-tier system, the success of a call requires the HLR and the callee’s current VLR to be failure-free. A VLR failure affects incoming calls to mobile hosts in the VLR’s location area. Meanwhile, if the HLR fails, it cannot direct calls to a mobile host from other hosts that are not in the same location area. Thus, tolerating the failures of the location registers (LRs) is important. In this dissertation, we propose some distributed and centralized schemes, which tolerate the failures of the location registers. Meanwhile, with quorum’s salient set property and region-based approach, our schemes store/retrieve the MH location information in the location registers of a quorum set of the local region as much as possible to avoid long delays caused by the possible long-distance of VLR and HLR. Thus, they yield better Quality of Service (QoS).
In this dissertation, firstly, we propose the Legion structure that can be used to construct schemes for distributed applications, such as location tracking, information dissemination, mutual exclusion, etc. We also present a new and simple distributed quorum-based location management scheme, LegRing, which is developed based on the Legion structure. With a small quorum size and the symmetric property, the LegRing scheme can be extended to a fault tolerant and load balanced location tracking algorithm. Also, it is applicable to distributed mobile platforms with any arbitrary number of nodes.
Furthermore, we propose a new fully distributed fault-tolerant location management algorithm, which is based on the quorum system. In the literature, many location management schemes have been proposed by researchers, which bent their efforts towards reducing the system cost. Nevertheless, our distributed location management scheme addresses the issue of service quality. With small quorum size and symmetric property, our scheme has salient features that have fault-tolerance for servers’ crashes, load balancing among location servers, and fast query response. With these features, our scheme offers better Quality of Service (QoS) in mobile networks.
In this dissertation, we also propose a centralized scheme, which tolerates the failures of the VLRs and HLR at the same time, without adding or changing any hardware of the systems. Moreover, our proposed scheme has lower HLR access rate, which can reduce the cost and delay in updating and querying. Experimental results show that our scheme can improve the performance of updating and querying in comparison with the traditional two-tier scheme.
Moreover, we propose a new scheme with cellular quorum construction to tolerate the failures of the HLR and VLRs in two-tier centralized networks. Based on the intersectional property of the update quorum and query quorum, the location information is disseminated to VLRs of the update quorum’s set and can be extracted from one of them by using the query quorum even though one or more location registers fail. Thus, without adding or changing the hardware of the systems in the centralized cellular quorum networks, our scheme provides fault tolerance for the system. Meanwhile, with region-based approach, our scheme is not only fault-tolerant but also connection establishment effective.
In summary, this dissertation investigates the problem of fault-tolerant location tracking in the mobile networks. Based on the Legion structure, we developed schemes both for the distributed and centralized systems. Our schemes address on the issues of fault-tolerance and service quality. Experimental results also show that our schemes have good performance compared to some current schemes.

Chapter 1  Introduction         1
1.1  The Mobile Networks        1
1.2  Location Tracking in Mobile Networks        4
1.3  Centralized and Distributed Location Tracking        5
1.4  Fault-Tolerant and Quorum-Based Scheme        8
1.5  Thesis Outline        9

Chapter 2  The Theory of Legion Structure        11
2.1  Quorum, Set System, and K-Coterie        11
2.2  Legion Structure        12
2.3  Applications of the Legion Structure        13
2.4.  A Location Management Scheme Based on Leg(null, null)        17
2.4.1  A Simple LegRing Scheme        17
2.4.2  The Scheme with   Quorum Size        19
2.5 Symmetric Property and Load Balance        20

Chapter 3  A Quorum-Based Scheme for Distributed Location Tracking        23
3.1  The System Model        23
3.2  Design Approach        24
3.3  Fault-Tolerant Load-Balanced Approach        27
3.4  Comparison and Discussion        28

Chapter 4  A Fully Distributed Fault-Tolerant Location Management Scheme        31
4.1  The System Model        31
4.2  Design Approach for Location Update        33
4.2.1  Local Update        33
4.2.2  Remote Update        37
4.3  Design Approach for Location Query        39
4.3.1  Local Query        39
4.3.2  Remote Query        41
4.4  Analytic Model        45
4.5  Latency Analysis for LSN        48
4.5.1  Update Latency        48
4.5.2  Query Latency        49
4.6  Latency Analysis for IS-41        50
4.6.1  Update Latency        50
4.6.2  Query Latency        51
4.7  Cost Analysis for LSN        51
4.7.1  Update Cost        51
4.7.2  Query Cost        52
4.8  Cost Analysis for IS-41        54
4.9  Numerical Results and Discussion        55

Chapter 5  Tolerating VLR and HLR Failures in Two-Tier PCS Networks        59
5.1  The System Description        59
5.2  System Design for Location Update        61
5.2.1  Intra-SR Update        63
5.2.2  Inter-SR Update        64
5.3  System Design for Location Query        67
5.3.1  Intra-SR Query        67
5.3.2  Inter-SR Query        69
5.4  Dealing with the Failure of the HLR        74
5.5  User Mobility Behavior Model        75
5.6  Performance Analysis for Proposed Scheme        79
5.6.1  Update Cost        79
5.6.2  Query Cost        80
5.7  Performance Analysis for IS-41 Scheme        82
5.8  Numerical Results        83

Chapter 6  A Cellular Quorum Scheme for Location Management        91
6.1  System Description        91
6.2  Cellular Quorum Constructions        93
6.3  The System Design        96
6.3.1  Region Update        97
6.3.2  Home Update        100
6.3.3  Region Query        102
6.3.4  Home Query        105
6.3.5  Dealing with the Failure of the HLR        108
6.4  Connection Establishment Delay Analysis        109
6.5  Numerical Results and Discussion        111
Chapter 7  Concluding Remarks        114

References        117

Appendix        123

LIST OF FIGURES


Fig. 1-1. Illustration of a cell with a MSS and mobile hosts (MHs)        3
Fig. 1-2. The basic cellular system infrastructure and location tracking scheme        5
Fig. 1-3. Signal flow of location update for IS-41scheme        6
Fig. 1-4. Signal flow of location query for IS-41scheme        7
Fig. 2-1. The applications of Legion mapped on the dimension and set system type.    16
Fig. 2-2. System structure based on the quorum system.        22
Fig. 3-1. Logical view of a mobile network with distributed location database        24
Fig. 4-1. Logical view of network topology         32
Fig. 4-2. Local update         34
Fig. 4-3. Remote update         36
Fig. 4-4. Local query        40
Fig. 4-5. Remote query         43
Fig. 4-6. The state diagram of the imbedded Markov chain         46
Fig. 4-7. Comparisons of average update latency under various RAs         56
Fig. 4-8. Comparisons of average query latency under various CMR         57
Fig. 4-9. Comparisons of total cost under various CMR         58
Fig. 5-1. System architecture        60
Fig. 5-2. Intra-SR Update         62
Fig. 5-3. Signal flow of intra-SR update         64
Fig. 5-4. Inter-SR update         65
Fig. 5-5. Signal flow of inter-SR update         67
Fig. 5-6. Intra-SR query         68
Fig. 5-7. Signal flow of intra-SR query         69
Fig. 5-8. Inter-SR query         70
Fig. 5-9. Signal flow of inter-SR query         72
Fig. 5-10. Dealing with the failure of the HLR         75
Fig. 5-11. The state transition diagram         77
Fig. 5-12. Comparisons of average query cost under various CMR         84
Fig. 5-13. Comparisons of total cost under various CMR         85
Fig. 5-14. Comparisons of average update cost under various LAs         86
Fig. 5-15. Comparisons of total cost under various LAs         87
Fig. 5-16. Comparisons of average query cost under various hit ratio         88
Fig. 5-17. Comparison of total cost under various fault probability         89
Fig. 6-1. System architecture with cellular quorum system         92
Fig. 6-2. A fault-tolerant region (FTR) and its position coordinate         93
Fig. 6-3. The construction and intersectional property of U-quorum and Q-quorum        95
Fig. 6-4. Region Update        99
Fig. 6-5. Home update         101
Fig. 6-6. Region query         103
Fig. 6-7. Home query         106
Fig. 6-8. Dealing with the failure of the HLR         108
Fig. 6-9. Comparisons of query latency under various CMR         111
Fig. 6-10. Comparisons of query latency under various hit ratio         112

LIST OF TABLES


Table 1-1. Wireless technologies and associated characteristics        2
Table 3-1. Comparisons of quorum-based location management schemes        30
                                

[1] D.P. Agrawal and Q.A. Zeng, Wireless and Mobile Systems, Thomson, 2003
[2] D.P. Agrawal, “Future directions in mobile computing and networking systems,” Workshop sponsored by the NSF, University of Cincinnati (Jun. 13–14), 1999; www.ececs.uc.edu/~dpa.
[3] R. Malladi and D.P. Agrawal, “Current and Future Applications of Mobile and Wireless Networks,” Communications of the ACM, 2002
[4] Y.-B. Lin, “Reducing Location Update Cost in a PCS Network,” IEEE/ACM Trans. Networking, vol. 5, no. 1, pp. 65-73, Feb. 1997.
[5] J. Li, Y. Pan, and X. Jia, “Analysis of Dynamic Location Management for PCS Networks,” IEEE Trans. Vehicular Technology, pp. 1109-1119, Sept. 2002.
[6] Z. Mao and C. Douligeris, “A Location-Based Mobility Tracking Scheme for PCS Networks,” Computer Comm., vol. 23, no. 18, pp. 1729-1739, Dec. 2000.
[7] A. Abutaleb and V.O.K. Li, “Location Update Optimization in Personal Communication Systems,” ACM-Baltzer J. Wireless Networks, vol. 3, no. 3, pp. 205-217, Aug. 1997.
[8] I.F. Akyildiz, J. Ho, and Y. Lin, “Movement-Based Location Update and Selective Paging for PCS Networks,” IEEE/ACM Trans. Networking, vol. 4, no. 4, pp. 629-638, Aug. 1996.
[9] 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, July 1995.
[10] A. Abutaleb and V.O.K. Li, “Paging Stragegy Optimization in Personal Communication Systems,” ACM-Baltzer J. Wireless Networks, vol. 3, no. 3, pp. 195-204, Aug. 1997.
[11] Y. Fang, I. Chlamtac, and Y. Lin, “Portable Movement Modeling for PCS Networks,” IEEE Trans. Vehicular Technology, vol. 49, no. 4, pp. 1356-1363, July 2000.
[12] I. Akyildiz and W. Wang, “A Dynamic Location Management Scheme for Next Generation Multisuer PCS Systems,” IEEE Trans. Wireless Comm., vol. 1, no. 1, pp. 178-189, Jan. 2002.
[13] U. Madhow, M. Honig, and K. Steiglitz, “Optimization of Wireless Resources for Personal Communications Mobility Tracking,” IEEE/ACM Trans. Networking, vol. 3, no. 4, pp. 698-707, Dec. 1995.
[14] J. 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.
[15] 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, June 1996.
[16] J. Li, H. Kameda, and K. Li, “Optimal Dynamic Mobility Management for PCS Networks,” IEEE/ACM Trans. Networking, vol. 8, no. 3, pp. 319-327, June 2000.
[17] EIA/TIA, “Cellular radio telecommunications intersystem operation,” PN-2991, Nov. 1995.
[18] M. Mouly and M.-B. Pautet, The GSM System for Mobile Communications. France: Palaiseau, 1992.
[19] G.H. Li, K.Y. Lam, T.W. Kuo, and S.W. Lo, “Location Management in Cellular Mobile Computing Systems with Dynamic Hierarchical Location Databases,” Journal of Systems and Software 69, pp.159-171, 2004.
[20] J. Hassan, and S. Jha, “A Cell-Based Distributed Location Management Protocol for Cell-Hopping networks,” Proceeding of 10th IEEE International Conference on Telecommunications, pp. 422-425, 2003.
[21] M.J. Yang, Y.M. Yeh, and Y.M. Chang, “Legion Structure for Quorum-Based Location Management in Mobile Computing,” Journal of Information Science and Engineering, pp.191-202, Jan. 2004.
[22] K. Ratnam, I. Matta, and S. Rangarajan, “A Fully Distributed Location Management Scheme for Large PCS,” Proceedings Fifth IEEE Symposium on Computer and Communications, pp.514-519, 2000
[23] R. Prakash, Z. Haas and M. Singhal, “Load-balanced location management for cellular mobile systems using quorums and dynamic hashing,” Wireless Networks 7 (5), pp.497-512, 2001.
[24] H.C. Lin, S.L. Lee and W.Y. Lin, “Dynamic Location Strategy for Hot Mobile Subscribers in Personal Communications,” Computer Communications 26 (12), pp.1353-1346, 2003
[25] H.C. Lin and S.L. Lee, “A Track-Presetting Strategy in PCS Using Hierarchical Location Databases,” Computer Communications 25 (18), pp.1727-17356, 2002.
[26] R. Prakash and M. Singhal, “A dynamic approach to location management in mobile computing systems,” Proceedings of the 8th International Conference on Software Engineering & Knowledge Engineering, pp. 488-495, 1996.
[27] Ihn-Han Bae, “A quorum-based dynamic location management method for mobile computings,” Proceedings of the 6th International Conference on Real-Time Computing Systems and Applications (RTCSA), pp.398-401, 1999.
[28] Y. Xiao, “Backoff strategies for demand re-registration in PCS database failure recovery,” Computer Communications 27(5), pp.400-411, 2004.
[29] C. Liu, D. Yu, H. Qiu, and J. Wu, “Research of VLR mobility database failure recovery and performance analysis for CDMA2000 system,” IEEE Proceedings on Personal, Indoor and Mobile Radio Communications, pp. 1501-1505, 2003.
[30] K. Ratnam, S. Rangarajan, and A.T. Dahbura, “An Efficient Fault-Tolerant Location Management Protocol for Personal Communication Networks,” IEEE Transactions on Vehicular Technology 49 (6), pp.2359-2369, 2000.
[31] M. Naor and A. Wool, “Access Control and Signatures via Quorum Secret Sharing,” IEEE Transaction on Parallel and Distributed Systems 9 (9), pp.909-922, 1998.
[32] R. H. Thomas, “A Majority Consensus Approach to Concurrency Control for Multiple Copy Databases,” ACM Transactions on Database Systems, Vol. 4, 1979, pp. 180-209.
[33] D. K. Gifford, “Weighted voting for replicated data”, Proceedings of the Seventh Sympisium on Operating Systems Principles, pp. 150-159, 1979
[34] S. Fujita, M. Yamashita, and T. Ae, “Distributed k-mutual exclusion problem and k-coteries,” Proceedings of the 2nd International Symposium on Algorithms, Lecture Notes in Computer Science, vol. 557, Springer, Berlin, pp. 22-31, 1991.
[35] S.T. Huang, J.R. Jiang, and Y.C.Kuo, “K-coteries for fault-tolerant k entries to a critical section,” Proceedings of the 13th IEEE International Conference on Distributed Computing systems, pp. 74-81, 1993.
[36] C.M. Lin, G.M. Chiu, and C.H. Cho, “A new quorum-based scheme for managing replicated data in distributed systems,” IEEE Transactions on Computers, Vol. 51, pp. 1442-1447, 2002.
[37] W.K. Ng and C.V. Ravishankar, “Coterie templates: A new quorum construction method, ” Proceedings of the 15th IEEE International Conference on Distributed Computing Systems, pp. 92-99, 1995.
[38] G. Karumanchi, S. Muralidharan, and R. Prakash, “Information dissemination in partitionable mobile ad hoc networks,” Proceedings of the 18th IEEE Symposium on Reliable Distributed Systems, pp. 4-13, 1999.
[39] H.N. Minh and H.R. As, “Performance Analysis of Distributed Location Management for Wireless Networks,” Proceedings of the 15th IEEE International Conference on Information Networking, pp. 25-31, 2001.
[40] I.F. Akyildiz and W.A.. Wang, “A Dynamic Location Management Scheme for Next-Generation Multitier PCS Systems,” IEEE Transactions on Wireless Communications 1 (1), pp.178 -189, 2002.
[41] K. Wang and J. Huey, “A Cost Effective Distributed Location Management Strategy for Wireless Networks," Wireless Networks 5 (4), pp.287 -297, 1999.
[42] S.C. Lo and Arbee L.P. Chen, “Adaptive region-based location management for PCS systems,” IEEE Transactions on Vehicular Technology 51 (4), pp.667 -676, 2002.

簡易檢索 / 詳目顯示

相關論文