;; Title: ANT-HOC-LOGO
;; By: Daniel J. Kucherhan, student 8097588
;; For: COMP5206, Fall 2016, Carleton University
;;
;; Description: This model emulates a series of mobile, ad-hoc, radio communication nodes
;; distributed in a randomly generated 2D outdoor world comprising of four types
;; of terrain with representational values. Ant Colony Optimization techniques are
;; used to route network messages by updating routing tables at each node, reinforcing optimal
;; pathways from source node to destination node.
;;
;; 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 (see below).
;;
;;
;; Code was also used from the following NetLogo Model Library examples:
;; -GIS: Line of Sight, Intersecting Links, Many Regions, Link-walking Turtles
;; -Vision Cone, Shape Animation, Preferential Attachment, Heroes and Cowards
;;
;; Programmers note: turn t-mode to ON to output troubleshooting information to the command window.


breed [walkers walker]
breed [markers marker]
breed [ants ant]
breed [messages message]
ants-own [source destination location hops tour-order tour-latency tour-attenuation]
walkers-own [routing-table trip-model trip-model-hops]
messages-own [mlocation mdestination mhops mlatency]
links-own [link-attenuation latency status]
patches-own [elevation attenuation mobility]
globals [counter broken-links active-links inactive-links message-count mdead-count marrival-count b total-mhops total-mlatency link-percentage overall-link-percentage lcounter]

  ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
  ;;;;;;;;;       TO SETUP       ;;;;;;;;;;;;
  ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

to setup
  clear-all
  set-default-shape markers "dot"
  set-default-shape ants "bug"
  ;; setup the terrain
  ask patches [ set elevation random 10000 ]
  repeat 2 [ diffuse elevation 0.75 ]                 ;;make terrain more graduated
  ask patches [
    set pcolor scale-color green elevation 1000 8000  ;;forested terrain represented by shades of green
    set attenuation 0.2                               ;;loss of signal propagation through forested areas
    set mobility 0.25                                 ;;moderate mobility through forested areas
    if elevation < 3400 and elevation > 3100
    [set pcolor (gray - 2)                            ;;urban areas represented by gray (city)
     set attenuation 2                                ;;great propagation loss through urban terrain
     set mobility 0.5]                                ;;enhanced mobility through urban areas
    if elevation < 3000
    [set pcolor (blue - 1)                            ;;low elevation represented by water (blue)
     set attenuation 0                                ;;no loss in signal propagation over water
     set mobility 0.1]                                ;;poor mobility through water
    if elevation > 7000
    [set pcolor white                                 ;;high elevation represented by whitecaps
     set attenuation 0                                ;;no loss in signal propagation over mountains
     set mobility 0.1]                                ;;poor mobility over mountains
    ]
  ;; setup the walkers
  create-walkers mobile-radios [
    set size 3.5
    setxy (one-of [-60 -50 -40 -30]) (random-ycor * 0.6)
    set color one-of [45 62 0 9.9]
    set heading 90
    set label who
    set label-color white
  ]
  ask walkers [
    setup-routing-tables
    setup-trip-models
  ]

  reset-ticks
end

  ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
  ;;;;;;;;;       TO GO          ;;;;;;;;;;;;
  ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

to go
  ;; get rid of all the old markers and links, reset variables
  ask markers [ die ]
  ;; reset all the link information
  set broken-links 0
  set active-links 0
  set inactive-links 0

  ;; move the walkers
  ask walkers [
   if movement? = true [
    if (random 20 < walker-speed) [
    rt random 10
    lt random 10
    fd mobility
    ]
    ]
  mark-propagation
  ]

  ;; send periodic ants through network to measure latency / attenuation between nodes
  ;; and normalize routing-table probabilities to prevent saturation
  if (counter = mobile-radios) [
    if auto-ant-check? = true [
      ant-check -1 -1
    ]
    if (auto-network-test? = true) and (ticks > mobile-radios * 20) [
      ask messages [ die ]
      repeat mobile-radios [ network-test ]
    ]
    normalize-routing-tables
    set counter 0]
  if (counter = (2 * mobile-radios)) [ set counter 0 ]

  ask ants [
     if (hops = count walkers) [        ;;if ant has maxed out its hops, then send ant back to origin
       if t-mode = true [          ;; t-mode is troubleshooting mode, used to output data in command window
         write who
         print " HAS REACHED ITS MAX HOPS!"
         print ""
       ]
       send-ant-backwards
     ]
     if location = destination [   ;;if ant has reached its random destination node, then send ant back to origin
       if t-mode = true [
         write who
         print " HAS REACHED ITS DESTINATION!"
         print ""
       ]
       send-ant-backwards
     ]
  ]

  update-trip-model-hops
  move-ants
  move-message            ;;this instance only used for directed messages
  update-output-window
  update-link-totals
  report-message-delivery ;;this instance only used for directed messages
  tick
  set counter (counter + 1)
end

  ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
  ;;;;;;       SETUP PROCEDURES     ;;;;;;;;;
  ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

to setup-routing-tables ;; walker procedure
 ;; This sets up the routing table at each network node (walker)
 ;; which is used by data packets and ants for probabilistic selection
 ;; of the subsequent link choice between nodes. Each entry in the routing table
 ;; represents the proability and the placement in the list represents the link
 ;; number in acending order (eg first entry's value of '0.4' represents a
 ;; 40% probability of a packet choosing [ link 0 1 ]). Probabilities are initially
 ;; normalized to 1/total number of nodes - 1.
 set routing-table []
 let destination-nodes []
 let i (count walkers)
 let temp-list []

 repeat i [set destination-nodes lput (precision (1 / (count walkers - 1)) 4) destination-nodes]
 set destination-nodes replace-item who destination-nodes 0
 repeat i [set routing-table lput destination-nodes routing-table]
 set routing-table replace-item who routing-table 0
 ;;tests
 ;;set temp-list (item (4) routing-table)
 ;;print temp-list
 ;;set temp-list replace-item 3 temp-list 99
 ;;set routing-table replace-item 4 routing-table temp-list
end

to setup-trip-models ;; walker procedure
 ;; This sets up the trip model at each network node (walker)
 ;; which is updated by ants and holds the average trip time
 ;; from this node to destination nodes. Each entry in the trip model
 ;; represents the average trip time to reach each destination and its associated variance
 ;; (eg first entry's value of '42' represents an average latency of 42ms
 ;; for a trip from source to node 0. Trip latencies are initially set to 100ms.
 set trip-model []
 set trip-model-hops []
 let y (count walkers) ;; The total number of possible destination nodes (including this node)
 repeat y [set trip-model lput 100 trip-model]
 set trip-model replace-item who trip-model "X"
 repeat y [set trip-model-hops lput 200 trip-model-hops]
 set trip-model-hops replace-item who trip-model-hops "X"
end


  ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
  ;;;;;;;;       GO PROCEDURES     ;;;;;;;;;;
  ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

to mark-propagation  ;; walker procedure
 ;;local variables
 let c color
 let dist 1
 let e1 0
 let last-heading heading
 let last-patch patch-here
 let attenuated-propagation maximum-propagation            ;;default value
 let total-attenuation 0                                   ;;counter for attenuation along a certain heading
 let mylist []                                             ;;create empty list
 repeat 360 [set mylist lput maximum-propagation mylist]   ;;fill list with initial maximum propagation value x 360 times

;; TOPOGRAPHY ATTENUATION OPTION
 if topography = true [                          ;;turn on/of topography related attenuation related to signal propagation
   set heading (heading + 1)                     ;;turns turtle around in 1 degree increments
   while [ heading != last-heading ] [           ;;while loop ends when turtle returns to original heading
    set total-attenuation 0                      ;;reset variable
     while [dist <= maximum-propagation] [
      let p patch-ahead dist
      if p != last-patch [
        set total-attenuation (total-attenuation + [attenuation] of p)  ;;cumulative sum of attenuation patch values along heading
      set last-patch p
      ]
     set dist (dist + 1)
     ]
    set dist 1                                                                           ;;reset dist variable
    if total-attenuation > attenuated-propagation [ set total-attenuation attenuated-propagation] ;;if negative value, make mylist entry zero
    set mylist replace-item heading mylist (attenuated-propagation - total-attenuation)  ;;save updated attenuation value in mylist
    set heading (heading + 1)                                                            ;;next heading
    ]
  ]

;; MAXIMUM PROPAGATION RADIUS OPTION
 if show-max-propagation = true [                ;;turn on/off max possible propagation
   set heading (heading + 1)                     ;;turns turtle around in 1 degree increments
   while [ heading != last-heading ] [           ;;while loop ends when turtle returns to original heading
    ask patch-at-heading-and-distance heading (item (heading) mylist) [   ;;ask the patch at rotating heading and at propagation distance
    sprout-markers 1 [ set color c ]]                                 ;;to sprout a small colour marker
   set heading (heading + 1)                     ;;next heading
  ]
   ;; ask patches in-cone maximum-propagation 360 [  ;;show maximum omni-directional propagation when no attenuation
 ]

;; VIEW-LINE-OF-SIGHT OPTION
if show-line-of-sight = true [                   ;;turn on/off to visualize line-of-sight of each node
 ;; iterate through all the patches within MAXIMUM-PROPAGATION
 ;; starting at the patch directly ahead
 set heading (heading + 1)                       ;;turns turtle around in 1 degree increments to verify line-of-sight ability
 while [ heading != last-heading ] [             ;;while loop ends when turtle returns to original heading
   while [dist <= item (heading) mylist] [
     let p patch-ahead dist
     ;; if we are looking diagonally across
     ;; a patch it is possible we'll get the
     ;; same patch for distance x and x + 1
     ;; but we don't need to check again.
     if p != last-patch [
     ;; find the angle between the turtle's position
     ;; and the top of the patch.
      let e2 atan dist ((elevation + 2000) - (([elevation] of p) + 2000))
      ;; if that angle is less than the angle toward the
      ;; last visible patch there is no direct line from the turtle
      ;; to the patch in question that is not obstructed by another
      ;; patch. Elevation has been augmented 2000 on both in-station
      ;; and out-station to represent an elevated radiating element.
      if e1 < e2
         [ ask p [ sprout-markers 1 [ set color c ] ]
         set e1 e2 ]
      set last-patch p
      ]
    set dist (dist + 1)
   ]
   set heading (heading + 1)
   set e1 0
   set dist 1
 ]
]

;; SHOW-LINKS OPTION
 if show-links = true [                          ;;turn on/off visibility of links between nodes
   ask links [
     set color black
     set thickness 0
     set shape "dashed"
     ifelse show-link-label = true [ set label self ] [ set label "" ]
   ]
   create-links-with other walkers ;;in-radius (attenuated-propagation - total-attenuation) ;;Make links with walkers within propagation radius
   ask links [
     set status "ACTIVE"                           ;;set all newly created links to ACTIVE status
     show-link
     set link-attenuation int((calculate-link-attenuation end1 end2) * 9)
     set latency int(link-length)

     let result clear-line-of-sight end1 end2      ;;check for line-of-sight between link endpoints
     if result = false [                           ;;if there is no line of sight between the two endpoints of the link, hide link
       hide-link
       set status "BROKEN"                         ;;Status to BROKEN and zeroize attenuation & latency
       set link-attenuation 0
       set latency 0
     ]
     if link-attenuation > 99 [                 ;;if attenuation is over 99%...no signal, change link to red, set latency to zero
          set color red
          set status "BROKEN"
          set latency 99
     ]
     if link-length > (attenuated-propagation - total-attenuation) [
       set status "INACTIVE"
       hide-link
       set latency 0
       set link-attenuation 0
       ;;die
     ]
    ]
   ]
;; update-link-totals
end


to ant-check [ s d ];; observer / go / network-test procedure
;; This procedure is called to generate artificial ants to find pathways through the network
if any? links [
  ifelse s = -1 and d = -1 [
    create-ants mobile-radios [ ;; red ants are called by go/observer (PROACTIVE ANTS)
      set color red
      set location one-of walkers
      set source location
      set destination one-of walkers
      while [source = destination]  [ set destination one-of walkers ]
      set tour-order []
      set tour-attenuation []
      set tour-latency []
      set tour-order lput location tour-order
      set size 3
      move-to location
    ]
  ]
  [ create-ants 1 [  ;; blue ants are called prior to sending a message (REACTIVE ANTS)
      set color blue
      set location s
      set source location
      set destination d
      set tour-order []
      set tour-attenuation []
      set tour-latency []
      set tour-order lput location tour-order
      set size 3
      move-to location
    ]
  ]
]
end

to move-ants  ;; go procedure
;; Send ants randomly around network to collect latency / attenuation of their tour
 let move-to-new-location true
 let link-check 0
 let link-latency 0
 let no-links-available 0
 let new-location 0
   if (any? ants) [ ask ants with [color = red] [   ;; ant procedure
      set new-location (choose-new-location location)   ;;choose new location...
      while [([link-with new-location] of location = nobody) or ([[status] of link-with new-location] of location = "INACTIVE") or ([[status] of link-with new-location] of location = "BROKEN")] [
       ifelse ([link-with new-location] of location = nobody) [
         if t-mode = true [
           write "Ant "
           write who
           write " FOUND NOBODY AT "
           print location
           print ""
         ]
         ask location [ set trip-model replace-item ([who] of new-location) trip-model 9999 ]
         set new-location (choose-new-location location )
       ]
       [if ([[status] of link-with new-location] of location = "INACTIVE") or ([[status] of link-with new-location] of location = "BROKEN") [
         if t-mode = true [
           write "ANT"
           write who
           print " HAS FOUND AN INACTIVE/BROKEN LINK"
         ]
         ask location [   ;;update node trip-model with inactive link value
            set trip-model replace-item ([who] of new-location) trip-model ([latency] of link-with new-location)
          ]
         set no-links-available (no-links-available + 1)     ;;counter in case of ant being stuck at a node with no links...
         if no-links-available >= 5 [
           die
           if t-mode = true [
             write "ANT"
             write who
             print " HAS DIED OF LONLINESS!!"
           ]
           set no-links-available 0
           set mdead-count (mdead-count + 1)
         ]
        ]
       ]
      set new-location (choose-new-location location )
      ]  ;; end while loop
        if ([[status] of link-with new-location] of location = "ACTIVE") [
         face new-location                                            ;;make ant face new location if there are any links available
         ask [link-with new-location] of location [   ;; link procedure
          set link-check link-attenuation
          set latency int(link-length)
          set link-latency latency
          set thickness 0.5                                           ;;set line thickness to indicate ant movement across link
         ]
         set tour-attenuation lput link-check tour-attenuation         ;;update ant tour-attenuation list value
         set tour-latency lput link-latency tour-latency               ;;update ant tour-latency list value
         move-to new-location                                          ;;move ant to new location across link
         set location new-location                                     ;;update ant's location
         set tour-order lput location tour-order                       ;;update ant's tour-order list value
         set hops (hops + 1)                                           ;;add one hop to ant hops total
        ]
        if t-mode = true [
          print (word who " " tour-order "LATENCY: " tour-latency "ATTENUATION: " tour-attenuation)
          print ""
        ]
     ]
  ]
end

to send-ant-backwards ;; ant procedure
;; The purpose of the backwards ants are to update the trip models and probability tables for each node (walker)
;; thereby adjusting the routing probabilities and the latency estimates used to direct network message traffic
  let z (length tour-order - 1)
  let node-1 0
  let node-2 0
  let node-3 0
  let whoz-1 0
  let whoz-2 0
  let whoz-3 0
  let latc (length tour-latency - 1)
  let latcz-1 0
  let latcz-2 0
  let latcz-3 0

  let g 0
  let f (1 / (50 * (count walkers - 1)))               ;;incremental pheromone value for routing table entries
  let ftotal 0
  let tempdestnodelist 0
  let temprt 0
  let minrt (f * 2.5 * (count walkers - 1))              ;;min value for the routing table (5%)
  let maxrt (f * 25 * (count walkers - 1))             ;;max value for the routing table (50%)
  let newer-better false

  while [ z > 0 ] [
   set node-1 (item (z - 1) tour-order)
   set whoz-1 ([who] of item z tour-order)
   set latcz-1 (item latc tour-latency)

   if z > 1 [ ;;if the ant's tour-order has more than one entry, it has at least 1x TWO hops
     set node-2 (item (z - 2) tour-order)
     set whoz-2 ([who] of item (z - 1) tour-order)
     set latcz-2 (item (latc - 1) tour-latency)
   ]

    if z > 2 [ ;;if the ant's tour-order has more than two entries, it has at least 1x THREE hops
     set node-3 (item (z - 3) tour-order)
     set whoz-3 ([who] of item (z - 2) tour-order)
     set latcz-3 (item (latc - 2) tour-latency)
   ]

;;  update trip-model for multi-hop neighbours

if (z > 2) [ ;; if the ant's tour-order has more than two entries, it has at least 1x THREE hops
  ask (node-3) [ ;; walker procedure (nodes)
     if whoz-1 != who [
        if t-mode = true [
           print (word "Current TRIP MODEL HOPS" node-3)
           print (word (item whoz-1 trip-model-hops) " is the current value for " whoz-1)
           print (word latcz-1 " + " latcz-2 " + " latcz-3 " = " (latcz-1 + latcz-2 + latcz-3))
        ]
        ifelse (latcz-1 + latcz-2 + latcz-3) < item whoz-1 trip-model-hops [ set newer-better true ] [ set newer-better false ]
        if t-mode = true [
           print newer-better
           print ""
        ]
        set trip-model-hops replace-item whoz-1 trip-model-hops (latcz-1 + latcz-2 + latcz-3)  ;;update time to get to multi-hop destination

        ;; update routing-table with backward-ant THREE-HOP neighbour values due to evaporation and reinforcement
        set g 0
        set tempdestnodelist (item whoz-1 routing-table)
        while [ g < count walkers ] [
          set temprt item g tempdestnodelist
          if (g != who) and (temprt > minrt) and (item whoz-3 tempdestnodelist < maxrt) [
             set tempdestnodelist replace-item g tempdestnodelist (precision (temprt - f) 4)  ;; EVAPORATION OF ANT PHEROMONE
              set ftotal (ftotal + f)
          ]
          set g (g + 1)
        ]
        set temprt item whoz-3 tempdestnodelist
        set tempdestnodelist replace-item whoz-3 tempdestnodelist (precision (temprt + ftotal) 4)  ;; REINFORCEMENT OF ANT PHEROMONE
        set ftotal 0
        set routing-table replace-item whoz-1 routing-table tempdestnodelist
     ]
  ]
]


if (z > 1) [ ;; if the ant's tour-order has more than one entry, it has at least 1x TWO hop
  ask (node-2) [ ;; walker procedure (nodes)
     if whoz-1 != who [
        if t-mode = true [
           print (word "Current TRIP MODEL HOPS" node-2)
           print (word (item whoz-1 trip-model-hops) " is the current value for " whoz-1)
           print (word latcz-1 " + " latcz-2 " = " (latcz-1 + latcz-2))
        ]
        ifelse (latcz-1 + latcz-2) < item whoz-1 trip-model-hops [ set newer-better true ] [ set newer-better false ]
        if t-mode = true [
           print newer-better
           print ""
        ]
        set trip-model-hops replace-item whoz-1 trip-model-hops (latcz-1 + latcz-2)  ;;update time to get to multi-hop destination

        ;; update routing-table with backward-ant TWO-HOP neighbour values due to evaporation and reinforcement
        set g 0
        set tempdestnodelist (item whoz-1 routing-table)
        while [ g < count walkers ] [
          set temprt item g tempdestnodelist
          if (g != who) and (temprt > minrt) and (item whoz-2 tempdestnodelist < maxrt) [
             set tempdestnodelist replace-item g tempdestnodelist (precision (temprt - f) 4)  ;; EVAPORATION OF ANT PHEROMONE
              set ftotal (ftotal + f)
          ]
          set g (g + 1)
        ]
        set temprt item whoz-2 tempdestnodelist
        set tempdestnodelist replace-item whoz-2 tempdestnodelist (precision (temprt + ftotal) 4)  ;; REINFORCEMENT OF ANT PHEROMONE
        set ftotal 0
        set routing-table replace-item whoz-1 routing-table tempdestnodelist
     ]
  ]
]

  ask (node-1) [ ;; walker procedure (nodes)
  ;; update trip-model for direct neighbours
    set trip-model replace-item whoz-1 trip-model (latcz-1)

    ;; update routing-table with backward-ant NEAREST NEIGHBOUR values due to evaporation and reinforcement
    set g 0
    set tempdestnodelist (item whoz-1 routing-table)
     while [ g < count walkers ] [
        set temprt item g tempdestnodelist
        if (g != who) and (temprt > minrt) and (item whoz-1 tempdestnodelist < maxrt) [
           set tempdestnodelist replace-item g tempdestnodelist (precision (temprt - f) 4)  ;; EVAPORATION OF ANT PHEROMONE
           set ftotal (ftotal + f)
        ]
     set g (g + 1)
     ]
     set temprt item whoz-1 tempdestnodelist
     set tempdestnodelist replace-item whoz-1 tempdestnodelist (precision (temprt + ftotal) 4)  ;; REINFORCEMENT OF ANT PHEROMONE
     set ftotal 0
     set routing-table replace-item whoz-1 routing-table tempdestnodelist
     ;; chose next node using stack (tour-order item)
     set z (z - 1)
     set latc (latc - 1)
    ]
  ]
die
end

to update-trip-model-hops
;; This procedure increments each trip-model-hops value over time to a maximum value of 200ms.
;; It is used to incrementally return the table to its default setting
  ask walkers [ ;; walker procedure (nodes)
    let v ((length trip-model-hops) - 1)
    let temprth 0
    while [ v > -1][
     if (v != who) and (item v trip-model-hops < 199) [
       set temprth (item v trip-model-hops + 2)  ;;increment trip-model-hops value due to lack of multi-hop traffic
       set trip-model-hops replace-item v trip-model-hops temprth
     ]
     set v v - 1
    ]

    ;; if a node has no active links, then all trip-model-hops are reset to their maximum values
    set v ((length trip-model-hops) - 1)
    let q 0
    while [ v > -1 ] [
      if (v != who) and (item v trip-model = 0) [  ;;count number of inactive links
        set q q + 1
      ]
    set v v - 1
    ]
    if (q = ((length trip-model-hops) - 1)) [
      set v ((length trip-model-hops) - 1)
      while [ v > -1 ] [
        if (v != who) [
          set trip-model-hops replace-item v trip-model-hops 200
        ]
      set v v - 1
      ]
    ]
  ]
end

to send_message ;; observer procedure
;; Generate observer-directed messages through network
  let a 0

  if (Message_Path = "From 0 to 1")      [ set a 0  set b 1 ]
  if (Message_Path = "From 0 to 2")      [ set a 0  set b 2 ]
  if (Message_Path = "From 0 to 3")      [ set a 0  set b 3 ]
  if (Message_Path = "From 0 to 4")      [ set a 0  set b 4 ]
  if (Message_Path = "From 1 to 2")      [ set a 1  set b 2 ]
  if (Message_Path = "From 1 to 3")      [ set a 1  set b 3 ]
  if (Message_Path = "From 1 to 4")      [ set a 1  set b 4 ]
  if (Message_Path = "From 2 to 3")      [ set a 2  set b 3 ]
  if (Message_Path = "From 2 to 4")      [ set a 2  set b 4 ]
  if (Message_Path = "From 3 to 4")      [ set a 3  set b 4 ]

  create-messages 1 [
    set color green
    set shape "arrow"
    set size 4
    set label who
    set label-color white
    set mlatency 0
    set mlocation (walker a)
    move-to mlocation
    set message-count (message-count + 1)
    set mdestination (walker b)
    ]

  create-messages 1 [
    set color red
    set shape "target"
    set size 4
    set label who
    set label red
    move-to (walker b)
    ]
end


to move-message
;; Send observer-directed messages through network and calculate message hops (mhops) and message latency (mlatency)
 let delay 0
  if any? messages [
    ask messages [  ;; message procedure
     ifelse color = green [
      let new-mlocation one-of [link-neighbors] of mlocation
      face new-mlocation
      if ([[status] of link-with new-mlocation] of mlocation = "ACTIVE") [
       ;; change thickness of link that was passed over &
       ;; update delay so it can be added to the message latency
       ask [link-with new-mlocation] of mlocation [ set thickness 0.5  set delay int(link-length)]
       move-to new-mlocation
       set mlocation new-mlocation
       set mhops (mhops + 1)
       set mlatency (mlatency + delay)             ;;add link delay to message latency
       ]
      ]
      [ move-to walker b ]                         ;;update "Target" red message icon
    ]
  ]
end

to report-message-delivery
;; This procedure is used to report message delivery
  ask messages [  ;; message procedure
      if mlocation = mdestination [
         if mlatency > 0 [
           if t-mode = true [
             print (word who " DELIVERED!  LATENCY:" mlatency "ms     #HOPS:" mhops)
             print ""
           ]

          set marrival-count (marrival-count + 1)
          set total-mlatency (total-mlatency + mlatency)
          set total-mhops (total-mhops + mhops)
          die
         ]
      ]
  ]
end

to update-output-window  ;; Update output window
clear-output
let i 0
let j 1

if show-output-window = true [
output-print "LINK / LATENCY / ATTENUTATION / STATUS"   ;;OUTPUT window header
;;The following double while loop prints all active links
;;in the output window, eliminating redundant links and non-existant links
 while [ i != (count walkers) ] [
   while [ j != (count walkers) and (i < j)] [
     ifelse link i j != nobody [
       output-write link i j                         ;;Outputs link name
       output-type "  "
       output-write ([ latency ] of link i j)
       output-type "ms   "
       output-write ([ link-attenuation ] of link i j)
       output-type "%     "
       output-print ([ status ] of link i j)
     ]
     [ output-type " (link"
       output-write i
       output-write j
       output-print ")    -      --    INACTIVE" ]

   set j (j + 1)
   ]
  set i (i + 1)
  set j (i + 1)
 ]
output-print ""

if show-trip-models = true [
;; This procdure outputs Trip Model info to the OUTPUT WINDOW
  output-print "LATENCY TRIP-MODEL (DIRECTLY LINKED NEIGHBOURS)"
  ;; prints the trip model average times to travel between nodes
  set i 0
  while [ i != (count walkers) ] [
    output-print (walker i)
    output-write ([trip-model] of walker i)
    output-print ""
    set i (i + 1)
  ]
  output-print ""

  output-print "LATENCY TRIP-MODEL-HOPS (SINGLE-HOP NEIGHBOURS)"
  ;; prints the trip model average times to travel between nodes
  set i 0
  while [ i != (count walkers) ] [
    output-print (walker i)
    output-write ([trip-model-hops] of walker i)
    output-print ""
    set i (i + 1)
  ]
  output-print ""
]

if show-routing-table = true [
;; This procdure outputs Routing Table info to the OUTPUT WINDOW
   output-print "ROUTING-TABLE PROBABILITIES"
   ;; prints the trip model average times to travel between nodes
   set i 0
   while [ i != (count walkers) ] [
    output-print (walker i)
    output-print ([routing-table] of walker i)
    ;;output-print sum [routing-table] of walker i
    set i (i + 1)
   ]
]
]
end


to update-link-totals
;; This procedure updates the Link Status totals
   set active-links (count links with [status = "ACTIVE"])
   set broken-links (count links with [status = "BROKEN"])
   let k mobile-radios
   let m 0
   while [k > 0] [ set m (m + k - 1)  set k (k - 1) ]  ;;count total possible links given # mobile-radios
   set inactive-links (m - active-links - broken-links)
   set link-percentage (100 * active-links / (active-links + broken-links + inactive-links))
   set lcounter (lcounter + 1)
   set overall-link-percentage (link-percentage + overall-link-percentage)
end

to normalize-routing-tables
;; This procedure is called regularly to incrementally bring each node's routing table value
;; closer to the inital / default setting of 1 /(count walkers - 1)
  ask walkers [  ;; walker procedure
    let changevalue (1 / 800 * (count walkers - 1))
    let topvalueplace count walkers
    let topvalue 0
    let changedvalue 0
    let tmpdistnodes 0
    let r ((length routing-table) - 1)
    let rtvalue 0
    let u ((length routing-table) - 1)

    while [(u >= 0)] [ ;; and (u != who)] [
     if u != who [
       set tmpdistnodes (item u routing-table)
       if t-mode = true [
         print (word who " is now being normalized, at routing-table index: " u)
         print ""
       ]
       while [(r >= 0)] [
         if r != who [
           set rtvalue item r tmpdistnodes
           ;;set changevalue abs (rtvalue - (1 / (count walkers - 1)))
           ifelse (rtvalue > (1 / (count walkers - 1))) [
             if topvalue < rtvalue [
               set topvalueplace r
               set topvalue rtvalue
             ]
           ]
           [ if (rtvalue < (1 / (count walkers - 1))) [
               set tmpdistnodes replace-item r tmpdistnodes (precision (rtvalue + changevalue) 4)
               set changedvalue (changedvalue + changevalue)
             ]
           ]
         ]
      set r (r - 1)
      ]
      if topvalueplace != (count walkers) [
        set rtvalue (item topvalueplace tmpdistnodes)
        set tmpdistnodes replace-item topvalueplace tmpdistnodes (precision (rtvalue - changedvalue) 4)
        if t-mode = true [
          print (word "Changed value is" changedvalue ". Change value is" changevalue ". These are the values:" tmpdistnodes " which sums to " (sum tmpdistnodes))
          print ""
        ]
        set changedvalue (changedvalue - changedvalue)
        set routing-table replace-item u routing-table tmpdistnodes
        set topvalueplace count walkers
      ]
      set changedvalue 0
      set r ((length routing-table) - 1)
      ]
     set u (u - 1)
     ]
   ]
end

  ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
  ;;;;;      NETWORK PROCEDURES     ;;;;;;;;;
  ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

to network-test ;; observer/go procedure
;;generates message traffic in order to test network performance
let tmpsource (walker 0)
let tmpdestination (walker 1)
;; generate random message
  create-messages 1 [
    set color white
    set shape "arrow"
    set size 4
    set label who
    set label-color white
    set mlatency 0
    set mlocation (one-of walkers)
     set mdestination (one-of walkers)
    while [mdestination = mlocation][
      set mdestination (one-of walkers)
    ]
    set tmpsource mlocation
    set tmpdestination mdestination
    move-to mlocation
    set message-count (message-count + 1)
    if t-mode = true [
      print (word "NETWORK TEST " who)
      print mlocation
      print mdestination
    ]
  ]

;; call upon reactive ants (BLUE in color) to find route to destination
if reactive-ant = true [
  ant-check tmpsource tmpdestination
  ask ants with [color = blue][ move-blue-ants ]
]

;; choose new message location using routing table probability values
let delay 0
let new-mlocation 0
let previous-mlocation [nobody]
let attempts 0
   ask messages [

     while [mdestination != mlocation] [
       set new-mlocation (choose-new-mlocation attempts)
       set attempts (attempts + 1)
       while [([link-with new-mlocation] of mlocation = nobody) or (new-mlocation = one-of previous-mlocation) or ([[status] of link-with new-mlocation] of mlocation = "INACTIVE") or ([[status] of link-with new-mlocation] of mlocation = "BROKEN")][
        if t-mode = true [
          print (word "Message " who " encountered an inactive/broken link at " mlocation " to " new-mlocation ". Attempts:" attempts)
          print ""
        ]
         if (attempts > ((count walkers) + 10)) [  ;;if max attempts reached, likely cause is all probabilities are of equal value
           if t-mode = true [
            print (word "Message " who " reached maximum number of attempts and DIED!  Attempts:" attempts)
             print ""
           ]
           set mdead-count (mdead-count + 1)
           die
         ]
         set new-mlocation (choose-new-mlocation attempts)
         set attempts (attempts + 1)
         set delay (delay + 5)
     ]
     if t-mode = true [
       print (word "Message " who " at mlocation " mlocation " found a new mlocation: " new-mlocation)
       print ""
     ]
     set attempts 0

    ;; change thickness of link that was passed over &
    ;; update delay so it can be added to the message latency
     ask [link-with new-mlocation] of mlocation [ set thickness 0.5  set delay int(link-length)]
     set previous-mlocation lput mlocation previous-mlocation
     set mlocation new-mlocation

     set mhops (mhops + 1)
     set mlatency (mlatency + delay)             ;;add link delay to message latency
     if mlatency >= (20 * maximum-propagation) [
           print (word "Message " who " reached maximum latency of " mlatency " and DIED.")
           print ""
           set mdead-count (mdead-count + 1)
           die
         ]
     if mhops >= (count walkers) [
           print (word "Message " who " reached maximum number of hops " mhops " and DIED.")
           print ""
           set mdead-count (mdead-count + 1)
           die
         ]
     ]
   ]
   report-message-delivery
end

to move-blue-ants  ;; network-test procedure
;; Send blue ants (REACTIVE ANTS) in response to message being sent
 let move-to-new-location true
 let link-check 0
 let link-latency 0
 let no-links-available 0
 let new-location 0
if (any? ants) [
  while [(hops < count walkers) and (location != destination)][
    set new-location (choose-new-location location)   ;;choose new location...
       while [([link-with new-location] of location = nobody) or ([[status] of link-with new-location] of location = "INACTIVE") or ([[status] of link-with new-location] of location = "BROKEN")] [
        ifelse ([link-with new-location] of location = nobody) [
         if t-mode = true [
           print (word "Ant " who " FOUND NOBODY AT " location)
           print ""
         ]
         ask location [ set trip-model replace-item ([who] of new-location) trip-model 9999 ]
         set new-location (choose-new-location location )
        ]
       [ if ([[status] of link-with new-location] of location = "INACTIVE") or ([[status] of link-with new-location] of location = "BROKEN") [
          if t-mode = true [
           write "ANT"
           write who
           print " HAS FOUND AN INACTIVE/BROKEN LINK"
          ]
          ask location [   ;;update node trip-model with inactive link value
          set trip-model replace-item ([who] of new-location) trip-model ([latency] of link-with new-location)
           ]
          set no-links-available (no-links-available + 1)     ;;counter in case of ant being stuck at a node with no links...
          if no-links-available >= 5 [
           die
           if t-mode = true [
             write "ANT"
             write who
             print " HAS DIED OF LONLINESS!!"
           ]
           set no-links-available 0
           set mdead-count (mdead-count + 1)
         ]
        ]
       set new-location (choose-new-location location )
       ] ;; end else statement
      ]  ;; end while loop
        if ([[status] of link-with new-location] of location = "ACTIVE") [
         face new-location                                            ;;make ant face new location if there are any links available
         ask [link-with new-location] of location [   ;; link procedure
          set link-check link-attenuation
          set latency int(link-length)
          set link-latency latency
          set thickness 0.5                                           ;;set line thickness to indicate ant movement across link
         ]
         set tour-attenuation lput link-check tour-attenuation         ;;update ant tour-attenuation list value
         set tour-latency lput link-latency tour-latency               ;;update ant tour-latency list value
         move-to new-location                                          ;;move ant to new location across link
         set location new-location                                     ;;update ant's location
         set tour-order lput location tour-order                       ;;update ant's tour-order list value
         set hops (hops + 1)                                           ;;add one hop to ant hops total
        ]
        if t-mode = true [
          print (word who " " tour-order "   LATENCY: " tour-latency "   ATTENUATION: " tour-attenuation)
          print ""
        ]
  ]
  send-ant-backwards
]
end


  ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
  ;;;::       SUB-PROCEDURES       ;;;;;;;;;;
  ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

to-report clear-line-of-sight [t1 t2]  ;;link procedure
  let p1 patch ([xcor] of t1) ([ycor] of t1)          ;;patch @ end1 of link
  let p2 patch ([xcor] of t2) ([ycor] of t2)          ;;patch @ end2 of link
  let pe1 (([elevation] of p1) + 2000)                ;;elevation patch1 +2000 for elevated radiating element
  let pe2 (([elevation] of p2) + 2000)                ;;elevation patch2 +2000 for elevated radiating element
  let peavg ((pe1 + pe2) / 2)                         ;;average elevation between end1 and end2 of link
  let d1 link-length                                  ;;link-length
  let h1 link-heading                                 ;;link-heading from end1 to end2
  let blocked false
  ;; verify each patch elevation along link from end2 back to end1, using d1/h1 as vector sequentially to each patch.
  ;; if any of the patch elevations along link are greater than peavg, there is no direct line-of-sight btw endpoints.
  while [(d1 > 0) and (blocked = false)] [
     let p? patch (([pxcor] of p1) + (d1 * cos (90 - h1))) (([pycor] of p1) + (d1 * sin (90 - h1)))       ;;patch coordinates along link-heading @ distance d1
     let pe? ([elevation] of p?)                                                           ;;elevation of patch along link-heading
     if (pe? > peavg) [                                                                    ;;if the elevation along link is higher than average of link endpoints
       ask p? [
         if (count markers-here < 1) [                                                     ;;if a marker already exists then skip
           sprout-markers 1 [ set color red  set shape "x" set size 2 ]                    ;;indicate peak blocking link with red X
         ]
        ]
       set blocked true
       report false
      ]
   set d1 (d1 - 1)
   ]
  report true
end

to-report choose-new-location [curloc]  ;;ant procedure
  let cloc curloc                    ;;current location of ant
  let whocloc ([who] of curloc)      ;;who number of current location of ant
  let nloc 0                         ;;selected new location for ant
  let destin destination             ;;destination of ant
  let probtablevalue 0
  ;;TODO: verify that the nloc != nodes previously visited...?

   let nlocmax 0                     ;;max new location attempts
   let randomfloat random-float 1    ;;new random float value between 0 and 1
  ask cloc [ ;;walker procedure
    ;; roulette wheel with routing-table values
    let s -1
    let tempdestlist (item [who] of destin routing-table) ;;get routing-table values
    let max-check (length tempdestlist - 1)  ;;stop counter in case there are no link neighbors
    ;; The following will pick a new location based upon the probabilities in routing-table of the current walker
    while [(probtablevalue < randomfloat) and (s < max-check)] [
      set s (s + 1)
      set probtablevalue ((item s tempdestlist) + probtablevalue)
      if t-mode = true [
        print (word who " " s " " probtablevalue " " randomfloat)
        print ""
      ]
    ]
    set nlocmax (nlocmax + 1)
    set nloc (walker s)
    if t-mode = true [
      print (word who " has a new location picked:" nloc)
      print ""
    ]
   ]
   if nlocmax = (2 * (count walkers)) [    ;;if there are no new locations to link to
     set nloc nobody
     if t-mode = true [
       print "NOBODY FOUND!"
     ]
     report nloc
     die
   ]
report nloc
end

to-report choose-new-mlocation [tries]  ;;message procedure
  let t 0                            ;;used to check duplicate probability values
  let numberduplicateprob 0
  let nloc 0                         ;;selected new location for message
  let destin mdestination            ;;destination of message
  let probtablevalue 0
  let r 0
  let all-probabilities-equal false  ;;assume that probabilities are not all equal
  let rchanged false

  ask mlocation [ ;;walker procedure, at the message's current location (mlocation)
    ;; choose highest routing-table value for destination node
    let tempdestlist (item ([who] of destin) routing-table) ;;get destination node's routing-table values
    let orderedtempdestlist sort-by > tempdestlist
    if tries >= count walkers - 1 [
      set tries (0)
    ]
    let bestprobtablevalue (item (t + tries) orderedtempdestlist) ;;picks the next highest value according to the number of tries
    while [(t < length tempdestlist - 1)] [
      if bestprobtablevalue = item t orderedtempdestlist [
        set numberduplicateprob (numberduplicateprob + 1)
      ]
      set t (t + 1)
    ]
    if bestprobtablevalue = (1 / (count walkers - 1)) [
      set all-probabilities-equal true
      set r tries
    ]

    let s -1
    let max-check (length tempdestlist - 1)  ;;stop counter in case there are no link neighbors
    ;; The following will pick a new location based upon the probabilities in routing-table of the current walker
    while [(s < max-check) and (all-probabilities-equal = false) and (rchanged = false)] [
      set s (s + 1)
      set probtablevalue (item s tempdestlist)
      if (probtablevalue != 0) and (probtablevalue = bestprobtablevalue) [
           set rchanged true
           set r s
         if numberduplicateprob > 1 and tries > 1 [
           set rchanged false
         ]
      ]
      if t-mode = true [
        print (word who " " r " Best prob table value: " bestprobtablevalue ".  Prob table value: " probtablevalue ". Duplicates: " numberduplicateprob ". Tries: " tries)
        print ""
      ]
    ]
    set nloc (walker r)
    if t-mode = true [
      print (word who " has a new location picked: " nloc)
      print ""
    ]
   if (tries = 3) or (all-probabilities-equal) [ ;; if all else fails, select lowest latency valued link and follow it!
     let tmptrip-model trip-model
     let besttmptrip-model 100
     let d 0
     let c 0
     while [(d < length tmptrip-model - 1)] [
       if (d != who) and (item d tmptrip-model != 0) and (besttmptrip-model > (item d tmptrip-model)) [
         set besttmptrip-model (item d tmptrip-model)
         set c d
       ]
       set d d + 1
     ]
     set nloc (walker c)
   ]
 ]
report nloc
end


to-report calculate-link-attenuation [l1 l2] ;;link procedure
  let la1 patch ([xcor] of l1) ([ycor] of l1)          ;;patch @ end1 of link
  let la2 patch ([xcor] of l2) ([ycor] of l2)          ;;patch @ end2 of link
  let ld link-length
  let lh link-heading                                  ;;link-heading from end1 to end2
  let link-att-sum 0                                   ;;link attenuation sum counter
  ;; calculate the sum of all patch-based attenuation along link path
  while [ld > 0] [
    let la? patch (([pxcor] of la1) + (ld * cos (90 - lh))) (([pycor] of la1) + (ld * sin (90 - lh)))  ;;patch coordinates along link-heading @ distance ld
    set link-att-sum (link-att-sum + [attenuation] of la?)
    set ld (ld - 1)
  ]
  report link-att-sum
end

to-report occurrences [x the-list]
  report reduce
    [ifelse-value (?2 = x) [?1 + 1] [?1]] (fput 0 the-list)
end

; Public Domain:
; To the extent possible under law, Uri Wilensky has waived all
; copyright and related or neighboring rights to this model.
@#$#@#$#@
GRAPHICS-WINDOW
164
10
879
516
70
47
5.0
1
12
1
1
1
0
1
1
1
-70
70
-47
47
1
1
1
ticks
30.0

BUTTON
0
80
131
113
NIL
setup
NIL
1
T
OBSERVER
NIL
NIL
NIL
NIL
1

BUTTON
1
135
132
168
GO
go
T
1
T
OBSERVER
NIL
NIL
NIL
NIL
0

SLIDER
2
43
144
76
maximum-propagation
maximum-propagation
1.0
60.0
50
1.0
1
NIL
HORIZONTAL

SLIDER
2
10
106
43
mobile-radios
mobile-radios
2
20
5
1
1
NIL
HORIZONTAL

SWITCH
0
483
120
516
topography
topography
0
1
-1000

SWITCH
0
380
162
413
show-line-of-sight
show-line-of-sight
1
1
-1000

TEXTBOX
4
462
155
490
PROPAGATION EFFECTS:
11
0.0
1

SWITCH
0
342
162
375
show-max-propagation
show-max-propagation
1
1
-1000

SWITCH
1028
527
1190
560
show-links
show-links
0
1
-1000

TEXTBOX
4
320
154
338
VISIBILITY OPTIONS:
11
0.0
1

SWITCH
0
418
162
451
show-link-label
show-link-label
1
1
-1000

TEXTBOX
3
214
153
232
WALKER OPTIONS:
11
0.0
1

SWITCH
0
235
119
268
movement?
movement?
0
1
-1000

SLIDER
0
274
119
307
walker-speed
walker-speed
0.5
5
1.5
0.5
1
NIL
HORIZONTAL

CHOOSER
254
541
346
586
Message_Path
Message_Path
"From 0 to 1" "From 0 to 2" "From 0 to 3" "From 0 to 4" "From 1 to 2" "From 1 to 3" "From 1 to 4" "From 2 to 3" "From 2 to 4" "From 3 to 4"
3

BUTTON
346
541
401
586
SEND
send_message
NIL
1
T
OBSERVER
NIL
NIL
NIL
NIL
1

SWITCH
0
172
124
205
auto-ant-check?
auto-ant-check?
0
1
-1000

TEXTBOX
638
40
873
109
LEGEND:\nThin dashed black line = possible link\nThick dashed black line = ant/message traffic\nThin dashed red line = broken link (attenuation)\nRed X = broken link (line of sight)\n\n
11
0.0
0

SWITCH
718
548
880
581
show-trip-models
show-trip-models
0
1
-1000

SWITCH
718
581
880
614
show-routing-table
show-routing-table
0
1
-1000

TEXTBOX
306
17
546
45
Broken Link = high attenuation, no line-of-sight
11
14.0
1

TEXTBOX
560
16
804
44
Inactive Link = beyond propagation distance
11
0.0
1

OUTPUT
879
10
1340
616
9

MONITOR
1139
48
1196
93
Active
active-links
17
1
11

MONITOR
1195
48
1252
93
Broken
broken-links
17
1
11

MONITOR
1251
48
1309
93
Inactive
inactive-links
17
1
11

TEXTBOX
1178
28
1328
46
LINK TOTALS:
14
0.0
1

SWITCH
777
613
880
646
t-mode
t-mode
1
1
-1000

TEXTBOX
266
525
416
543
SEND DIRECTED MESSAGE:
11
0.0
1

TEXTBOX
4
524
154
542
GENERATE MESSAGE TEST:
11
0.0
1

BUTTON
141
546
219
579
Test Network
network-test
NIL
1
T
OBSERVER
NIL
NIL
NIL
NIL
1

MONITOR
792
109
874
154
NIL
message-count
17
1
11

SWITCH
0
546
141
579
auto-network-test?
auto-network-test?
0
1
-1000

MONITOR
792
153
874
198
Delivered Msgs
marrival-count
17
1
11

MONITOR
792
197
874
242
Failed Msgs
mdead-count
17
1
11

MONITOR
735
154
792
199
Msg %
(word (precision (100 * (marrival-count / message-count)) 1) \"%\")
17
1
11

MONITOR
735
198
792
243
Link %
(word precision (link-percentage) 2 \"%\")
17
1
11

MONITOR
805
250
871
295
Avg Hops
precision (total-mhops / marrival-count) 3
17
1
11

MONITOR
789
300
871
345
Avg Latency
precision (total-mlatency / marrival-count) 2
17
1
11

SWITCH
718
516
880
549
show-output-window
show-output-window
0
1
-1000

MONITOR
723
250
800
295
Avg Link %
(word precision (overall-link-percentage / lcounter) 2 \"%\")
17
1
11

SWITCH
0
579
124
612
reactive-ant
reactive-ant
0
1
-1000

@#$#@#$#@
## 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.
@#$#@#$#@
default
true
0
Polygon -7500403 true true 150 5 40 250 150 205 260 250

airplane
true
0
Polygon -7500403 true true 150 0 135 15 120 60 120 105 15 165 15 195 120 180 135 240 105 270 120 285 150 270 180 285 210 270 165 240 180 180 285 195 285 165 180 105 180 60 165 15

arrow
true
0
Polygon -7500403 true true 150 0 0 150 105 150 105 293 195 293 195 150 300 150

box
false
0
Polygon -7500403 true true 150 285 285 225 285 75 150 135
Polygon -7500403 true true 150 135 15 75 150 15 285 75
Polygon -7500403 true true 15 75 15 225 150 285 150 135
Line -16777216 false 150 285 150 135
Line -16777216 false 150 135 15 75
Line -16777216 false 150 135 285 75

bug
true
0
Circle -7500403 true true 96 182 108
Circle -7500403 true true 110 127 80
Circle -7500403 true true 110 75 80
Line -7500403 true 150 100 80 30
Line -7500403 true 150 100 220 30

butterfly
true
0
Polygon -7500403 true true 150 165 209 199 225 225 225 255 195 270 165 255 150 240
Polygon -7500403 true true 150 165 89 198 75 225 75 255 105 270 135 255 150 240
Polygon -7500403 true true 139 148 100 105 55 90 25 90 10 105 10 135 25 180 40 195 85 194 139 163
Polygon -7500403 true true 162 150 200 105 245 90 275 90 290 105 290 135 275 180 260 195 215 195 162 165
Polygon -16777216 true false 150 255 135 225 120 150 135 120 150 105 165 120 180 150 165 225
Circle -16777216 true false 135 90 30
Line -16777216 false 150 105 195 60
Line -16777216 false 150 105 105 60

car
false
0
Polygon -7500403 true true 300 180 279 164 261 144 240 135 226 132 213 106 203 84 185 63 159 50 135 50 75 60 0 150 0 165 0 225 300 225 300 180
Circle -16777216 true false 180 180 90
Circle -16777216 true false 30 180 90
Polygon -16777216 true false 162 80 132 78 134 135 209 135 194 105 189 96 180 89
Circle -7500403 true true 47 195 58
Circle -7500403 true true 195 195 58

circle
false
0
Circle -7500403 true true 0 0 300

circle 2
false
0
Circle -7500403 true true 0 0 300
Circle -16777216 true false 30 30 240

cow
false
0
Polygon -7500403 true true 200 193 197 249 179 249 177 196 166 187 140 189 93 191 78 179 72 211 49 209 48 181 37 149 25 120 25 89 45 72 103 84 179 75 198 76 252 64 272 81 293 103 285 121 255 121 242 118 224 167
Polygon -7500403 true true 73 210 86 251 62 249 48 208
Polygon -7500403 true true 25 114 16 195 9 204 23 213 25 200 39 123

cylinder
false
0
Circle -7500403 true true 0 0 300

dot
false
0
Circle -7500403 true true 90 90 120

face happy
false
0
Circle -7500403 true true 8 8 285
Circle -16777216 true false 60 75 60
Circle -16777216 true false 180 75 60
Polygon -16777216 true false 150 255 90 239 62 213 47 191 67 179 90 203 109 218 150 225 192 218 210 203 227 181 251 194 236 217 212 240

face neutral
false
0
Circle -7500403 true true 8 7 285
Circle -16777216 true false 60 75 60
Circle -16777216 true false 180 75 60
Rectangle -16777216 true false 60 195 240 225

face sad
false
0
Circle -7500403 true true 8 8 285
Circle -16777216 true false 60 75 60
Circle -16777216 true false 180 75 60
Polygon -16777216 true false 150 168 90 184 62 210 47 232 67 244 90 220 109 205 150 198 192 205 210 220 227 242 251 229 236 206 212 183

fish
false
0
Polygon -1 true false 44 131 21 87 15 86 0 120 15 150 0 180 13 214 20 212 45 166
Polygon -1 true false 135 195 119 235 95 218 76 210 46 204 60 165
Polygon -1 true false 75 45 83 77 71 103 86 114 166 78 135 60
Polygon -7500403 true true 30 136 151 77 226 81 280 119 292 146 292 160 287 170 270 195 195 210 151 212 30 166
Circle -16777216 true false 215 106 30

flag
false
0
Rectangle -7500403 true true 60 15 75 300
Polygon -7500403 true true 90 150 270 90 90 30
Line -7500403 true 75 135 90 135
Line -7500403 true 75 45 90 45

flower
false
0
Polygon -10899396 true false 135 120 165 165 180 210 180 240 150 300 165 300 195 240 195 195 165 135
Circle -7500403 true true 85 132 38
Circle -7500403 true true 130 147 38
Circle -7500403 true true 192 85 38
Circle -7500403 true true 85 40 38
Circle -7500403 true true 177 40 38
Circle -7500403 true true 177 132 38
Circle -7500403 true true 70 85 38
Circle -7500403 true true 130 25 38
Circle -7500403 true true 96 51 108
Circle -16777216 true false 113 68 74
Polygon -10899396 true false 189 233 219 188 249 173 279 188 234 218
Polygon -10899396 true false 180 255 150 210 105 210 75 240 135 240

house
false
0
Rectangle -7500403 true true 45 120 255 285
Rectangle -16777216 true false 120 210 180 285
Polygon -7500403 true true 15 120 150 15 285 120
Line -16777216 false 30 120 270 120

leaf
false
0
Polygon -7500403 true true 150 210 135 195 120 210 60 210 30 195 60 180 60 165 15 135 30 120 15 105 40 104 45 90 60 90 90 105 105 120 120 120 105 60 120 60 135 30 150 15 165 30 180 60 195 60 180 120 195 120 210 105 240 90 255 90 263 104 285 105 270 120 285 135 240 165 240 180 270 195 240 210 180 210 165 195
Polygon -7500403 true true 135 195 135 240 120 255 105 255 105 285 135 285 165 240 165 195

line
true
0
Line -7500403 true 150 0 150 300

line half
true
0
Line -7500403 true 150 0 150 150

pentagon
false
0
Polygon -7500403 true true 150 15 15 120 60 285 240 285 285 120

person
false
0
Circle -7500403 true true 110 5 80
Polygon -7500403 true true 105 90 120 195 90 285 105 300 135 300 150 225 165 300 195 300 210 285 180 195 195 90
Rectangle -7500403 true true 127 79 172 94
Polygon -7500403 true true 195 90 240 150 225 180 165 105
Polygon -7500403 true true 105 90 60 150 75 180 135 105

plant
false
0
Rectangle -7500403 true true 135 90 165 300
Polygon -7500403 true true 135 255 90 210 45 195 75 255 135 285
Polygon -7500403 true true 165 255 210 210 255 195 225 255 165 285
Polygon -7500403 true true 135 180 90 135 45 120 75 180 135 210
Polygon -7500403 true true 165 180 165 210 225 180 255 120 210 135
Polygon -7500403 true true 135 105 90 60 45 45 75 105 135 135
Polygon -7500403 true true 165 105 165 135 225 105 255 45 210 60
Polygon -7500403 true true 135 90 120 45 150 15 180 45 165 90

square
false
0
Rectangle -7500403 true true 30 30 270 270

square 2
false
0
Rectangle -7500403 true true 30 30 270 270
Rectangle -16777216 true false 60 60 240 240

star
false
0
Polygon -7500403 true true 151 1 185 108 298 108 207 175 242 282 151 216 59 282 94 175 3 108 116 108

target
false
0
Circle -7500403 true true 0 0 300
Circle -16777216 true false 30 30 240
Circle -7500403 true true 60 60 180
Circle -16777216 true false 90 90 120
Circle -7500403 true true 120 120 60

tree
false
0
Circle -7500403 true true 118 3 94
Rectangle -6459832 true false 120 195 180 300
Circle -7500403 true true 65 21 108
Circle -7500403 true true 116 41 127
Circle -7500403 true true 45 90 120
Circle -7500403 true true 104 74 152

triangle
false
0
Polygon -7500403 true true 150 30 15 255 285 255

triangle 2
false
0
Polygon -7500403 true true 150 30 15 255 285 255
Polygon -16777216 true false 151 99 225 223 75 224

truck
false
0
Rectangle -7500403 true true 4 45 195 187
Polygon -7500403 true true 296 193 296 150 259 134 244 104 208 104 207 194
Rectangle -1 true false 195 60 195 105
Polygon -16777216 true false 238 112 252 141 219 141 218 112
Circle -16777216 true false 234 174 42
Rectangle -7500403 true true 181 185 214 194
Circle -16777216 true false 144 174 42
Circle -16777216 true false 24 174 42
Circle -7500403 false true 24 174 42
Circle -7500403 false true 144 174 42
Circle -7500403 false true 234 174 42

turtle
true
0
Polygon -10899396 true false 215 204 240 233 246 254 228 266 215 252 193 210
Polygon -10899396 true false 195 90 225 75 245 75 260 89 269 108 261 124 240 105 225 105 210 105
Polygon -10899396 true false 105 90 75 75 55 75 40 89 31 108 39 124 60 105 75 105 90 105
Polygon -10899396 true false 132 85 134 64 107 51 108 17 150 2 192 18 192 52 169 65 172 87
Polygon -10899396 true false 85 204 60 233 54 254 72 266 85 252 107 210
Polygon -7500403 true true 119 75 179 75 209 101 224 135 220 225 175 261 128 261 81 224 74 135 88 99

wheel
false
0
Circle -7500403 true true 3 3 294
Circle -16777216 true false 30 30 240
Line -7500403 true 150 285 150 15
Line -7500403 true 15 150 285 150
Circle -7500403 true true 120 120 60
Line -7500403 true 216 40 79 269
Line -7500403 true 40 84 269 221
Line -7500403 true 40 216 269 79
Line -7500403 true 84 40 221 269

x
false
0
Polygon -7500403 true true 270 75 225 30 30 225 75 270
Polygon -7500403 true true 30 75 75 30 270 225 225 270

@#$#@#$#@
NetLogo 5.3.1
@#$#@#$#@
@#$#@#$#@
@#$#@#$#@
@#$#@#$#@
@#$#@#$#@
default
0.0
-0.2 0 0.0 1.0
0.0 1 1.0 0.0
0.2 0 0.0 1.0
link direction
true
0
Line -7500403 true 150 150 90 180
Line -7500403 true 150 150 210 180

dashed
0.0
-0.2 0 0.0 1.0
0.0 1 4.0 4.0
0.2 0 0.0 1.0
link direction
true
0
Line -7500403 true 150 150 90 180
Line -7500403 true 150 150 210 180

dashed1
0.0
-0.2 0 0.0 1.0
0.0 1 4.0 4.0 2.0 2.0
0.2 0 0.0 1.0
link direction
true
0
Line -7500403 true 150 150 90 180
Line -7500403 true 150 150 210 180

dashed2
0.0
-0.2 0 0.0 1.0
0.0 1 2.0 2.0
0.2 0 0.0 1.0
link direction
true
0
Line -7500403 true 150 150 90 180
Line -7500403 true 150 150 210 180

@#$#@#$#@
0
@#$#@#$#@