Tour planning for mobile data-gathering mechanisms in wireless sensor networks

Ming Ma, Yuanyuan Yang, Miao Zhao

Research output: Journal article publicationJournal articleAcademic researchpeer-review

160 Citations (Scopus)

Abstract

In this paper, we propose a new data-gathering mechanism for large-scale wireless sensor networks by introducing mobility into the network. A mobile data collector, for convenience called an M-collector in this paper, could be a mobile robot or a vehicle equipped with a powerful transceiver and battery, working like a mobile base station and gathering data while moving through the field. An M-collector starts the data-gathering tour periodically from the static data sink, polls each sensor while traversing its transmission range, then directly collects data from the sensor in single-hop communications, and finally transports the data to the static sink. Since data packets are directly gathered without relays and collisions, the lifetime of sensors is expected to be prolonged. In this paper, we mainly focus on the problem of minimizing the length of each data-gathering tour and refer to this as the single-hop data-gathering problem (SHDGP). We first formalize the SHDGP into a mixed-integer program and then present a heuristic tour-planning algorithm for the case where a single M-collector is employed. For the applications with strict distance/time constraints, we consider utilizing multiple M-collectors and propose a data-gathering algorithm where multiple M-collectors traverse through several shorter subtours concurrently to satisfy the distance/time constraints. Our single-hop mobile data-gathering scheme can improve the scalability and balance the energy consumption among sensors. It can be used in both connected and disconnected networks. Simulation results demonstrate that the proposed data-gathering algorithm can greatly shorten the moving distance of the collectors compared with the covering line approximation algorithm and is close to the optimal algorithm for small networks. In addition, the proposed data-gathering scheme can significantly prolong the network lifetime compared with a network with static data sink or a network in which the mobile collector can only move along straight lines.
Original languageEnglish
Article number6359890
Pages (from-to)1472-1483
Number of pages12
JournalIEEE Transactions on Vehicular Technology
Volume62
Issue number4
DOIs
Publication statusPublished - 1 Jan 2013
Externally publishedYes

Keywords

  • Covering salesman problem (CSP)
  • data gathering
  • M-collector
  • mobile data collector
  • mobility
  • movement planning
  • spanning tree
  • traveling salesman problem (TSP)
  • wireless sensor networks (WSNs)

ASJC Scopus subject areas

  • Automotive Engineering
  • Aerospace Engineering
  • Computer Networks and Communications
  • Electrical and Electronic Engineering

Cite this