BSF 2006 - Grant Proposal
Title
- Current Title: Randomize Algorithms for Dynamic Sensor Networks
- Random Walk with Choice in General Metric Space
- Power of 2 Choice in (Randomize) Networks Algorithms
Possible Topics
- 16/10 Discussion: Concentrate on the Power of Choice:
- The hitting time on the line for RWC is O(n1.5), for the lollipop O(n1.5log(n)). Theoretical proofs.
- Simulation results for planar subgraphs of RGG: RNG, GG, random delaunay triangulation.
- Prove that the complete graph gives the least possible improvement.
- The affect of choice on mixing time and particular gossip algorithms for sensor networks.
- Theoretical results for the most visited node in RWC in some graphs.
- Previous Topics:
- Improve random walk techniques for sensor networks. This includes the power of choice and reducing the resistance between nodes of interest.
- random walks on subgraph of random geometric graphs, like the delaunay triangulation and other planar subgraphs.
- trade-off between random walks and gossip in terms of energy and time. Combine both techniques and/or classify when to use each.
- Dynamic network (over time): many topics to cover. representation, mobility, links error, failure. What is a simple model that we can start with. There is a lot of space for theoretical work as well as simulation and I think the modeling itself is not a simple issue. Tzika has done some work in the area and there seems to be more work than I was aware of. Never the less I think there is much to do here. What are the question we want to ask on these models (after we'll have them)? connectivity, clustering, random walks, routing...
- determine the regions of dynamics for which it is better to use optimize deterministic algorithms and for which it is better to use randomize algorithms.
Questions / Discussion
- What should be the main outcome? theoretical results, or we will also want to have practical side (which will require equipment and simulation.
- What is the focus of the work? We need to be very clear on want we want to achieve in the proposal.
- For a startup request (2 years, $60K) what is the expected outcome, 3-4 papers of the investigators? we need to contact the group here at BGU that deals with the proposals to find that out.
To do List
- Bhaskar and Tzika, sign up at the BSF site so I can add you to see the proposal on-line.
- Divide the workload
- set a time line for the work (taking into account the paper work that is required at each university, signatures , etc)
References / Reading
Links