Sage Journals: Discover world-class research

Abstract

This work focuses on delay-tolerant networks in a social network environment. The nonexistence of end-to-end path between the source and the destination poses great challenges to the successful message transmission in delay-tolerant networks. In this article, we attempt to find a socially connected path above the intermittently connected physical topology. To this end, we study a weighted community graph model, which turns the original network into a network composed of communities and then describes the interaction delays between these communities. By performing a Dijkstra algorithm on this community graph, the expected minimum transmission delay to a destination community can be computed. To improve the performance on delivery delay, we propose a social routing called weighted community graph–based social routing that makes use of interaction delays between communities and social ties among nodes, which consists of two routing phases. In inter-community routing phase, messages are forwarded to its destination communities based on the computed minimum delays, and then in intra-community routing phase, each copy is forwarded within a destination community based on the social ties between nodes until meeting the final destination. Extensive simulations are conducted and the results show that weighted community graph–based social routing can improve routing performance, especially the performance on delivery delay and overhead ratio.

Keywords

Delay-tolerant networks community graph social routing routing performance delivery delay

Introduction

Traditional communication model is based on some inherent network assumptions, such as the existence of end-to-end path, low delivery latency, and symmetrical bidirectional data transfer rate. Under these assumptions, traditional TCP/IP-based routing protocols are able to shield heterogeneous networks and communicate across multiple regions. However, such assumptions do not hold in delay-tolerant networks (DTNs),¹ an emerging network architecture for challenging environment such as vehicular ad hoc networks,² mobile social networks,³ and under water sensor networks.⁴ To deal with this problem and provide high-quality communication services, DTN routing adopts the store-carry and forward mechanism (i.e. exploiting the opportunistic contacts and node mobility to relay and carry messages around the network) to spread messages hop by hop. In this case, message transmission relies on other nodes to act as relays, carrying messages between the source and the destination.

Numerous routing algorithms have been proposed to address this difficult routing problem, such as Epidemic Routing and Spray and Wait. These “naive” routing schemes do not keep track of information about the network and choose relay nodes purely based on contact opportunities. For example, in Epidemic Routing, each node simply replicates each message it receives to all nodes it encounters. Spray and Wait limits the maximum number of message copies in the spray phase and directly transmit messages in the wait phase. Recently, more efficient routing schemes that utilize learned information (e.g. history state, utility metric, and knowledge oracles)^5–8 or network coding techniques⁹ have been proposed. DTN-Flow⁵ maintains nodes’ transiting probabilities among different geographical sub-areas and chooses nodes that are most likely to move to the proximity of destination node as relay nodes. It is shown that this scheme can not only reduce transmission delay but also improve delivery rate. EERP⁶ is done on the basis of intensity of received signals and messages are forwarded by the sensor node which has the maximum intensity of received signal from the object. Theoretical analysis and simulation results show that the protocol can reduce energy consumption and message transmission delay. Liu et al.⁷ proposed a centralized optimization model that offers theoretic insights and developed a distributed data query protocol, which minimizes the total communication cost. DSearch⁸ tracks the destination node with the geographical transiting information and nodes’ long-term staying probabilities, achieves greater transmission reliability than routing schemes that only use geographical information or meeting probabilities. All these schemes achieve improvement in delivery ratio and transmission delay; however, they do not consider the social aspects of the underlying network environment and may increase the difficulty of executing these algorithms in reality.

The state of the art in DTN routing is to leveraging social properties and human mobility to predict future contacts and therefore improve routing performance. Social network analysis (SNA) has been recently applied to perform such prediction. SNA provides an approach to analyze the social properties of humans such as social tie, community, and similarity. Based on these social properties, we can build a social graph which describes the social distances or ties between nodes. We can then search this graph to find an end-to-end “social” path between the source and the destination. The reason why we call the path “social” is that the path is socially connected (i.e. neighboring nodes along the path have certain social ties or are socially connected for common interest), but may not be physically connected. In fact, we can take a new viewpoint on the connectivity among nodes instead of the traditional one. Two nodes are also considered connected if they will meet each other in a very short period of time or if they have regular contacts with each other. Essentially, two nodes with strong social tie are very possible to contact each other in the near future, for example, two acquaintances usually come into contact with each other regularly. So from this new point of view, we can think the found social path is end-to-end connected. Then, in the social graph, we can find the best path to transfer message as long as the weights assigned to edges accurately reflect the strength of the social ties between nodes. In this sense, social graph provides an efficient way to overcome the intermittently connected physical topology.

However, for networks with a large number of nodes, the resulting social graphs (a complete graph with one vertex per network node) will have a large number of vertices and edges. Even if we only add the regular edges into the graph, the cost to search the whole graph is still high. In application scenarios where nodes have constrained resource, each node may not have enough computing capacity to perform the path discovery operation in the graph. Consequently, a simplified social graph model could be used instead.

In this article, we propose to model the DTN as a weighted community graph model. In the community graph model, the original network is turned into a network composed of communities. The weight of the edge between two communities describes their interaction delay, the weight of the edge within a community describes the strength of social tie between each pair of nodes with the community. By performing a Dijkstra shortest path algorithm on this model, we can derive the optimal relay set that the expected minimum transmission delay to a destination community, and by solving the associated maximum social tie strength with destination node problem, we can derive the optimal relay set within a community. Then, we propose an optimal opportunistic forwarding routing scheme which uses these two optimal relay sets. And finally based on this graph model, we propose a weighted community graph–based social routing (WCGSR) to improve routing performance in DTNs.

The main contributions of this work are summarized as follows:

To reduce the cost of searching the whole network and simplify the network model, we present a weighted community graph model and extend the interaction delay concept from a pair of nodes to a group of nodes. Besides, an evaluation criterion called social tie strength is proposed for evaluating social tie between nodes, and we use it as the next hop node’s selection condition within community.

We present a rule of optimal opportunistic forwarding routing through a theoretical analysis. We design two optimal opportunistic routing algorithms to determine the optimal relays and compute the minimum expected delivery delay. Based on this, the WCGSR algorithm can achieve the optimal routing performance.

We can simplify the original network by virtue of the weighted community graph model. We prove that the simplification does not affect the routing performance. Moreover, we extensively evaluate our proposed algorithm in a Helsinki City model–based mobility scenario and compared with several existing schemes. The simulation results obtained demonstrate the effectiveness of our algorithm.

The rest of this article is organized as follows. In section “Assumptions and notations,” we present our assumptions and explain the main notations used in this article. In section “Community graph model,” we present the two graph models: inter-community graph and intra-community graph. In section “Detailed routing design,” we present in detail the WCGSR. In section “Performance analysis,” we analyze the delivery delay and advantages of WCGSR. The performance evaluations and comparisons are presented in section “Simulation.” In section “Related work,” an overview of related work is presented. In section “Conclusion,” we conclude the work and discuss our future research direction.

Assumptions and notations

Before introducing the detailed framework, we first make the following assumptions:

The original network includes $| V |$ mobile human nodes $V = {v | v ϵ V}$ and these nodes are divided into $| C |$ communities $C = {C_{i} | C_{i} ϵ C, 1 \leq i \leq | C |}$ . Each mobile node $v \in V$ visits a few communities frequently, while visiting other communities rarely. In other words, each mobile node $v \in V$ resides in $n_{v}$ communities, where $1 \leq n_{v} \leq | C |$ and $| C | << | V |$ .

The inter-contact time (i.e. the time interval between two subsequent contacts) between each node pair follows a certain probability distribution (e.g. power law and exponential distribution) or can be accurately estimated by random sampling.

The source (and relays) knows which communities that the destination node belongs to. That is, the message consists of the source, the destination information, and the data to be delivered.

Regarding the first assumption, we can find some prototype networks in real world. For example, the members of the same family, the workers of the same office, and the students in the same class can form a community, and all of them can form such a prototype network. Previous works observed that 50% of mobile users in this network spent 74% of their time at a single access point (AP) to show the characteristic of frequently visiting a few locations.¹⁰ Moreover, many community detection algorithms^11,12 have been recently proposed for the networks without clear community structures. So we can use these algorithms to divide nodes into different communities easily. Regarding the second assumption, many existing works^13–16 have argued this issue, and their conclusions have shown that many human traces follow power law or exponential distribution. In fact, even for the network that inter-contact time does not follow a clear distribution, this assumption is still reasonable. Social relations and behaviors among mobile users are usually long-term characteristics and less volatile than node mobility. In this case, the interactions between nodes are regular and the changing scale of the inter-contact time between same node pair is small. Regarding the third assumption, this assumption is reasonable because the source generally knows some basic information about the destination in message delivery tasks. For example, the destination node can broadcast this information to all communities. A similar assumption is also adopted in previous work.¹⁷

Table 1 explains the notations used in this article.

Table 1.

Mathematical notations.

Notation	Meaning
$V = {v_{1}, v_{2}, \dots}$	The node set in the network
$C = {C_{1}, C_{2}, \dots}$	The community set in the network
$n_{v}$	The amount of the communities that v resides in
$e_{〈 i, j 〉}$	The edge between community $C_{i}$ and community $C_{j}$
$w_{〈 i, j 〉}$	The weight of the edge $e_{〈 i, j 〉}$
$X_{u, v}$	The inter-contact time between $u$ and $v$
$R_{u, v}$	The duration time when $u$ contacts $v$
$R_{m}$	The transmission time of message $m$
$I_{a, b}$	The social tie strength between node part a and b
$E [D_{v \to C_{i}}]$	The expected interaction delay that $v$ contacts the first node in $C_{i}$
$C_{v}^{+} = {v}$	The virtual community that only consists of $v$ itself
$S_{(v)} = {C_{i} \| v \in C_{i}, C_{i} \neq C_{v}^{+}}$	The destination communities that v resides in
$D_{(v, C_{d})}$	The computed minimum transmission delay from $v$ to $C_{d}$ by searching $G^{(v +)}$
$R_{m_{i}}^{(1)}$	The inter-community optimal relay set of $m_{i}$ in the first routing phase
$R_{m_{i}}^{(2)}$	The intra-community optimal relay set of $m_{i}$ in the second routing phase
$N_{(u)} = {v_{1}, v_{2}, \dots}$	The one-hop neighbors of $u$

Community graph model

Social property reflecting the social distance between human nodes provides a new way to characterize the connectivity of DTNs. In this section, taking full use of communities and social ties performed by humans, we introduce a weighted community graph model to assist message transmissions.

Common inter-community graph

Definition 1

Common weighted inter-community graph. A common weighted inter-community graph $G = 〈 C, W 〉$ is a social graph, in which all $| C |$ communities are included and the weight of each edge describes the average delay it takes to transfer a message from one community to another one.

As we focus on the usage of community graph in social routing, we assume the communities have been detected using any existing community detection algorithm. Now, the key issue is to compute a weight for each edge.

Definition 2

For two communities $C_{i} = {u_{1}, \dots, u_{m}}$ and $C_{j} = {v_{1}, \dots, v_{n}}$ , we treat the contact that node $u \in C_{i}$ meets the first node in $C_{j}$ as one interaction between $u$ and $C_{j}$ . With this interaction, $u$ can transfer a message to $C_{j}$ . The time this transmission consumes is equal to the interaction delay between $u$ and $C_{j}$ (i.e. the delay that $u$ contacts the first node in $C_{j}$ ). A given message will be forwarded to a node in $C_{i}$ randomly, so any node in $C_{i}$ may undertake this transmission task. Therefore, we define the weight $w_{〈 i, j 〉}$ of the edge $e_{〈 i, j 〉}$ between $C_{i}$ and $C_{j}$ as the average weighted of the interaction delays between each node $u \in C_{i}$ and $C_{j}$ .

Now with the above definition, we can compute $W = {w_{〈 i, j 〉} | C_{i} \in C, C_{j} \in C}$ for $G = 〈 C, W 〉$ by the following lemmas.

Lemma 1

For $C_{i} = {u_{1}, \dots, u_{m}}$ and node $v \notin C_{i}$ , we have the expected interaction delay $E [D_{v \to C_{i}}]$ that $v$ contacts the first node in $C_{i}$ , that is

E [D_{v \to C_{i}}] = \frac{1}{\sum_{u \in C_{i}} \frac{1}{E [X_{v, u}]}}

(1)

Proof

As shown in Figure 1, we can treat $C_{i}$ as a virtual node and then the contact between $v$ and any node $u \in C_{i}$ is seen as a contact between $v$ and the virtual node. Assume that $v$ in average contacts $u γ_{(v, u)} = 1 / (E [X_{v, u}] + E [R_{v, u}])$ times in one time unit, where $X_{v, u}$ denotes the inter-contact time between $v$ and $u$ , and $R_{v, u}$ denotes their contact duration time. Then, $v$ is considered to contact the virtual node $\sum_{u \in C_{i}} γ_{(v, u)}$ times within one time unit. Considering that $R_{u, v}$ is usually small and can be ignored compared to $X_{u, v}$ , we have $γ_{(u, v)} \approx 1 / (E [X_{u, v}])$ approximately. In this manner, we have $E [D_{v \to C_{i}}] \approx 1 / (\sum_{u \in C_{i}} γ_{(v, u)}) \approx 1 / (\sum_{u \in C_{i}} (1 / E [X_{v, u}]))$ .

Figure 1.

See community $C_{i}$ as a virtual node.

Lemma 2

For the edge $e_{〈 i, j 〉}$ between $C_{i}$ and $C_{j}$ in $G = 〈 C, W 〉$ , we have the weight

w_{〈 i, j 〉} = \frac{| C_{i} |}{\sum_{\begin{array}{l} u \in C_{i} \\ v \in C_{j} \end{array}} \frac{1}{E [X_{u, v}]}}

(2)

Proof

As shown in Figure 2, considering all interactions between each $u \in C_{i}$ and $C_{j}$ , we have the weighted average interaction delay

w_{〈 i, j 〉} = \sum_{u \in C_{i}} \frac{γ_{(u, C_{j})}}{\sum_{a \in C_{i}} γ_{(a, C_{j})}} E [D_{u \to C_{j}}] \approx \frac{| C_{i} |}{\sum_{a \in C_{i}} \frac{1}{E [D_{a \to C_{j}}]}} = \frac{| C_{i} |}{\sum_{\begin{array}{l} a \in C_{i} \\ v \in C_{j} \end{array}} \frac{1}{E [X_{a, v}]}}

(3)

where $γ_{(u, C_{j})} \approx 1 / (E [D_{u \to C_{j}}])$ denotes the average count that $u$ interacts with $C_{j}$ with one time unit.

Figure 2.

The weight for the edge between $C_{i}$ and $C_{j}$ .

Lemma 3

The proposed weighted inter-community graph $G = 〈 C, W 〉$ is a directed complete graph with $| C |$ communities and ${| C |}^{2}$ edges.

Proof

According to Lemma 2, when $| C_{i} | \neq | C_{j} |$ , we have

w_{〈 j, i 〉} = \frac{| C_{j} |}{\sum_{\begin{array}{l} v \in C_{j} \\ u \in C_{i} \end{array}} \frac{1}{E [X_{v, u}]}} \neq w_{〈 i, j 〉}

(4)

which proves in theory that $G$ is a directed graph. And then taking all $C_{| C |}^{2} = (| C | (| C | - 1)) / 2$ community pairs into consideration, there are $A_{| C |}^{2} = | C | (| C | - 1)$ edges among the $| C |$ communities.

Extended inter-community graph

Definition 3

The extended weighted community graph for node $v$ , $G^{(v +)} = 〈 C^{(v +)}, W^{(v +)} 〉$ , is created by extending the community graph $G = 〈 C, W 〉$ by adding a virtual community composed of $v$ itself, and adding edges from $v$ pointing to the existing $| C |$ communities.

Note that for each node in the network, there is such an extended weighted graph. In the original graph $G = 〈 C, W 〉$ , the weights of edges are the weighted average interaction delay between nodes from the communities. When making routing decisions at a particular node $v$ , we need to perform a shortest path search from node $v$ to the destination node within the whole network. For this reason, we add a virtual community to represent node $v$ into the graph.

To construct $G^{(v +)} = 〈 C^{(v +)}, W^{(v +)} 〉$ , we treat $v$ as a virtual community $C_{v}^{+} = {v}$ , then we get $C^{(v +)} = C + C_{v}^{+}$ and $W^{(v +)} = W + {w_{〈 v, i 〉} | C_{i} \in C}$ . Now we only need to compute the weight $w_{〈 v, i 〉}$ for $C_{v}^{+}$ and $C$ $(C = {C_{i} | C_{i} ϵ C, 1 \leq i \leq | C |})$ . Considering that $C_{v}^{+}$ only consists of $v$ itself, the weight $w_{〈 v, i 〉}$ is defined as follows.

Definition 4

The weight $w_{〈 v, i 〉}$ for the edge from the virtual community $C_{v}^{+}$ to the community $C_{i} \in C$ is defined as the expected delay that $v$ contacts the first node in $C_{i}$ .

For convenience, here we define a community set $S_{(v)} = {C_{i} | v \in C_{i}, C_{i} \neq C_{v}^{+}}$ . For each $C_{i} \in S_{(v)}$ , we have $C_{i} \cap C_{v}^{+} = {v}$ and $w_{〈 v, i 〉} = 0$ . This is because that $v$ resides in the two communities, and for a given message carried by $v$ , the delay from community $C_{v}^{+}$ to community $C_{i}$ is considered 0. For each $C_{i} \in C - S_{(v)}$ , we have $w_{〈 v, i 〉} = E [D_{v \to C_{i}}] = 1 / (\sum_{u \in C_{i}} (1 / E [X_{v, u}]))$ according to Lemma 1. Assume $v \in C_{i}$ and $v \notin C_{j}$ , if $w_{〈 v, j 〉} > w_{〈 i, j 〉}$ , there is at least a node $u \in C_{i}$ which can further reduce the interaction delay with $C_{j}$ , that is, $E [D_{u \to C_{j}}] < E [D_{v \to C_{j}}]$ . That is to say, $u$ can reduce the delay to transfer the message to $C_{j}$ through $C_{i}$ .

Now with $G^{(v +)} = 〈 C^{(v +)}, W^{(v +)} 〉$ , the original network with $| V |$ nodes and ${| V |}^{2}$ edges is turned into a network with $| C |$ communities and ${| C |}^{2}$ edges, where $| C | << | V |$ and ${| C |}^{2} << {| V |}^{2}$ . Consequently, the consumption of network resources (e.g. computing capability, storage, and energy) is greatly reduced. And the cost to search the whole network can be reduced to $O ({| C |}^{2} lo g^{| C |})$ compared to the cost $O ({| V |}^{2} lo g^{| V |})$ in the original network.

Estimate inter-contact time

To compute $W^{(v +)}$ for $G^{(v +)}$ , which can be estimated either by the assumption about the inter-contact time distribution (as described in the Assumption) or measurement. For example, for a pair of nodes $u$ and $v$ , we collect samples of the inter-contact time randomly using a time window. We describe two different time windows that can be adopted for this:

Sampling by growing time window. Samples of the inter-contact time between $u$ and $v$ are collected continuously from the very beginning. All collected samples are used to estimate $E [X_{u, v}]$ . The main idea of this approach is to use as many samples as possible to increase the accuracy of the estimation.

Sampling by sliding time window. In this approach, a pre-set time window is used to restrict the sample data. Only the samples collected in current time window will be used to compute $E [X_{u, v}]$ . This approach is to use the most recent sample datum to accurately estimate $E [X_{u, v}]$ .

In the above approaches, we need to set a variable $n_{u, v}$ for each node pair to record the current amount of the samples we have collected. Then, when getting a new sample data $x_{u, v}$ , we do

E [X_{u, v}] = \frac{E [X_{u, v}] n_{u, v} + x_{u, v}}{n_{u, v} + 1}

(5)

n_{u, v} = n_{u, v} + 1

(6)

This variable ensures that there is no need to store old sample data, which greatly saves the cache resource and makes the continuous sampling possible.

Intra-community graph

A community essentially consists of a set of nodes that frequently visit a common geographic location. Each node is more closely associated with nodes from the same community than nodes from other community. To route message among nodes within the same community, we need to estimate the likelihood of each node (community member) to deliver a message to the destination. For this purpose, we build an intra-community social graph which describes the social ties between nodes. Intuitively, within a community, frequent communications between nodes indicate higher encountering probability and existence of a strong tie between the nodes. For instance, students in the same laboratory have a higher chance to see each other than the students from other laboratories. Here, to illustrate this point, Figure 3 shows an example of encounter frequency in different communities. In this example, Professor 1 has two students, 1 and 2, and Professor 2 has two students, 3 and 4. Every week, each individual’s contact time is shown in Figure 3. Professors contact their own students more frequently than another laboratory’s students. Students tend to contact students on their own team more frequently than students on a team different from their own. Furthermore, social-based algorithms (e.g. Bubble Rap¹⁸ and SimBet¹⁹) have shown their superiority in choosing the most appropriate relay nodes by exploiting social ties such that messages are sent to those nodes well socially connected with their destinations. Therefore, routing based on an intra-community graph with social tie weights can significantly reduce delivery delay.

Figure 3.

An example of encounter frequency in different communities.

To accurately capture social ties between nodes, we consider the following two behavioral features of friendship: frequency and longevity. A stronger social tie between nodes means more frequent encounters and encounters of longer duration. Previous social-based routing schemes (such as Bubble Rap¹⁸) took into account some of these features, but not all at the same time. In contrast, we define the following metric to reflect the social ties more accurately using both features.

Definition 5

Social tie strength. For each node pair a and b of the same community, we use the statistical analysis methods to compute the social tie strength $I_{a, b}$ . For this purpose, each node maintains a matrix $M_{a}^{CDT}$ as illustrated in Formula (7), where $R_{a, b}^{k}$ denotes the kth sample of contact duration between node a and node b within a period of time T. Based on these samples, we use Formula (8) to estimate the quality of connection between node a and b. Here, $φ_{a, b}^{k}$ denote whether the kth contact between node a and b is stable (with a value of 1) or nor (with a value of 0), and $R_{m}$ denotes the transition time of message $m$ . Finally, the social tie strength $I_{a, b}$ characterized by the total number of stable connection times between node a and b is calculated using Formula (9)

M_{a}^{CDT} = (\begin{matrix} 1 & \dots & k & \dots & n \\ R_{a, 1}^{1} & \dots & R_{a, 1}^{k} & \dots & R_{a, 1}^{n} \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ \\ R_{a, b}^{1} & \dots & R_{a, b}^{k} & \dots & R_{a, b}^{n} \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ \\ R_{a, | V |}^{1} & \dots & R_{a, | V |}^{k} & \dots & R_{a, | v |}^{n} \end{matrix})

(7)

φ_{a, b}^{t} = {\begin{matrix} 1, & if R_{a, b}^{t} \geq R_{m}, 1 \leq t \leq n \\ 0, & otherwise \end{matrix}

(8)

I_{a, b} = {\begin{matrix} I_{a, b} + 1, & if ϕ_{a, b}^{t} = 1, 1 \leq t \leq n \\ I_{a, b}, & otherwise \end{matrix}

(9)

Definition 6

The weight $w_{〈 a, b 〉}$ for edge within community is defined as the social tie strength between node pair a and b

R_{C_{i}} = \begin{matrix} v_{0} \\ v_{1} \\ v_{2} \\ v_{3} \end{matrix} (\begin{matrix} v_{0} & v_{1} & v_{2} & v_{3} \\ \infty & 6 & 4 & 0 \\ 6 & \infty & 5 & 3 \\ 4 & 5 & \infty & 1 \\ 0 & 3 & 1 & \infty \end{matrix})

(10)

We can use a matrix to represent the social tie strength between different pairs of nodes within a community. Matrix $R_{C_{i}}$ in Formula (10) illustrates such an example, where the $v_{0}$ row and $v_{1}$ column element of the matrix is the social tie strength between node $v_{0}$ and $v_{1}$ . A value of $\infty$ in the diagonal line represents that each node has a stable connection with itself. The intra-community graph corresponding to the community illustrated in Formula (10) is shown in Figure 4.

Figure 4.

Intra-community $C_{i}$ graph.

Inter-community optimal relay set

Definition 7

Inter-community optimal relay set. For a message $m_{i}$ destined for community $C_{d}$ , its inter-community optimal relay set for routing in the first phase is defined as $R_{m_{i}}^{(1)}$ . Assuming node $v$ carries the message, then a node $u$ is added to $R_{m_{i}}^{(1)}$ if and only if $D_{(u, C_{d})} < D_{(v, C_{d})}$ , where $D_{(u, C_{d})} = \sum_{e_{〈 i, j 〉} \in S P_{(u \to C_{d})}} w_{〈 i, j 〉}$ and $S P_{(u \to C_{d})}$ denotes the shortest path from $C_{u}^{+} = {u}$ to $C_{d}$ in $G^{(u +)}$ .

Here, the threshold value for determining whether a node should be added to $R_{m_{i}}^{(1)}$ depends on the current carrier of the message, $v$ . Once a new relay $u$ is selected, the new threshold is set to $D_{(u, C_{d})}$ . As relay selections process continues, the set $R_{m_{i}}^{(1)}$ is updated continuously.

Intra-community optimal relay set

Definition 8

Intra-community optimal relay set. For a message $m_{i}$ destined for destination $d \in C_{d}$ , its intra-community optimal relay set for routing in the second phase is denoted as $R_{m_{i}}^{(2)}$ . Assuming that $m_{i}$ has been forwarded to node $v$ that belongs to the same community $C_{d}$ as the destination of the message, a node $u$ is added to $R_{m_{i}}^{(2)}$ if and only if $u \in C_{d}$ and $I_{u, d} > I_{v, d}$ . And as relay selection going on, $R_{m_{i}}^{(2)}$ is also continuously updated.

Optimal opportunistic forwarding routing

According to the above definitions, only nodes that can reduce the transmission delay of a message are added to the optimal relay sets. In the optimal opportunistic forwarding routing scheme, each message carrier delivers messages via its optimal relay set (i.e. $R_{m_{i}}^{(1)}$ and $R_{m_{i}}^{(2)}$ ). Thus, in each step of routing selection, we can ensure

\arg mi n_{v \in V} D_{C_{d}} (v) \in R_{m_{i}}^{(1)}

(11)

\arg ma x_{u \in C_{d}} I_{u, d} \in R_{m_{i}}^{(2)}

(12)

where $D_{C_{d}} (v) = D_{(v, C_{d})}$ . Next, we define optimal forwarding rules.

Definition 9

Optimal opportunistic forwarding routing rule. The optimal forwarding is to forward message to the encountered node that can get the minimum transmission delay to the destination. Concretely, for current carrier $v$ of the message, we define its one-hop neighbors as $N_{(v)} = {v_{1}, v_{2}, \dots}$ . Then, the optimal forwarding in the first phase is to select a relay $u \in (N_{(v)} \cap R_{m_{i}}^{(1)})$ , which can get the minimum $D_{(u, C_{d})}$ . The optimal forwarding in the second phase is to select the node $u \in (N_{(v)} \cap R_{m_{i}}^{(2)})$ that can maximize $I_{u, d}$ as the next relay.

This optimal forwarding rule ensures that each newly selected relay will further reduce the transmission delay of the message. As relay selection continues, $R_{m_{i}}^{(1)}$ and $R_{m_{i}}^{(2)}$ are updated continuously. The two sets become smaller as the message is forwarded closer to the destination community or the destination node.

Detailed routing design

With the above definitions, we now present details of WCGSR. We first present the basic ideas behind the routing scheme, then describe the initialization process, and finally present the two phases of the routing scheme (inter-community and intra-community routing).

Basic routing idea

The basic routing idea of WCGSR is to use long-term social ties of human nodes to forward messages along a socially connected path to the destination. Concretely, each node $v$ performs a Dijkstra algorithm on $G^{(v +)} = 〈 C^{(v +)}, W^{(v +)} 〉$ to find the shortest path to the destination community of the message, and then computes the minimum transmission delay. According to the optimal opportunistic forwarding routing rule, we take measures to spread the message to its destination community as quickly as possible. And then, we forward the message within the destination community until the message is delivered to its destination.

Initialization process

In the initialization stage, all nodes in the network are grouped into communities either by using a certain community detection algorithm or using community-aware opportunistic routing (CAOR),¹⁷ in which nodes visit the same location frequently form a community. In our simulation studies, the communities are formed by nodes with same interest.

Next, nodes exchange its community information with other nodes in the network. In particular, each node maintains a list $〈 C_{i}, C_{j}, \dots 〉$ which stores the communities that it belongs to. Each network node exchanges its list with other nodes. With the lists collected from all other nodes, each node determines the set of communities $C = {C_{1}, C_{2}, \dots}$ in $G = 〈 C, W 〉$ , where each community $C_{i} = {u_{1}, \dots, u_{m}}$ consists of nodes belonging to the community. Subsequently, each node computes the expected inter-contact time with other nodes and exchange this information with other nodes. The following matrix $M_{X}$ is maintained by each node (note that $E [X_{i, i}] = 0$ )

M_{X} = \begin{matrix} v_{1} \\ ⋮ \\ v_{i} \\ ⋮ \\ v_{| V |} \end{matrix} (\begin{matrix} v_{1} & \dots & v_{j} & \dots & v_{| V |} \\ E [X_{1, 1}] & \dots & E [X_{1, j}] & \dots & E [X_{1, | V |}] \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ \\ E [X_{i, 1}] & \dots & E [X_{i, j}] & \dots & E [X_{i, | V |}] \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ \\ E [X_{| V |, 1}] & \dots & E [X_{| V |, j}] & \dots & E [X_{| V |, | V |}] \end{matrix})

(13)

Now with $C$ and $M_{X}$ , each node has constructed the graph $G = 〈 C, W 〉$ , which we illustrate using the adjacency matrix below (note that $w_{〈 i, i 〉} = 0$ and $w_{〈 i, j 〉} \neq w_{〈 j, i 〉}$ )

G = \begin{matrix} C_{1} \\ ⋮ \\ C_{i} \\ ⋮ \\ C_{| C |} \end{matrix} (\begin{matrix} C_{1} & \dots & C_{j} & \dots & C_{| C |} \\ w_{1, 1} & \dots & w_{1, j} & \dots & w_{1, | C |} \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ \\ w_{i, 1} & \dots & w_{i, j} & \dots & w_{i, | C |} \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ \\ w_{| C |, 1} & \dots & w_{| C |, j} & \dots & w_{| C |, | C |} \end{matrix})

(14)

Next, we can obtain the extended inter-community graph for each node $v$ by treating the node as a virtual community. Following the Dijkstra shortest path algorithm on this graph then yields the minimum transmission delay from node $v$ to all other communities in the network.

Inter-community routing

The objective of inter-community routing phase is to forward the message to its destination communities as quickly as possible. The basic idea is to compute the minimum expected delivery delays from one community to the destination communities in an ascending order. In the meantime, when a node $u$ encounters another node $v$ which can achieve shorter delivery delay, node $u$ takes advantage of this opportunity and forward the message to node $v$ .

Concretely, when source $s$ generates a new message $m_{i}$ destined for $d$ , it first gets $S_{(d)} = {C_{i} | d \in C_{i}, C_{i} \neq C_{d}^{+}}$ , and then calls Algorithm 1 with $(s, N_{(s)}, m_{i}, C_{i})$ for each $C_{i} \in S_{(d)}$ . Notice that in Algorithm 1, when source $s$ forwards one copy of $m_{i}$ to a selected relay, the information about the specific destination community $C_{i}$ needs to be encoded into the message copy. This way, the relays know which community this copy is transferred to. When a relay $u \notin C_{d}$ receives a new message $m_{i}$ destined for $C_{d}$ , it also calls Algorithm 1 with $(u, N_{(u)}, m_{i}, C_{d})$ .

Algorithm 1: Inter-community routing
Input: current node: $u$ one-hop neighbors of $u$ : $N_{(u)} = {v_{1}, v_{2}, \dots}$ current message: $m_{i}$ destination community of $m_{i}$ : $C_{d}$ (1) compute $D_{(u, C_{d})}$ ; (2) for each $v \in N_{(u)}$ (3) compute $D_{(v, C_{d})}$ ; (4) if $D_{(v, C_{d})} < D_{(u, C_{d})}$ (5) add $v$ to set $S$ ; (6) forward $m_{i}$ to $\underset{v \in S}{argmin} D_{(v, C_{d})}$ ; (7) return;

Intra-community routing

After a message is forwarded to a node in the destination community, the intra-community routing scheme is used to forward it within the destination community until it is delivered to the destination. The basic idea of intra-community routing is to forward the message to member nodes with a stronger social tie with the destination. This is because that nodes with stronger social ties with the destination has a greater probability to come into contact with the destination in the near future. The details of the relay selections in the second phase are outlined in Algorithm 2.

Algorithm 2: Intra-community routing
Triggering condition: when $u \in C_{d}$ receives a message $m_{i}$ destined for $C_{d}$ $u$ executes: (1) $dest \leftarrow$ destination node of $m_{i}$ ; (2) compute $I_{u, dest}$ ; (3) get its one-hop neighbors $N_{(u)}$ (4) for each $v \in N_{(u)}$ (5) compute $I_{v, dest}$ ; (6) if $I_{v, dest} > I_{u, dest}$ (7) add $v$ to set $S$ ; (8) forward $m_{i}$ to $\underset{v \in S}{argman} I_{v, dest}$ ; (9) return;

Algorithm 2: Intra-community routing

Triggering condition:
when

u \in C_{d}

receives a message

m_{i}

destined for

C_{d}

u

executes:
(1)

dest \leftarrow

destination node of

m_{i}

;
(2) compute

I_{u, dest}

;
(3) get its one-hop neighbors

N_{(u)}

(4) for each

v \in N_{(u)}

(5) compute

I_{v, dest}

;
(6) if

I_{v, dest} > I_{u, dest}

(7) add

v

to set

S

;
(8) forward

m_{i}

\underset{v \in S}{argman} I_{v, dest}

;
(9) return;

Performance analysis

Upper bound of expected delivery delay

In this section, we derive a close formula for the upper bound of expected delivery delay. For a message $m_{i}$ generated by source $s$ and destined to node $d$ , we have $S_{(d)} = {C_{i} | d \in C_{i}, C_{i} \neq C_{d}^{+}}$ . For each $C_{i} \in S_{(d)}$ , we denote by $E [D_{m_{i} \to C_{i}}^{(1)}]$ the expected transmission delay in the first phase, and $E [D_{m_{i} \to d}^{(2)}]$ the expected transmission delay in the second phase. We have

E [D_{m_{i} \to C_{i}}^{(1)}] \leq D_{(s, C_{i})} = \sum_{e_{〈 i, j 〉} \in S P_{(s \to C_{i})}} w_{〈 i, j 〉}

(15)

E [D_{m_{i} \to d}^{(2)}] \leq max_{v \in C_{i}} {E [X_{v, d}]}

(16)

The expected transmission delay along the path $m_{i} \to C_{i} \to d$ is then

\begin{matrix} E [D_{m_{i} \to C_{i} \to d}] = E [D_{m_{i} \to C_{i}}^{(1)}] + E [D_{m_{i} \to d}^{(2)}] \\ \leq max_{v \in C_{i}} {E [X_{v, d}]} + \sum_{e_{〈 i, j 〉} \in S P_{(s \to C_{i})}} w_{〈 i, j 〉} \end{matrix}

(17)

Note that for message $m_{i}$ , there are multiple copies being forwarded simultaneously to different communities that the destination node $d$ belongs to. The delivery delay of message $m_{i}$ is the time elapsed from the generation time of $m_{i}$ to the time a copy of $m_{i}$ is first delivered to the destination. Therefore, we have

E [D_{m_{i}}] \leq min_{C_{i} \in S_{(d)}} {E [D_{m_{i} \to C_{i} \to d}]}

(18)

In addition, based on above analysis, the delivery probability of $m_{i}$ is

P_{m_{i}} = 1 - \underset{C_{i} \in S_{(d)}}{Π} P {E [D_{m_{i} \to C_{i} \to d}] > TT L_{m_{i}}}

(19)

Advantages

In this section, we discuss advantages achieved by WCGSR due to the adoption of extended graph $G^{(v +)}$ and intra-community graph.

First, the community graph model uses a graph composed of $| C |$ communities and ${| C |}^{2}$ edges to represent a network of $| V |$ nodes and ${| V |}^{2}$ edges. With the smaller graph, the cost to search for the shortest paths is greatly reduced. Network nodes consume less energy and computing capacity to compute the minimum transmission delay route to the destination community. Second, the edge weights in $G^{(v +)}$ represent the average interaction delay between two communities, taking into consideration all node pairs between the communities. We note that such metric has less variance than interaction delay between two nodes, leading to a more reliable and stable routing decision. Third, we build a social graph by using the social ties between nodes within the community. Since these frequently visit behaviors indicate the potential social ties between nodes, which show long-term characteristics. For example, the relationship between students in a class is a long-term social characteristic, which would not be violated by the teacher variation. Thus, according to the intra-community graph, we can greatly reduce message transmission delay and improve the message delivery probability. As we demonstrate in simulation studies (Figures 5 –12), our routing scheme demonstrates over perform routing schemes based upon the original network.

Figure 5.

Delivery ratio versus (a) buffer size, (b) message TTL, and (c) message size.

Figure 6.

Overhead ratio versus (a) buffer size, (b) message TTL, and (c) message size.

Figure 7.

Average latency versus (a) buffer size, (b) message TTL, and (c) message size.

Figure 8.

Average hop count versus (a) buffer size, (b) message TTL, and (c) message size.

Figure 9.

Delivery ratio versus (a) buffer size, (b) message TTL, and (c) node number.

Figure 10.

Overhead ratio versus (a) buffer size, (b) message TTL, and (c) node number.

Figure 11.

Average latency versus (a) buffer size, (b) message TTL, and (c) node number.

Figure 12.

Average hop count versus (a) buffer size, (b) message TTL, and (c) node number.

Simulation

In this section, we conduct extensive simulations to compare the performance of WCGSR against CAOR,¹⁷ Bubble Rap,¹⁸ SimBet,¹⁹ and Epidemic Routing.²⁰ We examine four commonly adopted performance metrics: delivery ratio, average latency, overhead ratio, and average hop count.

Our simulation results demonstrate that our proposed scheme significantly improves routing performance. We next describe the routing schemes studied, the simulation setting, evaluation metrics, and simulation results in detail.

Compared routing algorithms

We compared our routing scheme against the following routing schemes: CAOR, SimBet, Bubble Rap, and Epidemic Routing. Both CAOR and SimBet use social property to find a path to the destination, and its relay selection is similar to that of WCGSR. Similar to WCGSR, Bubble Rap is a typical social-based routing, which exploits the concept of community in a different way. Epidemic Routing scheme flood messages to the whole network and achieve the optimal delivery performance in the case where there are sufficient network resources (storage, bandwidth, and energy). In our simulation studies, we assume there is sufficient network resource. As a result, Epidemic Routing achieves optimal delivery performance and serves as a baseline to compare with WCGSR.

Simulation settings

We implement our simulations using the ONE²¹ simulator. We consider a network of 126 DTN nodes in a Helsinki City model–based mobility scenario, the Helsinki City scenario is with 15.3 km² area where 126 DTN nodes are classified as 80 pedestrians at 0.5–1.5 m/s, 40 cars at 2.7–13.9 m/s, and 6 trams at 7–10 m/s. Furthermore, human’s interests to visit places decides the nodes movement. Table 2 summarizes other parameters used in the simulation.

Table 2.

Simulation settings in Helsinki City model.

Parameter	Range
Initial topology	Uniform
Message size	400–900 (KB)
Message interval	10–80 (s)
Node buffer size	20–100 (MB)
Time-to-live (TTL)	100–500 (min)
Node number	200–700
Simulation time	12 h

Evaluation metrics

To evaluate the performance improvements of WCGSR, we focus on the following metrics:

Delivery ratio. The ultimate goal of routing in DTNs is to achieve great delivery performance. This criterion is the measure of delivery capability for a routing scheme. When the network resource is sufficient, Epidemic routing usually has the best delivery performance. This is because Epidemic routing always finds the best possible path to the destination. Therefore, it represents the baseline for the best possible delivery performance.

Overhead ratio. It is desirable to achieve a low overhead ratio, since it reflects the efficiency of message transmission. Overhead ratio is defined to be the number of relay operations over the number of total delivered messages.

Average latency. This metric is another important routing goal. Average latency is the average duration of time elapsed from message generation at the source to message delivery to destination. A lower end-to-end latency means a better routing performance.

Average hop count. Average hop count is the number of hops along the path that a message is delivered.

Comparison with CAOR and SimBet

We compare the performance of different routing schemes under varying node’s buffer size, varying TTL (time-to-live) for messages, and varying message size. In the first category of simulations, we set the message size constant at 600 KB. The buffer size is set from 20 to 50 MB. As shown in Figures 5(b)–8(b), CAOR and SimBet perform well when TTL is less than 300 min. Therefore, we set message TTL at 120 min in the first category and third category of simulations so as to better evaluate WCGSR’s improvements. The simulation results are shown in Figures 5(a)–8(a). In the second category of simulations, we set the buffer size constant and message size constant at 100 MB and 600 KB, respectively. The message TTL is varied from 100 to 500 min. The simulation results are shown in Figures 5(b)–8(b). In the third category of simulations, we set the buffer size constant and message TTL constant at 50 MB and 120 min, respectively. The message size is varied from 400 to 900 KB. The simulation results are shown in Figures 5(c)–8(c).

From Figure 5(a) we find that all algorithms perform well when buffer resources of nodes are sufficient. We also observe that WCGSR significantly outperforms SimBet in delivery ratio and slightly outperforms CAOR also. We think this is because WCGSR takes full advantage of community information and social properties and transfer message to its destination community gradually. So the routing selections are more efficient. In Figure 6(a)–(c), we compare the overhead ratio of the three schemes. We notice from Figure 6(a) that the overhead ratio of all algorithms decreases when a node is equipped with more buffer resources, because larger buffer size leads to copying with a higher overhead ratio (as shown in Figure 5(a)). In Figure 6(b), the overhead ratios of CAOR and SimBet are higher than that of WCGSR. This verifies that WCGSR has a better advantage in reducing the overhead ratio because WCGSR combines nodes’ social attributes and transmission delays to choose the next hop node instead of choosing blindly. Figure 6(c) shows that the overhead ratio of all the algorithms increases with message size greater than 600 KB because the buffer resource is always limited, thus increasing the message size will increase the message loss.

Figure 7(a)–(c) plots the average latency achieved by the three schemes. We observe that WCGSR has a great advantage in terms of average latency, due to the fact that the scheme tries to reduce transmission delay in each step of the relay selection. We also notice that WCGSR achieves a slighter lore latency than CAOR, which demonstrates that relay selection strategies adopted by WCGSR are effective. The simplified network model and the usage of social properties help to find a socially connected path to the destination node, avoiding blind selection and reduce transmission latency.

Figure 8(a)–(c) compare the average hop counts for the three routing schemes under different scenarios. We observe that WCGSR outperforms CAOR in terms of average hop count. This is because that WCGSR takes into account the community as a whole in the inter-community graph and makes use of social tie strengths when performing intra-community routing. These features help to choose the next hop node and also locate the destination from social perspective (other than the current location of the destination). From the above simulation results, we conclude that WCGSR achieves better routing performance than CAOR and SimBet.

Comparison with Bubble Rap and Epidemic

In our simulation studies comparing WCGSR with Bubble Rap and Epidemic Routing, we vary the node’s buffer size, message TTL, and the number of nodes in the network. In the first category of simulations, considering the vast amounts of data transmission tasks in real world and the commonly used multi-copy strategies in DTN routing, these storage resources may still not enough. So in order to evaluate WCGSR’s performance in the case of different storage resources, we change node’s buffer size from 30 to 80 MB while setting the message TTL to 120 min and the node number to 200. From Figure 9(a), it can be seen that with the increase in the buffer resources, the message delivery ratio of all algorithms’ performance goes up, but WCGSR still performs well even with limited buffer resources. In the second category of simulations, we change message’s TTL from 100 to 500 min while setting the buffer size to 100 MB and the node number to 200. As shown in Figure 9(b), WCGSR achieves the highest delivery ratio when message’s TTL is greater than 200 min. In the third category of simulations, we set the message TTL constant at 120 min. We change the node number from 200 to 700. The buffer size is set to 100 MB, which ensures that the other three algorithms can perform well. WCGSR achieves the highest delivery ratio when messages have a small TTL and nodes have sufficient buffer resources.

By locating the destination community of a message, WCGSR can find a socially connected path to the destination, thus overcoming the problem caused by the lacking of connected end-to-end path. As shown in Figure 9(a) and (b), WCGSR is able to improve delivery ratio, especially when messages have a larger TTL. From Figure 9(c), we observe that when node density is low, no routing schemes achieve satisfying delivery ratio, indicating that the successful message delivery depends largely on contacts among nodes. When there are only a small number of nodes in the network, each node has little chance to contact other nodes directly or indirectly. When more nodes are added into the network, the contact probability between nodes is improved. As shown in Figure 9(c), when more nodes are added into the network, all routing schemes achieve higher delivery ratios. From Figure 9(a) and (c) we can also see that more copies are helpful to improve delivery ratio when network resource is sufficient. However, these copies inevitably increase the network overhead ratio. As shown in Figure 10(a)–(c), the overhead ratios of Epidemic and Bubble Rap are higher than that of WCGSR. This also shows that WCGSR achieves a great trade-off between delivery ratio and network overhead ratio. From Figure 11(a)–(c), we observe that WCGSR achieves advantages on average delivery latency compared to the other three algorithms. This indicates that WCGSR can improve the performance on end-to-end latency. The key reason is that, in each step of relay selection, WCGSR tries to further reduce the transmission delay based on the extended graph $G^{(v +)}$ . So these results also show the accuracy and efficiency of our proposed community graph model in aspect of computing end-to-end latency. WCGSR and Bubble Rap both take full use of community information and then try to transfer message to its destination community gradually. So their routing selections are more efficient, and messages take fewer hops to reach the destinations. As shown in Figure 12(a)–(c), WCGSR and Bubble Rap outperform Epidemic Routing in the average hop count. This shows that community information is helpful to locate the destination from social perspective, no matter where the destination is currently located.

Related work

There have been many works proposing routing schemes for DTNs. Most of DTN routing research focus on leveraging contact opportunities, such as flooding-based algorithms (e.g. Epidemic²⁰ and Spray and Wait), the probability-based algorithms,^22–24 and the location-based algorithms.^25,26 Other works introduce additional communication facilities such as message ferry and control nodes into the network. Li et al.²⁴ proposed an optimal opportunistic routing strategy based on a continuous time Markov framework. GeoDTN²⁵ uses historical movement information to predict the possibility of two nodes becoming neighbors and forwards message to nodes more likely to be a neighbor of the destination node. However, these algorithms may increase the resource consumption and the difficulty of executing these protocols in reality.

To reduce computation complexity and achieve good performance in real networks, many social-aware DTN routing schemes have been proposed. These schemes take advantage of social characteristic (such as community, centrality, and similarity) of network nodes to improve delivery performance. Xiao et al.¹⁷ proposed a distributed community-aware opportunistic routing called CAOR. They present a home-aware community model and then turn the network into a network that only includes community homes. Through a reverse Dijkstra algorithm, they compute the minimum expected delivery delay for each node. And then based on the computed delays, they try to find the optimal relays for message transmission so as to achieve the optimal opportunistic routing performance. By simplifying the original network, they greatly reduce the cost of computing and maintaining the contact information among nodes. The SimBet¹⁹ is another social-based routing scheme, using centrality and similarity to find the optimal relays. SimBet estimates the betweenness for each node by considering its local neighbors. A high betweenness means that the node can act as bridges among their neighbors. In addition, SimBet computes a similarity for current node and destination node by considering the amount of common neighbors. A high similarity means that the node is more likely to contact the destination. The two metrics are used to detect the node that provides the maximum utility for transferring messages.

Pan et al.¹⁸ proposed social forwarding strategy called Bubble Rap, which uses the k-clique algorithm to detect a community. Bubble Rap ranks each node by their centrality values and then uses the rank values in the routing decision. Wu and Wang²⁷ proposed a hypercube-based multi-path social feature routing algorithm by taking full use of human contact features. This routing consists of two processes: social feature extraction process and multi-path routing process. In social feature extraction process, they first use Shannon Entropy to capture the $m$ most informative features for building social feature space and then transform the routing problem into a hypercube-based feature matching problem. Then in multi-path routing, they proposed two kinds of multi-path forwarding strategies for message transmission. OFPC²⁸ defines the relative importance of a node to a group of nodes as partial centrality and designs an opportunistic forwarding scheme with the partial centrality, which achieves significantly better delivery delay and cost compared to the state-of-the-art works. Besides, Xia et al.¹¹ studied the replication approaches in ad hoc social network. They propose a new data replication method called ComPAS. This method can significantly improve routing performance by exploiting social relationship while replicating in the community to achieve better efficiency and consistency while keeping the replica relocation cost as low as possible. This type of replica allocation method increases the availability of different data items in a partitioned social community.

In this work, we study the advantage of social network–based routing. We make use of the social properties (community and social tie) and interaction delays to achieve more informed optimal relay set selection. Furthermore, inspired by existing social routing schemes, we design a weighted community graph model and an opportunistic forwarding routing strategy for delivering message from the source node to the destination node.

Conclusion

In this article, we study a social-based routing in DTNs so as to find a socially connected path to the destination over an intermittently connected network. To this end, we introduce a weighted community graph model. Based on the proposed community graph, we propose a social routing called WCGSR, whose routing process consists of two phases. The first phase of WCGSR forward a message to its destination communities based on the computed minimum delays. The second phase forward the message within the destination community based on the social tie strength until the message is delivered to the destination. Extensive simulations have been conducted and the results show that WCGSR is able to improve performance on end-to-end latency and maximizing message delivery ratio.

In order to lower the delivery delay, we compute edge weights in $G^{(v +)}$ based on the interaction delays between communities. Alternatively, we can compute the weights based on the probability that one community can forward a message to another community, if message delivery ratio is the primary performance metric. We plan to study such alternative in our future work.

Footnotes

Handling Editor: Sergio Toral

Declaration of conflicting interests

The author(s) declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Funding

The author(s) disclosed receipt of the following financial support for the research, authorship, and/or publication of this article: This research was supported in part by National Natural Science Foundation of China (nos 61502261, 61572457, and 61379132), Key Research and Development Plan Project of Shandong Province (no. 2016GGX101032), and Science and Technology Plan Project for Colleges and Universities of Shandong Province under Grant No. J14LN85.

References

Soelistijanto

Howarth

. Transfer reliability and congestion control strategies in opportunistic networks: a survey. IEEE Commun Surv Tut 2014; 16(1): 538–555.

Soares

VNGJ

Rodrigues

JJPC

Farahmand

. GeoSpray: a geographic routing protocol for vehicular delay-tolerant networks. Inform Fusion 2014; 15(1): 102–113.

Mao

Jiang

Min

et al . Mobile social networks: design requirements, architecture, and state-of-the-art technology. Comput Commun 2017; 100: 1–19.

Guo

Wang

Cui

. Generic prediction assisted single-copy routing in underwater delay tolerant sensor networks. Ad Hoc Netw 2013; 11(3): 1136–1149.

Chen

Shen

. DTN-FLOW: inter-landmark data flow for high-throughput routing in DTNs. IEEE ACM T Network 2015; 23(1): 212–226.

Kumar

Kant Sahu

Chauhan

. Energy-efficient and reliable routing protocol for wireless sensor networks. Int J Comput Appl 2012; 43(11): 33–37.

Liu

Han

Yang

et al . Efficient data query in intermittently-connected mobile ad hoc social networks. IEEE T Parall Distr 2015; 26(5): 1301–1312.

Chen

Shen

Yan

. DSearching: using floating mobility information for distributed node searching in DTNs. IEEE T Mobile Comput 2016; 15(1): 121–136.

Yang

Gao

Zhou

et al . Delay control in MANETs with erasure coding and f-cast relay. Wirel Netw 2014; 20(8): 2617–2631.

10.

Henderson

Kotz

Abyzov

. The changing usage of a mature campus-wide wireless network. In: Proceedings of the 10th annual international conference on mobile computing and networking (MobiCom 04), Philadelphia, PA, 26 September–1 October 2004, vol. 52, no. 14, pp.2690–2712. New York: ACM Press.

11.

Xia

Ahmed

Yang

et al . Exploiting social relationship to enable efficient replica allocation in ad-hoc social networks. IEEE T Parall Distr 2014; 25(12): 3167–3176.

12.

. LocalCom: a community-based epidemic forwarding scheme in disruption-tolerant networks. In: Proceedings of the 6th annual IEEE communications society conference on sensor, mesh and ad hoc communications and networks (SECON ’09), Rome, 22–26 June 2009, pp.574–582. New York: IEEE.

13.

Jiang

et al . SEBAR: social-energy-based routing for mobile social delay-tolerant networks. IEEE T Veh Technol 2017; 66: 7195–7206.

14.

Zhang

Song

Jiang

et al . A social-aware framework for efficient information dissemination in wireless ad hoc networks. IEEE Commun Mag 2017; 55: 174–179.

15.

Chen

Shang

Wong

et al . Efficient multicast algorithms in opportunistic mobile social networks using community and social features. Comput Netw 2016; 111: 71–81.

16.

Tian

et al . Energy efficient social routing framework for mobile social sensing networks. Tsinghua Sci Technol 2016; 21(4): 363–373.

17.

Xiao

Huang

. Community-aware opportunistic routing in mobile social networks. IEEE T Comput 2014; 63(7): 1682–1695.

18.

Hui

Crowcroft

Yoneki

. Bubble Rap: social-based forwarding in delay tolerant networks. In: Proceedings of the 9th ACM international symposium on mobile ad hoc networking and computing (MobiHoc ’08), Hong Kong, China, 26–30 May 2008, vol. 10, no. 11, pp.241–250. New York: ACM Press.

19.

Daly

Haahr

. Social network analysis for routing in disconnected delay-tolerant MANETs. In: Proceedings of the 8th ACM international symposium on mobile ad hoc networking and computing (MobiHoc ’07), Montreal, QC, Canada, 9–14 September 2007, pp.32–40. New York: ACM Press.

20.

Vahdate

Becker

. Epidemic routing for partially-connected ad hoc networks. Technical report CS-2000-06, June 2000. Durham, NC: Duke University.

21.

Keranen

Ott

Karkkainen

. The ONE simulator for DTN protocol evaluation. In: Proceedings of the 2nd international ICST conference on simulation tools and techniques (Simutools ’09), Rome, 2–6 March 2009, p.55. Brussels: ICST.

22.

Chen

Shi

. Topology control for predictable delay-tolerant networks based on probability. Ad Hoc Netw 2015; 24(3): 147–159.

23.

Lee

Jeong

et al . Max-contribution: on optimal resource allocation in delay tolerant networks. In: Proceedings of the 2010 IEEE INFCOM, San Diego, CA, 14–19 March 2010, vol. 14, no. 3, pp.1136–1144. New York: IEEE.

24.

Jiang

Jin

et al . Energy-efficient optimal opportunistic forwarding for delay-tolerant networks. IEEE T Veh Technol 2010; 59(9): 4500–4512.

25.

Link

JAB

Schmitz

Wehrle

. GeoDTN: geographic routing in disruption tolerant networks. In: Proceedings of the IEEE global telecommunications conference, Houston, TX, 5–9 December 2011, pp.1–5. New York: IEEE.

26.

Alone

Mangrulkar

. Implementation on geographical location based energy efficient direction restricted routing in delay tolerant network. In: Proceedings of the 2014 international conference on power, automation and communication (INPAC), Amravati, India, 6–8 October 2014, vol. 68, no. 1, pp.129–135. New York: IEEE.

27.

Wang

. Hypercube-based multipath social feature routing in human contact networks. IEEE T Comput 2014; 63(2): 383–396.

28.

Yuan

Liu

Tang

. Exploiting partial centrality of nodes for data forwarding in mobile opportunistic networks. In: Proceedings of the 2014 IEEE international conference on computational science and engineering, Chengdu, China, 19–21 December 2014, pp.1435–1442. New York: IEEE.

Weighted community graph–based social routing in delay-tolerant networks

Abstract

Keywords

Introduction

Assumptions and notations

Community graph model

Common inter-community graph

Definition 1

Definition 2

Lemma 1

Proof

Lemma 2

Proof

Lemma 3

Proof

Extended inter-community graph

Definition 3

Definition 4

Estimate inter-contact time

Intra-community graph

Definition 5

Definition 6

Inter-community optimal relay set

Definition 7

Intra-community optimal relay set

Definition 8

Optimal opportunistic forwarding routing

Definition 9

Detailed routing design

Basic routing idea

Initialization process

Inter-community routing

Intra-community routing

Performance analysis

Upper bound of expected delivery delay

Advantages

Simulation

Compared routing algorithms

Simulation settings

Evaluation metrics

Comparison with CAOR and SimBet

Comparison with Bubble Rap and Epidemic

Related work

Conclusion

Footnotes

Declaration of conflicting interests

Funding

References