# Predicting Topology Propagation Messages in Mobile Ad Hoc Networks: The Value of History
## 3 History-Based Prediction Approach
### Using Different Historical Data-Window Sizes in the Prediction Process  
This section presents an analysis that determines the effect of using different historical data-window sizes (HDWS), i.e., different amounts of historical data in the prediction process. The analysis involved HDWS of 1, 4 and 24 h. This means that the historical data used by the predictor was reset every 1 h, 4 h and 24 h respectively. The experiments were performed during 24 h. Then, we split this historical data in 6 fragments of 4 h each, and also in 24 fragments of 1 h each. The results of every individual fragment were analysed and the average values of every fragment was computed. Figure 3 plots the predictability limit (percentage of TC messages that have already appeared in the past) for the three considered HDWS (i.e., 1, 4 and 24 h), with three different mobility models for the nodes (i.e., self-similar least action walk (SLAW), RandomWalk and Nomadic), and for 10 to 40 nodes participating in the network. The predictability limits range from 50% to more than 90%, with very low variance (average variance: 0.024% and maximum variance: 0.108%). As expected, the predictability limit increases with a larger HDWS; particularly, a HDWS of 24 h achieves the highest predictability limit, and a HDWS of 1 h presents the lowest values. These results can be explained, because in a 24 h time-period, there is a higher opportunity to find TP messages that have already appeared in the past. To analyse the effect of using different HDWS more in-depth, we conducted a prediction process considering two prediction algorithms (particularly, the \"last-value\" and \"most-frequent\" approaches), with and without a confidence mechanism (particularly, with 2 bit confidence and no-confidence). The rest of the parameters assumed for the experiment were: SLAW mobility model, 10 nodes network and dynamic HBP (tree) with a maximum history-depth of 5. Figure 4 presents the results obtained. The average and maximum variance of these values are 0.038% and 0.274% respectively, which indicates a low data dispersion. According to these results, when using a last-value prediction policy (left half of Figure 4), the HDWS should be short (1 h), because larger data-windows (4 and 24 h) decrease the percentage of hits and increase the percentage of total misses. This behaviour can be explained because larger HDWS have more variability and fewer opportunities to repeat last values. On the other side, when using a most-frequent prediction policy (right half of Figure 4), the HDWS should be large (24 h) since it increases the percentage of hits. This result is coherent because in large HDWS there are more opportunities to find the sequence of TP messages that we are looking for to perform the prediction. Concerning the use a confidence method to support the predictions, the aim is to reduce the number of bad predictions (misses) due to low confidence. The results show (second and fourth quarter in Figure 4) that the percentage of hits tends to decrease in these cases. The predictions that are not performed due to lack of confidence and would be misses (purple values in Figure 4), and are much larger for the most-frequent than for the last-value approach. The use of confidence jointly with the last-value approach is counterproductive, because most predictions that are not performed would have been hits (yellow values in Figure 4). Finally, it is important to determine if it is better to increase the percentage of hits at the cost of a higher number of misses when confidence is not applied, or whether it is better to decrease the  
Figure 4: History-based prediction using a self-similar least action walk (SLAW) mobility model with 10 nodes, and last-value and most-frequent policies, with and without confidence (1 h/4 h/24 h). Figure 3: Predictability limit for different historical data-window sizes (HDWS) and node mobility patterns. percentage of misses, and also the percentage of hits, applying confidence in the prediction.