• Protocol 5.3: Local minimum spanning tree (LMST)

    PROTOCOL

    Local Minimum Spanning Tree (LMST)

    SUMMARY

    The algorithm starts with every mote broadcasting its id and position to its neighbors. Once a mote has received information from all of its neighbors, it adds its own id and location to the list and computes a MST for its local neighborhood. Once it and all of its neighbors are part of this MST, it sends a CHCK message to any adjacent motes of which are directly connected in the MST. Any motes receiving a CHCK message check to seen if this link is part of their MST. If it is, then this link is added to the LMST network.

    OPERATION

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

    NOTICE

    • LMST edges are thick and orange in color.
    • The algorithm always produces a plane graph, but may not always produce a tree.
    • Use the MoteLabel list to change the labels to the mote id.

    TRY

    • What happens if the communication distance is too small, making a disconnected network? Does the algorithm still produce a LMST? Change this by adjusting the c slider.
    • Try selecting GG or RNG from the NetworkStructure drop-down box to change the network shape to a Gabriel Graph or Relative Neighborhood Graph. Does the algorithm run any differently?
    • Try selecting LMST Links from the ShowLinks drop-down box to get a better idea of how the LMST is structured.
    • 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 5.3

    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 5.3

    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 motesbreed [motes mote] ;; Each mote can store the local variables N which is the set of neighbors and;; locations and L which is the set of local candidate MST edges.motes-own [N L] ;; System setup and initializationto initialize if NetworkStructure =“UDG” [create-udg] ;; Create UDG networkif NetworkStructure =“GG” [create-udg create-gg] ;; Create GG networkif NetworkStructure =“RNG” [create-udg create-rng] ;; Create RNG networkask motes [ set N [] set L [] become “INIT”;; Set all motes to state INIT ] end;; Runs the LMST algorithmto go ask motes [ step ] mote_labels ;; Changes the labels of the motes based on the MoteLabel dropdown list show_links ;; Changes the visibility of links based on the ShowLinks dropdown listtickend;;;; Mote protocols;;;; Step through the current stateto step if state =“INIT” [ step_INIT stop ] if state =“LSTN” [ step_LSTN stop ] if state =“CHCK” [ step_CHCK stop ] end;; Every mote broadcasts a message containing their id and position to all of their;; neighbors.to step_INIT let p (listxcorycor) ;; Position coordinates of moteset N fput (listwho p) N ;; Add this motes id and location to neighbor set broadcast (list“PING”who p) ;; Broadcast location and id become “LSTN”end;; Once a mote has received information from all its neighbors, it computes a MST for;; its local neighborhood. Once it and all of its neighbors are part of this MST, it;; sends a CHCK message to any adjacent motes of which are directly connected in the MST.to step_LSTN let p (listxcorycor) ;; Position coordinates of moteif has-message “PING” [ ;; Receiving PING messagelet msg received "PING"let i item1 msg ;; Neighbor's idlet loc item2 msg ;; Neighbor's coordinatesset N fput (list i loc) N ;; Store neighbor's id and locationiflength N >countlink-neighbors [ ;; Process id/location pairs once received from all neighborslet M (listwho) ;; Initialize Prim's algorithm with first visited motewhile [length M <=countlink-neighbors] [ ;; Loop until all link neighbors plus this mote have been visitedlet O [] ;; Visited/unvisited mote pairslet MinO “NULL”foreach N [ let i1 item0 ? ;; Id 1let l1 item1 ? ;; Location 1foreach N [ let i2 item0 ? ;; Id 2let l2 item1 ? ;; Location 2ifmember? i1 M =trueandmember? i2 M =false [ ;; i1 is in M but i2 is notset O fput (list i1 l1 i2 l2) O ;; Add to list of visited/unvisited mote pairs ] ] ] foreach O [ let i1 item0 ? ;; Id 1let l1 item1 ? ;; Location 1let i2 item2 ? ;; Id 2let l2 item3 ? ;; Location 2ifelse MinO ="NULL" [ ;; Initializing MinOif dist l1 l2 >0 [ set MinO (list i1 l1 i2 l2) ] ] [ if dist l1 l2 >0and dist l1 l2 <= dist item1 MinO item3 MinO [ ;; Minimum length edge in O conditionsset MinO (list i1 l1 i2 l2) ] ] ] if MinO !=“NULL” [ set M fputitem2 MinO M ;; Store new visited neighbor idset L fput (listitem0 MinO item2 MinO) L ;; Store new candidate MST edge ] ] foreach L [ let id item0 ? let j item1 ? if id =who [ send (list"CHCK" id) (mote j) ;; Communicate CHCK to candidate neighbors ] ] become “CHCK”stop ] ] ;; “CHCK” message processing is deferred until in state “CHCK”end;; Any motes receiving a CHCK message check to seen if this link is part of their MST.;; If it is, then this link is added to the LMST network.to step_CHCK if has-message “CHCK” [ ;; Receiving CHCKlet msg received "CHCK"let i item1 msg foreach L [ let i1 item0 ? let i2 item1 ? if i1 =whoand i2 = i [ asklink i1 i2 [ ;; Store bidirected edgessetcolororangesetthickness0.15 ] ] ] stop ] end;; Changing the labels of the motes based on the MoteLabel dropdown listto mote_labels ask motes [ if MoteLabel ="none" [setlabel""] ;; Hide the labelif MoteLabel =“mote id” [setlabelwho] ;; Show mote id ] end;; Changing the visibility of the links based on the ShowLinks dropdown listto show_links asklinks [show-link] ;; Show all of the linksif ShowLinks =“LMST Links” [ ;; Show only the tree linksasklinks [hide-link] asklinkswith [color=orange] [show-link] ] end

    The NetLogo procedures for this applet can be downloaded directly as: Protocol5.3.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,290 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>