# Predicting Topology Propagation Messages in Mobile Ad Hoc Networks: The Value of History
## 3 History-Based Prediction Approach
### Dynamics of the Prediction Process  
In order to illustrate the dynamic of the prediction process, let us consider the example shown in Figure 2 that involves two mobile and one stationary node. The direction in which the nodes are moving is represented with an arrow, and their communication threshold is indicated with a dashed circle.  
The networking scenario depicted in Figure 1(a) indicates that communication between Nodes 1 and 2 is possible since their communication thresholds are overlapped; therefore, Node 1 can exchange TP messages with Node 2; however, they cannot exchange messages with Node 3. Then, such networking scenario evolves toward the topology depicted in Figure 1(b), where Node 1 can communicate with both Nodes 2 and 3. Finally, in the last scenario (Figure 1(c)) the communication is possible between Nodes 1 and 3, but Node 2 is out of reach.  
Each TP message has partial information about the current network topology, e.g., each node exchanges the list of neighbour nodes located to one-hop of distance. These messages are delivered with a certain frequency to communicate changes of the network structure. For instance, Node 1 in Figure 1(a) will send the following TP message while the network keeps such a topology: \(NodeList_{Node1}=[2]\). In the scenario shown in Figure 1(b) the messages will be: \(NodeList_{Node1}=[2,3]\). A possible sequence of TP messages for Node 1 starting in scenario 1(a) and finishing in 1(c) is the following: \([2]\)\([2]\)\([2]\)\([2]\)\([2,3]\)\([2,3]\)\([2,3]\)\([2,3]\)\([3]\)\([3]\)\([3]\).  
Figure 2: Example of a mobile scenario that involves three nodes, (**a**) First position, where nodes 1 and 2 can communicate, (**b**) Next position, where the 3 nodes can communicate, (**c**) Last position of nodes, where nodes 1 and 3 can communicate.  
The prediction process is conducted every time that a TP message should be delivered by a node, and it considers as input the mobility patterns of the neighbours of such a node. Each mobility pattern corresponds to a sequence of TP messages (one or more) that the node making the prediction has seen in the past and registered in its local table; therefore, the pattern can be identified analysing the local history table of that node. The history table also records supporting information that helps predict the next TP message when a mobility pattern is detected by a node. This information includes both, the most frequent TP message delivered after a certain mobility pattern was observed, and also the TP message delivered the last time that a particular pattern was identified. Summarizing, an entry of the history table will be composed by the following items:  
* A mobility pattern represented by one or more TP messages;
* The potential next TP messages to be delivered (or predicted), which are represented by the list of TP messages that appeared after each particular mobility pattern;
* The supporting information that helps predict the output, i.e., the next TP message.  
Table 1 shows an example of the history table of Node 1 considering the previous example. It assumes patterns with two consecutive TP messages, which are shown in the first column of the table. The second column indicates all TP messages that have appeared after the pattern, and the third column records the number of times that these TP messages have appeared in the past. Finally, the fourth column indicates if the TP message has been the last one observed after the pattern identification.  
Using this information we can define several strategies to predict the next TP message. Particularly, in this study we analyse the prediction performance of three different versions of the history-based prediction approach (HBP), which emphasizes the _last-value_ (last column of the table), _most-frequent value_ (third column) and _random value_ (it uses a randomly selected message).