Skip to Main Content
 

Global Search Box

 
 
 
 

Files

File List


osu1131725177.pdf (2.48 MB)

ETD Abstract Container

Abstract Header

Clock synchronization and dominating set construction in ad hoc wireless networks

Zhou, Dong
http://rave.ohiolink.edu/etdc/view?acc_num=osu1131725177

Abstract Details

2005, Doctor of Philosophy, Ohio State University, Computer and Information Science.
Ad Hoc wireless networks have been gaining importance in the communication world for the past decade. Wireless network extends the access to the network by removing the restriction of physical wires. Ad hoc network further improves the network coverage and availability to places without infrastructure support. Clock synchronization and dominating set are two of the fundamental issues in the wireless ad hoc networks. They are important for the correctness and/or performance of many protocols and applications. We focus on IEEE 802.11 wireless ad hoc networks in this dissertation due to the wide deployments of 802.11 networks. The theories and practices are definitely extensible to other types of ad hoc networks. IEEE 802.11 wireless network depends heavily on the distribution of timing information to all the stations in the network. Clock synchronization is important for frequency hopping, power saving and wireless medium reservation. We review the Timing Synchronization Function (TSF) of Ad Hoc mode defined in the 802.11 standard. It is well-known that the 802.11 TSF is not scalable. We carefully analyze the root causes of the scalability problem and design new schemes to overcome the problem. Our new schemes show great improvement over the 802.11 TSF and other solutions in the fields. Our solutions have nice characteristics: scalable, accurate, bounded and adaptive to station mobility. We are able to control the maximum clock differences under 25 micro seconds and 50 micro seconds in single hop and multihop networks respectively. The performance improvement is at least 200% or more compared with the current solutions. Dominating set has been widely used in multihop ad hoc networks (MANET) by numerous routing, broadcast and collision avoidance protocols. The problem to construct a minimum sized dominating set is known to be NP-hard. We propose a protocol that is simple, distributed, inexpensive, and adaptive to station mobility. We show that our protocol can construct dominating set using 35% to 60% less nodes than other distributed dominating set protocols. We study and address two of the fundamental and difficult problems in ad hoc wireless networks. Our solutions show significant improvements over the current solutions. Our work provides solid foundations to other important problems: routing, power saving, frequency hopping, media access scheduling, and broadcast storm mitigation.
Ten-Hwang Lai (Advisor)
165 p.
Computer Science
clock synchronization; dominating set; ad hoc network; distributed algorithm; wireless network; scalability

Recommended Citations

Citations

  • Zhou, D. (2005). Clock synchronization and dominating set construction in ad hoc wireless networks [Doctoral dissertation, Ohio State University]. OhioLINK Electronic Theses and Dissertations Center. http://rave.ohiolink.edu/etdc/view?acc_num=osu1131725177

    APA Style (7th edition)

  • Zhou, Dong. Clock synchronization and dominating set construction in ad hoc wireless networks. 2005. Ohio State University, Doctoral dissertation. OhioLINK Electronic Theses and Dissertations Center, http://rave.ohiolink.edu/etdc/view?acc_num=osu1131725177.

    MLA Style (8th edition)

  • Zhou, Dong. "Clock synchronization and dominating set construction in ad hoc wireless networks." Doctoral dissertation, Ohio State University, 2005. http://rave.ohiolink.edu/etdc/view?acc_num=osu1131725177

    Chicago Manual of Style (17th edition)

osu1131725177
4,097
© 2005, all rights reserved.
This open access ETD is published by The Ohio State University and OhioLINK.
Release 3.2.12