American Institute of Mathematical Sciences

Advanced
2011, 1(4): 763-780. doi: 10.3934/naco.2011.1.763

Markovian characterization of node lifetime in a time-driven wireless sensor network

Sebastià Galmés 1,

1. 

Department of Mathematics and Computer Science, University of Balearic Islands, 07122, Palma, Spain

Received  June 2011 Revised  August 2011 Published  November 2011

While feeling honoured for being invited to write a paper dedicated to Prof. Yutaka Takahashi, I was enthusiastically wondering how to connect my current research on sensor networks to his excellent professional profile. The question or, better, the answer, was not simple. Considering, for instance, the field of Markov chains, as far as I know there are hardly works in literature that use this well-known modelling paradigm to represent the operational states of a sensor network. However, in a very recent work on time-driven sensor networks, I proposed the exponential randomization of the sense-and-transmit process, in order to avoid tight synchronization requirements while preserving good expectations in terms of lifetime and reconstruction quality. But$\ldots{}$oh, I said exponential, that's the connection! $\ldots{}$ So, specifically, in this paper a Markov chain is constructed to characterize the activity of a node in a time-driven sensor network based on stochastic (exponential) sampling. Since this activity can be translated to energy consumption, the exact solution to the Markov chain yields the complete statistical distribution of node lifetime. The effects of several parameters on the average and variance of this lifetime are also analyzed in detail.
Keywords: continuous-time Markov chain, embedded discrete-time Markov chain, squared coefficient of variation., multi-dimensional sampling theorem, Wireless sensor network.
Mathematics Subject Classification: Primary: 90B18; Secondary: 60J1.
Citation: Sebastià Galmés. Markovian characterization of node lifetime in a time-driven wireless sensor network. Numerical Algebra, Control & Optimization, 2011, 1 (4) : 763-780. doi: 10.3934/naco.2011.1.763
References:
[1]

K. Akkaya and M. Younis, A survey on routing protocols for wireless sensor networks, Ad Hoc Networks, 3 (2005), 325-349. Google Scholar

[2]

A. V. Balakrishnan, On the problem of time jitter in sampling, IRE Trans. Inf. Theory, 8 (1962), 226-236. Google Scholar

[3]

G. Bolch, S. Greiner, H. de Meer and K. S. Trivedi, "Queueing Networks and Markov Chains," 2nd edition, Wiley, New York, 1998. doi: 10.1002/0471200581.  Google Scholar

[4]

R. L. Cook, Stochastic sampling in computer graphics, ACM Trans. on Graphics, 5 (1986), 51-72. doi: 10.1145/7529.8927.  Google Scholar

[5]

S. Galmés, System design issues in time-driven sensor networks based on stochastic sampling, Simulation Modelling, Practice and Theory, 19 (2011), 1530-1543. doi: 10.1016/j.simpat.2011.04.006.  Google Scholar

[6]

S. Galmés and R. Puigjaner, Randomized data-gathering protocol for time-driven sensor networks, Computer Networks Journal, 55 (2011), 3863-3885. doi: 10.1016/j.comnet.2011.08.002.  Google Scholar

[7]

J. R. Higgins, "Sampling Theory in Fourier and Signal Analysis: Foundations," Oxford University Press, Oxford, 1996. Google Scholar

[8]

H. Karl and A. Willig, "Protocols and Architectures for Wireless Sensor Networks," Wiley, New York, 2005. Google Scholar

[9]

B. Krishnamachari, "Networking Wireless Sensors," Cambridge University Press, Cambridge, 2005. doi: 10.1017/CBO9780511541025.  Google Scholar

[10]

A. Kumar, P. Ishwar and K. Ramchandran, On distributed sampling of smooth non-bandlimited fields, in ''Proc. of the Third International Symposium on Information Processing in Sensor Networks," Berkeley, CA, USA, (2004), 89-98. Google Scholar

[11]

A. Kumar, P. Ishwar and K. Ramchandran, On distributed sampling of bandlimited and non-bandlimited sensor fields, in ''Proc. of IEEE International Conference on Acoustics, Speech, and Signal Processing," Montreal, Canada, (2004), III-925-III-928. Google Scholar

[12]

, "OMNeT++ Community Site," OMNeT++ 3.x documentation and tutorials,, 2005. Available from: , ().   Google Scholar

[13]

A. V. Oppenheim, A. S. Willsky and I. T. Young, "Signals and Systems," Prentice-Hall, New Jersey, 1983. Google Scholar

[14]

G. Reise and G. Matz, Distributed sampling and reconstruction of non-bandlimited fields in sensor networks based on shift-invariant spaces, in ''Proc. of IEEE International Conference on Acoustics, Speech, and Signal Processing," Taipei, Taiwan, (2009), 2061-2064. Google Scholar

[15]

M. L. Santamaría, S. Galmés and R. Puigjaner, Simulated annealing approach to optimizing the lifetime of sparse time-driven sensor networks, in ''Proc. of 2009 IEEE International Symposium on Modeling, Analysis & Simulation of Computer and Telecommunication Systems," London, UK, (2009), 193-202. Google Scholar

[16]

I. Stojmenovic, "Handbook of Sensor Networks: Algorithms and Architectures," Wiley, New York, 2005. Google Scholar

[17]

S. Tilak, N. Abu-Ghazaleh and W. R. Heinzelman, A taxonomy of wireless micro-sensor network models, ACM Mobile Computing and Communications Review (MC2R), 6 (2002), 28-36. Google Scholar

[18]

Y. Yu, V. K. Prasanna and B. Krishnamachari, Energy minimization for real-time data gathering in wireless sensor networks, IEEE Trans. on Wireless Communications, 5 (2006), 3087-3096. doi: 10.1109/TWC.2006.04709.  Google Scholar

show all references

References:
[1]

K. Akkaya and M. Younis, A survey on routing protocols for wireless sensor networks, Ad Hoc Networks, 3 (2005), 325-349. Google Scholar

[2]

A. V. Balakrishnan, On the problem of time jitter in sampling, IRE Trans. Inf. Theory, 8 (1962), 226-236. Google Scholar

[3]

G. Bolch, S. Greiner, H. de Meer and K. S. Trivedi, "Queueing Networks and Markov Chains," 2nd edition, Wiley, New York, 1998. doi: 10.1002/0471200581.  Google Scholar

[4]

R. L. Cook, Stochastic sampling in computer graphics, ACM Trans. on Graphics, 5 (1986), 51-72. doi: 10.1145/7529.8927.  Google Scholar

[5]

S. Galmés, System design issues in time-driven sensor networks based on stochastic sampling, Simulation Modelling, Practice and Theory, 19 (2011), 1530-1543. doi: 10.1016/j.simpat.2011.04.006.  Google Scholar

[6]

S. Galmés and R. Puigjaner, Randomized data-gathering protocol for time-driven sensor networks, Computer Networks Journal, 55 (2011), 3863-3885. doi: 10.1016/j.comnet.2011.08.002.  Google Scholar

[7]

J. R. Higgins, "Sampling Theory in Fourier and Signal Analysis: Foundations," Oxford University Press, Oxford, 1996. Google Scholar

[8]

H. Karl and A. Willig, "Protocols and Architectures for Wireless Sensor Networks," Wiley, New York, 2005. Google Scholar

[9]

B. Krishnamachari, "Networking Wireless Sensors," Cambridge University Press, Cambridge, 2005. doi: 10.1017/CBO9780511541025.  Google Scholar

[10]

A. Kumar, P. Ishwar and K. Ramchandran, On distributed sampling of smooth non-bandlimited fields, in ''Proc. of the Third International Symposium on Information Processing in Sensor Networks," Berkeley, CA, USA, (2004), 89-98. Google Scholar

[11]

A. Kumar, P. Ishwar and K. Ramchandran, On distributed sampling of bandlimited and non-bandlimited sensor fields, in ''Proc. of IEEE International Conference on Acoustics, Speech, and Signal Processing," Montreal, Canada, (2004), III-925-III-928. Google Scholar

[12]

, "OMNeT++ Community Site," OMNeT++ 3.x documentation and tutorials,, 2005. Available from: , ().   Google Scholar

[13]

A. V. Oppenheim, A. S. Willsky and I. T. Young, "Signals and Systems," Prentice-Hall, New Jersey, 1983. Google Scholar

[14]

G. Reise and G. Matz, Distributed sampling and reconstruction of non-bandlimited fields in sensor networks based on shift-invariant spaces, in ''Proc. of IEEE International Conference on Acoustics, Speech, and Signal Processing," Taipei, Taiwan, (2009), 2061-2064. Google Scholar

[15]

M. L. Santamaría, S. Galmés and R. Puigjaner, Simulated annealing approach to optimizing the lifetime of sparse time-driven sensor networks, in ''Proc. of 2009 IEEE International Symposium on Modeling, Analysis & Simulation of Computer and Telecommunication Systems," London, UK, (2009), 193-202. Google Scholar

[16]

I. Stojmenovic, "Handbook of Sensor Networks: Algorithms and Architectures," Wiley, New York, 2005. Google Scholar

[17]

S. Tilak, N. Abu-Ghazaleh and W. R. Heinzelman, A taxonomy of wireless micro-sensor network models, ACM Mobile Computing and Communications Review (MC2R), 6 (2002), 28-36. Google Scholar

[18]

Y. Yu, V. K. Prasanna and B. Krishnamachari, Energy minimization for real-time data gathering in wireless sensor networks, IEEE Trans. on Wireless Communications, 5 (2006), 3087-3096. doi: 10.1109/TWC.2006.04709.  Google Scholar

[1]

Xi Zhu, Meixia Li, Chunfa Li. Consensus in discrete-time multi-agent systems with uncertain topologies and random delays governed by a Markov chain. Discrete & Continuous Dynamical Systems - B, 2020, 25 (12) : 4535-4551. doi: 10.3934/dcdsb.2020111
[2]

Angelica Pachon, Federico Polito, Costantino Ricciuti. On discrete-time semi-Markov processes. Discrete & Continuous Dynamical Systems - B, 2021, 26 (3) : 1499-1529. doi: 10.3934/dcdsb.2020170
[3]

Ran Dong, Xuerong Mao. Asymptotic stabilization of continuous-time periodic stochastic systems by feedback control based on periodic discrete-time observations. Mathematical Control & Related Fields, 2020, 10 (4) : 715-734. doi: 10.3934/mcrf.2020017
[4]

Lakhdar Aggoun, Lakdere Benkherouf. A Markov modulated continuous-time capture-recapture population estimation model. Discrete & Continuous Dynamical Systems - B, 2005, 5 (4) : 1057-1075. doi: 10.3934/dcdsb.2005.5.1057
[5]

Yueyuan Zhang, Yanyan Yin, Fei Liu. Robust observer-based control for discrete-time semi-Markov jump systems with actuator saturation. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020105
[6]

Samuel N. Cohen, Lukasz Szpruch. On Markovian solutions to Markov Chain BSDEs. Numerical Algebra, Control & Optimization, 2012, 2 (2) : 257-269. doi: 10.3934/naco.2012.2.257
[7]

Samuel N. Cohen. Uncertainty and filtering of hidden Markov models in discrete time. Probability, Uncertainty and Quantitative Risk, 2020, 5 (0) : 4-. doi: 10.1186/s41546-020-00046-x
[8]

Piotr Oprocha. Chain recurrence in multidimensional time discrete dynamical systems. Discrete & Continuous Dynamical Systems, 2008, 20 (4) : 1039-1056. doi: 10.3934/dcds.2008.20.1039
[9]

Abhyudai Singh, Roger M. Nisbet. Variation in risk in single-species discrete-time models. Mathematical Biosciences & Engineering, 2008, 5 (4) : 859-875. doi: 10.3934/mbe.2008.5.859
[10]

Badal Joshi. A detailed balanced reaction network is sufficient but not necessary for its Markov chain to be detailed balanced. Discrete & Continuous Dynamical Systems - B, 2015, 20 (4) : 1077-1105. doi: 10.3934/dcdsb.2015.20.1077
[11]

Ajay Jasra, Kody J. H. Law, Yaxian Xu. Markov chain simulation for multilevel Monte Carlo. Foundations of Data Science, 2021, 3 (1) : 27-47. doi: 10.3934/fods.2021004
[12]

Hyukjin Lee, Cheng-Chew Lim, Jinho Choi. Joint backoff control in time and frequency for multichannel wireless systems and its Markov model for analysis. Discrete & Continuous Dynamical Systems - B, 2011, 16 (4) : 1083-1099. doi: 10.3934/dcdsb.2011.16.1083
[13]

Joon Kwon, Panayotis Mertikopoulos. A continuous-time approach to online optimization. Journal of Dynamics & Games, 2017, 4 (2) : 125-148. doi: 10.3934/jdg.2017008
[14]

Hanqing Jin, Xun Yu Zhou. Continuous-time portfolio selection under ambiguity. Mathematical Control & Related Fields, 2015, 5 (3) : 475-488. doi: 10.3934/mcrf.2015.5.475
[15]

Zhigang Zeng, Tingwen Huang. New passivity analysis of continuous-time recurrent neural networks with multiple discrete delays. Journal of Industrial & Management Optimization, 2011, 7 (2) : 283-289. doi: 10.3934/jimo.2011.7.283
[16]

Jingzhi Tie, Qing Zhang. An optimal mean-reversion trading rule under a Markov chain model. Mathematical Control & Related Fields, 2016, 6 (3) : 467-488. doi: 10.3934/mcrf.2016012
[17]

Ralf Banisch, Carsten Hartmann. A sparse Markov chain approximation of LQ-type stochastic control problems. Mathematical Control & Related Fields, 2016, 6 (3) : 363-389. doi: 10.3934/mcrf.2016007
[18]

Kun Fan, Yang Shen, Tak Kuen Siu, Rongming Wang. On a Markov chain approximation method for option pricing with regime switching. Journal of Industrial & Management Optimization, 2016, 12 (2) : 529-541. doi: 10.3934/jimo.2016.12.529
[19]

Z.G. Feng, K.L. Teo, Y. Zhao. Branch and bound method for sensor scheduling in discrete time. Journal of Industrial & Management Optimization, 2005, 1 (4) : 499-512. doi: 10.3934/jimo.2005.1.499
[20]

Xiao Lan Zhu, Zhi Guo Feng, Jian Wen Peng. Robust design of sensor fusion problem in discrete time. Journal of Industrial & Management Optimization, 2017, 13 (2) : 825-834. doi: 10.3934/jimo.2016048

 Impact Factor: 

Tools

Metrics

  • PDF downloads (40)
  • HTML views (0)
  • Cited by (4)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences