Nature knows best
1 like1,420 views
This document discusses using biological systems as inspiration for engineered network routing algorithms. It compares ant colony optimization (ACO) routing to nearest neighborhood tree (NNT) routing in different scenarios. Three scenarios are tested with static, failure-prone, and large networks. Results show ACO struggles in static networks but may perform better in more dynamic environments. Fungal colony routing processes like explore, exploit, and degenerate are also discussed and mapped to a simulation model. The document concludes more testing is needed to optimize parameters and investigate routing in more volatile network conditions.
Nature knows best
- 1. Nature Knows Best ? How can biological systems be exploited in engineered systems ?
- 2. People Cathy Scott c.scott@napier.ac.uk Husna Osman ho12@hw.ac.uk Ioannis Polyzos i.polyzos@gmail.com Michael Matscheko mm@pervasive.jku.at Petros Papadopoulos petros.papadopoulos@acm.org Sarah Clayton s.clayton@napier.ac.uk
- 3. Outline Introduction Aim Scenarios Network Settings Results Fungal Colonies Conclusion Questions ?
- 4. Introduction Routing strategies are highly important for computer networks performance. The emergence of mobile/sensor networks raised several novel problems mainly due to resource constrained devices. Among others biological systems with the same characteristics have been exploited in order to solve several discrete optimization problems such as : Ant Colonies Fungal Colonies
- 5. Aim This case study focus in : Comparing Ant Colony Optimization(ACO) with other discrete optimization algorithms like Nearest Neighborhood Tree(NNT). Exploring a recently introduced systems inspired by Fungal Colonies 3 scenarios have been used in order to measure : Efficiency , Scalability and Robustness
- 6. Scenarios Scenario 1 : Static Network Focus on the performance of NNT and ACO in a static network where there is no update frequency/proactive ants. Scenario 2 : Focus on the performance of NNT(no update) and ACO(with proactive ants) in a static network. Scenario 3: Focus on the performance of NNT(with update) and ACO(with proactive ants) in a dynamic environment (possible failures).
- 7. Network Settings Typical Network1 : Population : 50 Distance : 0.09 Futuristic Network 2 : Population: 400 Distance : 0.04
- 8. Routing Overhead 10 bug ? 8 configuration ? more tests ? 6 4 ACO FA ACO FA 1 2 ACO FA 10 NNT UR -- NNT UR 5 0 0 5 10 15 20 25 30 35 40 NNT UR 10
- 9. Delivery Ratio 1 0.8 0.6 NNT UR -- NNT UR 5 NNT UR 10 0.4 ACO FA 1 ACO FA 10 0.2 corresponds to ACO FA routing overhead 0 0 5 10 15discrepancy 25 20 30 35 40
- 10. Delivery Ratio (Failure t=20) 1 low delivery rates: 0.8 congestion reduce data load? 0.6 NNT UR 5 NNT UR 10 0.4 0.2 ACO FA 1 ACO FA 10 0 0 5 10 15 20 25 30 35 40
- 11. Delivery Ratio (400 nodes) 1 far too much data 0.8 for large network rerun with decreased data load or increased radio 0.6 data rate 0.4 0.2 NNT UR 5 NNT UR 10 ACO FA 1 0 ACO FA 10 0 5 10 15 20 25 30 35 40
- 12. Conclusions Ant algorithm struggles with (almost) static network scenarious Network congestion leads to low delivery ratio Future Work: Investigate situation in more dynamic networks Volatile environment (high node failure rates) Mobile nodes Optimization of parameters Longer simulation timespan
- 13. Fungi Colonies
- 14. Fungal Colonies Processes Transactions Explore (sparse branching) Exploit (dense branching) Degenerate
- 15. Processes Triggers Explore Fitness function (sparse branching) Exploit Data message (dense branching) Degenerate Energy < pdegenerate
- 16. Mappings SpeckSim Fungal Colony Energy Nutrients Data Mobile biomass Established route Structural biomass
- 17. Message Type Transmission type Data message Broadcast Explore message Broadcast Establish route message Unicast
- 18. Network Flow
- 19. Thank you Questions ?