The Disk Covering Tour Problem in the Wireless Sensor Network

ABSTRACT

The paper discusses the disk covering tour problem for reducing the mobile devices’ mobile electricity costs consumed in the wireless sensor network. The DCTP discusses how to find a tour whose cost is the minimum under the condition of the defined initial points and some planar points. The tour starts from the initial stop point. After passing many stop points, the tour returns to the initial stop point. Although the stop point is unnecessary to be in the defined points, the distance between each defined point and a certain stop point during the tour at least should be within the defined disk 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 regarded as the disk covering problem. The decreasing k-means algorithm is proposed to try finding out the nearly minimum disk for covering all defined points, and then the Lin-Kernighan heuristic is introduced to find out the approximating shortest tour through the obtained stop points. The experimental simulations compare solution algorithms between the method proposed in the paper and other related methods with the Qi-Ferry method for finding out the shortest tour, and then the results show that the method proposed in the paper has the advantage of having a smaller tour cost.

Keywords: