Algorithms for energy-driven agent placement in wireless embedded systems with memory constraints

Abstract

The agent programming paradigm provides an easy to use framework for coding embedded applications in a pervasive environment. Under this model, applications are structured as mobile agents that can be flexibly installed on the available nodes of the system. Typically, such system nodes have limitations concerning battery and memory resources. The agent placement problem (APP) we consider in this paper, consists of deciding which agents should be placed at which nodes, in order to maximize the lifetime of the first node that runs out of battery. Since wireless communication has been identified in the past as a primary source of energy consumption, APP essentially involves bringing communicating agents close to each other, thus reducing communication costs. Nevertheless, this cannot always be done due to memory constraints. In fact as more and more agents are installed at the nodes finding free space at any node, let alone the desired one communication-wise, becomes hard. In this paper we tackle the problem of placing a newcomer agent in a step-wise fashion. First, enough memory space must be found or created at some node to place the agent. Second, the placement must be altered in order to make it energy efficient. We present algorithms that tackle each of the above steps separately as well as branch and bound methods for achieving both goals simultaneously. Our algorithms are centralized assuming a single entry point through which agents are injected into the system, with adequate knowledge of the system state and enough resources to run the proposed algorithms. The algorithms are evaluated under different simulated scenarios, and useful tradeoffs are identified. (C) 2010 Elsevier B.V. All rights reserved.