×

A learning automata-based algorithm for solving coverage problem in directional sensor networks. (English) Zbl 1319.68184

Summary: Wireless sensor networks have been used in a wide variety of applications. Recently, networks consisting of directional sensors have gained prominence. An important challenge facing directional sensor networks (DSNs) is maximizing the network lifetime while covering all the targets in an area. One effective method for saving the sensors’ energy and extending the network lifetime is to partition the DSN into several covers, each of which can cover all targets, and then to activate these covers successively. This paper first proposes a fully distributed algorithm based on irregular cellular learning automata to find a near-optimal solution for selecting each sensor’s appropriate working direction. Then, to find a near-optimal solution that can cover all targets with the minimum number of active sensors, a centralized approximation algorithm is proposed based on distributed learning automata. This algorithm takes advantage of learning automata (LA) to determine the sensors that must be activated at each stage. As the presented algorithm proceeds, the activation process is focused on the sensor nodes that constitute the cover set with the minimum number of active sensors. Through simulations, we indicate that the scheduling algorithm based on LA has better performance than the greedy algorithm-based scheme in terms of maximizing network lifetime.

MSC:

68T05 Learning and adaptive systems in artificial intelligence
68M14 Distributed systems
68Q45 Formal languages and automata
68Q80 Cellular automata (computational aspects)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Amac Guvensan M, Gokhan Yavuz A (2011) On coverage issues in directional sensor networks: a survey. Ad Hoc Netw 9(7):1238–1255 · Zbl 05927811 · doi:10.1016/j.adhoc.2011.02.003
[2] Zorbas D, Glynos D, Kotzanikolaou P, Douligeris C (2010) Solving coverage problems in wireless sensor networks using cover sets. Ad Hoc Netw 8(4):400–415 · Zbl 05738662 · doi:10.1016/j.adhoc.2009.10.003
[3] Yanli C, Wei L, Minglu L, Xiang-Yang L (2007) Target-oriented scheduling in directional sensor networks. In: INFOCOM 2007. 26th IEEE international conference on computer communications. IEEE, New York, 6–12 May 2007, pp 1550–1558 · Zbl 1368.68110
[4] Gil J-M, Kim C-M, Han Y-H (2010) A greedy algorithm for target coverage scheduling in directional sensor networks. J Wirel Mob Netw Ubiquitous Comput Dependable Appl 1:96–106
[5] Cardei M, Du D-Z (2005) Improving wireless sensor network lifetime through power aware organization. Wirel Netw 11(3):333–340. doi: 10.1007/s11276-005-6615-6 · Zbl 02225394 · doi:10.1007/s11276-005-6615-6
[6] Cardei M, Thai MT, Yingshu L, Weili W (2005) Energy-efficient target coverage in wireless sensor networks. In: Proceedings of 24th annual joint conference of the IEEE computer and communications societies (INFOCOM). Miami, FL, USA, pp 1976–1984
[7] Ma H, Liu Y (2005) On coverage problems of directional sensor networks. In: Lecture Notes in Computer Science: Mobile Ad-hoc and Sensor, Networks, vol 3794, pp 721–731
[8] Ai J, Abouzeid A (2006) Coverage by directional sensors in randomly deployed wireless sensor networks. J Comb Optim 11(1).pp 21–41 · Zbl 1132.90004
[9] Wang J, Niu C, Shen R (2009) Priority-based target coverage in directional sensor networks using a genetic algorithm. Comput Math Appl 57:1915–1922 · Zbl 1186.90138 · doi:10.1016/j.camwa.2008.10.019
[10] Akbari Torkestani J, Meybodi MR (2010) An efficient cluster-based CDMA/TDMA scheme for wireless mobile ad-hoc networks: A learning automata approach. J Netw Comput Appl 33(4):477–490 · doi:10.1016/j.jnca.2010.01.004
[11] Akbari Torkestani J, Meybodi MR (2010) An intelligent backbone formation algorithm for wireless ad hoc networks based on distributed learning automata. Comput Netw 54(5):826–843 · Zbl 1213.68102 · doi:10.1016/j.comnet.2009.10.007
[12] Akbari Torkestani J, Meybodi MR (2010) Clustering the wireless Ad Hoc networks: a distributed learning automata approach. J Parallel Distrib Comput 70(4):394–405 · Zbl 1233.68093 · doi:10.1016/j.jpdc.2009.10.002
[13] Akbari Torkestani J (2012) An adaptive backbone formation algorithm for wireless sensor networks. Comput Commun 35(11):1333–1344
[14] Akbari Torkestani J (2012) LAAP: A Learning automata-based adaptive polling scheme for clustered wireless Ad-Hoc networks. Wirel Pers Commun. pp 1–15. doi: 10.1007/s11277-012-0615-5
[15] Esnaashari M, Meybodi MR (2010) A learning automata based scheduling solution to the dynamic point coverage problem in wireless sensor networks. Comput Netw 54(14):2410–2438. doi: 10.1016/j.comnet.2010.03.014 · Zbl 1208.68092 · doi:10.1016/j.comnet.2010.03.014
[16] Torkestani JA, Meybodi MR (2012) A learning automata-based heuristic algorithm for solving the minimum spanning tree problem in stochastic graphs. J Supercomput 59(2):1035–1054. doi: 10.1007/s11227-010-0484-1 · doi:10.1007/s11227-010-0484-1
[17] Akbari Torkestani J, Meybodi MR (2011) A cellular learning automata-based algorithm for solving the vertex coloring problem. Expert Syst Appl 38(8):9237–9247 · doi:10.1016/j.eswa.2011.01.098
[18] Akbari Torkestani J (2011) A new approach to the job scheduling problem in computational grids. Cluster Computing. pp 1–10. doi: 10.1007/s10586-011-0192-5
[19] Akbari Torkestani J (2012) An adaptive learning automata-based ranking function discovery algorithm. J Intell Inf Syst:1–19. doi: 10.1007/s10844-012-0197-4
[20] Zorbas D, Douligeris C (2011) Connected coverage in WSNs based on critical targets. Comput Netw 55(6):1412–1425 · Zbl 05886203 · doi:10.1016/j.comnet.2010.12.023
[21] Fredkin E (1990) Digital mechanics: an informational process based on reversible universal cellular automata. Phys D 45(1–3):254–270. doi: 10.1016/0167-2789(90)90186-s · Zbl 0719.68044 · doi:10.1016/0167-2789(90)90186-S
[22] Packard NH, Wolfram S (1985) Two-dimensional cellular automata. J Stat Phys 38(5):901–946. doi: 10.1007/bf01010423 · Zbl 0625.68038
[23] Najim K, Poznyak AS (1994) Learning automata: theory and applications. Printice-Hall, New York
[24] Beigy H, Meybodi MR (2004) A mathematical framework for cellular learning automata. Adv Complex Syst 7(3–4):295–320 · Zbl 1098.68083
[25] Beigy H, Meybodi MR (2009) Cellular learning automata based dynamic channel assignment algorithms. Int J Comput Intell Appl 8:287–314 · Zbl 1184.68343 · doi:10.1142/S1469026809002618
[26] Beigy H, Meybodi M (2003) A self-organizing channel assignment algorithm: a cellular learning automata approach. Lecture notes in computer science, vol 2690. Springer, pp 119–126
[27] Thathachar MAL, Harita BR (1987) Learning automata with changing number of actions. IEEE Trans Syst Man Cybern 17(6):1095–1100 · doi:10.1109/TSMC.1987.6499323
[28] Nicopolitidis P, Papadimitriou GI, Pomportsis AS, Sarigiannidis P, Obaidat MS (2011) Adaptive wireless networks using learning automata. Wirel Commun IEEE 18(2):75–81 · doi:10.1109/MWC.2011.5751299
[29] Mostafaei H, Meybodi MR, Esnaashari M (2010) EEMLA: energy efficient monitoring of wireless sensor network with learning automata. In: Signal acquisition and processing, 2010. ICSAP ’10. pp 107–111
[30] Yanli C, Wei L, Minglu L, Xiang-Yang L (2009) Energy efficient target-oriented scheduling in directional sensor networks. Comput IEEE Transact 58(9):1259–1274 · Zbl 1368.68110 · doi:10.1109/TC.2009.40
[31] Gil J-M, Han Y-H (2011) A target coverage scheduling scheme based on genetic algorithms in directional sensor networks. Sensors 11(2):1888–1906 · doi:10.3390/s110201888
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.