On Exploiting Temporal, Social, and Geographical Relationships for Data Forwarding in Delay Tolerant Networks

Zhijie Li, Ming Li, Longxiang Gao

School of Information Technology, Deakin University, Melbourne, Australia.

DOI: 10.4236/jsea.2014.72009                

Abstract

Because of unpredictable node mobility and absence of global information in Delay Tolerant Networks (DTNs), effective data forwarding has become a significant challenge in such network. Currently, most of existing data forwarding mechanisms select nodes with high cumulative contact capability as forwarders. However, for the heterogeneity of the transient node contact patterns, these selection approaches may not be the best relay choices within a short time period. This paper proposes an appropriate data forwarding mechanism, which combines time, location, and social characteristics into one coordinate system, to improve the performance of data forwarding in DTNs. The Temporal-Social Relationship and the Temporal-Geographical Relationship reveal the implied connection information among these three factors. This mechanism is formulated and verified in the experimental studies of realistic DTN traces. The empirical results show that our proposed mechanism can achieve better performance compared to the existing schemes with similar forwarding costs (e.g. end-to-end delay and delivery success ratio).

Keywords

Delay Tolerant Networks; Temporal-Social Relationship; Temporal-Geographical Relationship

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	W. Gao, G. Cao, T. L. Porta and J. Han, “On Exploiting Transient Social Contact Patterns for Data Forwarding in Delay Tolerant Networks,” IEEE Transactions on Mobile Computing, Vol. 12, No. 1, 2013, pp. 151-165. http://dx.doi.org/10.1109/TMC.2011.249
[2]	N. Perra, B. Goncalves, R. Pastor-Satorras and A. Vespignani, “Activity Driven Modeling of Time Varying Net-Works,” Scientific Reports, Vol. 2, 2012.
[3]	A. Baronchelli, S. Liu and N. Perra, “Contagion Dynamics in Time-Varying Metapopulation Networks,” Bulletin of the American Physical Society, Vol. 58, No. 1, 2013.
[4]	M. Newman, “Networks: An Introduction,” Oxford University Press, Oxford, 2009.
[5]	S.-Y. Chan, P. Hui and K. Xu, “Community Detection of Time-Varying Mobile Social Networks,” Complex Sciences, Springer, 2009, pp. 1154-1159.
[6]	P. Costa, C. Mascolo, M. Musolesi and G. P. Picco, “Socially-Aware Routing for Publish-Subscribe in DelayTolerant Mobile ad hoc Networks,” IEEE Journal on Selected Areas in Communications, Vol. 26, No. 5, 2008, pp. 748-760. http://dx.doi.org/10.1109/JSAC.2008.080602
[7]	Q. Yuan, I. Cardei and J. Wu, “Predict and Relay: An Efficient Routing in Disruption-Tolerant Networks,” Proceedings of the 10th ACM International Symposium on Mobile ad hoc Networking and Computing, ACM, 2009, pp. 95-104.
[8]	P. Hui, J. Crowcroft and E. Yoneki, “Bubble Rap: SocialBased Forwarding in Delay-Tolerant Networks,” IEEE Transactions on Mobile Computing, Vol. 10, No. 11, 2011, pp. 1576-1589. http://dx.doi.org/10. 1109/TMC.2010.246
[9]	A. Vahdat, D. Becker, et al., “Epidemic Routing for Partially Connected ad hoc Networks,” Technical Report CS-200006, Duke University, 2000.
[10]	A. Lindgren, A. Doria and O. Schelen, “Probabilistic Routing in Intermittently Connected Networks,” Service Assurance with Partial and Intermittent Resources, Springer, 2004, pp. 239-254. http://dx.doi.org/10.1007/978-3-540-27767-5_24
[11]	M. Musolesi and C. Mascolo, “Car: Context-Aware Adaptive Routing for Delay-Tolerant Mobile Networks,” IEEE Transactions on Mobile Computing, Vol. 8, No. 2, 2009, pp. 246-260. http://dx.doi.org/10.1109/TMC.2008.107
[12]	C. Boldrini, M. Conti, J. Jacopini and A. Passarella, “Hibop: A History Based Routing Protocol for Opportunistic Networks,” IEEE International Symposium on a World of Wireless, Mobile and Multimedia Networks (WoW-MoM 2007), Espoo, 18-21 June 2007, pp. 1-12.
[13]	P. Flocchini, B. Mans and N. Santoro, “On the Exploration of Time-Varying Networks,” Theoretical Computer Science, Vol. 469, 2013, pp. 53-68. http://dx.doi.org/10.1016/j.tcs.2012.10.029
[14]	L. A. Adamic, R. M. Lukose, A. R. Puniyani and B. A. Huberman, “Search in Power-Law Networks,” Physical Review E, Vol. 64, No. 4, 2001, Article ID: 046135.
[15]	S. Jain, K. Fall and R. Patra, “Routing in a Delay Tolerant Network,” Proceedings of the 2004 Conference on Applications, Technologies, Architectures and Protocols for Computer Communications, Vol. 34, No. 4, 2004, pp. 145-158. http://dx.doi.org/10.1145/1030194.1015484
[16]	Z. Wu, H. Song, S. Jiang and X. Xu, “A Grid-Based Stable Routing Algorithm in Mobile ad hoc Networks,” 1st Asia International Conference on Modelling & Simulation (AMS’07), Phuket, 27-30 March 2007, pp. 181-186.
[17]	L. Pelusi, A. Passarella and M. Conti, “Opportunistic Networking: Data Forwarding in Disconnected Mobile ad hoc Networks,” IEEE Communications Magazine, Vol. 44, No. 11, 2006, pp. 134-141. http://dx.doi.org/10.1109/MCOM.2006.248176
[18]	C. Liu and J. Wu, “Scalable Routing in Delay Tolerant Networks,” Proceedings of the 8th ACM International Symposium on Mobile ad hoc Networking and Computing, ACM, 2007, pp. 51-60.
[19]	A. Casteigts, P. Flocchini, W. Quattrociocchi and N. Santoro, “Time-Varying Graphs and Dynamic Networks,” in Ad-hoc, Mobile and Wireless Networks, Springer, 2011, pp. 346-359.
[20]	N. Perra, A. Baronchelli, D. Mocanu, B. Goncalves, R. Pastor-Satorras and A. Vespignani, “Random Walks and Search in Time-Varying Networks,” Physical Review Letters, Vol. 109, No. 23, 2012, Article ID: 238701. http://dx.doi.org/10.1103/PhysRevLett.109.238701
[21]	J. Tang, M. Musolesi, C. Mascolo and V. Latora, “Temporal Distance Metrics for Social Network Analysis,” Proceedings of the 2nd ACM Workshop on Online Social Networks, ACM, 2009, pp. 31-36.
[22]	M. C. Gonzalez, C. A. Hidalgo and A.-L. Barabasi, “Understanding Individual Human Mobility Patterns,” Nature, Vol. 453, No. 7196, 2008, pp. 779-782. http://dx.doi.org/10.1038/nature06958
[23]	N. Eagle and A. Pentland, “Reality Mining: Sensing Complex Social Systems,” Personal and Ubiquitous Computing, Vol. 10, No. 4, 2006, pp. 255-268. http://dx.doi.org/10.1007/s00779-005-0046-3
[24]	Y.-C. Cheng, J. Bellardo, P. Benk¨o, A. C. Snoeren, G. M. Voelker and S. Savage, “Jigsaw: Solving the Puzzle of Enterprise 802.11 Analysis,” ACM, Vol. 36, No. 4, 2006.
[25]	Y.-C. Cheng, M. Afanasyev, P. Verkaik, P. Benk¨o, J. Chiang, A. C. Snoeren, S. Savage and G. M. Voelker, “Automating Cross-Layer Diagnosis of Enterprise Wireless Networks,” ACM, Vol. 37, No. 4, 2007.
[26]	J. Leguay, T. Friedman and V. Conan, “Mobyspace: Mobility Pattern Space Routing for DTNS,” ACM SIGCOMM, 2005.
[27]	R.-J. Lange, “Potential Theory, Path Integrals and the Laplacian of the Indicator,” Journal of High Energy Physics, Vol. 2012, No. 11, 2012, pp. 1-46. http://dx.doi.org/10.1007/JHEP11(2012)032
[28]	M. Ficek and L. Kencl, “Spatial Extension of the Reality Mining Dataset,” IEEE 7th International Conference on Mobile Adhoc and Sensor Systems (MASS), San Francisco, 8-12 November 2010, pp. 666-673.