On Optimal One-dimensional Routing Strategies in Sensor Networks^*

Abstract

In this paper we discuss three kind of routing strategies for wireless networks where the positions of nodes are fixed, which is a typical situation in sensor networks. We describe a strategy for finding optimal deterministic strategies and solve explicitly the problem of optimal strategies for some simple but canonical cases when nodes are placed on a line. Next we describe the notion of probabilistic strategies and improve a result from IPSN'2005 by Giridhar and Kumar giving a precise formula for a cost of an optimal probabilistic strategies for the nodes placed at equal distances on a line. Finally we introduce the notion of mixed strategies and show some its applications.

Keywords: Sensor Network; Placement Strategy; Energy Cost; Transmission Range; Routing.

Published in Proceedings of 4th International Conference on Broadband Communication, Information Technology & Biomedical Applications (BroadBandCom'09), Wrocław, Poland, July 15-18, 2009.

^*Partially supported by EU Operational Programme Innovative Economy 2007 2013 No POIG.01.03.01-02-002/08-00 and by the grant No 342346 of the Institute of Mathematics and Computer Science, Wroclaw University of Technology.

Conference paper