Algorithms and system - level support for agent placement and migration in wireless sensor networks

Abstract

Wireless sensor systems have drawn much attention from a considerable part of scientific community during the last years. The advances in this field range from the design of battery-powered embedded nodes to the development of software (i.e. operating system, middleware, etc) especially designed to run on such resource-constrained devices. One of the most challenging parts for both hardware and software oriented work is to maximize the lifetime of such nodes. This thesis focuses on the design and implementation of mobile code placement and migration algorithms for distributed applications in order to reduce the amount of application-level communication performed over the network. Since the largest part of a node’s energy expenditure is attributed to the wireless communication (not code execution), reducing the energy consumption becomes of paramount importance, leading in that way to an increased system lifetime. In the sequel, we give a brief overview of the application model, the algorithms and the middleware designed and implemented in the context of this thesis. The model adopted in this work is inspired by the POBICOS [91] platform, where the application is organized as a set of software entities (agents) that communicate with each other to implement the desired functionality. An agent can be ―non-generic? or ―generic?. Non-generic agents use special resources of a node, e.g. a sensor measuring a physical quantity or an actuator controlling a device or function. On the contrary, generic agents perform computational tasks and decision making at a higher level, without relying on special resources. Chapter 1 introduces the agent migration problem stated as follows: given an application that is deployed in a sensor network, perform generic agent migrations in order to reduce the data exchanged over the network due to the application-level communication between agents. We propose fully distributed algorithms that migrate an agent towards its center of gravity (in terms of communication load), thereby reducing the network cost. Also, two protocols are presented for handling the case of nodes with storage constraints (for hosting agents). iv Chapter 2 examines the same (above) problem, with the difference that it considers migrations of agent groups instead of single agent migrations. The algorithms in question deal with co-located agents that are ―mutually dependent?, which in the case of the simpler algorithms may hinder migration, leading to noticeably inferior placements. Chapter 3 discusses the competitiveness of the aforementioned algorithms versus the optimal algorithm. Also, it presents an enhancement of the group migration algorithms in order for them to produce an optimal agent placement (in terms of the network cost incurred by the application). It should be stressed that this enhancement guarantees optimality only if nodes do not have storage constraints, else the problem is NP-complete. Chapter 4 proposes fully distributed algorithms for the problem of generic agent migrations for resource-constrained nodes, introducing the concept of ―evictions?. Specifically, agent migrations are considered that are not beneficial in their own right but free space which can be used to perform additional (beneficial) migrations. Of course, the ultimate goal is to reduce the network load, so the total benefit of the migrations must be greater than the cost of the non-beneficial ones. In Chapter 5 we focus on the problem that the aforementioned algorithms are not able to ―guess? whether a (group) migration will turn out to actually reduce the network cost. They simply assume that the structure and communication pattern of the application remains stable for a ―sufficiently? long time, so as to amortize the migration cost. As a consequence, frequent changes in the application-level load may lead to frequent agent migrations, thereby increasing the network cost (instead of reducing it). For example, an agent may continuously ―oscillate? between two nodes due to periodic changes of the communication load with other agents (changing its center of gravity), before the respective migration cost is amortized. For this reason, we propose online algorithms, along with a discussion of their competitiveness versus the offline optimal algorithm. In Chapters 6 and 7 we propose centralized algorithms tackling more complex problems. Specifically, chapter 6 addresses the problem of reducing the network cost through migrations of both generic and non-generic agents, considering that the nodes of the system have storage capacity limitations. The proposed algorithms use graph coloring techniques. In Chapter 7, a two-dimensional problem is considered, the objectives being: (a) to maximize the number of agents hosted by the nodes of the system; and (b) to maximize the network lifetime (maximize the lifetime of the first node that depletes its battery). We propose algorithms solving each dimension (sequentially) in an independent way, along with a branch-and-bound algorithm v tackling the problem concurrently in both dimensions. Regarding the first dimension of the problem, a considerable part of the algorithms involves the de-fragmentation of the nodes’ storage capacity, through agent migrations. Chapter 8 describes the implementation of the component of the POBICOS middleware that provides full-fledged, distributed, agent management functionality, on top of the TinyOS embedded operating system. Specifically, we describe: i) the mechanism for creating agents on eligible nodes; ii) the mechanism for transporting agent-level messages; iii) the mechanism detecting and destroying ―orphan? agents; and iv) the mechanism for the migration of generic agents with full transparency for the application. Finally, Chapter 9 discusses works related to this thesis, while Chapter 10 includes an overview of this dissertation and future directions.