Throughput Optimization in Wireless Mesh Networks
(ACKNOWLEDGMENT: Sponsered by NSF Award# CNS-0831579 Collaborative Research: NEDG:)
People
Project Activities
During last four academic year (2008-2012), we have studied several problems motivated from technical developments of wireless network systems and related topics. 14 papers (1-14) have been published/accepted by conferences and journals.
Our research in this academic year (2012-2013) has two folders. On one side, we continue our study on some classical problems in wireless ad hoc and sensor networks, such as the sensor coverage. On the other side, we move our attention to new research directions, such as community partition, rumor blocking and optimal influence in social networks.
For the sensor coverage, we study the maximum lifetime coverage problem and discovered a new technique. With this technique, we construct a polynomial-time approximation with the best known provable performance ratio.
For community partition, rumor blocking and optimal influence in social networks, we introduced new models and studied computational complexity and approximation solutions under new models.
In addition, we obtained some significant results in underwater sensor networks.
All above research activities have graduate students involved. The discovery and research experience of the students helped them to prepare their career in academia and industry. Indeed, one Ph.D. student Zaixin Lu graduated in 2013 who was supported in part by NSF under this grant. He also found an academic position in a university.
During this period, we had several discussions with our collaborators Qilian Liang and Xiuzhen Cheng at George Washington University and University of Texas at Dallas and INFOCOM TPC TPC meeting. We exchanged our research results and ideas for future research. Research results obtained from those discussions are put in a journal paper [18].
New Findings and Results
- The node-to-sink latency is an important issue in study of wireless under-water sensor networks with a QoS requirement. To bound this latency, we studied a minimum d-hop sink placement problem, that is, given the latency bound, to minimize the number of sinks with possible placement to satisfy the latency bound. We showed that for wireless homogeneous sensor networks, this problem is NP-hard and designed a polynomial-time constant-approximation. This result is contained in paper 15.
- In application of wireless sensor networks, the coverage is an important issue. For a long term request of coverage, especially longer than the lifetime of a battery, how to schedule sleeping/active time of sensors to maximum the lifetime of coverage. This is a classic and important optimization problem, called the maximum lifetime coverage problem. In the literature, there are several designs of approximation solutions and the theoretical guaranteed performance ratio of those approximation solutions gets improved year by year, which is a challenge competition. We obtained a polynomial-time approximation with performance ratio 3, which is the best-known so far. This result is contained in paper 16.
- Community partition is an important problem in social networks. In this year, we studied the social community partition problem from the perspective of influence propagation which is one of the most important features of social communication. We formulate it as a combinatorial optimization problem which aims at partitioning a social network into disjoint communities such that the influence propagation within each community is maximized. We give both approximation algorithm and heuristic algorithm for this problem. The approximation algorithm has a provable performance guarantee for a class of influence propagation models and the heuristic algorithm is suitable for applications in large social networks. We also conduct simulation on real social networks to demonstrate the practical efficiency of our algorithms. The experimental results show that, more accurate partitions according to influence propagation can be obtained by using our algorithms rather than using some classic community partition algorithm. Results described as above are contained in paper 18.
- Rumor propagation in social networks may cause bad effects among the public. Thus, it is necessary to find strategies to control its spread. In this year, we consider such a setting: Initially, a subset of nodes is chosen as protectors, and the influence of protector diffuses competitively with that of rumor. However, in real world, we generally have limited budget (protectors) and time to fight with rumor. Therefore, we study the problem of maximizing rumor containment within a fixed number of initial protectors and a given deadline. We propose two new models which consider time and competitive influence in social networks. Under these two models, we show that the optimization problems are NP-hard and prove that the objective functions are submodular. Therefore, the greedy algorithm guarantees a performance ratio 1-1/e for these problems. Those results can be found in paper 19.
- Recently, increasing third-party applications have been developed to execute over certain open-API phone operating systems such as Apple’s iOS platform, Google’s Android platform and Windows Phone platform. Witnessing the envisioned popularity, more fear appears on malware programmers diffusing from one phone to another. Therefore, it is worthwhile for the service providers to find an efficient counter-mechanism to constrain mobile worms as soon as possible. In this year, we studied the problem of how to select an optimal set of phones to patch based on social relations between users in cellular networks. However, in most previous research works using this kind of social network relationships, two users within a friendship are usually assumed to possess the same probability to believe each other based on their communication frequencies. In our work, we introduce a new model in which the asymmetric (distinct) trust level exists, which has relation with the neighborhood size of each user. Under this model, we explore a timely protective set which is used to constrain the spread of worms with fast response. We analyze the complexity of selecting TPS and present a greedy algorithm and its approximation ratio. Those results are included in paper 17.
Contribution
1) We're training students with the techniques proposed in this project for designing efficient algorithm and analyzing their complexities.
2) We have developed a Ph.D. research seminar course for MCWN (Mobile Computing and wireless Networking) research group (http://theory.utdallas.edu/), in Spring 2008. We also developed an advanced graduate level class (CS 7301 Recent Advances in Computing - Algorithm Design In Wireless/Social Network). This course is covering various research issues focusing on the design and analysis of algorithms for optimization problems that occur in wireless networking environments and social networks. We have been continuously offering this course in Fall 2008, Fall 2009, Fall 2011, Fall 2012, and Spring 2013.
3) This project at UT Dallas has led to several novel techniques for designing efficient algorithms and analyzing their complexities in many applications in wireless sensor networks.
4) Our current (and future) direction is for all participants (including students, collaborated researchers from different research institutes) to make use of this collaborative project as an opportunity to gain proficiency in a broadly applicable skills including oral and written communication, research methods, critical thinking, and problem solving. Therefore, regardless of whether they continue in computer science or software engineering, students will have acquired valuable skills that will better prepare them for their future field of study. Thus, the benefits of such a program have been inter-disciplinary as well.
Outreach Activities
We have been holding regular seminars for all students at UTD to disseminate the new results generaged from this project. We also created a webpage and attended many high quanlity international conferences for external dissemination and outreach.
We present our new findings/results in several international conferences
such as SODA08, COCOON08, COCOA08, COCOON09, INFOCOM 2011, INFOCOM 2012, INFOCOM 2013, ICDCS 2011, COCOA 2011, WASA 2012, ICUIMC2011, ISFOR2012, DIS2012 etc. We also presented our results and our approaches in many invited talks at various well known research institutes and universities (e.g., Tsinghua University, Fudan University, Xi'an Electronic University, Harbin Institute of Technology (Shenzhen), Zhejiang Normal University, Microsoft Research Center in Beijing, University of Florida, Korea University, etc). In addition, we have produced several joural papers, which are published/accepted by the prestigous journals (e.g. IEEE Transactions on Parallel and Distributed Systems (TPDS), IEEE Transactions on Computers, Journal of Global Optimization, Journal of combinatorial Optimization, IEEE Transactions on Mobile Computing, etc) to disseminate our new findings.
Publications
1. Constructing Minimum Connected Dominating Sets with Bounded Diameters in Wireless Networks
2. Cooperative Bridges: Topology Control in Cooperative Wireless Ad Hoc Networks
3. Distributed Construction of Connected Dominating Sets with Minimum Routing Cost in Wireless
Networks
4. A Better Approximation Algorithm for Computing Connected Dominating Sets in Unit Ball Graphs
5. Minimum data latency bound k-sinks placement problem in wireless sensor networks
6. Efficient Algorithms for Topology Control Problem with Routing Cost Constraints in Wireless Networks
7. PND: A p-persistent neighbor discovery protocol in wireless networks
8. FTTP: A fast tree traversal protocol for efficient tag identification in RFID networ
9. Constant Approximation for Vitual Backbone Construction with Guaranteed Routing Cost
10. Radar placement along banks of river
11. Complexity and approximation of the connected set-cover problem
12. Approximation and Inapproximation for the Influence Maximization Problem in Social Networks under Deterministic Linear Threshold Model
13. Energy-Efficient Roadside Unit Scheduling for Maintaining Connectivity in Vehicle Ad-hoc Network
14. Tight Performance Bounds of Multihop Fair Access for MAC Protocols in Wireless Sensor Networks and Underwater Sensor Networks
15. On Bounding node-to-sink latency in wireless sensor networks with multiple sinks
16. New approximation for maximum lifetime coverage
17. Asymmetric Trust Dependent Worm Containment in Cellular Networks
18. Influence-based Community Partition for Social Networks
19. Maximizing Rumor Containment in Social Networks with Constrained Time
Collaboration Efforts
The PI, Dr. Du visited Dr. Cheng (one of their collaborators from George Washington University) for discussing research problems, exchanging ideas, and working out some solutions for this project. During this period, our research group had several discussions with our collaborators Qilian Liang and Xiuzhen Cheng at various places such as University at Dallas and INFOCOM TPC meeting. We exchanged our research results and ideas for future research.
For example, they would like to include the mobile sensors in the coverage problem. Actually, when all or part of sensors have certain mobility, the lifetime of coverage may increase a lot since mobile sensors can move to holes to keep the coverage alive when sensors are not deployed so balanced. Of course, this will also motivate several interesting problems, such as how to find holes, how to move to holes within certain moving capacity of each sensor?
Another planed collaborative research direction is to consider data processing. In fact, sensors have limited ability to process data. When we balance the energy consumption of each sensor, we may need to study not only data collection and transmission, but also some simple data processing.
Those planed research will be included in our new collaborative project.
Research Plan for Next Year
So far (during 2010-2012), we have studied some classical problems in wireless ad hoc and sensor networks, such as the virtual backbone and the sensor coverage. In the next year, we would like to include the mobile sensors in the coverage problem. Actually, when all or part of sensors have certain mobility, the lifetime of coverage may increase a lot since mobile sensors can move to holes to keep the coverage alive when sensors are not deployed so balanced. Of course, this will also motivate several interesting problems, such as how to find holes, how to move to holes within certain moving capacity of each sensor?
Another planed research direction is to consider data processiong. In fact, sensors have limited ability to process data. When we balance the energy consumption of each sensor, we may need to study not only data collection and transmission, but also some simple data processing.