SEARCH WITHIN CONTENT
Citation Information : International Journal on Smart Sensing and Intelligent Systems. Volume 6, Issue 1, Pages 77-94, DOI: https://doi.org/10.21307/ijssis-2017-529
License : (CC BY-NC-ND 4.0)
Received Date : 02-October-2012 / Accepted: 06-January-2013 / Published Online: 20-February-2013
Suppose n nodes with n0 acquaintances per node are randomly deployed in a two-dimensional Euclidean space with the geographic restriction that each pair of nodes can exchange information between them directly only if the distance between them is at most r, the acquaintanceship between nodes form a random graph, while the physical communication links constitute a random geometric graph. To get a fully connected and secure graph, we introduce a secrecy transfer algorithm which combines the random graph and the random geometric graph via an introduction process to produce an acquaintanceship graph Gn,n0. We find that the maximum component of graph Gn,n0 transitions rapidly from small components to a giant component when n0 is larger than a threshold, the threshold is derived, and applications for sensor networks are presented.
 Bollobás, B.. Random Graphs, 2nd ed. Cambridge University Press, (2001).
 Penrose, M.. Random Geometric Graphs. Oxford studies in probability. Oxford University Press, Oxford, (2003).
 Anderson, R. M. and May, R. M. Susceptible-infectious-recovered epidemic model with dynamic partnerships. Journal of Mathematical Biology, vol. 33, pp. 661–675, (1995).
 Bettstetter, C. On the minimum node degree and connectivity of a wireless multihop network. Proceedings of the third ACM International Symposium on Mobile ad hoc Networking and Computing (MobiHoc 02). ACM, (2002), pp. 80–91.
 Gupta, P. and Kumar, P. The capacity of wireless networks. IEEE Transactions on Information Theory, vol. 46, no. 2, pp. 388–404, March (2000).
 Pietro, R. D., Mancini, L., Mei, A., Panconesi, A. and Radhakrishnan, J. Redoubtable sensor networks. ACM Transactions on Information Systems Security, vol. 11, no. 3, pp. 13–22, (2008).
 Eschenauer, L. and Gligor, V. A key management scheme for distributed sensor networks. Proceedings of the 9th ACM Conference on Computer and Communications Security, CCS’02, (2002), pp. 41–47.
 Liu, Z., Ma, J., Pei, Q., Pang, L., and Park, Y. H. Key infection, secrecy transfer, and key evolution for sensor networks. IEEE Transactions on Wireless Communications, vol. 9, no. 8, pp. 2643–2653, August (2010).
 Anderson, R., Chan, H., and Perrig, A. Key infection: Smart trust for smart dust, ICNP’04, Berlin, Germany, (2004), pp. 24–31.
 Bollobás, B. A probability proof of an asymptotic formula for the number of labelled regular graphs. European Journal of Combinatorics, vol. 1(1980), pp. 311–316, (1980).
 Newman, M. E. J. The structure and function of complex networks. SIAM Review, vol. 45, pp. 167–256, (2003).
 Freris, N. M., Kowshik, H., and Kumar, P. R. Fundamentals of large sensor networks: Connectivity, capacity, clocks, and computation. Proceedings of the IEEE, vol. 98, no. 11, pp. 1828–1846, November (2010).
 Giruka, V. C., Singhal, M., Royalty, J., and Varansi, S. Security in wireless sensor networks. Journal of Wireless Communications and Mobile Computing, vol. 8, pp. 1–24, (2008).
 Liu, Z., Ma, J., Huang, Q., and Moon, S. J. Asymmetric key predistribution scheme for sensor networks. IEEE Transactions on Wireless Communications, vol. 8, no. 3, pp. 1366–1372, March (2009).
 Bloom, B. H. Space/time trade-offs in hash coding with allowable errors. Communications of ACM, vol. 13, no. 7, pp. 422–426, 1970.
 De, P., Liu, Y., and Das, S. K. Deployment-aware modeling of node compromise spread in wireless sensor networks using epidemic theory. ACM Transactions on Sensor Networks., vol. 5, no. 3, pp. 23:1–23:33, 2009.