Voronoi diagrams and Delaunay triangulations are gaining attention in several P2P applications managing a wide number of distributed and mobile entities, from resource discovery in auction-like networks to the realization of networked virtual environments. In this paper we consider a scalable partitioning technique of the entity space based on Voronoi diagrams, useful for a wide variety of distributed applications that exhibit a dynamically changing topology. Using the HyVonNe (Hybrid Voronoi Network) architecture, the space is partitioned in Voronoi regions, each one including a limited number of entities and managed by a Region Leader, that are created and deleted depending on the spatial density of such entities, while the Delaunay triangulation connecting the Region Leaders is used to support the partitioning, routing and searching activities. The resulting two-layers structure (entity space and Voronoi regions) is scalable and extendable, allows to reduce the propagation of the entity position updates in the network and to maintain the load balancing among regions. Simulation results related to two different application fields are presented.
展开▼
