A Simulated Annealing Based Algorithm for Energy-Constrained Ferry Route Design Problem

Abstract:

Message ferry is a controllable mobile node equipped with long distance communication antennas and rechargeable energy, to collect data in sparse wireless networks and delivery it to the base station. The Energy-Constrained Ferry Route Design (ECFRD) Problem aims to schedule the ferry route when the energy of the ferry is not sufficient to access all the nodes in the network in one tour without charging, so as to minimize the total route length of the ferry. In this paper, we propose a simulated annealing based algorithm to solve the ECFRD problem. The experimental results show that the algorithm proposed in this paper can greatly reduce the total route length of the ferry, comparing the classic nearest neighbor algorithm.

• Periodical: Advanced Materials Research (Volumes 791-793)
• Pages: 1113-1116
• DOI: https://doi.org/10.4028/www.scientific.net/AMR.791-793.1113
• Online since: September 2013
• Authors: Yong Wang, Qiang Dou, Wei Peng, Zheng Hu Gong
• Keywords: Energy Constrained, Message Ferry, Route Design, Simulated Annealing (SA), Sparse Wireless Networks

References

[1] P. Juang, H. Oki, Y. Wang, M. Martonosi, L. S. Peh, and D. Rubenstein, Energy-efficient computing for wildlife tracking: design tradeoffs and early experiences with zebranet, SIGOPS Oper. Syst. Rev., vol. 36, no. 5, p.96–107, (2002).

DOI: 10.1145/635508.605408

[2] Y. Wang, W. Peng, Q. Dou, and Z. Gong, Stationary distribution for the mobilities in catastrophe rescue scenario, "KSII Transactions On Internet and Information Systems, vol. 7, no. 2, pp.308-326, (2013).

DOI: 10.3837/tiis.2013.02.008

[3] W. Zhao and M. Ammar, Message ferrying: Proactive routing in highly-parititioned wireless ad hoc networks, in Proceedings of the 9th IEEE International Workshop on Future Trends of Distributed Computing Systems, (Puerto Rico), p.308–314, (2003).

DOI: 10.1109/ftdcs.2003.1204352

[4] W. Zhao, M. Ammar, and E. Zegura, A message ferrying approach for data delivery in sparse mobile ad hoc networks, in Proceedings of the 5th ACM international symposium on Mobile ad hoc networking and computing, (Roppongi Hills, Tokyo, Japan), p.187–198, ACM, (2004).

DOI: 10.1145/989459.989483

[5] K. Fall, A delay-tolerant network architecture for challenged internets, in Proceedings of the 2003 conference on Applications, technologies, architectures, and protocols for computer communications, (Karlsruhe, Germany), p.27–34, ACM, (2003).

DOI: 10.1145/863955.863960

[6] W. Yong, P. Wei, D. Qiang, and G. Zhenghu, Energy-constrained ferry route design for sparse wireless sensor networks, Submitted to Publish, (2013).

[7] S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi, Optimization by simulated annealing, Science, vol. 220, p.671–680, (1983).

DOI: 10.1126/science.220.4598.671