Title :
Who, when, where: Timeslot assignment to mobile clients
Author :
Chen, Fangfei ; Johnson, Matthew P. ; Alayev, Yosef ; Bar-Noy, Amotz ; La Porta, Thomas
Author_Institution :
Dept. of Comput. Sci. & Eng., Pennsylvania State Univ., State College, PA, USA
Abstract :
We consider variations of a problem in which data must be delivered to mobile clients en-route, as they travel towards their destinations. The data can only be delivered to the mobile clients as they pass within range of wireless base stations. Example scenarios include the delivery of building maps to firefighters responding to multiple alarms, and the in-transit ldquoilluminationrdquo of simultaneous surface-to-air missiles. We cast this scenario as a parallel-machine scheduling problem with the little-studied property that jobs may have different release times and deadlines when assigned to different machines. We present new algorithms and also adapt existing algorithms, for both online and offline settings. We evaluate these algorithms on a variety of problem instance types, using both synthetic and real-world data, including several geographical scenarios, and show that our algorithms produce schedules achieving near-optimal throughput.
Keywords :
mobile radio; telecommunication network routing; en-route; geographical scenario; job deadline; job release time; mobile client; near-optimal throughput; parallel-machine scheduling problem; timeslot assignment; wireless base station; Bandwidth; Base stations; Computer science; Data engineering; Lighting; Missiles; Mobile communication; Mobile computing; Scheduling algorithm; Throughput;
Conference_Titel :
Mobile Adhoc and Sensor Systems, 2009. MASS '09. IEEE 6th International Conference on
Conference_Location :
Macau
Print_ISBN :
978-1-4244-5113-5
DOI :
10.1109/MOBHOC.2009.5337050