Voronoi-based Overlay Network (VON)


A VON is a fully-distributed overlay network that allows neighbors to be discovered on a Voronoi-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 AOI neighbors. 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 Voronoi diagram. A Voronoi diagram partitions a space with n nodes into n Voronoi regions such that all points closest to a particular node are contained within the node's region. Certain boundary neighbors (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:

VON-move.jpg
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 gateway node), towards the direction of the joining position via greedy forward (i.e., at each hop, the message is sent to the node whose coordinate is closest to the destination, also known as geographic routing). Once the request has reached the acceptor 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 enclosing neighbors, 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 research publications.

VON-join.jpg
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


image002.jpg
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.