• KSII Transactions on Internet and Information Systems
    Monthly Online Journal (eISSN: 1976-7277)

Closed Walk Ferry Route Design for Wireless Sensor Networks

Vol. 7, No.10, October 29, 2013
10.3837/tiis.2013.10.002, Download Paper (Free):

Abstract

Message ferry is a controllable mobile node with large capacity and rechargeable energy to collect information from the sensors to the sink in wireless sensor networks. In the existing works, route of the message ferry is often designed from the solutions of the Traveling Salesman Problem (TSP) and its variants. In such solutions, the ferry route is often a simple cycle, which starts from the sink, access all the sensors exactly once and moves back to the sink. In this paper, we consider a different case, where the ferry route is a closed walk that contains more than one simple cycle. This problem is defined as the Closed Walk Ferry Route Design (CWFRD) problem in this paper, which is an optimization problem aiming to minimize the average weighted delay. The CWFRD problem is proved to be NP-hard, and the Integer Linear Programming (ILP) formulation is given. Furthermore, a heuristic scheme, namely the Initialization-Split-Optimization (ISO) scheme is proposed to construct closed walk routes for the ferry. The experimental results show that the ISO algorithm proposed in this paper can effectively reduce the average weighted delay compared to the existing simple cycle based scheme.


Statistics

Show / Hide Statistics

Statistics (Cumulative Counts from December 1st, 2015)
Multiple requests among the same browser session are counted as one view.
If you mouse over a chart, the values of data points will be shown.


Cite this article

[IEEE Style]
Qiang Dou, Yong Wang, Wei Peng and Zhenghu Gong, "Closed Walk Ferry Route Design for Wireless Sensor Networks," KSII Transactions on Internet and Information Systems, vol. 7, no. 10, pp. 2357-2375, 2013. DOI: 10.3837/tiis.2013.10.002

[ACM Style]
Dou, Q., Wang, Y., Peng, W., and Gong, Z. 2013. Closed Walk Ferry Route Design for Wireless Sensor Networks. KSII Transactions on Internet and Information Systems, 7, 10, (2013), 2357-2375. DOI: 10.3837/tiis.2013.10.002