• Protocol 5.6: GPSR – greedy perimeter stateless routing

    PROTOCOL

    GPSR – Greedy Perimeter Stateless Routing

    SUMMARY

    GPSR combines face routing with greedy georouting to route a message from a source to a destination. When deciding which neighbor to send the message to, motes collect position data from their neighbors and make a decision based on the following criteria:
    1. No target distance and there is a neighbor closer to the destination; send message to neighbor via greedy georouting.
    2. No target distance and there are no neighbors closer to the destination; face route message to next neighbor in an anticlockwise direction from the destination and set the target distance.
    3. One of the neighbors is closer to the destination than the target distance; send message to neighbor via greedy georouting and reset the target distance.
    4. No neighbors are closer to the destination than the target distance; face route message to next neighbor in an anticlockwise direction from the previous mote.

    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 source mote is yellow and the sink mote is red. Both are larger than the other motes.
    • The message path is orange when using greedy georouting and yellow when using face routing.
    • Use the MoteLabel list to change the labels to the mote id.

    TRY

    • What happens if the communication distance is too small, making a disconnected network? Does the algorithm still route the message? Change this by adjusting the c slider.
    • Try selecting UDG or RNG from the NetworkStructure drop-down box to change the network shape to a Unit Distance Graph or Relative Neighborhood Graph. Does the algorithm run any differently for planar and non-planar graphs?
    • 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.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 5.6

    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 N which is the set of neighbor locations,
    ;; m which is the message, d which is the coordinates of the sink mote, f which is the 
    ;; coordinates of the face routing mote and t which is the target distance.
    motes-own [N m d f t]
    
    ;; 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
        set N []
      ]
      let sink one-of motes ;; Selecting the sink mote
      ask sink [
        set color red
        set size (size * 1.5) ;; The sink mote is larger than other motes
      ]
      ask one-of motes [ ;; Selecting the source mote
        become "SEND"
        set size (size * 1.5) ;; The source mote is larger than other motes
        set m "'Hello!'"
        set color yellow
        set d (list [xcor] of sink [ycor] of sink) ;; Setting destination coordinates
      ]
    end
    
    ;; Runs the GPSR 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 ]
      if state = "LSTN" [ step_LSTN stop ]
    end
    
    ;; Sends an INIT message to neighbors, then waits for a response.
    to step_SEND
      set messages [] ;; Clear any messages
    
      broadcast (list "INIT" who) ;; Broadcast 'ping' to neighbors
      become "LSTN" ;; Change state to listen for responses to 'ping'
    end
    
    ;; Motes in the IDLE state respond to an INIT message by sending back their coordinates.
    ;; Motes respond to a GRDY message by determining if they are the sink mote. If they are,
    ;; they shout the relayed message. If they aren't, they store the message and destination
    ;; coordinates and transition into the SEND state.
    ;; Motes respond to a FACE message by determining if they are the sink mote. If they are,
    ;; they shout the relayed message. If they aren't, they store the message, destination
    ;; coordinates, face routing coordinates and the target distance before transitioning to
    ;; the SEND state.
    to step_IDLE
      if has-message "INIT" [ ;; Receiving INIT message
        let msg received "INIT"
        let p (list xcor ycor) ;; Motes position
        broadcast (list "POSN" p) ;; Broadcast location in response to 'ping' message
        stop
      ]
    
      if has-message "GRDY" [ ;; Receiving GRDY message
        let msg received "GRDY"
        let m' item 1 msg
        let d' item 2 msg
        let p (list xcor ycor) ;; Motes position
        ifelse p = d' [ ;; Check if this node location is the destination for this message
          show (word "Message " m' " received!") ;; The message has been successfully received at the destination
        ]
        [
          set m m' ;; Store the message and the destination
          set d d'
          become "SEND"
        ]
        stop
      ]
    
      if has-message "FACE" [ ;; Receiving FACE message
        let msg received "FACE"
        let m' item 1 msg ;; Message m'
        let d' item 2 msg ;; Destination d'
        let f' item 3 msg ;; Previous node f
        let t' item 4 msg ;; Target distance t
        let p (list xcor ycor) ;; Motes position
        ifelse p = d' [
          show (word "Message " m' " received!") ;; The message has been successfully received at the destination
        ]
        [
          set m m' ;; Store FACE message payload
          set d d'
          set f f'
          set t t'
          become "SEND"
        ]
        stop
      ]
    end
    
    ;; Motes in the LSTN state collect position data from their neighbors via POSN messages.
    ;; Once the data has been received from all motes, it will pass the message along in four 
    ;; ways depending on the following criteria:
    ;; 1. No target distance and there is a neighbor closer to the destination; send message
    ;;    to neighbor via greedy georouting.
    ;; 2. No target distance and there are no neighbors closer to the destination; face route
    ;;    message to next neighbor in an anticlockwise direction from the destination.
    ;; 3. One of the neighbors is closer to the destination than the target distance; send
    ;;    message to neighbor via greedy georouting.
    ;; 4. No neighbors are closer to the destination than the target distance; face route
    ;;    message to next neighbor in an anticlockwise direction from the previous mote.
    to step_LSTN
      if has-message "POSN" [ ;; Receiving POSN message
        let msg received "POSN"
        let l item 1 msg
        set N fput l N ;; Store received neighbor location
        if length N = count link-neighbors [ ;; Check if messages received from all neighbors
          let p (list xcor ycor) ;; Motes position
    
          let n. first N
          foreach N [ ;; Position of neighbor closest to destination
            let n' ?
            if dist d n' <= dist d n. [ ;; If current neighbor is closer to destination
              set n. n'
            ]
          ]
    
          ifelse t <= 0 [ ;; Message received through greedy georouting
            ifelse dist n. d < dist p d [
              let nextmote first [who] of motes with [xcor = item 0 n. and ycor = item 1 n.]
              ask link-with mote nextmote [ ;; Making the path taken by the message thick and orange in color
                set color orange
                set thickness 0.15
              ]
              send (list "GRDY" m d) mote nextmote ;; Forward message using greedy georouting
            ]
            [ ;; No neighboring mote closer to destination
              foreach N [ ;; Position of neighbor with the smallest angle between itself, current mote and destination
                let n' ?
                if angle d p n' <= angle d p n. [ ;; If angle with current neighbor is smaller
                  set n. n'
                ]
              ]
              let nextmote first [who] of motes with [xcor = item 0 n. and ycor = item 1 n.]
              ask link-with mote nextmote [ ;; Making the path taken by the message thick and yellow in color
                set color yellow
                set thickness 0.15
              ]
              send (list "FACE" m d p (dist p d)) mote nextmote ;; Forward message using face routing
            ]
          ]
    
          [ ;; Message received through face routing (t > 0)
            ifelse dist n. d < t [ ;; One neighbor is closer than target distance
              let nextmote first [who] of motes with [xcor = item 0 n. and ycor = item 1 n.]
              ask link-with mote nextmote [ ;; Making the path taken by the message thick and orange in color
                set color orange
                set thickness 0.15
              ]
              send (list "GRDY" m d) mote nextmote ;; Forward message using greedy georouting
            ]
            [
              foreach N [ ;; Position of next neighbor anticlockwise from the previous (face) mote
                let n' ?
                if angle f p n' <= angle f p n. [ ;; If angle with current neighbor is smaller
                  set n. n'
                ]
              ]
              let nextmote first [who] of motes with [xcor = item 0 n. and ycor = item 1 n.]
              ask link-with mote nextmote [ ;; Making the path taken by the message thick and yellow in color
                set color yellow
                set thickness 0.15
              ]
              send (list "FACE" m d p t) mote nextmote ;; Forward message using face routing
            ]
          ]
          set t 0
          set N []
          become "IDLE"
          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.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,281 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>