1. Field of the Invention
The present invention relates to wireless ad hoc networks, and particularly to obtaining time synchronization among member nodes in a mobile ad hoc network (MANET).
2. Discussion of the Known Art
Time synchronization is a critical requirement for wireless multi-hop mobile networks, especially tactical military networks. Such networks are typically characterized by rapidly changing topologies and high traffic loads, and present a constant challenge for traffic coordination in order to achieve efficient channel utilization. It is widely accepted that time division multiple access (TDMA) technology can improve channel access capacity over other contention-based access protocols. In TDMA systems, clear time slots and schedules are defined to ensure that member nodes transmit only during their assigned slots and that their transmissions do not overlap. Due to potential improvements in channel capacity and security requirements, TDMA channel access is widely used in military networks. Because all nodes throughout the network must operate according to a common time scale, the ability of each node to synchronize, i.e., to adjust the time at each node in order to conform with a common timing interface, is a fundamental requirement for tactical TDMA networks if collision free communications are to be maintained.
When applied to tactical MANETs, existing time synchronization protocols are limited by hardware and environmental restrictions. See, B. Kusy, et al., “Elapse Time on Arrival: A simple and versatile primitive for canonical time synchronization services”, International Journal of Ad Hoc and Ubiquitous Computing, 2(1) (2006) and B. Kusy, et al., “Tracking Mobile Nodes Using RF Doppler Shifts”, ACM Sensys Conference (2007), both of which are incorporated by reference. In addition, many existing techniques cannot satisfy all of the following requirements for tactical MANETs:
1. Scalable multiple hop networks
2. Rapid topology change from node mobility
3. Synchronization accuracy of 1 us
See also, F. Sivrikaya, et al., “Time synchronization in sensor networks: A Survey”, IEEE Network, at pages 45-50 (July/August 2004); B. Sundararaman, et al., “Clock synchronization for wireless sensor networks: a survey”, Ad Hoc Networks (Elsevier), vol. 3, no. 3, pages 281 to 323 (May 2005); M. L. Sichitiu, et al., “Simple, Accurate Time Synchronization for Wireless Sensor networks”, WCNC (2003); J. Elson, et al., “Fine-grained network time synchronization using reference broadcasts”, Proc. of 5th Symp. Operating Systems Design and Implementation (OSDI), Boston, Mass. (December 2002); and C. H. Rentel, et al., “A Mutual Network Synchronization Method for Wireless Ad Hoc and Sensor networks”, IEEE Transactions on Mobile Computing, vol. 7, no. 5, at pages 633 to 646 (May 2008), all of which are incorporated by reference.
For example, a so-called Reference Broadcast Synchronization (RBS) avoids the impact of processing delays at the transmitter side, but introduces propagation delays in clock skew and time offset estimation by about 1 us for each 300 meters. See, J. Elson, et al, “Fine-grained network time synchronization using reference broadcasts”, cited above. Thus, while RBS may work well for sensor networks, it cannot be used reliably in MANETs. Other protocols rely exclusively on deterministic algorithms that enable quantification of an upper bound on the error in clock offset estimation, but they are vulnerable to a single node failure.
Clock-Sampling Mutual Network Synchronization (CS-MNS) is a distributed algorithm that does not rely on structured networks and, thus, may avoid a single node failure. See, C. H. Rentel, et al, “Clock-sampling mutual network synchronization for mobile multi-hop wireless ad hoc networks”, cited above. In CS-MNS, each node adjusts its timing based on its neighbors' timing so that all nodes converge to a common timing. For example, assume a node n has clock hardware operating at a rate or frequency fn. The node n then uses timestamps it receives in its neighbors' messages to adjust the instant time determined by its clock hardware by a scale factor βn to achieve network time synchronization. Each node in the network then reaches such a state that βmfm=βnfn for any m≠n.
It can be seen, however, that CS-MNS may also arrive at other states in which αβmfm=αβnfn, where α≠1. Thus, if a network has a topology such as shown in FIG. 1, i.e., condensed nodes on two sides and sparse in between, it is possible for the disjoint subnets to settle into two different states, or α1≠α2. The CS-MNS protocol does not address how to resolve this problem if it occurs. In addition to the foregoing issues, many of the known algorithms address network time synchronization only in low traffic load networks, but fail to address operation in mobile and heavy loaded networks such as tactical MANETs.
For a distributed MANET, where there are no advantaged nodes that act as central controllers, time synchronization becomes even more challenging. While many of the known time synchronization protocols are scalable and efficient, they are intended for use in sensor networks and consume valuable channel resources if applied to mobile networks, leading to reduced channel efficiency. Furthermore, many of the algorithms only deal with time synchronization and while they may work well in low traffic load or sensor networks, they cannot operate properly in traffic loaded networks such as MANETs because of contention protocols and packet collisions in the latter.
Table 1, below, illustrates some of the functional and behavioral differences between tactical distributed MANETs and sensor networks, which preclude the effective use of a common time synchronization scheme for both types of networks.
TABLE 1TacticalSensorNetworksNetworksDistance0-10's km<10 metersMobility<10 m/sNoneTrafficMedium-highlowloadOperationHoursMonthstimePowerMediumhighefficiency
Distances between adjacent nodes in sensor networks are typically under 10 meters, causing not more than a 30 ns (30×10−9 sec.) propagation delay. Such a minimal delay can often be neglected when time synchronization of 1 us (1×10−6 sec.) is required. Distances between nodes in MANETs may reach tens of kilometers with about 30 us propagation delays, however. Such larger delays must therefore be considered for accurate time synchronization in MANETs.
Time synchronization is impossible without message exchanges among network nodes. For traffic loaded MANETs, this presents a challenge in scheduling the message transmissions to avoid contention and collision. The problem becomes even worse if mobility is considered. Because the typical operation time of each node in a MANET is much shorter than for nodes in sensor networks, however, power efficiency is not as critical in a MANET as it is for sensor networks.