Periodic Mobile Multi-Gateway Scheduling

Published 1 January 2008

Khaled Almi’ani, S. Selvakennedy, Anastasios Viglas

DOI10.1109/pdcat.2008.36

Citations13

TL;DR

The problem of scheduling the mobile gatewayspsila path so that the sensorspila visiting frequencies are satisfactory, and the sensorspsila data is uploaded to the sink at least at the frequency they are generated is presented and it is proved that the problem is NP-Hard.

Abstract

Recently, using mobile gateway(s) as a mechanical data carries emerges as a promising approach to prolong sensor network lifetime and relaying information in partitioned network. These mobile gateways, which move in pre-determined paths, visit the sensors to upload their data. As the sensors data generation rate for different sensors may vary based on their locations, sensors need to be visited at different frequencies. In this paper, we present the problem of scheduling the mobile gateways’ path so that the sensors’ visiting frequencies are satisfactory, and the sensors’ data is uploaded to the sink at least at the frequency they are generated. We also prove that the problem is NP-Hard. In addition to integer linear programming formulation, a practical heuristic is also proposed and its performance is compared against the optimal results

Keywords

Computer Science

Journal of the Operational Research SocietyIntroduction to Algorithms

16,942 Citations1991V. J. Rayward‐Smith, Thomas H. Cormen +2 more

Operations ResearchAlgorithms for the Vehicle Routing and Scheduling Problems with Time Window Constraints

4,181 Citations1987Marius M. Solomon

This paper considers the design and analysis of algorithms for vehicle routing and scheduling problems with time window constraints and finds that several heuristics performed well in different problem environments; in particular an insertion-type heuristic consistently gave very good results.

Society for Industrial and Applied Mathematics eBooksThe Vehicle Routing Problem

4,000 Citations2002Paolo Toth, Daniele Vigo

Journal of the ACMInteger Programming Formulation of Traveling Salesman Problems

1,994 Citations1960Casey Miller, A. W. Tucker +1 more

The present paper provides yet another example of the versatility of integer programming as a mathematical modeling device by representing a generalization of the well-known “Travelling Salesman Problem” in integer programming terms.

View PDF

Energy-efficient computing for wildlife tracking

1,803 Citations2002Philo Juang, Hidekazu Oki +4 more

The goal is to use the least energy, storage, and other resources necessary to maintain a reliable system with a very high `data homing' success rate and it is believed that the domain-centric protocols and energy tradeoffs presented here for ZebraNet will have general applicability in other wireless and sensor applications.

Data MULEs: modeling a three-tier architecture for sparse sensor networks

1,324 Citations2003Rahul Shah, Sumit Roy +2 more

This paper presents and analyzes an architecture to collect sensor data in sparse sensor networks that exploits the presence of mobile entities present in the environment and incorporates key system variables such as number of MULEs, sensors and access points.

Discrete Applied MathematicsModels, relaxations and exact approaches for the capacitated vehicle routing problem

971 Citations2002Paolo Toth, Daniele Vigo

This paper reviews the exact algorithms based on the branch and bound approach proposed in the last years for the solution of the basic version of the vehicle routing problem (VRP), where only the vehicle capacity constraints are considered, and concludes by examining possible future directions of research in this field.

Message ferrying: Proactive routing in highly-partitioned wireless ad hoc networks

359 Citations2004Wenrui Zhao, Mostafa Ammar

The basic design of the Message Ferrying or MF scheme is proposed and a general framework to classify variations of MF systems is developed and studied to study ferry route design problem in stationary node case which is shown to be NP-hard and provide an efficient algorithm to compute ferry route.

Intelligent fluid infrastructure for embedded networks

355 Citations2004Aman Kansal, Arun Somasundara +3 more

This work exploits mobility to develop a fluid infrastructure: mobile components are deliberately built into the system infrastructure for enabling specific functionality that is very hard to achieve using other methods.

View PDF

IEEE Transactions on Mobile ComputingMobile Element Scheduling with Dynamic Deadlines

263 Citations2007Arun Somasundara, Aditya Ramamoorthy +1 more

This work formulates the problem of scheduling the mobile element in the network so that there is no data loss due to buffer overflow and the problem is shown to be NP-complete and an integer-linear-programming formulation is given.