Send the link below via email or IMCopy
Present to your audienceStart remote presentation
- Invited audience members will follow you as you navigate and present
- People invited to a presentation do not need a Prezi account
- This link expires 10 minutes after you close the presentation
- A maximum of 30 users can follow your presentation
- Learn more about this feature in our knowledge base article
Decentralized spatial computing with NetLogo agent-based simulation
Transcript of Decentralized spatial computing with NetLogo agent-based simulation
If ≥ n tally marks, shout “Crowd!”
Else, pass paper to another randomly selected neighbor Distributed system: “a collection of multiple information systems that must interoperate [via a digital communications network] to complete some task”
Decentralized system: “a distributed system where no single information system element knows the entire system state” Challenge of generating global spatial properties using only local spatial knowledge
Opportunity of using spatial structures for efficient processing A node sense whether it is in or out of the region
Asks immediate neighbors if they also sense the region
Is an (inner) boundary node if it is inside the region, but has one or more neighbors outside the region. Duckham, M., Nussbaum, D., Sack, J-R, Santoro, N. (2011) Efficient, decentralized computation of the topology of spatial regions IEEE Transactions on Computers 60(8): 1100-1113. doi:10.1109/TC.2010.177 Intro Why? Design Test Decentralized spatial computing with NetLogo agent-based simulation Matt Duckham GIScience 2012 Tutorial
18 September 2012 Big idea Increasingly, computing happens somewhere, with that geographic location being relevant to the computational process itself. Structure Why study decentralized spatial computing?
How to design a decentralized spatial algorithm.
How to test a decentralized spatial algorithm. Duckham, M. (2012) Decentralized spatial computing: Foundations of geosensor networks. Springer, Berlin. ISBN 978-3-642-30852-9. Santoro, N. (2012) Design and analysis of distributed algorithms. Wiley, New York. ISBN 978-0-471-71997-7. Computing Somewhere computing simultaneously in and about geographic space Spatial constraints to movement of information Spatial constraints
to storage of information Yes No No Yes "Computing somewhere"
e.g., geosensor networks "Computing anywhere"
e.g., Intranets, MANETs "Computing everywhere"
e.g., LBS "Computing nowhere"
e.g., GIS Decentralization Decentralized versus distributed Why decentralized spatial? Why decentralized spatial? "Crowd" computing "Crowd" computing http://ambientspatial.net/book/?p=79 Ambient spatial intelligence "Ambient spatial intelligence (AmSI) is concerned with embedding into built and natural environments the intelligence to monitor geographical occurrences and respond to spatiotemporal queries." Photo courtesy Jarod Lyon, ARI Photo courtesy Gary Stoneham, DSE Example algorithms Flooding, gossiping, rumor routing, epidemics
Establishing rooted, bidirected, shortest path trees
Distributed function evaluation
Relative neighborhood graph, Gabriel graph, minimum spanning tree
Sweeps Surface critical points detection and events
Boundary detection, cycles, tracking
Topological region relations, structure, and events
Area and centroid of regions
Monitoring flocking and convoys Summary Discussion NetLogo Agent-based simulation system
Capable of modeling both computational and geographic environment Georouting Routing information through a network to a target at a known coordinate location Greedy: Send to next nearest neighbor
GPSR: Greedy + face routing Decentralized Area Compute the area of a monitored region Face route around boundary of region Overlay networks Logical network built on top of physical network Physical network modeled using UDG
Logical network structures include GG, RNG, RDT, ... Gabriel graph Relative neighborhood graph We don't need decentralization! Wildfire (Source: US Air Force) VANET (Source: Nilson Menezes) Personal navigation
(Source: Niall Kennedy) Marine (Source: Sarah Ackerman) Georouting: http://ambientspatial.net/book/?tag=georouting Area computation: http://ambientspatial.net/book/?p=398 Overlay network: http://ambientspatial.net/book/?tag=overlay-network Algorithm design Decentralized algorithms specify local rules, not global behaviors Restrictions: Specification of computational and geographical environment. In short, list of assumptions.
(System) events: Things that happen to nodes. Three options: message receipt, trigger, spontaneously.
Actions: Atomic (uninteruptable) list of operations completed in response to event. In short, "programs."
States: Allow nodes to respond to events with different actions, dependent on past interactions. Nodes are allowed only to access information generated by or previously communicated to them Crowd Gabriel graph Greedy georouting Crowd Exercises Browse through the algorithms, specification and code; ask us why they are that way; challenge us with other ways. Can you adapt greedy georouting to use direction rather than distance?
Find a degenerate case in GPSR.
Adapt georouting to geocasting (sending to a geographic region)
... and the book contains many other questions to consider. Evaluation Does it work?
Is it scalable?
Is it robust to errors and uncertainty? Scalability
Key feature is number of messages generated by a protocol
Overall: increase in messages as a function of (network) size
Load balance: relative spread of messages across network Complex areal objects Decentralized semi-line algorithm Overall scalability Load balance BehaviorSpace Evaluation Does it work?
E.g., Greedy georouting Protocol 5.4
Is it scalable?
E.g., Area protocol, Protocol 5.10
Is it robust to errors and uncertainty?
E.g., Inner boundary, Protocol 6.1