Greedy georouting protocol
The purpose of Greedy Georouting is to relay a message between two motes on the same network. After the source and sink mote have been selected, the source mote is given the coordinates of the sink mote. The source mote then sends the message to the neighbor with the closest Euclidean distance to the sink mote. This continues until the message has been relayed to the sink mote.
Code designed by Matt Duckham. Additional coding by Alan Both.
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.
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 m which is the message, N which is the set of ;; neighbor locations and d which is the coordinates of the sink mote. motes-own [m N d] ;; 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 N  become "IDLE" ;; Set all motes to state IDLE ] 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 set size (size * 1.5) ;; The source mote is larger than other motes set m "'Hello!'" become "SEND" set color yellow set d (list [xcor] of sink [ycor] of sink) ;; Setting destination coordinates ] end ;; Runs the greedy georouting 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 a PING message to neighbors, then transitions into the LSTN state. to step_SEND broadcast (list "PING") ;; Broadcast 'ping' to neighbors become "LSTN" ;; Change state to listen for responses to 'ping' end ;; Motes in the IDLE state respond to a PING message by sending back their coordinates ;; and respond to a MSGE message by determining if it is the sink mote. If it is, it ;; shouts the relayed message. If it isn't, it stores the message and destination ;; coordinates and transitions into the SEND state. to step_IDLE if has-message "PING" [ ;; Receiving PING message let msg received "PING" let p (list xcor ycor) broadcast (list "POSN" p) ;; Broadcast location in response to 'ping' message stop ] if has-message "POSN" [ ;; Ignore POSN message let msg received "POSN" stop ] if has-message "MSGE" [ ;; Receiving MSGE message let msg received "MSGE" let m' item 1 msg let d' item 2 msg ifelse (list xcor ycor) = 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 become "DONE" ] [ set m m' ;; Store the message and the destination set d d' become "SEND" ] stop ] end ;; Motes in the LSTN state wait until they have received POSN messages from all of its ;; neighbors. They then determine the neighbor with the closest Euclidean distance to the ;; sink mote. It then sends the relayed message to that neighbor. 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 min-dist 1000000 ;; Arbitrarily large initial distance let min-loc  foreach N [ let n' ? if min-dist > dist n' d [ ;; Find closest neighbor set min-dist dist n' d set min-loc n' ] ] send (list "MSGE" m d) one-of motes with [(list xcor ycor) = min-loc] ;; Forward message to next neighbor ask link-with one-of motes with [(list xcor ycor) = min-loc] [ set color orange set thickness 0.15 ] 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.3.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).