In the original
, each node is required to directly connect with all of its neighboring nodes within its area of interest (AOI), or
. However, sending position updates to
of them will consume a lot of bandwidth if the size of AOI neighbors is large.
Thus, another more bandwidth-efficient approach is to send only directly to the nearest
, and allow them to continuously forward a particular message or update to their neighbors, so that the update task is distributed among many nodes. In other words, we trade bandwidth usage with increased latency, in hope that more neighbors can be reached in time, without overloading the sender node.
The main issue then is to build a fully-connected spanning tree, centered at the sender node, to all its AOI neighbors, in a distributed way.
does this by using a reverse approach: deciding which neighbor to forward to, base on whether this neighbor would select me as its
. The parent selection criteria is also simple: if I am closer to the original sender node, among all possible parents, then I'll be the parent and thus can forward the message. See figures below. For more information, please refer to VoroCast's
VoroCast forwarding. (A) root sends the message to its enclosing neighbors. (B) node E sends to its enclosing neighbors node F. (C) node A and E are both considered as node G's parent, but node A is selected as it's closer to root. (D) similarly, both node D & F can be node Q's parent, but node D is selected as it's closer to root. (E) the end result: a spanning tree centered at the root node, without redundency, and constructed in a distributed manner.
Contributions to http://vastlib.wikispaces.com/ are licensed under a
Creative Commons Attribution Share-Alike 3.0 License
Portions not contributed by visitors are Copyright 2017 Tangient LLC
TES: The largest network of teachers in the world
Turn off "Getting Started"