This is the accepted version of the following article: Borrego Iglesias, Carlos; Robles Martínez, Sergi; Borrell i Viader, Joan. Efficient Broadcast in Opportunistic Networks using Optimal Stopping Theory. Ad Hoc Networks, Vol. 88 (May 2019) , p. 5-17, which has been published in final form at https://doi.org/10.1016/j. adhoc.2019.01.001. © 2019. This manuscript version is made available under the CC-BY-NC-ND 4.0 license http://creativecommons.org/licenses/by-nc-nd/4.0/ Efficient Broadcast in Opportunistic Networks using Optimal Stopping Theory Carlos Borregoa,∗, Joan Borrella , Sergi Roblesa a Department of Information and Communications Engineering Universitat Autònoma de Barcelona Bellaterra, Spain Abstract In this paper, we present a broadcast dissemination protocol for messages in opportunistic networks (OppNet) that is efficient in terms of energy consumption and network capacity usage, while not increasing the number of excluded nodes (nodes not receiving messages). The majority of the OppNet broadcast delivery schemes proposed in the literature, do not take into consideration that reducing energy and buffer usage is of paramount importance in these wireless networks normally consisting of small devices. In our protocol, broadcast messages are limited by carefully selecting their prospective forwarders (storers). The keystone of our protocol is the use of Optimal Stopping Theory, which selects the best message storers at every stage of the algorithm, while holding back broad message dissemination until convenient conditions are met. The broadcast efficiency of the proposed protocol out competes other OppNet broadcast proposals in four well-known scenarios. Furthermore, the protocol reduces the number of both dropped messages and nodes not receiving messages, thus maximising network capacity usage, and the span of the message delivery. Keywords: Opportunistic Networks, Broadcasting, Message Dissemination, Optimal Stopping Theory 1. Introduction be addressed before they can be widely deployed, such as efficient routing and delivery. When nodes need to communicate wirelessly, they can Routing and delivering of messages have been tradi- form an ad-hoc network using the links of direct neigh- tionally considered two sides of the same coin. This is, in bours to reach further nodes or can use a managed wireless part, because in connected networks, the recipients of the network (assisted by some infrastructural elements such messages and the way they have to be forwarded are closely as access points). However, sometimes nodes cannot be coupled. Examples of this are IP Multicast and IP Any- reached using these networks, due in part to node mo- cast. When it comes to opportunistic networks, the bond bility or availability reasons, and an alternative means between routing and delivery fades away. Which nodes are of communication, such as opportunistic networking, is intended to receive messages could be totally unrelated to needed. In opportunistic networks (OppNet) [14], mes- the way these messages are routed through the network. sages are sent to nodes in direct communication range, An example where this can be easily seen is broadcast: in who store and carry these messages until there is a new OppNet, although a message has to arrive at every single opportunity to forward the messages to other nodes. This node in the network (broadcast delivery), there are many provides a global communication service even when mes- ways of routing it (broadcast routing), such as flooding, sage storers only connect to other nodes temporarily. Opp- sending a limited number of copies, or carefully selecting Nets are not contenders for the fastest or most reliable the forwarding nodes –also called storers. network, but are second to none regarding delay and dis- The use of unicast delivery (messages intended to a ruption tolerance. This makes them a good candidate in particular node) in OppNet is generally set aside in favour a number of scenarios, including low cost —energy, re- of a broadcast-like delivery. This is mainly due to the very sources, money— networks such as sensor networks, or the nature of the network, in which opportunistic node gather- Internet of Things; interplanetary or submarine networks; ings make it difficult to have an efficient routing for these and networks where nodes need to maintain the privacy messages in arbitrarily large networks with discretionary of their whereabouts or the anonymity of their users. Al- node addresses. On the other hand, broadcast delivery though OppNet represent a communication solution where is widely used in OppNets, and having an efficient rout- other networks can be hardly used, there are still issues to ing strategy for these broadcast messages is essential for the implementation of useful real-world applications. One ∗ Corresponding author might think that this is a problem easy to solve. A sim- Email addresses: carlos.borrego@uab.cat (Carlos Borrego), plistic approach to broadcast in opportunistic networking joan.borrell@uab.cat (Joan Borrell), sergi.robles@uab.cat would be to have all nodes sending the broadcast message (Sergi Robles) January 7, 2019 to all nodes at sight, and perhaps keep transmitting the message storers are the only nodes allowed to perform the same message to other nodes in the future as well (so be- whole store-carry-and-forward process. This strategy re- coming a storer). The problem would be a general flooding duces the number of dropped messages and thus makes of the network, with not even the guarantee that all nodes the most of the network storage capacity, facilitating the would receive a copy. In terms of efficiency, this strat- spreading of messages throughout the network. The met- egy is therefore definitely not one of the best. There are rics used to assess favourable forwarding conditions include two important aspects that have to be considered here: betweenness egocentric centrality; least dropping probabil- the carry involved in OppNet emphasises the importance ity and most node capacity to store messages; and the least of the limitation posed by the network “capacity”, and common contacted nodes. The broadcast efficiency of the hence a constraint to be considered; and as these devices protocol out performs other OppNet broadcast proposals tend to have limited battery capacity, such as IoT sensors, when compared in four well-known scenarios, as shown in energy consumption has to be restricted, which involves the simulations carried out in Section 4. limiting the number of transmissions as much as possible. Hence, designing a coherent strategy to broadcast mes- 2. Related Work sages in OppNet is a complex task that has to take into account these constraints and ensure, at the same time, de- In this section, we study the state of the art of data livery efficiency in terms of dissemination, delivery time, broadcasting in Opportunistic Networks (OppNet). We and energy cost. pay special attention to node characterisation in these net- In the literature, some OppNet broadcast approaches works by providing a summary of the different ways of have been proposed [40, 19] but typically these are based studying node’s centrality, similarity and storer reliability. on limiting the number of message copies or their lifespan, Additionally, we present a summary of articles that use and are oblivious to the impact on network capacity in OST-based techniques to improve routing in OppNet. the overall performance, which leads to unwanted conse- quences such as uneven message dissemination or having 2.1. Message Broadcasting in Opportunistic Networks unreachable areas and excluded nodes. Opportunistic Networking [14] is a research field that In this paper, we offer a different perspective to the studies networks where end-to-end communication is not problem of message broadcasting in OppNet. We propose always guaranteed. OppNet nodes use intermediate nodes that broadcast messages should be limited but not just to route messages from their source to their destination in regarding the number of copies or their lifespan, but also an opportunistic way. by carefully select their prospective forwarders (storers). Message broadcasting in this field studies the problem Nodes that receive a message can accept it and delete it; of node communication in a many-to-many, any-to-many, store and carry the message, delivering it to other nodes and one-to-any way. Traditional routing protocols like in future encounters –which will delete the message after ProPHET [29], Bubble rap [24] or SPRINT [12] can not acceptance;– or pass it to nodes that will be selected as new be directly applied to OppNet broadcasting because these forwarders. These forwarding nodes, named storers, are proposals are defined for one-to-one (Unicast) communica- selected in terms of three different criteria: centrality –how tions. Sobin, et al. [36] present a complete survey of rout- well connected a node is in the network–, reliability –the ing and data dissemination in Opportunistic Networks. likeliness a node does not drop messages–, and similarity Regarding message broadcasting, this survey presents a –how alike a node is in terms of shared acquaintances– new taxonomy where data dissemination protocols are di- . The goal is to make the broadcast effective, even, and vided into two categories: social-based data dissemination pervasive all over the network using the minimum energy schemes and pure opportunistic ones. The social-based possible, while reducing the number of excluded nodes. schemes include publish/subscribe approaches such as the The main contribution of this paper is a broadcast dis- study by Yoneki, et al. [40], where communities are formed semination protocol for messages in an OppNet, that is by interconnecting nodes that frequently meet with each efficient with respect to message latency and message dis- other. Other non-publish/subscribe schemes, such as the semination per unit of energy. The protocol, presented work by Gao, et al. [19], propose different social metrics in Section 3, keeps low the percentage of excluded nodes and utility-based data dissemination methods. Following (nodes not receiving messages), while trying to maximize the second category presented in [36], pure opportunistic the range of message delivery. The keystone of the protocol data dissemination protocols can be either reactive, where is the use of Optimal Stopping Theory (OST), introduced the source node or nodes push data towards the destina- in Section 2, to select the best message storers in each stage tions [44], or proactive where the subscribers pull the data of the algorithm, holding back broad message dispersal un- from the nodes [21]. til convenient conditions are met. Even though the solu- There are few OppNet broadcast schemes proposals tion of finding the storers in each stage of our algorithm that have taken into account the energy consumption. In results in optimality, global optimisation (i.e. choosing the [20], the authors propose a broadcast protocol where nodes best storers possible for a message) is not pursued in this wait for an opportunity to reach multiple nodes with one proposal. The novelty of our proposal is the idea that these 2 transmission in order to reduce the number of transmis- choosing the best moment to make a particular decision to sions overall. Additionally, in [19], the authors propose maximise a certain reward or to minimise a certain cost. an efficient dissemination protocol for OppNet that uses a One of the most popular problems in OST is the sec- social centrality metric to ensure effective relay selection. retary problem [17], also known as the Classical Secretary They show, by means of simulations, that their approach Problem (CSP). In this problem, a person must interview obtains better cost-effectiveness than existing data dissem- a group of n candidates, that can be ranked from best to ination schemes. worse, with the aim of selecting the best one. The diffi- culty of this problem lies in the fact that once a candidate 2.2. Node characterisation in Opportunistic Networks is not selected, he/she cannot be recalled again. The so- In OppNet literature, different node characterisation lution to this problem, as presented in [17], is a selection metrics have been defined to help with routing decisions. strategy that discards the first n/e candidates interviewed In this article, we focus on node’s centrality, similarity and (e being the mathematical constant) and selects the first reliability. next one that is better than all of the previous ones, if In order to evaluate the importance of a node in a net- found. work, there are many centrality metrics the OppNet scien- From the CSP, more extensive Generalized Secretary tific community use. The three most important are degree, Problems (GSP) are obtained if, instead of only the best betweenness, and closeness centrality. Degree centrality possible candidate, a set of k good enough candidates have [31] measures the number of direct edges that reach a given to be chosen. These k candidates can be the k best ones, or node. Betweenness centrality [7], calculates the number of a combination which maximises a certain reward or min- shortest paths connecting other nodes that use the node imises a certain cost. In particular, Tamaki proposes in being measured as a hop. Finally, closeness centrality [30] Theorem 4 of [38] an optimal policy to find the first and studies the length of the shortest path connecting the rest the second best candidates in a GSP, and Ano proposes in of the nodes. Several studies propose to use these metrics Theorem 4 of [6] an optimal policy to find the first, second to assist with routing decision: nodes with high centrality and third best candidates in a GSP. are presumed to be good communication hubs. In the context of opportunistic wireless networks, OST Similarity or clustering has been studied in OppNet to is a very powerful tool to help with different network de- detect nodes that belong in the same community. Rout- cisions. In the field of distributed opportunistic schedul- ing decisions are made by comparing the similarity with ing [43], different proposals such as [42, 33] employ OST the destination node. Examples of these routing protocols techniques to optimally utilize wireless resources. The key include classical studies like [22] and [13]. of these studies lies in the fact that the wireless channel The ability of a node to be trusted in terms of how reli- quality changes with time and therefore, OST plays an able it is to delegate a copy of a message has been studied important role by choosing the best moment to perform from different perspectives. There is a large number of certain network decisions. An example of these is finding studies that propose different reputation-based schemes, the optimal data transmission duration time with the goal such as [41] to address the problem of nodes not forward- of minimizing energy consumption. [26] also uses OST to ing or accepting messages. These reputation schemes try achieve significant energy cost reduction in the context of to detect malicious nodes which are excluded from the epidemic information dissemination in ad hoc networks, routing process. Other proposals simply select nodes for particularly in the route discovery phase of the advanced message forwarding in terms of how reliable a node is ac- on-demand distance-vector (AODV) routing protocol. cording to network metrics such as how frequent a node Another OppNet proposal that uses OST is [8], in which drops its stored messages [35]. the authors present Softwarecast, a general delivery scheme for group communications based on mobile code. In Soft- 2.3. Optimal Stopping Theory in OppNet warecast, messages carry a software code and a delivery state that permit them to perform refined delivery-decision- In this article, we propose an efficient broadcasting pro- making methods based on OST to implement complex de- tocol for OppNet messages. The efficiency of this protocol livery decisions. is achieved by limiting the number of message storers in Moreover, in [23], the authors propose OSDR, an Opp- the network. Every node contacted by the message creator Net routing protocol that defines a utility function based node is studied as a candidate for storing and broadcasting on the average meeting time between an OppNet node and the message, but only those that are good enough are se- the destination of a message. Messages are replicated in lected. This local problem can be seen as an optimisation terms of an OST strategy that achieves a minimum deliv- problem. Probabilistically speaking, early contacted nodes ery message delay. will not guarantee optimal results, that is, poor nodes will In [9], the authors present Relcast, a delivery paradigm be selected for message storing. Late decisions, moreover, where messages are sent to profiles defined by relative de- will also fail as it is likely that good candidates will have livery functions such as best, maximum or over-the-average. been discarded. OST [34] deals specifically with this type Nodes belong to these relative profiles taking into account of problems. It is a statistical solution for the problem of not only attributes from the very same node but also rel- 3 ative to others from the same profile. Additionally, they Variable Description present Explore and Wait, a composite routing-delivery scheme that uses OST-based delivery strategies to route cent(n1 ) node n1 centrality. Relcast messages. sim(n1 , n2 ) Nodes n1 and n2 similarity. Finally, there are some very interesting proposals that rel(n1 ) node n1 reliability. use OST to find the optimal time to delay the reporting of S maximum number of storers. information in the context of opportunistic mobile sensor s(n1 , n2 ) storer suitability metric. networks [3]. In this context, the quality of the informa- TTL remaining life time of the message. tion gathered decreases over time. In order to optimise ict node inter-contact time. the quality of the context information delivered, proposals sict moving average of ict. like [3, 4, 5, 2] optimally decide on the moment to stop lastclist list of nodes recently contacted. the process of gathering context information and send it. maxlist kth best values of s(n1 , n2 ). This optimality is achieved by proposing different time- |C| number of nodes a node will contact before optimized models based on OST. a message T T L has expired. ns estimation of |C| (node scope). Table 1: Summary of notation. As reviewed, literature has many entries on broadcast protocols for OppNet. However, the designing of these pro- Our proposal limits the number of storers in the net- tocols does not stay within the basic criteria of efficiency, work for a certain message, that is, the number of nodes but mainly considers classical metrics like low latency or that are allowed to forward the message. This broadcast wide message dissemination. When it comes to efficiency, dissemination protocol is explained in Section 3.1. In Sec- preventing unrestrained propagation of messages is cru- tion 3.2, we introduce a metric used by the presented pro- cial, and therefore storer nodes must be carefully selected. tocol to characterise candidate nodes for the selection of In this article, we want to explore a novel way of dissem- the storers. This metric defines nodes’ storer suitability ination broadcast messages in OppNet that, contrary to in terms of node’s centrality, custody reliability and con- all of the previous unicast and broadcast OppNet propos- tacted node similarity. Since it is difficult to know which als presented in this section, does not limit the number of are good or bad values for this metric, as this depends message replicas in the network, but the number of storers not on the node itself but on how higher or lower this of the message. Nodes that receive the broadcast mes- metric value is relatively to other nodes’, we propose in sage, in turn, can not disseminate it again, unless they are Section 3.3 a method to select nodes for the delegation of chosen by the previous storer. This section introduced message storing. This node picking method is not triv- centrality, similarity and reliability of nodes as metrics ial. The selection is divided in to several stages, each one that have been customarily used by routing algorithms to using an independent OST based strategy using the pre- evaluate forwarding nodes. Unfortunately, merely using viously introduced suitability metric. Finally, since this these metrics does not guarantee that messages are going storer decision is performed in terms of how many nodes to spread across the whole network (mostly because of the a node could potentially contact during the lifetime of a limited network capacity). OST provides a mechanism to given message, we propose in Section 3.4 a means of esti- hold back each storer selection until a favourable context mating the number of nodes a certain node can potentially is found. In this article, we use the metrics explored in this contact during a certain period of time. section to define an OST reward function to select good At the end of Section 3, after a complete description enough storers for an efficient broadcast, by optimally solv- of our broadcast dissemination protocol, we include Algo- ing a different GSP in each of the stages of our protocol. rithm 1. The algorithm can be seen as a synthesis of the In the next section, we fully present our proposal. whole Section 3, and, to improve its readability, particular lines will be referenced throughout this section. 3.1. Routing Protocol 3. Efficient Broadcast Traditional network schemes include network primi- In computer networks, message broadcasting includes tives such as routing and delivery. Routing is the action different network paradigms, such as one-to-many and many- of relaying messages from one node to another thus defin- to-many, where messages are broadcast without necessar- ing a communication path. When a message is routed ily expecting a response from the recipients. In this sec- from one node to another, the latter is allowed, in turn, to tion, we present a broadcast dissemination protocol that store the message in order to route it as well. On the flip achieves high dissemination capacity, with a low number side, the delivery action is defined as the action of allowing of excluded nodes, while remaining very efficient in terms one or more applications in a node to receive the payload of energy consumption. of the message. In our broadcast proposal, we define a 4 Figure 1: Broadcast dissemination protocol strategy. Example with S = 8 storers. strict upper bound on the number of nodes that can store an OST based strategy in the context of this stage. broadcast messages. When an efficient broadcast message To avoid repeating storers, each node keeps a list of is created by a node (lines 15-19 of Algorithm 1), a par- all already forwarded messages and refuses to accept ticular number S is associated to that message, and the them again in the future. This mechanism is used in first stage of our protocol starts. Initially, S indicates the some epidemic proposals, such as [39]. maximum allowable number of storers of the message in the network. The node that creates the message becomes For the sake of clarity, we provide in Figure 1 an illus- the first storer of the message and it will replicate the mes- trative example where a message is sent from node n1 using sage with different values of S. Each time a new storer is the efficient broadcast proposed in this paper with an ini- chosen and it gets a replica of the message, an independent tial value of S = 8. The distinct stages of the protocol are new stage of the protocol starts (lines 32-33, 38-42 and 46 depicted using horizontal stripes of different colours. In of Algorithm 1). Following this, we describe how a storer the first stage, following the algorithm, n1 selects n2 , n3 , has to deal with a message it receives that is associated to and n4 as new storers, forwards the message to them using a particular value of S: S = 4, S = 2 and S = 1 values respectively, and goes up- dating its own S value until a final value of S = 1. These • S = 0: the node is allowed to locally deliver the storers are selected using a GSP strategy in the context of message but not to forward it to any other node. this first stage. While in the process of selecting the new storers, n1 forwards the message to all nodes on sight using • S = 1: the node can forward the message to as many a value of S = 0 for each new copy. Next, in a new stage nodes as it will contact. The S value in the new of the protocol, n2 will repeat the procedure with the local forwarded message is 0. copy of the message with S = 4. This time, n5 and n6 are selected as new stores following a totally separated GSP • S > 1: As in the previous case, the node can forward strategy, and copies of the message are forwarded to them the message to as many nodes as it contacts. The with S = 2 and S = 1 values, respectively. At this point, S value in the new forwarded message is also set to n5 and n3 can still choose a new storer because they still 0. Additionally, it chooses a node to delegate the have S = 2, and using independent CSP strategies in their storing of the message, and forwards the message to stages they choose n7 and n8 , and forward the message it with a new S value of dS/2e. The S value of the with S = 1. local copy is then set to bS/2c and the procedure is By following this scheme, as it can be seen in Figure repeated considering the new value of S. Following 1, there are a total of eight storers of the message in the the algorithm, a total number of blog2 Sc nodes are network (n1 to n8 ). The rest of the nodes in the figure selected as storers. The storers are selected using have received a copy of the message with S = 0 for local 5 delivery, and therefore they are not storers and cannot 3.2.2. Similarity further forward the message. For the similarity metric, we study how different a As we will see in section 3.3, each stage in the protocol storer node is in comparison to the contacted candidate will be related to a different GSP instance, each one with for message storing. Every time two nodes met, we com- its own optimal solution. pute a metric that calculates the intersection of the last contacted nodes from both nodes, i.e., when a given storer 3.2. Storer Suitability node ns contacts a given node nc , the similarity for node In this section, we propose a metric, s(n1 , n2 ), to com- nc is calculated in the following way: pare a node’s suitability to store a broadcast message. This metric is used in the reward function that will be used for storer selection, see Section 3.3. Using this met- simns ,nc = 1 − (|lastclistns ∩ lastclistnc | / |lastclistns |) ric, nodes are quantified in terms of three different char- (3) acteristics: being lastclistni node ni ’s list of its last contacted nodes. • Centrality. We measure how well physically con- 3.2.3. Reliability nected a node is. The more connected the node is, For defining the reliability of a node, we consider two the more likely it will find more nodes to broadcast variables: slastdrop (moving average for the percentage of the message. non-dropped messages from a certain period of time) and freebufferspace (free available buffer). • Similarity. We study how similar a node is to The slastdrop moving average is calculated every hour the studied candidate for message storing delegation. as: The more dissimilar these nodes are, the more likely the candidate will find new and different nodes to broadcast the message. slastdropnew = slastdropold +ρ×(lastdrop−slastdropold ) (4) • Reliability. We measure how reliable a node is for where ρ is the moving average weight factor. storing messages. The more reliable a node is, the For a certain node ni , the reliability compound metric more likely that it will disseminate the message. is calculated giving the same weight to both variables: For a given storer of a message ns we define the suit- ability of a contacted node nc as (lines 24-27 of Algorithm relni = slastdrop × 0.5 + freebufferspace × 0.5 (5) 1): 3.3. Storer Selection s(ns , nc ) = α1 × centnc + α2 × simns ,nc + α3 × relnc (1) If a node ns finds a node nc with a certain value for the storer suitability s(ns , nc ), as defined in the reward func- where centnc is how central the contacted node is, simns ,nc tion from the previous section, it is hard to know whether how similar the storer node is to the contacted node, relnc this value is a high one or a low one in comparison to what how reliable P for the storage of a message the contacted this node could find in future contacts. In this section, we 3 node is, and i=1 αi = 1. analyse from an OST perspective, the strategy to select a set of good storers for a given message m with a maximum 3.2.1. Centrality storer suitability value for s(ns , nc ). Regarding the centrality metric, we calculate it for ev- Being T T L the remaining life time of the message and ery node using its ego-centric network [18]. In this net- ni a certain node, we define the contact node list C(ni , T T L), work, nodes’ contacts are represented by an adjacency as the list of future contacts for node ni for a period of time symmetric matrix where its rank, n, is the number of con- T T L: tacts a given node has made. For this purpose, every node keeps a contact matrix (CM ) that represents the node’s C(ni , T T L) = {c1 , c2 , ..., c|C| } (6) contact ego perspective of the network [18]. Note that the cardinality of C is normally unknown in We propose to use the betweenness egocentric central- OppNet. This means that a given node ni cannot neces- ity as our centrality metric, a centrality metric with a small sarily know in advance the number of nodes it will contact computational cost. As presented in [16], for a certain before the message m expires. In Section 3.4, a method node ni , this metric is calculated by computing the num- for estimating this cardinality will be presented. For ex- ber of nodes that are indirectly connected through the ego ample, in Figure 1, node n1 , will find 20 nodes before the node using the following expression: broadcast message will expire. As presented in the previous section, given a node nc , centni = CM 2 × [1 − CM ]i,j (2) candidate for message storing, and ns , the current storer 6 of the message, we define s(ns , nc ) as a way of evaluating these nodes will not be the blog2 Sc best nodes in terms of node nc ’s storer suitability. s(ns , nc ). In the same way, if we wait for the last blog2 Sc The future contacts for a given storer ns in a network, contacted nodes, it will be equally likely that the best suit- in a hypothetical situation when seen together, may be able nodes will be discarded. Furthermore, the method of ordered from best to worst unambiguously in terms of deciding after encountering every node in the network is s(ns , nc ). Moreover, we define the criterion of order of not feasible: nodes may never be re-encountered again. a set of nodes P ⊆ C as: This optimisation problem corresponds to the CSP [17] X when k = blog2 Sc = 1, to the GSP of [38] (Theorems 1 and tP = s(ns , nm ) (7) 4) when k = blog2 Sc = 2, and to the GSP of [6] (Theorems m∈P 1 and 4) when k = blog2 Sc = 3. Equation (7) allows us to define how good the com- We follow the methodology for the GSPs presented by posite choice of a set of candidate nodes is for storing del- Ano in [6], Theorems 1 and 4. This methodology, for the egation. For example, in Figure 1, for the storer n1 , we particular case of k = blog2 Sc, is a strategy where there ex- calculate t{n2 ,n3 ,n4 } to evaluate how good the choice of the ists an optimal set of stopping values v1 |C| , v1 |C| , v2 |C|, set {n2 , n3 , n4 } is for storing delegation. ..., vblog2 Sc |C|, 1 ≤ v1 |C| ≤ v2 |C| ≤ · · · ≤ vblog2 Sc |C| ≤ Additionally, we define P as the set of all of the possible |C| such that the pth storer for message m (p ≤ blog2 Sc) subsets of C: is: • the first node which is the best of all the previously P = {{ni1 , ni2 , ..., nir } ⊆ C \ ∅} (8) seen nodes, if the node has contacted v1 |C| nodes. Additionally, let Pk ⊆ P be the set containing all the subset of P for a certain size k: • or, if not found, the first node which is the second best of all the previous nodes, if the node has con- Pk = {P ∈ P| |P | = k} (9) tacted v2 |C| nodes. As explained in Section 3.1, for a given message m, a .. node ni contacts different nodes until it delegates storing . for that message m to k = blog2 Sc nodes from the set C • or, if not found, the first node which is the blog2 Scth using opportunistic contacts. Let nit+1 be a new forwarded best of all the previous nodes, if the node has con- node for potential storing delegation. The delegation con- tacted vblog2 Sc |C| nodes. dition, f , is used to decide whether storing of this message should be delegated or not to nit+1 based only on the node • or, if not found, the (|C| − blog2 Sc + p)th node. and the previously forwarded nodes: The list of conditional statements enumerated above is f : CxP → {0, 1} (10) represented in Algorithm 1 on lines 35 and 37, comparing the storer suitability of the contacted node with the best We want to delegate storing of a message m to blog2 Sc k values of the storer suitability of past contacted nodes, and only blog2 Sc nodes P = {ni1 , ni2 , · · · , niblog2 Sc } ∈ Pk which are stored in the maxlist array. This array is up- that maximises tP . A solution to the problem has to define dated in Algorithm 1 in line 48. This strategy, applied a strategy to maximise the probability of selecting a set in independently at every stage of the protocol, maximises Pblog2 Sc , O, such that: W(P ) from a statistical perspective, that is, maximises the suitability of the selected nodes for storing the broad- cast message. Note that, even though the selection process O = {P ∈ Pblog2 Sc | tP ≥ tP 0 ∀P 0 ∈ Pblog2 Sc } (11) may result in optimality in each stage of the protocol, we This is equivalent to maximise a reward function W can not guarantee the global optimality of this selection, that returns 1 if the blog2 Sc nodes that fit best to the as the storers are not selected by a single node but by a set targeted criteria are selected and 0 otherwise. Given a list of distributed nodes, each of which follows an independent of nodes P = {ni1 , ni2 , · · · , niblog2 Sc } ∈ Pblog2 Sc selected GSP in its stage of the protocol. as new storers, we define W(P ): In Table 2, a list of the optimal stopping values for every statistical problem is presented along with the ref- erences used. Note, that this routing decision is in terms ( 1 P ∈O W(P ) = (12) of the cardinality of the contact node list (|C|). In the 0 otherwise following section, we explain how this cardinality can be For each stage of our protocol, this corresponds to an estimated. OST problem where the decision is whether a set of nodes should or should not be chosen as new storers when these 3.4. Node Scope nodes are contacted. Note that if the first blog2 Sc en- As introduced in the previous section, the cardinality of countered nodes are chosen as storers it is quite likely that the contact node list |C| is normally unknown in OppNet 7 k v1 v2 v3 Reference Algorithm 1 Broadcast dissemination behaviour. 1: . msg is the broadcast message. 1 1/e |C| - - [17] 2: . msg.contacted is the number of nodes the node has contacted 2 0.2291 |C| 0.6065 |C| - [38] since the creation of the message. 3 0.1668 |C| 0.437 |C| e−1/3 |C| [6] 3: . msg.maxlist are the kth best values for s. 4: . msg.p is the number of the storer to be delivered (first, second, Table 2: Optimal stop values for the statistical problem of finding k ..., kth ). storers, k values in 1 − 3. 5: . msg.k is the number of storers to select in the stage. 6: . msg.S is the maximum number of storers left. 7: . msg.T T L is the remaining life time of the message. 8: . localnode is the local node. because of the idiosyncrasy of the network: it is difficult 9: . contactednode is the contacted node. to know in advance the number of nodes a node will con- 10: . lastcontacttime is the last time the node was contacted. tact before the expiration time of a message. In order to 11: . vki is the ith optimal stop value for the optimal selection of k stores (see Table 2). calculate an estimation of the number of nodes a certain 12: . αi are the metric weights to compute s. node can contact before the expiration time of a message 13: procedure newMessage(msg) (T T L), a statistic of the time between contacted nodes is 14: #Procedure called when creating a message and starting the kept within the node. We call this statistic the smooth first stage. 15: msg.S = MAX NUMBER OF STORERS inter-contact time (sict). To prevent recently forwarded 16: msg.contacted = 0 nodes distorting this estimation, nodes keep a list of the 17: msg.p = 1 last nodes the node has contacted. We call this list last 18: msg.maxlist = [] 19: msg.k=blog2 msg.Sc contacted node list (lastclist). 20: end procedure Every time a node contacts another node not included 21: procedure onNewContact(contactednode, msg) in the list lastclist, the observed inter-contact time (ict) 22: #Procedure called each time localnode contacts a new node, is calculated (line 28 of Algorithm 1): for every broadcast message. 23: msg.contacted++ 24: cent = centrality(contactednode) ict = time.now() − lastcontacttime, (13) 25: sim = similarity(localnode,contactednode) 26: rel = reliability(contactednode) where time.now is the current time and lastcontacttime is 27: s = α1 × cent + α2 × sim + α3 × rel the last time the node contacted another node. 28: ict = time.now() - lastcontacttime The sict statistic is updated using an EWMA (Expo- 29: sict = sict + σ × (ict - sict) 30: ns = msg.T T L/sict nential Weighted Mobile Average) in the following way 31: c = msg.contacted + ns (line 29 of Algorithm 1): 32: replica=msg.replicate() 33: replica.S=0 34: #Conditional statements described in Section 3.3: sictnew = sictold + σ × (ict − sictold ), σ ∈ [0, 1], (14) 35: for i = 1, i ≤ k, i++ do 36: #Check if contactednode has to be a new storer. If so, a new stage starts: where sictold is the historical ict, σ is a weight factor and 37: if (s ≥ maxlist[i] & msg.contacted > ict the last ict measured. c × vki ) ||(msg.contacted > (c − k + msg.p)) then The estimated the number of nodes a certain node can 38: replica.S=dmsg.S/2e contact before a broadcast message expires ns(T T L) (node 39: replica.k=blog2 replica.Sc 40: replica.resetvalues(maxlist, contacted, lastcontacttime, p) scope) is calculated using the following expression (line 30 41: msg.S=bmsg.S/2c of Algorithm 1): 42: msg.p++ 43: break 44: end if ns(T T L) = T T L/sict. (15) 45: end for The estimation of |C| for a certain node ni for the 46: replica.forward(contactednode) 47: #Update maxlist: proposed optimal routing strategy proposed in Section 3.3 48: msg.maxlist.updatemax(s) can be calculated as (line 31 of Algorithm 1): 49: end procedure |C| = b contactedni + ns(T T L), (16) where contactedni is the number of contacted nodes by 4. Evaluation node ni . In this section, we present the experimentation carried out to evaluate the performance of our proposed broadcast In this section, we presented our efficient broadcast dis- dissemination protocol. First, we state the goal of the semination protocol for OppNet. In the next section, we evaluation and the metrics we use. Then, we describe the will evaluate its performance and compare our approach simulation environment, network scenarios and simulation to others from the state of art presented in Section 2. parameters. Finally, we present the achieved results. 8 Variable Info5 Cambridge Taxis MIT Density high low low high Modularity low medium low high Clustering Coeff. high high medium high Communities 6 3 4 4 Average Path length low high high medium Presence of hubs no yes yes no Table 3: Scenario characterisation. Info5 Cambridge Taxis MIT 1000 100 50 Contacts # Contacts 100 ratio 10 10 100 total 10 unique 1 0 10 20 30 40 0 10 20 30 40 50 0 100 200 300 0 25 50 75 100 Nodes Nodes Nodes Nodes Figure 2: Total and unique contacts for every node for the different studied scenarios. Third, we analyse the number of dropped messages to check the use of the network storage capacity. Last, we analyse the number of excluded nodes, i.e. the number of nodes which do not receive any broadcast message. 4.2. Simulation Environment (a) Info5. (b) Cambridge. (c) Taxis. (d) MIT. The experiment has been performed using the Oppor- tunistic Network Environment (TheONE) simulator [25]. Figure 3: Contact social network for Info5, Cambridge, Taxis and We have enhanced this simulator to include our proposed MIT scenarios. broadcasting protocol and for comparison purposes, other OppNet broadcast proposals from the state of the art. 4.1. Goal and performance metrics We choose four different scenarios to analyse the per- formance of our proposal. Node contacts from the four The goal of the experimentation is not only to evaluate scenarios are defined by physical contacts obtained from our proposed protocol but also to compare its performance real mobility traces from the Crawdad database1 , a com- with that of other protocols representative of the state of munity resource for collecting wireless data at Dartmouth the art regarding message broadcasting in OppNet. College, United States. First of all, this analysis and comparison are achieved The first scenario, the Info5 scenario, is based on real by using three classical metrics: mobility traces, as published in [1]. These traces were • Broadcast message dissemination: number of retrieved during the 2005 edition of the Infocom conference nodes a broadcast message arrives at. in the course of 2.97 days. Contacts from these mobility traces represent 41 students. The total number of physical • Energy consumption: energy needed to broadcast encounters provided in these traces is 22459. a message. The second scenario, the Cambridge scenario, is based on real contact traces from 51 students from the System • Message latency: average time for broadcast mes- Research Group of the University of Cambridge carrying sage delivery. small devices for six days [27]. Additionally, some station- ary nodes were placed at various points of interest such as Second, we use these three metrics in a compound man- grocery stores, pubs, market places, and shopping centres ner and analyse the broadcast efficiency, i.e. we study message dissemination per unit of energy consumption and message latency. 1 http://crawdad.org/keyword-DTN.html. 9 Info5 Cambridge Operation Average Units -3 Determinants 5,332 ×10 Ws/Mop (Joules/Mop) High Polynomials 1,20144 ×10-4 Ws/Mop (Joules/Mop) 10K messages 1,51875 ×10-4 Ws (Joules/message) α3 α3 Table 4: Energy consumption. α α 1 1 α2 α2 Low Taxis MIT described in section 3.2, as well as the energy cost of basic operations. 4.3.1. Metric weights α3 α3 The weights of centrality, similarity and reliability in the node suitability metric (namely α1 , α2 , and α3 , where α α 1 P3 1 i=1 αi = 1), determine the behaviour of the protocol. α2 α2 The best values for these parameters may depend on the Figure 4: Broadcast efficiency as a function of the different values specific scenario where the protocol is in operation, but for α1 (centrality weight), α2 (similarity weight) and α3 (reliability for the sake of comparison, simulations of different scenar- weight). ios should share these weights. In order to choose values that do not favour a particular scenario, we have analysed the outcome of the suitability metric for different com- all around the city of Cambridge, UK. A stationary device binations of values in all scenarios. Figure 4 shows the was also placed at the reception of the Computer Lab, in efficiency performance of a broadcast message for the dif- which most of the experiment participants were students. ferent scenarios and the different values of α1 , α2 and α3 . The number of contacts provided in these traces is 10641. As it can be seen, for the scenarios Info5 and MIT, low The third scenario, the Taxis scenario, as published in values for α3 obtain a higher efficiency performance. This [10], contains mobility traces from 370 taxi cabs in Rome is probably due to the fact that in both scenarios there is over 30 days. The number of contacts provided in these a high density of contacts, and reliability is not really a traces is 449226. decisive factor. Instead, for the Cambridge and Taxis sce- The fourth scenario, the MIT scenario, as published in nario, the best results seem to come with lower values of [15], represents the activity information from 97 subjects α1 , probably due to the fact that in these scenarios there at Massachusetts Institute of Technology over the course are hotspots that facilitate contacts and minimise the rel- of the 2004-2005 academic year (196 days). The number evance of the intrinsic centrality of nodes. of contacts provided in these traces is 205187. For the simulation, a safe triplet of values for the αi In Figure 2, we analyse the total contacts and unique constants is chosen, providing no significant differences be- contacts for every node for the different scenarios. As it tween scenarios, which provides a perfect balance of the can be seen, the Cambridge and MIT scenarios have a low three weighted metrics: number of contacts while in Info5 and Taxis the number α1 = α2 = α3 = 31 of contacts is high. We see that in the Info5 scenario, the Figure 4 shows that this combination does not favour ratio between the total number of contacts and the unique any particular scenario. contacts is very large in comparison to the other three scenarios. 4.3.2. Energy consumption In Figure 3, we depict the contact social network for When calculating efficiency, it is crucial to determine the Info5, Cambridge, Taxis and MIT scenarios. In Table the amount of energy consumed. To introduce an accu- 3, a scenario characterisation in terms of classical network rate estimation of energy consumption in the simulation, topology measures is presented. we conducted a practical experiment which measures real As can be seen from Figures 3 and 2, and Table 3, consumptions of data communications. the four scenarios are different in terms of their contact network topology. In the experiment, we used two Raspberry Pi devices with WiPi WiFi dongles, powered by AC 230V - DC 5V transformers. The electrical feed was monitored by two 4.3. Protocol parameters for simulation USB ammeters, as shown in Figure 5. One of the com- The simulations require particular values for certain puters was used to calculate the “idle” state energy con- parameters in order to get useful results. Specifically, the sumption, while the second was performing the tests. The protocol needs specific values for the weights of centrality, difference between the measured values provided the en- similarity and reliability in the node suitability metric, as ergy consumption of the test. To improve accuracy, each 10 described in Figure 1. See Section 3.1 for a complete de- scription of the behaviour of each storer in this situation. As a consequence of having an initial S value set to 8, we need to solve three different statistical problems, as introduced in Section 3.3: the GSP from [6] (blog2 Sc = 3), the GSP from [38] (blog2 Sc = 2) and the CSP [17] (blog2 Sc = 1). For every statistical problem the value for |C| is calculated following the estimation from Equation 16 (see Section 3.4). 4.5. Results In order to study the performance of our proposal, we conduct several simulations where 400 broadcast messages Figure 5: Energy consumption measurement: ammeters and Rasp- are sent to the networks defined in the four different sce- berry Pi. narios. In order to make these scenarios realistic, besides the studied broadcast messages, we are also including 1000 unicast messages that compete for the same network re- experiment was run continuously for two hours and re- sources. peated four times. The data from the first 20 minutes has We compare our broadcast dissemination protocol (“ef- been discarded to make sure the system was in a steady fi” in the figures) with three broadcast dissemination pro- condition after booting. For each experiment, the consid- tocols representative of the state of the art. On the one ered result is the average of the median values of the four hand, we study the performance of a scheme where mes- tests. sages are epidemically forwarded to every contacted node The aim of the experiments is to calculate the energy in the network (“epid” in the figures) as in [28]. Then, consumed by the routing algorithm. In Algorithm 1 there we evaluate the performance of a broadcast dissemina- are three basic operations: sending of messages, matrix tion protocol where central nodes in the network are se- determinants, and polynomial equations. The tests re- lected to disseminate the broadcast messages (“cent” in garding message sending consumption consisted of sending the figures), as in proposals such as [19, 32, 37]. Finally, a messages with a 10 KByte payload. As for the operation third proposal is evaluated where broadcast messages are tests, we used randomly generated matrices to calculate geography-limited by means of their message time to live determinants and second grade polynomial calculations. mandating a restriction on the propagation of the mes- As seen in Table 4, determinants and polynomials en- sages within a specified number of hops or distance from ergy consumption is negligible, as the routing algorithms the message source, as in proposals like [11] (“copylim” in use only a few of these operations (units in the table are in the figures). Joules per Mega operations). Each sent message consumed In Figure 7(a), Figure 7(b) and Figure 7(c) we anal- approximately 1.52 × 10-4 Joules. yse the performance of our proposal for these broadcast messages using the classical metrics: broadcast message 4.4. Routing strategy dissemination, energy consumption and average latency delivery time, respectively. As it can be seen, our pro- In Figure 6, we study the impact of the value of the posal performs well when compared to the other three in number of storers per message (S) on our protocol. We terms of message dissemination. Since our proposal effi- analyse three classical metrics: energy consumption, broad- ciently limits the flooding of the message, due to the mes- cast message dissemination and average latency time. As sage dropping, our proposal performs in some scenarios it can be seen, S has different impacts on the four stud- (Cambridge and MIT) even better than the epidemic one. ied scenarios. For most of the scenarios, the results for all Concerning energy consumption, our proposal improves on three metrics show a substantial improve for 0 < S <= 6. the other three in a very significant manner for the four Instead, for 6 < S < 12, most of the metrics stabilise or scenarios. Unfortunately, when it comes to message la- show a slight improvement. Some metrics start deteriorat- tency time, our proposal does not provide good results ing when S > 12. S = 12 seems to be the best choice for in comparison to the other three proposals, but this was our protocol in every scenario. somewhat expected, since we delay the selection of the For the experimentation, as we want to compare our storers. broadcast dissemination protocol to other three protocols If we consider these three metrics in a compound fash- representative of the state of the art, for the sake of fair- ion, we can study the broadcast efficiency, that is, the ness, we do not choose the best possible instance for our message dissemination per unit of energy consumption and protocol (S = 12) but we study a generic middle-case time to deliver the message. We analyse this efficiency in where the maximum number of storers in the network is Figure 8(a), as a function of the message time to live. As S = 8. With this choice, we also reproduce the example 11 Efficiency(#msg/(J*min)) Efficiency Dissemination Latency Dissemination(nodes) Latency(minutes) 50 8000 Scenario 3.5 45 Cambridge 6000 3.0 40 Info5 4000 35 MIT 2.5 2000 Taxis 30 4 8 12 4 8 12 4 8 12 S(number of storers) S(number of storers) S(number of storers) Figure 6: Broadcast message dissemination, protocol energy consumption and average latency time as a function of the number of storers (S). can be seen, in all scenarios, our proposal is a significant General Value improvement on the state-of-the-art. In Figure 8(b), we analyse the number of dropped mes- Simulation duration 55 h sages as a function of the message time to live. Our pro- Transmission Speed 250 KB/s posal greatly reduces this number, and thus improves the # Nodes (Info5) 41 network storage capacity, in comparison with the “epid” # Nodes (Cambridge) 51 and “copylim” proposals. Our proposed protocol cannot # Nodes (MIT) 97 compete with the reduction offered by “cent” because this # Nodes (Taxis) 370 last proposal is very restrictive regarding the replication # random seeds 50 of any message sent. However, this very restriction leads Buffer Size 100 KB-10 MB “cent” to achieve poorer dissemination results than our Traces information proposal, as we can see in Figure 7(a). # Contacts (Info5) 22459 Finally, we analyse the distribution of the frequency # Contacts (Cambridge) 10641 of the number of nodes contacted by the 400 broadcast # Contacts (Taxis) 449226 messages, paying attention to those nodes that are not # Contacts (MIT) 205187 contacted by any broadcast message (excluded nodes). In Figure 8(c), we analyse the number of excluded nodes as Message information a function of the message time to live. As it can be seen, # Broadcast Messages 400 our proposal matches the number of excluded nodes in # Unicast Messages 1000 comparison to the other broadcast protocols in the Info5 Message size 10 KB scenario, and reduces this number in the other three cases. TTL 5’-120’ Routing/Delivery Settings 5. Conclusions S 8 α1 ,α2 ,α3 1/3 Most applications running on OppNets require broad- γ (ageing constant) 0.98 cast delivery of messages (and other forms of multicast) k (time unit ageing constant) 30 s for their normal operation, and having an efficient broad- σ (sict moving average factor) 0.75 cast routing strategy for these messages is essential for the ρ (slastdrop moving average factor) 0.75 sake of real applications. slastdrop time period 1 hour As opposed to other proposals devoted to the problem of message broadcasting in OppNet, which are based on Table 5: Simulation variable summary. limiting the number of message copies or their life span, in this paper we proposed an efficient (in terms of energy con- sumption and network capacity usage) broadcast dissemi- in every stage, holding back broad message dissemination nation protocol which uses a different perspective. Broad- until convenient conditions are met. This strategy makes cast messages are limited not just regarding the number of the most of the network storage capacity, facilitating and copies or their life span, but also carefully selecting their expediting the spreading of messages throughout the net- prospective forwarders (storers). work. The metrics used to assess favourable forwarding In each stage of our proposed routing protocol we use a conditions include betweenness egocentric centrality; node different GSP as the key element to devise a strategy which reliability measured as both the least dropping probabil- maximises, from a statistical perspective, the suitability of ity and the most space availability for messages; and the the list of the selected nodes for storing every broadcast similarity among contacted nodes. message. Our strategy selects the best message storers We evaluate our protocol using four well-known sce- 12 Info5 Cambridge Taxis MIT Dissemination(nodes) 10000 1000 Routing 1000 effi 1000 1000 epid 500 500 100 cent 100 copylim 0 30 60 90 120 0 30 60 90 120 0 30 60 90 120 0 30 60 90 120 TTL(minutes) TTL(minutes) TTL(minutes) TTL(minutes) (a) Broadcast message dissemination as a function of message’s time to live. Ener. Consumption(J) Info5 Cambridge Taxis MIT 1e+03 Routing 100 10.0 10.0 effi 1e+01 1.0 epid 1 0.1 cent 0.1 1e−01 copylim 0 30 60 90 120 0 30 60 90 120 0 30 60 90 120 0 30 60 90 120 TTL(minutes) TTL(minutes) TTL(minutes) TTL(minutes) (b) Protocol energy consumption as a function of message’s time to live. Info5 Cambridge Taxis MIT Latency(minutes) Routing 10 effi 10 10 10 epid 1 cent 1 1 1 copylim 0 30 60 90 120 0 30 60 90 120 0 30 60 90 120 0 30 60 90 120 TTL(minutes) TTL(minutes) TTL(minutes) TTL(minutes) (c) Average latency time as a function of message’s time to live. Figure 7: Protocol performance: broadcast message dissemination, energy consumption and average latency time. narios based on real mobility traces from real communi- of dropped messages, when compared with epidemic and cation datasets, and comparing our protocol with three limited-epidemic proposals, and is insufficient when com- other broadcast protocols representative of the state of pared to protocols which select central nodes to dissem- the art in OppNet broadcasting. We first analyse three inate the broadcast messages. However, this limitation classical performance metrics: broadcast message dissem- gets compensated by the higher dissemination results at- ination, energy consumption and message latency. Our tained by our proposal. Finally, we analyse the number of proposal, when compared to the other proposals, performs excluded nodes, i.e. the number of nodes which are not well in terms of message dissemination; improves on the contacted by any broadcast message. In three of the four other three in a very significant way regarding energy con- scenarios, our work reduces the number of excluded nodes sumption; with only a minor increase in terms of message in comparison to the other broadcast protocols, while in latency. Second, we use these three metrics in a com- the fourth scenario we mandate parity. bined manner and analyse the broadcast efficiency, i.e. the message dissemination per unit of energy and message la- Acknowledgements tency. In this regard, our work is a significant improve- ment beyond the existing protocols. Next, we analyse the This work was partly supported by the Catalan AGAUR number of dropped messages to evaluate the usage of net- 2017SGR-463 project and the Spanish Ministry of Science work capacity. Our proposal greatly reduces the number and Innovation TIN2017-87211-R project. The authors 13 Efficiency(#msg/(J*min)) Info5 Cambridge Taxis MIT Routing 10.0 10.0 10.0 10.0 effi epid 0.1 0.1 0.1 cent 0.1 copylim 0 30 60 90 120 0 30 60 90 120 0 30 60 90 120 0 30 60 90 120 TTL(minutes) TTL(minutes) TTL(minutes) TTL(minutes) (a) Broadcast efficiency as a function of message’s time to live. Info5 Cambridge Taxis MIT # Dropped messages 10000 Routing 550 70000 600 effi 100 epid 50 500 100 cent copylim 0 30 60 90 120 0 30 60 90 120 0 30 60 90 120 0 30 60 90 120 TTL(minutes) TTL(minutes) TTL(minutes) TTL(minutes) (b) Number of dropped messages as a function of message’s time to live. Info5 Cambridge Taxis MIT # Excluded Nodes 5 300 25 85 4 Routing 20 200 80 epid 3 2 cent 15 100 75 1 copylim 10 70 0 0 0 30 60 90 120 0 30 60 90 120 0 30 60 90 120 0 30 60 90 120 TTL(minutes) TTL(minutes) TTL(minutes) TTL(minutes) (c) Number of excluded nodes as a function of message’s time to live. Figure 8: Routing performance: broadcast efficiency, number of dropped messages and number of excluded nodes. thank Marc Dalmau for his generous help with the energy tivariate context collection in mobile sensor networks. Computer consumption experimentation. We also thank Dr. Jason Networks, 57(6):1394–1407, 2013. [5] Christos Anagnostopoulos, Stathes Hadjiefthymiades, and Quinlan for his assistance reviewing the grammar of our Evangelos Zervas. Optimal stopping of the context collection manuscript. process in mobile sensor networks. In Personal Indoor and Mo- bile Radio Communications (PIMRC), 2013 IEEE 24th Inter- national Symposium on, pages 2067–2071. IEEE, 2013. References [6] Katsunori Ano. Optimal selection problem with three stops. J. Oper. Res. Soc. Japan, 32:491–504, 1989. [1] Dimitrios-Georgios Akestoridis. CRAWDAD dataset [7] Marc Barthelemy. Betweenness centrality in large complex net- uoi/haggle (v. 2016-08-28): derived from cam- works. The European Physical Journal B-Condensed Matter bridge/haggle (v. 2009-05-29). Downloaded from and Complex Systems, 38(2):163–168, 2004. http://crawdad.org/uoi/haggle/20160828/one, August 2016. [8] Carlos Borrego, Gerard Garcia, and Sergi Robles. Softwarecast: [2] Christos Anagnostopoulos. Time-optimized contextual informa- A code-based delivery manycast scheme in heterogeneous and tion forwarding in mobile sensor networks. Journal of Parallel opportunistic ad hoc networks. Ad Hoc Networks, 55:72–86, and Distributed Computing, 74(5):2317–2332, 2014. 2017. [3] Christos Anagnostopoulos and Stathes Hadjiefthymiades. [9] Carlos Borrego, Adrián Sánchez-Carmona, Zhiyuanand Li, and Delay-tolerant delivery of quality information in ad hoc net- Sergi Robles. Explore and wait: A composite routing-delivery works. Journal of Parallel and Distributed Computing, scheme for relative profile-casting in opportunistic networks. 71(7):974–987, 2011. Computer Networks, 123:51–63, 2017. [4] Christos Anagnostopoulos and Stathes Hadjiefthymiades. Mul- [10] Lorenzo Bracciale, Marco Bonola, Pierpaolo Loreti, Giuseppe Bianchi, Raul Amici, and Antonello Rabuffi. CRAW- 14 DAD dataset roma/taxi (v. 2014-07-17). Downloaded from ing in delay tolerant networks. IEEE Communications Letters, https://crawdad.org/roma/taxi/20140717, July 2014. 14(11):1026–1028, 2010. [11] Quanjun Chen, Salil S Kanhere, and Mahbub Hassan. Perfor- [29] Anders Lindgren, Avri Doria, and Olov Schelén. Proba- mance analysis of geography-limited broadcasting in multihop bilistic routing in intermittently connected networks. ACM wireless networks. Wireless Communications and Mobile Com- SIGMOBILE Mobile Computing and Communications Review, puting, 13(15):1406–1421, 2013. 7(3):19–20, 2003. [12] Radu Ioan Ciobanu, Ciprian Dobre, and Valentin Cristea. [30] Kazuya Okamoto, Wei Chen, and Xiang-Yang Li. Ranking of Sprint: social prediction-based opportunistic routing. In World closeness centrality for large-scale social networks. In Interna- of Wireless, Mobile and Multimedia Networks (WoWMoM), tional Workshop on Frontiers in Algorithmics, pages 186–195. 2013 IEEE 14th International Symposium and Workshops on Springer, 2008. a, pages 1–7. IEEE, 2013. [31] Tore Opsahl, Filip Agneessens, and John Skvoretz. Node cen- [13] Elizabeth M Daly and Mads Haahr. Social network analysis trality in weighted networks: Generalizing degree and shortest for routing in disconnected delay-tolerant manets. In Proceed- paths. Social networks, 32(3):245–251, 2010. ings of the 8th ACM international symposium on Mobile ad hoc [32] Jiho Park, Junyeop Lee, Sun-Kyum Kim, Kiyoung Jang, and networking and computing, pages 32–40. ACM, 2007. Sung-Bong Yang. A forwarding scheme based on swarm in- [14] Mieso K Denko. Mobile Opportunistic Networks: Architectures, telligence and percolation centrality in opportunistic networks. Protocols and Applications. CRC Press, 2016. Wireless Networks, 22(8):2511–2521, 2016. [15] Nathan Eagle and Alex (Sandy) Pentland. CRAWDAD [33] Ying Peng, Gaocai Wang, and Nao Wang. Energy-efficient dataset mit/reality (v. 2005-07-01). Downloaded from transmission strategy by using optimal stopping approach for https://crawdad.org/mit/reality/20050701, July 2005. mobile networks. Mobile Information Systems, 2016, 2016. [16] Martin Everett and Stephen P Borgatti. Ego network between- [34] Albert N Shiryaev. Optimal stopping rules, volume 8. Springer ness. Social networks, 27(1):31–38, 2005. Science & Business Media, 2007. [17] Thomas S Ferguson. Who solved the secretary problem? Sta- [35] Aloizio P Silva, Scott Burleigh, Celso M Hirata, and Katia tistical science, pages 282–289, 1989. Obraczka. A survey on congestion control for delay and dis- [18] Linton C Freeman. Centered graphs and the structure of ego ruption tolerant networks. Ad Hoc Networks, 25:480–494, 2015. networks. Mathematical Social Sciences, 3(3):291–304, 1982. [36] CC Sobin, Vaskar Raychoudhury, Gustavo Marfia, and Ankita [19] Wei Gao and Guohong Cao. User-centric data dissemination in Singla. A survey of routing and data dissemination in delay disruption tolerant networks. In INFOCOM, 2011 Proceedings tolerant networks. Journal of Network and Computer Applica- IEEE, pages 3119–3127. IEEE, 2011. tions, 67:128–146, 2016. [20] Appu Goundan, Eric Coe, and Cauligi Raghavendra. Efficient [37] Annalisa Socievole, Eiko Yoneki, Floriano De Rango, and Jon broadcasting in delay tolerant networks. In Global Telecommu- Crowcroft. Ml-sor: Message routing using multi-layer social net- nications Conference, 2008. IEEE GLOBECOM 2008. IEEE, works in opportunistic communications. Computer Networks, pages 1–5. IEEE, 2008. 81:201–219, 2015. [21] O Helgason and Gunnar Karlsson. Podnet: A system architec- [38] M Tamaki. Recognizing both the maximum and the second ture for opportunistic content distribution. Royal Institute of maximum of a sequence. Journal of Applied Probability, pages Technology (KTH), 2010. 803–812, 1979. [22] Theus Hossmann, Thrasyvoulos Spyropoulos, and Franck Leg- [39] Amin Vahdat, David Becker, et al. Epidemic routing for par- endre. Know thy neighbor: Towards optimal mapping of con- tially connected ad hoc networks. 2000. tacts to social graphs for dtn routing. In INFOCOM, 2010 [40] Eiko Yoneki, Pan Hui, ShuYan Chan, and Jon Crowcroft. A Proceedings IEEE, pages 1–9. IEEE, 2010. socio-aware overlay for publish/subscribe communication in de- [23] Di Huang, Sanfeng Zhang, and Zhou Chen. An optimal stopping lay tolerant networks. In Proceedings of the 10th ACM Sym- decision method for routing in opportunistic networks. In Wire- posium on Modeling, analysis, and simulation of wireless and less Communications and Networking Conference (WCNC), mobile systems, pages 225–234. ACM, 2007. 2013 IEEE, pages 2074–2079. IEEE, 2013. [41] Xi Zhang, Xiaofei Wang, Anna Liu, Quan Zhang, and Chaojing [24] Pan Hui, Jon Crowcroft, and Eiko Yoneki. Bubble rap: Social- Tang. Cooperation enforcement scheme based on reputation based forwarding in delay-tolerant networks. IEEE Transac- for delay tolerant networks. In Computer Science and Network tions on Mobile Computing, 10(11):1576–1589, 2011. Technology (ICCSNT), 2011 International Conference on, vol- [25] Ari Keränen, Jörg Ott, and Teemu Kärkkäinen. The ONE ume 4, pages 2372–2376. IEEE, 2011. simulator for DTN protocol evaluation. In Proceedings of [42] Bi Zhao and Vasilis Friderikos. Optimal stopping for energy the 2nd international conference on simulation tools and tech- efficiency with delay constraints in cognitive radio networks. In niques, page 55. ICST (Institute for Computer Sciences, Social- Personal Indoor and Mobile Radio Communications (PIMRC), Informatics and Telecommunications Engineering), 2009. 2012 IEEE 23rd International Symposium on, pages 820–825. [26] T Kontos, C Anagnostopoulos, E Zervas, and S Hadjiefthymi- IEEE, 2012. ades. Adaptive epidemic dissemination as a finite-horizon opti- [43] Dong Zheng, Weiyan Ge, and Junshan Zhang. Distributed op- mal stopping problem. Wireless Networks, pages 1–18, 2018. portunistic scheduling for ad hoc networks with random access: [27] Jérémie Leguay, Pan Hui, Jon Crowcroft, James Scott, An optimal stopping approach. IEEE Transactions on Infor- Anders Lindgren, and Timur Friedman. CRAWDAD mation Theory, 55(1):205–222, 2009. dataset upmc/content (v. 2006-11-17). Downloaded from [44] Gjergji Zyba, Geoffrey M Voelker, Stratis Ioannidis, and http://crawdad.org/upmc/content/20061117, November 2006. Christophe Diot. Dissemination in opportunistic mobile ad- [28] Yong Li, Pan Hui, Depeng Jin, Li Su, and Lieguang Zeng. Eval- hoc networks: The power of the crowd. In INFOCOM, 2011 uating the impact of social selfishness on the epidemic rout- Proceedings IEEE, pages 1179–1187. IEEE, 2011. 15