Skip to main content
You are not a member of this wiki.
Pages and Files
Voronoi-based Overlay Network (VON)
is a fully-distributed
that allows neighbors to be discovered on a
-partitioned virtual space. Each node in VON has a coordinate point and specifies an
Area of Interest
(AOI) within which the node is constantly aware of all
. Nodes are allowed to move continuously in space and connect with new AOI neighbors. For simplicity, we assume a 2D space but note that VON is generalizable to 3D spaces. To discover new AOI neighbors, each node organizes the coordinates of itself and its AOI neighbors in a
. A Voronoi diagram partitions a space with
n Voronoi regions
such that all points closest to a particular node are contained within the node's region. Certain
(i.e., AOI neighbors whose Voronoi regions overlap with the AOI boundary) thus can be asked to check if the moving node should be notified of new neighbors outside the moving node's current AOI. See figure below:
MOVE procedure (a) Triangle (▲) indicates the intended new position. Squares (▓) are new neighbors about to be discovered. Stars (★) are the boundary neighbors. (b) After the move, crosses (╳) are the neighbors no longer inside the AOI, therefore are disconnected.
To join a VON, a join request is forwarded from any existing node (but often a
node), towards the direction of the joining position via
(i.e., at each hop, the message is sent to the node whose coordinate is closest to the destination, also known as
). Once the request has reached the
node whose Voronoi region covers the joining spot, the acceptor can return a list of initial neighbors for the joining node to contact. Additional nodes within the joiner's AOI are discovered via notifications from known AOI neighbors. To maintain the overlay connectivity, each node should be aware of its closest
, even if those neighbors are outside of its AOI (see below for the join procedure and neighbor definitions in a VON).
For more information, please refer to VON's
JOIN procedure (a) Gateway server and its ENs are the circles. Acceptor and its ENs are the squares. Star (☆) is the intended joining spot. Join request is forwarded to the acceptor (b) Star (★) is the joining node, shades are neighbors affected by join. Note that the effect is localized
Large circle is the AOI boundary for the center node. Squares (▓) are enclosing neighbors; triangles (▲) are boundary neighbors; stars (★) are both enclosing and boundary neighbors; circle (●) represents a regular AOI-neighbor; crosses (╳) represent neighbors irrelevant (i.e. outside of AOI) to the center node.
help on how to format text
Turn off "Getting Started"