A Heuristic Routing Scheme for Wireless Sensor Networks Based on a Local Search Method
Satoshi Fujita, XingPing He, Sayaka Kamei · 2009
In this paper, we propose a distributed algorithm to calculate a subgraph of a given wireless sensor network (WSN) connecting a set of sources and a set of sinks such that: 1) the length of a path connecting from a source to a sink in the subgraph does not exceed the distance from the source to the farthest sink, and 2) the number of links contained in the subgraph is minimized. The proposed algorithm tries to improve the quality of an initial solution generated by a heuristic scheme by repeatedly applying a local search. The result of simulations indicates that: 1) using a heuristic to generate an initial solution, the size of the initial solution reduces by 10 % compared with a simple shortest path tree; and 2) a local search reduces the size of the resultant subgraph by 20 % and the cost required for such improvement can be recovered by utilizing the resultant subgraph for a sufficiently long time such as few days.