Mobile Element Scheduling with Dynamic Deadlines
Top Cited Papers
- 26 February 2007
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Mobile Computing
- Vol. 6 (4) , 395-410
- https://doi.org/10.1109/tmc.2007.57
Abstract
Wireless networks have historically considered support for mobile elements's an extra overhead. However, recent research has provided the means by which a network can take advantage of mobile elements. Particularly in the case of wireless sensor networks, mobile elements can be deliberately built into the system to improve the lifetime of the network and act as mechanical carriers of data. The mobile element, whose mobility is controlled, visits the nodes to collect their data before their buffers are full. In general, the spatio-temporal dynamics of the sensed phenomenon may require sensor nodes to collect samples at different rates, in which case, some nodes need to be visited more frequently than others. This work formulates the problem of scheduling the mobile element in the network so that there is no data loss due to buffer overflow. The problem is shown to be NP-complete and an integer-linear-programming formulation is given. Finally, some computationally practical algorithms for a single mobile and for the case of multiple mobiles are presented and their performances comparedKeywords
This publication has 25 references indexed in Scilit:
- CyclopsPublished by Association for Computing Machinery (ACM) ,2005
- Approximation algorithms for deadline-TSP and vehicle routing with time-windowsPublished by Association for Computing Machinery (ACM) ,2004
- Using Predictable Observer Mobility for Power Efficient Design of Sensor NetworksPublished by Springer Nature ,2003
- A Collaborative Approach to In-Place Sensor CalibrationPublished by Springer Nature ,2003
- Wireless sensor networks for habitat monitoringPublished by Association for Computing Machinery (ACM) ,2002
- Parallel Tabu Search for Real-Time Vehicle Routing and DispatchingTransportation Science, 1999
- Dynamic vehicle routing: Status and prospectsAnnals of Operations Research, 1995
- Algorithms for the Vehicle Routing and Scheduling Problems with Time Window ConstraintsOperations Research, 1987
- Local search in routing problems with time windowsAnnals of Operations Research, 1985
- Scheduling Algorithms for Multiprogramming in a Hard-Real-Time EnvironmentJournal of the ACM, 1973