[sim-wg] CPM in TOSSIM

[Philip Levis]

I've completed the CPM implementation in TOSSIM. There is currently  
no documentation on how to use it. I plan to add some later in the  
week. I also need to add a few tweaks, in order to incorporate  
greater variability (more on that later).

You can get all of the technical details in the paper on http:// 
sing.stanford.edu  (Improving Wireless Simulation Through Noise  
Modeling): what's below is just the basic idea.

The motivation of the approach is that low-power wireless is often in  
shared spectrum, and so must deal with RF energy not of its own  
creation (e.g., microwave ovens, 802.11, etc.). For example, if you  
send 802.15.4 packets during a burst of 802.11 traffic, you'll see a  
burst of packet losses as 802.11 is so much stronger.

So you simulate this noise (I call it noise rather than interference  
because you cannot control it). The algorithm that works best is  
called Closest Pattern Matching (CPM). To use CPM, you collect a high- 
frequency noise trace from a real network (we have a TinyOS program  
to do this in tinyos-2.x-contrib). CPM generates a statistical model  
of this trace.

The statistical model is a conditional probability distribution.  
Given the noise readings (n_{t-k}, n_{t-k+1}... n_{t-1}), CPM  
calculates the probability distribution of n_{t}. The value k is a  
parameter that controls how long the history CPM considers is. We  
found that a k of 20 works well for the trace we collected. A k of 0  
would make each noise value independent, while a k that is the length  
of the trace would just replay it exactly.

To simulate noise, CPM simply starts with the first k readings from  
the trace then starts using its model. If it cannot find a record  
that matches the past k values, it defaults to the most common record.

I'll leave it to the paper to explain the benefits CPM has over other  
approaches.

One problem you run into is that you're dealing with a very sparse  
state space. For example, with a k of 20 and 60 possible noise values  
(say, -100 dBm to -40 dBm), you are talking about 60^20 possible  
traces. The chances you'll find a match are very low. So CPM  
quantizes the readings into a smaller number of bins. The default  
implementation uses a quantization interval of 5dBm.

This is where the improvement I'll be adding comes in. Currently, it  
only generates integer multiples M of the quantization interval Q  
(-45dBm, -60dBm, -85dBm, etc.). I'm going to change it so it  
generates values in the range of MQ-Q/2, MQ+Q/2.

Vekatesh, did you see the email on tinyos-help about work on the  
CC1000? Someone was asking who was working on it and what the  
progress was. It might be good to answer.

Phil