• Protocol 6.4: Hop-count flooding for dynamic environments

    PROTOCOL

    Hop-count flooding for dynamic environments, with sensor value trigger

    SUMMARY

    The algorithm starts with every mote that detects an environmental event / region broadcasting a message to its neighbors. The message contains a hop-count initialized at zero. Every time a mote receives a message, it checks the hop-count in the message. If the hop-count is lower than ten, the mote increments the hop-count by one and broadcasts the message to its neighbors.

    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, motes that have received messages appear mid-blue.
    • Activate the ShowLabels? switch to display the current hop count of each mote.
    • Use the RegionChangeInterval slider to change the interval that the region is changed.
    • 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.
    • Use the MoteMoveInterval slider to change the interval that the locations of motes are changed. The communication graph will be re-generated once the locations of motes are changed.
    • Use the CorrelatedRandomWalk switch to control the direction of mote movement. If this switch is turned on, a mote will change its heading based on a normal distribution with standard deviation of 45 degrees. If this switch is turned off, the mote will change its heading based on a uniform distribution.
    • Use the LevyFlight switch to control how fast a mote can move. If this switch is turned on, the distance between current position and next position is determined based on a normal distribution. If this switch is turned off, the mote moves at a constant speed.

    TRY

    • What happens when a smaller netsize value and a small region is used?
    • 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 motes being flooded?
    • 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.4

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

    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, Last time that motes locations are changed.
    globals [region_timestamp motes_timestamp]
    
    ;; Define a new breed of turtle called motes
    breed [motes mote]
    
    ;; Each mote can store the local variable s which is the sensed value.
    motes-own [s]
    
    ;; System setup and initialization
    to initialize
      make-single-region RegionSize ;; 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 [
        update-reading ;; Update locally sensed data
        set state "IDLE" ;; Set all motes to state IDLE
      ]
      set region_timestamp 0 ;; Reset the region change timestamp
      set motes_timestamp 0 ;; Reset the motes movement timestamp
    end
    
    ;; Generate sensed data
    to update-reading
      set color white
      set label "" ;; Clear label
      set messages []
      ifelse [region] of patch-here = ["A"]
        [set s 1] ;; When region detected, s equals 1
        [set s 0] ;; When region not detected, s equals 0
    end
    
    ;; Runs the hop-count flooding algorithm
    to go
      ask motes [ step ]
      tick
    
      ;; Update the locations of motes and communication graph when interval elapsed
      if (ticks - motes_timestamp) >= MoteMoveInterval [
        ask motes [
          move-mote CorrelatedRandomWalk LevyFlight ;; Next movement of mote      
        ]
        clear-links ;; Delete all existing links between motes          
        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
        set motes_timestamp ticks ;; Update the timestamp of mote location change    
        ask motes [update-reading] ;; Update sensed values of the motes
      ]
    
      ;; 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
        ]
        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 = "IDLE" [ step_IDLE stop ]
      if state = "DONE" [ step_DONE stop ]
    end
    
    ;; When a mote detects an environmental event, it broadcasts a message and transitions
    ;; into the DONE state.
    ;; When a message is received, it will be rebroadcast message only if the hop-count is
    ;; lower than the maximum hop-count of 10.
    to step_IDLE
      if s = 1 [ ;; Environmental event detected
        broadcast (list "MSGE" 0) ;; Broadcast MSGE to neighbors
        set state "DONE"
        stop
      ]
      if has-message "MSGE" [ ;; Receiving message
        let msg received "MSGE"
        set color 95 ;; Become mid-blue when message is received
        let h item 1 msg  ;; Hop count
        if ShowLabels? = true [set label h] ;; Show current hop count
        if h < 10 [ ;; Maximum hop count of 10
          broadcast (list "MSGE" (h + 1)) ;; Broadcast MSGE to neighbors
        ]
        stop
      ]
    end
    
    ;; When a mote no longer detects an environmental event, it transitions into the IDLE
    ;; state.
    ;; When a message is received, it will be rebroadcast message only if the hop-count is
    ;; lower than the maximum hop-count of 10.
    to step_DONE
      if s = 0 [ ;; Check for absence of environmental event
        set state "IDLE"
        stop
      ]
      if has-message "MSGE" [ ;; Receiving message
        let msg received "MSGE"
        set color 95 ;; Become mid-blue when message is received
        let h item 1 msg  ;; Hop count
        if ShowLabels? = true [set label h] ;; Show current hop count
        if h < 10 [ ;; Maximum hop count of 10
          broadcast (list "MSGE" (h + 1)) ;; Broadcast MSGE to neighbors
        ]
        stop
      ]
    end
    

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