• Protocol 4.6: Rumor routing

    PROTOCOL

    Rumor routing

    SUMMARY

    The algorithm needs two events to occur in order to run; an environmental event (the green patch) which triggers a gossiping message RSRC and an external event triggered by the user which initiates a random walk message RQST. Both these messages leave a breadcrumb trail back to their sources using the predecessor id’s is and iq respectively. The RSRC message can optimize the route to the source as it makes use of a hopcount so that motes receiving a RSRC message with a smaller hopcount to the source will update their breadcrumbs accordingly. When the RQST message meets a mote that has been reached by the RSRC message, it follows the breadcrumb trail back to the environmental events source which then shouts “Request routed to source”.

    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.
    • Click on any mote to initiate the external event.

    NOTICE

    The RQST message will have links that are thick and orange. When this message reaches a mote with the RSRC message and follows it back to the source, the links will be thick and black.
    Use the MoteLabel list to change the labels to either the mote id, resource predecessor id: is, resource hop count: hs, request predecessor id: iq or request hop count: hq. This will help show how the algorithm runs.

    TRY

    • What happens when a small or large region is used? Does this affect the RSRC messages coverage?
    • What happens when more than one external event has been triggered? Try this by clicking one more than one mote when the algorithm is running.
    • What happens when a very small g value is used? Does it take longer for the algorithm to complete? Try this by adjusting the g value.
    • What happens if the communication distance is too small, making a disconnected network? Change 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 the algorithm run any faster?
    • 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.6

    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.6: Rumor routing

    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"]
    ;; Define a new breed of mote called motes
    breed [motes mote]
    
    ;; Each mote can store the local variables external, which indicates whether an event has
    ;; been triggered, Resource predecessor id: is, Resource hop count: hs,
    ;; Request predecessor id: iq and Request hop count: hq
    motes-own [external is hs iq hq]
    
    ;; 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 [
        become "IDLE" ;; Set all motes to state IDLE
        set external false
        set is 0
        set iq 0
        set hs 0
        set hq 0
      ]
    end
    
    ;; Runs the rumor routing algorithm
    to go
      ask motes [ step ]
      mote_labels ;; Changes the labels of the motes based on the MoteLabel dropdown list
      ExternalEvent ;; When the user clicks on a mote, it triggers an external event
      tick
    end
    
    ;;
    ;; Mote protocols
    ;;
    
    ;; Step through the current state
    to step
      if state = "IDLE" [ step_IDLE stop ]
      if state = "EVNT" [ step_EVNT stop ]
      if state = "DONE" [ step_DONE stop ]
    end
    
    ;; Motes that have not heard about the resource
    to step_IDLE
      if [region] of patch-here = ["A"] [ ;; When environmental event detected
        become "EVNT"
        set hs 0
        let r random-float 1
        if r < g [
          send (list "RSRC" 1 who) one-of link-neighbors ;; Gossip resource to random neighbor
        ]
        stop
      ]
    
      if external = true [ ;; When external request initiated
        send (list "RQST" who) one-of link-neighbors ;; Send request to random neighbor
        set external false
        stop
      ]
    
      if has-message "RSRC" [ ;; Receiving RSRC
        let msg received "RSRC"
        become "EVNT"
        set hs item 1 msg ;; Store hop count
        set is item 2 msg ;; Store resource predecessor
        send (list "RSRC" (hs + 1) who) one-of link-neighbors ;; Send resource message to random neighbor
        stop
      ]  
    
      if has-message "RQST" [ ;; Receiving RQST
        let msg received "RQST"
        set iq item 1 msg ;; Store breadcrumb to request predecessor
        send (list "RQST" who) one-of link-neighbors ;; Send request message to random neighbor
        ask link-with mote iq [ ;; Display RQST path thick and in orange
          set color orange
          set thickness 0.15
        ]
        stop
      ]
    end
    
    ;; Motes that have heard about the resource
    to step_EVNT
      ;; When external request initiated
      if external = true [
        ifelse hs = 0 [ ;; If source reached
          become "DONE"
          show "Request received at EVNT source"
        ]
        [
          send (list "RQST" who) mote is ;; Follow request breadcrumb
        ]
        set external false
        stop
      ]
    
      if has-message "RSRC" [ ;; Receiving RSRC
        let msg received "RSRC"
        let h item 1 msg
        if h < hs [ ;; If there is a shorter root to the resource
          set hs h ;; Store shorter resource hop count
          set is item 2 msg ;; Store shorter resource predecessor
        ]
        send (list "RSRC" (hs + 1) who) one-of link-neighbors ;; Send resource message to random neighbor
        stop
      ]
    
      if has-message "RQST" [ ;; Receiving RQST
        let msg received "RQST"
        ifelse hs = 0 [ ;; If source reached
          show "Request routed to source"
          ask link-with mote (item 1 msg) [ ;; Display RQST path thick and in black
            set color black
            set thickness 0.15
          ]
          become "DONE"
        ]
        [
          set iq item 1 msg ;; Store request predecessor
          send (list "RQST" who) mote is ;; Follow resource breadcrumb
          ask link-with mote iq [ ;; Display RQST path thick and in orange
            set color black
            set thickness 0.15
          ]
        ]
        stop
      ]
    end
    
    ;; Source motes that have received a request about the event
    to step_DONE
    end
    
    ;; When the user clicks on a mote, it triggers an external event
    to ExternalEvent
      if mouse-down? [
        let n min-one-of motes [distancexy mouse-xcor mouse-ycor]
        ask n [set external true]
      ]
    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 = "is" [set label is] ;; Show resource predecessor id
        if MoteLabel = "hs" [set label hs] ;; Show resource hop count
        if MoteLabel = "iq" [set label iq] ;; Show request predecessor id
        if MoteLabel = "hq" [set label hq] ;; Show request hop count
        if MoteLabel = "mote id" [set label who] ;; Show mote id
      ]
    end
    

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