Routing around a boundary cycle (see Protocol 5.7)
This algorithm is an extension of Protocol 5.7 which enables the routing of a message around the boundary. Once a boundary mote has determined its wind value, it sends a message to it and transitions into the BNDY state. Motes in the BNDY state will forward these messages along to their wind neighbors whereas motes in the IDLE state will use the id of the previous mote and the cyc function to pass the message along.
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" "../env.nls"] ;; Define a new breed of turtle called motes breed [motes mote] ;; Each mote can store the local variables s which is the sensed value of the region, ;; D which is the table containing the sensed values and id's of neighbors and wind ;; which is the id of the next mote in the boundary cycle. motes-own [s D wind] ;; System setup and initialization to initialize make-single-region "medium" ;; 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 [ ifelse [region] of patch-here = ["A"] [set s 1] ;; When region detected, s equals 1 [set s 0] ;; When region not detected, s equals 0 set D  set wind "NULL" become "INIT" ;; Set all motes to state INIT ] while [any? motes with [s = 1 and count link-neighbors with [s = 1] < 2]] [ ;; Ensuring that motes inside the region are at least 2-connected ask motes with [s = 1 and count link-neighbors with [s = 1] < 2] [die] ] end ;; Runs the routing around a boundary cycle 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 = "INIT" [ step_INIT stop ] if state = "IDLE" [ step_IDLE stop ] if state = "BNDY" [ step_BNDY stop ] end ;; All motes broadcast their sensed value and id to their neighbors and transition into ;; the IDLE state to step_INIT broadcast (list "PING" who s) ;; Broadcast sensed value and identifier become "IDLE" end ;; Motes in the IDLE state store the sensed values and ids of their neighbors and then ;; determine if they are boundary motes. If so they set their wind value to the id of ;; the next mote in the boundary cycle, send off a MSGE and transition into the BNDY ;; state. ;; Any motes in the IDLE state receiving the MSGE will forward it to the next neighbor ;; in the boundary cycle using the cyc function and the id of the previous mote. to step_IDLE if has-message "PING" [ ;; Receiving PING message let msg received "PING" let i. item 1 msg let d. item 2 msg set D fput (list i. d.) D ;; Store neighbor identifier and sensed value if length D = count link-neighbors [ ;; Check whether PING received from all neighbors let I  ;; Creating the I function foreach D [ let i' item 0 ? let d' item 1 ? set I fput d' I ;; The I function is populated with d values from the D table ] if s = 1 and member? 0 I [ ;; Check for node inside region with neighbor outside let tmp.i 0 let tmp.d 0 foreach D [ let i' item 0 ? let d' item 1 ? if d' = 0 [ set tmp.i i' ] ] while [tmp.d = 0] [ ;; Finding the first neighbor that has a sensed value of set tmp.i cyc tmp.i ;; 1, in an anticlockwise direction from a neighbor with foreach D [ ;; a sensed value of 0 let i' item 0 ? let d' item 1 ? if i' = tmp.i [ set tmp.d d' ] ] ] set wind tmp.i ;; Setting this neighbor as the wind value send (list "MSGE" who who) (mote wind) ;; Initiate message to first boundary neighbor become "BNDY" ] ] stop ] if has-message "MSGE" [ ;; Receiving MSGE message let msg received "MSGE" let i item 1 msg let i' item 2 msg send (list "MSGE" i who) (mote cyc i') ;; Forward message to next boundary cycle neighbor stop ] end ;; Motes in the BNDY state will either forward messages to the next boundary neighbor ;; using the wind value or if they are the original sender of the message, will shout ;; that the message had traversed the entire boundary. to step_BNDY if has-message "MSGE" [ ;; Receiving MSGE message let msg received "MSGE" let i item 1 msg let i' item 2 msg ifelse i = who [ ;; Check whether message returned to sender show "Message traversed entire boundary!" ] [ send (list "MSGE" i who) (mote wind) ;; Forward message to next boundary neighbor ] stop ] end ;; Changing the labels of the motes based on the MoteLabel dropdown list to mote_labels ask motes [ set label "" ;; Hide the label if MoteLabel = "mote id" [set label who] ;; Show mote id if MoteLabel = "wind" [if wind != "NULL" [set label wind]] ;; Show wind value if MoteLabel = "s" [set label s] ;; Show s value ] end
The NetLogo procedures for this applet can be downloaded directly as: Protocol5.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).