Cost-minimizing mobile access point deployment in workflow-based mobile sensor networks

Haiming Jin, He Huang, Lu Su, Klara Nahrstedt

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

In mission-based mobile environments such as airplane maintenance, workflow-based mobile sensor networks emerge, where mobile users (MUs) with sensing devices visit sequences of mission-driven locations defined by workflows, and demand the gathering of sensory data within mission durations. To satisfy this demand in a cost-efficient manner, mobile access point (AP) deployment needs to be part of the overall solution. Therefore, we study the mobile AP deployment in workflow-based mobile sensor networks. We categorize MUs' workflows according to a priori knowledge of MUs' staying durations at mission locations into complete and incomplete information workflows. In both categories, we formulate the cost-minimizing mobile AP deployment problem into multiple (mixed) integer optimization problems, satisfying MUs' QoS constraints. We prove that the formulated optimization problems are NP-hard and design approximation algorithms with guaranteed approximation ratios. We demonstrate using simulations that the AP deployment cost calculated using our algorithms is 50-60% less than the stationary baseline approach and fairly close to the optimal AP deployment cost. In addition, the run times of our approximation algorithms are only 10-25% of those of the branch-and-bound algorithm used to derive the optimal AP deployment cost.

Original languageEnglish (US)
Title of host publicationProceedings - IEEE 22nd International
PublisherIEEE Computer Society
Pages83-94
Number of pages12
ISBN (Electronic)9781479962044
DOIs
StatePublished - Dec 9 2014
Event22nd IEEE International Conference on Network Protocols, ICNP 2014 - Research Triangle, United States
Duration: Oct 21 2014Oct 24 2014

Publication series

NameProceedings - International Conference on Network Protocols, ICNP
ISSN (Print)1092-1648

Other

Other22nd IEEE International Conference on Network Protocols, ICNP 2014
CountryUnited States
CityResearch Triangle
Period10/21/1410/24/14

ASJC Scopus subject areas

  • Computer Networks and Communications
  • Software

Fingerprint Dive into the research topics of 'Cost-minimizing mobile access point deployment in workflow-based mobile sensor networks'. Together they form a unique fingerprint.

  • Cite this

    Jin, H., Huang, H., Su, L., & Nahrstedt, K. (2014). Cost-minimizing mobile access point deployment in workflow-based mobile sensor networks. In Proceedings - IEEE 22nd International (pp. 83-94). [6980368] (Proceedings - International Conference on Network Protocols, ICNP). IEEE Computer Society. https://doi.org/10.1109/ICNP.2014.29