## 4 ON Model  
We propose to apply Q-learning to a particular representation of the ON that we presented in [8]. In this model, a special _Opportunistic Network Model_ (_ONM_) graph is built, which represents both the encounters between network devices and the temporal evolution of the network. Each network device is represented in this model by a set of graph nodes. Each node of this set captures the network device's state at the moment of an encounter with another device. In the resulting graph, there are two classes of edges: \"copy\" edges that link nodes belonging to different devices and represent an opportunity to copy a message from one device to another during an encounter; and \"time\" edges link all the nodes that model a device through time. Figure 0(a) shows an example mobility scenario for four mobile devices, from \(A\) to \(D\). The devices follow closed trajectories and meet at the points marked with arrows at the indicated times. In this example, devices \(B\) and \(C\) meet twice, at times 15 and 45. The ONM graph that captures this scenario is shown in Figure 0(b). Solid arrows represent encounters; dotted arrows represent time passing between encounters. The colored edges show two opportunistic paths between devices \(A\) and \(C\). Although this graph can be built from a complete trace of the mobility scenario, as described in [8] (useful for analyzing recorded scenarios or synthetic traces produced by simulators), in this work, the graph is built online, by the devices themselves, during the real-life scenario execution. In this case, each device builds a local view of the whole graph in a distributed manner, with only the edges it participates in. Figure 0(c) shows this process for devices \(A\) and \(B\). Each device registers a local view of the graph as time passes and meetings occur. For example, in Figure 0(c), the new nodes created at \(t=30\) have corresponding identical pairs created in both participating devices. These duplicates will be merged if all the local views are consolidated in a single representation. The online-build model captures the history of what happened and does not contain information on the future evolution of the network. To predict the future, in this work, we capitalize on the temporal patterns of many opportunistic networks, as seen in Section 6. The pseudocode for the online graph construction is shown in Algorithm 1. ```
Data: Own device identity \(d\) Output: Local view of the Model Graph /* Types for graph definition */
1 Type Node: (Device, Time)
2 Type Edge: (Node, Node) /* Graph initialization */
3\(N\leftarrow\) new Set of Node
4\(E_{c}\leftarrow\) new Set of copy Edges
5\(E_{s}\leftarrow\) new Set of time Edges /* Create initial node */
6\(lastnode\leftarrow\) new \(Node(d,0)\)
7\(N\_\)add(\(lastnode\)) /* called when meeting other devices */
8 Function Encounter(\(neighbor\)):
9\(newnode\leftarrow\) new \(Node(d,time())\)
10\(N\_\)add(\(newnode\))
11\(remote\leftarrow\) new \(Node(neighbor,time())\)
12\(N\_\)add(\(remote\))
13\(E_{s}\)add( new \(Edge(lastnode,newnode)\) )
14\(E_{c}\)add( new \(Edge(newnode,remote)\) )
15\(lastnode\gets newnode\) // update trailing node
```  
**Algorithm 1**Distributed online ONM graph construction. An important detail is that all the nodes associated with a single device have a single _time edge_, except for the last one, which has none. Furthermore, notice that _time edges_ are added from the receiving node; this is once the edge has been \"traversed\". A path over the ONM graph represents a possible propagation trace of a message. A trajectory starting at a given node represents a new message emitted by the corresponding device at the indicated time. A message traversing a _copy edge_ represents that the message is copied between two devices. To traverse a _time edge_, a message must be stored in the device's buffer, surviving up to the destination node's time. Figure 1: Opportunistic network model construction. (**a**) Mobile devices’ trajectories.