# A Novel Opportunistic Network Routing Method on Campus Based on the Improved Markov Model
## 3 Materials and Methods
### Markov-Based Next Destination Prediction
In addition, \(X(t)\) satisfies the following conditions:  
* For a sufficiently small \(\Delta t\); \[P_{1}(t,t+\Delta t)=P\{X(t,t+\Delta t)=1\}=\lambda\Delta t+o(\Delta t)\] where the constant \(\lambda\) is called the intensity of process \(X(t)\), and \(o(\Delta t)\) is the high-order infinitesimal about \(\Delta t\) when \(\Delta t\to 0\). * Furthermore; \[\sum P_{j}(t,t+\Delta t)=\sum P\{X(t,t+\Delta t)=j\}=o(\Delta t)\] That is, for a sufficiently small \(\Delta t\), the probability of meeting twice or more in \((t,t+\Delta t]\) period can be ignored compared with the probability of meeting once. * \(X(0)=0\). For this process, it can be seen that \(\sum_{j=0}^{\infty}P_{j}(t,t+\Delta t)=1\), and combined with (2) and (3) we have:  
\[P_{0}(t,t+\Delta t)=1-P_{1}(t,t+\Delta t)-\sum P_{j}(t,t+\Delta t)=1-\lambda \Delta t+o(\Delta t)\]  
Conclusion 1: \(p_{ij}^{n_{k}}(t,t+s)\) denotes the transfer probability function of the above Markov process, i.e., the probability can also be written as \(p_{\rm ij}^{n_{k}}(s)\) that the number of times the nth node chooses location \(k\) as its destination from 0 to t period is \(i\), and the number of times it chooses location k after s time is \(j\), where s \(>0\). From conclusion 1, it follows that:  
\[\sum_{j}p_{ij}^{n_{k}}(s)=1,\ i=1,2,\ldots \tag{1}\]  
And stipulates that:  
\[p_{ij}(0)=\delta_{ij}= \begin{cases}1,i=j\\ 0,i\
eq j\end{cases}  \tag{2}\]  
Conclusion 2: \(q_{ij}^{n_{k}}\) denotes the rate function of the above Markov process and describes the rate of change of the transfer probability function \(p_{ij}^{n_{k}}(s)\) at the zero moments. From conclusion 2 it follows that:  
\[\lim_{t\to 0+}\frac{p_{ij}(t)-\delta_{ij}}{t}=q_{ij},i,j=0,1,2\ldots N \tag{3}\]  
According to the definition of the derivative, we can get:  
\[\frac{dp_{0j}(t)}{dt}=\lambda p_{0j-1}(t)-\lambda p_{0j}(t),j=1,2,\ldots \tag{4}\]  
\[ \begin{array}{ll}P\{X(s+t)&=j|X(s)=i\}\\ &=\frac{P\{X(s)=i,X(s+t)=j\}}{P\{X(s)=i\}}\\ &=\frac{P\{X(s)=i,X(s+t)-X(s)=j-i\}}{P\{X(s)=i\}}\\ &=\frac{P\{X(s)=i\}P\{X(s)+t\}-X(s)=j-i\}{P\{X(s)=i\}}\\ &=P\{X(s+t)-X(s)=j-i\}\end{array}  \tag{5}\]  
By assumption (1), the transfer probability function is independent of \(s\). Therefore, \(X(t)\) is a time-Ziemarkov process. Calculate \(q_{ij}\) based on Conclusion 1 and Conclusion 2:  
\[ \begin{array}{rl}p_{ij}(\Delta t)&=P\{X(t+\Delta t)=j|X(t)=i\}\\ &=P\{X(t+\Delta t)=j,X(t)=i|X(t)=i\}\\ &=P\{\text{the number of times the location is selected as}\\ &\quad\text{the next destination in }(t,t+\Delta t]\text{ period is }j\ -\ i|X(t)=i\}\\ &=P\{\text{the number of times the location is selected as}\\ &\quad\text{the next destination in }(t,t+\Delta t]\text{ period is }j\ -\ i\}\\ &\quad\lambda\Delta t+o(\Delta t),j=i+1\\ &=\left\{\begin{array}{c}1-\lambda\Delta t+o(\Delta t),j=i\\ o(\Delta t),j>i+1\\ 0,j<i\end{array}\right.\\ \end{array}  \tag{6}\]  
From conclusion 2, it follows that  
\[q_{ij}=\lim_{\Delta t\to 0+}\frac{p_{ij}(\Delta t)-\delta_{ij}}{\Delta t}= \left\{ \begin{array}{c}\lambda,\ j=i+1\\ -\lambda,j=i\\ 0,\ j<i\ or\ j>i+1\end{array} \right. \tag{7}\]  
Substituting into conclusion 1 and taking \(i\) = 0, we get  
\[\{\frac{dp_{0j}(t)}{dt}=\lambda p_{0j-1}(t)-\lambda p_{0j}(t),j=1,2,\ldots \tag{8}\]  
The solution of this system of equations satisfying the initial condition \(p_{0j}(0)=\delta_{ij}\) is:  
\[p_{0j}(t)=\frac{(\lambda t)^{j}}{j!}e^{-\lambda t} \tag{9}\]  
The final solution of this equation satisfying the initial condition \(p_{i\bar{j}}(0)=\delta_{\bar{j}}\) can be found as:  
\[p_{i\bar{j}}(t)=\frac{(\lambda t)^{j-i}}{(j-i)!}e^{-\lambda t},j=i,i+1,i+2,\ldots \tag{10}\]  
Find \(\lambda\) based on \(p\text{i}\bar{j}(t)\):  
\[ \begin{array}{rl}E(X(t))&=\sum\limits_{n=0}^{\infty}{(j-i)\frac{(\lambda t) ^{j-i}}{(j-i)!}e^{-\lambda t}}\\ &=(\lambda t)e^{-\lambda t}\sum\limits_{n=0}^{\infty}{\frac{(\lambda t)^{j-i }}{(j-i-1)!}}\\ &=(\lambda t)e^{-\lambda t}e^{-\lambda t}\\ &=\lambda t\end{array}