TY - GEN

T1 - Scalable modeling and performance evaluation of wireless sensor networks

AU - Kwon, Young Min

AU - Agha, Gul

PY - 2006

Y1 - 2006

N2 - A notable features of many proposed Wireless Sensor Networks (WSNs) deployments is their scale: hundreds to thousands of nodes linked together. In such systems, modeling the state of the entire system as a cross-product of the states of Individual nodes results in the well-known state explosion problem. Instead, we represent the system state by the probability distribution on the state of each node. In other words, the system state represents the probability that a randomly picked node is in a certain state. Although such statistical abstraction of the global state loses some information, it is nevertheless useful in determining many performance metrics of systems that exhibit Markov behavior. We have previously developed a method for specifying the performance metrics of such systems in a probabilistic temporal logic called iLTL and for evaluating the behavior through a novel method for model checking iLTL properties. In this paper, we describe a method for estimating the probabilities in a Discrete Time Markov Chain (DTMC) model of a large-scale system. We also provide a statistical test so that we can reject estimated DTMCs if the actual system does not have Markov behavior. We describe results of experiments applying our method to WSNs in an experimental test-bed, as well as using simulations. The results of our experiments suggest that our model estimation and model checking method provides a systematic, precise and easy way of evaluating performance metrics of some large-scale WSNs.

AB - A notable features of many proposed Wireless Sensor Networks (WSNs) deployments is their scale: hundreds to thousands of nodes linked together. In such systems, modeling the state of the entire system as a cross-product of the states of Individual nodes results in the well-known state explosion problem. Instead, we represent the system state by the probability distribution on the state of each node. In other words, the system state represents the probability that a randomly picked node is in a certain state. Although such statistical abstraction of the global state loses some information, it is nevertheless useful in determining many performance metrics of systems that exhibit Markov behavior. We have previously developed a method for specifying the performance metrics of such systems in a probabilistic temporal logic called iLTL and for evaluating the behavior through a novel method for model checking iLTL properties. In this paper, we describe a method for estimating the probabilities in a Discrete Time Markov Chain (DTMC) model of a large-scale system. We also provide a statistical test so that we can reject estimated DTMCs if the actual system does not have Markov behavior. We describe results of experiments applying our method to WSNs in an experimental test-bed, as well as using simulations. The results of our experiments suggest that our model estimation and model checking method provides a systematic, precise and easy way of evaluating performance metrics of some large-scale WSNs.

UR - http://www.scopus.com/inward/record.url?scp=33749625237&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=33749625237&partnerID=8YFLogxK

U2 - 10.1109/RTAS.2006.39

DO - 10.1109/RTAS.2006.39

M3 - Conference contribution

AN - SCOPUS:33749625237

SN - 0769525164

SN - 9780769525167

T3 - Proceedings of the IEEE Real-Time and Embedded Technology and Applications Symposium, RTAS

SP - 49

EP - 58

BT - Proceedings of the 12th IEEE Real-Time and Embedded Technology and Applications Symposium

T2 - 12th IEEE Real-Time and Embedded Technology and Applications Symposium

Y2 - 4 April 2006 through 7 April 2006

ER -