{'fraction_non_alphanumeric': 0.026727181038830056, 'fraction_numerical': 0.015560838556299979, 'mean_word_length': 4.973321858864027, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Performance Comparison of Deterministic and Stochastic Utility Ascent Routing Algorithms in Opportunistic Mobile Networks

Opportunistic mobile networks (OMNs) are a class of MANETs where complete endto-end paths rarely exist between sources and destinations; consequently, the end-to-end delays in these networks are much greater than typical MANETs. In this harsh environment networking algorithm actions and decisions are inherently local; the algorithms are mostly greedy, choosing the best solution among the locally ones. In this paper, we study the delivery performance of two classes of gradient utility ascent routing algorithms, deterministic (greedy) and stochastic utility ascent ones, in OMNs. We furthermore discuss the impact of these algorithms on traffic load distribution fairness among the network nodes, since this issue is critical in mobile networking whose nodes typically possess limited resources, e.g. power and storage capacity. Using simulation, driven by real human mobility traces, we investigate the performance of greedy ascent algorithms, Hill Climbing (HC) and Delegation Forwarding (DF), compared with that of stochastic ascent algorithms, Simulated Annealing (SA). The results under the scenario show an advantage of SA over HC and DF in terms of total delivered messages, average delivery delay, and traffic distribution fairness; however, SA negatively impacts the delivery cost performance, i.e. increasing the total message copies beyond those of HC and DF.


Introduction
In recent years opportunistic mobile networks (OMNs) have gained popularity in research and industry as a natural evolution from mobile ad-hoc networks (MANETs). OMNs maintain the MANET's basic features of cost-efficiency and self-organization, as nodes still self-organize in order to build multi-hop message transfers without requiring any pre-existing infrastructure. However, they completely redesign the characteristics of networking protocols proposed in MANETs, making them able to support communications between pairs of nodes, despite the lack of end-to-end paths. By introducing redundancy, e.g. message replication [1] and node contact prediction algorithms [2], messages can be delivered over a sequence of node contacts. Multi-hop message routing over these frequently disconnected networks however poses significant challenges: the volatile nature of these networks, the long transfer delay to learn the state of all nodes in the network, and the cost of flooding node state data over the network imply that conventional routing algorithms requiring global network state are costly and suboptimal, as they may rely on obsolete data. Consequently, the majority of routing algorithms proposed for OMNs are intuitive heuristics or greedy strategies that select optimal relays based on locally available knowledge. Routing problems in OMNs can be formulated as an optimization problem over the connectivity graph [3]. In traditional optimization problems, local search methods define a neighborhood of solutions around the current solution, evaluate all the neighbors, and finally "move" towards the best one therein. In the context of opportunistic networking optimization, however, optimization algorithms should be distributed among the network nodes and the solution space traversal over the network is dictated by node mobility; as a result, the "local" neighborhood of every node state constantly changes over time.
In this paper, we discuss two classes of gradient ascent optimization algorithms, namely deterministic (greedy) and stochastic utility ascent algorithms, as optimal relay selection strategies in OMNs. In the greedy ascent algorithms, when a node contact occurs the algorithm moves a (copy) message to the peers whose utility is higher than that of the forwarding node. Unlike the greedy algorithms, in contrast, the stochastic ascent algorithms allow moves to lower utility nodes but calibrate the probability of such moves as to provably converge to an optimal solution (i.e. messages arrive at the highest utility nodes).
The authors in [3] developed a mathematical model to study the performance of greedy and stochastic utility ascent algorithms in OMNs, evaluated in terms of convergence probability and delay. In this paper, on the other hand, we use computer simulation to investigate the delivery performance of greedy utility ascent forwarding algorithms, Hill Climbing (HC) and Delegation Forwarding (DF), compared with that of stochastic utility ascent algorithms, Simulated Annealing (SA), in terms of total delivered messages, average transfer delay, and delivery cost. In addition, we also discuss the impact of these algorithms on traffic load distribution fairness among the network nodes, since this issue is critical in the context of mobile networking whose nodes typically possess limited resources, e.g. battery and storage capacity.
The rest of the paper is structured as follows. Section 2 gives an overview of gradient utility ascent routing algorithms. Section 3 describes the simulation setup for evaluating the performance of these algorithms in real-life OMNs. A performance comparison of the greedy utility ascent (HC and DF) and stochastic utility ascent (SA) algorithms is reported in Section 4. Finally, Section 5 concludes the paper.

Deterministic (greedy) utility ascent algorithms
Greedy utility ascent algorithms in OMNs locally try to increase the utility of the current configuration at each opportunistic node contact until the (message) copies arrive at the highest utility nodes or no further improvement is possible. For these algorithms, we consider two variants: Hill Climbing (HC) and Delegation Forwarding (DF).
HC is a simple forwarding algorithm in that it greedily moves a (copy) message to a higher utility node at every node contact. For example, as depicted in figure 1, when a node contact occurs, S transfer its (copy) message M1 to the peer whose utility is higher than S's (in this case, A and G). The peer subsequently forwards the message to the neighbors with a higher utility, and this continues until the message arrives at the highest utility node. However, as we can see from figure 1 HC may fail to reach an optimal relay node (node E) due to the existence of local maxima. In the optimization theory, local maxima are states whose utilities are higher than any other state in its local neighborhood. Moreover, the convergence probability to an optimal solution of gradient ascent algorithms in OMNs has been thoroughly studied in [3].
The second variant of the greedy ascent algorithms is Delegation Forwarding (DF) [4], a forwarding strategy that applies the optimal stopping theorem from the probability theory. The algorithm works as follows: as shown in figure 2, S initially creates a new message M1 with the message utility value is set to "0" and next meets G during its mobility (we define "message utility" as the highest node utility of all the nodes seen by the message so far). Since G's utility is higher than S's, S then updates M1's utility with G's utility value and forwards a M1 copy to G afterwards. In the subsequent contact, S encounters A who has a utility value higher than S's, but S now will not transfer the message to A since A's utility is lower than the message's utility. However, when S subsequently meets K who has a utility value higher than both S's and M1's, S then updates the M1's utility and promptly sends the message copy to

Stochastic utility ascent algorithms
Unlike the greedy utility ascent algorithms, a stochastic utility ascent routing algorithm allows a forwarding node to transfer its message to a lower utility node. By introducing randomization, the algorithm is able to escape local maxima and to explore additional configurations; this however would not guarantee convergence. Consequently, the algorithm calibrates the probability of such moves so as to provably converge to an optimal solution (i.e. the message arrives at the highest utility node): when node A is in contact with B, the probability of A forwards its message to B is then given as where and are utility of node A and B, respectively, and T is a system parameter. For a small T, the algorithm surely converges to an optimal solution, but the convergence time increases. On the other hand, for larger value of T the algorithm will escape local maxima easier but less optimal configurations will have a higher probability to appear. To address these difficulties, a simulated annealing (SA) [5] strategy is used, where in the beginning temperature T is a relatively high but gradually cools down. Moreover, theoretical results showed that appropriate cooling schedules (e.g. logarithmic) guarantee to find a global optimum [6].

Simulation Setup for Evaluating Gradient Utility Ascent Algorithms in OMNs
We now discuss the choice of simulation scenarios, evaluation metrics, and node utility calculation used in this study. We implement all the routing algorithms using the ONE simulator [7], an event-driven simulator for mobile opportunistic networks. In our simulations, the number of nodes and the length of simulation time vary depending on the node mobility scenarios. The node buffer size and the message size are set to 20 MB and 4 kB, respectively. The simulations were run 10 times for all the algorithms with different random number seeds.
For the simulation's node mobility scenario, we use real human contact traces, namely Infocomm [8] and Reality [9] datasets. In Infocomm, 41 iMote Bluetooth-enabled devices were distributed to attendees at the IEEE Infocomm conference in Miami in 2005. These devices recorded the human contacts occurred during the 3-day seminar. In Reality, on the other hand, 100 smart phones were deployed among the students and staffs of MIT over period of 9 months. These phones were running software that logged contacts with other phones, capturing academic activities in the campus over an academic year.
For performance analysis, we consider several evaluation metrics as follows: (i) total delivered messages, which is the number of messages received by the destinations; (ii) total message copies, which quantifies the number of message copies created during the simulation time; (iii) average delivery To calculate node utility (i.e. node quality as a potential message carrier), we consider SimBet [10] algorithm. SimBet uses both betweeness centrality (calculated in an ego network) and neighbor similarity (i.e. the number of common neighbors between nodes in the network) to identify optimal relays for message transfers. Nodes with high betweeness centralities are those that can act as bridges for message transfers, while nodes with high similarities with the destination are most likely to find a common neighbor with the destination that can act as a carrier. Finally, node A computes its SimBet utility as a weighted combination of the betweness and similarity utilities, with a tuneable parameter α that adjusts the relative importance of the two utilities as follows:

Simulation Results
In this section, we present the simulation results that compare the performance of the greedy utility ascent algorithms (HC and DF) with that of the stochastic utility ascent algorithm (SA) in real-life OMNs based on the four considered evaluation metrics.   Figure 3 compares the number of messages successfully delivered to the destinations by all the algorithms with respect to total number of node contacts in Infocomm and Reality. Clearly, SA outperforms both HC and DF in total delivered message performance, with the performance difference is more obvious in Reality. However, as shown in figure 4 the SA's high delivery success rate comes at a price as it increases delivery cost (measured in total created message copies) beyond those of HC and DF in both datasets. As we noted, SA allows a forwarding node to send its (copy) message to lower utility nodes, leading to the increase of total message copies traversed in the network; this in turn improves the probability of the message to arrive at the destination. In contrast, DF is able to keep the total message copies significantly low throughout the simulation time, but it produces the lowest delivery success rate among the other algorithms. Thus, we see a trade-off between delivery success rate and delivery cost performance.  In delivery latency performance, on the other hand, we see in figure 5 that SA is able to deliver messages to the destinations in a relatively shorter delay than the greedy ascent algorithms (HC and DF) in both contact datasets. The explanation of this is similar to that given in SA's delivery success rate performance: since SA produces total message copies higher than those of HC and DF, this eventually increases the probability of a message to encounter the destination in a short delay.
Finally, figure 6 depicts the traffic load distribution fairness among nodes in Reality (due to space limitations, we omit the figure for Infocomm). It is clear that both HC and DF are likely to overburden higher utility nodes with relay messages, and DF performs poorer as it loads a few nodes with bulk of network traffic. Furthermore, we show in figure 7 the distribution of total direct message forwards to the destinations by nodes in Reality. In the case of HC and DF, obviously, a few nodes perform a large number of direct forwards. In contrast, the direct forwards is distributed more evenly in SA, meaning that more relay nodes, including possibly lower utility nodes, have an opportunity to forward the (relay) messages directly to the destinations.  6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 87 88 89 90 91 92 93 94