Re: [Roll] do we need a dominating set?

[Philip Levis <pal at cs.stanford.edu>]

On Nov 16, 2009, at 11:13 PM, Pascal Thubert (pthubert) wrote:

> Hi:
>
> The current RPL draft uses trickle to address density. Trickle has a  
> number of fine properties to throttle the control when things are  
> stable.
> Still, when an accident occurs, like a parent high in the DAG  
> degrades its rank, possibly most of the nodes in the whole network  
> will have to reassess their rank and reset their trickle timer.
> My understanding of that  process is that it can yield quite a bit  
> of activity, that grows with the number of nodes acting as routers.

Not really, if you have a small redundancy constant. Don't forget, the  
number of messages scales logarithmically with density.

> What I think is that even if we have trickle, we should be  
> considering some control on the density of nodes that act as a  
> router. To address that, there’s already ample work and large WSN  
> deployments that leverage the concept of dominating set.
>  A dominating set is a connected set of routers that enables  
> connectivity for all
> , that is all nodes in the network is connected to at least one  
> member of the dominating set.

I don't think a dominating set is what you mean: a dominating set can  
be disconnected. You're talking about a connected dominating set.

> Because we have trickle, such a set does not need to be  shrink to  
> minimal/optimal. In fact, we’d want that each node in the network  
> sees at least 2 members of the dominating set.
>
> Can that be achieved simply? Possibly.
>
> Each time a new sequence is spread, nodes are entitled to reassess  
> their need to be a router. When the sequence spreads, a form of  
> trickle could be used to decide Not TO advertise self as a router  
> and act as a host for the new sequence.
> Like if enough neighbor routers advertise the new sequence before T  
> elapse, then there might be no need for self to act as a router.

This is exactly what trickle is designed to do, with its redundancy  
counter.

I thought the major design goal right now to make RPL *less*  
complicated?

Phil