COLLOQUIUM Department of Computer Science and Engineering University of South Carolina Local Construction of Connected Dominating Sets in Wireless Ad Hoc Networks Fei Dai Department of Computer Science and Engineering Florida Atlantic University Date: February 25, 2005 Time: 3:30-4:30PM Place: Swearingen 1A03 (Faculty Lounge) Abstract Wireless ad hoc networks are infrastructure-less multi-hop networks consisting of mobile (such as in mobile ad hoc networks) or stationary (such as in wireless sensor networks) wireless devices. These networks involve several challenges, including limited bandwidth and energy resources, frequent topology changes, and lack of central control. Local acting, self-organizing, and self-healing algorithms (also called localized algorithms) are essential to the design of wireless ad hoc networks. A connected dominating set (CDS) is frequently used in wireless ad hoc networks to support energy-efficient routing, broadcasting, and area monitoring. For efficiency and robustness, the ideal CDS construction algorithm is light-weighted, has fast convergence, and minimizes the CDS size. This talk discusses localized algorithms for the fast construction of a CDS in wireless ad hoc networks, its application in efficient broadcasting, and mobility management schemes that maintain the CDS property in a highly dynamic environment. Fei Dai is a Ph.D. candidate in the Department of Computer Science and Engineering at Florida Atlantic University. His recent research has focused on localized self-organizing algorithms for wireless ad hoc networks. He has also conducted research in networking, parallel and distributed computing, artificial intelligence, and software engineering. In the past four years, he has published thirty peer-reviewed papers, including five papers in IEEE Transactions. Mr. Dai received his B.S. and M.S. degrees in Computer Science from Nanjing University, Nanjing, China. He has been a senior programmer at Greatwall Computer, China, a software architect and a team leader at J&A Securities, China, and a consultant for Motorola, Plantation, FL.