[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content

Advertisement

Springer Nature Link
Log in

Egocentric network focused community aware multicast routing for DTNs

  • Published:
Wireless Networks Aims and scope Submit manuscript

Abstract

Multicasting for delay-tolerant networks (DTNs) in sparse social network scenarios is a challenge due to the deficiency of end-to-end paths. In social network scenarios, the behaviors of their nodes are controlled by human beings, and node mobility is the same as that of humans. To design the multicasting algorithms for DTNs, therefore, it would be promising to capture the intrinsic characteristics of relationships among these nodes. In this paper, multicasting in DTNs is regarded as a message dissemination issue in social networks, and an egocentric network focused community aware multicast routing algorithm (ENCAR) is proposed. As distinct from some social-based routing algorithms which only focus on centrality analysis, ENCAR is an utility based and hierarchical routing algorithm, its utility function is constructed on the basis of centrality analysis and destination-oriented contact probability. We take notice of clustering phenomenon in social networks, and present the community aware forwarding schemes. In addition, to simulate the mobility of individuals in social networks, a novel community based random way point mobility model is also presented. In this paper, the performance of ENCAR is theoretically analyzed and further evaluated on simulator ONE. Simulation results show that ENCAR outperforms most of the existing multicast routing algorithms in routing overhead, on condition that delivery ratio is relatively high, with other significant parameters guaranteed to perform well.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9
Fig. 10

Similar content being viewed by others

References

  1. Musolesi, M., & Mascolo, C. (2009). CAR: Context-aware adaptive routing for delay-tolerant mobile networks. IEEE Transactions on Mobile Computing, 8(2), 246–260.

    Article  Google Scholar 

  2. Zhao, J., & Cao, G. (2008). VADD: Vehicle-assisted data delivery in vehicular ad hoc networks. IEEE Transactions on Vehicular Technology, 57(3), 1910–1922.

    Article  Google Scholar 

  3. Fall, K. (2008). DTN: An architectural retrospective. IEEE Journal on Selected Areas in Communications, 26(5), 828–836.

    Article  Google Scholar 

  4. Tovar, A., Friesen, T., Ferens, K., & McLeod, B. (2010). A DTN wireless sensor network for wildlife habitat monitoring. In Proceedings on IEEE CCECE ’10, pp. 1–5, May.

  5. Li, X., & Shu, W. (2008). DTN routing in vehicular sensor networks. In Proceedings of IEEE GlobeCom, pp. 1–5, November/December.

  6. Dunbabin, M., Corke, P., Vailescu, I., & Rus, D. (2006). Data muling over underwater wireless sensor networks using an autonomous underwater vehicle. In Proceedings of IEEE ICRA ’06, pp. 2091–2098, May.

  7. Caini, C., Cornice, P., Firrincieli, R., & Lacamera, D. (2008). A DTN approach to satellite communications. IEEE Journal on Selected Areas in Communications, 26(5), 820–827.

    Article  Google Scholar 

  8. Lu, Z., & Fan, J. (2010). Delay/disruption tolerant network and its application in military communications. In Proceedings of IEEE ICCDA ’10, pp. 231–234, June.

  9. Yong, L., Su, G., Wu, D., Jin, D., Su, L., & Zeng, L. (2011). The impact of node selfishness on multicasting in delay tolerant networks. IEEE Transactions on Vehicular Technology, 60(5), 2224–2238.

    Article  Google Scholar 

  10. Fan, J., Chen, J., Du, Y., Wang, P., & Sun, Y. (2011). DelQue: A socially aware delegation query scheme in delay-tolerant networks. IEEE Transactions on Vehicular Technology, 60(5), 2181–2193.

    Article  Google Scholar 

  11. Daly, E., & Haahr, M. (2009). Social network analysis for information flow in disconnected delay-tolerant MANETs. IEEE Transactions on Mobile Computing, 8(5), 606–621.

    Article  Google Scholar 

  12. Pan, H., Crowcroft, J., & Yoneki, E. (2011). BUBBLE rap: Social-based forwarding in delay-tolerant networks. IEEE Transactions on Mobile Computing, 10(11), 1576–1589.

    Article  Google Scholar 

  13. Gao, W., Li, Q. H., Zhao, B., & Cao, G. H. (2009). Multicasting in delay tolerant networks: A social network perspective. In Proceedings of ACM MobiHoc, pp. 299–308, May.

  14. Zhao, W., Ammar, M., & Zegura, E. (2005). Multicasting in delay tolerant networks: Semantic models and routing algorithms. In Proceedings of ACM SIGCOMM, pp. 268–275, August.

  15. Ye, Q., Cheng, L., Chuah, M., & Davison, B. (2009). Performance comparison of different multicast routing strategies in disruption tolerant networks. Computer Communications, 32(16), 1731–1741.

    Article  Google Scholar 

  16. Xi, Y., & Chuah, M. (2009). An encounter-based multicast scheme for disruption tolerant networks. Computer Communications, 32(16), 1742–1756.

    Article  Google Scholar 

  17. Le, T., Kalantarian, H., & Gerla, M. (June 2015). A two-level multicast routing strategy for delay tolerant networks. Proceedings of MED-HOC-NET.

  18. Galluccio, L., Lorenzo, B., & Glisic, S. (2015). Sociality-aided new adaptive infection recovery schemes for multicast DTNs. IEEE Transactions on Vehicular Technology. doi:10.1109/TVT.2015.2450202

  19. Gao, W., Li, Q., Zhao, B., & Cao, G. (2012). Social-aware multicast in disruption-tolerant networks. IEEE/ACM Transactions on Networking, 20(5), 1553–1566.

    Article  Google Scholar 

  20. Zhang, Y., & Zhao, J. (May 2009). Social-aware data diffusion in delay tolerant MANETs. Proceedings of MobiHoc.

  21. Xiao, M., Wu, J., & Huang, L. (2014). Community-aware opportunistic routing in mobile social networks. IEEE Transactions on Computers, 63(7), 1682–1695.

    Article  MathSciNet  MATH  Google Scholar 

  22. Zhu, Y., Xu, B., Shi, X., & Wang, Y. (2013). A survey of social-based routing in delay tolerant networks: Positive and negative social effects. IEEE Communications Surveys & Tutorials, 15(1), 387–401.

    Article  Google Scholar 

  23. Magaia, N., Francisco, A., Pereira, P., & Correia, M. (2015). Betweenness centrality in delay tolerant networks: A survey, ad hoc networks. doi:10.1016/j.adhoc.2015.05.002

  24. Freeman, L. (1978–1979). Centrality in social networks conceptual clarification. Social Networks, 1(3), 215–239.

  25. Marsden, P. (2002). Egocentric and sociocentric measures of network centrality. Social Networks, 24(24), 407–422.

    Article  Google Scholar 

  26. Everett, M., & Borgatti, S. (2005). Ego network betweenness. Social Networks, 27(1), 31–38.

    Article  Google Scholar 

  27. Cai, H., & Eun, D. (2009). Crossing over the bounded domain: From exponential to power-law intermeeting time in mobile ad hoc networks. IEEE Transactions on Networking, 17(5), 1578–1591.

    Article  Google Scholar 

  28. Zhu, H., Fu, L., Xue, G., Zhu, Y., Li, M., & Ni, L. (2011). Impact of traffic influxes: Revealing exponential intercontact time in urban VANETs. IEEE Transactions on Parallel and Distributed Systems, 22(8), 1258–1266.

    Article  Google Scholar 

  29. Conan, V., & Leguay, J. (2007). Characterizing pairwise inter-contact patterns in delay tolerant networks. In Proceedings of ICST.

  30. Gao, W., Cao, G., La Porta, T., & Han, J. (2013). On exploiting transient social contact patterns for data forwarding in delay-tolerant networks. IEEE Transactions on Mobile Computing, 12(1), 151–165.

    Article  Google Scholar 

  31. Batabyal, S., & Bhaumik, P. (2015). Mobility models, traces and impact of mobility on opportunistic routing algorithms: A survey. IEEE Communications Surveys & Tutorials, 17(3), 1679–1707.

    Article  Google Scholar 

  32. Schurgot, M., & Comaniciu, C. (2012). Beyond traditional DTN routing: Social networks for opportunistic communication. IEEE Communications Magazine, 50(7), 155–162.

    Article  Google Scholar 

  33. Chuah, M. (2009). Social network aided multicast delivery scheme for human contact-based networks. In Proceedings of SIMPLEX, July.

  34. Wu, J., & Wang, Y. (2010). A non-replication multicasting scheme in delay tolerant networks. In Proceedings of IEEE MASS, pp. 89–98, November.

  35. Wang, Y., Li, X., & Wu, J. (2010). Multicasting in delay tolerant networks: Delegation forwarding. In Proceedings of IEEE GLOBECOM.

  36. Keränen, A., Ott, J., & Kärkkäinen, T. (2009). The ONE simulator for DTN protocol evaluation. In Proceedings of SIMUTools.

  37. Augustin, C., Pan, H., Jon, C., Christophe, D., & Richard, G. (2007). Impact of human mobility on opportunistic forwarding algorithms. IEEE Transactions on Mobile Computing, 6(6), 606–620.

    Article  Google Scholar 

  38. Yang, S., Yang, X., Zhang, C., & Spyrou, E. (2010). Using social network theory for modeling human mobility. IEEE Journal on Network, 24(5), 6–13.

    Article  Google Scholar 

  39. Abdulla, M., & Simon, R. (2007). Characteristics of common mobility models for opportunistic networks. In Proceedings of PM2HW2N, pp. 105–109, October.

  40. Vahdat, A., & Becker, D. (2000). Epidemic routing for partially-connected ad hoc networks. Technical report, Duke University, Durham, NC, CS-200006, April.

Download references

Acknowledgements

This work is supported by National Natural Science Foundation of China under Grant 91538203.

Author information

Authors and Affiliations

  1. School of Electronic Information and Communications, Huazhong University of Science and Technology, Wuhan, 430074, China

    Guoxing Jiang, Yanqing Shen, Jun Chen, Yan Dong, Fang Lu & Qi Jiang

Authors
  1. Guoxing Jiang
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Yanqing Shen
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Jun Chen
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Yan Dong
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Fang Lu
    View author publications

    You can also search for this author in PubMed Google Scholar

  6. Qi Jiang
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Guoxing Jiang.

Appendix

Appendix

Theorem 1

For the proposed mobility model CB_RWP, the encounter process between a pair of nodes is Possion process, and the inter-contact time follows exponential distribution.

Proof

A continuous-time counting process \(\{N(t), t>0\}\) can be classified into Possion process if it possesses the following properties:

  1. 1.

    \(N(0)=0\);

  2. 2.

    The numbers of occurrences counted in disjoint intervals are independent from each other;

  3. 3.

    The probability distribution for the number of occurrences counted in any interval only depends on the length of the interval and follows Possion distribution.

In DTNs, an occurrence represents the contact between a pair of nodes. If \(t=0\), any two nodes do not contact with each other, of course, \(N(0)=0\). In CB_RWP, the speed of each node is randomly chosen between [3 m/s, 10 m/s], the moving direction of each node is randomly chosen between \([0,2\pi ]\), and the next waypoint is also randomly chosen within the simulation area. Apparently, every node stays in or departs from its community independently. Thus, the motions of nodes will not influence each other. As we know, the contacts of node pairs only occur when two nodes encounter each other. With any pair of nodes, the numbers of contacts in disjoint intervals are independent. Hence, the encounter process N(t) surely has the properties (1) and (2).

To prove the third property, we make the following notations firstly:

  1. 1.

    Let \(v_{i}\) and \(v_{j}\) be a pair of nodes in CB_RWP, and \(\lambda _{i,j}\) denote the contact ratio between them. \(\lambda _{i,j}\) represents the number of contacts in a unit interval and can be estimated as \(\lambda = \frac{n}{\sum \nolimits _{i=1}^{n}T_{i}}\), where \(T_{1}, T_{2}, \ldots , T_{n}\) are inter-contact time samples;

  2. 2.

    Let \(\triangle t\) be the unit interval. \(\triangle t\) represents a small duration, and a period of time T can be divided into \(n=\frac{T}{\triangle t}\) units;

  3. 3.

    Let \(P_{0}\) be the probability that \(v_{i}\) encounters \(v_{j}\) only once during \(\triangle t\).

The number of contacts during T is denoted as X. Obviously, X follows the Bernoulli distribution. The probability that \(v_{i}\) encounters \(v_{j}\) for k times during T can be formulated as:

$$\begin{aligned} P(X=k)= C^k_n\times {P_0}^k\times (1-P_0)^{n-k} \end{aligned}$$
(13)
$$\begin{aligned} E(X)= n\times P_0 \end{aligned}$$
(14)

The average number of encounters in T can also be represented as \(\lambda _{i,j}\cdot T\), and we have \(\lambda _{i,j}\cdot T=n\cdot P_0\), \(P_0=\frac{\lambda _{i,j}\cdot T}{n}\). Thus, Eq. (13) can be transformed into:

$$\begin{aligned} \begin{aligned}&P\{[N(t+T)-N(t)]=k\}\\&=\frac{n\cdot (n-1)\cdots (n-k+1)}{k!}\times \left( \frac{\lambda _{i,j}\cdot T}{n}\right) ^k\times \left( 1-\frac{\lambda _{i,j}\cdot T}{n}\right) ^{n-k}\\&=\frac{n\cdot (n-1)\cdots (n-k+1)}{n^k}\times \frac{(\lambda _{i,j}\cdot T)^k}{k!}\times \left( 1-\frac{\lambda _{i,j}\cdot T}{n}\right) ^{n-k} \end{aligned} \end{aligned}$$
(15)

When \(\triangle t \rightarrow 0\), \(n\rightarrow \infty\)

$$\begin{aligned}&\lim _{n\rightarrow \infty }\frac{n\cdot (n-1)\cdot \cdot \cdot (n-k+1)}{n^k}=1 \end{aligned}$$
(16)
$$\begin{aligned}&\lim _{n\rightarrow \infty }\left( 1-\frac{\lambda _{i,j}\cdot T}{n}\right) ^{n-k}=e^{\lim \limits _{n\rightarrow \infty }\ln \left( 1-\frac{\lambda _{i,j}\cdot T}{n}\right) ^{n-k}}\nonumber \\&=e^{\lim \limits _{n\rightarrow \infty } \left( (n-k)\cdot \left( -\frac{\lambda _{i,j}\cdot T}{n}\right) \right) }\nonumber \\&=e^{-\lambda _{i,j}\cdot T} \end{aligned}$$
(17)

Finally,

$$\begin{aligned} \begin{aligned}&P\{[N(t+T)-N(t)]=k\}=\frac{(\lambda _{i,j}\cdot T)^k\times e^{-\lambda _{i,j}\cdot T}}{k!} \end{aligned} \end{aligned}$$
(18)

Consequently, in CB_RWP, the probability distribution for the number of contacts counted in any time interval only depends on the length of the interval and follows Possion distribution. Thus, the third property is proven.

To sum up, it can be asserted that the encounter process \(\{N(t), t>0\}\) in CB_RWP is Possion process. From Eq. (18), the probability that \(v_{i}\) does not encounter \(v_{j}\) during T is

$$\begin{aligned} P\{[N(t+T)-N(t)]=0\}=e^{-\lambda _{i,j}\cdot T} \end{aligned}$$
(19)

As a result, we can derive that the probability that \(v_{i}\) encounters \(v_{j}\) during T is

$$\begin{aligned} F(T)=1 - e^{-\lambda _{i,j}\cdot T} \end{aligned}$$
(20)

Therefore, the inter-contact time between a pair of nodes follows exponential distribution, and Theorem 1 is proven. \(\square\)

Table 4 Acceptance ratio of \(\chi ^{2}\) tests
Full size table

To validate our theoretical proof, we do a lot of \(\chi ^{2}\) hypothesis tests. Each \(\chi ^{2}\) test is done on tens of thousands inter-contact time samples, which are derived from CB_RWP during simulation. The results of the acceptance ratio of \(\chi ^{2}\) hypothesis tests are listed in Table 4, in which \(P_{s}\) is the staying probability, n is the number of nodes and \(\alpha\) is the significance level.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Jiang, G., Shen, Y., Chen, J. et al. Egocentric network focused community aware multicast routing for DTNs. Wireless Netw 24, 1217–1235 (2018). https://doi.org/10.1007/s11276-016-1393-x

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11276-016-1393-x

Keywords

Search

Navigation