• Protocol 4.10: Tiny aggregation (TAG)

    PROTOCOL

    Computing the maximum value using tiny aggregation (TAG)

    SUMMARY

    The algorithm starts by getting motes without children to send their sensed value to the parents. When a mote receives a message it stores the largest value between the message and the motes own value. When a mote has received messages from all its children, it will send the maximum value to its parent unless it is the parent mote; in this case it will shout the maximum value.

    OPERATION

    • Click the Setup button to generate a tree network based on communication distance and network size.
    • Click the Go! button to run the algorithm.

    NOTICE

    • Use the MoteLabel list to change the labels to the max value, mote id, parent id or children. This will help show how the algorithm runs. When set to the max value, as the algorithm runs, the value may increase when a message is received.

    TRY

    • What happens if the communication distance is too small, making a disconnected network? Change this by adjusting the c slider.
    • Try selecting Tree (GG) or Tree (RNG) from the NetworkStructure drop-down box, do the resulting networks look any different?
    • 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

    See Protocol 4.10

    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 4.10

    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 stores maximum value and r which
    ;; stores a tally of the messages received
    motes-own [m r]
    
    ;;Network Setup
    to initialize
      ;; Create a network with the restriction that it is a rooted tree
      if NetworkStructure = "Tree (UDG)" [create-udg create-tree] ;; UDG network
      if NetworkStructure = "Tree (GG)"  [create-udg create-gg create-tree] ;; GG network
      if NetworkStructure = "Tree (RNG)" [create-udg create-rng create-tree] ;; RNG Network
      ask motes [
        set m random 1001 ;; The sensed value is a random number between 0 and 1000
        become "IDLE" ;; Set all motes to state IDLE
        set label m
      ]
      ask motes with [parent = ""] [ ;; Motes with no parent are not part of the tree
                                     ;; so will not be used
        become "DEAD"
        set label "" ;; The DEAD state does not have a label
      ]
    end
    
    ;; Runs the TAG 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 = "IDLE" [ step_IDLE stop ]
      if state = "LSTN" [ step_LSTN stop ]
    end
    
    ;; Every mote transitions to the LSTN state. Motes without children send their m
    ;; value to their parent.
    to step_IDLE
      if length children = 0 [ ;; If mote has no children
        send list "MTAG" m (mote parent) ;; Send message to parent
      ]
      become "LSTN"
    end
    
    ;; When the mote receives a message, it selects the maximum value from its own sensed
    ;; value and the messages value. Once the mote has received a message from all its
    ;; children, it sends that value to its parent unless it is the root mote. In this
    ;; case it shouts the maximum value.
    to step_LSTN
      if has-message "MTAG" [ ;; Receiving MTAG
        let msg received "MTAG"
        set r (r + 1)
        set m max list m item 1 msg ;; Store the maximum value
        if length children = r [ ;; If messages from all children have been received
          ifelse parent = -1 [ ;; If mote is the parent mote
            show word "Maximum value in network is " m
          ]
          [
            send list "MTAG" m (mote parent) ;; Send message to parent
          ]
        ]
        stop
      ]
    end
    
    ;; Changing the labels of the motes based on the MoteLabel dropdown list
    to mote_labels
      ask motes with [state != "DEAD"] [ ;; Motes in the DEAD state are ignored
        if MoteLabel = "none" [set label ""] ;; Hide the label
        if MoteLabel = "max value" [set label m] ;; Show maximum value
        if MoteLabel = "mote id" [set label who] ;; Show mote id
        if MoteLabel = "parent id" [set label parent] ;; Show parent id
        if MoteLabel = "children" [set label children] ;; Show list of children
      ]
    end
    

    The NetLogo procedures for this applet can be downloaded directly as: Protocol4.10.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,282 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>