Basic flocking algorithm
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).
Code designed by Matt Duckham. Additional coding by Alan Both and Hai Ruo Xie.
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.
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).