Dane Seaberg
MS Thesis Defense
Wednesday, April 10, 9:00am
112 Schorr Center
"FastLane: Flow-Based Channel Assignment in Dense Wireless Networks"
Wireless communication in dense networks is becoming more apparent and presents challenges in achieving reliable and near real-time communication. While some works have begun to address dense wireless networks, few address both reliability and latency. In this paper we introduce FastLane, a method of flow-based channel assignment for dense wireless networks, which works to achieve reliable, near real-time communication in a dense environment. FastLane uses an assignment mechanism that assigns channels at a flow-level granularity, rather than a tree-level or link-level granularity. Our scheme also takes into account channel quality and can adapt as the quality changes over time. We have created an extensive event-driven simulator to measure the performance of our design in terms of packet delivery rate and end-to-end latency, and also implemented our work on the MicaZ platform and evaluate in a real test bed. In the simulation and evaluation we compare FastLane to two state-of-the -art tree-level and link-level designs: RACNet and MMSN, respectively. Our results show considerable improvements of latency in even high densities while still achieving a comparable delivery rate.
Derrick Lam
MS Thesis Defense
Thursday, April 11, 11 a.m.
347 Avery Hall
"Improving Virtual Collaboration: Modeling for Recommendation Systems in a Classroom Wiki Environment"
Collaboration is of increased importance in today’s society, with increased emphasis placed on working jointly with others, whether it is in the classroom, in the lab, in the workplace, or virtually across the world. The wiki is one particular virtual collaboration tool that is gaining particular prominence in recent years, enabling people – either in small project groups or as part of the wiki’s entire user base – to socially construct knowledge asynchronously on a wide variety of topics. However, there are few intelligent support tools for wikis available, particularly those providing recommendation-based support to users.
This thesis investigates the topic of user and data modeling for recommendation systems in a wiki environment. In addition to conventional usage data, the proposed model uses new metrics designed for the wiki domain, including active-passive activity level rating and minimalist-overachiever score. The active-passive activity level rating provides a quick overview of a participant’s collaborative activity composition and can be leveraged to alert moderators when participants aren’t meeting expectations. The minimalist-overachiever score strongly correlates to evaluations that participants have received and can be used as an aid in determining performance in future collaborations. These, along with other findings, serve as the foundation for improved virtual collaboration.
Shant Karakashian
PhD Thesis Defense
Thursday, April 11, 3:30 p.m.
108 Avery Hall
"Practical Tractability of CSPs by Higher Level Consistency and Tree Decomposition"
Constraint Satisfaction is a flexible paradigm for modeling many decision problems in Engineering, Computer Science, and Management. Constraint Satisfaction Problems (CSPs) are in general NP-complete and are usually solved with search. Research has identified various islands of tractability, which enable solving certain CSPs with backtrack-free search. For example, one sufficient condition for tractability relates the consistency level of a CSP to treewidth of the CSP’s constraint network. However, enforcing higher levels of consistency on a CSP may require the addition of constraints, thus altering the topology of the constraint network and increasing its treewidth. This thesis addresses the following question: How close can we approach in practice the tractability guaranteed by the relationship between the level of consistency in a CSP and the treewidth of its constraint network?
To achieve “practical tractability,” this thesis proposes: (1) New local consistency properties and algorithms for enforcing them without adding constraints or altering the network's topology; (2) Methods to enforce these consistency properties on the clusters of a tree decomposition of the CSP; and (3) Schemes to bolster the propagation between the clusters of the tree decomposition.
Our empirical evaluation shows that our techniques approach us to practical tractability, and that they are both applicable and useful. We theoretically characterize the proposed consistency properties and empirically evaluate our techniques on benchmark problems. Our techniques for higher level consistency exhibit their best performances on difficult benchmark problems. They solve a larger number of difficult problem instances than algorithms enforcing weaker consistency properties, and moreover they solve them in an almost backtrack-free manner.