Technical reports

People are the network: experimental design and evaluation of social-based forwarding algorithms

Pan Hui

March 2008, 160 pages

This technical report is based on a dissertation submitted July 2007 by the author for the degree of Doctor of Philosophy to the University of Cambridge, Churchill College.

DOI: 10.48456/tr-713

Abstract

Cooperation binds but also divides human society into communities. Members of the same community interact with each other preferentially. There is structure in human society. Within society and its communities, individuals have varying popularity. Some people are more popular and interact with more people than others; we may call them hubs. I develop methods to extract this kind of social information from experimental traces and use it to choose the next hop forwarders in Pocket Switched Networks (PSNs). I find that by incorporating social information, forwarding efficiency can be significantly improved. For practical reasons, I also develop distributed algorithms for inferring communities.

Forwarding in Delay Tolerant Networks (DTNs), or more particularly PSNs, is a challenging problem since human mobility is usually difficult to predict. In this thesis, I aim to tackle this problem using an experimental approach by studying real human mobility. I perform six mobility experiments in different environments. The resultant experimental datasets are valuable for the research community. By analysing the experimental data, I find out that the inter-contact time of humans follows a power-law distribution with coefficient smaller than 1 (over the range of 10 minutes to 1 day). I study the limits of “oblivious” forwarding in the experimental environment and also the impact of the power-law coefficient on message delivery.

In order to study social-based forwarding, I develop methods to infer human communities from the data and use these in the study of social-aware forwarding. I propose several social-aware forwarding schemes and evaluate them on different datasets. I find out that by combining community and centrality information, forwarding efficiency can be significantly improved, and I call this scheme BUBBLE forwarding with the analogy that each community is a BUBBLE with big bubbles containing smaller bubbles. For practical deployment of these algorithms, I propose distributed community detection schemes, and also propose methods to approximate node centrality in the system.

Besides the forwarding study, I also propose a layerless data-centric architecture for the PSN scenario to address the problem with the status quo in communication (e.g. an infrastructuredependent and synchronous API), which brings PSN one step closer to real-world deployment.

Full text

PDF (4.6 MB)

BibTeX record

@TechReport{UCAM-CL-TR-713,
  author =	 {Hui, Pan},
  title = 	 {{People are the network: experimental design and evaluation
         	   of social-based forwarding algorithms}},
  year = 	 2008,
  month = 	 mar,
  url = 	 {https://www.cl.cam.ac.uk/techreports/UCAM-CL-TR-713.pdf},
  institution =  {University of Cambridge, Computer Laboratory},
  doi = 	 {10.48456/tr-713},
  number = 	 {UCAM-CL-TR-713}
}