TR-SDTN: Trust Based Efficient and Scalable Routing in Hostile Social DTNs

Abstract

A delay tolerant network (DTN) presents a new communication model, which uses a store-carry-forward approach to deliver messages due to the nature of the network. With the development of the mobile internet, the research on DTNs becomes a hot topic. One critical issue in the DTNs with social characteristics is that there could exist selfish and malicious nodes which block important data and as a result intentionally disturb the communication. Although there are many research works which address the issue and adopt various trust models to encourage nodes to forward information, most of them have not considered the social characteristics of the mobile nodes and they have not handled the selfish behaviors and attacks in a systematic way. In view of these defects, we propose a novel solution to address the selfish and security issues in social DTNs. Based on nodes’ social characteristics, a dynamic trust model is proposed to prevent bad-mouthing and ballot stuffing attacks and the Shannon entropy function is introduced to avoid blackhole and greyhole attacks. The simulation results show that our proposed scheme can significantly improve the performance of social DTNs. And the simulation is proved to be consistent with the results from theoretical analysis.

1. Introduction

With the development of mobile internet, wireless communication via mobile devices over a typical delay tolerant network (DTN) becomes a hot research topic. DTNs hold a new network architecture which takes use of a store-carry-forward communication model to forward messages because there is no persistent end-to-end path from the source to the destination. A lot of research works have been done on the efficient routing and transmission of messages in a DTN environment.

Pioneer studies on the routing in DTNs have mainly focused on the actions for the next hop transmission with consideration of historical information. Typical protocols include epidemic [1], prioritized epidemic (PREP) [2], probabilistic routing protocol using history of encounters and transitivity (PROPHET) [3], and some other improvements and variations proposed. As an example, the PROPHET is a routing mechanism based on historical information, which is the history of encounters and transitivity to select next hop for the message forwarding. And the transmit predictability $P_{(a,b)}\in (\mathrm{0,1}]$ has been adopted as the probability metrics. The main characteristic of PROPHET is that node i will forward a message to node j if node j has a higher predicted probability to the destination of the message than that of node i.

Although the protocols with history information work well to be able to achieve high message delivery ratio, messages are delivered with high latency. To reduce the delay, other properties such as mobility models and the relationship among mobile nodes have been considered to make routing decisions. In some particular DTN environments, clustering with hierarchical structures has been proposed to reduce the end-to-end delay. In [4], a hierarchical forwarding mechanism has been proposed to group the nodes according to their encounter frequency. Initially, each node is considered as a cluster consisting of a single node. And the operation which combines the two best clusters to form a new cluster, determined by a distance function, is repeated until the cluster including all nodes is finally formed. Similar works can be found in [5, 6]. By these protocols, the mobile nodes with frequent contact and the mobile nodes with less contact will be considered differently. By these mechanisms, the efficiency of message transmission can be improved. However, the destination of the messages may not be able to receive all the messages due to the unreliability of the wireless communication channels.

By the above mentioned routing schemes, good performance may not be obtained in some DTNs which have the characteristics of social networks (social DTNs). Existing studies show that, in such scenarios, there are some active nodes which can transmit messages to their destinations with less hops. For example, in a campus scenario, students in the same group communicate with each other frequently while students in different groups have less contact. But a group leader has more contacts among different groups. Some new schemes have been proposed to address routing issue in such DTNs. In [7], according to the small world theory, a routing algorithm has been proposed to combine the similarity and centrality, where the similarity refers to the number of the same neighbors of two nodes while the ratio of the number of the shortest paths including a node over the number of all the shortest paths is defined as the centrality of the node. Additionally, in [8] in accordance with the two important characteristics of a social network, community and centrality, the author has proposed a forwarding algorithm, by which messages will be constantly forwarded to the nodes with the higher centrality because these nodes will have higher probability to meet the destination node. More social characteristics such as the social distance defined in [9], the asynchronous centrality defined in [10], the node's social relation in [11], and the impact of strangers in [12] can be employed to make the forwarding decisions.

However, in social DTNs, there could exist some selfish or malicious nodes. They are unwilling to forward messages from strangers or impair communications by launching attacks. In [13], a dynamic trust management model has been used to select next carrier to avoid messages being forwarded to malicious nodes. By analyzing real traces, in [14], a secure friend discovery scheme has been proposed by identifying potential attacks. In [15], based on the social relation of nodes, a protocol for avoiding the internet threats caused by social selfishness has been proposed. In [16], the authors have pointed out that nodes may be selfish and may not be cooperative for packet forwarding and current research mainly focuses on encouraging nodes to participate in packet forwarding. Similarly, in [17], based on node's own trust relationships, a new scheme against social selfishness has been proposed. What is more, in [18, 19], different mechanisms have been proposed to handle the selfish behaviors of the mobile nodes in the networks. And in [20], a literature survey has presented a summary on the recent routing schemes which take advantages of the positive social characteristics or overcome the negative social characteristics. In addition, there are some research solutions against malicious attacks such as the solution against the blackhole attacks in [21]. From those recent research works, we can find that most of them have not made full use of the nodes’ positive social characteristics to overcome the selfish behaviors and prevent malicious attacks at the same time. They have only considered one aspect of the selfish behaviors or attacks. In general, considering the characteristics of DTNs and the properties of social networks, to avoid various threats from the selfishness of the mobile nodes and the attacks from the malicious nodes in the social DTN environments, we propose a novel routing scheme, named as trust routing in hostile social DTNs (TR-SDTN), which divides mobile nodes into different clusters according to the contact frequency. Since the nodes communicate with each other frequently in a cluster, it is assumed that nodes in the same cluster are friends. Selfish nodes and malicious nodes are only considered existing in different clusters. The main contribution of our work is that a direct trust model, an indirect trust model, and the Shannon entropy function are used to prevent the threats from selfish nodes and attacks from malicious nodes.

The remainder of this paper is organized as follows. In Section 2, the system model is introduced. The proposed routing mechanism is presented in Section 3. And in Section 4, the performance of the solution is evaluated by a mathematical model and simulation experiments. Finally, the conclusion of the paper is summarized in Section 5.

2. System Model

2.1. Characteristics of DTNs and Social Networks

The communication in DTNs is a type of asynchronous communication without an end-to-end path at any moment. One of its main characteristics is that the links between mobile nodes are volatile and may break down for a long period of time at any moment, which makes the DTNs always suffer from partitioning from time to time. There are ubiquitous scenarios of the DTNs including mobile sensor networks, disaster recovery, military deployment, and interstellar communications to hold those characteristics. And there are some scenarios to have the DTNs formed by several clusters. In such scenarios, the mobile nodes in the same cluster communicate with each other frequently and several active nodes will be able to communicate with the nodes in different clusters. These active mobile nodes show same characteristics as the nodes in the social networks. Therefore, the characteristics of social networks can be borrowed to design the routing protocols in those scenarios.

A social network is one type of network formed by the corporations of people. Due to different characteristics of different people in nationality, environment, interests, gender, age, and so forth, different communities could be established by the people with same characteristics. One person is more likely to only interact with another one in the same community than a randomly selected person. On the other hand, within a community, there are some individuals who are active in communication with other people. In addition to contacting frequently with the persons in the same community, they also have more contacts with others in other communities. These facts can be further exploited to design the routing protocols for the DTNs with the social characteristics. However, the assumption that all nodes are cooperative is unrealistic because in a social network there exist some nodes which are selfish. They are unwilling to forward messages from others. And there also exist malicious nodes which can launch a variety of attacks to impair normal communications.

2.2. System Model

In this paper, the system under the study is a social DTN, in which each mobile node is in continuous movement. Some nodes move in a small range at low speeds and they communicate with each other frequently in the range. And some other nodes move frequently over a larger area at high speeds. Due to the movement of the nodes, temporary clusters can be formed from time to time and there exist some mobile nodes which can be used to transmit messages among clusters. Therefore, in our system, clustering technology can be used with different forwarding mechanisms used for the intracluster and intercluster communications. Since in intracluster, nodes communicate with each other frequently, we assume that they are cooperative with each other as friends with low probability to behave selfishly and maliciously. On the contrary, selfishness and attacks must be considered in intercluster communication. So, in this paper, our solution will target preventing the selfishness and malicious attacks appearing only in the intercluster communication.

On the mobility of a node in the system, we have the following mobility model to describe movement of the nodes in the system. To simplify the scenario, we adopt the mobility model in [6] with some modifications. In the system, there are five hot spots and one cold spot denoted by $H_1\text{–}{H}_5$ and C as shown in Figure 1. Each mobile node is assumed to have a “home” hot spot where it stays most of time. And each mobile node always goes to the cold spot when it leaves a hot spot. It is further assumed that 20% of the nodes will take more time to move among different spots. As shown in Figure 2, when a node is home, it will have a probability of $P_H$ to stay or $1-P_H$ to move to the cold spot in the next time slot. While at the cold spot, it will go home with probability of $P_H$ , or have a probability of $P_C$ to stay, or move to other hot spots with probability of $1-P_H-P_C\hspace{0.17em}(P_H+P_C<1)$ . Finally, when the node stays in a hot spot which is not its home spot, it will have a probability of $P_H$ to move to the cold spot or stay with probability of $1-P_H$ .

Figure 1

Mobility model.

Figure 2

Change of the state of a node.

In the model, each node will have a unique ID and maintain the contact information with others by a list of parameters including node ID, contact probability, contact time, and trust value (direct trust value and indirect trust value) for other nodes (see Figure 1).

2.3. Attack Model

As mentioned in Section 2.1, in the social DTNs, there exist selfish and malicious nodes which block the important data and as a result intentionally disturb the communication over the networks. The most common attacks are blackhole attacks, greyhole attacks, bad-mouthing attacks, and ballot stuffing attacks. The blackhole attackers try to promote their importance by providing good recommendations on themselves. Subsequently, they will drop all the packets received. Instead of dropping all the packets, only partial droppings occur by the greyhole attacks which are more difficult to detect. And by the bad-mouthing attacks, a malicious node ruins the reputation of the well-behaved nodes by providing bad recommendations against those good nodes, while by the ballot stuffing attacks a malicious node provides good recommendations on the bad nodes so as to increase the opportunity of the message dropping. To some extent, these two attacks can make the blackhole and greyhole attacks more effectively. In this paper, it is assumed that malicious nodes will present the following behaviors.

• (1)

Behavior 1. A malicious node will provide good recommendations on itself and the other malicious nodes to the nodes it meets. In this way, the importance of these malicious nodes will be promoted.

(2)

Behavior 2. To reduce the importance of the good nodes, a malicious node will provide bad recommendations on the good nodes to the nodes it meets.

(3)

Behavior 3. A malicious node will drop packets it receives according to the dropping probability. If the dropping probability is set to 1, the node is considered as a blackhole attacker. Otherwise, if the dropping probability is between 0 and 1, the node is considered as a greyhole attacker.

(4)

Behavior 4. In order to increase the concealment, a malicious node could receive packets and forward packets like a normal node.

3. Routing Mechanism with Security Function

The nodes are clustered with different forwarding mechanisms used for intracluster and intercluster routing. By clustering technique, each node will belong to a cluster with a cluster ID and maintain the information of the members in the cluster by a list of parameters such as the node ID. Since the nodes communicate with each other frequently in one cluster, it is assumed that the nodes in the same cluster are friends. The selfish nodes and malicious nodes are only considered possibly existing in other clusters. For intracluster routing, the mechanism “spray and wait” is adopted and there are two copies for each message. For intercluster routing, the Shannon entropy function and a trust model have been used to select the next carrier and avoid attacks from malicious nodes. In this paper, our focus is on the intercluster routing with prevention of the selfish behaviors and malicious attacks. Since the trust value and Shannon entropy function have been used in intercluster routing, we first present the way to compute the trust value and the entropy function. And then the proposed intercluster routing scheme will be introduced.

3.1. Calculation of Trust Value

The trust value between node i and node j at time t is denoted by $T^{ij}(t)$ , which is computed as follows:

$$\begin{array}{cc}& T^{ij}\left(t\right)={\displaystyle \sum }_X^{\text{all}}{w}^x\ast T_X^{ij}\left(t\right),\end{array}$$

(1)

where X represents a trust property with the two attributes of selfishness and centrality, $T_X^{ij}(t)$ is node i's trust value in the trust property X toward node j, and $w^x$ is the weight of the trust property X.

Node i updates its trust value toward node j in the trust property X when encountering a node as follows, assuming the current time is t and $\Delta t$ is the encounter interval:

$$\begin{array}{l}{T}_X^{ij}\left(t+\Delta t\right)=\beta T_{\text{direct},\hspace{0.17em}X}^{ij}\left(t+\Delta t\right)\\ +\left(\mathrm{1}-\beta \right)T_{\text{indirect},\hspace{0.17em}X}^{ij}\left(t+\Delta t\right).\end{array}$$

(2)

When node i encounters the node k, the trust value will be updated. There are two cases which need to be considered. For example, node i updates its trust value towards node j: $k=j$ and $k\ne j$ .

• (i)

When $k=j$ , there are two trust properties used, selfishness and centrality.

$T_{\text{direct},\hspace{0.17em}\text{Selfishness}}^{ij}(t+\Delta t)$ : in social DTNs, some nodes are selfish which are not willing to forward messages from a stranger. However, friends will be cooperative toward each other even if they are selfish. By proposed protocol, each node will have a friend list, denoted by $F_i$ for node i. When node i receives a message from node j, node i will check whether node j is in its friend list. If node j belongs to $F_i$ , then $T_{\text{direct},\hspace{0.17em}\text{Selfishness}}^{ij}(t+\Delta t)$ will be valued to 1. Otherwise, it is assumed that nodes with similar attributes with values computed from a list ( $a_1,a_2,a_3,a_4,a_5$ ) will be easier to become friends. And in each attribute there are five selection froms:

$$\begin{array}{cc}& \left[\begin{array}{cccc}{a}_{\mathrm{11}}& a_{\mathrm{12}}& \cdots & a_{\mathrm{15}}\\ a_{\mathrm{21}}& a_{\mathrm{22}}& \cdots & a_{\mathrm{25}}\\ ⋮& ⋮& & ⋮\\ a_{\mathrm{51}}& a_{\mathrm{52}}& \cdots & a_{\mathrm{55}}\end{array}\right].\end{array}$$

(3)

If node i and node j have m same attributes, then $T_{\text{direct},\hspace{0.17em}\text{Selfishness}}^{ij}\left(t+\Delta t\right)=0.2m$ . To avoid forged information from malicious nodes, an encounter history will be stored. If the information of a node is changed frequently, it will be marked as a malicious node.

$T_{\text{direct},\hspace{0.17em}\text{Centrality}}^{ij}(t+\Delta t)$ : in social DTNs, nodes with high centrality will have higher probability to deliver messages. By the proposed trust protocol, nodes with higher centrality will have higher trust value towards trust property of centrality. The centrality of node i, denoted by ${CT}_i$ , is defined as the number of different clusters that the node i meets per unit time. The trust value on the centrality can be computed as

$$\begin{array}{cc}& T_{\text{direct},\hspace{0.17em}\text{Centrality}}^{ij}\left(t+\Delta t\right)=\frac{{CT}_j}{{CT}_i+{CT}_j}.\end{array}$$

(4)

In this case, these is no indirect trust; node i updates $T_{\text{indirect},\hspace{0.17em}X}^{ij}(t+\Delta t)$ as follows:

$$\begin{array}{cc}& T_{\text{indirect},\hspace{0.17em}X}^{ij}\left(t+\Delta t\right)=e^{-{\lambda }_d\Delta t}\ast T_{\text{indirect},\hspace{0.17em}X}^{ij}\left(t\right).\end{array}$$

(5)

In this way, the indirect trust value will be delayed if there is not new information from other nodes.

• (ii)

When $k\ne j$ , to calculate the indirect trust value, when node i meets node k, node i uses its one-hop neighbors including node k as recommenders to update $T_{\text{indirect},\hspace{0.17em}X}^{ij}\left(t+\Delta t\right)$ and to prevent bad-mouthing and ballot stuffing attacks, for any neighbor node a, $T^{ia}\left(t\right)\ge T^{\text{rec}}$ , where $T^{\text{rec}}$ is a threshold to indicate whether a node is trustworthy. The indirect value can be calculated as follows:

$$\begin{array}{l}{T}_{\text{indirect},\hspace{0.17em}X}^{ij}(t+\Delta t)\\ \hspace{1em}\hspace{1em}=\left\{\begin{array}{ll}{e}^{-{\lambda }_d\Delta t}\ast T_{\text{indirect},\hspace{0.17em}X}^{ij}\left(t\right)\hfill & \left|R_i\right|=\mathrm{0}\hfill \\ \frac{{\sum }_{kϵR_i}\left(T_X^{ik}\left(t\right)\ast T_X^{kj}\left(t\right)\right)}{{\sum }_{kϵR_i}{T}_X^{ik}\left(t\right)}\hfill & \left|R_i\right|\ne \mathrm{0},\hfill \end{array}\right.\end{array}$$

(6)

where $R_i$ is a set including node i's trustworthy neighbors and $\left|R_i\right|$ is the number of node i's trustworthy neighbors.

Since there is no direct trust, the direct trust will be delayed:

$$\begin{array}{cc}& T_{\text{direct},\hspace{0.17em}X}^{ij}\left(t+\Delta t\right)={e^{-{\lambda }_d\Delta t}\ast T}_{\text{direct},\hspace{0.17em}X}^{ij}\left(t\right).\end{array}$$

(7)

3.2. Calculation of the Entropy Function

The entropy function is defined as

$$\begin{array}{cc}& H\left(p\right)=-p{\log }_{\mathrm{2}}p-\left(\mathrm{1}-p\right){\log }_{\mathrm{2}}\left(\mathrm{1}-p\right),\end{array}$$

(8)

where p is the probability of a node forwarding a packet and $H_b\left(p\right)$ is the binary entropy function related to probability p.

According to formula (8), we define our trust value for node i as follows:

$$\begin{array}{cc}& T_{\text{Entropy-Function}}^i=\left\{\begin{array}{cc}\mathrm{1}-H\left(p\right)\hfill & \mathrm{0.5}\le p\le \mathrm{1}\hfill \\ H\left(p\right)-\mathrm{1}\hfill & \mathrm{0}\le p<\mathrm{0.5}.\hfill \end{array}\right.\end{array}$$

(9)

In this way, $T_{\text{Entropy-Function}}^i$ is an increasing function with probability p. If a malicious node drops packets, it will have lower probability p and then have lower $T_{\text{Entropy-Function}}^i$ .

The probability p is quantified based on the observations of a nodes’ forwarding behavior. Assume that the distribution to observe this process follows the binomial distribution. Then, the probability of a node forwarding k packets out of n packets can be computed as follows:

$$\begin{array}{cc}& p\left(t_n=k\hspace{0.17em}|\hspace{0.17em}\tau \right)=\left(\begin{array}{c}n\\ k\end{array}\right){\tau }^k{\left(\mathrm{1}-\tau \right)}^{n-k},\end{array}$$

(10)

where τ is the probability of performing forwarding, $t_n$ represents the number packets forwarded.

According to Bayesian approach, we can get

$$\begin{array}{cc}& p\left(t_{n+\mathrm{1}}=k+\mathrm{1}\hspace{0.17em}|\hspace{0.17em}{t}_n=k\right)=\frac{p\left(t_{n+\mathrm{1}}=k+\mathrm{1},t_n=k\right)}{p\left(t_n=k\right)},\end{array}$$

(11)

where

$$\begin{array}{cc}& p\left(t_n=k\right)\hspace{0.17em}={{\displaystyle \int }}_{\mathrm{0}}^{\mathrm{1}}p\left(t_n=k\hspace{0.17em}|\hspace{0.17em}\tau \right)d\tau ,\\ p\left(t_{n+\mathrm{1}}=k+\mathrm{1},t_n=k\right)={{\displaystyle \int }}_{\mathrm{0}}^{\mathrm{1}}\tau \ast p\left(t_n=k\hspace{0.17em}|\hspace{0.17em}\tau \right)d\tau .\end{array}$$

(12)

Then we can compute

$$\begin{array}{l}p\left(t_{n+\mathrm{1}}=k+\mathrm{1}\hspace{0.17em}|\hspace{0.17em}{t}_n=k\right)\\ \hspace{1em}\hspace{1em}=\frac{{\int }_{\mathrm{0}}^{\mathrm{1}}\tau \ast p\left(t_n=k\hspace{0.17em}|\hspace{0.17em}\tau \right)d\tau }{{\int }_{\mathrm{0}}^{\mathrm{1}}p\left(t_n=k\hspace{0.17em}|\hspace{0.17em}\tau \right)d\tau }=\frac{k+\mathrm{1}}{n+\mathrm{2}}.\end{array}$$

(13)

Therefore, probability p can be expressed as $(k+1)/(n+2)$ .

3.3. Routing Mechanism

As shown in Algorithm 1, when node i encounters node j, the $T_{\text{Entropy-Function}}^j$ will be computed first. A threshold $T_{\text{Entropy-Function}}^{\text{threshold}}$ is defined to identify whether node j is a malicious node. If $T_{\text{Entropy-Function}}^j\ge T_{\text{Entropy-Function}}^{\text{threshold}}$ , node j is admitted as a trustworthy node. And then compute the trust value $T^{ij}\left(t+\Delta t\right)$ . There is another threshold of $T^{\text{threshold}}$ . If $T^{ij}\left(t+\Delta t\right)\ge T^{\text{threshold}}$ , the messages will be forwarded from node i to node j. Using the Shannon entropy function, the blackhole and greyhole attacks can be prevented since in these attacks more packets are dropped than the normal nodes and then the value $T_{\text{Entropy-Function}}^j$ computed will be smaller than the threshold $T_{\text{Entropy-Function}}^{\text{threshold}}$ . By using the direct and indirect trust values, selfish behaviors, bad-mouthing, and ballot stuffing attacks can also be avoided because messages will not be forwarded to a node with lower trust value than the threshold. More details will be introduced in the following.

Algorithm 1: Message forwarding phase.

Message Forwarding Phase (for any node i and j )

(1) WHILE (node i meets node j) THEN

(2)  //compute the Entropy Function $$T_{\text{Entropy-Function}}^j$$ according to formula (9)

(3) IF ( $$T_{\text{Entropy-Function}}^j<T_{\text{Entropy-Function}}^{\text{threshold}}$$ ) THEN

(4)      //Node j is marked as malicious node, do nothing

(5) ELSE

(6) FOR (any node k && $$k\ne j$$ )

(7) //Compute indirect value $$T_{\text{indirect},X}^{ik}(t+\Delta t)$$ where node k is recommended by node j

  and one-hop neighbors of node i according to formula (6).

(8)      ENDFOR

(9)      //Compute the direct trust value $$T_{\text{direct},X}^{ij}(t+\Delta t)$$ with two attributes (selfishness, centrality).

(10)   //Compute $$T_X^{ij}(t+\Delta t)$$ by combining $$T_{\text{direct},X}^{ij}$$ ( $$t+\Delta t)$$ and $$T_{\text{indirect},X}^{ij}$$ ( $$t+\Delta t)$$ according to formula (2).

(11)   //Compute $$T^{ij}\left(t+\Delta t\right)$$ by combining all attributes (selfishness, centrality) according to formula (1).

(12)   IF ( $$T^{ij}\left(t+∆t\right)\ge T^{\text{threshold}}$$ )

(13)      //Node j is marked as a trustworthy node and messages will be forwarded to node j.

(14)   ELSE

(15)      //do nothing

(16)   ENDIF

(17) ENDIF

(18) ENDWHILE

As shown in Figure 3, each node will have a list of its attributes, centricity, and forwarding probability and a list of the information from other nodes. And $a_{11},a_{12},\dots ,a_{15}$ is used to represent the value of the attribute $a_1,a_{21},a_{22},\dots ,a_{25}$ is used to represent the value of the attribute $a_2$ , and it is similar for the attributes $a_3,a_4,a_5$ . In Figure 3, node j is a malicious node to launch a greyhole attack, which drops part of the received messages, and node l launches a blackhole attack to drop all the received messages.

Figure 3

Routing procedure.

In step one, when messages are required to be forwarded, node s should select a relay node according to the value including direct trust, indirect trust, and entropy function. In the figure, node s meets node i and node j and updates the information of trust value and entropy function. Since node j has dropped some of the messages it received, the value of entropy function will be lower which is smaller than the threshold of 0.5, and messages will not be forwarded to node j. Similarly, messages will not be forwarded from node i to node l in step two because all messages received by node l have been dropped. Therefore, by the proposed routing mechanism, the greyhole and blackhole attacks can be prevented.

Moreover, the proposed scheme can prevent the bad-mouthing attacks, by which a malicious node ruins the reputation of well-behaved nodes by providing bad recommendations against good nodes. By the proposed routing mechanism, the recommendation value is the average value of the recommendations from the one-hop neighbor nodes. And each recommendation from the neighbor will have a valid range. The recommendation out of range will not be considered. In this way, the recommendation value from one malicious node will not make much effect to the average value. This method is also efficient for the ballot stuffing attacks. Therefore, the bad-mouthing and ballot stuffing attacks can be avoided by the routing mechanism.

4. Performance Analysis

4.1. Theoretical Analysis for Delivery Probability

As shown in the system model, the mobility model is a Markov process, where nodes will change from one state to another due to movement. For any node k, let $S_n$ be the nth state, and $P(i,j,t)$ represents in the period time t; node k changes from state i to state j. We can get $P(i,j,t)$ as

$$\begin{array}{cc}& P\left(i,j,t\right)=P\left(S_{n+\mathrm{1}}=j,\Delta t\le t\hspace{0.17em}|\hspace{0.17em}{S}_n=i\right).\end{array}$$

(14)

In the Markov process, $P(i,j)$ indicates the probability of node k from state i to state j. And $P(i,j)$ can be represented as

$$\begin{array}{cc}& P\left(i,j\right)=P\left(S_{n+\mathrm{1}}=j\hspace{0.17em}|\hspace{0.17em}{S}_n=i\right).\end{array}$$

(15)

$G(i,j,t)$ can be used to represent that the time from state i to state j is less than t. And $G(i,j,t)$ is shown as

$$\begin{array}{l}G\left(i,j,t\right)=P\left(\Delta t\le t\hspace{0.17em}|\hspace{0.17em}{S}_{n+\mathrm{1}}=j,S_n=i\right)\\ ={\displaystyle \sum }_{\mathrm{1}\le u\le t}^{}P\left(\Delta t=u\hspace{0.17em}|\hspace{0.17em}{S}_{n+\mathrm{1}}=j,S_n=i\right).\end{array}$$

(16)

And then $P\left(i,j,t\right)$ can be computed using $P\left(i,j\right)$ and $G\left(i,j,t\right).$ Consider

$$\begin{array}{l}P\left(i,j,t\right)=P\left(S_{n+\mathrm{1}}=j,\Delta t\le t\hspace{0.17em}|\hspace{0.17em}{S}_n=i\right)\\ =P\left(\Delta t\le t\hspace{0.17em}|\hspace{0.17em}{S}_{n+\mathrm{1}}=j,S_n=i\right)\\ \hspace{1em}\times P\left(S_{n+\mathrm{1}}=j\hspace{0.17em}|\hspace{0.17em}{S}_n=i\right)\\ =G\left(i,j,t\right)\times P\left(i,j\right).\end{array}$$

(17)

As $P(i,j,t)$ is the probability of node k from state i to state j directly in the period time t, however, node k may enter another state and then enter the state j. So we use $Q(i,j,t)$ represents this situation. Consider

$$\begin{array}{l}Q\left(i,j,t\right)\\ \hspace{1em}={\displaystyle \sum }_{r=\mathrm{1}}^m\hspace{0.17em}{\displaystyle \sum }_{u=\mathrm{1}}^t\left(P\left(i,r,u\right)-P\left(i,r,u-\mathrm{1}\right)\right)\times Q\left(r,j,t-u\right)\\ \phantom{xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx}j\ne i,\end{array}$$

(18)

where m is the number of states that node k may enter. In other words, $Q(i,j,t)$ is, in fact, the probability of node k from the source cluster to the destination cluster, denoted by $P_{c-c}\left(\Delta t\le t\right)$ . Since in the same cluster, nodes communicate with each other frequently, it is assumed that the delivery ratio in one cluster is 1. So we can approximately compute the delivery ratio as

$$\begin{array}{cc}& P_{\text{delivery}}\left(\Delta t\le t_N\right)={{\displaystyle \sum }}_{\mathrm{0}\le i<T_N}^{}{P}_{c-c}\left(\Delta t\le i\right).\end{array}$$

(19)

Since there is a limited capacity for the cache at each node, when enough messages are generated, the cache could be overflowed, and the messages could be dropped. To compute the delivery probability, the service efficiency of the network δ should be known. Let ρ to be the ratio of customer service per unit time; we can obtain

$$\begin{array}{cc}& \rho =\frac{\mathrm{1}}{T_N}{{\displaystyle \sum }}_{i=\mathrm{1}}^{T_N}{P}_{\text{delivery}}\left(\Delta t\le i\right).\end{array}$$

(20)

Let λ be the arrival rate of the messages and $B_{\mathrm{Max}}$ be the maximum cache available. Since there are malicious nodes in the network, by the trust routing scheme, these nodes will be detected and will not be selected as next carrier. It can also be modeled that the cache becomes smaller. Therefore, we can get the new maximum cache $B_{\mathrm{Max}}^{\prime }={\omega B}_{\mathrm{Max}}$ , where ω is the percentage of the malicious nodes in the whole collection of the nodes. We can compute δ as

$$\begin{array}{cc}& \delta =\frac{\left(\lambda \ast T_N\ast \rho +B_{\mathrm{Max}}^{\prime }\right)}{\left(\lambda \ast T_N\right)}.\end{array}$$

(21)

Since we have obtained the delivery probability without considering the cache in formula (19), and according to the service efficiency, the delivery probability with the limited cache $P_{\text{inter-cluster}}^{\prime }\left(\Delta t\le T_N\right)$ can be approximated as

$$\begin{array}{cc}& P_{\text{delivery}}^{\prime }\left(\Delta t\le T_N\right)\approx \delta \ast P_{\text{delivery}}\left(\Delta t\le t_N\right).\end{array}$$

(22)

What is more, the service efficiency of the network δ can be approximately used as the forwarding probability to select proper $T_{\text{Entropy-Function}}^{\text{threshold}}$ .

4.2. Analysis for Average End-to-End Delay

As we all know, if the delivery ratio is close to 1, it indicates that most of the messages have been delivered.

When the delivery ratio $P_{\text{inter-cluster}}^{\prime }\hspace{0.17em}\left(\Delta t\le T_N\right)$ is close to 1, the average delay can be obtained as

$$\begin{array}{cc}& D_{\text{delay}}\approx {\displaystyle \sum }_{i=\mathrm{1}}^{T_N}{P}_{\text{delivery}}^{\prime }\left(\Delta t\le i\right).\end{array}$$

(23)

4.3. Complexity Analysis

It is assumed that there are M nodes in the network; according to the mechanism introduced in Section 3, the complexity analysis can be divided to four parts: the complexity of direct trust value, the complexity of indirect trust value, the complexity of entropy function, and the complexity of message forwarding. First, when the direct trust value is computed, in the worst case, any two nodes need to make finite computations, and there are maximum $M\ast (M-1)/2$ combinations of nodes. Therefore, the complexity of the direct trust value will be $O(M^2)$ . Second, when the indirect trust value is computed, for each node, it should integrate the indirect trust value from its $M-1$ neighbors. For each node, it should compute the indirect trust value for the other maximum $M-1$ nodes. So the complexity of indirect value is $O(M^2)$ , and for M nodes, the complexity of the indirect value is $O(M^3)$ . When the entropy function is computed, for each node, it should make finite computations for other $M-1$ nodes. Therefore, the complexity of the entropy function for each node is $O(M)$ and for M nodes, the complexity is $O(M^2)$ . Last, when messages are forwarded, there are finite comparisons for each transmission. Assume that there is no loop in the transmission of the messages, the complexity of message forwarding for each message is $O(M)$ . If there are N messages required to be transmitted, the complexity will be $O(M\ast N)$ . For the entire routing scheme, the complexity is $O(M\ast N+M^3)$ by combining all the four parts.

4.4. Simulation Analysis

The simulation experiments have been performed by using QualNet. Simulation parameters are shown in Table 1. As mentioned in system model, we set $P_H=0.7$ and $P_C=0.1$ for 80% of the nodes at each hot spot and $P_H=0.5$ and $P_C=0.1$ for other 20% nodes. And 100 nodes in total are distributed. The WIFI is adopted as the communication medium among all the mobile nodes and the radio range is about 250 meters. The simulation time is set to 10000 s with a 500 s warm-up period. And the size of simulation area is set to 3000 m ∗ 3000 m. CBR traffic is used for the data generation with 0.1 arrival rate. What is more, the malicious nodes could launch different types of attacks including blackhole attacks, greyhole attacks, bad-mouthing attacks, and ballot stuffing attacks randomly.

Table 1

Simulation parameters.

Parameter	Value
Simulation time	10000 S
Size of area	3000 * 3000
Warm-up time	500 S
Number of nodes	50
Traffic	CBR
Transmission range	250 M
Message size	150 Byte
Rate of message sending	0.1
MAC protocol	802.11
$$T_{\text{Entropy-Function}}^{\text{threshold}}$$	0.7
$$T^{\text{threshold}}$$	0.65

We compare the performance of our proposed solution with that of the clustering and network coding based efficient routing in social DTNs (CCS-DTN) [22], Bayesian [13], and PROPHET [3]. The successful delivery rate, defined as the ratio of the number of messages that have been successfully received by the destination over the number of messages that the source nodes have sent, and the average end-to-end delay, defined as the average time used for a message transmitted from a source to its destination, have been measured. What is more, the simulation results have been compared with those obtained from the theory analysis.

With the change of the number of malicious nodes, the performance in terms of successful delivery ratio has been shown in Figure 4. Clearly, the successful delivery ratio has become lower with the increase of the percentage of the malicious nodes because the number of messages dropped due to the attacks from the malicious nodes has been increased. When there are small malicious nodes, the delivery ratio of CCS-DTN is higher than TR_SDTN since the few packets dropped can be recovered by the network coding technology. But with the increase of malicious nodes, in CCS-DTN, many messages are dropped by the malicious nodes which cannot be recovered by the network coding technology while in TR_SDTN, messages will not be forwarded to the malicious nodes and there are smaller messages dropped. Therefore, the delivery ratio of TR_SDTN is higher than that of CCS-DTN when the number of malicious nodes is enough. What is more, When there are less malicious nodes, the delivery ratio by the proposed TR_SDTN scheme is much higher than that by the Bayesian scheme because, by the proposed TR_SDTN scheme, the social characteristics of the nodes in the network have been efficiently used. What is more, since there is no mechanism to tackle the malicious attacks in the Bayesian scheme, the delivery ratio has declined much quicker than that by the proposed TR_SDTN scheme.

Figure 4

Impact of malicious nodes on delivery ratio.

Meanwhile, as shown in Figure 5, as more malicious nodes exist in the network, more messages will be dropped. In this process, the messages to be delayed longer time will have higher probability to be dropped. Therefore, with the increase of percentage of malicious nodes, the average end-to-end delay becomes lower. Besides, compared with the Bayesian scheme and PROPHET scheme, the proposed TR_SDTN scheme has shown much lower average end-to-end delay due to the efficient use of the social characteristics of the nodes in the network. And the proposed TR_SDTN scheme can make the packet forwarded to destination much more quickly.

Figure 5

Impact of malicious nodes on average end-to-end delay.

Compared with the CCS-DTN and the PROPHET schemes, the delivery ratio of TR_SDTN has a slower decrease since the trust mechanism can detect the malicious nodes and avoid messages which are forward to these nodes. Using this method, messages dropped are declined. Another reason for the decline of delivery probability of TR_SDTN is that, with the increase of percentage of the malicious nodes, the number of available nodes becomes smaller which leads more messages to be dropped since available cache becomes smaller. What is more, we can find that the delivery probability of CCS-DTN decreases slower than that of the PROPHET scheme because some messages dropped are recovered by the network coding mechanism.

Another measurement on the network states for the evaluation is the number of mobile nodes. In the simulation, the percentage of the malicious nodes has been set as 20% of the total number of the nodes in the network. As shown in Figure 6, the average delivery ratio increases with the increase of the number of mobile nodes. Firstly, we can find when the number of nodes is in the range of 20 to 70, the increase of delivery ratio is faster. When there are only a small number of the nodes, the messages cached in the network will be limited and the contacts among mobile nodes will be not frequent, and many messages will be dropped. With the increase of the number of the nodes, this situation has been quickly mitigated. When the number of the nodes reaches a certain level, there is enough capacity of the caches in the network and nodes have more chances to contact with each other; the delivery ratio becomes stable. Lastly, the delivery ratio by the TR_SDTN scheme is significantly greater than those of the other three schemes including the CCS-DTN, the PROPHET, and the Bayesian scheme when the number of nodes reaches a certain level because, by the proposed trust mechanism, the messages will not be forwarded to the malicious nodes and there is enough capacity of the caches to keep these messages. We can conclude from the above mentioned facts that the proposed TR_SDTN scheme can approach a much better performance than those of the other three schemes for the social DTNs. Moreover, it is found that the results obtained from the mathematical analysis and the results from the simulations have shown only a little difference. That is to say, these results have been proved by each other to show the consistency.

Figure 6

Impact of number of nodes on delivery ratio.

The next simulation is to study the impact of the trust threshold on the delivery ratio. As shown in Figure 7, when the threshold is determined, the delivery ratio will become lower with the increase of the number of malicious nodes. And it is clear that, with different trust thresholds, the delivery ratios will be different. In the figure, when the trust threshold is 0.65, the delivery ratio is the largest among the other values of the threshold. When the trust threshold is too high, although the malicious nodes have been excluded, some normal nodes will be prevented from receiving messages because their trust values are lower than the threshold. With the reduction of the trust threshold, more and more malicious nodes could be allowed to receive messages. In this way, more and more messages will be dropped by the malicious nodes, and the delivery ratio becomes lower.

Figure 7

Impact of the trust threshold on delivery ratio.

The last simulation it to study the impact of the entropy function threshold on the delivery ratio. As shown in Figure 8, with the different threshold values, the delivery ratios will be different. When the threshold is 0.5, the delivery ratio is the largest among the other values of the thresholds. From the entropy function defined in formula (8), we can find that the major impact factor of the entropy function is the forwarding probability of each node. Since the cache is limited, some messages will be dropped at each node. There is a normal range of the values of the forwarding probability for each node. When the threshold of the entropy function is too high, the threshold of the forwarding probability will be also high. In this situation, many normal nodes would not be able to forward messages, which leads to the lower delivery ratio. With the increase of malicious nodes, the available normal nodes become fewer and fewer with more and more messages dropped. The delivery ratio declines faster. When the threshold of the entropy function is small, the threshold of the forwarding probability will be also small. In this case, the malicious nodes which launch greyhole attacks could be allowed to receive messages. At these nodes, more messages will be dropped than the normal nodes making the delivery ratio lower. So a proper threshold of the entropy function is important for the design of the routing mechanism.

Figure 8

Impact of entropy function threshold on delivery ratio.

5. Conclusion

In this paper, according the characteristics of the nodes and by analyzing the possible attacks in hostile social DTNs, we have proposed a novel TR_SDTN routing algorithm, by which, in the hostile social DTN environments, a direct trust model, an indirect trust model, and the Shannon entropy function have been combined to make full use of nodes’ selfishness and prevent blackhole attacks, greyhole attacks, bad-mouthing attacks, and ballot stuffing attacks from the malicious nodes. The theoretical analysis and the simulation results have consistently shown that, in the hostile social DTN environments, better performance can be achieved by the proposed TR_SDTN scheme.