טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
M.Sc Thesis
M.Sc StudentMhameed Aezalden
SubjectLocally vs. Globally Optimized Flow-Based Content
Distribution to Mobile Nodes
DepartmentDepartment of Computer Science
Supervisors Professor Dan Raz
Professor Reuven Cohen
Full Thesis textFull thesis text - English Version


Abstract

The research deals with efficient distribution of timely information to flows of mobile devices. We consider the case where a set of Information Dissemination Devices (IDDs) broadcast a limited amount of information to passing mobile nodes that are moving along well-defined paths. This is the case, for example, in intelligent transportation systems. We develop a novel model that captures the main aspects of the problem, and define a new optimization problem we call MBMAP (Maximum Benefit Message Assignment Problem). We distinguish between two variants of the problem: L-MBMAP, for the case where the assignment is made for each IDD separately, and G-MBMAP, for the case where the assignment is made for all the IDDs. We study the computational complexity of these global and local cases, and provide new approximation algorithms. In addition, we present a simulation study of the performance and the effectiveness of the various models in real life scenarios. We also discuss several schemes for identifying and determining the most important flows and we compare between these schemes using simulations.