The Disk Covering Tour Problem in the Wireless Sensor Network

摘要

The paper discusses the disk covering tour problem for reducing the mobile devices’ mobile electricity costsconsumed in the wireless sensor network. The DCTP discusses how to find a tour whose cost is the minimum under thecondition of the defined initial points and some planar points. The tour starts from the initial stop point. After passingmany stop points, the tour returns to the initial stop point. Although the stop point is unnecessary to be in the definedpoints, the distance between each defined point and a certain stop point during the tour at least should be within the defineddisk radius. The electricity can be consumed much when the mobile devices move in and out the stop points. Therefore,the less the number of the stop points is, the less the tour cost is. How to reduce the number of the stop points is regardedas the disk covering problem. The decreasing k-means algorithm is proposed to try finding out the nearly minimumdisk for covering all defined points, and then the Lin-Kernighan heuristic is introduced to find out the approximatingshortest tour through the obtained stop points. The experimental simulations compare solution algorithms between themethod proposed in the paper and other related methods with the Qi-Ferry method for finding out the shortest tour, andthen the results show that the method proposed in the paper has the advantage of having a smaller tour cost.