Title :
Mobile Element Scheduling with Dynamic Deadlines
Author :
Somasundara, Arun A. ; Ramamoorthy, Aditya ; Srivastava, Mani B.
Author_Institution :
Broadcom Corp., San Jose, CA
fDate :
4/1/2007 12:00:00 AM
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 compared
Keywords :
computational complexity; integer programming; linear programming; mobile radio; scheduling; wireless sensor networks; NP-complete; buffer overflow; dynamic deadlines; integer-linear-programming formulation; mobile element scheduling; sensor nodes; spatio-temporal dynamics; wireless sensor networks; Base stations; Dynamic scheduling; Environmentally friendly manufacturing techniques; Industrial pollution; Job shop scheduling; Mobile computing; Processor scheduling; Relays; Sensor phenomena and characterization; Wireless sensor networks; Controlled mobility; scheduling; wireless sensor networks.;
Journal_Title :
Mobile Computing, IEEE Transactions on
DOI :
10.1109/TMC.2007.57