Download the Nature Knows Best? Case Study Overview (PDF)

Download the Team Presentation (PDF)

Algorithms in Routing Sensor Networks (PDF)

'Fungi' by Ruth Falconer (PDF)

Nature Knows Best? Notes by Despina Davoudani (PDF)

Ant Colony Optimisation by Dr Bart Craenen and Prof. Emma Hart (PDF)

Led by Ruth Falconer, SIMBIOS Centre, University of Abertay and Emma Hart, Centre for Emergent Computing, Edinburgh Napier University

Future data communication networks show three emerging trends: increasing size of networks, increasing traffic volumes and dynamic network topologies. Efficient network management solutions are required that are scalable, can cope with large and increasing traffic volumes and provide decentralised and adaptive routing strategies that cope with the dynamics of the network topology. Routing strategies are an important aspect of network management as they have a significant influence on the overall network performance.

Participants will learn how existing biological systems have been exploited in engineered systems such as communication networks in order to determine the shortest path in a network. Determining the shortest path in a network is an important aspect of efficient network traffic management. In this case study the students will learn the underlying concepts relating to three different routing protocols: spanning tree, ant and fungal systems. These biological systems will be used as the basis of developing efficient and robust routing protocols and the success of each of the algorithms can be assessed under different scenarios.

Using a network simulator (SpeckSim) the students will have the opportunity to investigate an implementation of a spanning tree routing protocol. The participants will also have access to a basic implementation of an ant colony routing protocol that they can improve and adapt. Finally, the participants will implement a fungal based routing protocol informed by the robustness and resilience of real fungal networks. Using the simulator the effectiveness of each of the routing protocols can be assessed under different conditions:

• Static network
• Limited background traffic density
• Large radii for radio range

If time permits the scenarios can be increased in complexity and extended to test the effectiveness and robustness of each protocol for dynamic networks with various background traffic densities and radio ranges.

This case study will explore the possible use of bio inspired algorithms for data flow in wireless networked systems. The task will require research into existing exploitation of biological systems for wireless networks i.e. ant and immune systems and review the potential use of a fungal inspired communication protocol. Participants will learn about fungal systems and identify possible ways i.e. mappings between the biological and wireless system, that the resilience and robustness of the biological system can be transferred to wireless systems. If time permits participants can implement the protocol in the SpeckSim simulation environment and investigate:

• How fungal inspired algorithm compares with existing ant algorithm in determination of shortest path
• How robust the algorithm is to nodes dropping out of the network

We recommend that participants cover some basic background reading to familiarise themselves with the concepts utilised in the case-study before the summer school. Some suggestions for suitable reading are given below:

SpeckSim

During the case-study, we will make use of a free simulator developed by the SpeckNet project, called SpeckSim.

A guide to SpeckSim can be found here.

Spanning Trees (ST) In WSNs

• Distributed Algorithms for Constructing Approximate Minimum Spanning Trees in Wireless Sensor Networks’ by Khan M. et al. 2009 (PDF)
• ‘A Simple Randomized Scheme for Constructing Low-Weight k-Connected Spanning Subgraphs with Applications to Distributed Algorithms’ by Khan M. et al. 2005 (PDF)
• A Fast Distribution Approximation Algorithm for Minimum Spanning Trees’ by Khan M. et al. 2008 (PDF)
• Energy-Optimal Distributed Algorithms for Minimum Spanning Trees’ by Choi Y. et al. 2008 (PDF)

Ant Colony Algorithms

A general introduction to the concept of Ant Colony algorithms can be found in the following sources:

Dorigo M., Stuetzle T., Ant Colony Optimization, MIT Press, 2005

Dorigo M., Di Caro G., Gambardella L.M., "Ant Algorithms for Discrete Optimization" , Artificial Life, Vol. 5, N. 2, 1999

Dorigo M., Di Caro G., "The Ant Colony Optimization Meta-Heuristic", in Corne D., Dorigo M., Glover F., New Ideas in Optimization, McGraw-Hill, 1999

A great deal of additional information can be found in the official Ant Colony Optimization page

ACO Routing Algorithms

Details of an ant-colony algorithm (AntNET) that has been modified specifically to perform routing in telecommunications networks can be found here: 

• Ducatelle F., Di Caro G., Gambardella L.M., Using Ant Agents to Combine Reactive and Proactive Strategies for Routing in Mobile Ad Hoc Networks, International Journal on Computational Intelligence and Applications (IJCIA), Special Issue on Nature-Inspired Approaches to Networks and Telecommunications, Vol. 5, N. 2, June 2005
• Di Caro G., Ducatelle F., Gambardella L.M., AntHocNet: An Adaptive Nature-Inspired Algorithm for Routing in Mobile Ad Hoc Networks, European Transactions on Telecommunications, Special Issue on Self-organization in Mobile Networking, Vol. 16, N. 5, October 2005
• Di Caro G., Dorigo M., "AntNet: Distributed Stigmergetic Control for Communications Networks" (reprinted by permission from JAIR), Vivek, A Quarterly in Artificial Intelligence, Vol. 12(3-4), Pag. 2-37, 1999.
• Di Caro G., Dorigo M., "AntNet: Distributed Stigmergetic Control for Communications Networks", Journal of Artificial Intelligence Research (JAIR), Vol. 9, Pag. 317-365, 1998.

Fungal Colonies

Some background on fungal colony modelling (and its applications in computing) can be found below.

• R. Falconer, J. Bown. E. Hart and J. Timmis , A New Paradigm for SpeckNEts: Inspiration from Fungal Colonies. in Workshop on Pervasive Adaptive Systems, second IEEE International Conference on Self-Adaptive and Self-Organizing Systems Venice, Italy, October 20-24, 2008.
• Ruth E. Falconer, James L. Bown, Nia A. White & John W. Crawford (2007). Biomass Recycling: a key to efficient foraging; Oikos, 116 ( 9): 1558-1568.

You may like to look at some videos here:

Deadlock: A simulation of two fungi competing in a 3D soil structure. Due to the limitations on the physical architecture of soil (not shown) the movement of the fungi becomes deadlocked. Watch Video

Poro033: A simulation of two competing fungi on a 2D environment. Watch Video