## 1 Introduction  
To deal with data gathering in mobile and extreme environments lacking continuous connectivity, Delay Tolerant Mobile Sensor Networks (DTMSNs) [1-5] have been proposed in recent years. DTMSNs belongs to the general category of Delay Tolerant Networks (DTNs) [6-12], occasionally connected networks that may suffer from frequent partitions. Although with similar hardware components, DTMSNs distinguish themselves from conventional sensor networks by some unique characteristics such as nodal mobility, intermittent connectivity, delay tolerability, limited battery supply and buffer and so on. A typical DTMSN consists of two types of nodes: the mobile sensor nodes and the sink nodes. The former, which can intermittently connect with each other, are attached to mobile objects for data gathering, and the latter are either placed at special locations or taken by some of mobile objects to collect data from sensors and forward them to the end user. Obviously, it is difficult to form well connected end-to-end paths for mobile sensor nodes to transmit data to the sink nodes in DTMSNs, due to the sparse network density, short range radio and sensor node mobility, e.g., in scenarios like wildlife tracking for biological research, air quality monitoring, or flu virus tracking. Traditional data gathering approaches, which usually rely on a large number of densely deployed sensor nodes with short range radio to form a well connected end-to-end network, and collect the target data and transmit them to the sink nodes by collaborating together, cannot work effectively in DTMSNs. Therefore, how to develop efficient routing protocols, which can achieve high data delivery ratios with low transmission overhead and acceptable delay for DTMSNs, becomes the key issue. Many existing works [13-18] cannot adapt to the characteristics of DTMSNs well. For example, due to too low data deliver ratios in direct transmission [13] and the tremendous amount of energy expense in epidemic algorithms [14], both basic routing schemes do not work efficiently in practical applications. Although mitigating the resource burden, MaxProp [15] and PREP [16], two variants of the epidemic protocol, still have very high transmission overhead. Later, RED [17] and FAD [18] consider the characteristics of DTMSN and make routing decisions based on historic records. They achieve better routing performance compared with other works, but the routing decision methods only depend on nodes' utilities in one-hop scope, which overemphasizes the isolation and segmentation of networks, but don't take the usual and local multiple-hop connected feature dynamically formed by moving nodes into account. Thus RED and FAD still have some drawbacks in routing performance. For example, as shown in Figure 1, node 6 has two neighbors: nodes 3 and 7. According to the routing scheme based on the utility in RED or FAD, node 6 has to forward data messages to the nodes with higher delivery probability when it needs to send data messages to the sink node. For the delivery probability of node 6 is the highest among all its neighbors, therefore it cannot find the proper next hop to forward data, but there is evidently a multiple-hop connected path 6\(\rightarrow\) 3\(\rightarrow\) 5\(\rightarrow\) 8\(\rightarrow\) sink on which node 6 could deliver data messages to the sink node. Here we note that in Figure 1, each dashed circle denotes the communication range of the node which is at the centre of the circle. Each broken line represents a link between two nodes. The number beside each node denotes the identity of the node, and the one in parentheses is used to indicate the delivery probability. The arrow on each node indicates the moving direction of the node. As a result, we propose a new routing protocol called MEDR, which can efficiently find out and utilize temporary and local multiple-hop connected paths which are dynamically formed by moving nodes to improve the performance of data gathering.