在隨意移動無線網路環境中，由於節點具有移動性，因此廣播為一被廣泛使用在隨意移動無線網路環境中的通訊技術，其可被運用於路徑找尋、找尋某一特定節點或是發送緊急信號給網路上所有節點。然而，最直觀的廣播技術“洪流”容易造成傳遞過多多餘封包、網路擁塞和傳送封包碰撞，我們稱之為“廣播風暴問題”。而且“洪流”也會造成過多的能量消耗。在隨意移動無線網路環境中，大多數的行動節點的能量供應是藉由裝載之電池，是故能量消耗在隨意移動無線網路環境中是非常重要的研究議題，也因為這個理由有許多的方法被提出來去解決能量消耗的問題。其中基於連通支配集(Connected Dominating Set)的廣播方法似乎是個不錯的方式，因為只有屬於連通支配集的節點才需要去轉傳廣播封包。如果網路中所有不屬於集合S的節點皆有至少一個屬於集合S的相鄰節點則我們稱這個集合S是支配集(Dominating Set)。一般而言，屬於連通支配集的行動節點由於要處理許多不同的網路繞徑流量，因此這些節點所消耗的能量會比不屬於連通支配集的節點還要多許多。是故，這些屬於連通支配集的節點可算是被過度消耗的。在其他基於連通支配集的廣播方法中，也鮮少人著重去處理隨意移動無線網路環境中的移動特性。因此即便在眾多被提出基於連通支配集的廣播方法裡，他們也許可以找到接近最小數量的連通支配集(Minimum Connected Dominating Set)，但是由於網路的移動特性反容易令被選出來的連通支配集輕易的造成斷線，也就是將整個網路切分成兩個或數個子網路。
在這篇論文裡，我們提出一個基於計算多個連通支配集的廣播方式並且有秩序的從眾多行動節點中挑選合適的連通支配集的成員，我們稱之為增廣連通支配集(Extended Connected Dominating Set)。在這個提出的方法裡，我們藉由平衡能量消耗的方式去延長行動節點及網路的存活時間。除此之外，我們也提出了兩種輪流的型態從眾多的連通支配集中選擇一組出來擔任網路中的虛擬主幹。而最重要的是，我們在提出的增廣連通支配集廣播方式中也將網路的移動特性考慮進去。
我們所提出的增廣連通支配集廣播方式的優點是我們平衡了網路中行動節點的能量消耗使得網路的有效時間被延長，我們同時也以實驗去說明證實了我們提出的方法確實可以延長網路的有效時間。

In mobile ad hoc wireless networks (MANET), due to host mobility, broadcasting of communication technology is expected to be more frequently used to a particular mobile host, to page a mobile host, and alarm all mobile hosts. A straight forward broadcasting by basic flooding / blind flooding is usually very costly and will result in substantial redundancy, contention and collision, which we refer as the “Broadcast Storm Problem”. And basic flooding / blind flooding also result in more power consumption. Power consumption is an important issue since most mobile hosts operate on battery. Most schemes have been proposed to solve the above problems. Broadcasting based on a connected dominating set is a promising scheme, that only hosts belong to the connected dominating set need to relay the broadcast packet. We call a set is dominating if the entire mobile hosts in the network are either in the set or neighbors of the mobile hosts are in the set. In general, mobile hosts in the connected dominating set consume more energy to handle various bypass traffics than other mobile hosts that outside the connected dominating set. Thus the mobile hosts in the connected dominating set are excessively consumed. In other proposed schemes based on Connected-Dominating-Set-based broadcasting, little attention has been given to the significance of the mobility. Although they can find the near minimization number of connected dominating set, but the movement of selected forwarding nodes may easily lead to the disconnection, i.e. partition the entire network into two or more components.
In this thesis we propose a novel broadcasting scheme called Extended Connected Dominating Set, which calculate multiple connected dominating sets, to prolong the life time of each mobile host and the network by balancing the power consumption in the system, that mobile hosts in the network should be alternated in being chosen to form a connected dominating set. Otherwise, we also propose two types to deal with the way to rotate the role of each connected dominating set to be the backbone of the entire network. In the proposed ECDS, we also take the mobility into consider.
The effectiveness of the proposed scheme is to balance the energy consumption among each mobile host and in extending the live time of the entire network is confirmed through simulation.

[1]S. Alagar, S. Venkatesan, and J. Cleveland, “Reliable broadcast in mobile wireless networks,” in Military Communications Conference, MILCOM Conference Record, volume 1, pp. 236-240, 1995.
[2]C. Adjih, P. Jacquet, and L. Viennot, “Computing connected dominated sets with multipoint relays,” INRIA, Technical Report 4597, October 2002.
[3]S. Basagni, I. Chlamtac, V. R. Syrotiuk, and B. A. Woodward., “A distance routing effect algorithm for mobility (DREAM),” in Proceedings of the IEEE/ACM International Conference on Mobile Computing and Networking (MOBICOM), pp. 76-84, 1998.
[4]B. N. Clark, C. J. Colbourn, and D. S. Johnson, “Unit Disk Graphs,” Discrete Mathematics, pp. 165-177, 1990.
[5]E. S. –R. Committee, “Radio Equipment and Systems: HYPERLAN type 1,” Functional specifications ETS 300-652, ETSI, June 1996.
[6]I. S. Committee, “Wireless LAN medium access control (MAC) and physical layer (PHY) specifications,” in IEEE 802.11 Standard, IEEE, New York, 1997, ISBN: 1-55937-935-9.
[7]S. Corson and J. Macker, “Mobile Ad Hoc Networking (MANET): Routing Protocol Performance Issues and Evaluation Considerations,” RFC 2501, January 1999, available: http://www.faqs.org/frcs/rfc2501.html.
[8]T. Clausen and P. Jacquet, “Optimized Link State Routing Protocol (OLSR),” RFC 3626, October 2003, available: http://www.faqs.org/rfcs/rfc3626.html.
[9]Cartigny and D. Simplot, “Border Node Retransmission Based Probabilistic Broadcast Protocols in Ad-Hoc Networks.” in Proceedings of 36th International Hawaii International Conference on System Sciences (HICSS’03), Hawaii, USA. 2003.
[10]L. M. Feeney and M. Nilsson, “Investigating the energy consumption of a wireless network interface in an ad hoc networking environment,” IEEE INFOCOM, pp. 1548-1557, 2001.
[11]K. Fall and K. Varadhan, “ The NS2 manual”, the VINT Project, Apr. 2002, available at: http://www.isi.edu/nsnam/ns/doc/ .
[12]S. Funke, A. Kesselman, U. Mayer, and M. Segal, “A Simple Improved Distributed Algorithm for Minimum CDS in Unit Disk Graphs,” ACM Transactions on Sensor Networks (TOSN), 2006.
[13]M. Garey, and D. Johnson, “Computers and Intractability: a Guide to the Theory of NP-Completeness,” W. H. Freeman, 1979.
[14]M. Gerla, and J. T.-C. Tsai, “Multicluster, mobile, multimedia radio network,” ACM-Baltzer Journal of Wireless Networks, pp. 255-265, 1995.
[15]T. W. Haynes, Hedetniemi S. T. and P. J. Slater, “Fundamentals of Domination in Graphs,” A Series of Monographs and Text books, Marcel Dekker, Inc., 1998.
[16]C. Ho et al., “Flooding for Reliable Multicast in Multi-Hop Ad Hoc Networks,” in Proceedings of the 3rd ACM International Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications. (DIALM), pp. 64-71, 1999.
[17]C. Imrich, M.Conti, and J. Liu, “Mobile Ad Hoc Networking: Imperatives and Challenges,” Ad Hoc Networks, vol. 1, pp. 13-64, July 2003.
[18]D. B. Johnson and D. A. Maltz, “Dynamic Source Routing in Ad Hoc Wireless Networks”, Mobile Computer, pp. 153-181, 1996.
[19]M. Jiang, J. Li, and Y. C. Tay, “Cluster based routing protocol (CBRP) functional specification”, Internet Draft: draft-ietf-manet-cbrp-spec-01.txt, July 1999.
[20]J. Jetcheva, Y. Hu, D. Meltz, and D. Johnson, “A simple protocol for multicast and broadcast in mobile ad hoc networks,” Internet Draft: draft-ietf-manet-simple-mbcast-01.txt, July 2001.
[21]E. D. Kaplan, “Understanding GPS,“ Principles & Applications, 1996
[22]Young-Bae Ko and Nitin H. Vaidya, “Location-Aided Routing (LAR) in Mobile Ad Hoc Netwroks”, in Proceedings of the IEEE/ACM International Conference on Mobile Computing and Networking (MOBICOM), pp. 66-75, 1998.
[23]J. S. Kim, D. J. Scott, and A. Yasinsac, “Probabilistic broadcasting based on coverage area and neighbor confirmation in mobile ad hoc networks,” in Proceedings of IEEE Globecom, Nov-Dec 2004.
[24]H. Lim and C. Kim, “Multicast tree construction and flooding in wireless ad hoc networks,” in Proceedings of 3rd ACM International Workshop on Modeling, Analysis and Simulation of Wireless and Mobile Systems, 2000.
[25]W. Lou and J. Wu, “Double-covered broadcast (DCB): A simple reliable broadcastalgorithm in manets,” in Proceedings of IEEE Infocom, 2004.
[26]IETF MANET Working Group, http://www.ietf.org/html.charters/manet-charter.html.
[27]J. P. Macker and M. S. Corson, “Mobile ad hoc networking and the IETF”, Mobile Computing and Communications Reviews, July 1998.
[28]S.-Y. Ni, Y.-C. Tseng, and J.-P. Sheu, “The Broadcast Storm Problem in a Mobile Ad Hoc Network,” in Proceedings of International Conference on Mobile Computing and Networking (MOBICOM), pp. 151-162, 1999.
[29]Charles E. Perkins, “Highly Dynamic Destination-Sequenced Distance-Vector Routing (DSDV) for Mobile Computers,” ACM Conference on Communications Architectures, Protocols and Applications, SIGCOMM’94, 1994.
[30]C. E. Perkins, and E. M. Royer, “Ad Hoc On-Demand Distance Vector Routing,” Proceeding WMCS’99, pp. 90-100, February 1999.
[31]Charles E. Perkins, “Ad Hoc Networking,” Addison Wesley, 2nd Printing, March 2004.
[32]W. Peng and X. Lu, “On the reduction of broadcast redundancy in mobile ad hoc networks,” in Proceedings of the ACM Interational Symposium on Mobile Ad Hoc Networking and Computing (MOBIHOC), pp. 129-130, 2000.
[33]A. Qayyum, L. Viennot, and A. Laouiti, “Multipoint relaying for flooding broadcast messages in mobile wireless networks,” in Proceedings of the 35th Annual Hawaii International Conference on System Sciences (HICSS’02), Hawaii, 2002.
[34]C. Rohl, H. Woesner, and A. Wolisz, “A short look on power saving mechanisms in the wireless LAN standard draft IEEE 802.11”, in Proceedings of 6th WINLAB Workshop on Third Generation Wireless Systems, 1997.
[35]IEEE Standards Departments, “IEEE draft standard-Wireless LAN”, IEEE Press, 1996.
[36]M. Sheng, J. Li, and Y. Shi,. “Relative degree adaptive flooding broadcast algorithm for ad hoc networks.” IEEE Transactions on Broadcasting, vol. 51, pp. 216-222, 2005.
[37]C. K. Toh, “Ad Hoc Mobile Wireless Networks: Protocols and Systems,” Prentice Hall, December 2001.
[38]Y.-C. Tseng, S.-Y. Ni, and E.-Y. Shih, “Adaptive Approaches to Relieving Broadcast Storms in a Wireless Multihop Mobile Ad Hoc Network,” in Proceedings of IEEE 21st International Conference on Distributed Computing Systems, pp. 481-488, 2001.
[39]Douglas B. West, “Introduction to Graph Theory,” Prentice Hall, 1996.
[40]B. Williams and T. Camp, “Comparison of broadcasting techniques for mobile ad hoc networks,” in Proceedings of the ACM International Symposium on Mobile Ad Hoc Networking and Computing (MOBIHOC), pp. 194-205, 2002.
[41]Jie Wu and H.L. Li, “On calculating connected dominating set for efficient routing in ad hoc wireless network,“ in Proceedings of the 3rd ACM International Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications. (DialM), pp. 7-14, 1999.
[42]J. Wu and F. Dai, “Broadcasting in ad hoc networks based on self-pruning,” in Proceedings of IEEE Infocom, pp.2240-2250, March 2003.
[43]Jie Wu, and Fei Dai, “A Generic Distributed Broadcast Scheme in Ad Hoc Wireless Networks,” IEEE Transactions on Computers, vol.53, pp.1343-1354, October 2004.
[44]J. Wu and W. Lou, ” Extended Multipoint Relays to Determine Connected Dominating Sets in MANETs,“ Computers IEEE Transactions, vol. 55, pp. 334-347, Mar 2006.
[45]L. Yang et al., “Common Wireless Ad Hoc Network Usage Scenarios,” Internet Draft, October 2003, available at: http://www.flarion.com/ans-research/Drafts/draft-irtf-yang-ans-scenarios-oo.txt.
[46]H. Zhang and Z. P. Jiang, “Performance analysis of broadcasting schemes in mobile ad hoc networks,” IEEE Communications Letters, vol.8, no.12, pp.718- 720, 2004.
[47]Chunhui Zhu, M. Lee, and T. Saadawi, “A Border-aware Broadcast Scheme for Wireless Ad Hoc Network,” IEEE Consumer Communications & Networking, Las Vegas, January 2004.