We investigate three classes of random graph models, namely random connection graphs, random intersection graphs and a combination thereof known as Kryptographs. Both the models and research questions are driven by applications from the fields of wireless networking and sensor network security: (i) Modeling one-hop connectivity in mobile ad-hoc networks; (ii) Modeling random key pre-distribution; and (iii) Achieving secure connectivity in wireless sensor networks via random key management. Integrating geometric and non-geometric features, as is done in (iii), leads to new and challenging problems. The overall objective of this research is to develop the theoretical foundations to assess system performance, and to help dimension attending resources in wireless networks.
Technically, many of the questions of interest are asymptotic in nature (with the numbers of nodes becoming large) and take the following form: (i) Zero-one laws for graph properties such as graph connectivty and the absence of isolated nodes; (ii) Poisson convergence results which help shed some light on possible phase transitions; and (iii) Approximations to deal with finite node situations. The techniques are probabilistic in nature, with an important place given to the method of first and second moments, and to the Stein-Chen method. Particular emphasis is given to exploring the sensitivity of the results with respect to model assumptions, e.g., distribution of node locations. We expect to make contributions on a number of fronts, namely (i) Advance the study of random graphs, of both the geometric and non-geometric varieties, through probabilistic techniques; (ii) Develop more realistic models for one-hop connectivity in wireless networks; and (iii) Enhance one's understanding of the behavior of large scale wireless networks.
