臺灣博碩士論文加值系統

未來無線行動特殊網路支援群播系統的應用越來越重要。鑑於此，設計一個好的群播系統的演算法是很迫切由於節點的加入或離開不會破壞群播系統的建構。而無線行動特殊網路屬於無線電傳輸模式，在無線行動特殊網路上的每一個節點都可以自由任意行動。所以無線行動特殊網路比傳統固定式網路遭遇更多的問題，如頻寬的缺乏、連結的失敗等都可能使群播系統的效能降低。目前的群播系統擇路演算法並未有較好的效能在無線行動特殊網路的應用，尤其當移動性高的節點。因此，在這篇論文中我們深入探討這個問題並提出一個用於行動特殊網路中群播系統應用之權重式叢集路徑選擇演算法，簡稱WCMP路徑選擇演算法。此演算法透過權重計算機制選擇適當的叢集管理者去管理叢集成員。我們的方法分成兩個階段維護群播系統的傳送樹和動態的隨選叢集管理者。第一階段為被動期，用來當要尋找叢集管理者時才發出請求，此階段可以降低因請求及回應所產生的控制訊息而影響系統效能；第二階段為主動期，用來維護傳送樹的再重建及權重計算選擇叢集管者當節點的加入或離開，此階段可以快速反應網路拓樸的情況進而加以管理。透過模擬的分析顯示我們提出的樹狀式架構的演算法WCMP比網狀式架構演算法ODMRP好，這樣的結果在高移動性的環境下特別明顯。

The future wireless networks are expected to support multicast applications more and more. To facilitate this, multicast routing protocols are pivotal in enabling new receivers to join a multicast group. However, mobile ad hoc networks use radio propagation model. Each mobile node can freely move around in an ad hoc wireless network. It faces more serious problems than static network in multicast application such as link failures and scarce bandwidth. The current routing protocols do not have good performance between source and group members when source sending multicast datagrams to receivers. When the mobile nodes change their position, there is a change in the wireless network resources that can give rise to uncertainty in network conditions. In ad hoc wireless networks, the high mobility of hosts is usually a major reason for sending packets to all of members. For this reason, we propose a tree-based multicast protocol named, weight-based clustering multicast routing protocol (WCMP), to select appropriate clusterheads to manage the group members. In our method, there are two stages, that is, the reactive stage and the proactive stage, to maintain the multicast delivery tree and on demand determine clusterheads. First, the reactive stage can reduce the query-reply and control messages. Secondly, the proactive stage can quickly reflect the topology in mobile ad hoc networks according to weight mechanism and multicast delivery tree maintenance. We show through simulations that WCMP outperforms a mesh-based multicast routing protocol in terms of the packet delivery ratio and control message overhead, especially in high mobility situation.

DEDICATION……………………………………………………….………………i
Acknowledgements……………………………………….……………..ii
摘要………………………………………………………..……………iii
Abstract……………………………………………………………….....iv
List of Figures……………………………………………………………v
Chapter 1 Introduction…………………………………...………………………..1
1.1 Significance of the Research………………………………...………………….1
1.2 Multicasting……………………………………………………………………..2
1.2.1 The Basic Components of Multicasting…………………………………..3
1.2.2 Multicast Routing Concepts……………………………………...……….3
1.3 Mobile Ad Hoc Networks………………………………………………………4
1.3.1 Catrgorization of the Routing of Mobile Ad Hoc Networks…………...…5
1.3.2 Multicast Protocols for Mobile Ad Hoc Networks…………….………….5
1.4 Problem Description……………………………………………………….……7
1.4.1 Concepts of Hierarchy…………………………………………………….8
1.4.2 Selection of Schemes…………………………………..…………………8
1.4.3 Our Approach………………………………………………...………….10

Chapter 2 Background Knowledge…………………...……………….……….12
2.1 Comparisons of the ZRP and The Cluster Head Technique………………...…14
2.1.1 ZRP Protocol……………………………………………………….……14
2.1.2 The Clusterhead Technique……………………………………….……..16
2.1.3 Hybrid Mechanisms……………………………………………………..17
2.2 Concepts of Flooding………………………………………………………….17
2.3 Weight Concepts………………………………………………………………18

Chapter 3 Related Work……………………………..……...……………………20
3.1 MZR: A Multicast Protocol for Mobile Ad Hoc Networks……………...…….21
3.1.1 Multicast Tree Creation…………………………………………….……23
3.1.2 Tree Refresh……………………………………………………..………25
3.1.3 Reaction to Link Breaks…………………………………………..……..25
3.1.4 Scarcity……………………………………………………………….….26
3.2 Three Heuristics for Clusterhead Selection…………………………..………..27
3.2.1 Highest-Degree Heuristic……………………….……………………….27
3.2.2 Lowest-ID Heuristic……………………………………………………..27
3.2.3 Node-Weight Heuristic………………………………………..…………28
3.3 Analysis………………………………………………………………..………28

Chapter 4 Weight-Based Clustering Multicast Routing Protocol…………30
4.1 Tree Creation……………………………………………………………...…..30
4.2 Clusterhead Selection…………………………………………………………31
4.3 Maintain the multicast Delivery Tree…………………………………………38
4.3.1 Reactive Stage………………………………………………….………..38
4.3.2 Proactive Stage…………………………………………………………..40

Chapter 5 Simulation Results………………………………………...…………47
5.1 Simulation Environment…………………………………………..…………..47
5.2 Results and Analysis………………………………………………….……….48

Chapter 6 Conclusions and Future Work……………………………….…….54
6.1 Conclusions……………………………………………………..……………..54
6.2 Future Work…………………………………………………….……………..55

Reference……………………………………………….………………………….56

[1] S. Deering, C. Partrige, and D. Waitzman, “Distance Vector Multicasting Routing Protocol,” IETF RFC 1075, Nov. 1988.
[2] J. Moy, “Multicast Routing Extensions for OSPF,” Communication of the ACM, vol. 37, no. 8, pp. 61-66, Aug. 1994.
[3] A. Ballaradie, J. Crowcroft, and P. Francis, “Core Based Tree (CBT) – An Architecture for Scalable Inter-Domain Routing Protocol,” Proc. ACM SIGCOM ’93, pp. 85-95, Oct. 1993.
[4] S. Deering, D. Estrin, D. Fairnacci, V. Jacobson, C. Liu, and L. Wei, “An Architecture for Wide-Area Multicast-Routing,” Proc, ACM SIGCOMM ’94, pp. 126-135, Oct. 1994.
[5] S. Deering. “Host Extensions for IP Multicasting,” IETF RFC 1112, Aug. 1989.
[6] C. E. Perkins and P. Bhagwat, “Highly Dynamic Destination-Sequenced Distance-Vector (DSDV) Routing for Mobile Computers,” In ACM SIGCOMM, pp. 234-244, Oct.1994.
[7] C.-C. Chiang, H.K. Wu, W. Liu, and M. Gerla, “Routing in Clustered Multihop, Mobile Wireless Networks with Fading Channel,” Proceedings of IEEE SICON ’97, pp. 197-211, April 1997.
[8] S. Murthy and J. Garcia-Lunes-Aceves. “An efficient routing protocol for wireless networks,” ACM Baltzer Mobile Networks and Applications Journal, Special Issue on Routing in Mobile Communications Networks, 1996.
[9] E. M. Royer and C. E. Perkins. “Multicast operation of the ad-hoc on-demand distance vector routing protocol,” In Proceedings of the Fifth Annual ACM/IEEE International Conference on Mobile Computing and Networking (Mobicom ‘99), Seattle, Washington, pp. 207-218, Aug. 1999
[10] D. Johnson and D. Maltz. “Dynamic source routing in ad hoc wireless networks,” In T.Imielinski and H. Korth, editors, Mobile Comuting. Kluwer Academic Publishers, 1996.
[11] V. D. Park and M. S. Corson. “A hightly adaptive distributed routing algorithm for mobile wireless networks,” In IEEE Infocom, pp. 1405-1413, Apr. 1997
[12] Bommaiah, McAulcy, Talpade, “AMRoute: Ad-hoc Multicast Routing protocol,” Aug. 1998. Internet Draft: draft-talpade-manet-amroute-00.txt. Work in progress
[13] C. Wu, Y. Tay, and C.-K. Toh, “Ad hoc Multicast Routing protocol utilizing Increasing id-numberS (AMRIS) Functional specification,” Nov. 1998. (work in progress). Acessed March 18, 2000. Available at: http://www.freenic.net/drafts/drafts-i-j/draft-ietf-manet-amris-spec-00.html.
[14] S.-J. Lee, M. Gerla, and C.-C. Chiang. “On-demand multicast routing protocol,” In Proceedings of IEEE Wireless Communications and Networking Conference 1999 (WCNC ‘99), New Orleans, Louisiana, pp. 1298-1302, Sept. 1999.
[15] J. J. Garcia-Luna-Aceves and E. L. Madruga. “The core-assisted mesh protocol,” IEEE Journal on Selected Areas in Communications, 17(8), pp. 1380-1394, Aug. 1999.
[16] P. Sinha, R. Sivakumar, and V. Bharghavan. “MCEDAR: Multicast Core-Extraction Distributed Ad hoc Routing,” In proceedings of IEEE Wireless Communication and Networking Conference 1999 (WCNC ‘99), New Orleans, Louisiana, pp. 1313-1317, Sept. 1999.
[17] Z. J. Haas and M. R. Pearlman, “The Zone Routing Protocol (ZRP) for Ad Hoc Networks,” Internet Draft, draft-itef-manet-zone-zrp-02.txt, June 1999.
[18] T. G. Harrison et al. “Mobile multicast (MoM) Protocol: Multicast Support for Mobile Hosts,” Proc. ACM MobiCom ’97, Budapest, Hungary, pp. 151-160, Sep. 1997.
[19] C. L. Williamson et al. “Performance Evaluation of the MoM Mobile Multicast Protocol,” ACM/Baltzer Mobile Networks and applications, v.3 no.2, pp. 189-201, Aug. 1998.
[20] Jiunn-Ru, and Wanjinu Liao, “Mobile Multicast with Routing Optimization for Recipient Mobility,” IEEE Journal on Transactions, vol. 47, no.1, pp. 199-206, Feb. 2001.
[21] Z. J. Haas and Marc Pearlman, “Determining the Optimal configuration for the Zone Routing Protocol,” IEEE JSAC, special issue on Ad Hoc Networks, vol. 17, no.8, pp. 1395-1414, August 1999.
[22] C. R. Lin and M. Gerla, “Adaptive Clustering for Mobile Wireless Networks,” IEEE Journal on Selected Areas in Communications, Vol. 15, No.7, pp. 1265-1275, Sep. 1997.
[23] R. Ramanathan and M. Steenstrup, “Hierarchically-organized, Multihop Mobile Wireless Networks for Quality-of-service Support,” Mobile Networks and Applications, Vol. 3, pp. 101-119, 1998.
[24] T.-C. Hou, T.-J. Tsai, “Adaptive clustering in a hierarchical ad hoc network,” ICS Proceedings of the Workshop on Computer Networks, Internet, and Multimedia, Dec, 1998.
[25] E. Pagani, and G. P. Rossi “An On-Demand Shared Tree with Hybrid State for Multicast Routing in Ad Hoc Mobile Wireless Networks,” Proceddings, 1999 Intenational Workshop, pp. 4-9, 1999.
[26] Sze-Yao Ni, Yu-Chee Tseng, Yuh-Shyan Chen, and Jang-Ping Shen, “The broadcast storm problem in a mobile ad hoc network,” Mobicom ’99, pp. 151-162.
[27] C.-C. Chiang and M. Gerla, “Routing and multicast in multihop, mobile wireless networks,” Proc. IEEE, ICUPC, pp. 546-551, ’97.
[28] S-J. Lee, W. Su, J. Hsu, M. Gerla, and R. Bagrodia, “A performance comparison study of ad hoc wireless multicast protocols,’ INFOCOM ,pp. 565-574, 2000, http://www.ieee-infocom.org/2000.
[29] S. Basagni, I. Chlamtac, and A. Farago, “A Generalized Clustering Algorithm for Peer-to-Peer Networks,” Workshop on Algorithmic Aspects of Communication (satellite workshop of ICALP), Bologna, Italy, July 1997.
[30] P. Basu, N. Khan, T.D.C. Little, “A mobility based metric for clustering in mobile ad hoc networks,” 2001 International Conference on Distributed Computing Systems Workshop, pp. 413-418, 2001.
[31] M. Chatterjee, S.K. Sas, D. Turgut, “An on-demand weighted clustering algorithm (WCA) for ad hoc networks,” GLOBECOM ’00 IEEE Global Telecommunications Conference, vol. 3, pp. 1697-1701, 2000.
[32] D. Kim, S. Ha, Y.Choi, “Cluster-based dynamic source routing protocol in wireless ad-hoc packet radio network with variable-size clusters and variable transmission ranges,” 1999 IEEE 49th Vehicular Technology Conference, vol. 3, pp. 2441-2445, 1999.
[33] C.-B. Lin and S.-F. Hwang, “An efficient routing algorithm in ad hoc networks,” Proceedings of the NCS ’99, pp. C494-C503.
[34] A.B. McDonald, T.F. Znati, “Design and performance of a distributed dynamic clustering algorithm for ad-hoc networks,” Proceedings of the 34th Annual Simulation Symposium, pp. 27-35, 2001.
[35] D.C. Su, S.F. Hwang, C.R. Dow, and Y.W. Wang, “An Efficient K-hop Clustering Routing Scheme for Ad-hoc Wireless Networks,” Accepted by Journal of the Internet Technology, 2002.
[36] V. Devarapalli, D. Sidhu, “MZR: a multicast protocol for mobile ad hoc networks,” IEEE International Conference on, vol. 3, pp. 886-891, 2001.
[37] S. Basagni, “Distributed Clustering for Ad Hoc Networks,” International Symposiun on Parallel Architectures, Algorithms and Networks, Perth, pp. 310-315, June 1999.
[38] M. Gerla and J. T.C. Tsai, “Multicluster, Mobile, Multimedia Radio Network,” Wireless Networks, pp. 255-265, 1995.
[39] A.K. Parekh, “Selecting routers in ad-hoc wireless network,” ITS, 1994.
[40] C.-H.R. Lin and M. Gerla, “A Distributed Architecture for Multimedia in Dynamic Wireless Networks,” IEEE GLOBECOM, pp. 1468-1472, 1995.
[41] C.-H.R. Lin and M. Gerla, “A Distributed Control Scheme in Multi-hop Packet Radio Networks for Voice/Data Traffic Support,” IEEE GLOBECOM, pp. 1238-1242, 1995.
[42] University of California Los Angles Computer Science Department Parallel Computing Laboratory and Wireless Adaptive Mobility Laboratory, GloMoSim: A Scalable Simulation Environment for Wireless and Wired Network Systems, http://pcl.cs.ucla.edu/projects/glomosim/