This paper is concerned with reducing communication

costs when executing distributed user tasks in a sensor network.

We take a service-oriented abstraction of sensor networks,

where a user task is composed of a set of data processing

modules (called services) with dependencies. Communications

in sensor networks consume significant energy

and introduce uncertainty in data fidelity due to high bit

error rate. These constraints are abstracted as costs on

the communication graph. The goal is to place the services

within the sensor network so that the communication

cost in performing the task is minimized. In addition, since

the lifetime of a node, the quality of network links, and the

composition of the service graph may change over time, the

quality of the placement must be maintained in the face of

these dynamics. In this paper, we take a fresh look at what

is generally considered a simple but poor performance approach

for service placement, namely the greedy algorithm.

We prove that a modified greedy algorithm is guaranteed

to have cost at most 8 times the optimum placement. In

fact, the guarantee is even stronger if there is a high degree

of data reduction in the service graph. The advantage

of the greedy placement strategy is that when there are local

changes in the service graph or when a hosting node

fails, the repair only affects the placement of services that

depend on the changes. Simulations suggest that in practice

the greedy algorithm finds a low cost placement. Furthermore,

the cost of repairing a greedy placement decreases

rapidly as a function of the proximity of the services to be

aggregated.

PDF file

In: Proceedings of the 26th IEEE International Conference on Distributed Computing Systems (ICDCS 2006)

Publisher: Institute of Electrical and Electronics Engineers, Inc.
© 2007 IEEE. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the IEEE.

Details