PROTOCOL

Epidemic information diffusion for mobile nodes

SUMMARY

This protocol defines an epidemic infection count, e. When a node in the IDLE state senses an environmental event it transitions into the SEND stand and informs the next e neighbors it encounters before reverting back to the IDLE state.

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.
• Use the MoteLabel list to change the labels to either the mote id, sensed value or infection count. This will help show how the algorithm runs. When set to the sensed value, all motes within the region should have a value of 1, with the rest having a value of 0.
• 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.
• infection# determines the infection count for the algorithm.

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.
• What happens if the infection count is changed? Does this alter the coverage area?
• 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 alter the coverage area?
• 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.5

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

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 variables s which is the sensed value and ee which is the infection count.
motes-own [s ee]

;; 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
    become "IDLE" ;; Set all motes to state IDLE
    set ee infection# ;; Set the maximum number of neighbors that can receive the message
    set color white
    rt random-float 360 ;; Let the mote face a random direction
  ]
  set region_timestamp 0 ;; Reset the timestamp of the creation of new region
  set motes_timestamp 0 ;; Reset the timestamp of the creation of new mote locations and communication graph
end

;; Generate sensed data
to update-reading
  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 epidemic diffusion algorithm
to go
  ask motes [step]
  mote_labels ;; Changes the labels of the motes based on the MoteLabel dropdown list
  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 [ ;; When region changes, reset motes and update sensed values
        update-reading
        become "IDLE" ;; Set state to IDLE
        set messages [] ;; Clear messages    
        set ee infection# ;; Reset infection count
        set color white
      ]
    ]
  ]
end

;;
;; Mote protocols
;;

;; Step through the current state
to step
  if state = "IDLE" [ step_IDLE stop ]
  if state = "SEND" [ step_SEND stop ]
end

;; When a mote detects an environmental event, it transitions into the SEND state. If it
;; receives a message, it changes its color to mid-blue.
to step_IDLE
  if s = 1 [ ;; Check for presence of sensed variable    
    become "SEND"
  ]
  if has-message "MSGE" [ ;; Receiving message
    let msg received "MSGE"
    set color 95 ;; Become mid-blue when message is received
    stop
  ]
end

;; Motes in the SEND state will send ee messages where ee is the infection count before
;; reverting to the IDLE state.
;; Motes receiving the MSGE message will change their color to mid-blue.
to step_SEND
  let c_nbr count link-neighbors
  if c_nbr > 0 [ ;; Check for presence of sensed variable
    ifelse ee >= c_nbr  ;; If the infection count is larger the amount of neighbors
    [
      broadcast (list "MSGE") ;; Broadcast MSGE to neighbors
      set ee (ee - c_nbr) ;; Reduce the infection count by the amount of neighbors
    ]
    [ ;; If the amount of neighbors is larger than the infection count
      send (list "MSGE") n-of (ee) link-neighbors ;; Send MSGE to ee arbitrarily chosen neighbors
      set ee 0
      become "SEND"
    ]
    if ee = 0 [ ;; If infected sufficient neighbors
      set ee infection# ;; Infection count reset
      become "IDLE" ;; Revert to IDLE state
    ]
  ]
  if has-message "MSGE" [ ;; Receiving message
    let msg received "MSGE"
    set color 95 ;; Become mid-blue when message is received
    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 = "infection count" [set label ee] ;; Show epidemic infect count
  ]
end

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