## 3 Minimum Expected Delay Based Routing Protocol
### The Minimum Expected Delay  
In the paper, for any one node, e.g., node \(\mathrm{i}\), let \(\mathrm{MED}_{i}\) denote the expected earliest time that messages forwarded by node \(i\) can be successfully delivered to the sink node, and \(T_{i}^{M}\) be the period of validity of \(\mathrm{MED}_{i}\). Initially, \(\mathrm{MED}_{i}\) and \(T_{i}^{M}\) depend on the expected time of node \(i\) itself meeting and departing the sink node. While receiving a hello message sent by one of its neighbors, e.g., node \(\mathrm{j}\), node \(i\) can get the mobility parameters and \(\mathrm{MED}_{i}\) and \(T_{j}^{M}\) of node \(j\) from the message, and calculate the link expiration time \(T_{ij}^{E}\). Node \(i\) maintains a neighbor list in which identity, mobility parameters, \(T_{ij}^{E}\), \(\mathrm{MED}_{j}\) and \(T_{j}^{M}\) for each neighbor \(j\) are recorded, and it periodically updates the list through adding new neighbors and removing nodes whose links already expired. According to the information in the neighbor list as well as the expected time of meeting and departing the sink node, node \(i\) periodically calculates \(\mathrm{MED}_{i}\) and \(T_{i}^{M}\) and announces them to all its neighbors through hello messages. Let the current time be \(\mathrm{t}\), then for node \(i\) the process of calculating \(\mathrm{MED}_{i}\) and \(T_{i}^{M}\) is as follows:  
(1) If the node \(i\) comes within the communication range of the sink node, then \(\mathrm{MED}_{i}=\mathrm{t}\), \(T_{i}^{M}=T_{i}^{E}\). The calculation finishes. Otherwise, if node \(i\) has no any neighbor then goes to step (2), or else to step (3). (2) If \(t<T_{i}^{E}\), then \(\mathrm{MED}_{i}=T_{i}^{S},T_{i}^{M}=T_{i}^{E}\) ; or else \(\mathrm{MED}_{i}=\infty,T_{i}^{M}=0\).The calculation completes. (3) Let the neighbor set of node \(i\) be \(\sum=\left\{\Psi_{z}\mid 1\leq z\leq Z\right\},\) here \(\mathrm{Z}\) be the total number of neighbors of node \(\mathrm{i}\). Firstly \(i\) looks for whether at least a neighbor satisfying \(T_{i\
u_{z}}^{E}>t\), \(T_{\
u_{z}}^{M}>0\) in its neighbor set \(\sum\) exists. If doesn't exist, then going to step (2); otherwise, node \(i\) finds out such node(s) with the minimum MED value in all the neighbors satisfying \(T_{i\
u_{z}}^{E}>t\), \(T_{\
u_{z}}^{M}>0\). If the result is only one, then it is denoted as  
Figure 2: Illustration of computing nodes’ MED and expiration time. m; or else chooses the neighbor with the maximum value of \(\min(\,T_{v_{i}}^{M},T_{v_{i}}^{E})\) among the findings, denoted as m. If \(\,t<T_{i}^{E}\) and \(T_{i}^{S}\leq MED_{m}\,+\,t_{hop}\), then \(MED_{i}=T_{i}^{S}\), \(\,T_{i}^{M}=T_{i}^{E}\); otherwise \(MED_{i}=MED_{m}\,+\,t_{hop}\), \(\,T_{i}^{M}=\min(\,T_{m}^{M}\,,T_{i}^{E})\,-\,t_{hop}\). Here \(t_{hop}\) is a constant employed to indicate the estimated amount of time that a message is forwarded by a node to one of its neighbor(s), which includes the time required for the node to check its neighbor list and identify the next hop, and the propagation delay to transmit the message and so on. The impact of the size of \(t_{hop}\) on performance will be discussed in Section 4 in detail. Figure 2 shows the process of calculating MED and its valid period when \(\,t=0\) and \(t_{hop}=0.1\) s. Here we note that each broken line represents a link between two nodes, and the number tagged on the broken line is the expiration time of the link. There is a pair of parentheses beside each node, in which the four numbers denote the expected time of meeting and departing the sink node, as well as MED and its valid period, respectively. As shown in Figure 2, the expected time of meeting with the sink node of node 6 is the minimum among all nodes, so \(\,\mathrm{MED}_{6}=T_{6}^{S}=\)1, \(\,T_{6}^{M}=T_{6}^{E}=\)6. Through receiving hello message sent by node 6, node 4 and 7 update their MED and valid period as follows: \(\,\mathrm{MED}_{4}=1.1,\,T_{4}^{M}=1.9\); \(\,\mathrm{MED}_{7}=1.1,\,T_{7}^{M}=2.5\).