• Protocol 5.5: Face routing

    PROTOCOL

    Face Routing

    SUMMARY

    The purpose of Face Routing is to show how faces in the network can be routed around. After the SEND mote sends out its INIT message, motes in the IDLE state relay that message along by selecting the next neighbor in the anti-clockwise direction. All of these messages will eventually arrive back at the SEND mote which will report that it has received the message.

    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 initiating mote is larger than the other motes.
    • The path taken by the INIT message is thick and orange in color.
    • The send mote should receive a message for each of its neighbors.
    • Use the MoteLabel list to change the labels to the mote id.
    • What happens when the send mote is at the edge of the network?

    TRY

    • 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 the algorithm run any differently for planar and non-planar graphs?
    • What happens if the communication distance is too small, making a disconnected network? Does the algorithm still produce a Gabriel Graph? Change this by adjusting the c slider.
    • 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 5.5

    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 5.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"]
    ;; Define a new breed of turtle called motes
    breed [motes mote]
    
    ;; 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 INIT
      ask one-of motes [
        set size (size * 1.5) ;; The SEND mote is larger than other motes
        become "SEND" ;; Set one mote to state SEND
        broadcast (list "INIT" who) ;; Broadcast 'ping' with id to neighbors
      ]
    end
    
    ;; Runs the face routing 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 = "SEND" [ step_SEND stop ]
      if state = "IDLE" [ step_IDLE stop ]
    end
    
    ;; Sends an INIT message to neighbors, then waits for a response.
    to step_SEND
      if has-message "INIT" [ ;; Receiving INIT message
        let msg received "INIT"
        show "Message routed around face"
        stop
      ]
    end
    
    ;; Motes in the IDLE state respond to an INIT message by passing the message along to
    ;; the next neighbor in the anti-clockwise direction.
    to step_IDLE
      if has-message "INIT" [ ;; Receiving INIT message
        let msg received "INIT"
        let i item 1 msg
        send (list "INIT" who) (mote cyc i) ;; Route message to next neighbor in cyclic order
        ask link-with mote cyc i [ ;; Making the path taken by the message thick and orange in color
          set color orange
          set thickness 0.15
        ]
        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
      ]
    end
    

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

Leave a Reply

Your email address will not be published. Required fields are marked *

*

* Copy this password:

* Type or paste password here:

8,253 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>