• Protocol 4.12: Leader election in a ring (“as far”)

    PROTOCOL

    �As far�: Leader election in a ring

    SUMMARY

    The algorithm starts with every mote sending a LEAD message with their id to one of its neighbors. When motes receive this LEAD message, they check to see if the mote identifier (i) is smaller than their m value. If it is, it stores it as the new m value and sends the message to the next mote in the ring. This will continue around the ring until the mote identifier is the same as the m value. When this happens the mote transitions into the LEAD state.

    OPERATION

    • Click the Setup button to generate a ring network based on network size.
    • Click the Go! button to run the algorithm.

    NOTICE

    • Use the MoteLabel list to change the labels to either the mote id or m value. This will help show how the algorithm runs. When set to m, as the algorithm runs, this should reduce to 0 for all motes.

    TRY

    • 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

    Protocol 4.12

    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.12

    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/>.
    
    globals[c] ;; Communication distance, c is not used in this algorithm
    
    __includes["../gsn.nls"]
    ;; Define a new breed of turtle called motes
    breed [motes mote]
    
    ;; Each mote can store the local variable m, the smallest identifier
    motes-own [m]
    
    ;;Network Setup
    to initialize
      ;; Creating a ring network
      layout-circle motes 9.5
      ask motes [
        let id who
        ask  min-n-of 3 motes [distance myself] [
          if who != id [ ;; Mote can't create link with itself
            create-link-with (mote id)
          ]
        ]
      ]
      ask motes [
        become "INIT" ;; All motes start in state INIT
        set m who ;; Set m to mote id
        set label m
      ]
    end
    
    ;; Runs the leader election 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 = "LEAD" [ step_LEAD stop ]
    end
    
    ;; Every mote sends its id to a random neighbor
    to step_INIT
      let v [who] of one-of link-neighbors ;; Arbitrarily choose neighbor
      send (list "LEAD" who who) (mote v) ;; Broadcast node identifier to neighbor
      become "IDLE"
    end
    
    ;; When a mote receives a LEAD message, it checks to see if the mote identifier (i) is
    ;; smaller than its m value. If it is, it stores it as the new m value and sends the
    ;; message to the next mote in the ring. If the mote identifier is the same as the m
    ;; value, then the mote transitions into the LEAD state.
    to step_IDLE
      while [has-message "LEAD"] [ ;; Receiving LEAD message
        let msg received "LEAD"
        let i item 1 msg
        let v item 2 msg ;; Previous mote
        let nbr [who] of link-neighbors ;; Store a list of mote neighbor id's
        let next first remove v nbr ;; Remove previous mote from list of neighbors
    
        ifelse i < m [ ;; If smaller node identifier received
          set m i ;; Store new smallest id
          send (list "LEAD" i who) mote next ;; Forward lead message
        ]
        [ if i = m [
            become "LEAD" ;; Node receiving its own id is the leader
            show word m " is the leader"
          ]
        ]
        stop
      ]
    end
    
    to step_LEAD
    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 = "m" [set label m] ;; Show smallest root id
        if MoteLabel = "mote id" [set label who] ;; Show mote id
      ]
    end
    

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