## 2 Message Replication in OppNets for Sensed Data Collection
### Need for Message Replication Techniques  
OppNet routing protocols require knowledge about the network in order to determine suitable relay nodes during message forwarding. While knowledge can be derived from similarities in node movement patterns (e.g., MobySpace [29]) or social characteristics (e.g., PeopleRank [30], Bubble Rap [31] and dLife [32]), gateway nodes are neither mobile nor portray social characteristics. Also, the lack of adequate contextual information on gateway nodes limits the applicability of context-aware approaches (e.g., CiPRO [33]). By maintaining and updating history of encounters, encounter-based routing protocols can efficiently identify routing paths to gateway nodes [31], thereby making them more suitable for sensed data collection. With encounter-based routing, the ability of a node to contribute towards delivering a message is usually determined by computing its \"forwarding utility\" for the destination. Although different encounter-based protocols adopt different strategies for computing forwarding utilities, the concept is often the same, such that a higher value indicates higher delivery ability (e.g., PRoPHET [34] routing). Message replication on the other hand, is tasked with controlling the number of message copies introduced in the network. To explain this, consider the network illustrated in Figure 1, which consists of 11 nodes labelled \(a\) to \(k\) (note that this illustration is for explanatory purposes only and the topology, e.g., the number of nodes and their links, is not in accordance with any particular pattern). The nodes are connected by delay-tolerant links, meaning that two connected nodes are neighbours that regularly encounter each other.  
Taking node \(a\)'s forwarding utility for node \(k\) as \(U_{a}(k)\), node \(a\) forwards a copy of a message that is destined for node \(k\) to node \(b\), if \(U_{b}(k)>U_{a}(k)\). The direction of the link indicates the flow of the message towards the destination based on increasing forwarding utility values. Hence, source node \(a\) is likely to generate more copies of a message destined for node \(k\) than source node \(i\) would. In other words, source node \(i\) is likely to generate fewer copies than source node \(a\) since \(U_{i}(k)>U_{a}(k)\). For example, node \(a\) would generate 11 copies of a message destined for node \(k\) (i.e., every node in  
Figure 1: A sample opportunistic network (OppNet) consisting of 11 nodes.  
the network would have a copy), while node \(i\) would generate only 3 copies (i.e., only node \(i\), node \(j\) and node \(k\) would have copies). This shows that the forwarding utility alone is not a good indicator of the number of message copies generated in the network, and directly modifying it in this regard may reduce its ability to determine suitable relay nodes. This justifies the need for additional algorithms or mechanisms that can control the number of generated message copies without interfering with forwarding utility computation. For instance, every node, including source node \(a\), could drop the message after forwarding a copy. This would generate either 5, 6 or 4 copies, depending on the neighbour that encounters the source node first. Delivery opportunity could be increased by allowing the source node to drop the message after forwarding it twice. This case would generate either 9, 7 or 8 copies, depending on the two neighbours that the source node encounters first. We refer to such algorithms or mechanisms as \"message replication techniques\". Next, we identify OppNet characteristics that impact on the performance of message replication techniques. Then, we study existing message replication techniques and how they perform in the presence of the identified characteristics in Sections 2.3 and 2.4, respectively.