Abstract: Large-scale sensor networks, monitoring an environment at close range with high spatial and temporal resolutions are expected to play an important role in various applications, e.g., assessing the ``health'' of machines; environmental, medical, food-safety, and habitat monitoring; inventory control, building automation, etc. Ensuring the security of these complex and yet resource-constrained systems has emerged as one of the most pressing challenges for researchers. In this paper (i) we present the major threats and some characteristic countermeasures, (ii) we propose a way to classify existing systems for intrusion detection in wireless sensor networks and (iii) we present a new approach for decentralized energy efficient intrusion detection that can be used to improve security from both external and internal adversaries.
Abstract: We study the problem of scheduling permanent jobs on un-
related machines when the objective is to minimize the Lp
norm of the machine loads. The problem is known as load
balancing under the Lp norm. We present an improved up-
per bound for the greedy algorithm through simple analy-
sis; this bound is also shown to be best possible within the
class of deterministic online algorithms for the problem. We
also address the question whether randomization helps on-
line load balancing under Lp norms on unrelated machines;
this is a challenging question which is open for more than a
decade even for the L2 norm. We provide a positive answer
to this question by presenting the ¯rst randomized online
algorithms which outperform deterministic ones under any
(integral) Lp norm for p = 2; :::; 137. Our algorithms es-
sentially compute in an online manner a fractional solution
to the problem and use the fractional values to make ran-
dom choices. The local optimization criterion used at each
step is novel and rather counterintuitive: the values of the
fractional variables for each job correspond to °ows at an ap-
proximate Wardrop equilibrium for an appropriately de¯ned
non-atomic congestion game. As corollaries of our analysis
and by exploiting the relation between the Lp norm and the
makespan of machine loads, we obtain new competitive algo-
rithms for online makespan minimization, making progress
in another longstanding open problem.
Abstract: We study the problem of scheduling permanent jobs on un-
related machines when the objective is to minimize the Lp
norm of the machine loads. The problem is known as load
balancing under the Lp norm. We present an improved up-
per bound for the greedy algorithm through simple analy-
sis; this bound is also shown to be best possible within the
class of deterministic online algorithms for the problem. We
also address the question whether randomization helps on-
line load balancing under Lp norms on unrelated machines;
this is a challenging question which is open for more than a
decade even for the L2 norm. We provide a positive answer
to this question by presenting the ¯rst randomized online
algorithms which outperform deterministic ones under any
(integral) Lp norm for p = 2; :::; 137. Our algorithms es-
sentially compute in an online manner a fractional solution
to the problem and use the fractional values to make ran-
dom choices. The local optimization criterion used at each
step is novel and rather counterintuitive: the values of the
fractional variables for each job correspond to °ows at an ap-
proximate Wardrop equilibrium for an appropriately de¯ned
non-atomic congestion game. As corollaries of our analysis
and by exploiting the relation between the Lp norm and the
makespan of machine loads, we obtain new competitive algo-
rithms for online makespan minimization, making progress
in another longstanding open problem.