Effcient UAV-Based MEC Using GPU-Based PSO and Voronoi Diagrams

Mobile-Edge Computing(MEC)displaces cloud services as closely as possible to the end user.This enables the edge servers to execute the offloaded tasks that are requested by the users,which in turn decreases the energy consumption and the turnaround time delay.However,as a result of a hostile environment or in catastrophic zones with no network,it could be difficult to deploy such edge servers.Unmanned Aerial Vehicles(UAVs)can be employed in such scenarios.The edge servers mounted on these UAVs assist with task offloading.For the majority of IoT applications,the execution times of tasks are often crucial.Therefore,UAVs tend to have a limited energy supply.This study presents an approach to offload IoT user applications based on the usage of Voronoi diagrams to determine task delays and cluster IoT devices dynamically as a first step.Second,the UAV flies over each cluster to perform the offloading process.In addition,we propose a Graphics Processing Unit(GPU)-based parallelization of particle swarm optimization to balance the cluster sizes and identify the shortest path along these clusters while minimizing the UAV flying time and energy consumption.Some evaluation results are given to demonstrate the effectiveness of the presented offloading strategy.

Numerical Fitting of Planar Photographic Images with Spherical Voronoi Diagrams

There are many phenomena that generate polygonal tessellations on surfaces of 3D objects. One interesting example is the jackfruit, a multiple fruit found in the tropics. A recent study found the best-fit spherical Voronoi diagram from a photo of jackfruit skin, but the optimization was relative to the radius of the sphere and the height of the spikes. In this study, we propose a method for adjusting the position of the center of the sphere in addition to these parameters. Experiments were conducted using both ideal and real data. However, convergence with real data has not been confirmed due to relaxation of the convergence condition.

Township Classification and the Sphere of Influence Based on Voronoi Diagram——A Case of Bijie City

Supported by research available of township system and influential sphere, the research is conducted based on towns in Bijie City, as per Voronoi diagram and breaking point theory. In the research, Shixi Office dominated as the highest center and Salaxi Town and Haizijie Town were sub-centers, supplemented by Yachi Town, Zhuchang Town, Yangjiawan Town, Qingchang Town, Heguantun Town, Qingshuipu Town, Yanzikou Town and Longchangying Town. Hence, township system and influ- ential sphere were determined and related methods and technologies were explored.

TOOL PATH PLANNING USING VORONOI DIAGRAM AND THREE STACKS

Based on the object oriented data structure of Voronoi diagram, the algorithm of the trimmed offset generating and the optimal too l path planning of the pocket machining for multiply connected polygonal domains are studied. The intersection state transition rule is improved in this algorithm. The intersection is between the trimmed offsets and Voronoi polygon. On this basis, the trimmed offset generating and the optimal tool path planning are mad e with three stacks(I stack, C stack and P stack)in different monotonous pouches of Voronoi diagram. At the same time, a merging method of Voronoi diagram an d offsets generating for multiply connected polygonal domains is also presented. The above algorithms have been implemented in NC machining successfully, and the efficiency is fully verified.

Directional nearest neighbor query method for specified geographical direction space based on Voronoi diagram

The existing nearest neighbor query methods cannot directly perform the nearest neighbor query of specified geographical direction space.In order to compensate the shortcomings of the existing methods,a directional nearest neighbor query method in specific direction space based on Voronoi diagram is put forward.This work studies two cases,i.e.the query point is static and the query point moves with a constant velocity.Under the static condition,the corresponding pruning method and the pruning algorithm of the specified direction nearest neighbor(pruning_SDNN algorithm)are proposed by combining the plane right-angle coordinate system with the north-west direction,and then according to the smallest external rectangle of Voronoi polygon,the specific query is made and the direction nearest neighbor query based on Voronoi rectangle(VR-DNN) algorithm is given.In the case of moving with a constant velocity,first of all,the combination of plane right angle coordinate system,geographical direction and circle are used,the query range is determined and pruning methods and the pruning algorithm of the direction nearest neighbor based on decision circle(pruning_DDNN algorithm) are put forward.Then,according to the different position of motion trajectory and Voronoi diagram,a specific query through the nature of Voronoi diagram is given.At last,the direction nearest neighbor query based on Voronoi diagram and motion trajectory(VM-DNN) algorithm is put forward.The theoretical research and experiments show that the proposed algorithm can effectively deal with the problem of the nearest neighbor query for a specified geographical direction space.

A new heuristics model of simulating pedestrian dynamics based on Voronoi diagram

A new heuristics model based on the Voronoi diagram is presented to simulate pedestrian dynamics with the noncrowded state, in which these mechanisms of preference demand evading and surpassing, microscopic anti-deadlock, and site-fine-tuning are considered. The preference demand describes the willingness determination of detouring or following other pedestrians. In the evading and surpassing mechanisms, in order to achieve a balance between avoiding conflicts and minimizing detour distances, a new pair of concepts: "allow-areas and denial-areas" are introduced to divide the feasible region for pedestrians detour behaviors, in which the direction and magnitude of detour velocity are determined.A microscopic anti-deadlock mechanism is inserted to avoid deadlock problem of the counter-directional pedestrian. A site-fine-tuning mechanism is introduced to describe the behavior of avoiding getting too close to the neighbors in pedestrian movement. The presented model is verified through multiple scenarios, including the uni-or bi-direction pedestrian flow in the corridor without obstacles, the uni-direction pedestrian flow in the corridor with obstacles, and the pedestrian evacuation from a room with single-exit. The simulation results show that the velocity–density relationship is consistent with empirical data. Some self-organizing phenomena, such as lanes formation and arching are observed in the simulation.When pedestrians detour an obstacle, the avoiding area before the obstacle and the unoccupied area after the obstacle can be observed. When pedestrians evacuate through a bottleneck without panic, the fan-shaped crowd can be found, which is consistent with the actual observation. It is also found that the behavior of following others in an orderly manner is more conducive to the improvement of the overall movement efficiency when the crowd moves in a limited space.

A Study on Selecting the Shortest Routes by Voronoi Diagram in Route Networks of GIS

The problems of fast determining shortest paths through a polygonal subdivision planar with n vertices are considered in GIS. Distances are measured according to an Euclidean metric. A geographical information system (GIS) has a collection of nearest neighborhood operations and this collection serves as a useful toolbox for spatial analysis. These operations are undertaken through the Voronoi diagrams. This paper presents a novel algorithm that constructs a' shortest route set' with respect to a given source point and a target point by Voronoi diagrams. It will help to improve the efficiency of traditional algorithms, e. g., Djkstra algorithm, on selecting the shortest routes. Moreover, the novel algorithm can check the connectivity in a complex network between the source point and target one.

Efficient Generation of Conforming Voronoi Polygonal Surface Mesh

A novel construction algorithm is presented to generate a conforming Voronoi mesh for any planar straight line graph (PSLG). It is also extended to tesselate multiple-intersected PSLGs. All the algorithms are guaranteed to converge. Examples are given to illustrate its efficiency.

Voronoi Approach to Recursive Generation of Tool Path for SLS

Assuming that a Voronoi diagram of slice area is obtained, topological structures of all Voronoi edges and Voronoi polygons are used to accelerate the offsetting process. Once walk line intersects with one of Voronoi edges of the starting Voronoi object, the next starting Voronoi object is acquired through the topology relationship. Experimental results show the approach is effective and simple.

A new fast algorithm for computing the distance between two disjoint convex polygons based on Voronoi diagram

Computing the distance between two convex polygons is often a basic step to the algorithms of collision detection and path planning. Now, the lowest time complexity algorithm takes O(logm+logn) time to compute the minimum distance between two disjoint convex polygons P and Q, where n and m are the number of the polygons’ edges respectively. This paper discusses the location relations of outer Voronoi diagrams of two disjoint convex polygons P and Q, and presents a new O(logm+logn) algo- rithm to compute the minimum distance between P and Q. The algorithm is simple and easy to implement, and does not need any preprocessing and extra data structures.

Modeling rock fragmentation by coupling Voronoi diagram and discretized virtual internal bond

The rock fragmentation involves the inter-block and the intra-block fracture.A simulation method for rock fragmentation is developed by coupling Voronoi diagram(VD)and discretized virtual internal bond(DVIB).The DVIB is a lattice model that consists of bonds.The VD is used to generate the potential block structure in the DVIB mesh.Each potential block may contain any number of bond cells.To characterize the inter-block fracture,a hyperelastic bond potential is employed for the bond cells that are cut by the VD edges.While to characterize the intra-block fracture,an elastobrittle bond potential is adopted for the bonds in a block.By this method,both the inter-block and intra-block fracture can be well simulated.The simulation results suggest that this method is a simple and efficient approach to rock fragmentation simulation with block smash.

Path planning of the robot assembly based on Voronoi diagram

Based on the concepts of Voronoi diagram that describes geometry information of the robot assembly in C space, the position vector path parameter equation of the assembly movement between the step shaft and two-sided bearing bracket was given. And the path planning strategy of the component initiative assembly was put forward as well. Theoretical analysis proves that using the Voronoi diagram to do the geometry reasoning on the assembly space can evaluate the feasibility of the component assembly, and can present the reference position vector path of the component movement from the initial configuration to the objective configuration, therefore improves the flexibility of the robot initiative assembly.

2D Centroidal Voronoi Tessellations with Constraints

We tackle the problem of constructing 2D centroidal Voronoi tessellations with constraints through an efficient and robust construction of bounded Voronoi diagrams, the pseudo-dual of the constrained Delaunay triangulation.We exploit the fact that the cells of the bounded Voronoi diagram can be obtained by clipping the ordinary ones against the constrained Delaunay edges.The clipping itself is efficiently computed by identifying for each constrained edge the(connected) set of triangles whose dual Voronoi vertices are hidden by the constraint.The resulting construction is amenable to Lloyd relaxation so as to obtain a centroidal tessellation with constraints.

Location and Capacity Determination Method of Electric Vehicle Charging Station Based on Simulated Annealing Immune Particle Swarm Optimization

As the number of electric vehicles(EVs)continues to grow and the demand for charging infrastructure is also increasing,how to improve the charging infrastructure has become a bottleneck restricting the development of EVs.In other words,reasonably planning the location and capacity of charging stations is important for development of the EV industry and the safe and stable operation of the power system.Considering the construction and maintenance of the charging station,the distribution network loss of the charging station,and the economic loss on the user side of the EV,this paper takes the node and capacity of charging station planning as control variables and the minimum cost of system comprehensive planning as objective function,and thus proposes a location and capacity planning model for the EV charging station.Based on the problems of low efficiency and insufficient global optimization ability of the current algorithm,the simulated annealing immune particle swarm optimization algorithm(SA-IPSO)is adopted in this paper.The simulated annealing algorithm is used in the global update of the particle swarm optimization(PSO),and the immune mechanism is introduced to participate in the iterative update of the particles,so as to improve the speed and efficiency of PSO.Voronoi diagram is used to divide service area of the charging station,and a joint solution process of Voronoi diagram and SA-IPSO is proposed.By example analysis,the results show that the optimal solution corresponding to the optimisation method proposed in this paper has a low overall cost,while the average charging waiting time is only 1.8 min and the charging pile utilisation rate is 75.5%.The simulation comparison verifies that the improved algorithm improves the operational efficiency by 18.1%and basically does not fall into local convergence.

A novel model to evaluate spatial structure in thinned conifer-broadleaved mixed natural forests

In order to ensure the effective analysis and reconstruction of forests,it is key to ensure the quantitative description of their spatial structure.In this paper,a distance model for the optimal stand spatial structure based on weighted Voronoi diagrams is proposed.In particular,we provide a novel methodological model for the comprehensive evaluation of the spatial structure of forest stands in natural mixed conifer-broadleaved forests and the formulation of management decision plans.The applicability of the rank evaluation and the optimal solution distance model are compared and assessed for different standard sample plots of natural mixed conifer-broadleaved forests.The effect of crown width on the spatial structure unit of the trees is observed to be higher than that of the diameter at breast height.Moreover,the influence of crown length is greater than that of tree height.There are nine possible spatial structure units determined by the weighted Voronoi diagram for the number of neighboring trees in the central tree,with an average intersection of neighboring crowns reaching 80%.The rank rating of natural forest sample plots is correlated with the optimal solution distance model,and their results are generally consistent for natural forests.However,the rank rating is not able to provide a quantitative assessment.The optimal solution distance model is observed to be more comprehensive than traditional methods for the evaluation of the spatial structure of forest stands.It can effectively reflect the trends in realistic stand spatial structure factors close to or far from the ideal structure point,and accurately assesses the forest spatial structure.The proposed optimal solution distance model improves the integrated evaluation of the spatial structure of forest stands and provides solid theoretical and technical support for sustainable forest management.

A Voronoi diagram approach for detecting defects in 3D printed fiber-reinforced polymers from microscope images

Fiber-reinforced polymer(FRP)composites are increasingly popular due to their superior strength to weight ratio.In contrast to significant recent advances in automating the FRP manufacturing process via 3D printing,quality inspection and defect detection remain largely manual and inefficient.In this paper,we propose a new approach to automatically detect,from microscope images,one of the major defects in 3D printed FRP parts:fiber-deficient areas(or equivalently,resin-rich areas).From cross-sectional microscope images,we detect the locations and sizes of fibers,construct their Voronoi diagram,and employ-shape theory to determine fiber-deficient areas.Our Voronoi diagram and-shape construction algorithms are specialized to exploit typical characteristics of 3D printed FRP parts,giving significant efficiency gains.Our algorithms robustly handle real-world inputs containing hundreds of thousands of fiber cross-sections,whether in general or non-general position.

An efficient algorithm for approximate Voronoi diagram construction on triangulated surfaces

Voronoi diagrams on triangulated surfaces based on the geodesic metric play a key role in many applications of computer graphics.Previous methods of constructing such Voronoi diagrams generally depended on having an exact geodesic metric.However,exact geodesic computation is time-consuming and has high memory usage,limiting wider application of geodesic Voronoi diagrams(GVDs).In order to overcome this issue,instead of using exact methods,we reformulate a graph method based on Steiner point insertion,as an effective way to obtain geodesic distances.Further,since a bisector comprises hyperbolic and line segments,we utilize Apollonius diagrams to encode complicated structures,enabling Voronoi diagrams to encode a medial-axis surface for a dense set of boundary samples.Based on these strategies,we present an approximation algorithm for efficient Voronoi diagram construction on triangulated surfaces.We also suggest a measure for evaluating similarity of our results to the exact GVD.Although our GVD results are constructed using approximate geodesic distances,we can get GVD results similar to exact results by inserting Steiner points on triangle edges.Experimental results on many 3D models indicate the improved speed and memory requirements compared to previous leading methods.

Macro-mechanical properties of columnar jointed basaltic rock masses

From the geological structure of the columnar jointed rock mass, a visual model was established in software AUTOCAD by programming based on the algorithm of the Voronoi diagram. Furthermore, a program to convert the AUTOCAD model into 3DEC (3-dimensional distinct element code) model was developed, and a numerical model was established in 3DEC. Moreover, the results of triaxial compression tests of columnar jointed rock masses were simulated numerically. The REV (representative element volume) scale was studied, and the result shows that the REV size is 3 m × 3 m. The proposed approach, the established model and the numerical simulation were applied to study the macro-mechanical properties and the equivalent strength parameters of the columnar jointed rock mass. The numerical simulation results are in good accordance with the in-situ test results.

A novel mesh-free poly-cell Galerkin method

A novel numerical method is explored and named as mesh-free poly-cell Galerkin method. An improved moving least-square （MLS） scheme is presented, which can avoid the matrix inversion in standard MLS and can be used to construct shape functions possessing delta Kronecher property. A new type of local support is introduced to ensure the alignment of integral domains with the cells of the back-ground mesh, which will reduce the difficult in integration. An intensive numerical study is conducted to test the accuracy of the present method. It is observed that solutions with good accuracy can be obtained with the present method.

A Privacy-Preserving Mechanism Based on Local Differential Privacy in Edge Computing

With the development of Internet of Things(IoT),the delay caused by network transmission has led to low data processing efficiency.At the same time,the limited computing power and available energy consumption of IoT terminal devices are also the important bottlenecks that would restrict the application of blockchain,but edge computing could solve this problem.The emergence of edge computing can effectively reduce the delay of data transmission and improve data processing capacity.However,user data in edge computing is usually stored and processed in some honest-but-curious authorized entities,which leads to the leakage of users’privacy information.In order to solve these problems,this paper proposes a location data collection method that satisfies the local differential privacy to protect users’privacy.In this paper,a Voronoi diagram constructed by the Delaunay method is used to divide the road network space and determine the Voronoi grid region where the edge nodes are located.A random disturbance mechanism that satisfies the local differential privacy is utilized to disturb the original location data in each Voronoi grid.In addition,the effectiveness of the proposed privacy-preserving mechanism is verified through comparison experiments.Compared with the existing privacy-preserving methods,the proposed privacy-preserving mechanism can not only better meet users’privacy needs,but also have higher data availability.