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

摘要

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.