# CoDA: Collaborative Data Aggregation in Emerging Sensor Networks Using Bio-Level Voronoi Diagrams
## 4 Multi-Hop Transmission and Synchronization
### Precision Time Synchronization Model  
In distributed systems, different nodes have their own local clock. Due to the frequency of different nodes of the crystal oscillator frequency deviation, as well as temperature changes and electromagnetic interference and so on, their time clock will gradually deviats even if at a certain moment all nodes can achieve time synchronization. In the multi-hop mode, time synchronization issues need more attention in order to ensure that the data collected by different clusters can be accurately reached by the relay nodes. The precision clock synchronization protocol (PTP) is a high precision time synchronization protocol which is applied in industrial measurement and control system. In the process of network communication, its synchronization accuracy can still be controlled below the subtle level, which can effectively meet the requirements of real-time performance in distributed systems. In this paper, the basic mechanism of multi-hop time synchronization is designed based on the PTP protocol idea, and the time stamp exchange of PTP protocol in multi-hop mode is shown in Figure 4.  
Figure 4: Time stamp exchange of PTP in multi-hop mode. The horizontal axis represents the time interval, and demonstrates the process while the cluster head nodes forward data packets to a relay node in single hop or multi-hop manner. For the time synchronization in the first hop, \(CH_{k-1}\) is the slave node of \(CH_{k}\). However, the role of \(CH_{k-1}\) will become the master node for \(CH_{k-2}\), and so on. Actually, there exists a clock offset between the master and slave nodes, and time delay happens in the process of packet switching. If the slave nodes and the master node can calculate the clock offset by exchanging time stamps, the time synchronization can be achieved. The basic principle is that the slave node can calculate the clock offset \(\theta\) through the exchange message from the master node, which contains the time stamp information, then estimate the actual time of the master node and adjust the local clock. The time stamp exchange process of PTP protocol is shown in Figure 4. As can be seen from the Figure 4, \(t_{1}\) and \(t_{2}\) are the time stamps of a master node and slave node during an interaction for time synchronization respectively. \(t_{3}\) and \(t_{4}\) represent the time stamps of a master node and slave node derived from the delay request message in the following process. Considering the asymmetry of the transmission delay between the master and slave nodes, a linear equation set is established for the PTP synchronous packet switching process:  
\[\left\{ \begin{array}{l}t_{2}=t_{1}+\theta+d_{ms}\\ t_{4}=t_{3}-\theta+d_{sm}\end{array} \right. \tag{17}\]  
Then:  
\[\theta=\frac{(t_{2}-t_{1})-(t_{4}-t_{3})}{2}+\frac{d_{sm}-d_{ms}}{2} \tag{18}\]  
Similarly, time synchronization in multiple rounds can be derived from the above function. While the time synchronization happens at the round \(t\), the clock offset between the master node and slave node can be expressed as:  
\[\theta_{t}=\frac{1}{t}\sum_{i=1}^{t}\frac{[t_{2}^{(i)}-t_{1}^{(i)}]-[t_{4}^{(i )}-t_{3}^{(i)}]}{2}+\Delta d \tag{19}\]  
where \(\Delta d=\frac{d_{sm}-d_{ms}}{2}\) is a Gauss random variable with mean value of 0 and the variance of \(\sigma_{d}^{2}/2\). In the process of synchronous packet transmission, the discrete clock model is adopted to resolve the optimization problem in the case of the noise being doped [44; 45]. Then, the time deviation of Receiver-Only synchronization mode can be given as:  
\[\left\{ \begin{array}{l}\theta(t)=\theta(CH_{k},\Delta t)-\theta(CH_{k-1}, \Delta t)+\alpha[t]\tau[t]+v[\Delta t]\\ \Delta(t)=\{[\theta(CH_{k},t)-\theta(CH_{k},t-1)],[\theta(CH_{k-1},t)-\theta( CH_{k-1},t-1)]\}\end{array} \right. \tag{20}\]  
Once monitoring the SYNC message, the slave node begins to calculate the length of the synchronization beacon, count the number of synchronized packets received and the measure the transmission delay.