On the Structure of Low-Power Wireless Links

Tal Rusak Philip Levis

Cornell University Stanford University

`tr76@cornell.edu` `pal@cs.stanford.edu`

1 Problem and Motivation

Low-power wireless networks are becoming increasingly pervasive in a society that expects information anytime, anywhere. Various studies have attempted to model, explain, and build protocols optimized for the physical- or link-layers of the wireless channel. These efforts focus on modeling low-level details of physical- and link-layers, such as interference and scheduling [10] or adaptive power control [9]. Analytical models of some wireless networks, such as the cellular phone network, make simplifying assumptions such as time independence of packet reception, as in the log-normal shadowing model [7]. While many studies are complementary [8,9,12,13], some are also contradictory, coming to different conclusions even while examining the same data traces [2,6]. The purpose of this paper is not to support or reject any individual conclusion of the aforementioned work, but to suggest a fundamentally different way of understanding and modeling the wireless channel. We believe that a simple, parsimonious model may be possible for wireless links.

The main observation of this paper is that the signal power and packet reception time series of many wireless links is consistent with statistical self-similarity. We consider the generality of this property and possible modeling techniques that take into account the observed temporal variations.

2 Background and Related Work

2.1 Burstiness in Wireless Networks

Previous studies have observed burstiness in wireless links following the IEEE 802.11 and 802.15.4 standards [2,13]. In focusing on one time scale, or by attempting to discover a characteristic time scale for bursts of packet reception, such work does not capture the full extent of burstiness in many low-power wireless links. We show that in many such links, there is no single time scale for bursts of packet receptions or losses. Previous work [12,13] has shown that bursts occur at shorter time scales. We observe bursts at longer time scales as well, characterized by a coherent scaling property that we discuss in this work.

Figure 1: Burstiness in a low-power wireless link--each diagram is a zoomed-in version of the boxed, highlighted section of the preceding packet reception trace. The overall packet reception rate of both the experiment and the simulated trace is about 84%. (a) (Left) Real IEEE 802.15.4 link; (b) (Right) Simulated link using TOSSIM 2.0.2.

2.2 Methodology and Datasets

In order to characterize the physical-layer of low-power wireless networks, we begin with experimental data about the behavior of these links. The experiments are conducted with TelosB [11] or MICAz motes running TinyOS 2.0.2. Packet delivery experiments are conducted at a rate of 100 Hz. From each experiment with n successfully received and decoded packets, we derive a time series R = r₁, r₂, ..., r_n, where r_i is the RSSI value (in dBm) for the i-th received packet. We use R as a representation of the physical-layer of the network. For each experiment with k transmitted packets, we derive a time series P = p₁, p₂, ..., p_k where p_j is 1 if the j-th packet transmitted is received and correctly decoded and 0 otherwise. We use P to characterize the link-layer of the network.

Such datasets were collected over periods of six hours to two weeks in Gates Hall at Stanford University, at an apartment, and at the Mirage testbed [4]. All of these testbeds follow the IEEE 802.15.4 wireless standard.

2.3 Scaling and Self-Similarity in Time Series

The presence of self-similarity or other coherent structure over many time scales is called scaling, and can be detected using the wavelet transform and a tool called the logscale diagram [1]. The logscale diagram plots octaves (base-2 scales, i.e., octave 1 is 2¹ packets, octave 2 is 2² packets, etc.) on the horizontal axis and y_j on the vertical axis. y_j can be understood as the logarithm of an estimator for the variance of the discrete wavelet transform process d_X(j,·) defined by Abry et al. [1].

The slope of a linear portion of the logscale diagram, alpha, can be used to check for various types of scaling. If alpha > 1, where the linear regime includes the largest octaves available, then the underlying time series can be considered as consistent with the self-similarity hypothesis, but not with long range dependence. The octave at which the linear regime starts is known as the onset point of scaling.

3 Uniqueness of Approach

The observation of scaling comes from considering Figure 1. Figure 1(a) plots the reception characteristics of a real network link over non-overlapping time windows of varying sizes, and the variations are heuristically "similar" over different time scales, suggesting self-similarity and scaling. Figure 1(b) plots the equivalent link characteristic for the state-of-the-art TOSSIM simulator for low-power wireless sensor networks. This figure is simply a way of representing P for the Gates Hall experiment. Current simulation models, which assume signal power to be constant, do not capture burstiness and scaling correctly.

Figure 2: Logscale diagram for P for actual experimental data for the Gates Hall link. The solid blue line shows the actual value of y_j, while the dotted red line is a linear fit over a region including the highest scales.

Figure 3: Logscale diagram for R for experimental data for the Gates Hall link. Same conventions as in Figure 2.

To quantify and make more rigorous the notion of scaling in the trace studied above, we plot its logscale diagram for P (the link-layer reception trace) in Figure 2. As expected for a time-series consistent with self-similarity, there is a long linear regime in the asymptotic domain of this plot, i.e., including the largest octaves. Here, we find alpha = 1.21 > 1, which is consistent with the self-similarity hypothesis.

A natural question to ask is why the link-layer trace P is consistent with self-similarity. We can provide insight by considering the scaling behavior of the physical-layer trace R, which approximates signal power. It might be expected that scaling and self-similarity at the link-layer suggests the same behavior of the underlying physical-layer of the channel. The logscale diagram in Figure 3 shows that the physical-layer is also consistent with self-similarity, since alpha = 1.38 > 1, computed including the largest time scales available in the data.

Figure 4: Estimation of the point of the onset of scaling in the logscale diagram in Figure 2. The solid line shows regions of non-decreasing goodness-of-fit metric Q and the dotted line shows the Q values following the non-decreasing regime. The estimate of the onset scale is given by the diamond in the figure.

We noted above that in each of the logscale diagrams, scaling starts at some onset point. The onset point is estimated using an algorithm of Veitch et al. [14]. Figure 4 shows how the onset point is estimated for the logscale diagram in Figure 2; the onset octave shows a large increase in Q, a goodness-of-fit metric defined by Veitch et al. [14]. Experimental work [13] has shown that waiting 500 ms before retransmitting lost packets greatly increases link reliability in terms of the packet reception rate. The onset scale observed in this experiment, j₁ = 6, corresponds to 10 ms × 2⁶ = 640 ms, a relatively close value to the heuristic observation [13]. The onset point may correspond to the octave at which random variations stop impacting the wireless link and the self-similar scaling starts to dominate the variations of the link. Protocols that understand this parameter could use it to decide on optimal times to transmit packets so that the likelihood of packet loss is lessened.

4 Results and Contributions

4.1 Generality of the Scaling Phenomenon

Figure 5: This plot considers groups of 10 Mirage links each, sorted by order of increasing variance, and plots the probability that in each group aL > 1 versus the base-10 logarithm of the average variance. This plot shows that beyond a certain critical point, virtually all links in these experiments are consistent with self-similarity.

Although many links are consistent with self-similarity, we observe that not all links exhibit this property. Figure 5 plots the probability, over groups of ten links, that aL, the lower 95% confidence bound for alpha, is greater than 1 versus the logarithm of the variance in the physical-layer traces R of these links. We observe a phase transition in the consistency of these links with self-similarity. Stable, low-variance links are never self-similar, while high-variance links are almost always self-similar at the physical-layer. Any realistic model of such wireless networks has to take this transition into account.

4.2 Modeling Self-Similar Links

Figure 6: Logscale diagram for P for simulation with signal power modeled by F_H=0.192(t) (Infinitely Divisible Cascading random walk). Same conventions as in Figure 2.

State-of-the-art simulators of wireless networks assume signal power to be constant for a given link. To improve upon current techniques, we use two self-similar time series synthesis algorithms, fractional Brownian motion [5] and Infinitely Divisible Cascading random walks [3], to generate self-similar traces of signal power synthetically. In order to do this, we set only one parameter, H = (alpha-1)/2, in each of these models (computed from alpha of the logscale diagram of the physical-layer), and modify the range and minimum and maximum points to correspond to the experimental range and extrema. We confirmed that each trace is indeed self-similar using a logscale diagram.

Modeling signal power with fractional Brownian motion does not result in link-layer scaling. Figure 6, in contrast, shows that modeling signal power with an Infinitely Divisible Cascading random walk V_H=0.192(t) does lead to appropriate scaling at the link layer, since alpha = 1.28 > 1, using a fit including the largest time scales. Because it captures scaling at the link-layer, we have found that among the models that we have investigated, Infinitely Divisible Cascading random walks are the best model for synthesizing signal power traces for the Gates Hall wireless link.

We are interested in pursuing future work accounting for the variations of y_j at each time scale, instead of relying only on the statistical fit used to calculate alpha. It is especially important to understand whether the drop in y_j at the largest time scale is due to the limited data at this scale or some more fundamental variation in the model. This can be done by generating longer Infinitely Divisible Cascading random walks and simulating the corresponding link.

5 Conclusions

By considering the physical-layer structure of wireless links, we identified the self-similar nature at both the link- and physical-layers of such networks in many experiments. This concise explanation for the structure of IEEE 802.15.4 network links provides a possible reason for the difficulty in discovering common patterns in studies that have delved deeply into the details of particular networks. The simplicity of this explanation, as evidenced by the fact that we need to set only one parameter and the extrema in the model traces, is a strength of the observations of this paper. We believe that this general, parsimonious property that applied to many links in our experiments offers a new perspective from which to study wireless networks and to design effective, reliable protocols.

Acknowledgments

This work was supported by generous gifts from the Bartels Family, Microsoft Research, Cisco Research, Intel Research, DoCoMo Capital, Foundation Capital, the National Science Foundation under grants #0615308 ("CSR-EHS") and #0627126 ("NeTS-NOSS"), and a Stanford Terman Fellowship. An extended version of this work will appear in Mobile Computing and Communications Review. We appreciate insightful discussions with Jon Kleinberg and Lars Backstrom.

References

[1]     P. Abry, P. Flandrin, M. Taqqu, and D. Veitch. Wavelets for the analysis, estimation and synthesis of scaling data. Self-Similar Network Traffic and Performance Evaluation, pages 39-88, 2000.
[2]     D. Aguayo, J. Bicket, S. Biswas, G. Judd, and R. Morris. Link-level measurements from an 802.11b mesh network. In Proceedings of the 2004 conference on applications, technologies, architectures, and protocols for computer communications (SIGCOMM'04), pages 121-132, Aug. 2004.
[3]     P. Chainais, R. Riedi, and P. Abry. Scale invariant infinitely divisible cascades. In Proceedings of the international symposium on physics in signal and image processing, Jan. 2003.
[4]     B. Chun, P. Buonadonna, A. AuYoung, C. Ng, D. Parkes, J. Shneidman, A. Snoeren, and A. Vahdat. Mirage: a microeconomic resource allocation system for sensornet testbeds. In Proceedings of the 2nd IEEE workshop on embedded networked sensors (EmNets'05), pages 19-28, April 2005.
[5]     P. Flandrin. Wavelet analysis and synthesis of fractional Brownian motion. IEEE Transactions on Information Theory, 38(2):910-917, Mar. 1992.
[6]     D. Gokhale, S. Sen, K. Chebrolu, and B. Raman. On the feasibility of the link abstraction in (rural) mesh networks. In Proceedings of the 27th IEEE conference on computer communications (INFOCOM'08), pages 61-65, April 2008.
[7]     A. Goldsmith. Wireless Communications. Cambridge University Press, 2005.
[8]     J. Jeong, D. Culler, and J.-H. Oh. Empirical analysis of transmission power control algorithms for wireless sensor networks. In Proceedings of the 4th international conference on networked sensing systems (INSS'07), June 2007.
[9]     S. Lin, J. Zhang, G. Zhou, L. Gu, J. Stankovic, and T. He. ATPC: adaptive transmission power control for wireless sensor networks. In Proceedings of the 4th international conference on embedded networked sensor systems (SenSys'06), pages 223-236, Nov. 2006.
[10]     R. Maheshwari, S. Jain, and S. R. Das. A measurement study of interference modeling and scheduling in low-power wireless networks. In Proceedings of the 6th international conference on embedded network sensor systems (SenSys'08), pages 141-154, Nov. 2008.
[11]     J. Polastre, R. Szewczyk, and D. Culler. Telos: enabling ultra-low power wireless research. In Proceedings of the 4th international symposium on information processing in sensor networks (IPSN'05), pages 364-369, April 2005.
[12]     T. Rusak and P. Levis. Investigating a physically-based signal power model for robust low power wireless link simulation. In Proceedings of the 11th international conference on modeling, analysis, and simulation of wireless and mobile systems (MSWiM'08), pages 37-46, Oct. 2008.
[13]     K. Srinivasan, M. Kazandjieva, S. Agarwal, and P. Levis. The beta-factor: Measuring wireless link burstiness. In Proceedings of the 6th international conference on embedded networked sensor systems (SenSys'08), pages 29-42, Nov. 2008.
[14]     D. Veitch, P. Abry, and M. Taqqu. On the Automatic Selection of the Onset of Scaling. Fractals, 11(4):377-390, 2003.

Tal Rusak		Philip Levis
Cornell University		Stanford University
`tr76@cornell.edu`		`pal@cs.stanford.edu`