• Protocol 6.3: Tracking histories of mobile objects in cordon-structured networks

    PROTOCOL

    Tracking histories of mobile objects in cordon-structured networks

    SUMMARY

    This algorithm stores the movements of mobile objects in a database where each entry contains the id of the object the time it entered and exited an edge as well as the ids of the motes the object entered and exited the edge from.

    When a mobile object passes a mote, that mote creates a new entry in its table with the objects’ id, the time it entered the edge, and the motes id as the in-cordon. This entry is also broadcast to the motes neighbors as an EXIT message.

    Motes receiving this message will check if there are any open records in their table with the same object id. If there is, it will complete that entry with information from the EXIT message. It then sends an ENTR message containing the complete record to the mote which sent the EXIT message. This mote will add the record to their table.

    OPERATION

    • Click the Setup button to generate a network based on communication distance and network size, and the amount of mobile objects specified by the ObjectNo box.
    • Click the Go! button to run the algorithm.

    NOTICE

    • The mobile objects are shaped like fish and only travel along network edges.
    • Use the MoteLabel list to change the labels to the mote id.
    • A motes m table can be displayed by clicking on it. Table entries will appear in the output list to the right of the simulation.

    TRY

    • Try selecting a different network structure from the NetworkStructure drop-down box, does the algorithm run any differently?
    • What happens if the communication distance is too small, making a disconnected network? Does the algorithm still function? Try this by adjusting the c slider.
    • Try adding more mobile objects by increasing the number in the ObjectNo box.
    • Try altering the speed of the mobile objects by adjusting the speed slider.
    • Try running the algorithm slowly, with a small network size and amount of mobile objects to get a better idea of how the algorithm runs. Change this by adjusting the speed slider, the NetSize and ObjectNo box.

    LINK TO BOOK

    Protocol 6.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 6.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 motes
    breed [motes mote]
    motes-own [m]
    ;; Event table m = [oid : N; enter : T; exit : T; in : N; out : N]
    ;;                 [object id; enter time; exit time; id of cordon the object entered the
    ;;                  edge from; id of cordon object left the edge from]
    
    ;; Define a new breed of turtle called objects
    breed [objects object]
    objects-own [next-cordon]
    ;; next-cordon, the id of the cordon the object is travelling towards
    
    ;; System setup and initialization
    to initialize
      ;; Setting up the network
      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
      ;; Create a network with the restriction that it is a 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
    
      ;; Create the amount of mobile objects specified by the ObjectNo box and place them
      ;; on random edges of the network.
      repeat ObjectNo [ ;; Repeat this the for every mobile object
        create-objects 1 ;; Create a mobile object
        ask one-of motes with [count link-neighbors > 0] [ ;; Pick a random mote
          let prev who ;; random motes' id
          let next [who] of one-of link-neighbors ;; next is a neighbor of this mote
          ask objects with [state = 0] [ ;; Pick the object that is not yet in the "MOVE" state
            let x mean (list [xcor] of (mote prev) [xcor] of (mote next))
            let y mean (list [ycor] of (mote prev) [ycor] of (mote next))
            setxy x y ;; move object to between the random mote and its neighbor
                      ;; this can produce odd results if the world is wrapped
            set next-cordon next
            face (mote next-cordon)
            set label-color black ;; The label color is black
            set messages [] ;; Clear messages
            set msgsent [] ;; Clear the list of messages sent
            set msgrecv [] ;; Clear the list of messages received
            set msghear [] ;; Clear the list of messages received
            become "MOVE"
            set shape "fish" ;; The mobile objects are shaped like fish
          ]
        ]
      ]
    
      ask motes [
        become "IDLE" ;; Set all motes to state IDLE
        set m [] ;; Clearing data
      ]
     end
    
    ;; Runs the convoy algorithm
    to go
      ask motes [step]
      ask objects [step]
      mote_labels ;; Changes the labels of the motes based on the MoteLabel dropdown list
      DisplayM ;; When the user clicks on a mote, it displays the m table
      tick
    end
    
    ;;
    ;; Mote protocols
    ;;
    
    ;; Step through the current state
    to step
      if state = "IDLE" [step_IDLE stop]
      if state = "MOVE" [step_MOVE stop]
    end
    
    ;; When a mobile object passes a mote (receiving a SENSE message), that mote creates a 
    ;; new entry in its m table with the objects' id, the time it entered the edge, and the
    ;; motes id as the in-cordon. This entry is the broadcast to the motes neighbors as an
    ;; EXIT message.
    ;; Motes receiving an EXIT message will check if there are any open records in their table
    ;; with the same object id. If there is, it will complete that entry with information from
    ;; the EXIT message. It then sends an ENTR message containing the complete record to the
    ;; mote which sent the EXIT message. 
    ;; Motes receiving an ENTR message will add the record to their m table.
    to step_IDLE
      if has-message "SENSE" [  ;; If it's the sense(now) values from the mobile objects
        let msg received "SENSE"
        let o (item 1 msg) ;; o is mobile object id
    
        set m fput (list o ticks "NULL" who "NULL") m ;; Create new open record
        broadcast (list "EXIT" o ticks who)
        stop
      ]
    
      if has-message "EXIT" [ ;; If EXIT message received
        let msg received "EXIT"
        let o (item 1 msg)
        let tx (item 2 msg)
        let i (item 3 msg)
        foreach m [ ;; Look through each row of the m table
          let oid (item 0 ?)
          let enter (item 1 ?)
          let exit (item 2 ?)
          let in (item 3 ?)
          let out (item 4 ?)
          if exit = "NULL" and oid = o and in = who [
            set m remove ? m
            let tn enter
            set m fput (list oid enter tx in i) m ;; Close record by replacing exit with tx and out with i
            send (list "ENTR" o tn tx who) (mote i)
          ]
        ]
        stop
      ]
    
      if has-message "ENTR" [ ;; If ENTR message received
        let msg received "ENTR"
        let o (item 1 msg)
        let tn (item 2 msg)
        let tx (item 3 msg)
        let i (item 3 msg)
        set m fput (list o tn tx i who) m ;; Add record to m table
        stop
      ]
    end
    
    ;; Makes the objects move along the edges. When an object reaches a cordon, it sends a
    ;; message containing the sense(now) value, picks a random neighbor of that cordon and
    ;; moves towards it.
    to step_MOVE
      jump min (list Speed distance (mote next-cordon)) ;; Make sure the object doesn't overshoot the cordon
      if distance mote next-cordon < .01 [ ;; It may not EXACTLY hit the cordons location
        send (list "SENSE" who) (mote next-cordon) ;; Sending the sense(now) value
        set next-cordon [who] of one-of [link-neighbors] of (mote next-cordon)
        face (mote next-cordon) ;; Needs to face in the correct direction
      ]
      stop
    end
    
    ;; Changing the labels of the motes based on the MoteLabel dropdown list
    to mote_labels
      ask turtles [set label ""] ;; If nothing is specified, then the labels are blank
      if MoteLabel = "id" [ask turtles [set label who]] ;; Show id
    end
    
    ;; When the user clicks on a mote, it displays the m table
    to DisplayM
      if mouse-down? [ ;; If the mouse has been clicked
        let ClickedMote min-one-of motes [distancexy mouse-xcor mouse-ycor] ;; Pick the closest mote
        clear-output ;; Clears the output field
        output-print (word "M table of mote " [who] of ClickedMote ":")
        output-print "[oid enter exit in out]"
        output-print ""
        foreach [m] of ClickedMote [output-print ?] ;; Show the m table
        stop
      ]
    end
    

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