## 2 Previous and Related Works
### DTN Routing and Forwarding Algorithms  
Epidemic routing [11] is one of the earliest opportunistic routing protocols. In its basic form, a node running epidemic routing replicates the messages it needs to send to every neighbor it meets. Then, each message is replicated by those neighbors to their neighbors, until, eventually, the message reaches its destination. Epidemic routing can guarantee the delivery of all messages if enough resourcesare available. However, it can have problems with buffer and bandwidth management, as the messages can quickly exhaust the available capacity.  
Spray and Wait routing [12] is an evolution of epidemic routing. A node running Spray and Wait also replicates the messages it needs to send, but it does so in two phases. The first phase, Spray, replicates a limited number of copies using one of two schemes (Source or Binary). The second phase, Wait, just transmits the message when it encounters its destination, stopping the replication process.  
BUBBLE routing [13] is a protocol that exploits social features of the nodes communicating in a intermittently connected network. It uses labels to know to which communities or subcommunities the nodes belong to, and it also uses the centrality of the nodes to determine a ranking and take forwarding decisions.  
The most known routing protocol for DTNs is PROPHET [9]. PROPHET stands for a Probabilistic Routing Protocol using History of Encounters and Transitivity. A node running PROPHET uses a history of contacts to assign delivery probabilities to nodes it meets and also to nodes its contacts can reach (transitivity). These probabilities decay over time so nodes can predict delivery probabilities to remote nodes.  
Authors in [14] propose MPAD (Mobility Prediction-based Adaptive Data gathering protocol), a routing protocol that replicates messages and sends them to high delivery probability nodes. This protocol manages nodes' queues based on the messages' time to live, and it manages forwarding decisions based on direction movement regarding sink position. Authors assume that nodes have GPS or positioning capabilities and that nodes can determine where the sink is.  
Other social-based routing protocols for DTNs are SimBet [15] and PeopleRank [16]. These protocols use some measurements or estimations about nodes' centrality, betweenness, similarity, or social distance to rank or qualify neighboring nodes and decide whether or not to pass them the message.  
Finally, other hybrid routing protocols are RAPID [17], SMART [18], and LSF [19]. RAPID (Resource Allocation Protocol for Intentional DTN) qualifies neighboring nodes with a utility function and replicates its message to the best qualified nodes. SMART (Selectively MAking pRogress Towards delivery) creates communities of nodes called companions and replicates the messages to the destination companions and, after a time threshold, the nodes will behave like binary Spray-and-Wait. LSF (Last Seen First spraying) passes several copies of a message (sprays) to a neighboring node with a more recent contact time to the destination.  
Table 1 summarizes the classification of these previously described protocols. More routing protocols and other classifications can be found in reviews [20; 21; 22]. Our algorithm uses ideas from some of the protocols described in this section. It can be considered a hybrid protocol, since it has social, probabilistic, and replication characteristics. In the next section we will give more details about it.