Ankur Kamthe
Skip Abstract Section
Abstract
Modeling the behavior of 802.15.4 links is a nontrivial problem, because 802.15.4 links experience different level of dynamics at short and long time scales. This makes the design of a suitable model that combines the different dynamics at different time scales a nontrivial problem. We propose a novel multilevel approach, the M&M model, involving hidden Markov models (HMMs) and mixtures of multivariate Bernoullis (MMBs) for modeling the long and short time-scale behavior of wireless links from 802.15.4 test beds. We characterize the synthetic traces generated from our model of the wireless link in terms of the mean and variance of the packet reception rates from the data traces, comparison of distributions of run lengths, and conditional packet delivery functions of successive packet receptions (1's) and losses (0's). Our results show that when compared to the closest-fit pattern matching model in TOSSIM, the proposed modeling approach is able to mimic the behavior of the data traces quite closely, with differences in packet reception rates of the empirical and simulated traces of less than 1.9%; on average and 6.6% in the worst case. Moreover, the simulated links from our proposed approach were able to account for long runs of 1's and 0's as observed in empirical data traces.
- Aguayo, D., Bicket, J., Biswas, S., Judd, G., and Morris, R. 2004. Link-level measurements from an 802.11b mesh network. SIGCOMM Comput. Commun. Rev. 34, 4, 121--132. Google Scholar
Digital Library
- Alizai, M. H., Landsiedel, O., Ágila Bitsch Link, J., Götz, S., and Wehrle, K. 2009. Bursty traffic over bursty links. In Proceedings of the 7th ACM Conference on Embedded Networked Sensor Systems (SenSys'09). Google ScholarDigital Library
- Baum, L. E., Petrie, T., Soules, G., and Weiss, N. 1970. A maximization technique occurring in the statistical analysis of probabilistic functions of markov chains. Ann. Math. Stat. 41, 1, 164--171.Google ScholarCross Ref
- Becher, A., Landsiedel, O., Kunz, G., and Wehrle, K. 2008. Towards short-term wireless link quality estimation. In Proceedings of the 5th ACM Workshop on Embedded Networked Sensors (HotEmNetS'08).Google Scholar
- Bilmes, J. 1997. A gentle tutorial of the EM algorithm and its application to parameter estimation for Gaussian mixture and hidden Markov models. Tech. rep. TR-97-021, International Computer Science Institute.Google Scholar
- Bishop, C. M. 2006. Pattern Recognition and Machine Learning. Springer-Verlag, Berlin. Google ScholarDigital Library
- Carreira-Perpiñán, M. Á. and Renals, S. 2000. Practical identifiability of finite mixtures of multivariate Bernoulli distributions. Neural Comput. 12, 1, 141--152. Google ScholarDigital Library
- Cerpa, A., Busek, N., and Estrin, D. 2003. SCALE: A tool for simple connectivity assessment in lossy environments. Tech. rep. 0021, University of California, Los Angeles.Google Scholar
- Cerpa, A., Wong, J., Kuang, L., Potkonjak, M., and Estrin, D. 2005a. Statistical model of lossy links in wireless sensor networks. In Proceedings of IEEE IPSN'05. 81--88. Google ScholarDigital Library
- Cerpa, A., Wong, J., Potkonjak, M., and Estrin, D. 2005. Temporal properties of low power wireless links: Modeling and implications on multi-hop routing. In Proceedings of ACM MobiHoc'05. 414--425. Google ScholarDigital Library
- Chen, Y. and Terzis, A. 2010. On the mechanisms and effects of calibrating RSSI measurements for 802.15.4 radios. In Wireless Sensor Networks. Lecture Notes in Computer Science, vol. 5970, 256--271. Google ScholarDigital Library
- Elliot, E. O. 1965. A model of the switched telephone network for data communications. Bell Syst. Tech. J. 4, 1, 89--109.Google ScholarCross Ref
- Forney JR., G. D. 1973. The viterbi algorithm. Proc. IEEE 61, 3, 268--278.Google ScholarCross Ref
- Gilbert, E. N. 1960. Capacity of a burst-noise channel. Bell Syst. Tech. J. 39, 1253--1266.Google ScholarCross Ref
- Girod, L., Elson, J., Cerpa, A., Stathopoulos, T., Ramanathan, N., and Estrin, D. 2004. Emstar: A software environment for developing and deploying wireless sensor networks. In Proceedings of the Annual USENIX Technical Conference (USENIX'04). 283--296. Google ScholarDigital Library
- Kamthe, A. 2009. M&M simulator for TOSSIM. http://www.andes.ucmerced.edu/software.Google Scholar
- Kamthe, A., Carreira-Perpiñán, M. Á, and Cerpa, A. 2011. Adaptation of a mixture of multivariate bernoulli distributions. In Proceedings of the 22nd International Joint Conference on Artificial Intelligence (IJCAI'11). Google ScholarDigital Library
- Kamthe, A., Carreira-Perpiñán, M. A., and Cerpa, A. E. 2009. M&M: Multi-level Markov model for wireless link simulations. In Proceedings of the 7th ACM Conference on Embedded Networked Sensor Systems (SenSys'09). ACM, New York, NY, 57--70. Google ScholarDigital Library
- Kashyap, A., Ganguly, S., and Das, S. R. 2008. Measurement-based approaches for accurate simulation of 802.11-based wireless networks. In Proceedings of the 11th International Symposium on Modeling, Analysis and Simulation of Wireless and Mobile Systems (MSWiM'08). ACM, New York, NY, 54--59. Google ScholarDigital Library
- Khayam, S. A. and Radha, H. 2003. Markov-based modeling of wireless local area networks. In Proceedings of the 6th International Symposium on Modeling Analysis and Simulation of Wireless and Mobile Systems (MSWiM'03). 100--107. Google ScholarDigital Library
- Konrad, A., Zhao, B., Joseph, A., and Ludwig, R. 2001. A Markov-based channel model algorithm for wireless networks. In Proceedings of the 4th International Symposium on Modeling Analysis and Simulation of Wireless and Mobile Systems (MSWiM'01). Google ScholarDigital Library
- Konrad, A., Zhao, B. Y., and Joseph, A. D. 2006. Determining model accuracy of network traces. J. Comput. Syst. Sci. 72, 7, 1156--1171. Google ScholarDigital Library
- Kotz, D., Newport, C., Gray, R. S., Liu, J., Yuan, Y., and Elliott, C. 2004. Experimental evaluation of wireless simulation assumptions. In Proceedings of the 7th International Symposium on Modeling Analysis and Simulation of Wireless and Mobile Systems (MSWiM'04). 78--82. Google ScholarDigital Library
- Kullback, S. and Leibler, R. A. 1951. On information and sufficiency. Ann. Math. Stat. 22, 1, 79--86.Google ScholarCross Ref
- Lee, H., Cerpa, A., and Levis, P. 2007. Improving wireless simulation through noise modeling. In Proceedings of ACM IPSN'07. 368--373. Google ScholarDigital Library
- Lenders, V. and Martonosi, M. 2009. Repeatable and realistic experimentation in mobile wireless networks. IEEE Trans. Mobile Comput. 8, 1718--1728. Google ScholarDigital Library
- Levis, P. and Lee, N. 2003. TOSSIM: A simulator for tinyOS networks - user manual. http://www.cs.berkeley.edu/ pal.pubs/nido.pdf.Google ScholarDigital Library
- Levis, P., Lee, N., Welsh, M., and Culler, D. 2003. TOSSIM: Accurate and scalable simulation of entire tinyOS applications. In Proceedings of SenSys'03. 126--137. Google ScholarDigital Library
- Lin, S., Zhang, J., Zhou, G., Gu, L., Stankovic, J. A., and He, T. 2006. ATPC: Adaptive transmission power control for wireless sensor networks. In Proceedings of SenSys'06. 223--236. Google ScholarDigital Library
- Metcalf, C. 2007. TOSSIM live: Towards a testbed in a thread Master's Thesis, Department of Mathematical and Computer Sciences, Colorado School of Mines, Golden, CO.Google Scholar
- Meyer, C. 2001. Matrix Analysis and Applied Linear Algebra. SIAM, Philadelphia, PA. Google ScholarDigital Library
- Nguyen, G. T., Katz, R. H., Noble, B., and Satyanarayanan, M. 1996. A trace-based approach for modeling wireless channel behavior. In Proceedings of the Winter Simulation Conference. 597--604. Google ScholarDigital Library
- Pawlikowski, K., Jeong, H.-D. J., and Lee, J.-S. R. 2002. On credibility of simulation studies of telecommunication networks. IEEE Commun. Mag. 40, 1, 132--139. Google ScholarDigital Library
- Raman, B., Chebrolu, K., Gokhale, D., and Sen, S. 2009. On the feasibility of the link abstraction in wireless mesh networks. ACM Trans. Netw. 17, 2, 528--541. Google ScholarDigital Library
- Rappaport, T. 2001. Wireless Communications: Principles and Practice. Prentice Hall, Upper Saddle River, NJ. Google ScholarDigital Library
- Reddy, D. and Riley, G. 2007. Measurement based physical layer modeling for wireless network simulations. In Proceedings of the International Symposium on Modeling, Analysis, and Simulation of Computer Systems. 46--53. Google ScholarDigital Library
- Reis, C., Mahajan, R., Rodrig, M., Wetherall, D., and Zahorjan, J. 2006. Measurement-based models of delivery and interference in static wireless networks. SIGCOMM Comput. Commun. Rev. 36, 4, 51--62. Google ScholarDigital Library
- Rubner, Y., Tomasi, C., and Guibas, L. J. 2000. The earth mover's distance as a metric for image retrieval. Int. J. Comput. Vision 40, 2, 99--121. Google ScholarDigital Library
- Rusak, T. and Levis, P. 2009. Burstiness and scaling in the structure of low-power wireless links. SIGMOBILE Mob. Comput. Commun. Rev. 13, 1, 60--64. Google ScholarDigital Library
- Rusak, T. and Levis, P. A. 2008. Investigating a physically-based signal power model for robust low power wireless link simulation. In Proceedings of the International Symposium on Modeling Analysis and Simulation of Wireless and Mobile Systems (MSWiM'08). 37--46. Google ScholarDigital Library
- Salamatian, K. and Vaton, S. 2001. Hidden Markov modeling for network communication channels. SIGMETRICS Perform. Eval. Rev. 29, 1, 92--101. Google ScholarDigital Library
- Srinivasan, K., Dutta, P., Tavakoli, A., and Levis, P. 2006. Some implications of low power wireless to IP networking. In Proceedings of the ACM HotNets Conference. 31--37.Google Scholar
- Srinivasan, K., Dutta, P., Tavakoli, A., and Levis, P. 2010. An empirical study of low-power wireless. ACM Trans. Sen. Netw. 6. Google ScholarDigital Library
- Srinivasan, K., Kazandjieva, M. A., Agarwal, S., and Levis, P. 2008. The β-factor: Measuring wireless link burstiness. In Proceedings of SenSys'08. 29--42. Google ScholarDigital Library
- Towsley, D., Yajnik, M., Moon, S. B., and Kurose, J. 1999. Measurement and modeling of the temporal dependence in packet loss. In Proceedings of IEEE INFOCOM'99.Google Scholar
- Werner-Allen, G., Swieskowski, P., and Welsh, M. 2005. Motelab: A wireless sensor network testbed. In Proceedings of IPSN'05. 68. Google ScholarDigital Library
- Zhao, J. and Govindan, R. 2003. Understanding packet delivery performance in dense wireless sensor networks. In Proceedings of SenSys'03. 1--13. Google ScholarDigital Library
- Zuniga, M. and Krishnamachari, B. 2004. Analyzing the transitional region in low power wireless links. In Proceedings of SECON'04. 517--526.Google Scholar
Index Terms
- Improving wireless link simulation using multilevel markov models
Recommendations
M&M: multi-level Markov model for wireless link simulations
SenSys '09: Proceedings of the 7th ACM Conference on Embedded Networked Sensor Systems802.15.4 links experience different level of dynamics at short and long time scales. This makes the design of a suitable model that combines the different dynamics at different timescales a non-trivial problem. In this paper, we propose a novel ...
Wireless link simulations using multi-level Markov models
SenSys '09: Proceedings of the 7th ACM Conference on Embedded Networked Sensor SystemsModeling the behavior of 802.15.4 links is a non-trivial problem because of the widespread heterogeneity in the quality of any given link over short and long time scales. We propose a novel multilevel approach involving Hidden Markov Models (HMMs) and ...
Coding with partially hidden Markov models
DCC '95: Proceedings of the Conference on Data CompressionPartially hidden Markov models (PHMM) are introduced. They are a variation of the hidden Markov models (HMM) combining the power of explicit conditioning on past observations and the power of using hidden states. (P)HMM may be combined with arithmetic ...
Comments