Solving Closed Walk Ferry Route Design Problem by Using an Improved Genetic Algorithm

Abstract:

In recent years, using message ferries as mechanical carriers of data has been shown to be an effective way to collect information in wireless sensor networks. Closed Walk Ferry Route Design (CWFRD) problem aims to minimize the average weighted delay of the sensed data to the sink by designing the ferry route as a closed walk which contains more than one simple cycle. In this paper, an improved genetic algorithm is proposed to solve the CWFRD problem. Different to other problems solved by the genetic algorithm, in the CWFRD problem, the ferry may access the sink node more than one time, and then the lengths of the two chromosomes for evolving may be different. The proposed Improved Genetic Algorithm (IGA) can solve this problem, and experimental results show that IGA can greatly reduce the average weighted delay.

• Periodical: Advanced Materials Research (Volumes 791-793)
• Pages: 1117-1120
• DOI: https://doi.org/10.4028/www.scientific.net/AMR.791-793.1117
• Online since: September 2013
• Authors: Yong Wang, Qiang Dou, Wei Peng, Zheng Hu Gong
• Keywords: Closed Walk, Genetic Algorithm (GA), Message Ferry, Route Design, Wireless Sensor Network (WSN)

References

[1] A. S. Arun, R. Aditya, and B. S. Mani, Mobile element scheduling with dynamic deadlines, Mobile Computing, IEEE Transactions on, vol. 6, no. 4, p.395–410, (2007).

DOI: 10.1109/tmc.2007.57

[2] 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

[3] A. Vahdat and D. Becker, Epidemic routing for partially connected ad hoc networks, tech. rep., Duke University, (2000).

[4] 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

[5] W. Yong, D. Qiang, P. Wei, and G. Zhenghu, Closed walk ferry route design for wireless sensor networks, Submitted to Publish, (2013).

[6] D. E. Goldberg, Genetic Algorithms in Search, Optimization and Machine Learning. Boston, MA, USA: Addison-Wesley Longman Publishing Co., Inc., 1st ed., (1989).