# Predicting Topology Propagation Messages in Mobile Ad Hoc Networks: The Value of History
## 3 History-Based Prediction Approach
### Using Confidence Mechanisms in the Prediction Process  
The proposed prediction method includes a confidence mechanism to determine the likelihood of a right prediction. The purpose of this mechanism is to avoid incorrect predictions, which can skew the network topology map and decrease the reliability of the process. The confidence mechanism determines if each TP message had already been predicted in the past. If so, a counter is incremented by 1; otherwise, it is decremented by 1.  
The counter is initialized to 1, and it can take values in the range from 0 to 3. A prediction is considered to have a high confidence value (i.e., high certainty of a right prediction) if the counter is equal to or higher than 2.  
In order to determine the granularity of the historical information that is appropriate for conducting this prediction process, the HBP approach defines the _history depth_ (HD) metric. This metric can be computed as the number of TP messages that composes a mobility pattern. For instance, if we consider a table with HD = 1, the number of messages that identifies each pattern is one, and there will be one entry in the table for every TP message appeared in the past. Considering this metric,  
\begin{table}
\begin{tabular}{c c c c} \hline \hline
**Pattern** & **Next** & **Count** & **Last** \\ \hline \([2]\)\([2]\) & \([2]\) & 3 & \\ \([2]\)\([2]\) & \([2,3]\) & 1 & ✓ \\ \hline \([2]\)\([2,3]\) & \([2,3]\) & 1 & ✓ \\ \hline \([2,3]\)\([2,3]\) & \([2,3]\) & 3 & \\ \([2,3]\)\([2,3]\) & \([3]\) & 1 & ✓ \\ \hline \([2,3]\)\([3]\) & \([3]\) & 1 & ✓ \\ \hline \([3]\)\([3]\) & \([3]\) & 3 & ✓ \\ \hline \hline \end{tabular}
\end{table}
Table 1: Example of the history table for Node 1.  
it is reasonable to assume that a high HD leads to high prediction accuracy, but low prediction opportunities, because the message sequences are longer.  
Although applying a confidence mechanism based on HD can improve the prediction accuracy, the opportunities of performing appropriate predictions are fixed if we consider a fixed HD (i.e., a fixed length for the sequence that represents the patterns). Therefore, in this HBP approach we use a _prediction tree_ in which the HD is not initially fixed. In this tree the maximum HD is assumed to make a prediction. If it is not possible to make such an assumption (e.g., because there is no entry in the table or there is not enough certainty in the prediction), the HD will be decreased by 1. The predictor then attempts to make a new prediction, but using a shorter pattern. This will be repeated until the HD metric reaches 0.  
The performance of the HBP approach was analysed with and without a confidence mechanism. To understand the limits of HBP and determine how far a particular version of this approach is from the best performance, different metrics were analysed. The repetition of TP messages over time was quantified, as well as the maximum prediction accuracy of the different HBP versions. Moreover, the number of incorrect predictions (for various HD values) that could be correctly predicted were also quantified. We assume that if a certain TP message has appeared in the past at least once, it could be correctly predicted. We also analysed the representativeness of the most-frequent messages with respect to the whole set of messages received by a node over time. This helps us understand the difficulty in making right predictions and let us know how much data (historical information) must be tracked to be able to make these predictions.