On-line genetic programming of multi-hop broadcast protocols in ad hoc networks

Abstract

From the family of ad hoc communication protocols the most challenging ones are those, that are designed to disseminate messages to all, or most of the nodes in the system. By their nature, these kinds of protocols use significant network resources, as the communication must involve a large fraction of the network nodes. Reducing the network load can be achieved by using the available local broadcast medium (radio channel), but it is not trivial how to select the set of nodes that should participate in the dissemination process. Previous attempts delivered algorithms that can provide reasonable performance and reliability but mostly for specific cases of ad hoc networks. In this paper a new way of tackling the broadcast problem is presented that takes no assumptions about the nature of the underlying network. Instead of using hand-optimizing protocols, we propose a framework for a self-optimizing and self-managing system inspired by natural selection and evolution. A generic distributed feed-forward performance evaluation criterion based on natural selection is presented along with an implementation of a virtual machine and a corresponding language for Genetic Programming to be used in tandem with the natural selection process.