PROTOCOL

Monitoring topological changes in dynamic regions

SUMMARY

Any nodes that detect a change in their sensed value inform neighbors of the change. A node maintains the sensed value for its one-hop neighbors. Based on its own sensed value and the sensed value of its neighbors, a node determines whether a region has appeared, disappeared, split or merged. Each region is assigned with a region ID, which will be disseminated to all boundary nodes of the region. When a region is split into two parts, each part will get a new region ID from the node where the split happens.

OPERATION

• Click the Setup button to initialize the environment.
• Click the Go! button to run the algorithm.

NOTICE

• You do not need to change the values in Netsize.
• When a mote detects a topographic change, a message will be displayed in the command center.
• The color of idle nodes, i.e., the nodes outside a region and inside the boundary of a region is cyan.
• The color of boundary nodes is red.
• The color of pinch nodes is yellow.
• Use the MoteLabel list to change the labels to mote id, sensed value or region id.
• Use the RegionChangeInterval slider to change the interval that the region moves.

LINK TO BOOK

Protocol 6.9

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

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, maximum distance of a link
globals [region_timestamp c]

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

;; Each mote can store the local variable s which is the sensed value, s_l which is the previous sensed value
;; d is the sensed value of neighbors, rid is the region id
motes-own [s s_l d rid]

;; System setup and initialization
to initialize  
  if (max-pxcor - min-pxcor) * (max-pycor - min-pycor) <= netsize [
    show "The number of motes should be smaller than the number of patches. Please reduce the Netsize or increase the number of patches."
    stop
  ]
  ;; *********Create maximal planar graph************
  ;; Distribute motes evenly and randomly in the whole area
  ;; Divide the whole area into 'netsize' virtual tiles
  let tile_size (max-pxcor - min-pxcor) * (max-pycor - min-pycor) / netsize ;; Size of a tile
  let xy_ratio (max-pxcor - min-pxcor) / (max-pycor - min-pycor) ;; Ratio of width versus height
  let th sqrt (tile_size / xy_ratio) ;; Height of a tile
  let tw sqrt (tile_size * xy_ratio) ;; Width of a tile  
  ;; Place a mote at a random location within a tile
  let mID 0 ;; Mote ID  
  let px min-pxcor + 0.5 * tw
  while [px <= max-pxcor][
    let py min-pycor + 0.5 * th    
    while [py <= max-pycor][
      let inc_px random-float tw
      let inc_py random-float th
      ask mote mID [
        setxy (px + inc_px - 0.5 * tw) (py + inc_py - 0.5 * th)        
      ]
      set mID mID + 1        
      set py py + th
    ]
    set px px + tw
  ]    
  ;; Adjust the positions of motes to ensure that no patch has more than one mote
  while [any? patches with [(count motes-here) > 1]] [ ;; No patch should contain more than one mote
    ask patches with [(count motes-here) > 1][
      ask motes-here [
        let inc_px random-float 1
        let inc_py random-float 1      
        setxy (xcor + inc_px - 0.5) (ycor + inc_py - 0.5)                      
      ]
    ]
  ]  
  ;; Create links between motes  
  set c (sqrt (tw * tw + th * th)) * 2 ;; To keep the graph balanced, set a limit of the length of links 

  create-udg ;; The MPG is a sub-graph of the UDG
  create-gg ;; The GG is a sub-graph of the MPG

  ;; Some links that have been removed earlier may need to be re-created. Add links to complete the graph based on cyc function.
  repeat 2 [completeMPG]
  ;; Check to ensure that every mote has two or more linked neighbor
  if any? motes with [count link-neighbors < 2] [
    show "There are one or more motes which have less than two linked neighbors. Re-generating the network..."
    setup
    initialize    
    stop
  ]
  ;; *********Finished creating maximal planar graph************
  
  ;; Initialize local data  
  ask motes [
    set d []
    foreach sort link-neighbors [
      set d lput (list [who] of ? 0) d ;; Init. to d(i)=0
    ]
    set rid 0 ;; Init. to rid:=0
    set color white    
    become "IDLE" ;; Initialize to IDLE first
  ]
  
  set region_timestamp 0 ;; Reset the timestamp of region change
end

;; Complete maximal planar graph: ensure that there is a link between any pair of adjacent linked neighbors A and B (A=cyc(B)) of every mote.
to completeMPG
  ask motes [    
    foreach sort link-neighbors [
      let nbr1ID [who] of ?
      let nbr2ID cyc nbr1ID
      while [ [color] of link who nbr2ID = blue ] [ ;; Ignore blue links
        set nbr2ID cyc nbr2ID
      ]
      if is-link? link nbr1ID nbr2ID = false and nbr1ID != nbr2ID [ ;; Only form new links
        ask mote nbr1ID [create-link-with (mote nbr2ID)]
        ask link nbr1ID nbr2ID [
          ifelse link-length > c
            [die] ;; Kill link if it exceeds maximum distance
            [set color blue] ;; Newly added links are blue
        ]
      ]
    ]
  ]

  ;; Removing intersecting links from the MPG
  ask links [ 
    if color != blue [stop] ;; Only considering the newly added links
    let link1_end1 [who] of end1
    let link1_end2 [who] of end2
    ask other links [        
      if color = red [stop] ;; Not considering links which are already marked for deletion
      let link2_end1 [who] of end1
      let link2_end2 [who] of end2

      if (link1_end1 != link2_end1) and (link1_end2 != link2_end2) and (link1_end2 != link2_end1) and (link1_end1 != link2_end2) [
        let p_a list [xcor] of (mote link1_end1) [ycor] of (mote link1_end1)
        let p_b list [xcor] of (mote link1_end2) [ycor] of (mote link1_end2)        
        let p_c list [xcor] of (mote link2_end1) [ycor] of (mote link2_end1)        
        let p_d list [xcor] of (mote link2_end2) [ycor] of (mote link2_end2)        
        if intersect p_a p_b p_c p_d [ ;; If two links intersect, highlight the longer one
          ifelse ([link-length] of link link1_end1 link1_end2) <= ([link-length] of link link2_end1 link2_end2)
            [ask link link2_end1 link2_end2 [set color red]]
            [ask link link1_end1 link1_end2 [set color red]]
        ]
      ]        
    ]
  ]
  ask links [
    ifelse color = red
      [die] ;; Remove the highlighted links
      [set color grey] ;; Remaining links will be grey
  ]
end

;; Runs the region monitoring algorithm
to go   
  if count patches <= netsize [
    show "The number of motes should be smaller than the number of patches. Please reduce the Netsize or increase the number of patches."
    stop
  ]  
  ask motes [ step ]
  mote_labels ;; Changes the labels of the motes based on the MoteLabel dropdown list
  tick
  
  ;; Change region at certain rate
  if (ticks - region_timestamp) >= RegionChangeInterval [
    ifelse not any? patches with [region = ["A"]] 
    [
      make-single-region 1 ;; Create a region when there is no region
    ]
    [
      ;; Randomly make one of the three changes: create a region, evolve a region or shrink a region
      let rnd random-float 1
      if rnd < 0.1 [make-single-region 1] ;; Create a new region
      if 0.1 <= rnd and rnd < 0.9 [evolve-region-special ["A"] RegionSize] ;; Incrementally change the existing region
      if rnd > 0.9 [      
        ask one-of patches with [(region = ["A"]) and (any? neighbors4 with [region = []])] [
          set region [] ;;Remove the patch from the region
          set pcolor white ;;Restore color
        ]
        FillHole
      ]
    ]
    ask motes [ ;Update sensed value
      ifelse [region] of patch-here = ["A"]
        [set s 1]
        [set s 0]
    ]     
    set region_timestamp ticks ;; Update the timestamp of region change
  ]
 
end

;; Get set I (IDs of neighbors n where d(n)=0 and d(cyc(n))=1)
to-report CI
  let c_i [] ;; A list of the IDs of neighbors satisfying the criteria of I
  foreach d [
    let d_n (item 1 ?) ;Reading of neighbor n
    let cyc_n cyc (item 0 ?) ;ID of next neighbor anticlockwise
    let d_cyc_n item 1 item 0 (filter [item 0 ? = cyc_n] d)
    if d_n = 0 and d_cyc_n = 1 [
      set c_i lput (item 0 ?) c_i
    ]
  ]
  report c_i
end

;; Unique new region identifier function u
to-report id_func [mt]
  let value (word mt (" at ") ticks)
  report value
end

;;
;; Mote protocols
;;

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

;; Motes in the IDLE state an upd8 message when their sensed value changes
;; Motes receiving the upd8 message update their d table with the received sensed value
;; and if they are within the region, send an idnt message to neighbors with ???
;; and transition to the BNDY state
to step_IDLE
  if s_l != s [ ;; When sensed value changes
    set s_l s ;; Update the previous sensed value so this part only executes once
    broadcast (list "upd8" who s) ;; Broadcast sensed value and identifier
    ifelse length filter [item 1 ? = 0] d = count my-links [ ;; All neighbors sense value 0
      set rid id_func who
      become "BNDY" 
      type "Region appeared at mote " type who type ". Rid: " type rid type "\n" ;; Report region rid appeared
    ]  
    [ ;; Not all neighbors sense value 0
      let c_i CI
      if length c_i = 1 [ ;; Only one sequence of neighbors which are not part of the region
        send (list "idnt" who) (mote cyc item 0 c_i)
        become "BNDY"
      ]
      if length c_i >= 2 [ ;; Two or more sequences of neighbors which are not part of the region (region merge)
        set rid id_func who
        foreach c_i [
          send (list "regn" rid who) (mote cyc ?) 
        ]
        type "Region merged at mote " type who type ". Rid: " type rid type "\n" ;; Report region merge detected
        become "PNCH"
      ]
    ]
    stop
  ]
  if has-message "upd8" [ ;; Received upd8 message
    let msg received "upd8"
    let i' item 1 msg
    let s' item 2 msg

    let NewRecord (list i' s')
    let OldRecord first filter [item 0 ? = i'] d ;; Find record where i = i'
    set d replace-item (position OldRecord d) d NewRecord ;; set d(i') as s
    
    if s = 1 [
      let c_i CI
      if length c_i = 1 [
        send (list "idnt" who) (mote cyc item 0 c_i)
        become "BNDY"
      ]
    ]
    stop
  ]         
end

;; Motes in the BNDY state detecting a change in their sensed value will set their rid to
;; zero and will transition to the IDLE state if none of their neighbors detect the 
to step_BNDY
  set color red

  if s_l != s [ ;; When sensed value changes
    set s_l s
    broadcast (list "upd8" who s) ;; Broadcast sensed value and identifier
    if length filter [item 1 ? = 0] d = count my-links [ ;; All neighbors sense value 0
      type "Region disappeared at mote " type who type ". Rid: " type rid type "\n" ;; Report that region has disappeared 
    ]
    become "IDLE"            
    set rid 0 ;; Delete stored region id rid
    stop
  ]
  
  PNCH-BNDY  ;; Runs the functions common to both the PNCH and BNDY states.
end

;; Motes in the PNCH state detecting a change in their sensed value will transition to 
;; the IDLE state and send messages with new rids to neighbors indicating that a split
;; has occurred.
to step_PNCH
  set color yellow

  if s_l != s [
    set s_l s 
    broadcast (list "upd8" who s) ;; Broadcast sensed value and identifier
    become "IDLE" 
    type "Region split at mote " type who type "." type "\n" ;; Report region r split  
    let c_i CI   
    foreach c_i [
      let new_rid id_func (cyc ?)
      send (list "regn" new_rid who) (mote (cyc ?)) ;; Update rid for all boundary nodes
    ]
    set rid 0
    stop
  ]

  PNCH-BNDY ;; Runs the functions common to both the PNCH and BNDY states.
end

;; Motes receiving the upd8 message update their d table with the latest sensed value and
;; depending on the number of sequences of neighbors which are not part of the region,
;; will transition into either the IDLE, BNDY or PNCH state.
;; Motes receiving the regn message will update their rid value if the sent value is 
;; different and forward this message to the neighboring boundary motes.
;; Motes receiving the idnt message will send their rid back to the mote which made the 
;; request.
to PNCH-BNDY
  if has-message "upd8" [
    let msg received "upd8"
    let i' item 1 msg
    let s' item 2 msg
        
    let NewRecord (list i' s')
    let OldRecord first filter [item 0 ? = i'] d ;; Find record where i = i'
    set d replace-item (position OldRecord d) d NewRecord ;; set d(i') as s
 
    let c_i CI ;; IDs of neighbors n where d(n)=0 and d(cyc(n))=1
    if length filter [item 1 ? = 1] d = count my-links [
      become "IDLE"
      set rid 0
    ]
    if length c_i = 1 [become "BNDY"] ;; Pinch point now in region interior
    if length c_i = 2 [become "PNCH"] ;; Boundary node now pinch point    
    stop 
  ]

  if has-message "regn" [ ;; Received regn message
    let msg received "regn"
    let r' item 1 msg
    if r' != rid [ ;; Region update message continues only as far as new updates required
      set rid r'
      let c_i CI   
      foreach c_i [
        send (list "regn" r' who) (mote (cyc ?)) ;; Update rid for all boundary nodes
      ]
    ]
    stop
  ]

  if has-message "idnt" [ ;; Received idnt message
    let msg received "idnt"
    let i' item 1 msg
    send (list "regn" rid who) (mote i') ;; Send rid to mote which made the idnt request
    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 s] ;; Show sensed value
    if MoteLabel = "region id" [ ;; Show non-zero region ids
      ifelse rid = 0
        [set label ""] ;; Show nothing
        [set label rid] ;; Show region id
    ]
  ]
end

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