Problems that Kensho is trying to address:
- Programming effort does not scale with the size of the network
- Message based programming is difficult with a large number of nodes
- Distributing computation becomes more difficult
- Programming effort does not scale with the lifetime of the network
- Nodes must be replaced and possibly reprogrammed
- New nodes may be introduced with different capabilities
- Manually programming the nodes (function placement and message passing) may lead to an inefficient use of resources
- Manual node choice may not be optimal (too many messages passed for example)
- New nodes may have longer battery life or more efficient hardware
- Topology may change and make a static route inefficient
- Manually programming nodes may lead to a fragile environment
- Nodes may die and the computation/data may be lost
- Nodes may report poor/incorrect values
Application Characteristics that Kensho assumes:
- Applications exhibit regular patterns
- A basestation may send data/commands to some subset of nodes
- Data collected from nodes are often aggregated at a sink (cluster head)
- A sensor network may have multiple users and applications
- Environmental monitoring that runs alongside a fire detection app
- An employee tracking system that also detects large radiation doses
- A sensor network will run for a long time
- Specific computation may change over time
Issues: How do deal with routing on non-contiguous groups? The user can specify a group (possibly hierarchical) that consists of members that are separated with many intermediate nodes between them. These intermediate nodes ideally would have minimal knowledge concerning the groups that may connect. Otherwise, we may see poor scaling behavior as we increase the number of groups.
One solution is to simply limit the geographic size of groups. That way the number of intermediate nodes would be minimized. However, obviously nodes very far away that belong in that group may not be reachable.
We could also do the following: First, create a routing tree starting at the group leader. Now each group can communicate with all its members. However, many branches of this tree will be useless since they may not go towards any group member. Over time, we can try pruning this tree using a gradient type method (at each timestep, we increase the gradient value for the node that consistently delivers messages from within the group).
We can also try a more proactive solution. Since a node may learn it is a member of a particular group nearly at the same time as the leader node learns that it is the leader, both nodes can try constructing a routing tree towards each other (this essentially amounts to flooding). Hopefully the intermediate nodes will receive multiple routing tree messages from members of a single group. This could be used as indication that it is an intermediate node and force its gradient number of increase.
Should read Directed Diffusion papers again to see if they have solved this problem.
Papers:
- Application Experiments + overhead experiments + simple cluster experiments + simple routing experiment Overview Paper
- Comparative Analysis (EnviroSuite and Query) + Survey of other systems Comparative Analysis
