## 2 Related Work  
Various approaches have been proposed to address the data gathering problem in DTMSNs, which aim to obtain high data delivery ratio at the cost of low transmission overhead and acceptable delivery delays. In [13], the authors presented a basic and simple routing protocol called direct transmission, where data is only allowed to be delivered when sensors are in direct proximity to the sinks. For messages are only sent directly from the source sensor node to the sink node, the protocol has relatively lower communication overhead but much longer delivery delay. Moreover, since it depends on the contacts of sensor nodes and the sink node, when there are very few sink nodes or the network is very sparse, the delivery ratio might be very low  
[PERSON] and [PERSON] [14] propose an epidemic routing protocol to increase the data delivery ratio in partially connected networks. In epidemic routing scheme, two nodes exchange the data that they do not possess whenever they meet. Given unbounded bandwidth, buffer, and energy and so on, the extensive data exchanges ensure eventual message delivery at the cost of lots of redundant messages. Figure 1: Illustration of next hop election. However, the resources of bandwidth, buffer and energy are strictly limited in mobile sensor networks, which results in many messages dropped and poor performance in epidemic routing. Other examples of epidemic-based routing protocols include MaxProp [15] and PREP [16]. Although trying to mitigate the resource burden from flooding-based protocols, these two epidemic protocol variants still have very high transmission overhead, and thus may not be applicable for DTMSNs. [PERSON] and [PERSON] [17] presented a replication-based efficient data delivery called RED, which consists of two components for data delivery and message management. First, data delivery uses a history-based method like ZebraNet to calculate the delivery probabilities of sensor nodes. Second, the message management algorithm decides the optimal erasure coding parameters based on sensor's current delivery probability to improve the data delivery ratio. However, as indicated in [13], the optimization of erasure coding parameters is usually inaccurate, especially when the source is very far away from the sinks. In [18], [PERSON] and [PERSON] _et al._ also proposed a FAD protocol to increase the data delivery ratio in DTMSNs. Besides using the same delivery probability calculation method as RED, FAD further discusses how to constrain the number of data replications in the sensor network by using a fault tolerance value associated to each data message. However, that protocol still has a quite high transmission overhead. The work by [PERSON] _et al._ uses a history-based approach for routing in the ZebraNet project [19]. The routing decision here is made according to the past success rate with which each node transmits data packets to the sink nodes directly. However, the protocol may fail in delivering data messages generated by the sensor nodes that are far away from the sink nodes [20], so it is difficult for the simple scheme to reach good data delivery ratios. In [21], [PERSON] and [PERSON] propose a system called SWIM to gather biological information about whales. In SWIM, data gathering is based on the assumption that sensor nodes move randomly and every node has the same chance to meet the sink. Thus each sensor node distributes a number of copies of a data packet to other nodes so as to reach the desired data delivery probability. However, in many practical applications different nodes may have different probabilities to reach the sink, so SWIM may not work efficiently. Recently, several new routing protocols such as OPF [22], RCM [23] and EBR [24] have been proposed to achieve the desired performance. OPF assumes that all nodes have full routing information, that is, the mean inter-meeting times between all pairs of nodes.