PROTOCOL

Basic flocking algorithm

SUMMARY

Motes periodically record their identifiers, coordinates and time stamps in their local memory and broadcast this information to their neighbors. Motes receiving this message will record this information if they are within the flock radius (r) and the information is new before rebroadcasting the message.

Motes constantly check whether they are moving in a flock based on their records, flock size (n) and flocking duration (k).

OPERATION

• Click the Setup button to generate a network based on communication distance and network size.
• Click the Go! button to run the algorithm.

NOTICE

• Motes appear in red when they detect that they are moving in a flock.
• Use the MoteLabel list to change the labels to mote id.
• Use the n slider to control the flock size.
• Use the k slider to control the flocking duration.
• Use the r slider to control the flock radius.
• Use the CorrelatedRandomWalk switch to control the direction of mote movement. If this switch is turned on, a mote will change its heading based on a normal distribution with standard deviation of 45 degrees. If this switch is turned off, the mote will change its heading based on a uniform distribution.
• Use the LevyFlight switch to control how fast a mote can move. If this switch is turned on, the distance between current position and next position is determined based on a normal distribution. If this switch is turned off, the mote moves at a constant speed.
• A motes m table can be displayed by clicking on it. Table entries will appear in the output list to the right of the simulation.

TRY

• What happens when a smaller netsize value is used?
• What happens if the communication distance is much smaller than the flock radius? Try this by adjusting the c and r sliders.
• Try selecting GG or RNG from the NetworkStructure drop-down box to change the network shape to a Gabriel Graph or Relative Neighborhood Graph. Does this have an effect on the amount of flocks detected?
• Try running the algorithm slowly to get a better idea of how the algorithm runs. Change this by adjusting the speed slider.
• For easy demonstration of flocks, try setting the netsize and n to small values.

LINK TO BOOK

Protocol 6.6

CREDITS

Code designed by Matt Duckham. Additional coding by Alan Both and Hai Ruo Xie.

LICENSE

Copyright 2011, 2012 Matt Duckham

This program is free software: you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, either version 3 of the License, or (at your option) any later version.

This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License http://www.gnu.org/licenses/ for more details.

Protocol 6.6

The formal specification procedure used for all the protocols on this site is based on the standard distributed systems approach of Nicola Santoro (see Santoro, N. Design and Analysis of Distributed Algorithms. Wiley, Hoboken, NJ. 2007.) For more details on the protocol specification style, please refer to the book accompanying book for this website, Decentralized Spatial Computing: Foundations of Geosensor Networks.

;;  Copyright 2011, 2012 Matt Duckham
;;
;;  This program is free software: you can redistribute it and/or modify
;;     it under the terms of the GNU General Public License as published by
;;     the Free Software Foundation, either version 3 of the License, or
;;     (at your option) any later version.
;;
;;     This program is distributed in the hope that it will be useful,
;;     but WITHOUT ANY WARRANTY; without even the implied warranty of
;;     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
;;     GNU General Public License for more details.
;;
;;     You should have received a copy of the GNU General Public License
;;     along with this program.  If not, see <http://www.gnu.org/licenses/>.

__includes["../gsn.nls"]
;; Time when locations of motes are changed
globals [network_timestamp]

;; Define a new breed of turtle called motes
breed [motes mote]

;; Interval between the triggering of broadcasting POSN message, last time trigger, epoch
;; (e in Protocol 6.6. We do not use e as it's reserved in Netlogo), movement table m,
;; posns records the motes position at each tick for the last 20 ticks.
motes-own [TriggerInterval trigger_l epoch m posns]

;; System setup and initialization
to initialize
  set network_timestamp 0
  if NetworkStructure = "UDG" [create-udg] ;; Create UDG network
  if NetworkStructure = "GG"  [create-udg create-gg] ;; Create GG network
  if NetworkStructure = "RNG" [create-udg create-rng] ;; Create RNG network
  ask motes [
    become "IDLE" ;; Set all motes to state IDLE
    set color white
    set TriggerInterval (random 3) + 1 ;; A mote broadcast POSN message at random interval
    set trigger_l 0 ;; Last time trigger when the mote broadcast posn
    set epoch 0 ;; The initial epoch is tick 0
    set m []
    set m lput (list who epoch) m ;; Initialize movement table with one record
    set posns []
    set posns lput (list ticks xcor ycor) posns ;; Initialize posns table with current tick and coordinates
    rt random-float 360 ;; All motes face in random directions
  ]
end

;; Runs the flocking algorithm
to go
  ask motes [step]
  mote_labels ;; Changes the labels of the motes based on the MoteLabel dropdown list
  DisplayM ;; When the user clicks on a mote, it displays the m table
  tick

  ;; Update the locations of motes and communication graph
  ask motes [
    let rd random-float 1
    if rd < 0.1 [ ;; At each tick, a mote has a chance to make a movement
      move-mote CorrelatedRandomWalk LevyFlight ;; Next movement of mote      
    ]
    set posns lput (list ticks xcor ycor) posns ;; Add current tick and coordinates to table posns
    while [length posns > 2 * k][
      set posns but-first posns ;; Delete old records until the table only contains the coordinates for a certain period
    ]
  ]

  if (ticks - network_timestamp) >= 10 [ ;; Update the communication graph every 10 ticks  
    clear-links ;; Delete all existing links between motes          
    if NetworkStructure = "UDG" [create-udg] ;; Create UDG network
    if NetworkStructure = "GG"  [create-udg create-gg] ;; Create GG network
    if NetworkStructure = "RNG" [create-udg create-rng] ;; Create RNG network
    set network_timestamp ticks ;; Update the timestamp of mote location change      
  ]
end

;;
;; Mote protocols
;;

;; Step through the current state
to step
  if state = "IDLE" [ step_IDLE stop ]
end

;; Motes periodically record their identifiers, coordinates and time stamps in their
;; local memory and broadcast this information to their neighbors as a POSN message.
;; Motes receiving this message will record this information if they are within the
;; flock radius (r) and the information is new before rebroadcasting the message.
to step_IDLE
  if (ticks - trigger_l) >= TriggerInterval [ ;; When time trigger elapsed
    set epoch ticks ;; Store current time as latest epoch
    set m lput (list who epoch) m ;; Store new data with relevant epoch

    discard-data ;; Only keep recent data

    broadcast (list "POSN" who (list xcor ycor) epoch) ;; Broadcast identifier, position, and current epoch
    set trigger_l ticks ;; Update time trigger
    set TriggerInterval (random 3) + 1 ;; Motes will broadcast their POSN message after a random interval    
  ]

  while [has-message "POSN"] [ ;; Receiving (POSN, i, p', e')
    let msg received "POSN"
    let i item 1 msg
    let p' item 2 msg
    let e' item 3 msg

    ;; Find motes position at the time e'
    let p_e' list (item 1 item 0 posns) (item 2 item 0 posns) ;; Initialize p(e') as the oldest coordinates recorded in posns
    foreach posns [
      if item 0 ? = e' [
        set p_e' list (item 1 ?) (item 2 ?) ;; Find the coordinates recorded at tick e'
      ]
    ]        

    if dist p_e' p' < r [ ;; Process message if it originated within flock radius r
      let g (item 1 item 0 m) ;; Initialize relevant epoch g as the oldest tick in m
      foreach m [ ;; let g:= SELECT max(epoch) INTO g FROM m WHERE epoch <= e'
        if (item 1 ? > g) and (item 1 ? <= e')[
          set g item 1 ? ;; Find relevant epoch
        ]
      ]      

      let d length filter [(item 0 ? = i) and (item 1 ? = g)] m ;; Amount of records where nid=i and epoch=g
      if d = 0 [ ;; Check if data is new
        set m lput (list i g) m ;; Store new data with relevant epoch

        discard-data ;; Only keep recent data

        broadcast (list "POSN" i p' e') ;; Rebroadcast message        
      ]
    ]
  ]

  check-flock ;; Check whether mote is moving in a flock  
end

;; Discards data that is older than the flocking duration (plus 20 ticks)
to discard-data
  set m sort-by [item 1 ?1 <= item 1 ?2] m ;; Sort m based on epoch    
  let current_epoch (item 1 last m) ;; Set the current epoch as the most recent epoch recorded in m
  let index 0
  while [index < length m] [
    if (item 1 item index m) < current_epoch - k - 20 [ ;; Keep data for 20 ticks more than the flocking duration (k)
      set m replace-item index m "x" ;; Mark the data that will be discarded
    ]
    set index (index + 1)
  ]
  set m remove "x" m ;; Discard old data that is marked as "x"
end

;; Checks whether a mote is moving in a flock
to check-flock
  let flock true
  let cnt [] ;; A table containing the count of records for each unique epoch value in m. A record in cnt is constructed as <epoch, count>.
  foreach m [
    let epo item 1 ? ;; Epoch value in current record
    if length filter [item 0 ? = epo] cnt = 0 [ ;; When this epoch has not been inserted into cnt
      let cnt_epo (length filter [item 1 ? = epo] m) ;; Count the nids in m for this epoch
      set cnt lput (list epo cnt_epo) cnt ;; Add the count for this epoch into cnt
    ]
  ]
  set cnt sort-by [item 0 ?1 < item 0 ?2] cnt ;; Sort cnt based on the order of epoch

  let current_epoch (item 0 last cnt) ;; The most recent epoch
  let oldest_epoch (item 0 first cnt) ;; The oldest epoch
  ifelse current_epoch - oldest_epoch < k [ ;; Not within minimum duration of a flock (k)
    set flock false ;; Not in flock if the epoch range didn't span over k ticks
  ]
  [ ;; Within minimum duration of a flock (k)
    let epo oldest_epoch
    let index 0
    while [index < length cnt] [
      if epo <= current_epoch - k [ ;; Find the most recent epoch that is equal to or less than (current_epoch - k)
        set epo (item 0 item index cnt)
      ]
      set index (index + 1)
    ]

    ;; Check if there are sufficient number of objects to be considered a flock (n)
    set index 0
    while [index < length cnt] [
      if (item 0 item index cnt) >= epo [
        if (item 1 item index cnt) < n [set flock false] ;; Not in flock if there are less than n nids at an epoch in a period spanning last k ticks
      ]
      set index (index + 1)
    ]
  ]

  ifelse flock = true
    [set color 15] ;; Mote is red when in a flock  
    [set color 9.9] ;; Mote is white when not in a flock
end

;; Changing the labels of the motes based on the MoteLabel dropdown list
to mote_labels
  ask motes [
    if MoteLabel = "none" [set label ""] ;; Hide the label
    if MoteLabel = "mote id" [set label who] ;; Show mote id
  ]
end

;; When the user clicks on a mote, it displays the m table
to DisplayM
  if mouse-down? [ ;; If the mouse has been clicked
    let ClickedMote min-one-of motes [distancexy mouse-xcor mouse-ycor] ;; Pick the closest mote
    clear-output ;; Clears the output field
    output-print (word "M table of mote " [who] of ClickedMote ":")
    foreach [m] of ClickedMote [output-print ?] ;; Show the m table
    stop
  ]
end

The NetLogo procedures for this applet can be downloaded directly as: Protocol6.6.nlogo

All the NetLogo simulation models for this book depend on two library files: gsn.nls and env.nls
These files should be placed in the parent directory of the .nlogo file (and are common to all the .nlogo models on this website).