• Protocol 6.9: Monitoring topological changes in dynamic regions

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

Leave a Reply

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

*

* Copy this password:

* Type or paste password here:

8,253 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>