• Protocol 4.15: Determining the topological relation between two sensed regions A and B

    PROTOCOL

    Determining the topological relation between two sensed regions A and B

    SUMMARY

    The algorithm starts with the root mote broadcasting a tree message to its neighbors containing its sensed value and id before transitioning to the SINK state. Motes receiving this message will do three things;
    1. Append their N table with the id of the broadcasting mote.
    2. If the mote doesn’t have a parent, it will set it as the id of the broadcasting mote and broadcast the tree message to its neighbors containing its sensed value and id. This will continue throughout the network until a complete tree is built.
    3. If their sensed value is [“A” “B”] they will compare it with the sensed value of the broadcasting mote and update their bin value.

    Once a mote has received a tree message from all of its neighbors, it will transition to the DONE state and send a report message to its parent containing its bin value. These report messages will travel up the tree, combining with other motes bin values until they reach the sink mote. Using table 4.2, the sink mote then determines the topological relation.

    OPERATION

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

    NOTICE

    • The topological relation determined by the sink mote is shown in the output box.
    • The sink mote is initially white and is larger than the other motes.
    • Use the MoteLabel list to change the labels to either the mote id, parent id, bin value or the sensed value. This will help show how the algorithm runs. When set to the sensed value, all motes within the green region should have a value of [“A”], all motes within the blue region should have a value of [“B”] and all motes within the cyan region should have a value of [“A” “B”].

    TRY

    • What happens when a smaller netsize value and a small region is used? Does the algorithm still correctly determine the topological relation?
    • What happens if the communication distance is too small, making a disconnected network? Change 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 results?
    • 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 4.15

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

    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 variable s which is the sensed value, bin which is the
    ;; summary of the non-empty intersections and N which is set of "visited" neighbors.
    motes-own [s bin N]
    
    ;; System setup and initialization
    to initialize
      make-region RegionSize SelectRegion ;; Create 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 [
        set s [region] of patch-here ;; Determining sensed value
        set bin "0000"
        set parent []
        set N []
        become "IDLE" ;; Set all motes to state IDLE
      ]
      ask one-of motes [
        set size (size * 1.5) ;; The sink mote is larger than other motes
        become "INIT" ;; Set one mote to state INIT
      ]
    end
    
    ;; Runs the topological relations 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 = "INIT" [ step_INIT stop ]
      if state = "SINK" [ step_SINK stop ]
      if state = "IDLE" [ step_IDLE stop ]
      if state = "DONE" [ step_DONE stop ]
    end
    
    ;; Sink mote initiates the algorithm.
    to step_INIT
      broadcast (list "TREE" s who)
      become "SINK"
      output-type translate bin
    end
    
    ;; Motes receiving a TREE message will do the following;
    ;; 1. Append their N table with the id of the broadcasting mote.
    ;; 2. If the mote doesn't have a parent, it will set it as the id of the broadcasting 
    ;;    mote and broadcast the tree message to its neighbors containing its sensed value
    ;;    and id.
    ;; 3. If the mote is within region AB and the received sensed value differs from this, 
    ;;    the mote updates its bin value based no the received sensed value.
    ;; 4. Once a mote has received a tree message from all of its neighbors, it will
    ;;    transition to the DONE state and send a RPRT message to its parent containing its
    ;;    bin value.
    ;; Motes receiving a RPRT message will update their bin value and send it to their parent
    to step_IDLE
      if has-message "TREE" [ ;; Receiving TREE
        let msg received "TREE"
        let x (item 1 msg)
        let v (item 2 msg)
    
        set N fput v N ;; Update list of visited nodes
        if parent = [] [ ;; Check for first tree received
          set parent v ;; Store tree parent
          broadcast (list "TREE" s who) ;; Continue building tree
        ]
        if x != s and s = ["A" "B"] [ ;; Check for boundary node in A and B
          if x = ["B"] [set bin BinaryOR bin "0010"] ;; Node at boundary of A only
          if x = ["A"] [set bin BinaryOR bin "0100"] ;; Node at boundary of B only
          if x = [] [set bin BinaryOR bin "1000"] ;; Node at boundary of A and B
        ]
        if length N = length [who] of link-neighbors [ ;; If tree received from all neighbors
          if bin = "0000" and s = ["A" "B"] [set bin "0001"]
          if bin != "0000" [send (list "RPRT" bin) mote parent] ;; Initiate message to sink
          become "DONE"
        ]
        stop
      ]
    
      if has-message "RPRT" [ ;; Receiving RPRT
        let msg received "RPRT"
        let b (item 1 msg)
    
        if BinaryOR b bin != bin [ ;; Check for new data
          set bin BinaryOR b bin ;; Data aggregation
          send (list "RPRT" bin) (mote parent) ;; Forward aggregate data
        ]
        stop
      ]
    end
    
    ;; If a mote receives a RPRT message with new bin information, it sends it to its parent mote.
    to step_DONE
      if has-message "RPRT" [ ;; Receiving RPRT
        let msg received "RPRT"
        let b (item 1 msg)
        if BinaryOR b bin != bin [ ;; Check for new data
          set bin BinaryOR b bin ;; Data aggregation
          send (list "RPRT" bin) (mote parent) ;; Forward aggregate data
        ]
        stop
      ]
    end
    
    ;; Sink mote determines the topological relation using the bin values received.
    to step_SINK
      if has-message "RPRT" [ ;; Receiving RPRT
        let msg received "RPRT"
        let b (item 1 msg)
        set bin BinaryOR b bin ;; Data aggregation
        clear-output
        output-type translate bin ;; Topological relationship between A and B can be deduced using the translate function
        stop
      ]
    end
    
    ;; Determining topological relation based on bin value.
    to-report translate [num]
      if num = "0000" [report "A, B disjoint"]
      if num = "0010" [report "B contains A, A has no interior nodes"]
      if num = "0100" [report "A contains B, B has no interior nodes"]
      if num = "1000" or num = "1100" or num = "1010" or num = "0110" or num = "1110" [report "A, B meet"]
      if num = "0011" [report "A inside B"]
      if num = "0101" [report "A contains B"]
      if num = "1001" [report "A, B equal"]
      if num = "1111" or num = "0111" [report "A, B overlap"]
      if num = "1011" [report "A covered by B"]
      if num = "1101" [report "A covers B"]
      if num = "0001" [report "not possible"]
    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 = "parent" [set label parent] ;; Show mote parent
        if MoteLabel = "bin" [set label bin] ;; Show summary of non-empty intersections
      ]
    end
    

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