This chapter deals with self-organization and communication for Wireless Sensor Networks (WSNs). It shows that nodes do not always need to know their true physical coordinates to be able to communicate in an energy-efficient manner. They can be replaced by coordinates which are not related to their geographical position, yet are easier to obtain and more efficient when used by routing protocols. The authors start by analyzing the techniques used by a node to infer its geographical location from a small number of location-aware anchor nodes. They describe how nodes can use their geographical locations to self-organize the network. The authors then present an anchor-free positioning algorithm in which nodes acquire virtual coordinates. Through a continuous updating process, virtual coordinates of neighbor nodes are brought close together. Although not related to the nodes’ geographical location, routing using these coordinates outperforms routing using true physical coordinates. This chapter hence shows that localization algorithms are not per se required when considering communication in a WSN. A better strategy is to use geographic routing protocols over non-physical virtual coordinates which are easier to obtain.
TopSelf-Organizing Wireless Sensor Networks: A Paradigm Shift
Self-organization can be defined as “the emergence of system-wide functionality from simple local interactions between individual entities” (Prehofer & Bettstetter, 2005). As we will describe in this section, self-organization principles can be applied to any collection of individual entities, be it a group of economic agents, individual bacteria, a school of fishes, or a wireless multi-hop network.
The goal of self-organization in WSNs is to create a fully-autonomic network, which can be used without human intervention after deployment. From a networking point of view, it includes enabling network-wide communication from local simple interactions between nodes. This is, in fact, the definition of self-organization given above. (Mills, 2007) extended this definition by describing the design strategies of self-organizing systems. In the following paragraphs, we give examples of emergent behavior in economics and biological systems.
Emergent behavior principles apply to economics. Every economic agent uses only local information to decide how to behave. Buyers know only their own preferences and their own budget constraints, sellers know only their own costs. Their buying and selling on markets generate market prices, containing and transmitting all information about preferences, resources and production techniques. This way, market prices guide economic agents in making the best use of the resources available. Adam Smith called the market price “the invisible hand” which leads people to behave in the interest of society even when they seek only their self-interest (McMillan, 2002).
Emergent behavior also applies to much simpler systems such as a colony of Escherichia coli, a type of bacteria. Each bacterium is provided with flagella enabling it to move. In the presence of succinate (a chemical component), each bacterium excretes chemical substances which serve as attractants for other bacteria. Whereas these unicellular beings follow simple rules, these local interactions between individual entities yield chemotactic pattern formation: the bacteria organize into swarm rings and aggregates (Brenner, Levitov, & Budrene, 1998).
In “migrating groups of fish, ungulates, insects and birds, crowding limits the range over which individuals can detect one another” (Couzin, Krause, Franks, & Levin, 2005). Despite the local knowledge of each bird, a flock of birds moves in a coherent way (see Figure 1). Moreover, as detailed in (Prehofer & Bettstetter, 2005), bird flocks exhibit all the advantageous properties of a self-organized system, namely adaptability (the flock changes when attacked by a bigger bird), robustness (the flock is still coherent even when a bird gets killed) and scalability.
Figure 1. (left) Illustration of the main principles of a self-organizing system borrowed from (Prehofer & Bettstetter, 2005). (right) picture of a starlings flock in Denmark (by Bjarne Winkler).
The previous paragraphs have shown examples of self-organizing entities and emergent behavior in economics and biological systems. We will see that WSNs have a lot in common with those systems. Because of the potentially very high number of nodes creating a wireless multi-hop network, the manufacturing cost of each individual node needs to be kept low. As a consequence, each node is capable of fulfilling only a limited set of tasks, and can only communicate with a limited number of close neighbor nodes. Hence, the concepts of emergent behavior can apply to large scale WSNs in a fashion similar to what the described biological systems achieve. This emergence enables extraordinary accomplishments by the network as a whole.