Title :
A Heuristic Routing Scheme for Wireless Sensor Networks Based on a Local Search Method
Author :
Fujita, Satoshi ; He, XingPing ; Kamei, Sayaka
Author_Institution :
Grad. Sch. of Eng., Hiroshima Univ., Higashi-Hiroshima, Japan
Abstract :
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.
Keywords :
distributed algorithms; graph theory; telecommunication network routing; tree searching; wireless sensor networks; distributed algorithm; heuristic routing scheme; local search method; shortest path tree; subgraph; wireless sensor networks; Arithmetic; Costs; Distributed algorithms; Event detection; Helium; Joining processes; Routing; Search methods; Wireless communication; Wireless sensor networks;
Conference_Titel :
Pervasive Systems, Algorithms, and Networks (ISPAN), 2009 10th International Symposium on
Conference_Location :
Kaohsiung
Print_ISBN :
978-1-4244-5403-7
DOI :
10.1109/I-SPAN.2009.50
