## 3 Predict and Forward Scheme Based on Node Profile
### Complexity Analysis of the Proposed Algorithm  
In conclusion, we propose an efficient routing-delivery scheme (Predict and Forward) based on node profile in opportunistic networks, and the detailed steps of the proposed algorithm are as follows.  
**Step 1**: The source node defines the message delivery function through its previous experience.  
**Step 2**: The Prelearn message starts to route from a node to another in the network, gathers and updates the statistics about the attribute characteristics of nodes, and finds the destination profile by the message delivery function defined by the source node.  
**Step 3**: When routed by the Prelearn message, the new node adopts the historical meeting information shared from the Prelearn message to predict the future encounter probabilities with others.  
**Step 4**: Based on the optimal stopping theory, Prelearn message carriers select an optimal transition moment to forward Prelearn messages to the relay nodes which have a bigger probability of a future meeting with the destination profile than the Prelearn message carriers.  
For the readability of this algorithm, we provide the pseudo-code description to introduce our proposed scheme briefly. As the pseudocode shows, the first loop represents Prelearn messages route from the source node to the \(n/e\)-th node in the Predict phase, so its time complexity is \(0(n/e)\). Additionally, the second loop of the pseudo-code indicates that the message carrier compares the probability of the future meeting between nodes and makes appropriate message delivery decisions in Forward phase, so its time complexity is \(0(nlogn)\). On the whole, the time complexity of the proposed algorithm is \(O(n/e+nlogn)=O(nlogn)\). Meanwhile, we may compare the proposed algorithm with other traditional algorithms of opportunistic networks. The time complexity in Spray and Wait algorithm is \(O(nlogn)\), while that in the Epidemic algorithm is \(O(n)\).  
Figure 4: The delivering process diagram of Forward phase.  
```
0: Prelearn message \(L(SOURCE,DATA\),\(W\)\({}_{n\times n}^{*},pf\) ), \(node_{1}.......node_{n}\), a destination node \(D\);
0: the node set \(R\), the probability prediction matrix \(W_{n\times n}^{*}\);
1: Predict phase: the Prelearn message \(L\) routes the network form \(node_{1}\) to \(node_{n/e}\)
2:for (int \(i=1;i\leq n/e;i++\)) do
3:if (\(node_{i}\). is destination profile()) then
4:\(R_{new}=R_{old}\cup node_{i}\)
5:endif
6: Collect and update the encounter information between nodes
7: Predict the future meeting probability \(P\) between \(node_{i}\) and the others
8: Add \(P\) to \(W_{n\times n}\)
9:\(W_{n\times n}^{*}=funSVD(W_{n\times n})\)
10:endfor
11: Output the node set \(R\) and the probability matrix \(W_{n\times n}^{*}\) ;
12: Forward phase: making the delivery decisions for Prelearn message \(L\)
13:for (int \(i=1;X\leq n;x++\)) do
14:if (\(node_{X}\).carry Prelearn message(\(L\))) then
15:if (\(P_{(node_{Y},node_{D})}>P_{(node_{X},node_{D})}\)) then
16:\(node_{X}\) sends the Prelearn message \(L\) to \(node_{Y}\)
17: Finally Prelearn message \(L\) will be sent to the destination profile \(node_{D}\)
18:endif
19:endif
20:endfor
```  
**Algorithm 1** Predict and Forward scheme