We are a research group in the Department of Computer and Information Sciences and Engineering at the University of Florida, directly supervised by Dr. My T. Thai. Our research interests are centered on the Applied Optimization and its applications in Networks and Computational Biology. More specifically, our focus is to design and analyze efficient algorithms for many optimization problems, arising in two main application domains: Wireless Networks and Computational Biology. Besides seeking for a practical solution, we are also concerned about their theoretical merits.
Within the wireless networks domain, we are tackling several problems in order to optimize the use of wireless networks. Our long term goal is to provide the mathematical models, algorithmic tools, and robust protocols for an integrated system as a whole. The motivation and benefits of these studies are enormous. It is well-known that wireless networks are recognized as a new frontier in communications and as one of the ten emerging technologies that will change the world. They are being used in a variety of military and civil applications, providing great benefits to both businesses and individuals. Therefore, it is important to provide algorithmic and theoretical foundations to optimize and analyze the use of WSNs. From the theoretical point of views, these studies have lead into many beautiful and challenging questions and results. As an example, the class of connected dominating sets and set covers have been under extensive research over the past few decades. They have also enriched other computer science and mathematical areas, such as graph theory and analysis techniques for non-sub modular greedy functions.
Within the computational biology domain, we are studying several optimization problems, such as combinatorial group testing, non-unique probes selection, and community structure decomposition. The purpose of these studies may vary widely. For example, the combinatorial group testing has various applications in blood testing, chemical leakage testing, coding, multi-access channel communication, and many others. In the context of biology, group testing is usually referred as pooling designs. As the technology for obtaining sequenced genome data is getting mature, more and more sequenced genome data are available to scientific research community, so that the study of gene functions has become a popular research direction. Such a study is supported by a high quality DNA library which usually is obtained through a large amount of testing and screening. Therefore, the efficiency of testing and screening becomes very important. Pooling design is a tool to reduce the number of tests in DNA library screening as well as in DNA micro arrays.
The following are some of our recent research work:
Detection of Malicious Users (DMU):
- Motivations: Detecting all malicious users (DMU) in the timely fashion is a very important topic nowadays since malicious users are a great threat currently in networking security. Yet no work in literature has exactly addressed this issue, to the best of our knowledge. This DMU problem underlies many attacking scenarios in the computer networking area, such as DOS or ARP spoofing.
- Objectives: Provide a novel theoretical framework for DMU, called Size Constraint Group Testing (SCGT). The main difference between this model and other existing GT models is that it has a size constraint on both the maximum number of items grouped together and the maximum number of pools used. With these size constraints, it poses several challenges in the group testing design. Study the properties of SCGT in depth and devise several algorithms, including both sequential and adaptive to solve the DMU. Based on the SCGT model and algorithms, provide the solid techniques from the system perspective to handle the malicious users.
Community Structures
- Motivations: Community structure is defined as a subgraph such that there is a higher density of edges within the subgraph than between them. This has applications in many domains, not only in computer networks, but also in computational biology, social research, life sciences and physics. Being able to identify these communities could help us to understand and exploit the networks more effectively. It also helps to reveal the hidden structure of complex networks. In addition, community structure can be used as a graph-based model to present the relationship of concepts in different domains or to identify the virtual organization.
- Objectives: Develop mathematical models and efficient approximation algorithms to determine the community structure of a given network; handle the dynamic and evolution of community structures; develop a weighted directed graph-based model to better represent the network and its properties, such as context-dependent dynamic relationship.
Virtual Backbone Assisted Routing
- Motivations: Since there are no fixed or pre-defined infrastructures in wireless ad hoc networks, it is important to construct the virtual backbone to alleviate the broadcast storm problem as well as to simplify routing maintenance and reduce energy consumption.
- Objectives: Model the virtual backbone as the Connected Dominating Set (CDS) problem, study the CDS problem in different models of networks: Unit Disk Graphs, Disk Graphs, and Directed Graphs; design and analyze the efficient approximation algorithms for this NP-hard problem; study the variants of this problem such as CDS with bounded Diameter, Dominating Tree, and Fault Tolerant CDS.
Broadcast Scheduling
- Motivations: Broadcast scheduling is a fundamental problem in wireless ad hoc networks. Thus it is very important to obtain the broadcast schedule which can deliver a message from a given source to all other nodes without collision or interference in a minimum amount of time. Most existing work on this problem use a limited interference model, which is only based on the transmission ranges of nodes.
- Objectives: Provide a more practical and realistic model to capture all interference scenarios; study and analyze this model in depth; devise constant approximation algorithms and efficient heuristic; investigate the generalization of this problem, which is to find a schedule in mesh networks with multi-channels, multi-radios.
Routing Protocols in Dynamic Networks
- Motivations: There are many pervasive applications that will benefit from wireless networks. For instance, wireless sensor networks can help improve the quality of life, especially for elderly people. This is very important as an aging baby-boomer generation is stressing the U.S. healthcare system. However, the lack of research in dynamic and mobile communication in a large-scale wireless networks must be remedied in order to fully being benefitted by wireless networks in the next generation.
- Objectives: Provide the probabilistic and evolving models representing the dynamic networks; investigate new routing paradigms based on the social interest profile rather than on (x, y)-coordinator; study the optimization problems underlying these models and paradigms; devise novel context and mobility-aware routing protocols.
Pooling Designs:
- Motivations: Pooling designs (mathematically called Group Testing) are used in DNA library screening to efficiently distinguish positive clones from negative clones, which are of fundamental importance in studying gene functions. Due to the large number of testing and screening, it is desirable to obtain a pool design with the minimum number of tests. More complicated, biological experiments usually contain errors and in some applications, there is a third category of clones called "inhibitors" whose effect is to neutralize positives. Thus pooling designs must be able to handle the fault-tolerance and inhibitors.
- Objectives: Construct pooling design using d-disjunct matrix for both classical and complex models; devise new algorithms for non-unique probes; investigate a more sophisticated mathematical models and provide in depth analysis; study the complexity of these models.