Reza Moazzez Estanjini

May 2011
Vehicle Scheduling And Routing For Data Transport In Wireless Sensor Networks
Committee Members: Advisor: Ioannis Paschalidis, SE/ECE; Appointed Chair: David Castanon, SE/ECE; Christos Cassandras, SE/ECE; Calin A. Belta, SE/ME; David Starobinski, SE/ECE

Abstract: The traditional approach for data relaying in Wireless Sensor NETworks (WSNETs) involves multi-hop communications from data sources to destinations. In addition to problems that multi-hop routing may cause when networks become partitioned, relaying data over a large number of hops reduces the lifetime of sensor nodes. It is known that the use of some mobile elements, which in this dissertation are referred to as Message Ferries (MFs), to transport data from node to node can overcome the mentioned difficulties. In this dissertation, a WSNET in which MFs are used is termed Mobile Sensor NETworks (MSNETs). In MSNETs, the data transfer efficiency depends heavily on the path followed by the MFs, hence the main challenge is the scheduling of the MFs. This dissertation addresses this issue within two settings: a static perspective and a dynamic one.

The static setting is suitable for MSNETs whose underlying dynamics are relatively slow. For such scenarios, the proposed solutions in this dissertation have performance guarantees, some present novel results on scalability of MSNETs, and some even improve the best-known solutions to some classical problems in combinatorial optimization.

On the other hand, for MSNETs whose underlying dynamics are faster and less predictable, a dynamic perspective is more suitable. For such scenarios, this dissertation addresses the problems in a Markov Decision Process (MDP) framework. A powerful novel approximate Dynamic Programming (DP) algorithm for MDP problems is presented. The algorithm is of the Actor-Critic (AC) type and uses a Least Squares Temporal Difference (LSTD) learning method. The use of the algorithm is not restricted to MSNET problems; it can also be used for many MDP problems as well as Partially Observable Markov Decision Process (POMDP) problems arising in other application areas. The forklift dispatching problem illustrated in this dissertation, which can be seen as an instance of the MF scheduling problems in MSNETs, is in fact an example of a real world problem in warehouse management where the use of the proposed algorithm is shown to be effective.