Distributed Self-Stabilizing Capacitated Maximal Independent Set Construction in Wireless Sensor Networks
Pages 3271 - 3293
Abstract
Wireless sensor networks (WSNs) are composed of a large number of wireless self-organized sensor nodes connected through a wireless decentralized distributed network without the aid of a predefined infrastructure. Fault-tolerance and power management are fundamental challenges in WSNs. A WSN is self-stabilizing if it can initially start at any state and obtain a legitimate state in a finite time without any external intervention. Self-stabilization is an important method for providing fault-tolerance in WSNs. Maximal independent set (MIS) is an extensively used structure for many important applications such as clustering (Randhawa and Jain in Wirel Personal Commun 97(3):3355, 2017. 10.1007/s11277-017-4674-5) and routing (Attea et al. in Wirel Personal Commun 81(2):819, 2015. 10.1007/s11277-014-2159-3; Lipiński in Wirel Personal Commun 101(1):251, 2018. 10.1007/s11277-018-5686-5) in WSNs. The capacitated MIS (CapMIS) problem is an extension of MIS in that each node has a capacity that determines the number of nodes it may dominate. In this paper, we propose a distributed self-stabilizing capacitated maximal independent set algorithm (CapMIS) in order to reduce energy consumption and support load balancing in WSNs. To the best of our knowledge, this is the first algorithm in this manner. The algorithm is validated through theoretical analysis as well as testbed implementations and simulations.
References
[1]
Randhawa S and Jain S Data aggregation in wireless sensor networks: Previous research, current status and future directions Wireless Personal Communications 2017 97 3 3355
[2]
Attea BA, Khalil EA, Ozdemir S, and Yildiz O A multi-objective disjoint set covers for reliable lifetime maximization of wireless sensor networks Wireless Personal Communications 2015 81 2 819
[3]
Lipiński Z Routing algorithm for maximizing lifetime of wireless sensor network for broadcast transmission Wireless Personal Communications 2018 101 1 251
[4]
Rashid B and Rehmani MH Applications of wireless sensor networks for urban areas: A survey Journal of Network and Computer Applications 2016 60 192
[5]
Jain B, Brar G, Malhotra J, and Rani S A novel approach for smart cities in convergence to wireless sensor networks Sustainable Cities and Society 2017 35 440
[6]
Ramson, S. R. J. & Moni, D. J. (2017) In 2017 international conference on innovations in electrical, electronics, instrumentation and media technology (ICEEIMT), pp. 325–329. 10.1109/ICIEEIMT.2017.8116858
[7]
Henry E, Adamchuk V, Stanhope T, Buddle C, and Rindlaub N Precision apiculture: Development of a wireless sensor network for honeybee hives Computers and Electronics in Agriculture 2019 156 138
[8]
Erciyes K Distributed graph algorithms for computer networks 2013 New York Springer
[9]
Akyildiz IF, Melodia T, and Chowdhury KR A survey on wireless multimedia sensor networks Computer Networks 2007 51 4 921
[10]
Singh SP and Sharma S A survey on cluster based routing protocols in wireless sensor networks Procedia Computer Science 2015 45 687
[11]
Rostami AS, Badkoobe M, Mohanna F, keshavarz H, Hosseinabadi AAR, and Sangaiah AK Survey on clustering in heterogeneous and homogeneous wireless sensor networks The Journal of Supercomputing 2018 74 1 277
[12]
Dijkstra EW Self-stabilizing systems in spite of distributed control Communications of the ACM 1974 17 11 643
[13]
Karp RM and Wigderson AA fast parallel algorithm for the maximal independent set problemJournal of the ACM19853247628103360633.68026
[14]
Alon N, Babai L, and Itai AA fast and simple randomized parallel algorithm for the maximal independent set problemJournal of Algorithms1986745678667920631.68063
[15]
Luby MA simple parallel algorithm for the maximal independent set problemSIAM Journal on Computing198615410368613690619.68058
[16]
Goldberg, M. & Spencer, T. (1987). In 28th annual symposium on foundations of computer science (sfcs 1987), pp. 161–165. 10.1109/SFCS.1987.2.
[17]
Łuczak T and Szymańska EA parallel randomized algorithm for finding a maximal independent set in a linear hypergraphJournal of Algorithms199725231114785730887.68048
[18]
Blelloch, G. E., Fineman, J. T. & Shun, J. (2012). In Proceedings of the twenty-fourth annual ACM symposium on parallelism in algorithms and architectures (ACM, New York, NY, USA, 2012), SPAA ’12, pp. 308–317. 10.1145/2312005.2312058.
[19]
Fischer, M. & Noever, A. (2018). In Proceedings of the twenty-ninth annual ACM-SIAM symposium on discrete algorithms (Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, 2018), SODA ’18, pp. 2152–2160.
[20]
Kuhn, F., Moscibroda, T., Nieberg, T. & Wattenhofer R. (2005). In DISC.
[21]
Schneider, J. & Wattenhofer, R. (2008). In Proceedings of the twenty-seventh ACM symposium on principles of distributed computing (ACM, New York, NY, USA, 2008), PODC ’08, pp. 35–44. 10.1145/1400751.1400758.
[22]
Linial NLocality in distributed graph algorithmsSIAM Journal on Computing199221119311488250787.05058
[23]
Scott, A., Jeavons, P., & Xu, L. (2013). In Proceedings of the 2013 ACM symposium on principles of distributed computing (ACM, New York, NY, USA), PODC ’13, pp. 147–156. 10.1145/2484239.2484247.
[24]
Ghaffari, M. (2017). In Proceedings of the ACM symposium on principles of distributed computing (ACM, New York, NY, USA), PODC ’17, pp. 141–149. 10.1145/3087801.3087830.
[25]
Guellati N and Kheddouci H A survey on self-stabilizing algorithms for independence, domination, coloring, and matching in graphs Journal of Parallel and Distributed Computing 2010 70 4 406
[26]
Shukla, S. K., Rosenkrantz, D. J., Ravi, S. S., S, N. & Shukla, E.K. (1995). In Proceedings of the second workshop on self-stabilizing systems, pp. 7–1.
[27]
Hedetniemi SM, Hedetniemi ST, Jacobs DP, and Srimani PKSelf-stabilizing algorithms for minimal dominating sets and maximal independent setsComputers & Mathematics with Applications2003465–68052020439
[28]
Lin JC and Huang TC An efficient fault-containing self-stabilizing algorithm for finding a maximal independent set IEEE Transactions on Parallel and Distributed Systems 2003 14 8 742
[29]
Shi Z, Goddard W, and Hedetniemi STAn anonymous self-stabilizing algorithm for 1-maximal independent set in treesInformation Processing Letters2004912772064647
[30]
Ikeda, M., Kamei, S. & Kakugawa, H. (2002). In Proceedings 3rd international conference on parallel and distributed computing, applications and technologies
[31]
Goddard, W., Hedetniemi, S., Jacobs, D. & Srimani, P. (2003). In Proceedings of parallel and distributed processing symposium, pp. 14.
[32]
Turau VLinear self-stabilizing algorithms for the independent and dominating set problems using an unfair distributed schedulerInformation Processing Letters20071033882323653
[33]
Arapoglu O, Akram VK, and Dagdeviren O An energy-efficient, self-stabilizing and distributed algorithm for maximal independent set construction in wireless sensor networks Computer Standards and Interfaces 2019 62 32
[34]
Kuhn F and Moscibroda TDistributed approximation of capacitated dominating setsTheory of Computing Systems201047481127189181213.68694
[35]
Shang W and Wang X Discrete mathematics Algorithms and Applications 2011 03 01 9
[36]
Kao MJ, Liao CS, and Lee DTCapacitated domination problemAlgorithmica20116022742783117
[37]
Cygan M, Pilipczuk M, and Wojtaszczyk JOCapacitated domination faster than O()Information Processing Letters201111110992893941
[38]
Pradhan DAlgorithmic aspects of k-tuple total domination in graphsInformation Processing Letters2012112218162960327
[39]
Potluri A and Singh A Metaheuristic algorithms for computing capacitated dominating set with uniform and variable capacities Swarm and Evolutionary Computation 2013 13 22
[40]
Liedloff M, Todinca I, and Villanger YSolving capacitated dominating set by using covering by subsets and maximum matchingDiscrete Applied Mathematics2014168603168017
[41]
Kao MJ, Chen HL, and Lee DTCapacitated domination: Problem complexity and approximation algorithmsAlgorithmica201572113332922
[42]
Li R, Hu S, Zhao P, Zhou Y, and Yin M A novel local search algorithm for the minimum capacitated dominating set Journal of the Operational Research Society 2017 69 6 849-863
[43]
Chuzhoy, J. & Naor, J.S. (2002). in The 43rd annual IEEE symposium on foundations of computer science, 2002. Proceedings. pp. 481–489. 10.1109/SFCS.2002.1181972.
[44]
Guha S, Hassin R, Khuller S, and Or ECapacitated vertex coveringJournal of Algorithms200348125720061051079.68074
[45]
Gandhi R, Halperin E, Khuller S, Kortsarz G, and Srinivasan AAn improved approximation algorithm for vertex cover with hard capacitiesJournal of Computer and System Sciences20067211621855351105.68089
[46]
Kao, M. J., Shiau, J. Y., Lin, C. C., & Lee, D. (2019). Tight approximation for partial vertex cover with hard capacities. Theoretical Computer Science. 10.1016/j.tcs.2019.01.027.
[47]
Clark BN, Colbourn CJ, and Johnson DSUnit disk graphsDiscrete Mathematics199086116510885690739.05079
[48]
Inc. M. Iris datasheet. http://www.memsic.com/userfiles/files/Datasheets/WSN/IRIS_Datasheet.pdf. Accessed 1 Sept 2019.
[49]
Karl H and Willig A Protocols and architectures for wireless sensor networks 2005 New York Wiley
[50]
Datta AK, Larmore LL, Devismes S, Heurtefeux K, and Rivierre YSelf-stabilizing small k-dominating setsInternational Journal of Networking and Computing201331161336.68195
Recommendations
Sensor scheduling for p-percent coverage in wireless sensor networks
We study sensor scheduling problems of p-percent coverage in this paper and propose two scheduling algorithms to prolong network lifetime due to the fact that for some applications full coverage is not necessary and different subareas of the monitored ...
The optimization of sensor relocation in wireless mobile sensor networks
Wireless Sensor Networks (WSNs) have been an active research area these years due to their broad range of potential applications. Several research issues, which include energy-aware routing, sensor deployment problems, data aggregation, etc., have been ...
Relay Node Placement in Wireless Sensor Networks
A wireless sensor network consists of many low-cost, low-power sensor nodes, which can perform sensing, simple computation, and transmission of sensed information. Long distance transmission by sensor nodes is not energy efficient since energy ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
© Springer Science+Business Media, LLC, part of Springer Nature 2020.
Publisher
Kluwer Academic Publishers
United States
Publication History
Published: 01 October 2020
Author Tags
Qualifiers
- Research-article
Funding Sources
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 12 Nov 2024
Other Metrics
Citations
View Options
View options
Get Access
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in