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

fYear

2009

fDate

14-16 Dec. 2009

Firstpage

46

Lastpage

51

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;

fLanguage

English

Publisher

ieee

Conference_Titel

Pervasive Systems, Algorithms, and Networks (ISPAN), 2009 10th International Symposium on

Conference_Location

Kaohsiung

Print_ISBN

978-1-4244-5403-7

Type

conf

DOI

10.1109/I-SPAN.2009.50

Filename

5381971