• Protocol 6.6: Basic flocking algorithm

    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).

Leave a Reply

Your email address will not be published. Required fields are marked *

*

* Copy this password:

* Type or paste password here:

8,296 Spam Comments Blocked so far by Spam Free Wordpress

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>