Name
Abstract | ||
|---|---|---|
In social swarming applications, participants equipped with 3G and WiFi-capable smart phones are tasked to provide reports (possibly voluminous ones that include full-motion video) about their immediate environment to a central coordinator. In this paper, we consider the problem of timely delivery of these reports: each report has an associated deadline and the goal of the system is to retrieve as many reports as possible (or retrieve the most valuable reports), while satisfying each report's deadline. Reporters can use their cellular interface to upload their reports, but can also ask neighbors (using their faster WiFi interface) to help upload parts of their reports. Under an assumption that WiFi transmission delays are negligible, we first show that there exists a polynomial time optimal solution using an earliest-deadline-first (EDF) strategy for achieving the goals described above. In practice, WiFi delays are not negligible: in this case, it turns out that the scheduling problem is strongly NP-hard. We formulate two heuristic algorithms, and show, through simulations with real-world measurements, that these heuristics perform 2-4× better than without peer-assistance, and within 60% of an upper-bound on the optimal. |
Year | DOI | Venue |
|---|---|---|
2012 | 10.1109/DCOSS.2012.8 | DCOSS |
Keywords | Field | DocType |
scheduling,wifi transmission delay,3g smart phones,np-hard problem,upper-bound,cellular interface,wifi transmission delays,wifi-capable smart phone,upload part,delays,computational complexity,associated deadline,scheduling problem,3g mobile communication,wifi-capable smart phones,faster wifi interface,earliest-deadline-first strategy,edf strategy,valuable report,heuristic algorithms,timely report delivery,smart phones,wifi interface,social swarming applications,wireless lan,wifi delay,polynomial time optimal solution,polynomial time,np hard problem,polynomials,bandwidth,satisfiability,earliest deadline first,heuristic algorithm,schedules,upper bound | Heuristic,Job shop scheduling,Scheduling (computing),Computer science,Upload,Computer network,Heuristics,Schedule,Time complexity,Computational complexity theory,Distributed computing | Conference |
ISBN | Citations | PageRank |
978-1-4673-1693-4 | 1 | 0.35 |
References | Authors | |
14 | 6 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Bin Liu | 1 | 1281 | 68.98 |
| Peter Terlecky | 2 | 62 | 6.17 |
| Xing Xu | 3 | 1 | 0.35 |
| Amotz Bar-Noy | 4 | 2986 | 400.08 |
| ramesh govindan | 5 | 15430 | 2144.86 |
| Dror Rawitz | 6 | 494 | 44.18 |