PROTOCOL

Tracking the (inner) boundary of a region, defined as sensed value above threshold r

SUMMARY

The algorithm starts with every mote broadcasting a message to its neighbors stating its current sensed value as a real number. Every time a mote receives a message, it checks the received value with its own. If a mote’s sensed value is equal to or greater than r but receives a message that a neighbor’s sensed value is lower than r, the mote transitions into the BNDY state. Every mote is reinitialized when the trigger time interval (d) has elapsed.

OPERATION

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

NOTICE

• The region is green in color, once the algorithm runs, BNDY motes should appear in mid-blue around the edges.
• Use the MoteLabel list to change the labels to either the mote id or sensed value. This will help show how the algorithm runs. When set to the sensed value, all motes within the region should have a value equal to or greater than threshold r with the rest having a value below r. For this algorithm the threshold is 0.
• Use the RegionChangeInterval slider to change the interval that the region is changed.
• Use the d slider to change the interval that the motes are reinitialized.
• Use the RegionMovement list to alter how the region changes. When set to static, the region never changes. When set to uncorrelated, the new region will have no relation to the old region in terms of shape and position. When set to evolving, the new region is incrementally changed from the old region.

TRY

• What happens when a smaller netsize value and a small region is used? Do any motes transition into the BNDY state?
• What happens if the communication distance is too small, making a disconnected network? Try this by adjusting the c slider.
• 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 BNDY motes?
• Try running the algorithm slowly to get a better idea of how the algorithm runs. Change this by adjusting the speed slider.

LINK TO BOOK

Protocol 6.1

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

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 and 
;; INIT_timestamp which is the time that the mote becomes INIT
motes-own [s INIT_timestamp]

;; 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 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 INIT_timestamp ticks ;; Record the time when the mote becomes INIT
  broadcast (list "PING" s) ;; Broadcast sensed value
  become "IDLE"
end

;; Motes receiving a PING message determine if they are on the boundary of the region, if
;; they are, they transition into the BNDY state. Once the trigger time interval (d) has
;; elapsed, the motes will revert to the INIT state.
to step_IDLE
  if has-message "PING" [ ;; Receiving PING
    let msg received "PING"
    let s' item 1 msg ;; Received sensed value
    if s' < r and r <= s [ ;; Check if mote is within region threshold, but adjacent to mote outside the region
      become "BNDY"
    ]
    stop
  ]
  
  if (ticks - INIT_timestamp) >= d [ ;; When time step elapsed
    become "INIT" ;; Revert to the INIT state (re-trigger the motes)
    stop
  ] 
end

;; Motes in the BNDY state will revert to the INIT state once the trigger time interval
;; (d) has elapsed.
to step_BNDY
  set messages [] ;; Clear messages
  
  if (ticks - INIT_timestamp) >= d [ ;; When time step elapsed
    become "INIT" ;; Revert to the INIT state (re-trigger the motes)
    stop
  ] 
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 (rounded) sensed value
  ]
end

The NetLogo procedures for this applet can be downloaded directly as: Protocol6.1.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).