VoroCast

VoroCast


In the original VON, each node is required to directly connect with all of its neighboring nodes within its area of interest (AOI), or AOI neighbors. However, sending position updates to all 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 enclosing neighbors, 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. VoroCast does this by using a reverse approach: deciding which neighbor to forward to, base on whether this neighbor would select me as its parent. 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 research paper.


vorocast-all-2col-label.gif
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.