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

  1. 16/10 Discussion: Concentrate on the Power of Choice:
    1. The hitting time on the line for RWC is O(n1.5), for the lollipop O(n1.5log(n)). Theoretical proofs.
    2. Simulation results for planar subgraphs of RGG: RNG, GG, random delaunay triangulation.
    3. Prove that the complete graph gives the least possible improvement.
    4. The affect of choice on mixing time and particular gossip algorithms for sensor networks.
    5. Theoretical results for the most visited node in RWC in some graphs.
  2. Previous Topics:
    1. Improve random walk techniques for sensor networks. This includes the power of choice and reducing the resistance between nodes of interest.
      1. random walks on subgraph of random geometric graphs, like the delaunay triangulation and other planar subgraphs.
    2. trade-off between random walks and gossip in terms of energy and time. Combine both techniques and/or classify when to use each.
    3. 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...
      1. 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

  1. What should be the main outcome? theoretical results, or we will also want to have practical side (which will require equipment and simulation.
  2. What is the focus of the work? We need to be very clear on want we want to achieve in the proposal.
  3. 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

  1. Bhaskar and Tzika, sign up at the BSF site so I can add you to see the proposal on-line.
  2. Divide the workload
  3. set a time line for the work (taking into account the paper work that is required at each university, signatures , etc)

References / Reading

Links