Characterizing and leveraging people movement for content distribution in mobile Peer-to-Peer networks

Vu, Long H.

Permalink

https://hdl.handle.net/2142/18347 Copy

Description

Title

Characterizing and leveraging people movement for content distribution in mobile Peer-to-Peer networks

Author(s)

Vu, Long H.

Issue Date

2011-01-14T22:47:04Z

Director of Research (if dissertation) or Advisor (if thesis)

Nahrstedt, Klara

Doctoral Committee Chair(s)

Nahrstedt, Klara

Committee Member(s)

• Gupta, Indranil
• Campbell, Roy H.
• Campbell, Andrew
• Vaidya, Nitin H.

Department of Study

Computer Science

Discipline

Computer Science

Degree Granting Institution

University of Illinois at Urbana-Champaign

Degree Name

Ph.D.

Degree Level

Dissertation

Keyword(s)

• Content Distribution
• Mobile Peer-to-Peer Networks
• Movement behavior
• Schelling model
• Bluetooth trace
• Wifi trace

Abstract

In this thesis, we present a framework to characterize and leverage people movement for improvements of content distribution in mobile Peer-to-Peer (P2P) networks. Particularly, we study two typical classes of people movement including the Schelling behavior and repetitive behavior. The Schelling behavior exists in real-world scenarios where co-located people collaboratively share mutual content interest when they are moving towards the same Point of Interest such as shopping mall, football stadium, and outdoor concert. Meanwhile, the repetitive behavior of people movement can be found in numerous places where people visit regular locations and make regular social contacts for their daily routines such as university campuses and work places. For the first part of the thesis, we start by analyzing the original segregation model proposed by Thomas Schelling, a Nobel prize winner in economics. We find that the properties of the segregation model exist in numerous real-world scenarios, in which the co-located people may form groups and collaboratively share data messages using their wireless devices when they are moving towards the same Point of Interest. This grouping behavior of people (or their mobile devices) is called the “Schelling behavior” of people movement. We find that when mobile nodes exhibit Schelling behavior, the network formed by these nodes has two important properties: (1) co-located mobile nodes form “moving” coalitions, and (2) the coalition size increases at the closer distance from Point of Interest. We then conduct a validation study on these properties by: (1) simulating people movement on real Google maps, and (2) modeling people movement in different street configurations by using the Mobius modeling tool. Our validation study confirms the two properties of the Schelling behavior of people movement. Then, we exploit these properties to design three protocols to improve content distribution in mobile P2P networks, including COADA, iShare, and DENTA. We evaluate our protocols via simulation and the evaluation results show that our protocols outperform other existing content distribution schemes significantly by improving message delivery and reducing message overhead. For the second part of the thesis, we exploit the repetitive behavior of people movement for the design of content distribution protocols. Particularly, we propose a new methodology to collect people movement trace using mobile phones. We then apply this method to implement a trace collection system named UIM, which collects MAC addresses of Wifi access points and Bluetooth-enabled devices in the proximity of the experiment phones. The UIM system is deployed on Google Android phones carried by 123 faculties, staff, and students in University of Illinois campus from March 2010 to August 2010. The collected MAC addresses of Wifi access points are used to infer location information and the collected Bluetooth MACs are used to infer social contact. To the best of our knowledge, the UIM system is the first system to collect both location information and social contact of people movement. The inferred location information and social contact then are used in the characterization study, which shows that people movement exhibits a high degree of repetition. We then propose a novel method named Jyotish to construct a predictive model of people movement from the joint Wifi/Bluetooth trace to predict future information of location, stay duration at the location, and social contact. Applying the Jyotish method, we construct a predictive model from the joint Wifi/Bluetooth trace collected by the UIM scanning system. To the best of our knowledge, Jyotish is the first method to construct the predictive model of people movement from the joint Wifi/Bluetooth trace and our constructed predictive model is the first to provide altogether predictions for location, stay duration, and social contact. Finally, we leverage the constructed predictive model to design a new content distribution protocol named COMFA, which exploits the regularity of social contact found in the Bluetooth trace collected by the UIM system to maximize the message delivery probability and preserve message delivery deadline. We compare the performance of COMFA with Prophet routing and Epidemic routing over the collected Bluetooth trace and the evaluation results show that COMFA outperforms other alternatives by reducing the message delivery delay and message overhead considerably.

Graduation Semester

2010-12

Permalink

http://hdl.handle.net/2142/18347

Copyright and License Information

Copyright 2010 Long H. Vu

Owning Collections