臺灣博碩士論文加值系統

隨著網際網路科技的迅速發展，網路拓撲型態也走向無線化。行動無線網路的趨勢使得分散式系統的設計也實行在行動計算之中。現今行動無線網路中有許多應用服務在執行時需要領袖選擇演算法來配合，比如在群組通訊協議之中，當原本的群組協調者發生錯誤無法正常運作時，該群組即需要產生新的協調者。換句話說，領袖選擇在分散式計算中是一個基本問題。然而在無線網路的環境下，分散式系統是極為不安全的，處理器或是無線通訊皆有可能發生錯誤，良好的處理器或是通訊通道可能因此遭受其影響，因此在這個網路環境之下，更需要容錯計算來確保領袖選擇的運作。我們在此提出一個容錯式領袖選擇演算法，該演算法可以容許最多的錯誤單元，並且使用最佳化的通訊複雜度達成所有良好的處理器可以選擇共同的領袖。

Mobile ad hoc network is new trend of networking system. This technology trends have greatly encouraged distributed system design and practice to support mobile computing. In present, there are a lot of applications for mobile networks need some sort of leader election algorithm for their operation. For example, in the group communication protocols, the election of a new coordinator is required when a group coordinator crashes or departs the system. In other words, leader election is a fundamental problem for distributed computing. However, it is more dangerous under such mobile environment. Processors in mobile network may suffer the influences caused by illegal processors that can intrude this network easily. Besides, the communication in wireless network is transmitted by radio frequency. It is also possible for an unauthorized processor, located within the transmitter’s communication radius, to listen to the communication. Thus, we need fault-tolerant computing under mobile networks to tolerate faulty components and ensure the correct operation of the leader election process. The protocol we proposed is a leader election algorithm for fault-tolerant mobile ad hoc network in this article. The protocol can tolerant maximum faulty components to ensure that all fault-free processors to elect a common leader with optimal communication complexity.

LIST OF TABLES　　　　　　　　　　　　　　　　　　　 II
LIST OF FIGUERS　　　　　　　　　　　　　　　　　　 　 III
ABSTRACT 　　　　　　　　　　　　　　　　　　 IV
1 Introduction………………………………………………………………1
2 Related work………………………………………………………………3
2.1 Mobile Ad hoc Network………………………………………………3
2.2 Routing of MANET……………………………………………3
2.3 Leader Election in a Wired Network……………………………9
2.4 Leader Election in MANET………………………………11
2.5 Fault Tolerance…………………………………………………17
2.6 Identity-based signature and Threshold cryptography………20
2.7 Conclusion of chapter…………………………………………26
3 System Model……………………………………………………………28
3.1 Definitions and Assumptions……………………………………28
3.2 Constraints on failures…………………………………………29
3.3 Problem statement………………………………………………31
4 Principles and Concepts of proposed protocol………………………32
4.1 Basic concept and approaches…………………………………32
4.2 The algorithm of FTLE…………………………………………38
4.2.1 The encrypt method with digital signatures40
4.2.2 Removing the influence of a Faulty Intermedium40
4.2.3 Removing the influence of a Dormant Faulty Sender……43
4.2.4 Removing the influence of an Arbitrary Faulty Sender44
4.3 Examples of algorithm……………………………………………46
4.3.1 The case of the broadcast network with mixed faults on both processors and links………………………………………46
4.3.2 The general case of the mobile ad-hoc network with mixed faults on both processors and links…………………………48
4.3.3 The extreme case network…………………………………52
4.4 Correctness………………………………………………………53
4.4.1 The proof of LE mechanism………………54
4.4.2 The proof of FTLE………………………55
4.5 Complexity…………………………………………………59
5 Conclusion and Future work……………………………………61
5.1 Conclusion…………………………………………………61
5.2 Future works…………………………………………………64
Reference

[1] A. Acharya and B. R. Badrinath, "Checkpointing Distributed Applications on Mobile Computers," the 3rd Intl. Conf . on Parallel and Distributed Information Systems, September 1994
[2] M. Aguilera, C. Gallet, H. Fauconnier, S. Toueg Stable leader election. In LNCS 2180, p. 108 ff.
[3] E. R. Anton and Duarte, "Group Key Establishment in Wireless Ad Hoc Networks," In Workshop on em Qualidade de Servicoe Mobilidade, O. C. M. B., 2002.
[4] O. Babaoglu and R. Drummond, “Street of Byzantium: Network Architectures for Fast Reliable Broadcasts,” IEEE Trans. Software Eng., vol. 11, no. 6, pp. 546-554, June 1985.
[5] R. Baldoni, J. M. Helary, A. Mostefaoui, and M. Raynal, "Consistent Checkpointing in Message Passing Distributed Systems," IRISA Tech. Rep. RR-2564, IRISA, July 1995.
[6] A. Bar-Noy, D. Dolev, C. Dwork, and R. Strong, "Shifting Gears: Changing Algorithms on the Fly to Expedite Byzantine Agree¬ment," Proc. Symp. Principle of Distributed Computing, pp. 42-51, 1987.
[7] Miguel Castro, Barbara Liskov, "Practical Byzantine Fault Tolerance", Proceedings of the Third Symposium on Operating Systems Design and Implementation, New Orleans, USA, February 1999
[8] J. C. Cha and J. H. Cheon. "An Identity-Based Signature from Gap Diffie-Hellman Groups." In International Workshop on Practice and Theory in Public Key Cryptography, January 2003.
[9] Chunhsiang Cheng, Srikanta P. R. Kumar. "A Loop-Free Spanning-Tree protocol in Dynamic Topology. Proc. 27th Annual Allerton Conference on Communication", Control and Computing, Sept. 1989, pp. 594-595.
[10] M.S. Corson, A. Ephremides, A distributed routing algorithm for mobile wireless networks, Wireless Networks 1 (1995).
[11] M.S. Corson, S. Batsell and J. Macker, Architectural considerations for mobile mesh networking, working draft, May 1996, available at http://tonnant.itd.nrl.navy.mill"netl"netRFC.txt.
[12] N. Deo, GRAPH THEORY with Applications to Engineerring and Computer Science. Englewood Cliffs, N.J.: Prentice Hall, 1974.
[13] D. Dolev, "The Byzantine Generals Strike Again," J. Algorithms, vol. 3, no.1, pp. 14-30, 1982.
[14] D. Dolev and H.R. Strong, "Authenticated Algorithms for Byzantine Agreement,"SIAM J. Comput. Vol. 12, No. 4, pp. 191-204, 1985.
[15] D. Dolev, N. Lynch, S. Pinter, E. Stark, and W. Weihl, "Reaching Approximate Agreement in the Presence of Faults," J. ACM, vol. 33, no. 3, pp. 499-516, July 1986.
[16] E. Gafni and D. Bertsekas, Distributed algorithms for generating loop-free routes in networks with frequently changing topology, IEEE Trans. Commun. (January 1981).
[17] Kostas P. Hatzis, George P. Pentaris, aul G. Spirakis, Vasilis T. Tampakas and Richard B. Tan. Fundamental Control Algorithms in Mobile Networks. Proc. 11th Annual ACM Symposium on Parallel Algorithms and Architectures, pages 251-260, 1999.
[18] A. Khalili, J. Katz, W.A. Arbaugh, "Toward secure key distribution in truly ad-hoc networks," Applications and the Internet Workshops, 2003. Proceedings. 2003 Symposium on 27-31 Jan. 2003 Page(s):342 - 346
[19] L. Lamport, R. Shostak, and M. Pease, "The Byzantine Generals Problem," ACM Trans. Programming Language Systems, vol. 4, no. 3, pp. 382-401, July 1982.
[20] Nancy A. Lynch, "Distributed Algorithms"Algorithms”, Morgan Kaufmann Publishers,
Inc, 1997.
[21] N. Malpani, J. Welch and N. Vaidya. Leader Election Algorithms for Mobile Ad Hoc Networks. In Fourth International Workshop on DiscreteAlgorithms and Methods for Mobile Computing and Communications,Boston, MA, August 2000.
[22] F.J. Meyer and D.K. Pradhan, "Consensus with Dual Failure Modes," IEEE Trans. Paralledl and Distributed Systems, vol. 2, no.2, pp. 214-222, Apr. 1991.
[23] Vicent D. Park and M. Scott Corson. A Hightly Adaptive Distributed Routing Algorithm for Mobile Wireless Networks. Proc. IEEE INFOCOM, April 7-11, 1997.
[24] N. Suri, M.M. Hugue, and C.J. Walter, "Synchronization Issues in Real-Time Systems," Proc. IEEE, vol. 82, no. 1, pp. 41-53, Jan. 1994.
[25] Vincent D. Park and M. Scott Corson. "A Highly Adaptive Distributed Routing Algorithm for Mobile Wireless Networks," IEEE Trans. Commun. 1997
[26] Elizabeth M. Royer and Charles E. Perkins. "Multicast Operations of the Ad-hoc On-demand Distance Vector Routing Protocol." Proc. Fifth Annual AM/IEEE International conference on Mobile Computing and networking (MOBICOM), pages 207-218, August 15-20, 1999.
[27] Elizabeth M. Royer, Samir R. Das and Charles E. Perkins. "Ad Hoc On-Demand Distance Vector (AODV) Routing (Internet-Draft)." Mobile Ad Hoc Network (MANET) Working Group, 10 March, 2000.
[28] H. S. Siu, Y. H. Chin and W. P. Yang, "A Note on Consensus on Dual Failure Modes," IEEE Transaction on Parallel and Distributed System, Vol. 7, No. 3, pp. 225-230, 1996.
[29] H. S. Siu, Y. H. Chin and W. P. Yang, "Byzantine Agreement in the Presence of Mixed Faults on Processors and Links," IEEE Trans. Parallel and Distributed Systems, Vol. 9, No. 4, pp. 980-986, 1998.
[30] Maarten Van Steen, Andrew S. Tanenbaum, "Distributed Systems: Principles and Paradigms," 2002.
[31] Andrew S. Tanenbaum, Maarten van Steen, "Distributed systems Principles and paradigms," Pearson Education, p.361-367, 2002.
[32] G. Taubenfeld. Leader Election in presence of n-1 initial failures. In Information Processing Letters, vol.33, no.1, pages 25-28, October 1989.
[33] J. Turek and D. Shasha, "The Many Faces of Consensus in Dis¬tributed Systems," Computer, vol. 25, no. 6, pp. 8-17, June 1992.
[34] S.C. Wang, K.Q. Yan, and H.C. Hsieh, "The Byzantine Agreement under Mobile Network," in the Proceeding of 2004 IEEE International Conference on Networking, Sensing and Control (ICNCS2004), March 2004, pp. 46-51.
[35] John Wiley and Sons, "Blueprints for Hight Availability - Designing Resilient Distributed System".
[36] Stallins William, "Cryptography and Network Security: Principles and Practice Second Edition".
[37] S. Vasudevan, J. Kurose and D. Towsley. Design and Analysis of a Leader Election Algorithm for Mobile, Ad Hoc Networks. UMassCMPSCI Technical Report 03-20.
[38] S. Vasudevan, J. Kurose, D. Towsley, "Design and analysis of a leader election algorithm for mobile ad hoc networks," Network Protocols, 2004. ICNP 2004. Proceedings of the 12th IEEE International Conference on 2004 Page(s):350 – 360.
[39] L. Zhou and Z. Haas, "Securing Ad Hoc Networks," IEEE Network Magazine, 13(6), November/December 1999.