Orhan DAĞDEVİREN, Vahid KHALILPOUR AKRAM

TAPU: Test and pick up-based k-connectivity restoration algorithm for wireless sensor networks

A k -connected wireless sensor network remains connected if any k -1 arbitrary nodes stop working. The aimof movement-assisted k -connectivity restoration is to preserve the k -connectivity of a network by moving the nodes to the necessary positions after possible failures in nodes. This paper proposes an algorithm named TAPU for k -connectivity restoration that guarantees the optimal movement cost. Our algorithm improves the time and space complexities of the previous approach (MCCR) in both best and worst cases. In the proposed algorithm, the nodes are classified into safe and unsafe groups. Failures of safe nodes do not change the k value of the network while failures of unsafe nodes reduce the k value. After an unsafe node’s failure, the shortest path tree of the failed node is generated. Each node moves to its parent location in the tree starting from a safe node with the minimum moving cost to the root. TAPU has been implemented on simulation and testbed environments including Kobuki robots and Iris nodes. The measurements show that TAPU finds the optimum movement up to 79.5% faster with 50% lower memory usage than MCCR and with up to 59% lower cost than the greedy algorithms.

PDF

___

[1] Abbasi AA, Younis M, Akkaya K. Movement-assisted connectivity restoration in wireless sensor and actor networks. IEEE Transactions on Parallel and Distributed Systems 2009; 20: 1366–1379.
[2] Akram VK, Dagdeviren O. Deck: A distributed, asynchronous and exact k-connectivity detection algorithm for wireless sensor networks. Computer Communications 2018; 116: 9–20.
[3] Al Turjman FM, Hassanein HS. Towards augmented connectivity with delay constraints in WSN federation. International Journal of Ad Hoc and Ubiquitous Computing 2012; 11: 97–108.
[4] Almasaeid HM, Kamal A. On the minimum k-connectivity repair in wireless sensor networks. In: IEEE Conference on Communications, 2009. pp. 195–199.
[5] Bai X, Xuan D, Yun Z, Lai TH, Jia W. Complete optimal deployment patterns for full-coverage and k-connectivity (k≤6) wireless sensor networks. In: 9th ACM International Symposium on Mobile Ad Hoc Networking and Computing, 2008. pp. 401–410.
[6] Barrera J, Cancela H, Moreno E. Topological optimization of reliable networks under dependent failures. Operations Research Letters 2015; 43: 132–136.
[7] Censor-Hillel K, Ghaffari M, Kuhn F. Distributed connectivity decomposition. In: Proceedings of the 2014 ACM Symposium on Principles of Distributed Computing, 2014. pp. 156–165.
[8] Cornejo A, Lynch N. Fault-tolerance through k-connectivity. In: Workshop on Network Science and Systems Issues in Multi-Robot Autonomy, 2010. pp. 2–6.
[9] Dagdeviren O, Akram VK. Pack: Path coloring based k-connectivity detection algorithm for wireless sensor networks. Ad Hoc Networks 2017; 64: 41–52.
[10] Deniz F, Bagci H, Korpeoglu I, Yazici A. An adaptive, energy-aware and distributed fault-tolerant topology-control algorithm for heterogeneous wireless sensor networks. Ad Hoc Networks 2016; 44: 104–117.
[11] Even S. An algorithm for determining whether the connectivity of a graph is at least k. SIAM Journal on Computing 1975; 4: 393–396.
[12] Even S, Tarjan RE. Network flow and testing graph connectivity. SIAM Journal on Computing 1975; 4: 507–518.
[13] Fredman ML, Tarjan RE. Fibonacci heaps and their uses in improved network optimization algorithms. Journal of the ACM 1987; 34: 596–615.
[14] Galil Z. Finding the vertex connectivity of graphs. SIAM Journal on Computing 1980; 9: 197–199.
[15] Georgiou O, Dettmann CP, Coon JP. k-Connectivity for confined random networks. Europhysics Letters 2013; 103: 2–8.
[16] Gupta B, Gupta A. On the k-connectivity of ad-hoc wireless networks. In: 7th International Symposium on Service Oriented Systems, 2013. pp. 546–550.
[17] Henzinger MR, Rao S, Gabow HN. Computing vertex connectivity: new bounds from old techniques. Journal of Algorithms 2000; 34: 222–250.
[18] Imran M, Younis M, Said AM, Hasbullah H. Localized motion-based connectivity restoration algorithms for wireless sensor and actor networks. Journal of Network and Computer Applications 2012; 35: 844–856.
[19] Jia X, Kim D, Makki S, Wan PJ, Yi CW. Power assignment for k-connectivity in wireless ad hoc networks. Journal of Combinatorial Optimization 2005; 9: 213–222.
[20] Jorgic M, Goel N, Kalaichelvan K, Nayak A, Stojmenovic I. Localized detection of k-connectivity in wireless ad hoc, actuator and sensor networks. In: Proceedings of 16th International Conference on Computer Communications and Networks, 2007. pp. 33–38.
[21] Kuhn HW. The Hungarian method for the assignment problem. Naval Research Logistics Quarterly 1955; 2: 83–97.
[22] Natarajan MSG. On the probability of k-connectivity in wireless ad hoc networks under different mobility models. International Journal on Application of Graph Theory in Wireless Ad Hoc Networks and Sensor Networks 2010; 2: 1–13.
[23] Nutov Z. Approximating minimum-power k-connectivity. Ad Hoc and Sensor Wireless Networks 2010; 9: 129–137.
[24] Rahbar AG. Fault tolerant broadcasting analysis in wireless monitoring networks. Turkish Journal of Electrical Engineering & Computer Sciences 2014; 22: 1437–1452.
[25] Ranga V, Dave M, Verma AK. Network partitioning recovery mechanisms in WSANs: a survey. Wireless Personal Communications 2013; 72: 857–917.
[26] Segal M, Shpungin H. On construction of minimum energy k-fault resistant topologies. Ad Hoc Networks 2009; 7: 363–373.
[27] Senturk IF, Akkaya K, Janansefat S. Towards realistic connectivity restoration in partitioned mobile sensor networks. International Journal of Communication Systems 2016; 29: 230–250.
[28] Szczytowski P, Khelil A, Suri N. Dkm: Distributed k-connectivity maintenance in wireless sensor networks. In: 9th Annual Conference on Wireless On-demand Network Systems and Services, 2012. pp. 83–90.
[29] Wan PJ, Yi CW. Asymptotic critical transmission radius and critical neighbor number for k-connectivity in wireless ad hoc networks. In 5th ACM International Symposium on Mobile Ad Hoc Networking and Computing, 2004. pp. 1–8.
[30] Wang S, Mao X, Tang SJ, Li X, Zhao J, Dai G. On movement-assisted connectivity restoration in wireless sensor and actor networks. IEEE Transaction on Parallel and Distributed Systems 2011; 22: 687–694.
[31] Younis M, Akkaya K. Strategies and techniques for node placement in wireless sensor networks:a survey. Ad Hoc Networks 2008; 6: 621–655.
[32] Younis M, Senturk IF, Akkaya K, Lee S, Senel F. Topology management techniques for tolerating node failures in wireless sensor networks: a survey. Computer Networks 2014; 58: 254–283.
[33] Yun Z, Bai X, Xuan D, Lai T. H, Jia W. Optimal deployment patterns for full coverage and k-connectivity (k≤6) wireless sensor networks. IEEE/ACM Transactions on Networking 2010; 18: 934–947.
[34] Zhang H, Hou J. On the critical total power for asymptotic k-connectivity in wireless networks. In: 24th Annual Joint Conference of the IEEE Computer and Communications Societies, 2005. pp. 466–476.
[35] Zhang L, Wang X, Dou W. Design and analysis of a k-connected topology control algorithm for ad hoc networks. In: International Symposium on Parallel and Distributed Processing and Applications, 2004. pp. 178–187.
[36] Zhao J. Minimum node degree and k-connectivity in wireless networks with unreliable links. In: International Symposium on Information Theory, 2014. pp. 246–250.
[37] Zhao J, Yagan O, Gligor V. Exact analysis of k-connectivity in secure sensor networks with unreliable links. In: 13th International Symposium on Modeling and Optimization in Mobile, Ad Hoc and Wireless Networks, 2015. pp. 191–198.
[38] Zhao J, Yagan O, Gligor V. On k-connectivity and minimum vertex degree in random s-intersection graphs. In: Proceedings of the Meeting on Analytic Algorithmics and Combinatorics, 2015. pp. 1–15.