Wireless Link Modeling

The common denominator in all wireless sensor networks (WSNs), regardless of their underlying application, is the use of the radio to communicate information extracted from the sensed environment and, more importantly, to coordinate with other nodes. Consequently, radio communication and intelligent usage of the radio is a critical component of wireless distributed system in general and WSNs in particular. Due to the low power nature of WSNs, the radio used for communication is especially susceptible to changes in the quality of the wireless medium resulting in packet losses which can be attributed to limited transmission power levels as well as multipath effects resulting from lack of frequency diversity. Studies have confirmed that low power wireless communication is unpredictable, is sensitive to changes in the environment and is known to significantly change over different time scales.

Recent studies have indicated the presence of a wide chasm between the real world radio channel behavior and existing radio channel models in wireless simulators. This leads to significant differences in performance of a system in simulation as compared to a real world deployment. Thus, improving wireless simulators by incorporating accurate and robust radio channel models will reduce the gap between simulation and real-world performance. To reach this goal, we believe it is required to collect data traces of packet reception information over long periods of time at fine granularity. This data would be the seed for creating radio channel models that would help simulate more realistic packet losses, thus helping application designers increase the robustness of their applications by accounting in simulation for losses in the wireless medium.

Long and Short Term Link Dynamics

Long and Short Term Link Dynamics

The fundamental motivation for our modeling approach is that observed traces display structure at different temporal scales. In Figure, for example, one can see that over a period of minutes the link seems to switch between two states: one with PRR=0.6 (approx.) and the other with PRR=0.8 (approx.). We call this the long-term dynamics wherein the PRR stays roughly constant for a period of a few seconds. Within these regimes of near-constant PRR, it is more likely to observe a bursty sequence 0000111111 than a wildly oscillating sequence 1010101101. We call this the short-term dynamics; In order to simulate realistically the behavior of links, we want a model that is flexible enough to replicate this multiscale structure, and we want to estimate its parameters (which determine its typical PRRs or its local burstiness) from observed traces.

We propose a novel multilevel approach involving Hidden Markov Models (HMMs) and Mixtures of Multivariate Bernoullis (MMBs) for modeling the long and short time scale behavior of links in wireless sensor networks, that is, the binary sequence or trace of packet receptions (1s) and losses (0s) in the link. We call our model, the Multi-level Markov model or simply, the M&M Model. In our approach, a HMM models the long-term evolution of the trace (level 1) as transitions among a set of unobserved, level-1 states. These states typically correspond to a roughly constant packet reception rate (as determined by the data) and might correspond to different regimes of the link. Within each level-1 state, the short-term evolution of the trace (level 2) is modeled by either another HMM or by a MMB. This captures the faster, but not random, variations of the sequence of packet receptions and losses. For more details regarding the model, link to pre-prints of our paper are available.


Ankur Kamthe, Miguel A. Carreira-Perpinan, Alberto E. Cerpa, "Quick construction of data-driven models of the short-term behavior of wireless links," Proceedings of Thirty Second Annual IEEE International Conference on Computer Communications (INFOCOM 2013) Mini-Conference, pp. 5 pages, IEEE, Turin, Province of Turin, Italy, April, 2013.
Ankur Kamthe, Miguel A. Carreira-Perpinan, Alberto E. Cerpa, "Improving Wireless Link Simulation Using Multi-level Markov Models," ACM Transactions on Sensor Networks (TOSN), pp. 28 pages, 2012.
Ankur Kamthe, Miguel A. Carreira-Perpinan, Alberto E. Cerpa, "Adaptation of a mixture of multivariate bernoulli distributions," Proceedings of the Twenty Second International Joint Conference on Artificial Intelligence (IJCAI 2011), pp. 1336--1341, Barcelona, Catalonia, Spain, 2011.
Ankur U. Kamthe, Miguel A. Carreira-Perpinan, Alberto E. Cerpa, "Wireless Link Simulations using Multi-level Markov Models," Proceedings of the Seventh ACM Conference on Embedded Network Sensor Systems (SenSys 2009), pp. 391--392, ACM, Berkeley, CA, USA, November, 2009.
Ankur U. Kamthe, Miguel A. Carreira-Perpinan, Alberto E. Cerpa, "M & M: Multi-level Markov Model for Wireless Link Simulations," Proceedings of the Seventh ACM Conference on Embedded Network Sensor Systems (SenSys 2009), pp. 57--70, ACM, Berkeley, CA, USA, November, 2009.
HyungJune Lee, Alberto Cerpa, Philip Levis, "Improving Wireless Simulation Through Noise Modeling," Proceedings of the Sixth ACM/IEEE International Conference on Information Processing on Sensor Networks (IPSN 2007), pp. 368--373, ACM/IEEE, Cambridge, MA, USA, April, 2007.
Alberto Cerpa, Jennifer Wong, Miodrag Potkonjak, Deborah Estrin, "Temporal Properties of Low Power Wireless Links: Modeling and Implications on Multi-Hop Routing," Proceedings of the Sixth ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc 2005), pp. 414--425, ACM, Urbana-Champaign, Illinois, USA, August, 2005.
Alberto Cerpa, Jennifer Wong, Louane Kuang, Miodrag Potkonjak, Deborah Estrin, "Statistical Model of Lossy Links in Wireless Sensor Networks," Proceedings of the Fourth ACM/IEEE International Conference on Information Processing in Sensor Networks (IPSN 2005), pp. 81--88, ACM/IEEE, Los Angeles, CA, USA, July, 2005.
Alberto Cerpa, Naim Busek, Deborah Estrin, "SCALE: A Tool for Simple Connectivity Assessment in Lossy Environments," CENS Technical Report 0021, pp. 1--13, Center of Embedded Networked Systems (CENS), University of California, Los Angeles, September, 2003.