• Protocol 5.12: Determining the topological structure of a complex areal object

    PROTOCOL

    Determining the topological structure of a complex areal object

    SUMMARY

    This algorithm is an extension of Protocol 5.11 which uses the hole values to determine the containment relationships between all holes and islands. It does so by having each mote in the lead state sending a RPRT message up the network to a sink mote. This message includes a score which is either incremented or decremented by one each time it crosses a boundary cycle. Once this value reaches zero, it is known that the current boundary cycle directly contains the cycle which initiated the message. These RPRT messages are then used by the sink mote to determine the containment relationship.

    OPERATION

    • Select a region from the Region_Type drop-down box.
    • Click the Setup button to generate a network based on communication distance and network size.
    • Click the Go! button to run the algorithm.

    NOTICE

    • The region is cyan in color, once the algorithm runs, BNDY motes should appear in mid-blue around the edges.
    • The sink mote is large and purple in color.
    • The leading mote should be the purple in color.
    • The path taken by the AREA message is orange in color.
    • The hole value should be 0 for an island and 1 for a hole.
    • Use the MoteLabel list to change the labels to the mote id, sensed value, wind value, m value, hole, ring, parent or hop count value. Only motes in the boundary cycle will show their m, hole or ring value.

    TRY

    • 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 the algorithm run any differently for planar and non-planar graphs?
    • Try adding more motes by increasing the number in the Netsize box. Does the boundary cycle reflect the region more accurately?
    • 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 5.12

    CREDITS

    Code designed by Matt Duckham. Additional coding by Alan Both.

    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 4.14

    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"]
    ;; Define a new breed of turtle called motes
    breed [motes mote]
    
    ;; Each mote can store the local variables s which is the sensed value of the region,
    ;; D which is the table containing the sensed values and id's of neighbors, wind which
    ;; is the id of the next mote in the boundary cycle, m which is the smallest
    ;; identifier, Def which is the defer value, hole which defines whether the cycle is a
    ;; hole or an island, ring which stores the cycle leaders' id and hop.r which stores
    ;; the hop count for the shortest path tree.
    motes-own [s D wind m Def hole ring hop.r]
    
    ;; System setup and initialization
    to initialize
    
      if Region_Type = "Region 1" [reg1]
      if Region_Type = "Region 2" [reg2]
      if Region_Type = "Region 3" [reg3]
      if Region_Type = "Region 4" [reg4] 
    
      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 [
        ifelse [region] of patch-here = ["A" "B"]
          [set s 1] ;; When region detected, s equals 1
          [set s 0] ;; When region not detected, s equals 0
        set D []
        set wind "NULL"
        set m who
        set hole -1
        set ring -1
        set parent -1
        set hop.r -1
        become "INIT" ;; Set all motes to state INIT
      ]
      while [any? motes with [s = 1 and count link-neighbors with [s = 1] < 2]] [ ;; Ensuring that motes inside the region are at least 2-connected
        ask motes with [s = 1 and count link-neighbors with [s = 1] < 2] [die]
      ]
      ask one-of motes with [xcor < min-pxcor / 3 and ycor > max-pycor / 3 and s = 0] [ ;; The sink mote must be in the exterior of the complex areal object
        become "ROOT"
        set size (size * 1.5) ;; The ROOT mote is larger than other motes
      ]
    end
    
    ;; Runs the algorithm
    to go
      ask motes [ step ]
      mote_labels ;; Changes the labels of the motes based on the MoteLabel dropdown list
      tick
    end
    
    ;;
    ;; Mote protocols
    ;;
    
    ;; Step through the current state
    to step
      if state = "ROOT" [ step_ROOT stop ]
      if state = "INIT" [ step_INIT stop ]
      if state = "IDLE" [ step_IDLE stop ]
      if state = "BNDY" [ step_BNDY stop ]
      if state = "LEAD" [ step_LEAD stop ]
    end
    
    ;; The root mote broadcasts its id and then changes state to INIT.
    to step_ROOT
      set hop.r 0
      broadcast (list "TREE" who hop.r) ;; Broadcast root identifier and hop count of zero
      become "INIT"
      stop
    end
    
    ;; All motes broadcast their sensed value and id to their neighbors and transition into
    ;; the IDLE state.
    ;; Any motes in the INIT state receiving the TREE message that has a smaller hop count
    ;; will change their parent to that mote, set their hop count to the received hop count
    ;; plus one and broadcast the message to their neighbors.
    ;; Any motes in the INIT state receiving the RPRT message will defer the message until
    ;; they are in the IDLE, BNDY or LEAD state.
    to step_INIT
      broadcast (list "PING" who s) ;; Broadcast sensed value and identifier
      become "IDLE"
    
      if has-message "TREE" [ ;; Receiving TREE
        let msg received "TREE"
        let i item 1 msg
        let h item 2 msg
        if hop.r < 0 or h + 1 < hop.r [
          set parent i ;; Store parent id
          set hop.r (h + 1) ;; Store hop count to root
          broadcast (list "TREE" who hop.r) ;; Broadcast node identifier incrementing hop count
        ]
      stop
      ]
    end
    
    ;; Motes in the IDLE state store the sensed values and ids of their neighbors and then
    ;; determine if they are boundary motes. If so they set their wind value to the id of
    ;; the next mote in the boundary cycle, send off a MSGE and transition into the BNDY
    ;; state.
    ;; Any motes in the IDLE state receiving the MSGE will forward it to the next neighbor
    ;; in the boundary cycle using the cyc function and the id of the previous mote.
    ;; Any motes in the IDLE state receiving the AREA message will calculate their portion 
    ;; of the area equation and then forward it to the next neighbor in the boundary cycle
    ;; using the cyc function and the id of the previous mote.
    ;; Any motes in the IDLE state receiving the RING message will update their hole and 
    ;; ring values and then forward it to the next neighbor in the boundary cycle using the
    ;; cyc function and the id of the previous mote.
    ;; Any motes in the IDLE state receiving the RPRT message will forward the message to
    ;; their parents unless they are the root/sink mote. In this case, they will show the
    ;; containment relationship.
    ;; Any motes in the IDLE state receiving the TREE message that has a smaller hop count
    ;; will change their parent to that mote, set their hop count to the received hop count
    ;; plus one and broadcast the message to their neighbors.
    
    to step_IDLE
      if has-message "PING" [ ;; Receiving PING message
        let msg received "PING"
        let i. item 1 msg
        let d. item 2 msg
        set D fput (list i. d.) D ;; Store neighbor identifier and sensed value
    
        if length D = count link-neighbors [ ;; Check whether PING received from all neighbors
          let I [] ;; Creating the I function
          foreach D [
            let i' item 0 ?
            let d' item 1 ?
            set I fput d' I ;; The I function is populated with d values from the D table
          ]
    
          ifelse s = 1 and member? 0 I [ ;; Check for node inside region with neighbor outside
            let tmp.i 0
            let tmp.d 0
            foreach D [
              let i' item 0 ?
              let d' item 1 ?
              if d' = 0 [
                set tmp.i i'
              ]
            ]
    
            while [tmp.d = 0] [   ;; Finding the first neighbor that has a sensed value of
              set tmp.i cyc tmp.i ;; 1, in an anticlockwise direction from a neighbor with
              foreach D [         ;; a sensed value of 0
                let i' item 0 ?
                let d' item 1 ?
                if i' = tmp.i [
                  set tmp.d d'
                ]
              ]
            ]
            set wind tmp.i ;; Setting this neighbor as the wind value
            send (list "MSGE" who who) (mote wind) ;; Initiate message to first boundary neighbor
            become "BNDY"
          ]
          [
            set Def 1
          ]
        ]
        stop
      ]
    
      if has-message "MSGE" and Def = 1 [ ;; Receiving MSGE message
        let msg received "MSGE"
        let i item 1 msg
        let i' item 2 msg
        send (list "MSGE" i who) (mote cyc i') ;; Forward message to next boundary cycle neighbor
        stop
      ]
    
      if has-message "AREA" and Def = 1 [ ;; Receiving AREA message
        let msg received "AREA"
        let i item 1 msg
        let xy item 2 msg
        let a item 3 msg
        let cx item 4 msg
        let cy item 5 msg
    
        let x item 0 xy
        let y item 1 xy
    
        let x' xcor
        let y' ycor
    
        let u x * y' - x' * y
    
        send (list "AREA" who (list x' y') (a + u) (cx + (x + x') * u) (cy + (y + y') * u)) (mote cyc i)
        ask link-with mote cyc i [ ;; Making the path taken by the AREA message thick and orange in color
          set color orange
          set thickness 0.3
        ]
        stop
      ]
    
      if has-message "RING" [ ;; Receiving RING message
        let msg received "RING"
        let i item 1 msg
        let o item 2 msg
        let r item 3 msg
        send (list "RING" who o r) (mote cyc i) ;; Forward message to next boundary cycle neighbor
        stop
      ]
    
      if has-message "RPRT" [ ;; Receiving RPRT message
        let msg received "RPRT"
        let r.a item 1 msg
        let r.b item 2 msg
        let s.p item 3 msg
        let c.score item 4 msg
        ifelse parent = -1
          [;show msg
          show (word r.a " is in " r.b)]
          [send (list "RPRT" r.a r.b s c.score) (mote parent)] ;; Forward message to parent
    
        stop
      ]
    
      if has-message "TREE" [ ;; Receiving TREE
        let msg received "TREE"
        let i item 1 msg
        let h item 2 msg
        if hop.r < 0 or h + 1 < hop.r [
          set parent i ;; Store parent id
          set hop.r (h + 1) ;; Store hop count to root
          broadcast (list "TREE" who hop.r) ;; Broadcast node identifier incrementing hop count
        ]
      stop
      ]
    end
    
    ;; Motes in the BNDY state will either forward messages to the next boundary neighbor
    ;; if the i value is lower than the m value, not forward the message if it is higher or
    ;; transition into the LEAD state if the i value is the same as their id and initiate
    ;; the AREA message.
    ;; Any motes in the BNDY state receiving the AREA message will calculate their portion 
    ;; of the area equation and then forward it to the next neighbor in the boundary cycle
    ;; using the wind value.
    ;; Any motes in the BNDY state receiving the RING message will update their hole and 
    ;; ring values and then forward it to the next neighbor in the boundary cycle using the
    ;; wind value.
    ;; Any motes in the BNDY state receiving the TREE message that has a smaller hop count
    ;; will change their parent to that mote, set their hop count to the received hop count
    ;; plus one and broadcast the message to their neighbors.
    ;; Any motes in the BNDY state receiving the RPRT message will defer the processing of
    ;; the message until after the RING message has been processed. The c value will then
    ;; be incremented, decremented or remain unchanged based on the sensed values of the
    ;; current, previous and parent mote as well as the hole value.
    to step_BNDY
      if has-message "MSGE" [ ;; Receiving MSGE message
        let msg received "MSGE"
        let i item 1 msg
        let i' item 2 msg
    
        ifelse i = who [ ;; Check whether message returned to sender
          send (list "AREA" who (list xcor ycor) 0 0 0) (mote wind)
          ask link-with mote wind [ ;; Making the path taken by the AREA message thick and orange in color
            set color orange
            set thickness 0.3
          ]
          become "LEAD"
        ]
        [
          if i < m [
            set m i
            send (list "MSGE" i who) (mote wind) ;; Forward message to next boundary neighbor
          ]
        ]
        stop
      ]
    
      if has-message "AREA" [ ;; Receiving AREA message
        let msg received "AREA"
        let i item 1 msg
        let xy item 2 msg
        let a item 3 msg
        let cx item 4 msg
        let cy item 5 msg
    
        let x item 0 xy
        let y item 1 xy
    
        let x' xcor
        let y' ycor
    
        let u x * y' - x' * y
    
        send (list "AREA" who (list x' y') (a + u) (cx + (x + x') * u) (cy + (y + y') * u)) (mote wind)
        ask link-with mote wind [ ;; Making the path taken by the AREA message thick and orange in color
          set color orange
          set thickness 0.3
        ]
        stop
      ]
    
      if has-message "RING" [ ;; Receiving RING message
        let msg received "RING"
        let i item 1 msg
        let o item 2 msg
        let r item 3 msg
    
        set hole o
        set ring r
        send (list "RING" who o r) (mote wind) ;; Forward message to next boundary neighbor
        stop
      ]
    
      if has-message "TREE" [ ;; Receiving TREE
        let msg received "TREE"
        let i item 1 msg
        let h item 2 msg
        if hop.r < 0 or h + 1 < hop.r [
          set parent i ;; Store parent id
          set hop.r (h + 1) ;; Store hop count to root
          broadcast (list "TREE" who hop.r) ;; Broadcast node identifier incrementing hop count
        ]
      stop
      ]
    
      if has-message "RPRT" and hole >= 0 [ ;; Receiving RPRT message (Defer until after ring message)
        let msg received "RPRT"
        let r.a item 1 msg ;; contained ring id
        let r.b item 2 msg ;; containing ring id
        let s.p item 3 msg ;; previous sensed value
        let c.score item 4 msg ;; c score
    
        if r.b < 0 [ ;; Check for RPRT without containing region
          if s.p != s [set c.score (c.score + 1 - 2 * hole)] ;; Increment score based on incoming neighbor
          if member? (list parent s) D = false [set c.score (c.score - 1 - 2 * hole)] ;; Increment score based on outgoing nbr
          if c.score = 0 [set r.b ring] ;; Update containing region if required
        ]
        send (list "RPRT" r.a r.b s c.score) (mote parent) ;; Forward message to parent
        stop
      ]
    end
    
    ;; The mote in the LEAD state will calculate the final portion of the area calculation
    ;; and display the area and centroid of the boundary. If the area is positive, a RING
    ;; message with a ring value of 0 will be sent along with the leading motes' id as the
    ;; ring value. If the area is negative, the message will be sent with a ring value of 1
    ;; Any motes in the LEAD state receiving the TREE message that has a smaller hop count
    ;; will change their parent to that mote, set their hop count to the received hop count
    ;; plus one and broadcast the message to their neighbors.
    ;; Any motes in the LEAD state receiving the RPRT message will defer the processing of
    ;; the message until after the RING message has been processed. The c value will then
    ;; be incremented, decremented or remain unchanged based on the sensed values of the
    ;; current, previous and parent mote as well as the hole value.
    ;; Any motes in the LEAD state receiving the RING message will update their hole and 
    ;; ring values and then generate a RPRT message containing their id, sensed value and a
    ;; c score based on their hole value, their sensed value and the sensed value of their
    ;; parent.
    to step_LEAD
      if has-message "AREA" [ ;; Receiving AREA message
        let msg received "AREA"
        let i item 1 msg
        let xy item 2 msg
        let a item 3 msg
        let cx item 4 msg
        let cy item 5 msg
    
        let x item 0 xy
        let y item 1 xy
    
        let x' xcor
        let y' ycor
    
        let u x * y' - x' * y
    
        let area (a + u) / 2
    ;;    show (word "Area: " precision area 3)
    
        if area != 0 [
          let cenx (cx + (x + x') * u) / (6 * area)
          let ceny (cy + (y + y') * u) / (6 * area)
    ;;      show (word "Centroid: " precision cenx 3", " precision ceny 3)
        ]
    
        ifelse area > 0
          [send (list "RING" who 0 who) (mote wind)] ;; Positive area bounds island
          [send (list "RING" who 1 who) (mote wind)] ;; Negative area bounds hole
        stop
      ]
    
      if has-message "TREE" [ ;; Receiving TREE
        let msg received "TREE"
        let i item 1 msg
        let h item 2 msg
        if hop.r < 0 or h + 1 < hop.r [
          set parent i ;; Store parent id
          set hop.r (h + 1) ;; Store hop count to root
          broadcast (list "TREE" who hop.r) ;; Broadcast node identifier incrementing hop count
        ]
      stop
      ]
    
      if has-message "RPRT" and hole >= 0 [ ;; Receiving RPRT message (Defer until after ring message)
        let msg received "RPRT"
        let r.a item 1 msg ;; contained ring id
        let r.b item 2 msg ;; containing ring id
        let s.p item 3 msg ;; previous sensed value
        let c.score item 4 msg ;; c score
    
        if r.b < 0 [ ;; Check for RPRT without containing region
          if s.p != s [set c.score (c.score + 1 - 2 * hole)] ;; Increment score based on incoming neighbor
          if member? (list parent s) D = false [set c.score (c.score - 1 - 2 * hole)] ;; Increment score based on outgoing nbr
          if c.score = 0 [set r.b ring] ;; Update containing region if required
        ]
        send (list "RPRT" r.a r.b s c.score) (mote parent) ;; Forward message to parent
        stop
      ]
    
      if has-message "RING" [ ;; Receiving RING message
        let msg received "RING"
        let i item 1 msg
        let o item 2 msg
        let r item 3 msg
    
        set hole o
        set ring r
    
        ifelse (member? (list parent s) D = false and hole = 0) or (member? (list parent s) D = true and hole = 1)
          [send (list "RPRT" who -1 s 1) (mote parent)] ;; Initiate report with score 1 (cases I1/I4)
          [send (list "RPRT" who -1 s 2) (mote parent)] ;; Initiate report with score 2 (cases I2/I3)
    
        stop
      ]
    end
    
    ;; Changing the labels of the motes based on the MoteLabel dropdown list
    to mote_labels
      ask motes [
        set label "" ;; Hide the label
        if MoteLabel = "mote id" [set label who] ;; Show mote id
        if MoteLabel = "wind" and wind != "NULL" [set label wind] ;; Show wind value
        if MoteLabel = "s" [set label s] ;; Show s value
        if MoteLabel = "m" and (state = "BNDY" or state = "LEAD") [set label m] ;; Show m value for motes within the boundary cycle
        if MoteLabel = "hole" and (state = "BNDY" or state = "LEAD") [set label hole] ;; Show hole value for motes within the boundary cycle
        if MoteLabel = "ring" and (state = "BNDY" or state = "LEAD") [set label ring] ;; Show ring value for motes within the boundary cycle
        if MoteLabel = "parent" [set label parent] ;; Show parent value
        if MoteLabel = "hop count" [set label hop.r] ;; Show hop.r value
      ]
    end
    
    ;; The following procedures generate four different types of regions
    to reg1 ;; Generates two small regions
      let rsize count patches
    
      ;; 2 small regions
      let p one-of patches with [
        pxcor = int (.5 * min-pxcor) and pycor = int (.5 * min-pycor)
      ]
      growRegion (rsize * .10) ["A" "B"] p
      ask patches with [region = [] and count neighbors with [region = ["A" "B"]] > 0] [
        set region ["A"]
        set pcolor 57 ;; Region A is green
      ]
      ask patches with [region = [] and count neighbors4 with [region = ["A"]] > 0] [
        set region ["A"]
        set pcolor 57 ;; Region A is green
      ]
      set p one-of patches with [
        region = [] and count neighbors4 with [region = ["A"]] > 0 and count neighbors4 with [region = []] > 0 and InsideBuffer = true
      ]
      growRegion int (rsize * .03) ["A"] p
      set p one-of patches with [
          pxcor = int (.5 * max-pxcor) and pycor = int (.5 * max-pycor)
      ]
      growRegion int (rsize * .10) ["A" "B"] p
    
      ;; Removing region A
      ask patches [
        if region = ["A"] [
          set region []
          set pcolor 9.9 ;; Null is white
        ]
      ]
    end
    
    to reg2 ;; Generates a large region with a small hole in it
      let rsize count patches
    
      ;; 1 region with a hole inside it
      let p patch 0 0
      growRegion (rsize * .01) ["A"] p
      ask patches with [region = [] and count neighbors with [region = ["A"]] > 0] [
        set region ["A" "B"]
        set pcolor 87 ;; A B is cyan
      ]
      ask patches with [region = [] and count neighbors4 with [region = ["A" "B"]] > 0] [
        set region ["A" "B"]
        set pcolor 87 ;; A B is cyan
      ]
      set p one-of patches with [
        region = [] and count neighbors4 with [region = ["A" "B"]] > 0 and count neighbors4 with [region = []] > 0 and InsideBuffer = true
      ]
      growRegion int (rsize * .3) ["A" "B"] p
    
      ;; Removing region A
      ask patches [
        if region = ["A"] [
          set region []
          set pcolor 9.9 ;; Null is white
        ]
      ]
    end
    
    ;; Code truncated for length, please download .nlogo file below
    

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