## 3 The Proposed Routing Mechanism
### Functions and Parameters  
_Definition 1: Contact Probability_: The Contact Probability describes that how likely it is for two nodes to communicate in a time slot. Node \(i\) maintains an entry of contact probability \(\varepsilon_{ij}\) for node \(j\), which is updated in each time slot according to the formula (1) as follows. That is to say, if node \(i\) meets node \(j\) in a time slot, \(\varepsilon_{ij}\) will be updated as \((1-\alpha)[\varepsilon_{ij}]+\alpha\). Otherwise, it will be updated as \((1-\alpha)[\varepsilon_{ij}]\). When two nodes meet at the first time, there will be an initial value of the contact probability for these two nodes. The term \(\alpha\) is a constant value which will be evaluated according to different scenarios:  
\[\varepsilon_{ij}=\left\{\begin{array}{l}(1-\alpha)[\varepsilon_{ij}]+\alpha \;i\;meets\;j\\ (1-\alpha)[\varepsilon_{ij}]\;otherwise\end{array}\right. \tag{1}\]  
Figure 1: Mobility Model.  
Figure 2: Change of the State of a Node.  
Obviously, when nodes meet frequently, the probability will increase over time. Otherwise, it will become lower. In this way, we can predict the probability of future contact for different nodes, which provides the basis for the message forwarding.  
_Definition 2. Node's Stability_: The Node's Stability describes how likely it is a node will meet any other nodes in the same cluster. A node with a higher stability will have a higher chance to meet any other nodes in the same cluster and then to forward a message. The stability of node \(i\) is the minimum contact probability between node \(i\) and the other nodes in \(C_{i}\), which is denoted \(S_{i}\) and is calculated as follows:  
\[S_{i}=min\{\varepsilon_{ik}|k\epsilon C_{i}\} \tag{2}\]  
_Definition 3. Nodes' Synchronization_: If node \(i\) and node \(j\) need synchronization, node \(i\) sends node \(j\) a list of its cluster members. Upon receiving the list, node \(j\) divides it into two subsets according to the contact time:  
\[\psi_{1}=\{k\big{|}T_{i}^{k}>T_{j}^{k},k\in M_{i},k\
ot\in M_{j}\} \tag{3}\]  
\[\psi_{2}=\{k\big{|}T_{i}^{k}\leq T_{j}^{k},k\in M_{i},k\
ot\in M_{j}\} \tag{4}\]  
where, \(\psi_{1}\) is a set including a list of nodes in which node \(i\) has the latest update that is not known by node \(j\). Similarly, in \(\psi_{2}\), node \(j\) has the latest update which is not known by node \(i\). As a result, node \(j\) updates the list of the members in \(M_{j}\) by adding the node in \(\psi_{1}\). Meanwhile, node \(j\) sends \(\psi_{2}\) to node \(i\), which updates the list of the members in \(M_{i}\) by removing the node in \(\psi_{2}\). Next, node \(j\) sends node \(i\) the list of its cluster members for a similar process.  
_Definition 4. Node's Centrality_: The centrality of node \(i\) is the number of different clusters that the node \(i\) meets per unit time. Node \(i\)'s centrality, denoted as \(CT_{i}\).  
_Definition 5. Random Linear Network Coding_: Suppose the source node generates \(n\) messages \(p_{1},p_{2},...p_{n}\) with the same destination. By using the coding method, \(c_{x}(1\leq x\leq m)=\sum_{k=1}^{n}e_{k}^{x}p_{k}\), we can obtain \(m\) (\(m\)\(>\)\(n\)) coded messages \(c_{1},c_{2},...c_{m}\). To be noted that \(e_{k}^{x}(1\leq x\leq m,1\leq k\leq n)\) is randomly generated from a finite field and each arithmetic is carried out in the finite field. And then each coded message \(c_{x}(1\leq x\leq m)\) will be forwarded with the vector \([e_{1}^{x},e_{2}^{x},...e_{n}^{x}]\). When the destination receives \(n\) coded messages \(c_{1},c_{2},...c_{n}\), which are linearly independent, it can decode the original messages \(p_{1},p_{2},...p_{n}\).