Master thesis Implementing and simulating the cross-entropy ant system Jonathan Brugge July 1, 2010 ii Contents Preface vii Introduction and contributions ix I The Cross Entropy Ant System 1 1 Background 3 2 The Cross Entropy Ant System 5 2.1 Foraging ants . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 2.2 CEAS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 2.2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 6 2.2.2 Implementation . . . . . . . . . . . . . . . . . . . . . . . . 7 2.2.3 Avoiding converging to a local optimum . . . . . . . . . . 7 2.2.4 Cycles in paths . . . . . . . . . . . . . . . . . . . . . . . . 8 2.2.5 Extensions . . . . . . . . . . . . . . . . . . . . . . . . . . 8 II Porting CEAS to ns-3 11 3 Introduction 13 iii 4 About ns-3 15 4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 4.2 Features . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 5 CEAS in ns-3 - the architecture 19 5.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 5.2 Temperature table . . . . . . . . . . . . . . . . . . . . . . . . . . 20 5.3 Pheromone table . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 5.4 Ant packets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 5.4.1 Neighbour discovery packets. . . . . . . . . . . . . . . . . 24 5.5 Routing protocol . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 5.5.1 Before sending the ants . . . . . . . . . . . . . . . . . . . 25 5.5.2 Leaving node A . . . . . . . . . . . . . . . . . . . . . . . . 25 5.5.3 Passing through node B . . . . . . . . . . . . . . . . . . . 26 5.5.4 Arriving at node C . . . . . . . . . . . . . . . . . . . . . . 27 5.5.5 The way back . . . . . . . . . . . . . . . . . . . . . . . . . 27 5.6 Infrastructure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 6 Validation 29 7 Experience with ns-3 33 7.1 Comparison with ns-2 . . . . . . . . . . . . . . . . . . . . . . . . 34 7.1.1 Abstraction level . . . . . . . . . . . . . . . . . . . . . . . 34 7.1.2 Usability and adaptability . . . . . . . . . . . . . . . . . . 35 7.1.3 Built-in components and models . . . . . . . . . . . . . . 36 7.1.4 Experiment setup, control and analysis . . . . . . . . . . 36 7.1.5 Development status . . . . . . . . . . . . . . . . . . . . . 37 iv 7.1.6 Efficiency . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 III Simulation and optimization 39 8 Simulation 41 8.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 8.2 The scenario . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 8.2.1 The layout . . . . . . . . . . . . . . . . . . . . . . . . . . 41 8.3 Basic results. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 8.4 Load-sensitive cost functions . . . . . . . . . . . . . . . . . . . . 45 8.5 Preplanning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 8.6 Packet format improvements . . . . . . . . . . . . . . . . . . . . 51 9 Conclusion 55 9.1 The original plan . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 9.2 What actually happened . . . . . . . . . . . . . . . . . . . . . . . 55 9.3 Future work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 A Simulation parameters 59 B Paper 61 C Presentation TM8105 69 D Research project 75 v vi Preface This report describes the work I have done as my graduation project at NTNU in Trondheim. The work was performed within the Telematics department of the university under supervision of Poul Heegaard and Laurent Paquereau. At my home university in Enschede, Pieter-Tjerk de Boer was my first supervisor, with Geert Heijenk taking the role of second supervisor. I would like to thank them for their help with this project. Pieter-Tjerk always spots the even smallest issues, whether they are mistakes in some formula in the research project or layout problems deeply hidden in the bibliography. I enjoyed the mix of discussing those issues and discussing everything else - from university politics to bicycle holidays. Thanks for that! InNorway,PoulandLaurenttookover-andkeptdoingthat,evenwhenresults took longer than expected to arrive and graphs managed to deviate from the expected results in a surprising number of different ways. Extra meetings to find the last bugs and an Easter holiday spent writing a paper with Laurent - my project definitely took more of your time than the standard NTNU thesis. Thanks for all your help along the way! Jonathan Brugge June 2010 vii viii Introduction and contributions Forthisthesisproject,IhaveworkedontheCross-EntropyAntSystem(CEAS), aroutingprotocoldevelopedatNTNU.CEAShadbeenimplementedinnetwork simulator ns-2 [1]. At the start of the project, the plan was to Implement CEAS in ns-3 • Verify the implementation against the existing ns-2 implementation • Come up with improvements to CEAS for use in environments with a • relatively high rate of changes in the network topology Simulate the improvements to verify them • Ns-3isanewsimulator,writtenbythedevelopersofns-2,butotherwiseincom- patible. During the project, it became clear that porting to ns-3 was more work than originallyexpected. Thus,arelativelybigpartofthisreportisdedicatedtothe work done to implement CEAS in ns-3. The last part is about the additional scenariosthathavebeensimulatedwiththens-3implementationandthespecific improvements that have been made. Where applicable, parameters used for the simulation have been included in thisreport. Anearlier study[2] foundthatmanystudiesin thefield ofnetwork simulation lack information about the parameters, making it difficult to verify the results. The source code used for all simulations is available on request. TogetherwithLaurentandPoul,Ihavewrittenapaperabouttheexperienceof porting CEAS from ns-2 to ns-3. The paper has been accepted at a conference and is included in this report as appendix B. Appendix C contains part of the presentationaboutns-3. IpreparedandpresenteditaspartofacourseforPhD students at NTNU, organized by Poul. ix Structure This thesis starts with an introduction to CEAS, including existing extensions to the system. It is followed by an introduction to ns-3 in chapter 3 and 4. Chapter 5 describes how CEAS has been implemented and how it fits in ns-3. The implementation is then validated against the existing ns-2 implementation in chapter 6. Some remarks about ns-3, derived from the experience of imple- menting CEAS in it, form chapter 7. Improvements to CEAS to make it more usable in congested networks are dis- cussed in chapter 8, which also includes simulations of such networks. Conclu- sions follow in chapter 9, after which some appendices are included. Contributions The original goal of the project was to improve CEAS by making it more suit- able for highly dynamic networks. Others have worked on different projects to improve CEAS: the most important examples are the addition of a system called elite selection, described in [3], and the subpath extension, introduced in [4]. Both extensions are described in section 2.2.5 of this report. Though some work has been done to adapt CEAS for use in such networks, an importantpartofthisthesisprojectistheexperiencegainedfromimplementing theprotocolinns-3. Becausetheprotocolhadbeenimplementedinns-2before, it was possible to compare the two implementations and with that, the two simulators. As many researchers will have to decide whether to use ns-2 or ns-3 for future projects, the comparison can be useful to others. I will present the paper Laurent, Poul and I wrote about that decision at SIMUL 2010, a conference about simulations in August 2010 in Nice. x