Network Time Synchronization and Code-based Scheduling for Wireless Ad Hoc Networks 

Carleton University, Ontario, Canada. January 2006.

This thesis addresses the study of a network time synchronization (NTS) algorithm for wireless Ad Hoc networks (WAHNs), and the design and analysis of a medium access control (MAC) paradigm referred to as code-based scheduling. We present a novel network time-synchronization algorithm referred to as Clocksampling Mutual Network Synchronization (CSMNS) that shows excellent scalability, accuracy and low implementation complexity. CSMNS is evaluated analytically and numerically in single-hop and multi-hop scenarios. The performance of CSMNS is also compared to the performance of the timing synchronization function (TSF) of the IEEE 802.11 standard of which, to the best of our knowledge we are the first to provide performance results in a multi-hop scenario. CSMNS has the ability to make the time difference among the clocks in the network converge to a common and small value by utilizing the timing information carried on beacons originated in any point of the network. CSMSN also reduces the need for constant refreshment of the timing information.

General principles of code-based scheduling are investigated and particular examples A MAC strategy we call code-based scheduling is proposed that utilizes the codewords of codes traditionally used for channel coding purposes. We use a novel approach that utilizes coding theory concepts to devise a scheduling strategy that allows for the possibility to guarantee a minimum level of performance in the nodes of a WAHN.based on Reed-Solomon and Hermitian codes are evaluated analytically and numerically in terms of their average, minimum and maximum delay and throughput performance. Additionally, a metric that can be used to identify better codes for the purpose of codebased scheduling is identified.

The average performance of a large family of code-based scheduling protocols is analytically compared to the one obtained by slotted-ALOHA. A code-selection algorithm is proposed that can improve the average throughput of code-based scheduling when the number of nodes in the network is larger than the number of code-words available. Finally a hybrid code-based contention-based scheduling protocol is discussed and evaluated, which combines the performance guarantee advantage of a code-based scheduling approach with the better average performance of contention-based scheduling protocols with feedback.