• Protocol 4.8: Establishing a rooted shortest path tree

    PROTOCOL

    Establishing a rooted shortest path tree

    SUMMARY

    The algorithm starts with the root mote broadcasting its id and a hop count to its neighbors. When these motes receive the message they set that mote as their parent, set their hop count to the received hop count plus one and broadcast the message to their neighbors. If a message is received that has a smaller hop count, the mote will change their parent and hop count and then broadcast the message to their neighbors again.

    OPERATION

    • Click the Setup button to generate a network on communication distance and network size.
    • Click the Go! button to run the algorithm.

    NOTICE

    • As the message is passed along the network links, the links should change color from grey to orange.
    • Use the MoteLabel list to change the labels to either the mote id, parent id or hop count. This will show how the tree is structured.

    TRY

    • What happens if the communication distance is too small, making a disconnected network? Try this by moving the c slider to the minimum.
    • Try selecting GG or RNG from the NetworkStructure drop-down box to change the network shape to a Gabriel Graph or Relative Neighborhood Graph before pressing go. Does the algorithm run any differently?
    • Try selecting Tree Links from the ShowLinks drop-down box to get a better idea of how the network is structured.
    • 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.8

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

    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 hop count, r as a local variable
    motes-own [r]
    
    ;; 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 [
        set r 0
        set parent -1
        become "IDLE" ;; Set all motes to state IDLE
      ]
      ask one-of motes [
        become "ROOT" ;; Set one mote to state ROOT
      ]
    end
    
    ;; Runs the shortest path tree algorithm
    to go
      ask motes [ step ]
      mote_labels ;; Changes the labels of the motes based on the MoteLabel dropdown list
      show_links ;; Changes the visibility of links based on the ShowLinks dropdown list
      tick
    end
    
    ;;
    ;; Mote protocols
    ;;
    
    ;; Step through the current state
    to step
      if state = "ROOT" [ step_ROOT stop ]
      if state = "IDLE" [ step_IDLE stop ]
      if state = "DONE" [ step_DONE stop ]
    end
    
    ;; The root mote broadcasts its id and then changes state to done
    to step_ROOT
      broadcast (list "TREE" who 0) ;; Broadcast mote id and hop count
      set messages [] ;; Clearing all messages
      become "DONE"
    end
    
    ;; When these motes receive the message they set the mote as their parent, broadcast 
    ;; their own id, kill off all of their links, make a link with their parent node and
    ;; transition to the DONE state
    to step_IDLE
      if has-message "TREE" [ ;; Receiving TREE
        let msg received "TREE"
        set parent item 1 msg ;; Set this motes parent id
        set r (item 2 msg + 1) ;; Set hop count
        become "DONE"
        broadcast (list "TREE" who r) ;; Broadcast mote id and hop count
        ask link-with mote parent [set color orange]
        stop
      ]
    end
    
    ;; The mote has finished generating the tree
    to step_DONE
      if has-message "TREE" [ ;; Receiving TREE
        let msg received "TREE"
        let h (item 2 msg + 1) ;; Set messages hop count as h
        if h < r [ ;; If received hop count is lower than stored hop count
          set parent item 1 msg ;; Set this motes parent id
          set r h ;; Set received hop count as motes hop count
          broadcast (list "TREE" who r) ;; Broadcast mote id and hop count
          ask link-with mote parent [set color orange] ;; Change color of link with parent
        ]
        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 = "parent" [set label parent] ;; Show mote parent
        if MoteLabel = "hop count" [set label r] ;; Show hop count
      ]
    end
    
    ;; This removes all non tree links to make the tree network easier to see
    to show_links
      if ShowLinks = "All Links" [ask links [show-link]] ;; Show all of the links
      if ShowLinks = "Tree Links" [
        ask links [hide-link] ;; Hide all links
        ask motes [ ;; Show link with parent unless you are the root mote
          if parent != -1 [ask link-with mote parent [show-link]]
        ]
      ]
    end
    

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