«2.1 Time Synchronization The actual need for time synchronization within an underwater acoustic network is not always present. It can be argued that ...»
Topics Bordering the Physical Layer
2.1 Time Synchronization
The actual need for time synchronization within an underwater acoustic network is
not always present. It can be argued that given a network with an operation time of
hours or a few days, any standard equipment will have a clock drift that is negligible given most applications and network protocol stacks. Given this argument,
synchronization of clocks can be done on board, before deployment. This might be
true for some cases, even though from a practical and logistical point of view, especially when the number of nodes gets large, it gets time consuming to access all nodes individually through their electrical interface to set their clock manually.
Another option is to synchronize clocks through switching the power on simultaneously for all nodes, but this can also be impractical. Common for both approaches is that the accuracy will vary and errors might occur (human in the loop). From this point of view it would be beneﬁcial to be able to have the nodes doing time synchronization through the actual acoustic network.
The accuracy of a clock is inﬂicted by factors as temperature, supply voltage, shock  and ageing, all which an underwater network node is experiencing. The accuracy of the clock crystal is given in parts per million, ppm. Typical accuracies found in simulations for time synchronization methods are 40 ppm [1, 2], 50 ppm  and 80 ppm . For example, given a clock with an accuracy of 40 ppm this effectively means a clock skew of 40 microseconds per second. Given an operation time of a week, the resulting clock offset will be 24 s. Such a ﬁgure might also result in a need for re-synchronization after deployment.
The application of the network is important when deciding the need for synchronization. Sensor networks might be divided into basically three categories in this respect . The ﬁrst group of applications merely requires the order of events, while the second requires the time interval of each of the events, whereas third require the absolute time of the event. Same type of division might also be true if any actuators are connected to the nodes. Delivery of packets in an underwater R. Otnes et al., Underwater Acoustic Networking Techniques, SpringerBriefs in Electrical and Computer Engineering, DOI: 10.1007/978-3-642-25224-2_2, Ó The Author(s) 2012 6 2 Topics Bordering the Physical Layer Node 1 skew = δ 1 Local time Ideal clock skew = 1 Node 2 skew = δ 2 Δ1
Fig. 2.1 Clock inaccuracies in two nodes network generally has a high and non-deterministic latency, so time-stamping of sensor and actuator data with a global clock might be beneﬁcial for many applications. Applications as target tracking and positioning requires time stamping.
Also sleep scheduling for saving power will need time synchronization between nodes within a network. When it comes to the implementation of the network protocol stack, TDMA-based MAC protocol schemes beneﬁt strongly from time synchronization.
2.1.1 Clock Inaccuracy Model
To avoid frequent re-synchronization between nodes it is beneﬁcial to both estimate the clock skew and offset. The local time of any node i is related to the true global time, t by ti ðtÞ ¼ di Á t þ Di where, ti ðtÞ denotes the local time of node i at time t, di the clock skew and Di the clock offset. Figure 2.1 illustrates the clock inaccuracies for two nodes. Generally it is assumed that clocks are short term stable, which is that they do not vary while doing estimation of clock skew . This means that the clock drift can be represented with straight lines in the ﬁgure.
2.1.2 Time Synchronization Protocols
but does no consider energy consumption issues. In RF-based sensor networks it is usually considered that the propagation delay is negligible, assuming nearly instantaneous and simultaneous reception and ignoring movement of nodes during synchronization. In underwater networks we know that propagation delays are large and variable.
Minimizing overhead of signalling for time synchronization is important due to the generally low data rate in underwater acoustic networks. The re-synchronization frequency should be minimized, thus the synchronization algorithm should be able to maintain a certain accuracy without the need for frequent re-synchronization. When re-synchronization is required the system performance should not degrade substantially. Any mobile nodes in the network introduce the need for the synchronization algorithm to compensate for the movements during synchronization.
Cross layer design with time stamping at the MAC layer is suggested by the work performed on synchronization within underwater acoustic networks [1, 2].
Utilizing data from the PHY layer in the protocol also shows to be beneﬁcial .
Generally, what seems not to have been studied in detail in the literature found is how the synchronization is achieved network wide. Great amount of detail can be found on synchronization between two nodes or within a cluster, but things can get complicated when nodes start to move, extra nodes are deployed, or nodes are taken out of the network. Reference  is mentioning that a cluster needs to select its cluster head, but does not discuss it in detail. This might introduce some additional overhead for time synchronization, and is a point of further study. The degradation of time accuracy as a function of number of hops in a multi-hop network is suggested in  to degrade as the square-root of the number of hops.
This is based on the assumption that the error per hop follows a Gaussian distribution of equal standard deviation. This might be a viable ﬁrst order assumption.
The Mobi-Sync  method is one of the latest time synchronization protocols and is getting some attention for synchronization within networks with mobile nodes. What is special with this method is that it assumes that nodes are spatially correlated. That means that when one node moves, the other nodes also move in a related pattern. Even though this is the case for e.g. free ﬂoating drifters in a sea current, this generally does not hold when having gliders and AUVs in the network. The method also requires a dense network with every node having contact with at least three or more super nodes, a super node having correct time, in order to perform well. For static networks there are more energy efﬁcient methods.
220.127.116.11 Time Synchronization for High Latency (TSHL)
The protocol TSHL  was proposed to compensate for high latency in acoustic networks. The method estimates and compensates both for clock skew and offset.
This work assumes static nodes, and performance is strongly degraded when nodes are moving. It is shown in  that the method performs even worse than no 8 2 Topics Bordering the Physical Layer
synchronization when nodes move. This is due to the fact that the estimation of clock skew is inﬂicted by the movement.
This method is among the most energy efﬁcient in the literature found.
For estimation of clock skew, a beacon node is ﬁrst broadcasting a number of messages to the neighbouring nodes. Every neighbouring node is then using linear regression on the times of arrival to estimate its clock skew. After that a single two way message exchange, see the scheme in Fig. 2.2, is used for estimating the clock offset. This is done as the reference node is informing the synchronizing node about time stamp T2 and T3 in the message sent back to the synchronizing node.
The MU-Sync method  is designed for mobile networks. It assumes a cluster based network, and in contrast to the TSHL method it is the cluster head that takes responsibility for initiating and calculating the clock skew and offset for the nodes in the cluster. The cluster assumption does not exclude the method from working within a sparse network with maybe only one neighbour node to the cluster head.
The method is relying on two way message exchange for acquisition of clock skew and offset. The number of messages suggested is 25, same as for TSHL. The cluster head is then using linear regression to calculate clock skew and offset.
Finally these parameters are distributed to each node.
18.104.22.168 D-Sync Integrating the Doppler estimate of the PHY-layer for relative velocity estimates with the time stamps, preferably also at the PHY-layer, the D-Sync method  represents a novel approach for time synchronization in mobile underwater
2.1 Time Synchronization 9 acoustic networks. Similar to Mu-sync it is the beacon or cluster head that initiates and calculates the clock skew and offset relying on two way message exchange.
At the end the clock skew and offset is distributed to the synchronized node.
Reference is made to  for details of the method. There are two main sources of error in the method: the error due to Doppler measurements and the error due to the fact that Doppler measurements are not available continuously.
In a coherent transmission scheme accurate estimation of Doppler of the received signal is important to be able to equalize and decode the transmission.
So the actual Doppler measurements tend to be very accurate. The work assumes a nominal error of 0.1 m/s, but simulations with up to 0.5 m/s are performed.
The Doppler is measured at T2 and T4 in Fig. 2.2. The time between these two measurements will in a dense network with a slotted contention based MAC protocol be governed by the Hold off time (T3–T2). This time might be several tens of seconds. This leads to a potential under-sampling of the Doppler and thereby the actual movement of the node. For slower moving nodes under water such as AUVs and gliders, this might not have such a severe effect. But it can be imagined that for gateway buoys on the surface submerged nodes in the splash zone exposed to wave motion, this under-sampling will degrade the performance of the algorithm.
Anyhow, simulations show that for a given set of parameters, including a network of 10 nodes distributed within a square of 1000 m sides, the error of the time sync two hours after the synchronization is 20 ms. This maps into an error of 2 s after a week of operation after the synchronization.
There is also described a light weight protocol B-D-Sync that has the same power consumption as TSHL. The performance of this protocol introduces a degradation of 5 times compared to the full D-sync.
Time synchronization is not always needed in an underwater acoustic network, but might be required given a long deployment, applications as target tracking or TDMA based protocols. Handling and logistics of nodes might also be simpliﬁed if they can be synchronized after deployment.
There exist a few time synchronization protocols in the literature. They all estimate both clock skew and offset in order to be able to minimize the need for resynchronization. TSHL is suitable only for static networks, while Mu-Sync and D-sync are suitable for mobile networks. Even though designed for mobile networks it might be stated that even these methods would beneﬁt from avoiding movement of nodes during synchronization.
All work on the methods considers local time synchronization between two nodes or within a cluster of nodes. Further work must be done to ﬁnd optimal ways of getting network-wide synchronization in a multi-hop network.
10 2 Topics Bordering the Physical Layer
2.2 Full-Duplex Links
A full-duplex link allows communication in both directions simultaneously. Fullduplex over the same physical medium is often emulated using the methods of Time-Division Duplex (TDD) or Frequency Division Duplex (FDD). TDD is bordering Time Division Multiple Access (TDMA) in functionality where separate time slots are used for sending and receiving signals. FDD is bordering Frequency Division Multiple Access (FDMA) where separate frequency bands are used for sending and receiving signals.
Full-duplex links are common in the cabled and radio frequency domain, included in systems as ADSL (cabled), UMTS (mobile) and satellite communication systems, while half-duplex links are predominant in underwater communication systems. No commercial full duplex modems seem to be available and a limited number of experiments has been conducted [5–7].
Obtaining full-duplex in a network is affecting the complexity of the link layer as well as the physical layer: The link layer may become simpler while the physical layer will be more complex.
2.2.1 Link Layer
Many half duplex underwater acoustic network protocols use collision avoidance by reserving the channel through a request to send and clear to send (RTS/CTS) session before accessing the channel. Further, ﬂow control is often implemented using some kind of stop-and-wait ﬂow control mechanisms. Given the large propagation delay of the acoustic channel this will lead to a lot of time waiting with potential low resource use efﬁciency. Study of channel reservation and ﬂow control is done in Sects. 3.3.2 and 4.2, respectively.
If the available bandwidth is channelized and nodes are assigned unique channels within their respective two-hop neighborhoods, the need for collision avoiding coordination prior to message transmission is eliminated as each node is effectively operating over point-to-point links with its neighbors. The resulting full-duplex communications also allow for more efﬁcient ﬂow control mechanisms, such as sliding-window based methods . The large propagation delay of the channel will result in the channel to act as a virtual buffer of data waiting to be read by the receiver.
The down-side of allocating two unidirectional channels for each connection is that it may result in very low bandwidth efﬁciency, unless the trafﬁc from each node is regular and constant. However, in most data communications exchanges, the data is irregular and bursty, resulting in periods where allocated bandwidth is unused. This will again lead to potential low resource use efﬁciency.
In , this is mitigated by techniques from satellite communications capacity management: Demand Assigned Multiple Access (DAMA) controls and