How Much Delay Has to Be Tolerated in a Mobile Social Network?

Abstract

Message delivery in a mobile social network (MSN) is difficult due to the fact that the topology of such network is sparse and unstable. Various routing schemes for MSNs were proposed to make the message delivery robust and efficient. However, little research has been conducted to explore how much delay has to be tolerated for the message delivery from the source to the destination. Since the social relationships among nodes are stable during a certain period of time, it is expected that the delay of message delivery in MSNs could be modeled with a probability model. In this paper, we take the first step to address this issue. We firstly extract three routing models from the existing routing schemes for MSNs and then develop the probability models of the message transmission delay for each abstract routing model. The simulation results show that the theoretical models match very well the simulation trace statistics.

1. Introduction

Mobile social network is a type of delay-tolerant networks (DTN [1]) which take into consideration the sociality of the participating nodes of the networks [2]. If the terminals of MSN are smartphones facilitated with rich sensing capability, it can function as a typical distributed sensor network [3]. Similar to the traditional mobile ad hoc networks (MANETs), no fixed infrastructures are built in such networks, and communications between the nodes depend on short-distance wireless links, like Wi-Fi or even Bluetooth. Since equipment in an MSN is usually carried by people moving freely, those nodes may organize themselves into highly dynamic topology, and the links between the nodes are usually intermittent and connected by opportunity due to the mobility of the nodes. As a result, large transmission delay is allowed in MSN. So in some extent, MSN is considered as a type of delay-tolerant networks. Although routing in an MSN might adopt the similar store-and-forward strategies [4] that dominate DTNs, it is essentially different from the DTN routing because the sociality of the user behavior can be cooperated explicitly to improve the efficiency of networking and communication in MSNs. Previous works [5–7] have shown that the performance of routing in MSN may heavily depend on the users' social behavior like that in a human social network, which is also the key characteristic for the design and analysis of the other issues in MSNs; see, for example [8, 9].

Traditional MANET routing protocols such as AODV [10], DSR [11], DSDV [12], and LAR [13] make assumption that the topologies of the networks are fully connected. These protocols will fail to route any message if there is no precomputed route from source to destination at the time of message being sent. In an opportunistic MSN, nodes carry the data to be forwarded and also are ready to forward data for other nodes. What is more, the mobility of nodes can be exploited to forward data opportunistically upon the encounter with each other. The key problem here is hence how to design appropriate relay selection strategies to improve the opportunity or probability of data forwarding. This improvement will make the data forwarding more efficient with less delay. Relay selection strategies depending on the history of contacts among nodes were proposed to find the right forwarding relays [14, 15].

While the end-to-end connections cannot be preset when the message is ready for transmission, social networks often demonstrate unique social characteristic like the so-called small-world phenomenon shown in the Milgram's 1967 mail transfer experiment [16]. In a social network, two-people contacts frequently usually have social ties. Recently, several sociality-aware routing strategies have been proposed to improve the routing efficiency for the MSNs [17–19].

Both contact history-based and social network metrics-based routing schemes designed for MSNs are best-effort, and there is no delay guarantee for the message delivery from the source to the destination. While MSNs are transmission delay-tolerant, it is still curious that how much delay must be tolerated for the message to be delivered from source to the destination or the delay bounds for message delivery in certain scenarios. These bounds are particularly interesting for the future multimedia application over the MSNs. While most of the work for data delivery in MSNs focuses on the design of new routing schemes, researches about how to evaluate the message delay remain rare and we try to make a first step to fill this gap.

In our opinion, the difficulty of the delay estimation for MSNs comes from two aspects: the dynamics of network topology and the uncertainty of the routing path. Though the mobility of nodes makes the networks' physical topology change dynamically, the nodes' social behavior tries to maintain regular contacts among nodes with social ties. We believe, therefore, it is possible to predict the routing behavior, at least the bounds of end-to-end delay of message delivery in an MSN.

In this paper, we illuminate a unified framework for evaluating the delay of message delivery in MSNs. Firstly, we propose general routing models extracted from the existing routing schemes. Then, we evaluate the delay with stochastic process theory based on the extracted routing model. The contributions of our paper are in threefold. First, we extract characteristics from the existing MSN routing strategies and classify them into three general models. Second, we propose a general method to evaluate the end-to-end delay in an MSN. And last, we design simulation experiments to validate the theoretical model. To our knowledge, this is the first effort to estimate the end-to-end delay of message delivery in an MSN via a probability framework.

The rest of this paper is organized as follows. Section 2 reviews the existing work. Section 3 presents the abstract routing model of the MSNs. Section 4 analyzes the delay bounds of the three types of general routing models with stochastic process theory and gives out the estimation results. Section 5 validates the performance of the proposed probability delay model by comparing the theoretical result with the simulation, and Section 6 concludes the paper.

2. Related Work

There is much work on the routing schemes for MANETs [20], from which the DTNs were evolved. The researches about routing schemes in a DTN might originate from the work of Jain et al. [4], in which messages are to be moved end-to-end across a time-varying connected graph but the topology dynamics may be known in advance. After that, there is much progress on this topic [21, 22].

Epidemic routing [23] which is originally designed for MANETs could deliver data fast and robustly by forwarding data to any encounters. To satisfy the limitation of energy and memory of nodes, a variety of relay selection strategies specially for DTNs are proposed [14, 15, 17–19]. Lindgren et al. proposed the ProPhet [14], making use of contact history to predict the probability of the meeting of the two nodes. Only nodes that can reach the destination with a higher probability will get the data from the relay.

Data dissemination in the delay tolerant MSNs is a critical component of many applications, for example, content update in an online social networks [24]. Sociality-based routing schemes for the DTNs have also been studied in recent years. SimBet routing [17] uses two social metrics (centrality and similarity) to estimate or predict the probability that potential relay nodes may reach the destination. Unlike the ProPhet and Epidemic, only one copy of data exists in the networks by SimBet routing. After that, Daly and Haahr tried to improve SimBet by using multiple copy of data forwarding [18]. Recently, Hui et al. [19] proposed a novel sociality-based forwarding algorithm, BUBBLE, which employed two social and structural metrics, namely, centrality and community.

Though there have been many research works on the design of routing schemes for the delay tolerant MSNs, model-based performance evaluation of these routing schemes is relatively scarce. Boldrini et al. [25] considered a utility-based cooperative data dissemination system in which the utility of data was defined based on the social relationships between users. Specifically, they designed a Markov model to characterize the data dissemination process in both its stationary and transient regimes. The main result of their analysis is that the data distribution process always converges to one of two possible stationary regimes.

Our study is obviously different from above work. In this paper, we concentrate on how to evaluate the delay from the source to the destination in a delay tolerant MSN by a probabilistic way. Based on the abstracted routing models, the data disseminating process is modeled as a stochastic process to estimate the delay to be experienced in such routing process.

3. Models

3.1. Network Model

In an MSN, nodes may be in a moving status and links between some nodes do not always exist. These characteristics make the topology of an MSN dynamic. However, during a certain time, the social relationships among the nodes are fixed. Being similar with [26, 27], we assume the pairwise node intercontact time is exponentially distributed. We consider the links among nodes as the social relationships of their holders, and the network model can be described as follows.

Consider an MSN with n mobile nodes, which can be denoted as a graph $G = (V, E)$ , where V is the set of nodes and E is the set of links between nodes. If there is social relationship between node i and node j, let $e_{i j} \in E$ denote the edge $e_{i j}$ between them. Letting $λ_{i j}$ denote the weight of the link $e_{i j}$ , then the intercontact time between nodes i and j obeys exponential distribution with parameter $λ_{i j}$ . And further, the contacts between nodes i and j form a homogeneous Poisson process with the contact rate $λ_{i j}$ .

3.2. The Model of MSN Routing

An MSN may experience frequent, persistent link partitioning and may never have a stable end-to-end path. Like in DTNs, routing in MSN employs the store-and-forward strategies over the opportunistic links. From various routing schemes existing currently, we extracted the following essential attributes which play the key roles for message delivery in an MSN. (a)

The relay selection strategy: this is without doubt the most important issue in the design of MSN routing, which directly affects the routing performance. Generally, we divided the strategies into two categories: nonstrategic that forwards data to any nodes it meets, and strategic that only forwarding data to those nodes which have better forwards quality.

(b)

The data copying strategy: to improve the successful ratio of message delivery, the relays usually forward multiple copies of the data to their neighbors concurrently. However, this strategy significantly increases the consumption of the network resource. The data copying strategy here can be classified as single-copy and multicopy in general. The multicopy strategies can be further divided into finite-copy and infinite-copy strategies. While the routing scheme with finite-copy strategy usually forward fixed number of copies to the neighbors, the routing schemes with infinite-copy strategy simply forward the data to all the nodes it encounters.

(c)

Clustering: while a good relay selection strategy can restrain the number of data copy to be forwarded, clustering is an effective approach to limit the overconsumption of the resource in a large scale MSN. According to whether the nodes will be clustered, the routing schemes for MSNs can be classified into layered routing and plain routing.

In this paper, only plain routing is considered. We extract three types of routing models from existing instances of routing schemes designed for MSNs based on the first two attributes described above.

3.2.1. Single-Copy Strategic Routing (SCSR)

The routing strategy refers that node carrying data will not indiscriminately forward data to whichever it encounters but only chooses those nodes that can forward the data to destination with one or more hops. The usual routing strategies include what we have mentioned before, for example, the contacts history-based and social metric-based relay selection. A typical routing scheme belonging to this type is SimBet.

3.2.2. Multicopy Routing without Strategies (MCR-WS)

This is the simplest routing schemes. Mobile node will forward its carried data to any nodes it encounters and keep the data at the same time. An infinite-copy strategy is more popular than the finite multiple copy strategy. Epidemic routing belongs to this type of routing schemes.

3.2.3. Multicopy Strategic Routing (MCSR)

In this type of multicopy routing schemes, strategies are considered which makes routing decisions more complex. Since it combines the simplicity of multicopy routing and efficiency of strategic routing, it attracts more attention and most of the routing schemes belong to this type. Compared with MCR-WS routing, if the relay selection strategy is designed to be effective enough, MCSR could achieve similar performance while consuming less system resources. ProPhet is a typical routing scheme of this type.

3.3. Some Assumptions of the Routing Model

We make the following assumptions listed from weak to strong. (1)

There is enough time for the nodes to exchange their data when they contact.

(2)

For the intercontact time is much longer than the data transmission time over the link, the latter would be ignored when evaluating the transmission delay.

(3)

In the case of multicopy routing strategy, nodes' buffer capacity is large enough thus no packet will be discarded due to the lack of memory.

(4)

TTL (time-to-live) field is set as time limitation and the data will be discarded actively if it does not arrive at the destination after TTL time's forwarding.

(5)

All nodes will not receive the same data for two times by numbering the message with a global ID created by a Hash function.

4. Analysis

We will analyze the delay of message delivery in MSNs based on the three routing models in Section 3. Before the detailed analysis, we firstly present an important result in Lemma 1. Assume that the source S intends to send data to the destination D through the intermediate node set ${N_{1}, N_{2}, \dots, N_{r}}$ as shown in Figure 1. Denote $λ_{1}, λ_{2}, \dots, λ_{r + 1}$ as the weight of intermediate links in sequence, and the corresponding intercontact time is $X_{1}, X_{2}, \dots, X_{r + 1}$ . As described in Section 3.1, the intercontact time between nodes follows exponential distribution, so the probability density function of $X_{k}$ is $f_{X_{k}} (x) = λ_{k} e^{- λ_{k} x}$ . Then the maximal aggregated time needed to forward data from S to D is

\begin{matrix} Y = \sum_{i = 1}^{r + 1} X_{i}, \end{matrix}

(1)

which is hypoexponentially distributed [28] according to the following lemma.

Figure 1

Opportunistic path connecting nodes S and D.

Lemma 1 (section $5.2 . 4$ of [28]).

For an opportunistic path with r hops, the corresponding edges weight as $λ_{1}, λ_{2}, \dots, λ_{r + 1}$ , then the probability density function of Y as in (1) is

\begin{matrix} f_{Y} (x) = \sum_{k = 1}^{r + 1} C_{k}^{(r + 1)} f_{X_{k}} (x), \end{matrix}

(2)

where

C_{k}^{(r + 1)} = \prod_{s = 1, s \neq k}^{r + 1} (λ_{s} / (λ_{s} - λ_{k}))

By formula (2) and assumption 5, the expected delay of the path in Figure 1 is

\begin{array}{l} E [Y] = \int_{0}^{T} x p_{Y} (x) d x = \int_{0}^{T} x \sum_{k = 1}^{r + 1} C_{k}^{(r + 1)} λ_{k} e^{- λ_{k} T} d x \\ = \sum_{k = 1}^{r + 1} C_{k}^{(r + 1)} (\frac{1}{λ_{k}} - (T + \frac{1}{λ_{k}}) e^{- λ_{k} T}) . \end{array}

(3)

4.1. Delay of Multicopy Routing without Strategies

We firstly analyze the case of MCR-WS and the typical routing of this type is Epidemic [23]. Messages generated at source node will be forwarded to encountering nodes that have not received the data. Data will disseminate over the whole network quickly by multicopying in the network. As we know, MCR-WS usually enjoys the minimum delay but consumes much more system resources.

According to assumptions 1 and 2 in Section 3, the time needed to send data from the source to the destination is the sum of the intercontact time between intermediate nodes pairs. There might be several possible routing paths connecting the source to the destination. But due to the multicopy strategy, the transmission delay is always the minimum of delays along all the possible paths as the following lemma.

Lemma 2.

There are m paths ${P_{1}, P_{2}, \dots, P_{m}}$ between the source node S and destination node D . The corresponding transmission delay of each path is elements of set ${Y_{1}, Y_{2}, \dots, Y_{m}}$ . Then with MCR-WS, the delay between S and D is $T (S, D) = \min {Y_{1}, Y_{2}, \dots, Y_{m}}$ .

Proof.

The proof is obvious and omitted.

Because the weight of every edge constructing a path can be got according to formula (2), the cumulative distribution function $F_{Y_{i}} (x)$ of each path's delay can be derived by Lemma 1. By Lemma 2, the cumulative distribution function of $T (S, D)$ is given out in Proposition 3.

Proposition 3.

In the MCR-WS scheme, if ${Y_{1}, Y_{2}, \dots, Y_{m}}$ are independent with each other, then the transmission delay from S to D $T (S, D) = \min {Y_{1}, Y_{2}, \dots, Y_{m}}$ follows the distribution

\begin{matrix} F_{T} (x) = 1 - \prod_{i = 1}^{m} (1 - F_{Y_{i}} (x)) . \end{matrix}

(4)

Proof.

According to Lemma 2, any one of the elements in ${Y_{1}, Y_{2}, \dots, Y_{m}}$ satisfying $Y_{i} \leq x$ makes sure $T \leq x$ . The probability of $Y_{i} > x$ for all i is $\prod_{i = 1}^{m} (1 - F_{Y_{i}} (x))$ , thus $F_{T} (x) = 1 - \prod_{i = 1}^{m} (1 - F_{Y_{i}} (x))$ .

Proposition 3 is provable on conditions that all the possible paths are independent. If two paths do not share any node, these two paths are independent with each other. However, all paths in ${Y_{1}, Y_{2}, \dots, Y_{m}}$ from S to D usually are not independent, and some correlated paths should be fixed approximately. Assuming that $P_{i} = {N_{1}^{(i)}, N_{2}^{(i)}, \dots, N_{m}^{(i)}}$ and $P_{j} = {N_{1}^{(j)}, N_{2}^{(j)}, \dots, N_{n}^{(j)}}$ are two paths sharing intermediate node, the shared node $N_{k_{1}}^{(i)}$ or $N_{k_{2}}^{(j)}$ is called broken node if $N_{k_{1}}^{(i)} = N_{k_{2}}^{(j)}$ and $N_{k_{1} + 1}^{(i)} \neq N_{k_{2} + 1}^{(j)}$ . In contrast, $N_{k_{1}}^{(i)}$ or $N_{k_{2}}^{(j)}$ is called backing node if $N_{k_{1}}^{(i)} = N_{k_{2}}^{(j)}$ and $N_{k_{1} - 1}^{(i)} \neq N_{k_{2} - 1}^{(j)}$ . By the position of the broken node and the next backing node, two subpaths can be found which have the same source $S^{'}$ (broken node) and the same destination $D^{'}$ (backing node). Because the two subpaths share no common intermediate nodes, they are independent. As a result, through Lemma 1 and Proposition 3, the expectation of transmission delay from $S^{'}$ to $D^{'}$ can be calculated as $T^{'}$ , building a dummy connection between $S^{'}$ and $D^{'}$ instead of the paths which connecting them. The distribution of intercontact time $Y^{'}$ between $S^{'}$ and $D^{'}$ is approximated as exponential distribution with parameter $λ_{S^{'} D^{'}} = 1 / T^{'}$ . Through the above approximate treatment, two related paths could be merged into one path. What is more, if the same merging process is done on all the paths ${Y_{1}, Y_{2}, \dots, Y_{m}}$ , a group of independent paths will be constructed. Finally, transmission delay evaluation of MCR-WS will be done using Proposition 3 directly.

4.2. Delay of Single-Copy Strategic Routing

Now we consider the second case, SCSR. The strategy here refers to that relaying nodes will not forward data to any encounters but select those that could forward the data to the destination with better quality. There are several different relay selection strategies. Some maintain a local encountering probability by contact history and others calculate the utility value using social metrics. Despite of the distinct of the strategies, no strategy can guarantee that the relay selection will always reach the destination. It is assumed that the probability of selecting a right relay is a constant $P_{Eval- W}$ . We will show how to estimate the value of $P_{Eval- W}$ later.

Let V be the node forwarding data and $N (V)$ its neighbor set. Because not all neighbors can lead to the destination, let $W (V) \subseteq N (V)$ denote nodes that can forward data to the destination and tend to be selected as the next relay by the strategy. Due to the single-copy strategy, only one of the nodes in $N (V)$ will receive data from V. To make sure the data could be forwarded to the destination with highest probability, the intercontact history between node V and the candidates of relays is used to decide the probability of relay selection. Let $P_{s} (N_{i})$ denote the probability that node $N_{i} \in W (V)$ is selected by V as the next relay. For node $N_{i} \in W (V)$ , it is obvious that the more frequently contacting with V, the higher probability of $P_{s} (N_{i})$ . So we have

\begin{matrix} \sum_{i \in W (V)} P_{s} (N_{i}) = P_{Eval- W} \\ P_{s} (N_{i}) : P_{s} (N_{j}) = w (N_{i}, V) : w (N_{j} : V) \forall i, j \in W (V) . \end{matrix}

(5)

In most cases, there are many possible paths connecting the source S and the destination D. All the possible path set can be found and it is denoted as PathSet $(S, D) = {(P_{1}, Pro b_{1})$ , $(P_{2}, Pro b_{2}), \dots, (P_{m}, Pro b_{m})}$ , in which $Pro b_{i}$ denotes the probability of selecting path $P_{i}$ for message delivery. Assuming the path $P_{i}$ includes the following nodes $N_{1} (source)$ , $N_{2}, \dots, N_{m - 1}, N_{m}$ (destination), then

\begin{matrix} Pro b_{i} = \prod_{i = 2}^{m} p_{s} (N_{i}) . \end{matrix}

(6)

Because there is only one data copy in the network, with the assumption of independent probability of possible path selection, we can calculate the probability of the successful message delivery:

\begin{matrix} P_{Eval} = \sum_{i = 1}^{m} Pro b_{i} . \end{matrix}

(7)

What is more, it is easy to get the probability of successful message delivery of the real scenario and we denote it as $P_{Real}$ . Then letting $P_{Eval} = P_{Real}$ , with (5), (6), and (7), the probability of selecting the proper relay $P_{Eval- W}$ can be calculated.

Through above discussion, the preparation for the evaluation of SCSR has been done and then Proposition 4 is given as follows.

Proposition 4.

In the type of SCSR, assume the possible routing path set is $Path (S, D) = {(P_{1}, {Prob}_{1})$ , $(P_{2}, {Prob}_{2}), \dots$ , $(P_{m}, {Prob}_{m})}$ , in which ${Prob}_{i}$ denotes the probability of selecting path $P_{i}$ . And let $Y_{i}$ denote the transmission delay over path $P_{i}$ . Then the delay T needed to send data from source to destination successfully has the following probability density function:

\begin{matrix} f_{T} (x) = \sum_{i = 1}^{m} f_{Y_{i}} (x) \times \frac{{Prob}_{i}}{P_{Real}}, \end{matrix}

(8)

where

P_{Real} = \sum_{i = 1}^{m} {Prob}_{i}

and

f_{Y_{i}} (x)

is the probability distribution function of the variable

Y_{i}

Proof.

Firstly, it is proved that $f_{T} (x)$ satisfies the property of probability density function. Obviously, for all $x \in R$ , $f_{T} (x) \geq 0$ and it has

\begin{array}{l} \int_{- \infty}^{+ \infty} f_{T} (x) = \int_{0}^{+ \infty} f_{T} (x) d x \\ = \int_{0}^{+ \infty} \sum_{i = 1}^{m} f_{Y_{i}} (x) \times \frac{Pro b_{i}}{P_{Real}} d x \\ = \sum_{i = 1}^{m} \frac{Pro b_{i}}{P_{Real}} \times \int_{0}^{+ \infty} f_{Y_{i}} (x) d x \\ = \sum_{i = 1}^{m} \frac{Pro b_{i}}{P_{Real}} = 1 . \end{array}

(9)

So $f_{T} (x)$ can be probability density function of variable T. Then we prove that the relationship in (8) makes sense. Because of the single-copy strategy, there is only one path that is selected to transmit data. The probability $Pro b_{i}$ of each path being chosen can be calculated according to (5), (6), and (7), and the distribution functions of transmission delay $Y_{i}$ on each path are known; we have

\begin{matrix} p (T = x) = \sum_{i = 1}^{m} p (Y_{i} = x) \times Pro b_{i} . \end{matrix}

(10)

By the influence of policy, the data may not be sent to the destination for selecting the wrong path, which makes the transmission delay infinite. If the case of choosing the broken path is not taken into consideration, the sum of chosen probability of all the possible left paths $\sum_{i = 1}^{m} Pro b_{i}$ is less than 1, which makes the component of T uncompleted. But if we normalize the probability of selecting the proper path, that is to say, letting the probability $Pro b_{i}$ be normalized as $Pro b_{i} / P_{Real}$ , which would keep the component of T completed, then we can get the probability density function $f_{T} (x) = \sum_{i = 1}^{m} f_{Y_{i}} (x) \times Pro b_{i} / P_{Real}$ under the condition of successful message delivery.

By Proposition 4, the expected time delay from the source node S to the destination D in this type of routing schemes can be easily got as

\begin{matrix} E [T (S, D)] = \sum_{i \in Path (S, D)} E [Y_{i}] \times \frac{Pro b_{i}}{P_{Real}} . \end{matrix}

(11)

4.3. Delay of Multicopy Strategic Routing

The multicopy strategy improves the probability of successful message delivery comparing with the SCSR. And the relay selection strategy reduces the overhead of MCR-WS. Spyropoulos et al. [15] proved that the performance of MCSR could achieve the performance of Epidemic routing if the strategy was designed properly.

The method of dealing with relay selection strategy is similar to that in SCSR. We still assume the probability of selecting the proper relay is a constant $P_{Eval- W}$ . However, due to the multicopy strategy, every node in $W (S)$ is selected with the same probability $P_{Eval- W}$ . All paths connecting the source S and destination D will be denoted as $Path (S, D) = {(P_{1}, Pro b_{1}), (P_{2}, Pro b_{2}), \dots, (P_{m}, Pro b_{m})}$ . Then the probability of transferring data on path $P_{i}$ is

\begin{matrix} Pro b_{i} = {(P_{Eval- W})}^{| P_{i} | - 1}, \end{matrix}

(12)

where

| P_{i} | - 1

is the number of relays selected. Unless all the possible paths fail, the data will fail to be transmitted to the destination. So the probability of successfully sending data is

1 - \prod_{i = 1}^{m} (1 - Pro b_{i})

. Letting

\begin{matrix} 1 - \prod_{i = 1}^{m} (1 - Pro b_{i}) = P_{Real}, \end{matrix}

(13)

then

P_{Eval- W}

and each probability

Pro b_{i}

can be calculated. To evaluate the transmission delay in the MCSR, Proposition 5 is given as follows.

Proposition 5.

In the type of MCSR, node S sends message to node D and the all possible routing path set is $Path (S, D) = {(P_{1}, {Prob}_{1})$ , $(P_{2}, {Prob}_{2})$ , $\dots, (P_{m}, {Prob}_{m})}$ . If the routing paths are independent with each other, the transmission delay T follows:

\begin{matrix} F_{T} (x) = 1 - \prod_{i = 1}^{m} (1 - F_{Y_{i}} (x)) \times {Prob}_{i} . \end{matrix}

(14)

Proof.

We consider all the cases of $T > x$ . Firstly, if the data is sent successfully to the destination, it requires all transmission delay on every possible routing path that has $Y_{i} > x$ . Because all $Y_{i}$ are independent with each other, through the distribution function of $Y_{i}$ , the probability of $Y_{i} > x$ for $i = 1,2, \dots, m$ is $\prod_{i = 1}^{m} (1 - F_{Y_{i}} (x))$ . For every possible routing path is selected at the probability of $Pro b_{i}$ , the probability of $Y_{i} > x$ should be multiplied by $Pro b_{i}$ . Then we have $F_{T} (x) = 1 - \prod_{i = 1}^{m} (1 - F_{Y_{i}} (x)) \times Pro b_{i}$ . Secondly, we verify whether $F_{T} (x)$ fulfills the definition of distribution function. Obviously, it is true that $\lim_{x \to \infty} F_{T} (x) = 1$ , for $\lim_{x \to \infty} F_{Y_{i}} (x) = 1$ , for all $i = 1,2, \dots, m$ .

Proposition 5 requires that all possible correlated routing paths are independent with each other. Some fixing similar to MCR-WS should be done. Two related routing paths that share intermediate nodes will be merged. The merging process is as same as the process in MCR-WS, but the probability of the new merged routing path should be re-calculated. Assume, in the merging process, two subpaths which have $m_{1}$ and $m_{2}$ nodes, respectively, include their common head node $S^{'}$ and tail node $D^{'}$ . After they have been merged, the probability of having data flow from $S^{'}$ to $D^{'}$ is $1 - (1 - (P_{Eval- W})^{m_{1}}) \times (1 - (P_{Eval- W})^{m_{2}})$ . Through the path merging and probability modifying process, a new independent routing path will be got. Then using Proposition 5, the transmission delay in MCSR can be calculated.

5. Simulation

In this section, we validate our delay model by comparing the theoretical delay model with the simulation results. All of the three routing schemes corresponding to each routing model are included: Epidemic [23] for MCR-WS, SimBet [17] for SCSR, and ProPhet [14] for MCSR.

5.1. Simulation Setup

The simulation experiment is developed based on the general discrete event simulation platform OMNET++ [29]. Though the scale of network in our simulation could be set as any size only if it is within the resource constraints of the simulator, the theoretical delay model has no relevance to the scale. In the simulation, 30 nodes are randomly placed inside an area of $500 \times 500 m^{2}$ . IEEE 802.11b DCF is used as the MAC layer protocol. The radio propagation range of all nodes is set as 100 meters. The nodes move according to the Gauss-Markov mobility models [30], with a minimum speed of 0 m/s and a maximum speed of 5 m/s. When two nodes are in the radio propagation range, it is considered that they meet and can communicate with each other. As models omit the transmission delay of the channel, the transmission delay of all channels is set as 0.

During the simulation, the source and destination nodes are selected randomly from the node set. Data packets are generated by the source node every five seconds and 3000 packets will be sent during this interval. The time-to-live fields of these packets are set as 15 s, which means the message will be discarded if it has not arrived at the destination after 15 seconds. The intercontact time of nodes meeting each other is recorded to provide the social ties for the model-based numerical experiment. We approximate the parameter of the exponential distribution as the reciprocal of the average intercontact time. The parameter setting of ProPhet is as same as in [14], that is, $P_{init} = 0.75$ , $β = 0.25$ , and $γ = 0.98$ . And the parameters of SimBet are just like in [17], that is, $α = β = 0.5$ . To simulate the packet routing process, every data packet is forwarded on the meeting of the expected nodes according to the routing schemes and the transmission delay is traced.

5.2. Model Evaluation

We try to evaluate the accuracy of the theoretical model by comparing the estimated delay with the corresponding statistics of the simulation result. We have already derived the probability density function or cumulative distribution function of the transmission delay of each routing model, respectively, as in (4), (8) and (14). Denote all the delays traced in the simulation as ${d_{1}, d_{2}, \dots, d_{m}}$ and divide the time interval $[0, T T L]$ into constant k parts equally. The constant k should be carefully set. Then counting the number $c_{i}$ of $d_{i}$ belongs to each subinterval and let $c_{i} / m$ be the probability of the subinterval. In one simulation, the comparison results are shown in Figures 2, 3, and 4. It is obvious that the delay in simulation matches very well the delay calculated by the proposed theory model.

Figure 2

Comparison of MCR-WS.

Figure 3

Comparison of SCSR.

Figure 4

Comparison of MSCR.

Then we run the simulation for 20 times of each routing model, each of which includes sending 3000 data packets. Each time the network scale is also $N = 30$ but with different network topology. Through the simulation, the average transmission delay is obtained and the expected delay by the model could also be calculated. Pearson Correlation Coefficient [31] is a measure of the correlation between two variables X and Y, giving a value between +1 and −1 inclusive. The more close to +1 or −1, the more related they are. It is commonly denoted with r and can be obtained from the following formula:

\begin{matrix} r = \frac{\sum_{i = 1}^{n} (X_{i} - \bar{X}) (Y_{i} - \bar{Y})}{n \sqrt{\sum_{i = 1}^{n} {(X_{i} - \bar{X})}^{2}} \sqrt{\sum_{i = 1}^{n} {(Y_{i} - \bar{Y})}^{2}}} . \end{matrix}

(15)

We use Pearson Correlation Coefficient to show further how much the average transmission delay in simulation matches the theoretical result. The result presented in Table 1 shows that the simulation delays and theory-calculated delays are highly related.

Table 1

Pearson Correlation Coefficient.

Routing model	Pearson Correlation Coefficient
MCR-WS	0.8591
SCSR	0.8021
MCSR	0.9065

6. Conclusions

In this paper, we proposed a probability model to estimate the delay of message delivery in the delay tolerant mobile social networks. We firstly extracted three general routing models from the existing various routing schemes for MSNs. According to an elegant result in probability theory, we constructed probability delay models for each of the three routing models. Then the simulation experiments were designed to validate the accuracy of the theoretical delay model. It was found that the delay statistics from the simulation trace matched very well the theoretical results, which means that proposed model is quite accurate for the prediction of delay of message delivery in an MSN.

During the model construction, we omitted the storage limitation of the nodes in an MSN. In the future work we will enhance the proposed delay model considering the message loss from the storage limit. For only the plain routing schemes for MSNs being considered in the current work, delay estimation for the layered routing schemes is also a valuable extension to this work.

Footnotes

Acknowledgments

The work was supported by National Science Foundation of China under Grant no. 61070170, Science Research Program of Universities in Jiangsu Province under Grant no. 11KJB520017, and Application Foundation Research of Suzhou (Jiangsu, China) under Grant no. SYG201238.

References

Fall

A delay-tolerant network architecture for challenged internets

Proceedings of the Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications

August 2003

27 34

2-s2.0-1242310099

Falk

Applications, architectures, and protocol design issues for mobile social networks: a survey

Proceedings of the IEEE 2011 99 12 2125 2129

2-s2.0-81855227205

10.1109/JPROC.2011.2170750

Lane

N. D.

Miluzzo

Peebles

Choudhury

Campbell

A. T.

A survey of mobile phone sensing

IEEE Communications Magazine 2010 48 9 140 150

2-s2.0-77956382087

10.1109/MCOM.2010.5560598

Jain

Fall

Patra

Routing in a delay tolerant network

Proceedings of the Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications

September 2004

New York, NY, USA

145 158

2-s2.0-21844451437

10.1145/1030194.1015484

Yoneki

Hui

Chan

Crowcroft

A Socio-Aware Overlay for publish/subscribe communication in delay tolerant networks

Proceedings of the 10th ACM Symposium on Modeling, Analysis, and Simulation of Wireless and Mobile Systems

October 2007

New York, NY, USA

225 234

2-s2.0-42149145531

10.1145/1298126.1298166

Gao

Zhao

Cao

Multicasting in delay tolerant networks: a social network perspective

Proceedings of the 10th ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc'09)

May 2009

New York, NY, USA

299 308

2-s2.0-70450161107

10.1145/1530748.1530790

Henderson

Kotz

Abyzov

The changing usage of a mature campus-wide wireless network

Proceedings of the 10th Annual International Conference on Mobile Computing and Networking

October 2004

New York, NY, USA

187 201

2-s2.0-11244321489

Beach

Gartrell

Akkala

Elston

Kelley

Nishimoto

Ray

Razgulin

Sundaresan

Surendar

Terada

Han

WhozThat? Evolving an ecosystem for context-aware mobile social networks

IEEE Network 2008 22 4 50 55

2-s2.0-48749092900

10.1109/MNET.2008.4579771

W. D.

Siddiqui

Towards a wireless mobile social network system design in healthcare

Proceedings of the 3rd International Conference on Multimedia and Ubiquitous Engineering

June 2009

429 436

2-s2.0-72849143109

10.1109/MUE.2009.77

10.

Perkins

C. E.

Royer

E. M.

Ad-hoc on-demand distance vector routing

Proceedings of the 2nd IEEE Workshop on Mobile Computing Systems and Applications

February 1999

90 100

2-s2.0-34347349933

10.1109/MCSA.1999.749281

11.

Johnson

Maltz

Dynamic source routing in ad-hoc wireless networks

Mobile Computing 1996 353 153 181

12.

Perkins

C. E.

Bhagwat

Highly dynamic destination-sequenced distance-vector routing (DSDV) for mobile computers

Proceedings of the Conference on Communications Architectures, Protocols and Applications

1994

New York, NY, USA

4 234 244

13.

Y.-B.

Vaidya

N. H.

Location-aided routing (LAR) in mobile ad hoc networks

Wireless Networks 2000 6 4 307 321

2-s2.0-0034266911

10.1023/A:1019106118419

14.

Lindgren

Doria

Schelen

Probabilistic routing in intermittently connected networks

Mobile Computing and Communications Review 2003 7 3 19 20

15.

Spyropoulos

Psounis

Raghavendra

C. S.

Spray and wait: an efficient routing scheme for intermittently connected mobile networks

Proceedings of the ACM SIGCOMM Workshop on Delay-Tolerant Networking

August 2005

New York, NY, USA

252 259

2-s2.0-29244491141

16.

Milgram

The small world problem

Psychology Today 1967 1 1 60 67

17.

Daly

E. M.

Haahr

Social network analysis for routing in disconnected delay-tolerant MANETs

Proceedings of the 8th ACM International Symposium on Mobile Ad Hoc Networking and Computing

September 2007

New York, NY, USA

32 40

2-s2.0-37849017498

10.1145/1288107.1288113

18.

Daly

E. M.

Haahr

Social network analysis for information flow in disconnected delay-tolerant MANETs

IEEE Transactions on Mobile Computing 2009 8 5 606 621

2-s2.0-63049119529

10.1109/TMC.2008.161

19.

Hui

Crowcroft

Yoneki

Bubble Rap: social-based forwarding in delay-tolerant networks

IEEE Transactions on Mobile Computing 2011 10 11 1576 1589

2-s2.0-80052124479

10.1109/TMC.2010.246

20.

Royer

E. M.

Toh

C.-K.

A review of current routing protocols for ad hoc mobile wireless networks

IEEE Personal Communications 1999 6 2 46 55

2-s2.0-0032621035

10.1109/98.760423

21.

Ott

Kutscher

Dwertmann

Integrating DTN and MANET routing

Proceedings of the ACM SIGCOMM Workshop on Challenged Networks

September 2006

221 228

2-s2.0-34247389278

10.1145/1162654.1162659

22.

Zhu

Shi

Wang

A survey of social-based routing in delay tolerant networks: positive and negative social effects

IEEE Communications Surveys & Tutorials 2013 15 1 387 401

2-s2.0-84859243948

10.1109/SURV.2012.032612.00004

23.

Vahdat

Becker

Epidemic routing for partially connected ad hoc networks

2000 CS-200006

Duke University

24.

Ioannidis

Chaintreau

Massoulié

Optimal and scalable distribution of content updates over a mobile social network

Proceedings of the 28th Conference on Computer Communications (IEEE INFOCOM '09)

April 2009

1422 1430

2-s2.0-70349678474

10.1109/INFCOM.2009.5062058

25.

Boldrini

Conti

Passarella

Modelling data dissemination in opportunistic networks

Proceedings of the 3rd ACM Workshop on Challenged Networks

September 2008

New York, NY, USA

89 96

2-s2.0-60149093585

10.1145/1409985.1410002

26.

Freeman

L. C.

A set of measures of centrality based on betweenness

Sociometry 1977 40 1 35 41

27.

Freeman

L. C.

Centrality in social networks conceptual clarification

Social Networks 1979 1 3 215 239

2-s2.0-33750177351

28.

Ross

S. M.

Introduction To Probability Models 2006

Academic Press

29.

OMNeT++ Community Site http://www.omnetpp.org/

30.

Johnson

D. B.

Maltz

D. A.

Dynamic source routing in Ad Hoc wireless networks

Mobile Computing 1996 353 153 181 The Kluwer International Series in Engineering and Computer Science

31.

http://en.wikipedia.org/wiki/Pearson_correlation_coefficient

How Much Delay Has to Be Tolerated in a Mobile Social Network?

Abstract

1. Introduction

2. Related Work

3. Models

3.1. Network Model

3.2. The Model of MSN Routing

3.2.1. Single-Copy Strategic Routing (SCSR)

3.2.2. Multicopy Routing without Strategies (MCR-WS)

3.2.3. Multicopy Strategic Routing (MCSR)

3.3. Some Assumptions of the Routing Model

4. Analysis

Lemma 1 (section 5.2 . 4 of [28]).

4.1. Delay of Multicopy Routing without Strategies

Lemma 2.

Proof.

Proposition 3.

Proof.

4.2. Delay of Single-Copy Strategic Routing

Proposition 4.

Proof.

4.3. Delay of Multicopy Strategic Routing

Proposition 5.

Proof.

5. Simulation

5.1. Simulation Setup

5.2. Model Evaluation

6. Conclusions

Footnotes

Acknowledgments

References

Lemma 1 (section $5.2 . 4$ of [28]).