×

zbMATH — the first resource for mathematics

Convergence of distributed WSN algorithms: The wake-up scattering problem. (English) Zbl 1237.90105
Majumdar, Rupak (ed.) et al., Hybrid systems: Computation and control. 12th international conference, HSCC 2009, San Francisco, CA, USA, April 13–15, 2009. Proceedings. Berlin: Springer (ISBN 978-3-642-00601-2/pbk). Lecture Notes in Computer Science 5469, 180-193 (2009).
Summary: In this paper, we analyze the problem of finding a periodic schedule for the wake-up times of a set of nodes in a wireless sensor network that optimizes the coverage of the region the nodes are deployed on. An exact solution of the problem entails the solution of an integer linear program and is hardly viable on low power nodes. A. Giusti, A. L. Murphy and G. P. Picco [“Decentralized scattering of wake-up times in wireless sensor networks”, Lect. Notes Comput. Sci. 4373, 245–260 (2007)] have recently proposed an efficient decentralized approach that produces a generally good suboptimal solution. In this paper, we study the convergence of this algorithm by casting the problem into one of asymptotic stability for a particular class of linear switching systems. For general topologies of the WSN, we offer local stability results. In some specific special cases, we are also able to prove global stability properties.
For the entire collection see [Zbl 1161.93001].
MSC:
90B36 Stochastic scheduling theory in operations research
90C59 Approximation methods and heuristics in mathematical programming
93C55 Discrete-time control/observation systems
93D05 Lyapunov and other classical stabilities (Lagrange, Poisson, \(L^p, l^p\), etc.) in control theory
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Alfieri, A., Bianco, A., Brandimarte, P., Chiasserini, C.F.: Maximizing system lifetime in wireless sensor networks. European Journal of Operational Research 127(1), 390–402 (2007) · Zbl 1121.90309 · doi:10.1016/j.ejor.2006.05.037
[2] Cărbunar, B., Grama, A., Vitek, J., Cărbunar, O.: Redundancy and coverage detection in sensor networks. ACM Transaction on Sensor Networks 2(1), 94–128 (2006) · doi:10.1145/1138127.1138131
[3] Cao, Q., Abdelzaher, T., He, T., Stankovic, J.: Towards optimal sleep scheduling in sensor networks for rare-event detection. In: Proc. of the 4th Int. Symp. on Information Processing in Sensor Networks (IPSN) (April 2005) · doi:10.1109/IPSN.2005.1440887
[4] Cardei, M., Thai, M., Li, Y., Wu, W.: Energy-efficient target coverage in wireless sensor networks. In: Proc. of INFOCOM (2005) · doi:10.1109/INFCOM.2005.1498475
[5] Carli, R., Fagnani, F., Speranzon, A., Zampieri, S.: Communication constraints in the average consensus problem. Automatica 44(3), 671–684 (2008) · Zbl 1283.93014 · doi:10.1016/j.automatica.2007.07.009
[6] Giusti, A., Murphy, A.L., Picco, G.P.: Decentralized Scattering of Wake-up Times in Wireless Sensor Networks. In: Langendoen, K.G., Voigt, T. (eds.) EWSN 2007. LNCS, vol. 4373, pp. 245–260. Springer, Heidelberg (2007) · doi:10.1007/978-3-540-69830-2_16
[7] Hsin, C., Liu, M.: Network coverage using low duty-cycled sensors: Random & coordinated sleep algorithms. In: Proc. of the 3th Int. Symp. on Information Processing in Sensor Networks (IPSN) (2004) · doi:10.1145/984622.984685
[8] Jadbabaie, A., Lin, J., Morse, A.S.: Coordination of groups of mobile autonomous agents using nearest neighbor rules. IEEE Trans. on Automatic Control 48(6), 988–1001 (2003) · Zbl 1364.93514 · doi:10.1109/TAC.2003.812781
[9] Liu, H., Jia, X., Wan, P., Yi, C., Makki, S., Pissinou, N.: Maximizing lifetime of sensor surveillance systems. IEEE/ACM Trans. on Networking 15(2), 334–345 (2007) · doi:10.1109/TNET.2007.892883
[10] Marshall, J.A., Broucke, M.E., Francis, B.A.: Formations of vehicles in cyclic pursuit. IEEE Trans. on Automatic Control 49(11), 1963–1974 (2004) · Zbl 1366.91027 · doi:10.1109/TAC.2004.837589
[11] Martínez, S., Bullo, F.: Optimal sensor placement and motion coordination for target tracking. Automatica 42(4), 661–668 (2006) · Zbl 1110.93050 · doi:10.1016/j.automatica.2005.12.018
[12] Martinez, S., Bullo, F., Cortes, J., Frazzoli, E.: On synchronous robotic networks - Part I: Models, tasks and complexity. IEEE Trans. on Automatic Control 52(12), 2199–2213 (2007) · Zbl 1366.93388 · doi:10.1109/TAC.2007.908301
[13] Martinez, S., Bullo, F., Cortes, J., Frazzoli, E.: On synchronous robotic networks - Part II: Time complexity of rendezvous and deployment algorithms. IEEE Trans. on Automatic Control 52(12), 2214–2226 (2007) · Zbl 1366.93389 · doi:10.1109/TAC.2007.908304
[14] Meyer, C.D. (ed.): Matrix analysis and applied linear algebra. Society for Industrial and Applied Mathematics, Philadelphia (2000)
[15] Olfati-Saber, R., Fax, J.A., Murray, R.M.: Consensus and cooperation in networked multi–agent systems. Proc. of IEEE 95(1), 215–233 (2007) · Zbl 1376.68138 · doi:10.1109/JPROC.2006.887293
[16] Palopoli, L., Passerone, R., Picco, G.P., Murphy, A.L., Giusti, A.: Maximizing sensing coverage in wireless sensor networks through optimal scattering of wake-up times. Technical Report DIT-07-048, Dipartimento di Informatica e Telecomunicazioni, University of Trento (July 2007)
[17] Slijepcevic, S., Potkonjak, M.: Power efficient organization of wireless sensor networks. In: Proc. of the IEEE Int. Conf. on Communications (ICC) (June 2001) · doi:10.1109/ICC.2001.936985
[18] Tian, D., Georganas, N.D.: A coverage-preserving node scheduling scheme for large wireless sensor networks. In: First ACM Int. Wkshp. on Wireless Sensor networks and Applications (WSNA) (2002) · doi:10.1145/570738.570744
[19] Ye, F., Zhong, G., Cheng, J., Lu, S., Zhang, L.: PEAS: A robust energy conserving protocol foo long-lived sensor networks. In: 3rd Int. Conf. on Distributed Computing Systems (ICDCS 2003) (May 2003)
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.