Establishing a bidirected rooted tree
The algorithm starts with the root mote broadcasting its id to its neighbors. When these motes receive the message they set that mote as their parent, broadcast their own id and parent id to their neighbors, kill off all of their links and make a link with the parent mote. They then listen for any messages that list them as a parent and add these motes to their children list.
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] ;; 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 children  ;; Make children an empty list set parent -1 become "IDLE" ;; Set all motes to state IDLE ] ask one-of motes [become "ROOT"] ;; Set one mote to state ROOT end ;; Runs the bidirected tree 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 = "ROOT" [ step_ROOT stop ] if state = "IDLE" [ step_IDLE stop ] if state = "DONE" [ step_DONE stop ] end ;; The root mote broadcasts its id and then changes state to done to step_ROOT broadcast (list "TREE" who -1) ;; Broadcast mote id set messages  ;; Clearing all messages become "DONE" end ;; When these motes receive the message they set the mote as their parent, broadcast ;; their own id and parent id, kill off all of their links, make a link with their ;; parent node and transition to the DONE state to step_IDLE if has-message "TREE" [ ;; Receiving TREE let msg received "TREE" set parent item 1 msg ;; Set this motes parent id become "DONE" ;; Become done set messages  ;; Clearing all messages create-link-with mote parent ;; The parent mote has already severed the link so it needs to be restored broadcast (list "TREE" who parent) ;; Broadcast mote id and parent id ask my-links [die] ;; Remove all links create-link-with mote parent ;; Create link with parent mote stop ] end ;; The mote has finished generating the tree so it starts storing children to step_DONE if has-message "TREE" [ ;; Receiving TREE let msg received "TREE" let i item 1 msg ;; Set this motes potential child let j item 2 msg ;; Get the neighbors parent from the message if j = who [ ;; If this mote is the neighbors parent set children fput i children ;; Add child mote id to children list ] 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 if MoteLabel = "parent" [set label parent] ;; Show mote parent if MoteLabel = "children" [set label children] ;; Show the motes children ] end
The NetLogo procedures for this applet can be downloaded directly as: Protocol4.9.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).