[SensorNetArch] MIA Monday + Synopsis Diffusion

[Jerry Zhao]

I think what makes synopsis diffusion interesting is that it does not
assume any "strict" structure. To approximately compute an aggregation
function, it only requires very loose structure ("rings" in there
paper). Given the computation is insensitive to duplicates, the partial
results can take arbitrary routes to the base station. However, how to
trade off accuracy (both in the aggregated result and in the epoch
interval), energy expense (partially depending on message size) and
latency (depending on path selection/how well the aggregation is
synchronized) is quite interesting.

I also agree with Phil that the "large scale" aggregation is very useful
in sensor network management and self-monitoring. Also it is useful to
computing baseline of ambient activity for sensing and event detection.
In our SNPA03 workshop paper, we argue that we can compute long-term
network status "digest" for monitoring sensor network. Despite our
efforts in exploring some approximate counting and random sampling
techniques, we found, at that time, such approaches introduce quite high
error in worst case with moderate (to the smaller scale side) network
size. Thus we chose a hybrid approach that computes inherent
duplicate-insensitive digests by "digest diffusion" and others by a
tree-base aggregation. It will be interesting to see if the new approach
in this sensys paper and the icde paper can really do the magic.  

On Mon, 2004-11-08 at 10:49, Cheng Tien Ee wrote:
> All right. Btw, Scott and Ion will be away at HotNets next week.
> 
> I was thinking more about synopsis diffusion. I think an important part 
> is the ability to extract information from a packet that is the 
> compressed form of multiple downstream packets. I believe that to 
> achieve better compression (i.e. not send more packets than the tree 
> scheme) the authors sacrificed some amount of accuracy, in which case it 
> still did better than the usual tree aggregation scheme. However, for 
> applications that cannot tolerate information loss, or generate data 
> with little correlation, less compression can be performed and it is not 
> clear whether the resultant increase in # packets transmitted is acceptable.
> 
> Another point is that the authors assumed that the network is dense 
> enough so that each mote has possibly multiple parent motes. It is 
> possible that the network be sparse enough, so that we end up with the 
> tree scheme anyway. In this case having retransmissions should increase 
> the accuracy of counts.
> 
> The other point was brought up by Matt during the conference: there is 
> an overhead of epoch maintenance and aging, so that data that isn't 
> fresh anymore and that arrived at a later time can be ignored. I'm 
> wondering if this sort of overhead is required regardless of the type of 
> traffic (e.g. not periodic counting of motes). I guess there's probably 
> some way of getting around it though.
> 
> 
> Ee
>