Abstract
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.
Chapter PDF
Similar content being viewed by others
References
Al Hanbali, A., Ibrahim, M., Simon, V., Varga, E., Carreras, I.: A survey of message diffusion protocols in mobile ad hoc networks. In: Proceedings of the 3rd International Conference on Performance Evaluation Methodologies and Tools, ValueTools 2008, pp. 82.1–82.16. ICST, Brussels (2008)
Cheng, X., Huang, X., Li, D., Du, D.Z.: Polynomial-time approximation scheme for minimum connected dominating set in ad hoc wireless networks. Networks 42, 202–208 (2003)
Colagrosso, M.D.: Intelligent broadcasting in mobile ad hoc networks: three classes of adaptive protocols. EURASIP J. Wirel. Commun. Netw. 2007, 25 (2007)
Dai, F., Wu, J.: Performance analysis of broadcast protocols in ad hoc networks based on self-pruning. IEEE Trans. Parallel Distrib. Syst. 15, 1027–1040 (2004)
Guha, S., Khuller, S.: Approximation algorithms for connected dominating sets. Algorithmica 20, 374–387 (1998)
Tang, K.S., Kwong, S., Man, K.F.: Genetic algorithms: Concepts and applications (in engineering design). IEEE Transactions on Industrial Electronics 43, 519–534 (1996)
Ni, S.-Y., Tseng, Y.-C., Chen, Y.-S., Sheu, J.-P.: The broadcast storm problem in a mobile ad hoc network. In: Proceedings of the 5th Annual ACM/IEEE International Conference on Mobile Computing and Networking, MobiCom 1999, pp. 151–162. ACM, New York (1999)
Simon, V., Bérces, M., Varga, E., Bacsárdi, L.: Natural selection of message forwarding algorithms in multihop wireless networks. In: Proceedings of the 7th International Conference on Modeling and Optimization in Mobile, Ad Hoc, and Wireless Networks, WiOPT 2009, Piscataway, NJ, USA, pp. 16–22. IEEE Press (2009)
Varga, E.S., Wiandt, B., Benko, B.K., Simon, V.: Biologically Inspired Networking and Sensing: Algorithms and Architectures. IGI Books (2012)
Williams, B., Camp, T.: Comparison of broadcasting techniques for mobile ad hoc networks. In: Proceedings of the 3rd ACM International Symposium on Mobile Ad Hoc Networking & Computing, MobiHoc 2002, pp. 194–205. ACM, New York (2002)
Wu, J., Li, H.: On calculating connected dominating set for efficient routing in ad hoc wireless networks. In: Proceedings of the 3rd International Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications, DIALM 1999, pp. 7–14. ACM, New York (1999)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2012 IFIP International Federation for Information Processing
About this paper
Cite this paper
Wiandt, B., Simon, V., Varga, E.S. (2012). Efficient Multihop Broadcast with Distributed Protocol Evolution. In: Szabó, R., Vidács, A. (eds) Information and Communication Technologies. EUNICE 2012. Lecture Notes in Computer Science, vol 7479. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-32808-4_28
Download citation
DOI: https://doi.org/10.1007/978-3-642-32808-4_28
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-32807-7
Online ISBN: 978-3-642-32808-4
eBook Packages: Computer ScienceComputer Science (R0)