Evolution of scale-free wireless sensor networks with feature of small-world networks. (English) Zbl 1373.90025

Summary: Scale-free networks and small-world networks are the most impacting discoveries in the complex networks theories and have already been successfully proved to be highly effective in improving topology structures of Wireless Sensor Networks (WSNs). However, currently both theories are not jointly applied to have further improvements in the generation of WSN topologies. Therefore, this paper proposes a cluster-structured evolution model of WSNs considering the characteristics of both networks. With introduction of energy sensitivity and maximum limitation of degrees that a cluster head could have, the performance of our model can be ensured. In order to give an overall assessment of lifting effects of shortcuts, four placement schemes of shortcuts are analyzed. The characteristics of small-world network and scale-free network of our model are proved via theoretical derivation and simulations. Besides, we find that, by introducing shortcuts into scale-free wireless sensor network, the performance of the network can be improved concerning energy-saving and invulnerability, and we discover that the schemes constructing shortcuts between cluster heads and the sink node have better promoted effects than the scheme building shortcuts between pairs of cluster heads, and the schemes based on the preferential principle are superior to the schemes based on the random principle.


90B10 Deterministic network models in operations research
90B18 Communication networks in operations research
Full Text: DOI


[1] Li, W.-F.; Fu, X.-W., Survey on invulnerability of wireless sensor networks, Jisuanji Xuebao/Chinese Journal of Computers, 38, 3, 625-647, (2015)
[2] Fortino, G.; Guerrieri, A.; O’Hare, G. M. P.; Ruzzelli, A., A flexible building management framework based on wireless sensor and actuator networks, Journal of Network and Computer Applications, 35, 6, 1934-1952, (2012)
[3] Meseguer, R.; Molina, C.; Ochoa, S. F.; Santos, R., Energy-aware topology control strategy for human-centric wireless sensor networks, Sensors (Switzerland), 14, 2, 2619-2643, (2014)
[4] Fichera, L.; Messina, F.; Pappalardo, G.; Santoro, C., A Python framework for programming autonomous robots using a declarative approach, Science of Computer Programming, 139, 36-55, (2017)
[5] Nazi, A.; Raj, M.; Di Francesco, M.; Ghosh, P.; Das, S. K., Deployment of robust wireless sensor networks using gene regulatory networks: An isomorphism-based approach, Pervasive and Mobile Computing, 13, 246-257, (2014)
[6] De Benedetti, M.; Messina, F.; Pappalardo, G.; Santoro, C., JarvSis: a distributed scheduler for IoT applications, Cluster Computing, 20, 2, 1-16, (2017)
[7] Strogatz, S. H., Exploring complex networks, Nature, 410, 6825, 268-276, (2001) · Zbl 1370.90052
[8] Karrer, B.; Newman, M. E. J., Competing epidemics on complex networks, Physical Review E, 84, 3, (2011)
[9] Barabási, A. L.; Albert, R.; Jeong, H., Mean-field theory for scale-free random networks, Physica A: Statistical Mechanics and its Applications, 272, 1, 173-187, (1999)
[10] Pastor-Satorras, R.; Vespignani, A., Epidemic spreading in scale-free networks, Physical Review Letters, 86, 14, 3200-3203, (2001)
[11] Rubinov, M.; Sporns, O., Complex network measures of brain connectivity: Uses and interpretations, NeuroImage, 52, 3, 1059-1069, (2010)
[12] Watts, D. J.; Strogatz, S. H., Collective dynamics of “small-world” networks, Nature, 393, 6684, 440-442, (1998) · Zbl 1368.05139
[13] Chen, L.-J.; Chen, D.-X.; Xie, L.; Cao, J.-N., Evolution of wireless sensor network, Proceedings of the IEEE Wireless Communications and Networking Conference (WCNC ’07)
[14] Zhu, H.; Luo, H.; Peng, H.; Li, L.; Luo, Q., Complex networks-based energy-efficient evolution model for wireless sensor networks, Chaos, Solitons and Fractals, 41, 4, 1828-1835, (2009)
[15] Li, S.; Li, L.; Yang, Y., A local-world heterogeneous model of wireless sensor networks with node and link diversity, Physica A: Statistical Mechanics and Its Applications, 390, 6, 1182-1191, (2011)
[16] Jiang, N.; Chen, H.; Xiao, X., A local world evolving model for energy-constrained wireless sensor networks, International Journal of Distributed Sensor Networks, 2012, (2012)
[17] Qi, X.; Ma, S.; Zheng, G., Topology evolution of wireless sensor networks based on adaptive free-scale networks, Journal of Information and Computational Science, 8, 3, 467-475, (2011)
[18] Zheng, G.; Liu, S.; Qi, X., Scale-free topology evolution for wireless sensor networks with reconstruction mechanism, Computers and Electrical Engineering, 38, 3, 643-651, (2012)
[19] Chen, L.-J.; Liu, M.; Chen, D.-X.; Xie, L., Topology evolution of wireless sensor networks among cluster heads by random walkers, Jisuanji Xuebao/Chinese Journal of Computers, 32, 1, 69-76, (2009)
[20] Wang, Y. Q.; Yang, X. Y., A random walk evolution model of wireless sensor networks and virus spreading, Chinese Physics B, 22, 1, (2013)
[21] Helmy, A., Small worlds in wireless networks, IEEE Communications Letters, 7, 10, 490-492, (2003)
[22] Chitradurga, R.; Helmy, A., Analysis of Wired Short Cuts in Wireless Sensor Networks, Proceedings of the The IEEE/ACS International Conference on Pervasive Services
[23] Sharma, G.; Mazumdar, R., Hybrid sensor networks: a small world, Proceedings of the 6th ACM International Symposium on Mobile Ad Hoc Networking and Computing
[24] Hawick, K. A.; James, H. A., Small-world effects in wireless agent sensor networks, International Journal of Wireless and Mobile Computing, 4, 3, 155-164, (2010)
[25] Toyonaga, S.; Kominami, D.; Murata, M., Virtual wireless sensor networks: Adaptive brain-inspired configuration for internet of things applications, Sensors (Switzerland), 16, 8, article no. 1323, (2016)
[26] Guidoni, D. L.; Mini, R. A. F.; Loureiro, A. A. F., On the design of heterogeneous sensor networks based on small world concepts, Proceedings of the 11th ACM International Conference on Modeling, Analysis, and Simulation of Wireless and Mobile Systems, MSWiM’08
[27] Guidoni, D. L.; Mini, R. A. F.; Loureiro, A. A. F., On the design of resilient heterogeneous wireless sensor networks based on small world concepts, Computer Networks, 54, 8, 1266-1281, (2010) · Zbl 1204.68017
[28] Fu, X.; Li, W.; Fortino, G., Empowering the invulnerability of wireless sensor networks through super wires and super nodes, Proceedings of the 13th IEEE/ACM International Symposium on Cluster, Cloud, and Grid Computing, CCGrid 2013
[29] Lei, L.; Kuang, Y.; Shen, X. S.; Yang, K.; Qiao, J.; Zhong, Z., Optimal reliability in energy harvesting industrial wireless sensor networks, IEEE Transactions on Wireless Communications, 15, 8, 5399-5413, (2016)
[30] Dorogovtsev, S. N.; Mendes, J. F. F.; Samukhin, A. N., Structure of growing networks with preferential linking, Physical Review Letters, 85, 21, 4633-4636, (2000)
[31] Krapivsky, P. L.; Redner, S.; Leyvraz, F., Connectivity of growing random networks, Physical Review Letters, 85, 21, 4629-4632, (2000)
[32] Sarshar, N.; Roychowdhury, V., Scale-free and stable structures in complex ad hoc networks, Physical Review E—Statistical, Nonlinear, and Soft Matter Physics, 69, 2, 1-6, (2004)
[33] Heinzelman, W. R.; Chandrakasan, A.; Balakrishnan, H., Energy-efficient communication protocol for wireless microsensor networks, Proceedings of the 33rd Annual Hawaii International Conference on System Siences (HICSS ’00), IEEE
[34] Wu, X.; Chen, G.; Das, S. K., Avoiding energy holes in wireless sensor networks with nonuniform node distribution, IEEE Transactions on Parallel and Distributed Systems, 19, 5, 710-720, (2008)
[35] Albert, R.; Jeong, H.; Barabási, A.-L., Error and attack tolerance of complex networks, Nature, 406, 6794, 378-382, (2000)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.