The design of efficient routing algorithms is an important issue in dense ad hoc wireless networks. Previous theoretical work has shown that benefits can be achieved through the creation of a set of data “highways” that carry packets across the network, from source(s) to sink(s). Current approaches to the design of these highways however require a–priori knowledge of the global network topology, with consequent communications burden and scalability issues, particularly with regard to reconfiguration after node failures. In this chapter, we describe a bio–inspired approach to generating these data highways through a distributed reaction–diffusion model that uses localized convolution with activation–inhibition filters. The result is the distributed emergence of data highways that can be tuned to provide appropriate highway separation and connection to data sinks. In this chapter, we present the underlying models, algorithms, and protocols for generating data highways in a dense wireless sensor network. The proposed methods are validated through extensive simulations performed using OMNeT++.
TopIntroduction
An activator-inhibitor model is a special case of a reaction-diffusion system where two chemicals interact in an antagonistic way, resulting in Turing patterns in space (Turing, 1952), such as spots and stripes on the skin of animals (e.g. leopard, zebra). Activator-inhibitor models are customarily used to study the process of morphogenesis. They offer an abstract model to explain many different morphogenetic phenomena, including the regular spacing of cactus thorns and bird feathers, shape regeneration after damage, the production of sequences of repeated elements such as insect body segments, the assembly of photoreceptor cells in insect eyes, and the positioning of leaves in growing plants (Bar-Yam, 2003 ; Koch & Meinhardt, 1994). They have also been used as inspiration for algorithms to produce textures and landscapes in computer graphics, and for autonomous, decentralized, distributed coordination algorithms, for instance in amorphous computing (Abelson, 2000), wireless and sensor networks (Durvy & Thiran, 2005), and autonomous surveillance systems (Yoshida, Aoki & Araki, 2005; Hyodo, Wakamiya & Murata, 2007).
In several works, authors proposed the use of bio-inspired approaches in order to face the design of an efficient routing protocol, which is the major challenge in ad hoc wireless network research. An ad hoc wireless network is a decentralized wireless network, where each node can communicate with every other node within communication range. In ad hoc wireless networks, the specific algorithm used for conveying traffic through the network from a data source to a destination can have a major impact on the power efficiency, communication latency and robustness of the network (Yu & Chong, 2005; Erciyes, 2007). Previous work (Franceschetti, Dousse, Tse & Thiran, 2007) showed that the creation of a set of wireless “backbones” or data highways that carry packets across the network, from sources to sink, can provide a communication capacity in networks with randomly located nodes that is comparable to that which can be achieved in networks with arbitrarily placed nodes. The highways are constructed such that every source node is within range of at least one highway (implying it can access it in a single hop). The highways then drain packets to the sinks along a series of much shorter length hops, with correspondingly lower power requirements and hence a lower interference footprint. Every sink is at most one hop from the highway.
In previous work, approaches such as percolation theory were used to identify the existence of highways (Franceschetti, Dousse, Tse & Thiran, 2007). This has the disadvantage that it requires an a–priori analysis of the entire network structure, with the consequence that the approaches cannot readily accommodate randomly placed nodes unless there is a mechanism for determining and communicating node location— a constraint that adds a layer of complexity and a performance burden. It also typically makes the network less robust, as any change (such as a failure or location change of a highway node) requires a global recalculation of the routing pathways.
In this chapter, we discuss a bio–inspired approach to addressing this problem through distributed construction and optimization of the data highways based on an activation–inhibition diffusion that generates optimal highway separation. We argue that this bio–inspired approach represents a significant contribution, insofar as it will improve robustness and allow localized self–healing of the data highways — an important characteristic of dense networks with randomly placed nodes.
The remainder of this chapter is organized as follows. In Section 2, we briefly describe the bio–inspired approach pursued to build data highways in a fully distributed fashion. In Section 3, we describe the algorithms used to build the data highways and to route packets from any node to the closet sink. Then, Section 4 presents simulation results and analysis showing the performance of the bio–inspired approach. Finally, we present our conclusions in Section 5.