Digital Repository at the University of Maryland (DRUM)  >
Theses and Dissertations from UMD  >
UMD Theses and Dissertations 

Please use this identifier to cite or link to this item:

Authors: Han, Bo
Advisors: Srinivasan, Aravind
Bhattacharjee, Bobby
Department/Program: Computer Science
Type: Dissertation
Sponsors: Digital Repository at the University of Maryland
University of Maryland (College Park, Md.)
Subjects: Computer science
Keywords: centrality
hybrid delivery
mobile content delivery
random walks
Issue Date: 2012
Abstract: Hybrid mobile content delivery systems improve performance of wide-area networks by combining both wide-area and local-area communications. In hybrid content delivery, service providers send data packets first to a small number of selected users (e.g., those with good channel quality) and then these mobile users help forward the packets to others (e.g., those with poor channel quality). The central theme of our work is to identify the initial target set composed of influential mobile users (i.e., individuals with high centrality in their social-contact graphs) and thus improve the efficiency of hybrid mobile content distribution. We first present two centralized algorithms for this target-set selection problem. The greedy algorithm has a provable performance guarantee, due to the submodularity of the underlying information dissemination function. The heuristic algorithm exploits the regularity of human mobility and is more practical than the greedy algorithm. We then propose a lightweight and distributed protocol to identify these influential users through random-walk sampling. This distributed protocol leverages random-walk probe messages to sample mobile users and estimates their centrality based on how many times they are visited by the probe messages. This protocol has low communication and computation overhead and lends itself well to mobile content delivery. We verify the effectiveness of these approaches through extensive trace-driven simulation studies using real-world mobility traces.
Appears in Collections:Computer Science Theses and Dissertations
UMD Theses and Dissertations

Files in This Item:

File Description SizeFormatNo. of Downloads
Han_umd_0117E_13525.pdf2.27 MBAdobe PDF338View/Open

All items in DRUM are protected by copyright, with all rights reserved.


DRUM is brought to you by the University of Maryland Libraries
University of Maryland, College Park, MD 20742-7011 (301)314-1328.
Please send us your comments