Some Properties for the Largest Component of Random Geometric Graphs with Applications in Sensor Networks

In this paper we consider the standard Poisson Boolean model of random geometric graphs G（Hλ,s; 1） in Rd and study the properties of the order of the largest component L1 （G（Hλ,s; 1）） . We prove that ElL1 （G（Hλ,s; 1））] is smooth with respect to A, and is derivable with respect to s. Also, we give the expression of these derivatives. These studies provide some new methods for the theory of the largest component of finite random geometric graphs （not asymptotic graphs as s - co） in the high dimensional space （d 〉 2）. Moreover, we investigate the convergence rate of E[L1（G（Hλ,s; 1））]. These results have significance for theory development of random geometric graphs and its practical application. Using our theories, we construct and solve a new optimal energy-efficient topology control model of wireless sensor networks, which has the significance of theoretical foundation and guidance for the design of network layout.

The Coverage Holes of The Largest Component of Random Geometric Graph

In this paper, a domain in a cube is called a coverage hole if it is not covered by the largest component of the random geometric graph in this cube. We obtain asymptotic properties of the size of the largest coverage hole in the cube. In addition, we give an exponentially decaying tail bound for the probability that a line with length s do not intersect with the coverage of the infinite component of continuum percolation. These results have applications in communication networks and especially in wireless ad-hoc sensor networks.

CONVERGENCE OF A CLASS OF MULTI-AGENT SYSTEMS IN PROBABILISTIC FRAMEWORK

Multi-agent systems arise from diverse fields in natural and artificial systems, and a basic problem is to understand how locally interacting agents lead to collective behaviors （e.g., synchronization） of the overall system. In this paper, we will consider a basic class of multi-agent systems that are described by a simplification of the well-known Vicsek model. This model looks simple, but the rigorous theoretical analysis is quite complicated, because there are strong nonlinear interactions among the agents in the model. In fact, most of the existing results on synchronization need to impose a certain connectivity condition on the global behaviors of the agents＇ trajectories （or on the closed-loop dynamic neighborhood graphs）, which are quite hard to verify in general. In this paper, by introducing a probabilistic framework to this problem, we will provide a complete and rigorous proof for the fact that the overall multi-agent system will synchronize with large probability as long as the number of agents is large enough. The proof is based on a detailed analysis of both the dynamical properties of the nonlinear system evolution and the asymptotic properties of the spectrum of random geometric graphs.

Consensus of Flocks under M-Nearest-Neighbor Rules

This paper investigates a class of flocks with an M-nearest-neighbor rule,where each agent's neighbors are determined according to M nearest agents with M being a given integer,rather than all the agents within a fixed metric distance as in the well-known Vicsek's model.Such a neighbor rule has been validated by biologists through experiments and the authors will prove that,similar to the Vicsek's model,such a new neighbor rule can also achieve consensus under some conditions imposed only on the system's speed and the number M,n,without resorting to any priori connectivity assumptions on the trajectory of the system.In particular,the authors will prove that if the number M is proportional to the population size n,then for any speed v,the system will achieve consensus with large probability if the population size is large enough.

Flocking with General Local Interaction and Large Population

This paper studies a flocking model in which the interaction between agents is described by a general local nonlinear function depending on the distance between agents. The existing analysis provided sufficient conditions for flocking under an assumption imposed on the system’s closed-loop states; however this assumption is hard to verify. To avoid this kind of assumption the authors introduce some new methods including large deviations theory and estimation of spectral radius of random geometric graphs. For uniformly and independently distributed initial states, the authors establish sufficient conditions and necessary conditions for flocking with large population. The results reveal that under some conditions, the critical interaction radius for flocking is almost the same as the critical radius for connectivity of the initial neighbor graph.

On the minimum number of neighbors needed for consensus of flocks

This paper investigates consensus of flocks consisting of n autonomous agents in the plane, where each agent has the same constant moving speed v and updates its heading by the average value of the kn nearest agents from it, with vn and kn being two prescribed parameters depending on n. Such a topological interaction rule is referred to as k,-nearest-neighbors rule, which has been validated for a class of birds by biologists and verified to be robust with respect to disturbances. A theoretical analysis will be presented for this flocking model under a random framework with large population, but without imposing any a priori connectivity assumptions. We will show that the minimum number of k~ needed for consensus is of the order O（log n） in a certain sense. To be precise, there exist two constants C1 〉 C2 〉 0 such that, if k 〉 C1 logn, then the flocking mode] will achieve consensus for any initial headings with high probability, provided that the speed vn is suitably small. On the other hand, if k 〈 Ca ]ogn, then for large n, with probability 1, there exist some initial headings such that consensus cannot be achieved, regardless of the value of Vn.