We are entering a new age in the evolution of computer systems, in which pervasive computing technologies seamlessly interact with human users [Satyanarayanan, 2001;Weiser, 1991]. These technologies serve people in their everyday lives at home and work by functioning invisibly in the background. They free them from tedious routine tasks and create a smart environment around them [Cook and Das, 2004]. In the influential article ââ¬ÅThe Computer for the 21st Centuryââ¬?, Mark Weiser described smart environments as a ââ¬Åphysical world that is richly and invisibly interwoven with sensors, actuators, displays, and computational elements, embedded seamlessly in the everyday objects of our lives, and connected through a continuous networkââ¬? [Weiser, 1991]. For example, this would be an intelligent building, or a smart traffic control system. Now, since such smart environments need information about their surroundings, they rely first and foremost on sensory data from the real world. More accurately, this data is provided by wireless sensor networks, which are responsible for sensing as well as for information collecting [Lewis, 2004]. Thus, improving the efficiency of these tasks in the networks of wireless sensors is of necessity. Given this, we will focus on efficient long-term (e.g. lifetime-long) information collection of these networks, using learning-theory to tackle this challenge.