• Protocol 4.13: Hop count sweep

    PROTOCOL

    Hop count sweep

    SUMMARY

    The hop count sweep generates a coordinated front (sweep line) which proceeds as vertical line from the left section of the network to the right.

    Motes in the leftmost position initiate the sweep line in the INIT state, generating a minimum hop count function from the sweep line, inviting neighbors to join the sweep function and transitioning into the SWPT state. IDLE motes can only transition to the FRNT state if they are adjacent to a SWPT node and no adjacent FRNT or IDLE motes have a lower hop count. FRNT nodes can only transition to the SWPT state if adjacent FRNT motes have the same hop count and adjacent IDLE motes have a larger hop count.

    OPERATION

    • 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 sweep front should proceed as a vertical line of yellow FRNT motes, with dark blue SWPT motes to the left and light blue IDLE motes to the right.
    • Use the MoteLabel list to change the labels to either the mote id, the hop count for the FRNT motes or the hop count for all of the motes.

    TRY

    • What happens when a small or large network size is used? Does this affect the sweep line?
    • 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. Does this alter the sweep fronts’ coordination?
    • 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.13

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

    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"]
    ;; Define a new breed of turtle called motes
    breed [motes mote]
    
    ;; Each mote can store the local variables hop count, a list of accept neighbors (unsw)
    ;; and a list of confirm neighbors (swep)
    motes-own [hop unsw swep]
    
    ;; System setup and initialization
    to initialize
      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 [
        become "IDLE" ;; Set all motes to state IDLE
        set hop -1
        set unsw []
        set swep []
      ]
      ask min-n-of 15 motes [xcor] [
        become "INIT" ;; Initializing the sweep line
        set color yellow
      ]
    end
    
    ;; Runs the sweep 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 = "IDLE" [ step_IDLE stop ]
      if state = "FRNT" [ step_FRNT stop ]
      if state = "SWPT" [ step_SWPT stop ]
    end
    
    ;; Motes in the INIT state initialize the sweep front before transitioning to the SWPT
    ;; state
    to step_INIT
      if ticks = 1 [ ;; On the first tick broadcast a ping message
        set hop 0 ;; Reset hop count
        broadcast (list "PING" hop) ;; Initiate hop count potential function
      ]
      if ticks > 20 [ ;; Wait until hop 21 to broadcast first INVT
        broadcast (list "INVT" hop) ;; Initiate sweep algorithm inviting neighbors to join
        become "SWPT"
      ]
    end
    
    ;; Motes receiving a PING message will update their hop count if the received value is
    ;; lower before broadcasting their updated hop count.
    ;; Motes receiving an INVT message will respond by broadcasting an "UNSW" message along
    ;; with their hop count and id.
    ;; Motes receiving a SWEP message will broadcast a CONF message along with their id and a
    ;; b value to the receiving mote. The b value is true only if the received hop count is
    ;; exactly one lower lower than the motes' hop count.
    ;; Motes receiving an UNSW message will broadcast an ACPT message along with their id and 
    ;; a b value. The b value is true only if the received hop count is equal to or lower
    ;; than the motes' hop count.
    ;; Motes receiving an ACPT message will add the received motes' id to their unsw table
    ;; only if the received mote is in the SWPT state or has a lower hop count. If all
    ;; neighboring motes meet these conditions, the mote transitions into the FRNT state.
    to step_IDLE
      if has-message "PING" [ ;; Receiving PING
        let msg received "PING"
        let h item 1 msg ;; Received hop count
        if (h + 1) < hop or hop < 0 [ ;; Construct shortest path hop count potential function
          set hop h + 1 ;; Update hop count
          broadcast (list "PING" hop) ;; Continue construction of hop count potential function
        ]
        stop
      ]
    
      ;; Note --- there is an error here. Events should be enclosed in 
      ;; "if" rather than "while" statements. As a result, it is possible
      ;; for unfair executions, where one type of message always dominates another
      ;; This error led to some of the issues discussed in chapter 7 of the book
      ;; associated with this code.
      while [has-message "INVT"] [ ;; Receiving INVT
        let msg received "INVT"
        broadcast (list "UNSW" hop who) ;; If invited, check for unswept neighbors
      ]
    
      while [has-message "SWEP"] [ ;; Receiving SWEP
        let msg received "SWEP"
        let h item 1 msg ;; Received hop count
        let i item 2 msg
        ifelse h = hop - 1 ;; If received hop count is lower
          [send (list "CONF" true who) mote i]
          [send (list "CONF" false who) mote i]
      ]    
    
      while [has-message "UNSW"] [ ;; Receiving UNSW
        let msg received "UNSW"
        let h item 1 msg ;; Received hop count
        let i item 2 msg
        ifelse h <= hop ;; If received hop count is higher, invite can be accepted
          [send (list "ACPT" true who) mote i]
          [send (list "ACPT" false who) mote i]
      ]
    
      while [has-message "ACPT"] [ ;; Receiving ACPT
        let msg received "ACPT"
        let b item 1 msg ;; Received confirm or no
        let i item 2 msg
        if b and not member? i unsw [
          set unsw fput i unsw ;; Add neighbor to unswept list
        ]
        if length unsw = count link-neighbors [ ;; If all neighbors are in unsw list
         become "FRNT" ;; Accept invitation once all neighbors respond
        ]
      ]
    end
    
    ;; Motes receiving a PING message will update their hop count if the received value is
    ;; lower before broadcasting their updated hop count.
    ;; Motes receiving a CONF message will add the received motes' id to their swep table
    ;; only if the received mote is in the UNSW state with the same hop count or in the IDLE
    ;; state with a greater hop count. If all neighboring motes meet these conditions, the
    ;; mote transitions into the SWPT state.
    ;; Motes receiving a SWEP message will broadcast a CONF message along with their id and a
    ;; b value. The b value is true only if the received hop count is equal to the motes'
    ;; hop count.
    ;; Motes receiving an UNSW message will broadcast an ACPT message along with their id and 
    ;; a b value. The b value is true only if the received hop count is equal to or lower
    ;; than the motes' hop count.
    to step_FRNT
      set color yellow
      if length messages = 0 [ ;; Spontaneously
        broadcast (list "SWEP" hop who)
      ]
    
      if has-message "PING" [ ;; Receiving PING
        let msg received "PING"
        let h item 1 msg ;; Received hop count
        if (h + 1) < hop or hop < 0 [ ;; Construct shortest path hop count potential function
          set hop h + 1 ;; Update hop count
          broadcast (list "PING" hop) ;; Continue construction of hop count potential function
        ]
        stop
      ]
    
      while [has-message "CONF"] [ ;; Receiving CONF
        let msg received "CONF"
        let b item 1 msg ;; Received confirm or no
        let i item 2 msg
        if b and not member? i swep [
          set swep fput i swep ;; Add neighbor to swept list
        ]
        if length swep = count link-neighbors [ ;; If all neighbors are in unsw list
          broadcast (list "INVT" hop) ;; Broadcast new invite
          become "SWPT"
        ]
      ]
    
      while [has-message "SWEP"] [ ;; Receiving SWEP
        let msg received "SWEP"
        let h item 1 msg ;; Received hop count
        let i item 2 msg
        ifelse h = hop ;; Check sweep condition
          [send (list "CONF" true who) mote i]
          [send (list "CONF" false who) mote i]
      ]  
    
      while [has-message "INVT"][ ;; Do nothing
        let msg received "INVT"
      ]
    
      while [has-message "ACPT"][ ;; Do nothing
        let msg received "ACPT"
      ]
    
      while [has-message "UNSW"] [ ;; Receiving UNSW
        let msg received "UNSW"
        let h item 1 msg ;; Received hop count
        let i item 2 msg
        ifelse h <= hop ;; If received hop count is higher, invite can be accepted
          [send (list "ACPT" true who) mote i]
          [send (list "ACPT" false who) mote i]
      ]
    end
    
    ;; Motes receiving a SWEP message will broadcast a CONF message along with their id and a
    ;; b value. The b value is true.
    ;; Motes receiving an UNSW message will broadcast an ACPT message along with their id and 
    ;; a b value. The b value is true.
    to step_SWPT
      set color 104 ;; Dark blue
      while [has-message "SWEP"] [ ;; Receiving SWEP
        let msg received "SWEP"
        let h item 1 msg ;; Received hop count
        let i item 2 msg
        send (list "CONF" true who) mote i ;; Swept motes can always respond to conf message
      ]  
    
      while [has-message "INVT"][ ;; Do nothing
        let msg received "INVT"
      ]
    
      while [has-message "PING"][ ;; Do nothing
        let msg received "PING"
      ]
    
      while [has-message "UNSW"] [ ;; Receiving UNSW
        let msg received "UNSW"
        let h item 1 msg ;; Received hop count
        let i item 2 msg
        send (list "ACPT" true who) mote i ;; Swept motes can always respond to unsw message
      ]
    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" [
        ask motes [set label "who"] ;; Show mote id
      ]
      if MoteLabel = "hop count (front)" [
        ask motes with [state = "FRNT"] [set label hop] ;; Motes in the FRNT state show their hop count
      ]
      if MoteLabel = "hop count (all)" [
        ask motes [set label hop] ;; All motes show their hop count
      ]
    end
    

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