Efficient Multihop Broadcast with Distributed Protocol Evolution

摘要

In this paper we describe an efficient way of implementing multi hop broadcast in ad hoc mobile networks with an online, distributed machine intelligence solution. In our solution not just the runtime parameters of predefined protocols are optimized, but the decision logic itself also emerges dynamically. The model is based on genetic programming and natural selection: sucessive generations of protocol instances are produced to approximate optimal performance by picking certain instances from the previous generation (natural selection) and combining them with each other and/or mutating (genetic operators) them. We implemented (i) a genetic programming language to describe protocols, and (ii) defined a distributed, communication-wise non-intensive, stigmergic feed-forward evaluation and selection mechanism over protocol instances, and (iii) a budget based fair execution model for competing protocols. The results indicate that online, autonomous protocol evolution outperforms traditional approaches, by adapting to the situation at hand, when used for the multi-hop broadcast problem in ad hoc mobile networks. The evolution also protected the system from the negative effects of initially present harmful protocols.