NetLogo User Community Models

(back to the NetLogo User Community Models)

Download If clicking does not initiate a download, try right clicking or control clicking and choosing "Save" or "Download".(The run link is disabled for this model because it was made in a version prior to NetLogo 6.0, which NetLogo Web requires.)

## 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 [1] 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

General Description.
Patch variables that comprised the landscape were given attribute values such as elevation, attenuation for radio wave signals, and mobility for movement. Four different types of terrain were modelled (mountains, forest, urban, and lakes), randomly generated and diffused throughout the world, which wraps continuously in the horizontal and vertical planes. A breed of turtle (walkers) was then created to serve as the mobile radio nodes, and emulated humans with radios walking within a geographical region. Number of walkers, speed of their movement, as well as maximum radio propagation radius are variables that are able to be modified using sliders on the NetLogo interface tab. Additional visibility options are also available from an observer context, such as: Displaying propagation limits with the effects of attenuation, displaying line of sight from the perspective of each walker, and showing the label associated with each communication link between walkers/nodes.

Links.
As the walkers traverse slowly throughout the simulated world, communication links between these mobile nodes are either established or fail due to environmental conditions. Although mobile radio propagation is generally omnidirectional, an established communication pathway between two nodes is represented as a simple dashed line, or active link. To maintain an active link between two nodes, several conditions must be met: Both nodes must be within maximum propagation distance of their associated radio, line of sight must be confirmed, and attenuation must be acceptably low so the outstation node can receive the radio communication signal. Broken links between nodes can occur as a result of either an obstruction to the line of sight (such as a mountain) or due to accumulated attenuation reaching a value above 99%. Indication of a broken link is either by a red ‘X’ indicating the high feature obstructing radio communication or by a red dashed line to indicate excessive attenuation. Finally, inactive links are also possible and caused by two walkers being beyond the maximum propagation distance of a mobile radio carried by each walker. Each of the three link conditions, whether active, broken or inactive, coupled with node displacement over time, provide the dynamic network topology MANET requires.

Nodes.
The nodes used in this model represent mobile radios employed by humans that are moving across the observer viewing area. Nodes thus are able to both receive and transmit message traffic between other nodes within maximum propagation range. Nodes also store information that is used by message traffic to decide which path to follow in order to reach its ultimate destination: A routing table with probability values associated with other nodes, a tour model that contains the most recently updated latency information to other nodes, and similarly a tour model hops table contains the most recently updated latency information to nodes with one hop to destination node. Routing table probabilities are initialized to identical weighted values equal to 1/(number nodes – 1) and the tour model is initialized to a default value of 100ms.

Ant-Hoc-Logo: ACO Techniques.
Ants use pheromone to reinforce pathways to food sources, while natural evaporation causes the pheromone to become less potent over time. Ant-Hoc-Logo similarly uses artificial ants and pheromone/evaporation principles to update message routing tables and consequently direct message traffic to each message’s intended destination. There are two types of ants used in this hybrid MANET model: proactive and reactive ants. As their name implies, proactive ants are generated at regular intervals during the course of the simulation. Conversely, reactive ants are only generated immediately prior to sending a network message.

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.
When a backwards ant arrives at a node, it overwrites the latency time to its previous node (found in the tour-model table at each node), and reinforces the probability of the node’s routing traffic to the previous node by an increase of approximately 2%. The exact value is dependent on the number of radios in the network. Correspondingly, all other routing probabilities in the node’s routing table array are reduced proportionally to the reinforcement amount in order to maintain a summed routing-table probability equal to 1. Routing table probabilities have a minimum and maximum threshold of 5% and 50% respectively, so as to avoid saturation.

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.
Message traffic is generated in this model in order to test network effectiveness. If auto-network-test is turned on, automatically generated messages with a random source and destination node are created at periodic intervals, following a brief ‘network configuration period’ used by ants to initialize routing table and tour model values. Messages use the routing table at each node to decide which node to move to in order to best reach its destination. The routing table value with the highest probability is selected first and message transmission is attempted.

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
- Code examples/GIS/Intersecting Links Example
- Code examples/GIS/Many Regions Example
- Sound/Vision Cone Example
- Shape Animation example
- Sample Models/Networks/Preferential Attachment
- Code examples/GIS/Link-walking turtles
- IABM Textbook/Chapter 3/Heroes and Cowards

## CREDITS AND REFERENCES

[1] Bonabeau, E., Dorigo, M., & Theraulaz, G. (1999). Swarm Intelligence: From Natural to Artificial Systems. Oxford University Press.

[2] 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.

[3] Wilensky, U. (1999-2016). NetLogo model Library Examples.