Tracking the (inner) boundary of a region, with state maintenance
The algorithm starts with every mote storing its current sensed value and broadcasting its current sensed value to its neighbors. Motes store the sensed values of all one-hop neighbors which are updated with the sensed values from these messages. Motes also constantly check the changes in their own sensed value and if this sensed value has changed enough to cross the threshold (r), the mote is reinitialized (unlike the previous algorithm where motes reinitialize after a trigger time interval (d) has elapsed). When an IDLE mote’s sensed value is above the threshold and it has at least one neighbor whose sensed value is below the threshold, the mote transitions into the BNDY state.
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" "../env.nls"] ;; Last time that a region is changed, x/y coordinates of the center of the region, ;; Highest possible sensed value, Threshold for region detection. globals [region_timestamp RegionCenter MaxReading r] ;; Define a new breed of turtle called motes breed [motes mote] ;; Each mote can store the local variables s which is the sensed value, s_l which is the ;; sensed value at time of state change and d which is a list of neighbor ids and their ;; sensed values. motes-own [s s_l d] ;; System setup and initialization to initialize set r 0 ;; Threshold for region detection make-single-region RegionSize ;; Create the region update-region-cnt ;; Calculate the center of the region 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 [ update-reading ;; Update locally sensed data become "INIT" ;; Set all motes to state INIT set d  foreach sort link-neighbors [ ;Store the sensed value for each neighbor set d lput (list -1 ([who] of ?)) d ;; The sensed value of each neighbor is initialized to -1 ] ] set region_timestamp 0 ;; Reset the region change timestamp end ;; Calculate the center of the region and highest possible sensed value to update-region-cnt let min_rgn_x min [pxcor] of patches with [region = ["A"]] - 0.5 let min_rgn_y min [pycor] of patches with [region = ["A"]] - 0.5 let max_rgn_x max [pxcor] of patches with [region = ["A"]] + 0.5 let max_rgn_y max [pycor] of patches with [region = ["A"]] + 0.5 set RegionCenter list (0.5 * (min_rgn_x + max_rgn_x)) (0.5 * (min_rgn_y + max_rgn_y)) ;; Region center coordinates set MaxReading (max_rgn_x - min_rgn_x + max_rgn_y - min_rgn_y + 2) / 2 ;; Highest possible reading (sensed at region center) end ;; Generate sensed data based on region threshold r to update-reading let p list xcor ycor ;; Mote coordinates ifelse [region] of patch-here = ["A"] [set s MaxReading - dist p RegionCenter] ;; When mote is inside the region, the reading should be above 0 [set s r - dist p RegionCenter] ;; When mote is outside the region, the reading should be below 0 end ;; Runs the boundary algorithm to go ask motes [ step ] mote_labels ;; Changes the labels of the motes based on the MoteLabel dropdown list tick ;; Alter region when the RegionChangeInterval value has elapsed if (ticks - region_timestamp) >= RegionChangeInterval [ ;; Interval has elapsed if RegionMovement = "Static"  ;; Do nothing to the region if it is static if RegionMovement = "Uncorrelated" [ ask patches [ ;; Clear patches set pcolor white set region  ] make-single-region RegionSize ;; Create a new region that is unrelated to the existing region ] if RegionMovement = "Evolving" [ evolve-region ["A"] RegionSize ;; Incrementally change the existing region ] update-region-cnt ;; Calculate the center of the region set region_timestamp ticks ;; Update the region change timestamp ask motes [update-reading] ;; Update sensed values of the motes ] end ;; ;; Mote protocols ;; ;; Step through the current state to step if state = "INIT" [ step_INIT stop ] if state = "IDLE" [ step_IDLE stop ] if state = "BNDY" [ step_BNDY stop ] end ;; Broadcast sensed value to neighbors. to step_INIT set s_l s ;; Store the current reading as s_l broadcast (list "PING" s who) ;; Broadcast PING with sensed value become "IDLE" end ;; Common procedures for the IDLE and BNDY states: ;; Motes in these states will transition into the BNDY state if they are within the ;; region threshold, but have at least one neighbor outside the region. Otherwise they ;; will transition into the IDLE state. ;; Motes receiving the PING message update their d tables to include new sensed values ;; from their neighbors. ;; If the sensed value of the motes drop below or increase above the threshold (r), they ;; revert to the INIT state. to common-proc ifelse s >= r and (length filter [item 0 ? < r] d > 0) [ become "BNDY" ;; If mote is within region threshold, but with at least one neighbor outside the region ] [ become "IDLE" ] ;; Receiving PING if has-message "PING" [ let msg received "PING" let s' item 1 msg ;; Received sensed value let i item 2 msg ;; The identifier of neighbor foreach d [ let d.i (item 1 ?) ;; Neighbor id if d.i = i [ ;; Find the record in d corresponding to the neighbor who sent the PING message set d replace-item (position ? d) d (list s' i) ;; Update record with received sensed value ] ] stop ] ;; Become INIT if sensed value cross threshold if (s < r and r <= s_l) or (s_l < r and r <= s) [ become "INIT" ;; Change the states of motes when the mote's reading drop below or increase above threshold stop ] end to step_IDLE common-proc end to step_BNDY common-proc 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 if MoteLabel = "sensed value" [set label precision s 1] ;; Show sensed value ] end
The NetLogo procedures for this applet can be downloaded directly as: Protocol6.2.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).