廣播(Broadcasting)是隨建即連網路(Mobile Ad Hoc Networks)中一項極為重要的通訊服務。廣播也是許多需求導向式繞徑協定(On-Demand Routing Protocols)尋求服務或詢問繞徑中重要的操作。由於盲目式氾濫(Blind Flooding)的方式具有簡單且可靠的達成率，因此以往常以盲目式氾濫的方式實現廣播。雖然盲目式氾濫具有簡單的特性，但盲目式氾濫在移動節點密集的網路中會造成大量重複的封包而耗用大量的網路資源。盲目式氾濫可能會造成網路中極為嚴重重複、競爭與碰撞，此一現象亦稱為廣播風暴(Broadcast storm)。為了減輕廣播風暴的問題，重播節點的數目應該被限制。
　　在此一論文中，我們提出了一種創新的叢集架構，此一架構能夠充分利用叢集架構的優點，因此我們僅需要叢集領導(Clusterheads)，初始節點(Initial Nodes)以及一部份選定的閘道節點(Gateways)來傳遞廣播的封包。我們的方式減輕了廣播風暴的問題，同時也具有許多的優點，除了廣播方式變得更有效率外，也更適用於高密度的網路或是節點移動性高的網路。實驗結果顯示，我們的方法比傳統的AODV在高密度的網路有較佳的表現，而在移動性較高的網路中也比現有的叢集架構，如最小識別碼叢集演算法或最大連結度叢集演算法，有較為傑出的表現。

　　Of all the communication services in Mobile Ad Hoc Networks, a fundamental service is broadcast. It is an important operation in service discovery and route query in many On-Demand Routing Protocols. In implementing broadcast service, blind flooding is commonly used in Mobile Ad Hoc Networks in the past for its simplicity and reliable accessibility. Though blind flooding is simple, it consumes plenty of network resources as it produces a large number of duplicate messages in a dense network. It may also lead to serious redundancy, contention and collision in Mobile Ad Hoc Networks, a problem referred to as the broadcast storm problem. To alleviate the broadcast storm problem, the number of retransmissions has to be reduced.
　　In this thesis, we propose a Neighbors Dependent Cluster Algorithm which takes the advantage of the cluster structure and which only requires clusterheads, initial nodes and selected gateways to forward the broadcast packets. Our approach alleviates the broadcast storm problem and promises many benefits, including efficient flooding, density adaptation and mobility adaptation. Simulation shows that our approach outperforms conventional AODV in the dense network, and overmatches some existing cluster schemes such as Lowest-ID and Highest-Connectivity Cluster Algorithm in respect of mobility adaptability.

[1] 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, Jul. 1997.
[2] S. Basagni, “Distributed Clustering Algorithm for Ad Hoc Networks,” Proc. Int’l Symp. Parallel Architectures, Algorithms, and Networks (I-SPAN), Jun. 1999, pp. 310-315.
[3] M. Chatterjee, S.K. Das and D. Turgut, “An On-Demand Weighted Clustering Algorithm (WCA) for Ad hoc Networks,” Proceedings of IEEE GLOBECOM 2000, San Francisco, Nov. 2000, pp. 1697-1701.
[4] M. Chatterjee, S.K. Das and D. Turgut, “WCA: A Weighted Clustering Algorithm for Mobile Ad hoc Networks”, Journal of Clustering Computing, (Special Issue on Mobile Ad hoc Networks), Vol. 5, No. 2, Apr. 2002, pp. 193-204.
[5] C. C. Chiang, H. K. Wu, W. Liu and M. Gerla, “Routing in Clustered Multihop, Mobile Wireless Networks with Fading Channel,” Proc. IEEE Singapore international Conference on Networks (SICON97), 1997, pp. 197-211.
[6] Tzu-Chiang Chiang, Po-Yi Wu and Yueh-Min Huang, “An Adapted On-Demand Cluster Routing in Multi-Hop Wireless Ad Hoc Networks,” International Conference on Systems and Signals (ICSS 2005), Kaohsiung, Taiwan, Apr. 2005.
[7] Tzu-Chiang Chiang, Po-Yi Wu and Yueh-Min Huang, “A Limited Flooding Scheme for Mobile Ad Hoc Networks,” IEEE International Conference on Wireless and Mobile Computing, Networking and Communications (WiMob 2005), Montreal, Canada, Aug. 2005. (To be published)
[8] S. Corson and J. Macker, “Mobile Ad Hoc Networking (MANET): Routing Protocol Performance Issues and Evaluation Considerations,” IETF RFC 2501, Jan. 1999.
[9] L. R. Ford and D. R. Fulkerson, “Flows in Networks,” Princeton Univ. Press, 1962.
[10] Magnus Frodigh, Per Jonasson, and Peter Larsson, “Wireless Ad Hoc Networking - The Art of Networking without a Network,” Ericsson Review, No. 4, 2000.
[11] M. Gerla and J. T.C. Tsai, “Multicluster, Mobile, Multimedia Radio Networks,” Wireless Networks vol. I, 1995, pp. 255-265.
[12] M. Gerla, T.J. Kwon and G. Pei, “On Demand Routing in Large Ad Hoc Wireless Networks with Passive Clustering” Proc. IEEE WCNC 2000, Chicago, IL, Sep. 2000.
[13] Z. J. Haas, M. R. Pearlman, and P. Samar, “The Zone Routing Protocol (ZRP) for Ad Hoc Networks,” IETF Internet draft, Jul. 2002.
[14] R. Hekmat, “Fundamental Properties of Wireless Mobile Ad-hoc Networks,” KiVI Telecommunicatieprijs, Netherlands, Mar. 2004.
[15] T. C. Hou, T. J. Tsai, “Adaptive clustering in a hierarchical ad hoc network,” Proc. Int. Computer Symp., Tainan, Taiwan, R.O.C., Dec. 1998, pp. 171–176.
[16] M. Jiang, J. Y. Li, and Y. C. Tay, “Cluster Based Routing Protocol (CBRP) functional specification,” IETF Internet draft, Aug. 1999.
[17] D. B. Johnson and D. A. Maltz, “The Dynamic Source Routing Protocol for Mobile Ad Hoc Networks (DSR),” IETF Internet draft, 19 Jul. 2004.
[18] C.R. Lin, and M. Gerla, “Adaptive Clustering for Mobile Wireless Networks,” IEEE Journal on Selected Areas in Communications, Vol. 15, No. 7, Sep. 1997, pp. 1265-1275.
[19] S. Murthy and J. J. Garcia-Luna-Aceves, “An Efficient Routing Protocol for Wireless Networks,” ACM Mobile Networks and Applications Journal, Special Issue on Routing in Mobile Communication Networks, vol. 1, no. 2, Oct. 1996, pp. 183-197.
[20] S. Y. Ni, Y. C. Tseng, Y. S. Chen, and J. P. Sheu, “The Broadcast Storm Problem in a Mobile Ad Hoc Network,” Int’l Conf on Mobile Computing and Networking (MobiCom’99), 1999, pp. 151-162.
[21] C. E. Perkins et al. “Ad hoc On-Demand Distance Vector (AODV) Routing,” RFC 3561, Jul. 2003.
[22] C. E. Perkins and P. Bhagwat, “Highly Dynamic Destination-Sequenced Distance-Vector Routing (DSDV) for Mobile Computers,” Comp. Commun. Rev., Oct. 1994, pp. 234–44.