# Adaptive Data Synchronization Algorithm for IoT-Oriented Low-Power Wide-Area Networks
## 4 Adaptive File Synchronization
### Adaptive Chunking Algorithm  
A fixed chunk-based synchronization mechanism does not allow sole and exclusive identification of the bytes being updated, as for the case of Figure 3b where unnecessary literal bytes are sent, thus increasing the final \(\Delta\) size. However, by analyzing the indexes corresponding to the tokens (unchanged data) and literal bytes (new information) collected in \(\Delta\), it is possible to indicatively infer the amount and position of the updates within the file. This kind of information is then exploited for the adaptation of the chunk size \(d\) so to minimize the \(\Delta\) dimension for the next file synchronization event. Specifically, we consider the file synchronization at time \(t\) resulting in a file \(\Delta_{t}\) generated by the DIoT. As described in the previous sections, \(\Delta_{t}\) is composed of both tokens and literal bytes. The basic approach of the proposed adaptive chunking is the following:  
1. Having consecutive, adjacent, chunks (Figure 3a) suggests that the chunk size \(d\) could be increased in order to reduce the number of tokens (in the limit case, two \(d\)-bytes chunks corresponding to two tokens can be replaced by a unique \(2d\)-bytes chunk expressed by a single token). 2. If the two consecutive matching chunks are not adjacent, it means that some updates are in between (Figure 3c). Therefore, \(d\) should be conveniently decreased to optimize the transmission of literal bytes, that is to reduce the redundancy. The here-described possibilities must be evaluated on \(\mathcal{P}_{t}=\{p_{1},p_{2},...,p_{m},...,p_{M}\}\), defined as the set of tokens in \(\Delta_{t}\) sorted in ascending order. Finally, the sum of the occurrences, suitably weighted, returns the new chunk size to be used for the next file synchronization event. The analysis of the sequence \(\mathcal{P}_{t}\) is conducted by considering two consecutive tokens at a time, namely \(p_{m}\) and \(p_{m-1}\), finally resulting in \(M-1\) couples. Given \(d_{t}\) as the chunk size used in the current file synchronization event, we consider the difference \(\Phi_{q}=p_{m}-p_{m-1}\), with \(q=m-1\), hence \(q=1,2,...,(m-1),...,(M-1)\). As inferred by Figure 3a, having \(\Phi_{q}=d_{t}\) reveals that the matching chunks \(p_{m-1}\) and \(p_{m}\) are adjacent, therefore leading to the conclusion at point-1 introduced above. Furthermore, if the measure of \(\Phi\) remains constant and equal to \(d_{t}\) as \(q\) grows, then it means that there are multiple adjacent chunks identifying a portion of the file that does not need to be modified. The number of adjacent chunks \(N_{ac}\) defines the size of the unmodified portion and it is used to drive the adaptive chunking as follows:  
\[d_{t+1,w}=d_{t}+\mu N_{ac} \tag{1}\]  
According to Equation (1), the chunk dimension is increased as a function of the number of detected adjacent chunks composing the \(w\)-th file section. The parameter \(\mu\) acts as a step size ruling the speed of adaptation. On the other hand, measuring \(d_{t}<\Phi_{q}\leq 2d_{t}\) (Figures 3b,c) shows that there is at least an updated byte between the chunks \(p_{m-1}\) and \(p_{m}\), resulting in point-2 of the considered possibilities. This kind of approach does not provide the exact knowledge of both the number and position of the new bytes; however, we remark that the first step of the proposed algorithm concerns only an approximate description of the update distribution along the file \(F_{DIoT}\). Therefore, in this direction, it is sufficient for us to detect the minimum number of updated bytes.