he study of self-organizing systems has now reached the tool-building phase, in which a new discipline of self-managing systems engineering can begin to emerge. The next step is to refine the principles of self-organization into a system of composable parts suitable for engineering-much as components such as capacitors, transistors, and resistors capture electromagnetism principles for electronic engineering. To transform a science into an engineering discipline, we must • decouple aspects of the problem from one another, • identify an operating range, • create standard interfaces for composition, • identify primitive components that conform to the standards, and • create abstraction rules that hide the complexity of systems of components. We've begun this process in the domain of sensor/actuator network applications, observing that in many applications the deployed network approximates a physical space and that the space, rather than the network, is being programmed. This observation lets us use the amorphous medium abstraction to decouple self-management problems. So, global behavior descriptions in our Proto language can be compiled automatically into locally executed code that produces emergent phenomena matching the global description. We've experimentally verified our code both in simulation and (for small programs) on a network of sensor/actuator nodes called Mica2 motes. Consider deploying a network of devices to manage a large farm. The tasks that the devices will carry out-irrigation, pest management, and fertilization, for example-are naturally specified in terms of regions of the farm: "water a potato field every somany hours during hot weather" or "treat minor alfalfa weevil infestations with an early harvest, but treat major infestations with pesticides." An applications programmer for farms should be able to write code at this abstraction layer, rather than specifying how the devices in the fields will coordinate to carry out the programs. The amorphous-medium abstraction captures the divide between specification and implementation; it's a continuous computational material filling the space of interest. Every point in the medium is a computational device that independently executes the same code as every other device in the medium. (Executions diverge owing to differences in sensor values, randomness, and each device's interactions with nearby devices.) Each device has a neighborhood of devices less than d units of distance away to which it exposes its internal state. Conversely, a device can read the internal state of devices in its neighborhood, obtaining values lagged proportionally to the distance separating them. We can't, of course, build a continuous medium containing uncountably many infinitely small computers. We can, however, approximate it by scattering a discrete set of devices throughout the medium. We then compute using as our basis the relatively few systems whose discrete behavior is a good approximation of their continuous behavior, just as electronic engineering uses components that capture only a few electromagnetism phenomena. In both cases, restricting the behavior range supports engi- neering abstractions that ignore much of the underlying system's complexity. The amorphous-medium abstraction separates the space being programmed from the devices carrying out the program, letting us decompose self-managing systems engineering into three layers of abstraction-global, local, and discrete (see figure 1) . Each layer is supported by its own infrastructure component; this decouples aspects of self-managing systems design into largely independent subproblems: • The discrete layer consists of devices embedded in space exchanging messages with nearby neighbors. Infrastructure for this level is a discrete kernel that approximately emulates an amorphous medium. • The local layer executes on the amorphous medium, using our Proto language to specify a uniform behavior for each point. • The global layer executes on the amorphous medium, using a library of amorphous-computing algorithms translated into Proto to control the regions' behavior. Table 1 illustrates some design problems that this approach separates: • Our approach's implementation has three infrastructure components: a kernel providing the neighborhood abstraction, a compiler for the Proto language, and libraries of long-range coordination and control primitives coded in Proto. • Global-layer coordination primitives operate on regions and are implemented with local-layer interactions between points and their neighborhoods. The neighborhood is, in turn, implemented by messages passed between discrete devices. • This approach describes global control as homeostatic processes continually moving regions toward a desired behavior. It implements these processes as networks of streams in the local layer, which compile to update code executed periodically in the discrete layer. • Different layers handle different failure modes: the neighborhood abstraction masks individual device crashes, the homeostatic primitives handle outside events that destroy regions of the network, and a clean global-layer interface minimizes bugs in the user's code. • Assuming that the cost of communication dominates energy consumption, the amount of communication depends on how many long-range coordination operations occur in the global layer, how many reductions over neighbor state are used to implement coordination at the local layer, and how many packets are transmitted and received to implement shared neighbor state at the discrete layer. For information on amorphous-medium research and other related research, see the sidebar "Related Work on Engineering Self-Managing Systems." We can consider a sensor/actuator network in which devices communicate only with nearby neighbors to be an amorphous computer. 1 Amorphous computing takes inspiration from biological systems engaged in morphogenesis and regeneration, in which extremely large numbers of unreliable devices (cells) coordinate to achieve predictable results with high precision. We've chosen the amorphous-computer model for two reasons. First, its biologically inspired specifications imply the self-management issues www.computer.org/intelligent S e l f -M a n a g i n g S y s t e m s 12 www.computer.org/intelligent IEEE INTELLIGENT SYSTEMS of robustness, distribution, and scalability. Second, real-world sensor/actuator networks are growing rapidly in scale and capability, bringing them into closer alignment with the amorphous-computer model. In particular, we designed Proto and its infrastructure to operate on sensor/actuator networks with these properties: • The number of devices n might range from dozens to billions. • Devices are distributed arbitrarily through space and collaborate via unreliable broadcast to neighbors no farther than r distance away. • Devices move much more slowly than communication, if at all. • Memory and processing aren't limiting resources. (Profligate expenditure of either is still bad, and memory is an important constraint for our mote implementation.) • Execution is partially synchronous-each device has a clock that ticks regularly, but frequency might vary by up to ⑀, and clocks have an arbitrary initial time and phase. • The networks don't provide naming, routing, and coordinate services. (These services might be made available as sensor values, with appropriate characterization of reliability and error.) • Arbitrary point and region stopping failures and joins might occur, including changes in the network's connectedness. Our operating-range specification doesn't directly address energy consumption, although it has been a concern in implementation. Each abstraction layer can independently address energy issues, however, and we expect that optimizing the discrete-kernel implementation Our research on self-managing systems engineering draws on previous work in many fields: our contribution lies in integrating the pieces that others have developed. Previous research on amorphous-medium languages proposed the amorphousmedium abstraction and general strategies for controlling an amorphous medium; 1,2 this article describes a practical implementation. Other research on amorphous-computing languages has shared the same general goals but has been directed more toward problems of morphogenesis and pattern formation than general computation. Examples include Daniel Coore's research on topological patterns 3 and research on geometric-shape formation by Radhika Nagpal; 4 Attila Kondacs; 5 and Justin Werfel, Yaneer Bar-Yam, and Radhika Hagpal. 6 A notable exception is William Butera's work on paintable computing, which allows general computation but lacks an abstraction barrier separating an applications programmer from low-level details of network operation. 7 An alternate approach to engineering self-organizing systems is rooted in gossip communication, 8-10 a technique we also use. However, gossip communication deploys lesspowerful abstractions than our approach does, because it's solving more-general networking problems. More distant are approaches based on alternate computational paradigms such as chemical computation 11,12 and membrane computation. 13 Sensor network researchers have proposed several other highlevel programming abstractions to enable the programming of large networks. For example, GHT (Geographic Hash Table) provides a hash table abstraction for storing data in the network, 14 and TinyDB focuses on gathering information through query processing. 15 Both of these approaches, however, are data-centric rather than computation-centric and don't provide guidance on how to do distributed manipulation of gathered data. TinyOS 16 and the Hood abstraction 17 provide useful general programming tools-indeed, our implementation of Proto on motes uses TinyOS-but the abstractions are less powerful and lead to bulkier, less reusable code. More similar is the Regiment language, which uses a stream-processing abstraction to distribute computation across the network. 18 Regiment, however, is distributed only when the compiler finds optimization opportunities, and significant challenges remain in adapting its programming model to the sensor network environment. Finally, Proto's structure as a dynamic network of streams is strongly influenced by Jonathan Bachrach's previous work on Gooze, 19 as are many compilation strategies used to compact Proto code for execution on motes. There's a long tradition of stream processing in programming languages. The closest and most recent work is Functional Reactive Programming, 20 which is based on Haskell, 21 a statically typed programming language with lazy evaluation semantics. FRP has been demonstrated on robotics, 22 graphics, 20 and user interface design. 23 These systems focus less on runtime space and time efficiency than our approach does, and the type system is firmly wedded to Haskell, with all its strengths and weaknesses.
One of the application scenarios envisioned for the (programming) techniques developed within the framework of such an initiative was to engineer the emergence of structures in sensor-actuator networks REF .
Infrastructure for engineered emergence on sensor/actuator networks
IEEE Intelligent Systems
IEEE Intelligent Systems
Computer Science