CSE 590 Course Project

The final report is due on Dec 21, 2007, 2pm. Hardcopy required. No email submissions. 

Ground Rules

• Two students per project. Three students team is acceptable; but more comprehensive work will be expected (naturally). Going solo is also acceptable; but not recommended. It usually means a lot of work for the individual to complete a reasonable project. 
• Your goal should be developing an idea to solve a problem, and evaluating your idea. Most common method of evaluation is via simulation. But sometimes analytical methods or experiments are appropriate. Evaluating existing techniques (e.g., comparative evaluation of existing techniques to solve a specific problem) can also make good projects. You should read of a lot of papers related to your project topic and attempt to discover better/more comprehensive solutions/approaches/studies than may exist in literature. 
•  The project report should resemble a conference paper. There is no specific page limit or format requirements. The best projects are likely to result in actual conference/workshop papers, possibly with some additional follow-up work later. This should be your goal.
• It is expected that each project will be presented in a 15 min presentation in class. We will come up with a presentation schedule later. If results are not available at the time of presentation, the presentation should focus on the background, concept, design, related published work, etc. Here, your goal will be to educate others about your work. If there are too many projects than we have time for, we will either pick only certain projects to be presented, or use a poster session.  
• The project grade will be based on the difficulty/depth of the problem you are trying to solve, your accomplishments/progress on solving the problem, and your report/presentation. This means that an easy problem will require a very comprehensive work, while less complete work will be acceptable for a challenging problem. If you are able to come up with a new and promising idea, even initial work will be appreciated. Basically, you are do not easily win by choosing an easy problem.  
• To make sure that you are actually working on the project at a steady pace, we will have checkpoints. The checkpoints are not mandatory, and are only meant to give you feedback. But if you receive poor feedback on checkpoints, you should take it seriously. Though checkpoints are not mandatory, experience has shown that those who do not submit checkpoints, receive poor grades in the final submission. Checkpoint reports also help you with the final report as you can reuse much of the text you have already written. Checkpoints should be emailed with subject header "Checkpoint n: CSE590," where n is 1 or 2.
  • Checkpoint 1: Due Nov 19. Submit a 0.5-1 page document describing describing the broad idea of your project with appropriate references.
  • Checkpoint 2: Due Dec 3. Submit a 2-2.5 page document describing a detailed set of goals and an initial design of your project. This should contain enough details to convince us that you have a good set of plans for a successful project, and you have a focus. For example, it should contain a high-level description of the techniques/algorithms, choice of evaluation mechanisms/platforms etc, probably some initial experiments/results.

Project ideas

We have ideas here that you can use as starting points. Note that the ideas as stated may be broad-based or vague or incomplete or too complex. It is your responsibility to pick an idea or part of an idea and make it somewhat concrete. It is acceptable to have more than one team working on the same broad idea. We are sure that you will all have different approaches. You are also encouraged to work on your own idea that is not in the list. We will update this section with more ideas over the next one week or so. For most ideas we have one or more references to get you started. But many of them may have more substantial literature.

Note that there is Wikipedia entry for list of ad hoc network routing protocols. This could come in handy.

• Hybrid and/or adaptive routing: Evaluate proactive versus reactive routing protocols via extensive simulations. Find a set of traffic and mobility parameters that you can vary in a continuum that demonstrate the performance differences. Can you design some sort of a hybrid protocol, by taking a proactive protocol and making it slightly reactive, or vice versa, where the proactive and reactive can vary automatically depending on traffic and mobility? [Example reference: Rajendra's Boppana's ADV protocol in Infocom 2001; Ramanathan did some analysis in Mobihoc 2001]
• Geographic routing and location service: Geographic routing is attractive as there is no real routing overhead. However, one needs a location service to learn the destination's location in a mobile network. How does geographic routing perform relative to a traditional routing protocol when the cost of such location service is factored in? Is geographic routing still a clear winner? How much of it might depend on the location service protocol? One way to think about it is that a source does not need to have a perfect location information of the destination. Approximate location information is fine initially so long as more accurate information is available as the packet makes progress. Thus, the location information for a node X can be progressively less accurate as one goes away from X. [Reference: look at the Dead Reckoning protocol from WINGS lab web page.] You can also evaluate other location service protocols. [Reference: Tracy Camp in Colorado School of Mines has some work on evaluating location service protocols.]
• Geographic multicast: How would you use geographic routing to perform multicast? How much is the performance advantage relative to traditional methods. [Some ideas are presented here.]
• Trajectory-based routing: There are techniques that can route a packet along a curve (specified by an equation, for example). How can you use this technique for multicast or for  network-wide flood? How efficient is it in comparison with more traditional methods? [Reference: Niculescu/Badri Nath's work in Rutgers. Also see  Space-Filling curves paper from WINGS lab web page]. 
• Routing metrics: It is well-known that number of hops is a not a good routing metric. It has been demonstrated that interference is a better metric. Interference influences how long it might take for a packet to be transmitted. It may also influence the bit rate of the channel. But the question is how to quantify interference. Also, interference can vary dynamically. Can you design a routing metric that takes interference into account? The challenge is to design practical schemes that evaluate the designed interference metric "passively" and "efficiently," and then use this metric in a routing protocol. [Reference: Robert Morris's group in MIT and Microsoft Research mesh networking group. Both appeared in past Mobicoms. Anand Kashyap in Wings lab is pursuing a similar project.]
• Trade latency and memory for throughput: It has been suggested that in a mobile ad hoc network, it is possible to design protocols that attain lower packet drops by simply buffering packets until a suitable opportunity arises to forward the packet. An extreme example is to buffer the packet until the destination comes within one hop from the source. This, of course, can increase latency and memory requirement to arbitrarily high. Can we design "more reasonable" protocols that exploit this idea? For example, do not drop a packet when a link is broken; buffer it; forward it when a path is available again. What do we have to do to attain a 100% packet delivery? Can we really do this? What can we say about latency or memory requirements? Can we design protocols that can do as good as possible given a limited memory available in a node. [Reference: some ideas were pursued in this MS thesis.]
• Disconnection tolerant sensor network: This problem is similar to the above problem. Think of a sensor network where nodes turn off and on periodically to conserve energy. How would you gather data effectively in such a network? Assume that duty cycles can be arbitrary or random and depend on considerations other than routing. Suppose, that network always has sufficient coverage. This means that each point in the area is always covered (sensed) by at least one sensor that is on.  The trick here would be to develop techniques to buffer data temporarily at source and/or intermediate nodes. Evaluate performance subject to limited node memory. What is the impact on latency of data gathering? Can you do better if you know how/when nodes turn off and on? [Reference: Kevin Fall's work on disconnection tolarent networking, though not specifically related to sensor networks.]
• Fairness in forwarding: Studies have shown that multihop forwarding is fraught with  fairness problems. For example, packets generated by a node (as a source) gets an unfair share of bandwidth relative to the packets that are forwarded by that node (as an intermediate relay). Investigate and characterize this problem. Suggest and evaluate solutions. [Reference: Ed Knightly's (Rice) work in Mobicom 2004. Also, this paper by Sichitiu of NC State. ]
• Bad fish problem: In traditional CSMA protocol (such as in 802.11) all nodes get an equal chance to access the radio medium. Thus, nodes with slower bit rate may get an unfair share of the bandwidth as they take a longer time to transmit a packet. Characterize this problem and suggest solutions. Solutions can range from fixing the 802.11 protocol itself (ideal) to deploying practical solutions. [Reference: This Infocom03 paper.] 
• Misbehavior in the MAC layer: Characterize the misbehaviors that are possible in the 802.11 MAC layer that can either give the misbehaving node unfair (as defined by the 802.11 protocol) share of the network bandwidth or can launch a denial of service attack in an extreme case. Suggest and evaluate approaches to detect such misbehaviors. [Reference: Nitin Vaidya's work in UIUC and Jean-Pierre Hubaux's work in EPFL (Domino protocol).]
• MAC layer (reliable) multicast: How would you do multicast in the MAC layer? Using simply broadcast may not be a good idea as typical broadcasts are not reliable, as there is no acknowledgement. This is important as broadcasts may suffer from the hidden terminal problem. What is the performance impact of the reliability mechanism? [Reference: Mario Gerla's work in UCLA. Shweta Jain's work on WINGS lab web page.]
• Multiple channels on a single interface:  In an 802.11-based network there are multiple orthogonal channels available. Using multiple channels judiciously can improve performance by improving spatial reuse. The trouble is that two directly communicating nodes must have their interfaces on the same channels. If channels are changed dynamically, we need to ensure some sort of synchronization such that two communicating nodes  return to the same channel while communicating. A received-directed scheme assigns a channel to each node (called quiescent channel). A sending node must turn to the receiver's quiescent channel to communicate. How does this scheme perform relative to a scheme that needs synchronization? How would one assign the quiescent channel? [Reference: Nitin Vaidya's (UIUC)'s MMAC protocol in Mobihoc 2004 and Microsoft Research's SSCH protocol in Mobicom 2004. Ritesh Maheswari's paper on WINGS web page.]
• Multiple channels on multiple interfaces: This is a different twist on the pervious idea. Suppose, there are multiple interfaces on each node of a 802.11-based mesh/ad hoc network. How would you assign channels to these interfaces to reduce interference? This is actually a topology control problem as different topologies can be created with different assignments. You can look at this problem from many angles. For example, interesting/efficient static heuristics given that the problem is NP complete, or a dynamic traffic dependent solution. [Reference: Raniwala/Chiueh's work in Infocom 2005. Anand Prabhu Subramanian's work in WINGS lab web page.] We are doing some experimental evaluation for such systems on a testbed. It may be possible that you can do something here.
• Power control/Carrier sense threshold/Rate control in CSMA protocol: One or more of these three parameters can be controlled (statically/dynamically) to optimize performance. You can use the 802.11 protocol and study the impact of controlling one or more of these on performance, and may be devise strategies or protocols to control these. [Reference: Nitin Vaidya and his students' work (UIUC).  Also look at Jennifer Hou (UIUC) and her students' work].

The following are primarily experimental/systems projects.

• SINR modeling on sensor motes: Experimentally develop a model for bit/packer error rate vs. SINR on the motes platform. You need to learn how to work with motes and TinyOS. [References: Similar work has been done by Bhaskar Krishnamachari (USC) in SECON05 and Sensys06, but using a different hardware than what we have. Ritesh Maheshwari in WINGS lab will help].
• WiFi Traffic Analysis: Collect WiFi traffic via snooping in a busy environment. Analyze the data. Comment on performance. Are there performance issues? Any interesting observations? Multiple concurrent snoopers will make the work more interesting. [Reference: Elizabeth Belding-Royer's work (UC-Santa Barbara) in IMC 05 and IMC07. David Kotz's (Dartmouth) work in MobiCom02 and Mobicom04. His group also has some recent work on WiFi measurements. Also, Ratul Mahajan's (Microsoft Research) work in Sigcomm06].
• Using TDMA with 802.11 PHY layer:  We have interest in running TDMA with 802.11 radios available off-the-shelf. There are two problems that need to be solved to do this. First, somehow 802.11 MAC has to be turned off. This means no carrier sense or backoffs. Second, the nodes need to be time synchronized.  You can target one of both of these issues. [References: Multimac and Softmac work in Colorado. You will also need help from students in WINGS lab as we have some specific ideas here.]