INT J COMPUT COMMUN, ISSN 1841-9836 8(5):744-753, October, 2013. Performance Analysis of Epidemic Routing in DTN with Overlapping Communities and Selfish Nodes Y. Wu, S. Deng, H. Huang, Y. Deng Yahui Wu, Su Deng, Hongbin Huang Science and Technology on Information Systems Engineering Laboratory National University of Defense Technology Changsha, 410073, China wuyahui@nudt.edu.cn, yahui_wu@163.com, dzyxxxb@163.com Yiqi Deng University College London Department of Computer Science zndxxb@sina.com Abstract: Routing algorithms in delay tolerant networks (DTN) adopt the store- carry-forward way, and this needs the nodes to work in a cooperative way. However, nodes may not be willing to help others in many applications and this behavior can be seen as individual selfish. On the other hand, nodes often can be divided into different communities, and nodes in the same community often have some social ties. Due to these social ties, nodes are more willing to help the one in the same community. This behavior can be seen as social selfish. Note that some nodes may belong to more than one community in the real world, and this phenomenon makes the network have overlapping communities. This paper proposed a theoretical model to describe the performance of epidemic routing (ER) in such network. Simulation results show the accuracy of our model. Numerical results show that the selfish nature can make the performance of the routing policy be worse, but those nodes belonging to multi-communities can decrease the impact of the selfish nature in certain degree. Keywords: Delay Tolerant Networks (DTN), selfish nodes, overlapping communities, epidemic routing, performance analysis. 1 Introduction At present, there has been a growing interest to study the communication policy for challenged networking applications, such as deep-space exploration [1], vehicular networks [2], mobile social networks [3], etc. In these new environments, the end-to-end connectivity cannot be assumed because the network is quite sparse or nodes are moving fast. That is, a complete path from source to destination does not exist or such a path is highly unstable and may change or break soon after it has been discovered. These networks belong to the general category of Delay Tolerant Networks (DTN) [4]. In traditional Mobile Ad Hoc Networks (MANET), nodes communicate with each other based on the assumption that there exists at least one fully connected path between communication nodes. Therefore, routing policies in MANET cannot be used directly in DTN. In order to overcome the network partitions, nodes of DTN communicate through a store-carry-forward mode. Due to the node mobility, different links come up and down. If the sequence of connectivity graphs over a time interval is overlapped, then an end-to-end path might exist, so the message should be forwarded over the existing link, stored and carried at the next hop until the next link comes up [5]. Many routing policies have been proposed in DTN. According to the number of replicas, these policies can be divided into two classes: that is, single-copy and multi-copy. In the first class, nodes keep only one copy of the message and attempt to forward that copy towards the node which has higher probability to meet the destination, such as the works in [6], [7], etc. Therefore, Copyright c⃝ 2006-2013 by CCC Publications Performance Analysis of Epidemic Routing in DTN with Overlapping Communities and Selfish Nodes 745 how to select the proper relay nodes to carry the copy is critical. In the multi-copy methods, one message may have many replicas and they are transited at the same time to increase the successful ratio [8]- [9]. The core is to select proper relay nodes to store or forward these copies. Therefore, routing policies in both classes depend on the help of other nodes. However, nodes may not be willing to help others due to the constraint of buffer space or power resources [10]. This behavior can be seen as individual selfish [11]. Hui et al. studied the its impact in mobile social network, and they found that mobile social network is robust to the individual selfish due to the multiple paths [11]. Then, it was studied further in [12]. There are also some incentive methods to make nodes be cooperative[13]-[14]. On the other hand, nodes can be divided into different communities according to their interesting, citation relation, etc. Obviously, nodes in the same community often have some social ties, and they are more willing to help each other. This behavior can be seen as social selfish. Li et al. proposed this behavior for the first time [15]. Its impact on the routing performance of ER was explored in [16], and then they studied the impact of both individual selfish and social selfish on multicasting application [17]. However, above works failed to consider the fact that some nodes may belong to more than one community which is common in the real world [18]. In this paper, we studied the routing performance of ER in DTN with overlapping commu- nities and selfish nodes by the Markov process for the first time. At present, many researchers are interesting in ER algorithm [19]. For example, the performance of ER based on the sparsely exponential graph was studied in [20], and the problem was explored again with heterogeneous nodes [21]. The performance of two-hop relay routing (a special case of ER) under limited packet lifetime was studied in [22]. The authors in work [23] studied the routing performance with con- tention. In addition, some works begin to study how to decrease the energy consumption of ER. Authors in [24] proposed the optimal probabilistic forwarding policy under a fluid model approximation, and they proved that the optimal policy is the threshold form. Then, they ad- dressed the problem of online estimation of optimal policies in [25], and explored the problem with heterogeneous nodes in [26]. The optimal forwarding problem with multiple destinations was proposed in [27]. Li et al. designed an optimal relaying scheme for DTN, which considers nodes’ heterogeneous contact rates and delivery costs when selecting relays to minimize the de- livery cost while satisfying the required message delivery probability [28]. The optimal control problem with dead nodes was proposed in [29]. However, to our best knowledge, none of the works considered the problem as ours. 2 Network Model The set of nodes in the network is denoted by V. Besides the source S and destination D, every node belongs to at least one of the two communities, which are denoted by C 1 and C 2, respectively. It is easy to see that the source and destination may belong to any class. For simplicity, we assume that D belongs to C 1 and S belongs to C 2. In fact, our work can be extended to other cases easily. Nodes other than the destination can be seen as relay nodes. The number of relay nodes in the first class is M and the second class has N nodes. Due to the overlap of the communities, there are O<= min {M, N -1} nodes belonging to both classes. Therefore, there are totally V =M +N +1-O nodes. The link exists between two nodes only when they come into the transmission range of each other, which means a contact, so the mobility of the users is critical. In this paper, we assume that the occurrence of contacts between two nodes follows a Poisson distribution, which is found in many well-known mobility models, such as random waypoint and random direction [30]. This assumption also has been checked by certain real motion traces [31]. Therefore, we can assume that the inter-meeting time between two contacts follows an exponential distribution 746 Y. Wu, S. Deng, H. Huang, Y. Deng with parameter λ . Nodes may not be willing to help others due to the individual selfish nature. In this paper, we assume that nodes in C 1 help the one in the same class with probability p1, and nodes in C 2 help the one in the same class with probability p2. On the other hand, nodes is social selfish, so we assume that nodes in C 1 help nodes belonging to C 2 with probability p12, and nodes in C 2 help nodes belonging to C 1 with probability p21. In fact, many papers used this mode to denote the selfish nature of nodes [15], [16] [17], etc. Because nodes are more willing to help the one in the same community, we have p1 > p12 and p2 > p21. In addition, for any two nodes i and j which belong to C 1 and C 2 at the same time, we assume that they communicate with each other with probability p >= max {p1, p2}. This assumption is based on the observation that nodes having more common hobbies often have much closer relationship. Therefore, they are more willing to help others. For simplicity, we assume p=max{p1, p2} in this paper. That is, if p1 > p2, nodes i and j communicate with probability p1, or with probability p2. 3 Data Dissemination Process and Performance Analysis Now, we begin to explore the data dissemination process based on the ER algorithm. First, we give a new classification of the nodes. In particular, nodes only belonging to C 1 are denoted by C 11, and nodes just belonging to C 2 are denoted by C 22. Nodes belonging to both C 1 and C 2 are denoted by C 12. Therefore, class C 11 has M-O relay nodes, class C 22 has N-O relay nodes, and class C 12 has O relay nodes. A snapshot of the network can be seen in Figure 1. Figure 1: A snapshot of the network The dashed lines in Figure 1 mean that the link between the nodes is opportunistic. The caption on the line denotes the forwarding probability. Specially, it denotes the forwarding probability from the starting point to the end point. On the other hand, we have p1m=max{p1, p21} and p2m=max{p2, p12}. That is, for any node i in C 11 and j in C 12, because j takes i as a friend, it forwards toward i with probability p1. However, node j also belongs to C 2, if nodes in C 2 are altruism, node j may forward toward i with probability p21 which is bigger then p1. Therefore, j should forward to i with probability p1m. We can get the meaning of p2m according to above analysis easily. 3.1 Date Dissemination Model Let X (t) denote the number of relay nodes in class C 11 which is carrying data at time t (not including D), Y (t) denote the number of nodes carrying data in C 22 (including S ), and Z (t) denote the corresponding number in C 12. Therefore, the state of the network at time t can be denoted as (X (t), Y (t), Z (t)), and there are totally (M-O+1)( N-O+1)(O+1) transient states. When the destination gets data, the transmission stops, and this state can be seen as the absorption state which is denoted by Dst. From state (X (t), Y (t),Z (t)), the network may change to one of the following four states through one-step transition, that is, S 1=(X (t)+1, Y (t),Z (t)), S 2=(X (t), Y (t)+1,Z (t)), S 3=(X (t), Performance Analysis of Epidemic Routing in DTN with Overlapping Communities and Selfish Nodes 747 Y (t),Z (t)+1) and Dst. State S 1 means that one node in C 11 received data. Obviously, one premise condition of this transition is X (t)< M-O, which means that at least one relay node in C 11 does not receive data at time t. The node in C 11 which just received data can get the data from nodes in any class. For simplicity, if the node received data from node j, we say that the transition is triggered by j. Obviously, node j may be any node in the network which is carrying data. If j is in class C 11, one node in C 11 without data must encounter with node j, and node j is also willing to forward data to it. Because there are X (t) nodes in the class C 11 carrying data at time t, so there are M-O- X (t) nodes without data in C 11. Obviously, node j may be any node in the X (t) nodes, and the new node which just received data may be any one in the M-O- X (t) nodes. In addition, nodes encounter with each other according to the exponential distribution with parameter λ , combining the selfish behavior, we know that the transition rate is λ X (t)(M-O- X (t))p1. If the transition is triggered by nodes in C 22, nodes without data in C 11 must encounter with one node which has received data before in C 22. Because there are Y (t) nodes in the class C 22 which is carrying data at time t, and nodes in C 22 forward to nodes in C 11 with probability p21, we can know that the transition rate is λ Y (t)(M-O- X (t))p21. By the same method, we know that if the data comes from C 12, the transition rate is λ Z (t)(M-O- X (t))p1m. Now, we can get the total transition rate from state (X (t), Y (t),Z (t)) to S 1 through one-step transition which is shown as follows, (X(t),Y (t),Z(t)) → S1,rateλ(M − O − X(t))(X(t)p1 + Y (t)p21 + Z(t)p1m) (1) Similarly, we can get the transition rate from state (X (t), Y (t),Z (t)) to S 2 and S 3 through one-step transition, which is shown as follows, (X(t),Y (t),Z(t)) → S2, rateλ(N − O − Y (t))(X(t)p12 + Y (t)p2 + Z(t)p2m), (X(t),Y (t),Z(t)) → S3, rateλ(O − Z(t))(X(t)p1 + Y (t)p2 + Z(t)p) (2) If the network comes into Dst from state (X (t), Y (t),Z (t)), the destination D must receive data. According to above analysis and the forwarding probability in Figure 1, we can get, (X(t),Y (t),Z(t)) → Dst, rateλ(X(t)p1 + Y (t)p21 + Z(t)p1m) (3) Let Q denote the generate matrix which is defined as follows, Q = ( T R 0 0 ) (4) The elements in the matrix are different. T is a sub-matrix and it denotes the rate of the transition from one transient state to another. So the number of the rows and columns of the matrix is both (M-O+1)(N-O+1)(O+1). R is a column vector with (M-O+1)(N-O+1)(O+1) elements and it denotes the rate of the transition from one transient state to the absorbing state Dst. The left 0 is a row vector with (M-O+1)(N-O+1)(O+1) elements and it denotes the rate of the transition from Dst to any transient state. The right 0 is a vector with only one element and it denotes the rate of the transition from Dst to Dst. According to Equations (1), (2) and (3), we can get every element of Q. For example, from state (x, y, z ), we have,  T(x + 1,y,z|x,y,z) = λ(M − O − x)(xp1 + yp21 + zp1m), T(x,y + 1,z|x,y,z) = λ(N − O − y)(xp12 + yp2 + zp2m), T(x,y,z + 1|x,y,z) = λ(O − z)(xp1 + yp2 + zp), R(Dst|x,y,z) = λ(xp1 + yp21 + zp1m), R(others|x,y,z) = 0 (5) Symbol others may be any state other than (x +1, y, z ), (x, y+1, z ), (x, y, z +1) and Dst. 748 Y. Wu, S. Deng, H. Huang, Y. Deng 3.2 Performance Analysis First, we define the one-step transition probability matrix P which can be got from the generator matrix Q easily. For example, the transition probability from state i to j is P(j|i), which is an element of P. Each row of Q represents the transition rate from one state to others. Therefore, the sum of all elements in one row denotes the rate of leaving the current state. For example, given state SS, the rate of leaving this state denoted by speed(SS ) can be shown as, speed(SS) = ∑ i∈Sspace Q(i|SS) (6) Symbol Sspace represents the set of all valid states and Q(i|SS ) is one element in Q which represents the transition rate from SS to i. Now, we can get the probability of the transition. P(i|SS) = Q(i|SS)/speed(SS), i ∈ Sspace (7) Let DT (k ) denote the average delivery delay till D received data, starting from state k = (x, y, z ). Obviously, we have DT (Dst)=0. Similarly, let ST (k ) denote the residence time in state k and we also have ST (Dst)=0. For any transient state k, we have speed (k )>0 and ST (k )=1/speed (k ).By conditioning on the one-hop transition out of the current state, we have DT(k) = ∑ j∈Sspace−{k} P(j|k)DT(j) + ST(k) = ∑ j∈Sspace P(j|k)DT(j) + ST(k) − P(k|k)DT(k) = ∑ j∈Sspace P(j|k)DT(j) + ST(k) (8) Define DT as a column vector of the average delivery delay starting from any valid transient state, and ST also a column vector of the residence time. Then, we can obtain, DT = P ∗ DT + ST ⇒ DT = (I − P)−1ST (9) Because only the source has data at the beginning, we know that the initial state is initial- state=(0, 1, 0). Therefore, the average delivery delay is DT(initialstate). Now, we begin to compute the average energy cost using similar method. Here, we only consider the energy cost in the transition process. As descried in [24], [25] and [26], the energy cost is proportional to the number of transmissions which contain both the forwarding and receiving process. In this paper, we use the number of transmissions to denote the energy cost simply. Let ER(k ) denote the average energy cost till D received data, starting from state k = (x, y, z )), obviously ER(Dst)=0. According to above analysis, from state k, the network may come into any state of the following four states: k 1=(x +1, y, z ), k 2=(x, y+1, z ), k 3=(x, y, z+1) and Dst. Obviously, if the network changes into one of them, one node must forward data and the other one must receive data. That is, if the network changes state, there is one transmission. Therefore, we can obtain, ER(k) = P(k1|k)(1 + ER(k1)) + P(k2|k)(1 + ER(k2)) + P(k3|k)(1 + ER(k3)) + P(Dst|k)(1 + ER(Dst)) = ∑ j∈Sspace P(j|k)(1 + ER(j)) = ∑ j∈Sspace P(j|k) + ∑ j∈Sspace P(j|k)ER(j) = 1 + ∑ j∈Sspace P(j|k)ER(j) (10) Define ER as the corresponding column vector. Equation (10) can be changed to the following equation. ER = P ∗ ER + e ⇒ ER = (I − P)−1e (11) Symbol e is a column vector and every element in it equals to 1. Therefore, the average energy cost starting from state initialstate=(0, 1, 0) is ER(initialstate). Performance Analysis of Epidemic Routing in DTN with Overlapping Communities and Selfish Nodes 749 10 20 30 40 50 60 70 80 90 100 200 400 600 800 1000 1200 1400 1600 Number of relay nodes A ve ra g e d e liv e ry d e la y (s ) Theoretical, RWP Simulation, RWP (a) RWP mobility mode 10 20 30 40 50 60 70 80 90 100 0.4 0.6 0.8 1 1.2 1.4 1.6 1.8 2 2.2 2.4 x 10 5 Number of relay nodes A ve ra g e d e liv e ry d e la y (s ) Theoretical, Poisson contact model Simulation, Poisson contact model (b) Poisson contact model Figure 2: Theoretical and simulation result comparison of the average delivery delay 4 Simulation and Numerical Results 4.1 Simulation Results In this section, we will check the accuracy of our theoretical model, and we run several simulations using the Opportunistic Network Environment (ONE) simulator [32]. The simulation is based on both synthetic mobility model and real-world-based scenarios. The synthetic model is the famous Random Waypoint (RWP) mobility model. In this model, the simulation terrain is 1000mĄÁ1000m, and the speed varies from 0.5 to 1.25m/s. The transmission range is 2m. For the real-world-based scenario, we use the Poisson contact model. Specially, we have λ =3.71ĄÁ10-6s−1. As shown in [17] and [33], this value is obtained from the vehicle model, which is based on real motion traces from about 2100 operational taxis for about one month in Shanghai city collected by GPS. Authors of [34] proposed a least-fitting method to identify the exponential parameter and find that above value is well proper. For the theoretical model related parameters, we set p1=0.5, p12=0.2, p2=0.8 and p21=0.1. As described above, there are totalnum=M+N-O relay nodes in the network. Without loss of generality, we set M=N and O=0.2totalnum. Through let the number of relay nodes increase from 10 to 100, we get the results in Figure 2. From the result we can see that the average deviation between the theoretical results and the simulation is very small. For example, the deviation is about 2.8% for the RWP mobility model and 4.6% for the Poisson contact model. This demonstrates the accuracy of our theoretical model. Then, we will use the theoretical results obtained by our model to evaluate the performance in different cases. 4.2 Performance Analysis with Numerical Results First, we will explore the impact of the overlap between communities. Here, we increase the value of O continuously till reaching to totalnum. Let the ratio O/totalnum increase from 0.1 to 1. Other settings are the same as that in RWP model in the simulation. The numerical results are shown in Figure 3 when the number of relay nodes equals to 20, 40 and 80, respectively. Figure 3 shows that if there are more nodes belonging to both communities at the same time, the average delivery delay will be smaller. For example, when N =20, the average delivery delay is reduced by about 79.2% when the value of O/totalnum increases from 0 to 1. However, the value of O/totalnum has little influence on the average energy cost. Then, we will explore the impact of the overlap when the selfish level is different. First, we explore the case with different social selfish level, so we can assume that nodes in the same community are altruism for each other, that is p1=p2=1. The total number of relay nodes 750 Y. Wu, S. Deng, H. Huang, Y. Deng 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 100 200 300 400 500 600 700 800 900 1000 Value of O/totalnum A ve ra g e d e liv e ry d e la y (s ) N=20 N=40 N=80 (a) Average delivery delay 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 10 15 20 25 30 35 40 45 50 55 Value of O/totalnum A ve ra g e e n e rg y co st N=20 N=40 N=80 (b) Average energy cost Figure 3: Impact of the overlap phenomena with different number of relay nodes 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 180 200 220 240 260 280 300 320 340 360 Value of O/totalnum A ve ra g e d e liv e ry d e la y (s ) p 12 =p 21 =0.1 p 12 =p 21 =0.5 p 12 =p 21 =0.8 p 12 =p 21 =1 (a) Average delivery delay 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 20 20.5 21 21.5 22 22.5 23 23.5 24 24.5 25 Value of O/totalnum A ve ra g e e n e rg y co st p 12 =p 21 =0.1 p 12 =p 21 =0.5 p 12 =p 21 =0.8 p 12 =p 21 =1 (b) Average energy cost Figure 4: Impact of the overlap phenomena with different level of social selfish totalnum is 40, and we have M=N. Other settings are also the same as that in RWP model. We set p12= p21, and let their value equal to 0.1, 0.5, 0.8 and 1, respectively. Through letting O/totalnum increase from 0.1 to 1, we can get Figure 4. From Figure 4 we can see that with fixed social selfish level, the average delivery delay is decreasing with the increasing of the nodes in C 12 when p12= p21<1. When p12= p21=1, every node is altruism, so the overlap between communities cannot have any impact. This result also shows that the smaller of p12 (p12= p21), the bigger of the decreasing ratio will be. In addition, the difference of the delivery delay with different social selfish level is decreasing with O/total- num, and they have the same value when O/totalnum=1. Figure 4(b) is a surprising result, and it shows that the average energy cost is not monotonous with O/totalnum. This demonstrates the complex correlation between the overlap and the social selfish behavior. When the cooper- ative level is small, for example when p12= p21=0.1, the average energy cost is decreasing with O/totalnum. This is because that with the increasing of O/totalnum, the average delivery delay decreasing rapidly (see Figure 4(a)), data has less time to spread further. However, when nodes are more cooperative, the average energy cost is first increasing, and then begins to decrease with O/totalnum. In this case, though the average delivery delay still decreases with O/totalnum, the increasing degree of the data spreading speed is much bigger. Therefore, the energy cost in- creases in some degree, but the impact of the increasing of the data spreading speed becomes smaller when O/totalnum is big enough. In fact, the fluctuation of the average energy cost is very small under different value of O/totalnum. Therefore, if there are more nodes belonging to more community, the network can get better performance without much increasing of the energy cost. Now, we want to explore the results with different individual selfish level when the social Performance Analysis of Epidemic Routing in DTN with Overlapping Communities and Selfish Nodes 751 (a) Average delivery delay 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 22 22.5 23 23.5 24 24.5 25 Value of O/totalnum A ve ra g e e n e rg y co st p 1 =p 2 =0.2 p 1 =p 2 =0.5 p 1 =p 2 =0.8 p 1 =p 2 =1 (b) Average energy cost Figure 5: Impact of the overlap phenomena with different level of individual selfish selfish level is fixed. Here, we assume that nodes in one community helps the one in other community with probability 0.1. Other settings are the same as that in Figure 4. We give the numerical results when p12= p21=0.2, 0.5, 0.8 and 1, respectively. Let O/totalnum increase from 0.1 to 1, we can get Figure 5. The result also shows that the average delivery delay decreases with O/totalnum. The average energy cost has similar changing rule as that in Figure 4(b). This further demonstrates that the overlap is good for the network. 5 Conclusions This paper explored the performance of ER algorithm in DTN which has overlapping com- munities and selfish nodes, and a theoretical model based on the Markov process was proposed. Simulation results show the accuracy of the model. Numerical results show that the overlap between communities can improve the performance without much increasing of the energy cost. Bibliography [1] S. Haoliang, L. Lixiang and H. Xiaohui, A network coding based DTN convergence layer reliable transport mechanism over interplanetary networks, International Journal of Com- puters, Communications and Control, vol.6, no.2, pp.236-245, 2011. [2] A. Rahim, Z. S. Khan, F. B. Muhaya, M. Sher and M. K. Khan, Information sharing in ve- hicular adhoc network, International Journal of Computers, Communications and Control, Vol.5, No.5, pp.892-899, 2010. [3] W. Gao, Q. Li, B. Zhao and G. Cao, Multicasting in delay tolerant networks: a social network perspective, In Proc. ACM MobiHoc, 2009. [4] K. Fall, A delay-tolerant network architecture for challenged internets, In Proc. ACM SIG- COMM, 2003. [5] T. Spyropoulos, T. Turletti and K. Obrazcka, Routing in delay tolerant networks comprising heterogeneous populations of nodes, IEEE Transaction on Mobile Computing, vol. 6, no. 8, 2009. [6] T. Spyropoulos, K. Psounis and C. Raghavendra, Efficient routing in intermittently con- nected mobile networks: the single-copy case, ACM/IEEE Transaction on Networking, 2008. 752 Y. Wu, S. Deng, H. Huang, Y. Deng [7] Z. Guo, B. Wang and J. -H. Cui, Prediction assisted single-copy routing in underwater delay tolerant networks, In Proc. IEEE Globecom, 2010. [8] E. Bulut, Z. Wang and B. Szymanski, Cost effective multi-period spraying for routing in delay tolerant networks, ACM/IEEE Transaction on Networking, vol. 18, no. 5, 2010. [9] W. Gao, G. Cao, On exploiting transient contact patterns for data forwarding in delay tolerant networks, In Proc. IEEE ICNP, 2010. [10] G. Resta, P. Santi, The effects of node cooperation level on routing performance in delay tolerant networks, In Proc. IEEE SECON, 2009. [11] P. Hui, K. Xu, V. O. K. Li, J. Crowcort, V. Latora and P. Lio, Selfishness, altruism and message spreading in mobile social networks, In Proc. IEEE NetSciCom, 2009. [12] K.Xu, P. Hui, V. O. K. Li, J. Crowcort, V. Latora and P. Lio, Impact of altruism on opportunistic communications, In Proc. IEEE ICUFN, 2009. [13] R. Lu, X. Lin, H. Zhu, X. Shen and B. Preiss, Pi: a practical incentive protocol for delay tolerant networks, IEEE Transactions on Wireless Communications, vol.9, no.4, 2010. [14] T. Ning, Z. Yang, X. Xie and H. Wu, Incentive-aware data dissemination in delay-tolerant mobile networks, In Proc. IEEE SECON, 2011. [15] Q. Li, S. Zhu and G. Cao, Routing in socially selfish delay tolerant network, In Proc. IEEE INFOCOM, 2010. [16] Y. Li, P. Hui, D. Jin, L. Su and L. Zeng, Evaluating the impact of social selfishness on the epidemic routing in delay tolerant networks, IEEE Communication Letters, vol.14, no.11, pp.1026-1028, 2010. [17] Y. Li, G. Su, D. O. Wu, D. Jin, L. Su and L. Zeng, The impact of node selfishness on multicasting in delay tolerant networks, IEEE Transactions on Vehicular Technology,vol.60, no.5, 2011. [18] N. P. Nguyen, T. N. Dinh, S. Tokala, M. T. Thai, Overlapping communities in dynamic networks: their detection and mobile applications, In Proc. ACM Mobicom,2011. [19] A. Vahdat, D. Becker, Epidemic routing for partially-connected ad hoc networks, Technical Report, Duke University,2000. [20] X. Zhang, G. Neglia, J. Kurose and D. Towsley, Performance modeling of epidemic routing, Computer Networks,vol. 51, no. 10, pp. 2867-2891, 2007. [21] Y. K. Ip, W. -C. Lau and O. -C Yue, Performance modeling of epidemic routing with heterogeneous node types, In Proc. IEEE ICC,pp. 219-224, 2008. [22] A. AI-Hanbali, P. Nain and E. Altman, Performance of ad hoc networks with two-hop relay routing and limited packet lifetime, In Proc. Valuetools,2006. [23] A. Jindal, K. Psounis, Contention-aware performance analysis of mobility-assisted routing, IEEE Transaction on Mobile Computing,vol. 8, no. 2, pp. 145-161, 2009. [24] E. Altman, T. Basar and F. D. Pellegrini, Optimal monotone forwarding policies in delay tolerant mobile ad-hoc networks, In Proc. ACM Inter-Perf,2008. Performance Analysis of Epidemic Routing in DTN with Overlapping Communities and Selfish Nodes 753 [25] E. Altman, G. Neglia, F. D. Pellegrini and D. Miorandi, Decentralized stochastic control of delay tolerant networks, In Proc. IEEE INFOCOM,2009. [26] F. D. Pellegrini, E. Altman and T. Basar, Optimal monotone forwarding policies in delay tolerant mobile ad hoc networks with multiple classes of nodes, In Proc. WiOpt,2010. [27] C. Singh, A. Kumar, R. Sundaresan and E. Altman, Optimal forwarding in delay tolerant networks with multiple destinations, In Proc. WiOpt,2011. [28] Y. Li, Z. Wang, D. Jin, L. Su, L. Zeng and S. Chen, Optimal relaying in heterogeneous delay tolerant networks, In Proc. IEEE ICC,2011. [29] M. Khouzani, S. Sarkar and E. Altman, Optimal control of epidemic evolution, In Proc. IEEE INFOCOM,2011. [30] R. Groenevelt, P. Nain and G. Koole, The message delay in mobile ad hoc networks, Per- formance Evaluation,2005. [31] T. Karagiannis, J. -Y. L. Boudec and M. Zojnovic, Power law and exponential decay of inter contact times between mobile devices, In Proc. ACM Mobicom,2007. [32] A. Keranen, J. Ott, and T. Karkkainen, The ONE simulator for DTN protocol evaluation, In Proc. SIMUTOOLS,2009. [33] S. J. U. Traffic information grid team, Grid Computing Center, Shanghai Taxi Trace Data. http://wirelesslab.sjtu.edu.cn/ [34] H. Zhu, L. Fu, G. Xue, Y. Zhu, M. Li and L. Ni, Recognizing exponential inter-contact time in VANETs, In Proc. IEEE INFOCOM,2010.