In the 1^st year of this project, we studied Bounded Data Latency Guaranteeing and Data Latency Bounded k-Sink Placement Problems in underwater sense networks and some connected dominating set problems in wireless sensor networks. Six papers have been produced from our efforts in study of those problems. Three are accepted and three are submitted to prestigious journals and conference, such as IEEE Transactions and INFOCOM, under review. All of our research work have graduate students involved. The discovery and research experience of the students have helped them to increase their research capability and to prepare their career in academia and industry.

For the Data Latency Bounded k-Sink Placement Problem, we are given a set of sensors in underwater environment and a positive integer k and want to find locations for k sinks to minimize the maximum hop-distance from each sensor to k sinks. The problem is similar to the well-known k-center problem in the literature. However, we found that they are quite different. Indeed, although the best polynomial-time approximation algorithm (2-approximation algorithm) for the k-center problem is still a constant-approximation for the Data Latency Bounded k-Sink Placement Problem, it is far from the best. Actually, we showed that the lower bound for performance ratio of polynomial-time approximation algorithm for the Data Latency Bounded k-Sink Placement Problem is still 2 and the 2-approximation algorithm for the k-center problem has performance ratio much bigger than 2 for the Data Latency Bounded k-Sink Placement Problem. However, we found a new polynomial-time approximation for the Data Latency Bounded k-Sink Placement Problem, which has performance ratio 2.

For the Bounded Data Latency Guaranteeing Problem, we are given a set of sensor in underwater environment and a positive integer d and want to find the minimum number of sink locations such that each sensor has distance at most d to at least one sink. We showed that this problem is NP-hard even in case that all sensors are identical. We also studied polynomial-time approximation algorithms for this problem.

In the 2^nd year of this project, we studied maximum lifetime coverage problem in wireless sensor networks, the positive influnce dominating set in social networks and data retriveal scheduling in wireless data broadcasting as well as energy efficient connected dominating set and connected set cover related to connected coverage problem. Six more papers (papers 7-12) have been produced from our efforts in study of those problems. They are accepted/published in some prestigious journals and conference, such as IEEE Transactions on Computers, Journal of Global Optimization and IEEE International Conference on Computer Communications (INFOCOM). All of our research work have graduate students involved. The discovery and research experience of the students have helped them to increase their research capability and to prepare their career in academia and industry. Actully, two female Ph.D. students (Ling Ding and Lidan Fan) were partially supported by this project. One (Ling Ding) has just graduated in Spring'2012 and now becomes an assistant professor in University.

For the maximum lifetime coverage problem, we are given a set of (point) targets and a set of sensors in the Euclidean plane and the problem is to find a schedule for sensors' sleeping/active time in order to maximize the lifetime of coverage, i.e., to maximum the length of the time period during which every target is monitored by at least one sensor. This is a fundamentl problem in wireless sensor networks. We constructed a polynomial-time constant-approximation for this problem, which solved an open problem known in the literature for many years. We also extended our new technique to a connected version of the coverage problem. Solutions for those problems are obtained through study of the minimum weight sensor cover problem or the minimum weight connected sensor cover problem. The latter is a special case of the minimum connected set cover problem. Therefore, we also moved our attention to the minimum connected set cover problem.

Clearly the approximation for the minimum connected set cover cannot be better than that for the minimum set cover. However, it is open for many years whether or not the minimum connected set cover is harder to approximate than the minimum set cover. We solved this open problem by showing that it is unlikely for the minimum connected set cover to have a polynomial-time (log n)^2-approximation.

The positive influnce dominating set is a variation of dominating sets. Since a dominating set can be considered as a special case of set cover. Therefore, we also studied the positive influnce dominting set in social networks with techniques developped by us, and made some significant contributions to the problem.

For the Bounded Data Latency Guaranteeing Problem, we are given a set of sensor in underwater environment and a positive integer d and want to find the minimum number of sink locations such that each sensor has distance at most d to at least one sink. We showed that this problem is NP-hard even in case that all sensors are identical. We also studied polynomial-time approximation algorithms for this problem.

In academic year 2012-2013, our goal is to study the bounding node-to-sink latency in underwater wireless sensor networks with multiple sinks, the lifetime of coverage in wireless sensor networks and the connected sensor cover in wireless sensor networks, and community expansion in social networks. We expected that the descovery in the study and the research experience would help participated students to prepare their career in academia and industry.

We organized a research seminar once a week. We had also initiated a course "cs7301 Advanced Algorithm Design in Wireless Sensor Networks and Social Networks" in Spring 2013. Meanwhile, we had discussion with our collaborator Jie Wang and Jinhong Cui frequently. There are four journal papers published and six conference papers published. One of them is a result of discussion with our collaborators.

In the last year of the project, We organized a research seminar once a week. We had also continued to provide a course "cs7301 Advanced Algorithm Design in Wireless Sensor Networks" and a course "cs7301 Advance Algorithm Design in Social Networks" in Fall 2013 and Spring 2014. Meanwhile, we had discussion with our collaborator Jie Wang and Jinhong Cui frequently. There are ten journal papers published and seven conference papers published/accepted. Results in above publications are formed main parts of five Ph.D. dissertations of Yuqing Zhu, Lidan Fan, Lidong Wu, Yuanjun Bi and Kai Xing who received their Ph.D. degree in 2014.

Our research has generated several novel algorithms, some of which improve on the performance and accuracy of previous algorithms, theoretically prove and showcase the optimal placement of data replica to enhance the security in distributed database, and provide an opportunity for the training of several graduate students. Most of our results have been published in various prestigious journals and conferences such as IEEE Transactions on Knowledge and Data Engineering (TKDE), IEEE Transactions on Mobile Computing (TMC), the International Conference on Distributed Computing Systems (ICDCS), the International Conference on Data Mining (ICDM), IEEE International Conference on Computer Communications (INFOCOM), and IEEE Transactions on Parallel and Distributed Systems, etc.

The PI Weili Wu has also been actively doing professional service. She is an area chair for ICDM2013, TPC members for INFOCOM2014 and 2015.

Many routing protocols aim to improve delivery ratio, as well as reduce end-to-end delay time and total replicas in delay tolerant networks, or disruption tolerant network (DTN). Most prior literatures study mobile ad hoc wireless networks without considering existing physical infrastructure. By taking them into considerations, we propose a routing protocol in DTNs considering consecutive forwarding quality (CFQ), and conduct extensive simulations with real trace data, so as to evaluate the performance of CFQ. Simulation results show that CFQ outperforms most existing pure probability based forwarding protocols and most existing pure centrality-community based forwarding protocols in that its delay time and replicas are significantly reduced and its delivery ratio is significantly increased. At last, we are able to conclude that CFQ is more buffer-efficient and time-efficient.

Using a connected dominating set (CDS) to serve as the virtual backbone of a wireless network is an effective way to save energy and alleviate broadcasting storm. Since nodes may fail due to an accidental damage or energy depletion, it is desirable that the virtual backbone is fault tolerant. A node subset C is an m -fold connected dominating set ( m -fold CDS) of graph G if every node not in C has at least m neighbors in C and the subgraph of G induced by C is connected. In a journal paper, we designed a greedy algorithm to compute an m -fold CDS in a general graph, which has size at most 2+ln(Δ+m−2) times that of a minimum m-fold CDS, where Δ is the maximum degree of the graph. This result improves on the previous best known performance ratio of 2H(+m−1) for this problem, where H() is the Harmonic function.

Swapped Networks (SNs) are a family of two-level interconnection networks, suitable for constructing large parallel and distributed systems. In this paper, the Minimum Dominating Set (MDS) problem and the Minimum Connected Dominating Set (MCDS) problem in wireless sensor networks are investigated based on the connectivity rule of SNs. We prove the two problems in wireless sensor networks are NP-hard, and present two efficient algorithms for building dominating sets and connected dominating sets in wireless sensor networks. The proposed algorithms use as input a given (connected) dominating set of the factor network, and yield a good approximation of an MDS or MCDS for the SN provided that the input is a good approximation of an MDS or MCDS for the factor network. We also derive several non-trivial bounds on the (connected) domination parameters of wireless sensor networks.

One type of distributed systems is the client/server system consist of clients and servers. In order to improve the performance of such a system, client assignment strategy plays an important role. There are two criteria to evaluate the load on the servers - total load and load balance. The total load increases when the load balance decreases, vice versa. It has been proved that finding the best client assignment is NP-hard. In this paper, we propose a new model for the client assignment problem and design an algorithm based on Semidefinite programming (SDP). Our method has a (relaxed) performance ratio 0.87 when only 2 servers exist. In general case, our method becomes a heuristic, and the ratio of each iteration is 0.87. We are the first one to give these bounds. Our simulation results are compared with the state-of-art client assignment method, and our strategy outperforms it in terms of running time while keeps the load in similar level.

Effectiveness of MapReduce as a big data processing framework depends on efficiencies of scale for both map and reduce phases. While most map tasks are preemptive and parallelizable, the reduce tasks typically are not easily decomposed and often become a bottleneck due to constraints of data locality and task complexity. By assuming that reduce tasks are non-parallelizable, we study offline scheduling of minimizing makespan and minimizing total completion time, respectively. Both preemptive and non-preemptive reduce tasks are considered. On makespan minimization, for preemptive version we design an algorithm and prove its optimality, for non-preemptive version we design an approximation algorithm with the worst ratio of 3/2-1/2h where h is the number of machines. On total complete time minimization, for non-preemptive version we devise an approximation algorithm with worst case ratio of 2-1/h, and for preemptive version we devise a heuristic. We confirm that our algorithms outperform state-of-art schedulers through experiments.

Wireless data broadcast is a popular data dissemination method in mobile computing environments because of its capability of concurrently disseminating data to multiple users. In this paper, we study the data retrieval scheduling problem for multi-item requests in multi-channel broadcast environments. To maximize the number of downloads given a deadline, we define a problem called largest number data retrieval (LNDR). We prove the decision problem of LNDR is NP-hard, and we investigate approximation algorithm for it. We also define another problem called minimum cost data retrieval (MCDR), which aims at downloading a set of requested data items with the least response time and energy consumption. We prove MCDR is NP-hard to approximate to within any non-trivial factor. Therefore, we investigate heuristic algorithm for it. Finally we provide simulation results to demonstrate the practical efficiency of the proposed algorithms.

The spread of rumor or misinformation in social networks may cause bad effects among the public. Thus, it is necessary to find effective strategies to control the spread of rumor. Specifically, in our paper, we consider such a setting: initially, a subset of nodes is chosen as the set of protectors, and the influence of protector diffuses competitively with the diffusion of rumor. However, in real world, we generally have limited budget (limited number of 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 time deadline. Generalizing two seminal models in the field—the Independent Cascade (IC) model and the Linear Threshold (LT) model—we propose two new models of competitive influence diffusion in social networks with the following three factors: a time deadline for information diffusion, random time delay of information exchange and personal interests regarding the acceptance of information. Under these two models, we show that the optimization problems are NP-hard. Furthermore, we prove that the objective functions are submodular. As a result, the greedy algorithm is used as constant-factor approximation algorithms with performance guarantee 1−1e for the two optimization problems.

Key outcomes or other achievements:

Obtained results have been put in 10 journal papers and 7 conference papers. All journal papers have been published. Among 7 conference papers, 6 have been published and 1 is accepted. 5 of them are published / accepted in top conferences ICDM2013, INFOCOM2014 and INFOCOM 2015.

In our published paper 1 (see the publication section), we showed that the Bounded Data Latency Guaranteeing Problem is NP-hard and presented a polynomial-time O(d)-approximation algorithm for the problem on 2-dimensional underwater sensor networks and a polynomial-time O(d^2)-approximation algorithm for the problem on 3-dimensional underwater sensor networks.

In paper 2, we showed that the Data Latency Bounded k-Sink Placement Problem is NP-hard and also showed that although the problem looks similar to the well-known k-center problem, they are quite different in the sense that approximation strategy for the k-center problem may not work well for the Data Latency Bounded k-Sink Placement Problem. Furthermore, we presented a polynomial-time 2-approximation for the Data Latency Bounded k-Sink Placement Problem and showed that this is the best possible in term of performance ratio.

In paper 3, we constructed a distributed algorithm to produce weakly connected dominating set in a secure system.

In paper 4, we study data collection problem with moving devices and give a good approximation algorithm with theoretical analysis and computational experimental evidence.

In paper 5, we found several errors existing in the literature about fault-tolerant virtual backbone in wireless sensor networks and presented a polynomial-time constant-approximation algorithm for 3-connected virtual backbone in wireless sensor networks when all sensor are identical.

In paper 6, we gave a distributed construction of virtual backbone in wireless networks with directional antennas. This construction is under constraint that the routing cost between any two stations keeps the minimum, i.e., the hop-distance between two stations passing through virtual backbone is the same as the hop-distance between them without asking to pass through the virtual backbone. We showed that the problem is NP-hard and a lower bound for the performance ratio of possible polynomial-time approximation algorithms, which indicates that our construction is nearly best possible.

In paper 7, we construct a polynomial-time (4+a)-approximation for the maximum lifetime coverage problem in wireless sensor networks, which solved an open problem known since 2005. In 2005, the coverage problem has been identified as a fundamental problem in wireless sensor networks. Many efforts have been made to find a good approximtion solution bacause the problem is NP-hard. However, no polynomial-time constant-approximation had be found prior to our work.

In paper 8, we study the minimum connected set cover problem. In this problem, we are given a cllection C of subsets of a base set X and a graph G with vertex set C. The problem is to find a subcollection C' with the minimum cardinality such that every element in X is in a subset in C' and the subgraph induced by C' is connected. It was an open problem whether there exists a polynomial-time O(log n)-approximation for this problem. We solved this problem by showing the equivalence between this problem and the group Steiner tree. As a consequence, it is unlikely for this problem to have a polynomil-time O(log^2 n)-approximation.

In paper 9, an approximation algorithm is designed for the connected dominating set with the minimum energy consumption.

In paper 10, a connected variation of the maximum lifetime coverage problem is studied. We extend developped techiques in paper 7 to this variation and obtained a polynomial-time constant-approximation again.

In paper 11, a data retriveal scheduling problem is studied in wireless data broadcast systems. We obtained some nice approximation algorithms with good performance both in theory and computational experiments.

In paper 12, we study the positive influnce dominating set in social networks. In this problem, we are given a graph and the problem is to find a vertex subset D with minimum cardinality such that for every vertex x, there are at least a half of neighbors belong to D. We construct a greedy algorithm with a good theoretical guarantee performance ratio for the problem in a class of social networks.

In paper 13, Bounding node-to-sink latency is an important issue of wireless sensor networks (WSNs) with a quality of service requirement. In this paper, we proposes to deploy multiple sinks to control the worst case node-to-sink data latency in WSNs. The end-to-end latency in multihop wireless networks is known to be proportional to the hop length of the routing path that the message moves over. Therefore, we formulate the question of what is the minimum number of sinks and their locations to bound the latency as the minimum d-hop sink placement problem. We also consider its capacitated version. We show problems are NP-hard in unit disk graph (UDG) and unit ball graph, and propose constant factor approximations of the problems in both graph models. We further extend our algorithms so that they can work well in more realistic quasi UDG model. A simulation study is also conducted to see the average performance of our algorithms.

In paper 15, we study the aggregation problem with power control under the physical interference. The maximum power is bounded. The goal is to assign power to nodes and schedule transmissions toward the sink without physical interferences such that the total number of time slots is minimized. We present a constant-approximation for the aggregation problem.

In paper 16, inspired by the backbone concept in wired networks, virtual backbone is expected to bring substantial benefits to routing in wireless sensor networks (WSNs). Virtual backbone construction based on Connected Dominating Set (CDS) is a competitive approach among the existing methods used to establish virtual backbone in WSNs. Traditionally, CDS size was the only factor considered in the CDS-based approach. The motivation was that smaller CDS leads to simplified network maintenance. However, routing cost in terms of routing path length is also an important factor for virtual backbone construction. In our research, both of these two factors are taken into account. Specifically, we attempt to devise a polynomial-time constant-approximation algorithm that leads to a CDS with bounded CDS size and guaranteed routing cost. In this paper, we prove that, under general graph model, there is no polynomial-time constant-approximation algorithm unless P = NP. Under Unit Disk Graph (UDG) model, we propose an innovative polynomial-time constant-approximation algorithm, GOC-MCDS-C, that produces a CDS D whose size I D is within a constant factor from that of the minimum CDS. In addition, for each node pair u and v, there exists a routing path with all intermediate nodes in D and path length at most 7 · d(u, v), where d(u, v) is the length of the shortest path between u and v. Our theoretical analysis and simulation results show that the distributed version of the proposed algorithm, GOC-MCDS-D, outperforms the existing approaches.

In paper 17, given a requested area, the Minimum Connected Sensor Cover problem is to find a minimum number of sensors such that their communication ranges induce a connected graph and their sensing ranges cover the requested area. Several polynomial-time approximation algorithms have been designed previously in the literature. Their best known performance ratio is O(r ln n) where r is the link radius of the sensor network and n is the number of sensors. In this paper of publication list, we will present two polynomial-time approximation algorithms. The first one is a random algorithm, with probability 1 - ε, producing an approximation solution with performance ratio O(log3 n log log n), independent from r. The second one is a deterministic approximation with performance ratio O(r), independent from n.

In paper 18, building upon the observation that individuals’ decisions to purchase a product are influenced by recommendations from their friends as well as their own preferences, in this paper, we propose a new model that factors in people’s preferences for a product and the number of his/her neighbors that have adopted this product. In our model, as in related ones, beginning with an “active” seed set (adopters), an adoption action diffuses in a cascade fashion based on a stochastic rule. We demonstrate that under this model, maximizing individuals’ adoption of a product, called the product adoption maximization (PAM) problem, is NP-hard, and the objective function for product adoption is sub-modular for time T (T = 1, 2) when the function for estimating the influence coming from neighbors is sub-linear. Hence, a natural greedy algorithm guarantees an approximation.

In paper 19, we use the charged system model to represent the social influence. This model provides a natural description about the behaviors of influence and explains why the influence makes communities expand. Based on this physical model, we propose two objective functions for choosing proper candidates to enlarge a community, considering of the cost and benefit issue. Then a linear programming approach is given to maximize those two objective functions. We validate our ideas and algorithm using two real-world networks. The results demonstrate that our model can choose excellent propagation candidates for a specific community, comparing to other two algorithms.

In paper 20, while most existing work about community focus on the community structure and the tendency of one individual joining a community; equally important is to understand social influence from community and to find strategies of attracting new members to join the community, which may benefit a range of applications. In this paper, we formally define the problem of community expansion in social network, which is under the marketing promotional activities scenario. We propose three models, Adopter Model, Benefit Model and Combine Model, to present different promotion strategies over time, taking into consideration the community structure characters.

In paper 21, taking advantage of online social network, rumars spead fast in public and give undesirable effect. In this paper, we studied rumor blocking pronblem and gave nearly best approximation solutions.

In paper 22, we present a middleware named SmartPrint to provide cloud print service in office, where many heterogeneous networks exist. The goal of the system is to implement a platform that shields the communication heterogeneity of office devices and make authorized users freely connect to all the printers with no modification on their terminals. SmartPrint manages all the printers in an office building, and it is easy to use for strange users who may even know nothing about the printers. SmartPrint can automatically choose printers for the office staffs. We propose and implement two printer allocation methods, one aims to improve the experience of the user with short print task, and the other is a multiple attributes decision algorithm which considers all factors including spatial information that impact the user experience. Through experiments we validate the methods, and prove SmartPring achieves high user satisfaction from collected real data.

1) We are training students with the techniques discovered in this project for designing efficient algorithms and analyzing their complexities.

2) In Spring 2011, We have developed a research class (CS 7301 Recent Advances in Computing - Advanced Data Management and Data Communication) in Computer Science Department. In Fall 2011 and Spring 2012, we have been continuously offering this advanced course, which covers various research topics focusing on the design and analysis of algorithms for optimization problems that occur in wireless networking environments. Especially, we incorporated some research topics related to the project in this class. A number of Computer Science Ph.D students attended this class, and some of them are very interested to work on the underwater sensor networks. The PI, Dr. Wu especially encourage women and minority students to join in this research project and take this related research class. She has been supervising many female students on research projects and plan to continue this effort.

3) Obtained results from this project have been used for teaching in two developed advanced research courses cs7301 (Advanced Algorithm Design in Wireless Sensor Networks) and cs7301 (Advanced Algorithm Design in Social Networks), which were offered in Fall 2013 and Spring 2014 in Department of Computer Science, University of Texas at Dallas. They have also been used in Ph.D. dissertations of Yuqing Zhu, Lidan Fan, Lidong Wu, Yuanjun Bi, and Kai Xing. These five graduate students have received their Ph.D. degree in Spring 2014 or Summer 2014. Three of them are already working in universities as assistant professors. Moreover, a collaborator (former student) Zaixin Lu has moved from a postdoctor position to an assistant professor position. The PI, Dr. Wu, especially encourages female and minority students to join in this research project and take this related research class. She has been supervising many female students on research projects and plans to continue this effort.

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 have presented our new findings/results in several top international conferences such as IEEE International Conference on Computer Communications (INFOCOM) 2012 and 2013, the International Conference on Distributed Computing Systems (ICDCS) 2013, IEEE International Conference on Mobile Ad-hoc and Sensor Networks (MSN) 2013, Database Systems for Advanced Applications (DASFAA) 2013, COCOON (CSoNet) 2013, 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, Microsoft Research Center in Beijing, etc). In addition, we have produced several joural papers, which are published/accepted by the prestigous journals (e.g., IEEE Transactions on Computers, Journal of Global Optimization, IJSNet, IEEE Transactions on Parallel and Distributed Systems, etc) to disseminate our new findings.

1. On Guaranteeing Bounded Data Latency in Wireless Sensor Networks
2. Minimum Data Latency Bound k-Sinks Placement Problem in Wireless Sensor Networks
3. Constructing Weakly Connected Dominating Set for Secure Clustering in Distrubuted Sensor Network
4. Minimizing Data Collection Latency in Wireless Sensor Network with Multiple Mobile Elements
5. On Construction of Fault-Tolerant Virtual Backbone in Wireless Networks
6. Efficient Virtual Backbone Construction with Routing Cost Constraint in Wireless Net
7. Constant-approximation for target coverage problem in wireless sensor networks
8. Complexity and approximation of the connected set-cover problem
9. Minimum Total Communication Power Connected Dominating Set in Wireless Networks
10. Maximum Lifetime Connected Coverage with Two Active-Phase Sensors
11. Optimal Data Retriveal Scheduling in the Multi-Chnannel Data Broadcast Environments
12. Positive influence dominating sets in power-law graphs
13. On bounding node-to-sink latency in wireless sensor networks with multiple sinks
14. CSI: Charged System Influence Model for Human Behavior Prediction
15. Conflict-Free Many-to-One Data Aggregation Scheduling in Multi-Channel Multi-Hop Wireless Sensor Networks
16. CDS-Based Virtual Backbone Construction with Guaranteed Routing Cost in Wireless Sensor Networks
17. Approximations for Minimum Connected Sensor Cover
18. A New Model for Product Adoption over Social Networks
19. Community Expansion Model Based on Charged System Theory
20. Community Expansion in Social Network
21. Least Cost Rumor Blocking in Social Networks
22. SmartPrint: A Cloud Print System for Office
23. Influence and Profit: Two Sides of the Coin
24. On Construction of Quality Fault-Tolerant Virtual Backbone in Wireless Networks
25. Constant-approximation for optimal data aggregation with physical interference
26. PTAS for the minimum k-path connected vertex cover problem in unit disk graphs
27. The Maximum Community Partition Problem in Networks
28. An approximation algorithm for client assignment in client/server systems
29. Minimizing makespan and total completion time in MapReduce-like systems
30. Approximation Algorithm for the Balanced 2-Connected Bipartition Problem
31. Minimum Latency Multiple Data MULETrajectory Planning in Wireless Sensor Networks
32. Data Retrieval Scheduling for Multi-Item Requests in Multi-Channel WirelessBroadcast Environments
33. Mining hidden links in social networks to achieve equilibrium
34. A novel approach to online social influence maximization
35. Maximizing rumor containment in social networks with constrained time
36. Evaluation and comparison of various indexing schemes in single-channel broadcast communication environment
37. Minimum vertex cover in ball graphs through local search
38. An individual-based model of information diffusion combining friends' influence
39. A nature-inspired influence propagation model for the community expansion problem
40. A greedy algorithm for the fault-tolerant connected dominating set in a general graph
41. Minimum number of disjoint linear forests covering a planar graph
42. An efficient routing protocol based on consecutive forwarding prediction in delay tolerant networks

Dr. Wu invited Dr. Wang (one of her collaborators from UML) to visit her research laboratory discussing research problems, exchanging ideas, and working out some solutions for this project. Dr. Wu and her students have met Dr. Cui (another collaborator from UConn) several times at some conferences (TPC meeting for INFOCOM 2011, INFOCOM 2012, INFOCOM 2013, WUWNet 2011, etc.) to discuss the research progress, exchange new ideas for research problems proposed in this project.

WUWNet is an ACM workshop on underwater network (http://wuwnet.org) in conjunction with ACM MobiCom. Dr. Wu sent her student, Ms. Ling Ding (She recently graduated and becomes a facuty member at University of Washington Tacoma) to attend this important conference last year (December 1-2, 2011, Seattle, Washington, USA) to learn the new trending and new technologies in this area.

In addition to the regular weekly meeting via skype/conference call with the collaborators, Dr. Jie Wang from University of Massachusetts Lowell and Dr. Junhong Cui from University of Connecticut to discuss this collaborated project, the PI, Dr. Du also travel to IEEE INFOCOM TPC meeting to personally meet one of the collaborator, Dr. Cui to exchange and discuss research ideas related to this project.

So far (during 2012-2013), we found two polynomial-time approximation algorithms for the minimum connected sensor cover problem. The first one is a random algorithm, with probability 1 - ε, producing an approximation solution with performance ratio O(log3 n log log n), independent from r. The second one is a deterministic approximation with performance ratio O(r), independent from n. Here, r is the link radius of the network and n is the number of sensors. This decovery suggests us that either there exists a unknown relationship between r and n, or there exists a polynomial-time constant-approximation for the minimum connected sensor cover problem. Therefore, we want to study futher on the following problems in next academic year:

(1) What ralationship exists between the number of sensors and the link radius of the sensor network?

(2) Is there a polynomial-time constant-approximation for the minimum connected sensor cover problem? Since it is known that the minimum sensor cover problem has PTAS, our problem would reduce to study whether there exists or not a polynomial-time approximation for node-weighted Steiner tree problem in unit disk graphs.

(3) It is also an interesting subject to extend our results to wireless sensor networks with certain mobility. In fact, the mobility may reduce the size of connected sensor cover and gives us a new challenge to design a good solution.