NetLogo User Community Models
by Dan Kucherhan (Submitted: 01/24/2018)
## WHAT IS IT?
Natural system dynamics that have evolved over the course of millions of years tend to be optimized within their environmental context for a singular, profound objective: survival. As is the case with behaviours exhibited by ants, arguably one of the most industrious of creatures on the planet, Ant Colony Optimization (ACO) methods employed by these tiny, independent actors allow the colony to proactively find food, recruit other ants to help forage, and adopt other behavioural patterns in order to ensure that all duties of the colony are being fulfilled. Inspired by nature, algorithms developed by  have employed ACO based metaheuristics that optimize functions used in man-made systems, such as telecommunication network routing arrays.
Mobile Ad-hoc Networking (MANET) is a term used to describe a series of moveable information system nodes with temporal and spatial distribution, able to receive and transmit data, which share a collective network. MANET differs from centrally-managed, static-network infrastructures in that routing rules are locally controlled instances that dynamically change due to the geographic displacement of each network node and communication between two nodes is variable according to radio wave propagation factors.
Ant-Hoc-Logo is a model created to simulate MANET and uses an ACO metaheuristic to probabilistically route dynamic data traffic. Ant-Hoc-Logo was developed using NetLogo, an agent-based model (ABM) software environment, that permits the simulation and modelling of a variety of complex and dynamic constructs and comes with an extensive model library.
## HOW IT WORKS
Ant-Hoc-Logo: ACO Techniques.
As communication nodes move through their model environment and the network configuration accordingly adapts, proactive ants are generated automatically (using the auto-ant-check? selector switch) within the network at regular intervals and randomly assigned a source and destination node. The number and frequency of proactive ants generated correspond to the number of nodes within the network. One reactive ant is sent immediately prior to a message being relayed from a specific source to a specific destination, and the reactive ant has an identical source / destination as the instantiating message. Each ant generated chooses each of its subsequent nodes on route to their intended destination. The node choice is performed probabilistically according to a roulette wheel scheme represented by the probability values found in the current node’s routing table. The values contained within each node’s routing table corresponds to the probability that the ant should be routed to each other node.
Both proactive and reactive ants record several parameters on their journey from source node to destination node, including: the number and the name of each node visited, latency time and attenuation percentage between nodes visited. While ants move toward their respective destination, their journey can be visualized on the observer’s viewing window as small red ant figures, and links are widened to show an ant’s passage between nodes. Upon arrival to their destination, every ant generates a backwards ant that is provided all the tour parameters obtained by the original ant. This backwards and then returns sequentially backtracks towards the source node of the original ant performs updates to node routing tables it traverses using the information previously obtained.
The probability reinforcement and reduction of routing table values are modified by each individual backward ant based upon the forward ant’s experience gained during its tour. In essence, this updating procedure lies at the heart of the ACO metaheuristic that efficiently routes traffic through the MANET topology. Not only are direct neighbour routing table values adjusted during the backward ant’s updating procedures, but multi-hop neighbour values are also reinforced. Double and triple hop neighbours receive a similar reinforcement/evaporation to routing table values. When a backwards ant finally arrives at its source, it updates the source node’s routing table and tour model, and having fulfilled its purpose, is then deleted from the network.
Simulated Message Traffic.
Should the link be broken or inactive, then transmission to the next highest node probability is attempted, and so forth. Should no active links be available at a node, the message reaches a maximum number of attempts to be transmitted, and expires, registering as a failed message attempt. Messages that have hopped to multiple nodes and have attained the maximum allowed number of hops will also expire. All successfully delivered messages expire upon arrival at their intended destination. Failed as well as successful messages are recorded and displayed on the corresponding observer output window.
The observer also has the option to send directed messages at any time during the simulation of the model, which begin at a desired source node and sent to a desired destination node over the network.
## HOW TO USE IT
Adjust the MOBILE-RADIOS slider to select the desired number of nodes and the MAXIMIMUM-PROPAGATION radius which determines the maximum distance that a communication link can be established between two nodes. To prepare the model, select SETUP and your desired number of nodes will appear on the left side of the viewing area.
Selecting GO will then cause the nodes to begin moving randomly towards the right side of the viewing area, but movement can be modified by turning MOVEMENT? on or off, as well as changing the relative overall WALKER-SPEED graduated scale.
AUTO-ANT-CHECK? switch allows you to control whether ants, equal to the number of mobile-radios selected, move from node to node in order to gather data regarding the network topology, latency, and attenuation. This information collected is used to update routing tables when ants have reached their destination node.
Three Visibility Options are available to the user: SHOW-MAX-PROPAGATION sprouts markers at a maximal propagation distance from each node, SHOW-LINE-OF-SIGHT sprouts markers at topography features visible by each node within its maximum propagation radius, and SHOW-LINK-LABEL displays the link names in the observer window beside each link.
The TOPOLOGY propagation effects switch allows attenuation due to patch attenuation values to be included or excluded from the simulation.
Under the Generate Message Test heading there are two options, AUTO-NETWORK-TEST? creates messages (and REACTIVE-ANTs if selected) at regular intervals each message with a random source and destination node seeking to find their way through the network using the routing-table values at each node. A selectable TEST-NETWORK button can also initiate a volley of messages at any time during the simulation.
Sending directed messages (where the user selects the source and destination nodes) is possible for a selection of nodes and can be generated by selecting an option and pressing the SEND button.
There are also visibility options for the Output Window on the far right side of the observer panel that will several system status registers, such as: Overall link connectivity status (only available to the observer), Trip Model values at each node for single and double hops which represent latency between nodes, Routing Table probabilities at each node used to direct message and ant traffic through the network. Finally, there is also a T-MODE (Troubleshooting Mode) which enables a detailed feed of runtime information to be displayed in the Command Window for programming purposes.
## THINGS TO NOTICE
When all nodes are within communication range, link % is relatively high. However, as the nodes move further apart from one another and reach maximum propagation range, links become broken or inactive, causing link % to drop.
Ants begin to analyse the network in the early stages and require an initialization phase to update nodal routing table values to represent the actual network topology. Individual nodes only hold information regarding neighbouring nodes (up to three hops away) which makes them 'locally aware' since their information is updated by the ants on their backward path. You can observe ants travelling from node to node (red ant figures) and links temporarily get thicker to represent the travel pathway of ants.
Following the ant initialization phase (about 20x the number of mobile-radio nodes worth of ticks), messages will begin to be sent if AUTO-NETWORK-TEST is selected. Message success rate will be displayed along with the number of accumulated failed and delivered messages over time. The Reactive Ant is a very important pre-message pathway check and will increase the likelihood of successful message delivery despite reduced link %.
As nodes move further and further apart, communication links become increasingly strained. At times, a node may have no communication links, which could cause messages with this node as its intended source and/or destination to fail. Increasing maximum-propagation and/or removing topology effects may aleviate some of the poor propagation.
## THINGS TO TRY
Try adjusting the maximum-propagation and number of mobile-radios to see how long it takes for communication links to degrade significantly with the dynamic network topology.
Change the walker-speed or stop movement entirely to see how relative geographic stability increases successful message delivery, as ants update nodes to optimum routing table values for message traffic.
Try sending directed messages at various times throughout the simulation.
How does turning off AUTO-ANT-CHECK? and REATIVE-ANT cause message traffic to be directed? If routing table values at each node are not updated by the ants, messages have equal probability of being directed to adjacent nodes. How does this affect the message delivery rate? Turn the ants back on and see how the message delivery rate changes.
## EXTENDING THE MODEL
Possible enhancements to this model include: simplification of the code, as there are likely efficiencies to be gained through reduction of programming lines, improved representational display of routing table information, and adding a resizing function to adjust the size of the movement space for the walkers. Many modern radio-frequency mobile communication devices additionally employ automatic channel selection to optimize transmission/reception quality and throughput. Modifying Ant-Hoc-Logo to allow ACO algorithms to select optimal channels would be a future improvement to this model. Lastly, adding a feature to be able to adjust the number of nodes in a neighbourhood subset may further enhance this model’s performance.
## LIBRARY MODELS USED
- Code examples/GIS/Line of Sight
## CREDITS AND REFERENCES
 Bonabeau, E., Dorigo, M., & Theraulaz, G. (1999). Swarm Intelligence: From Natural to Artificial Systems. Oxford University Press.
 Di Caro, G., Ducatelle, F., & Gambardella, L.M. (2004). AntHocNet: An Ant-Based Hybrid Routing Algorithm for Mobile Ad Hoc Networks. PPSN, LNCS 3242, pp. 461-170, Springer-Verlag.
 Wilensky, U. (1999-2016). NetLogo model Library Examples.
(back to the NetLogo User Community Models)