Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Wireless Networks
Published in: Wireless Networks 8/2019

04-05-2018

KEIP: a distributed k-connectivity estimation algorithm based on independent paths for wireless sensor networks

Authors: Orhan Dagdeviren, Vahid Khalilpour Akram

Published in: Wireless Networks | Issue 8/2019

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

Maintaining the connectivity between all nodes is a challenging task in wireless sensor networks (WSNs) because failure of some nodes may divide the network to disconnected parts. A network is k-connected if we need to remove at least k nodes to disconnect it. There are at least k disjoint paths between each pair of nodes in a k-connected network which preserves the connectivity of the network after removing k-1 arbitrary nodes. Therefore, with high k values the network may tolerate more failures without losing its connectivity. Finding the k value of a given network can provide useful information about the robustness of the connectivity. The existing distributed k-connectivity estimation (detection) algorithms use local neighborhood information to find an approximated value for k. In this paper, we propose a new energy efficient distributed algorithm which finds the k value of the given WSN with more accuracy by detecting the minimum number of disjoint paths between the sink and all other nodes. We extend the definition of disjoint paths to independent paths, which are the disjoint paths with shared nodes, and use this concept to find the k value. The comprehensive simulation and testbed results show that the proposed algorithm is faster and has at least 20% higher correct detection ratio, lower mean square error ratio and also lower energy consumption than the existing algorithms.
previous article LiMCA: an optimal clustering algorithm for lifetime maximization of internet of things
next article Congestion control in wireless sensor and 6LoWPAN networks: toward the Internet of Things

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
Literature
1.
Akyildiz, I. F., Su, W., Sankarasubramaniam, Y., & Cayirci, E. (2002). A survey on sensor networks. IEEE Communications Magazine, 40(8), 102–114.CrossRef
2.
Memon, I., & Arain, Q. A. (2017). Dynamic path privacy protection framework for continuous query service over road networks. World Wide Web, 20(4), 639–672.CrossRef
3.
Arain, Q. A., Uqaili, M. A., Deng, Z., Memon, I., Jiao, J., Shaikh, M. A., et al. (2017). Clustering based energy efficient and communication protocol for multiple mix-zones over road networks. Wireless Personal Communications, 95(2), 411–428.CrossRef
4.
5.
Ahmed, H. I., Wei, P., Memon, I., Du, Y., & Xie, W. (2013). Estimation of time difference of arrival (TDoA) for the source radiates BPSK signal. IJCSI International Journal of Computer Science Issues, 10(3), 164–171.
6.
Akhtar, R., Leng, S., Memon, I., Ali, M., & Zhang, L. (2015). Architecture of hybrid mobile social networks for efficient content delivery. Wireless Personal Communications, 80(1), 85–96.CrossRef
7.
Gustav, Y.H., Wang, Y., Domenic, M.K., Zhang, F., & Memon, I. (2013). Velocity similarity anonymization for continuous query location based services. In IEEE international conference on computational problem-solving (ICCP), 2013 (pp. 433–436).
8.
Arain, Q. A., Memon, H., Memon, I., Memon, M. H., Shaikh, R. A., & Mangi, F. A. (2017). Intelligent travel information platform based on location base services to predict user travel behavior from user-generated GPS traces. International Journal of Computers and Applications, 39(3), 155–168.CrossRef
9.
Wang, S., Mao, X., Tang, S. J., Li, X., Zhao, J., & Dai, G. (2011). On movement-assisted connectivity restoration in wireless sensor and actor networks. IEEE Transactions on Parallel and Distributed Systems, 22(4), 687–694.CrossRef
10.
Yilmaz, O., Dagdeviren, O., & Erciyes, K. (2014). Localization-free and energy-efficient hole bypassing techniques for fault-tolerant sensor networks. Journal of Network and Computer Applications, 40, 164–178.CrossRef
11.
Moghadam, M. N., Taheri, H., & Karrari, M. (2014). Minimum cost load balanced multipath routing protocol for low power and lossy networks. Wireless networks, 20(8), 2469–2479.CrossRef
12.
Cornejo, A., & Lynch, N. (2010). Fault-tolerance through k-connectivity. In Workshop on network science and systems issues in multi-robot autonomy: ICRA (vol. 2).
13.
Atay, N. & Bayazit, B. (2009). Mobile wireless sensor network connectivity repair with k-redundancy. Algorithmic Foundation of Robotics VIII (pp. 35–4).
14.
Even, S., & Tarjan, R. E. (1975). Network flow and testing graph connectivity. SIAM Journal on Computing, 4(4), 507–518.MathSciNetCrossRef
15.
Henzinger, M. R., Rao, S., & Gabow, H. N. (2000). Computing vertex connectivity: New bounds from old techniques. Journal of Algorithms, 34(2), 222–250.MathSciNetCrossRef
16.
Jorgic, M., Goel, N., Kalaichevan, K., Nayak, A., & Stojmenovic, I. (2007). Localized detection of k-connectivity in wireless ad hoc, actuator and sensor networks. In IEEE international conference on computer communications and networks, ICCCN, (pp. 3–33).
17.
Szczytowski, P., Khelil, A. & Suri, N. (2012). DKM: Distributed k-connectivity maintenance in wireless sensor networks. In IEEE annual conference on wireless on-demand network systems and services (WONS) (pp. 83–90).
18.
Censor-Hillel, K., Ghaffari, M., & Kuhn, F. (2014). Distributed connectivity decomposition. In Proceedings of the 2014 ACM symposium on principles of distributed computing (pp. 156–165). New York: ACM.
19.
Gupta, B. & Gupta, A. (2013). On the k-connectivity of ad-hoc wireless networks. In IEEE 7th international symposium on service oriented system engineering (SOSE) (pp. 546–550).
20.
Nutov, Z. (2010). Approximating minimum-power k-connectivity. Ad Hoc & Sensor Wireless Networks, 9(1–2), 129–137.
21.
Li, N. & Hou, J. C. (2004) FLSS: A fault-tolerant topology control algorithm for wireless networks. In Proceedings of the 10th ACM annual international conference on Mobile computing and networking (pp. 275–286).
22.
Zeng, H., Zhang, J., & Dai, G. (2013). Construction of low weighted and fault-tolerant topology for wireless ad hoc and sensor network. International Journal of Sensor Networks, 14(4), 197–210.CrossRef
23.
Jia, X., Kim, D., Makki, S., Wan, P. J., & Yi, C. W. (2005). Power assignment for k-connectivity in wireless ad hoc networks. Journal of Combinatorial Optimization, 9(2), 213–222.MathSciNetCrossRef
24.
Guo, W., Xiong, N., Vasilakos, A. V., Chen, G., & Yu, C. (2012). Distributed k-connected fault-tolerant topology control algorithms with PSO in future autonomic sensor systems. International Journal of Sensor Networks, 12(1), 53–62.CrossRef
25.
Ma, H., & Liu, Y. (2007). Some problems of directional sensor networks. International Journal of Sensor Networks, 2(1–2), 44–52.CrossRef
26.
Bagci, H., Korpeoglu, I., & Yazici, A. (2015). A distributed fault-tolerant topology control algorithm for heterogeneous wireless sensor networks. IEEE Transactions on Parallel and Distributed Systems, 26(4), 914–923.CrossRef
27.
Saha, I., Sambasivan, L. K., Ghosh, S. K., & Patro, R. K. (2010). Distributed fault-tolerant topology control in wireless multi-hop networks. Wireless Networks, 16(6), 1511–1524.CrossRef
28.
Ahn, N., & Park, S. (2015). An optimization algorithm for the minimum k-connected m-dominating set problem in wireless sensor networks. Wireless Networks, 21(3), 783–792.CrossRef
29.
Sharma, K. P., & Sharma, T. P. (2016). ZBFR: Zone based failure recovery in WSNs by utilizing mobility and coverage overlapping. Wireless Networks, 23, 1–18.CrossRef
30.
Zhang, L., Wang, X., & Dou, W. (2004). Design and analysis of a k-connected topology control algorithm for ad hoc networks. In International symposium on parallel and distributed processing and applications (pp. 178–187). Berlin: Springer.
31.
Younis, M., Senturk, I. F., Akkaya, K., Lee, S., & Senel, F. (2014). Topology management techniques for tolerating node failures in wireless sensor networks: A survey. Computer Networks, 58, 254–283.CrossRef
32.
Almasaeid, H.M. & Kamal, A.E. (2009). On the minimum k-connectivity repair in wireless sensor networks. IEEE international conference on communications (pp. 1–5).
33.
Yun, Z., Bai, X., Xuan, D., Lai, T. H., & Jia, W. (2010). Optimal deployment patterns for full coverage and k-connectivity (\(\text{ k }\le 6\)) wireless sensor networks. IEEE/ACM Transactions on Networking (TON), 18(3), 934–947.CrossRef
34.
Georgiou, O., Dettmann, C. P., & Coon, J. P. (2013). k-connectivity for confined random networks. EPL (Europhysics Letters), 103(2), 28006.CrossRef
35.
36.
Pishro-Nik, H., Chan, K., & Fekri, F. (2009). Connectivity properties of large-scale sensor networks. Wireless Networks, 15(7), 945–964.CrossRef
37.
Zhao, J., Yagan, O., & Gligor, V. (2015). Exact analysis of k-connectivity in secure sensor networks with unreliable links. In 13th IEEE international symposium on modeling and optimization in mobile, ad hoc, and wireless networks (WiOpt), 2015.
38.
Verma, V. K., Singh, S., & Pathak, N. P. (2014). Comprehensive event based estimation of sensor node distribution strategies using classical flooding routing protocol in wireless sensor networks. Wireless Networks, 20(8), 2349–2357.CrossRef
39.
Erdos, P., Pach, J., Pollack, R., & Tuza, Z. (1989). Radius, diameter, and minimum degree. Journal of Combinatorial Theory, Series B, 47(1), 73–79.MathSciNetCrossRef
40.
41.
Levis, P., Madden, S., Polastre, J., Szewczyk, R., Whitehouse, K., Woo, A., & Culler, D. (2005). Tinyos: An operating system for sensor networks. In W. Weber, J. M. Rabaey, & E. Aarts (Eds.), Ambient intelligence (pp. 115–148). Springer.
42.
Levis, P., Lee, N., Welsh, M. & Culler, D. (2003). TOSSIM: Accurate and scalable simulation of entire TinyOS applications. In International conference on embedded networked sensor systems (pp. 126–137), ACM.
Metadata
Title
KEIP: a distributed k-connectivity estimation algorithm based on independent paths for wireless sensor networks
Authors
Orhan Dagdeviren
Vahid Khalilpour Akram
Publication date
04-05-2018
Publisher
Springer US
Published in
Wireless Networks / Issue 8/2019
Print ISSN: 1022-0038
Electronic ISSN: 1572-8196
DOI
https://doi.org/10.1007/s11276-018-1739-7

Other articles of this Issue 8/2019

Wireless Networks 8/2019 Go to the issue

OriginalPaper

A survey on wireless sensor network databases

OriginalPaper

Congestion control in wireless sensor and 6LoWPAN networks: toward the Internet of Things

OriginalPaper

SER and throughput analysis of space–time analog network coded relaying system over shadowed Rician fading channels

OriginalPaper

The controller placement problem for wireless SDN

OriginalPaper

Iterative hybrid precoder and combiner design for mmWave MIMO-OFDM systems

OriginalPaper

Resource refrain quota based routing protocol for delay tolerant network