Title: Success guaranteed routing in almost Delaunay planar nets for wireless sensor communication

Authors: Md. Bahlul Haider, Shinji Imahori, Kokichi Sugihara

Addresses: Department of Computer Science, University of Western Ontario, 1151 Richmond Street, London, Ontario N6A 3K7, Canada. ' Department of Computational Science and Engineering, Graduate School of Engineering, Nagoya University, Furo-cho, Chikusa-ku, Nagoya 464-8603, Japan. ' Meiji Institute for Advanced Study of Mathematical Sciences, Meiji University, 1-1-1 Higasimita, Tamaku, Kawasaki 214-8571, Japan

Abstract: This paper proposes a routing strategy for wireless sensor networks that is valid even when the sensor nodes are distributed non-uniformly. Energy efficiency is the most important consideration in wireless sensor networks; hence, global communication should be achieved by combinations of local messages. We first propose a new underlying graph called the almost Delaunay planar net, which can be calculated from information local to the sensor nodes. We statistically analyse the efficiency of existing routing strategies in the almost Delaunay planar net. We also propose a new routing strategy that always guarantees the reachability on planar graphs, including the almost Delaunay planar net. We show that the proposed routing strategy exhibits good performance if the underlying graph in the sensor network is the almost Delaunay planar net.

Keywords: wireless sensor networks; WSNs; routing strategy; Delaunay triangulation; Voronoi polygon; cluster head; wireless networks; non-uniform distribution; sensor nodes; energy efficiency; planar graphs.

DOI: 10.1504/IJSNET.2011.038760

International Journal of Sensor Networks, 2011 Vol.9 No.2, pp.69 - 75

Available online: 01 Mar 2011 *

Full-text access for editors Access for subscribers Purchase this article Comment on this article