Establishing a tree with multiple initiators
The algorithm starts with every mote broadcasting its id to their neighbors. When these motes receive a message they check to see if it contains a smaller tree id (t). If it does, the mote sets that tree id as its smallest root id (m), the messages sender as its parent and broadcasts a message with its id and the tree id. This will eventually spread through the whole network, killing off trees until only the tree with the smallest tree id remains.
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 variable m, the smallest root id motes-own [m] ;; 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 "INIT" ;; All motes start in state init set parent -1 set m who ;; Set m as mote id ] end ;; Runs the multi-tree algorithm to go ask motes [ step ] show_links ;; Changes the visibility of links based on the ShowLinks dropdown list 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 = "IDLE" [ step_IDLE stop ] if state = "INIT" [ step_INIT stop ] end ;; Every mote broadcasts its id then transitions to the IDLE state to step_INIT broadcast (list "TREE" who who) ;; Broadcast mote id as root id and tree id become "IDLE" set m who ;; Set m as id end ;; Motes receiving the tree message check to see if it contains a smaller tree id (t). ;; If it does, the mote sets the messages sender as its parent and broadcasts a message ;; with its id and the tree id. to step_IDLE if has-message "TREE" [ ;; Receiving TREE let msg received "TREE" let i item 1 msg let t item 2 msg if t < m [ ;; If smaller tree id received broadcast (list "TREE" who t) set parent i ;; Set new parent id set m t ;; Store id of new root ask my-links [set color red] ;; Normal links are red ask link-with (mote parent) [set color blue] ;; Tree links are blue ] stop ] end ;; Changing the visibility of links based on the ShowLinks dropdown list to show_links ask links [show-link] ;; Show all of the links if ShowLinks = "Tree Links" [ ;; Show only the tree links ask links with [color = red] [hide-link] ] if ShowLinks = "Original Links" [ ;; Show only the original links ask links with [color = blue] [hide-link] ] 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 = "tree id" [set label m] ;; Show smallest root id if MoteLabel = "mote id" [set label who] ;; Show mote id if MoteLabel = "parent id" [set label parent] ;; Show parent id ] end
The NetLogo procedures for this applet can be downloaded directly as: Protocol4.11.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).