Reliable Spatial-Temporal Coverage with Minimum Cost in Wireless Sensor Network Deployments

In the first three years of this project, we studied several reliable spatial-temporal coverage problems in wireless sensor network application [3, 31, 4, 2, 23, 1]. The connected dominating set (CDS) is the focus of our research in this project. It has been a well known approach for constructing a virtual backbone to alleviate the broadcasting storm in wireless networks. With the help of the CDS, average message burden of the network could be reduced so that routing becomes much easier and can adapt quickly to network topology changes. Furthermore, using a CDS as forwarding nodes can efficiently reduce the energy consumption, which is also a critical concern in wireless sensor networks.

A Virtual Backbone (VB) of a wireless network is a subset of nodes such that only VB nodes are responsible for routing-related tasks. Since a smaller VB causes less overhead, size is the primary quality factor of VB. Frequently, Unit Disk Graphs (UDGs) are used to model 2D homogeneous wireless networks, and the problem of finding minimum VBs in the networks is abstracted as Minimum Connected Dominating Set (MCDS) problem in UDGs. In some applications, the altitude of nodes can be hugely different and UDG cannot abstract the networks accurately. Then, Unit Ball Graph (UBG) can replace UDG. In this project, we study how to construct quality CDSs in UBGs for spatial-temporal coverage problem in distributed environments.

We have been working on efficient algorithm and theoretical analysis [3, 4, 2, 23, 1] focusing on:

1) The performance of these approximations highly depends on the relationship between the size of maximal independent set and the size of minimum connected dominating set in unit disk graph.

2) The approximation algorithms for minimum connected dominating set in 3-dimensional wireless network (unit ball graph) and minimum connected d-hop dominating set in unit disk graph.

1) Constructing quality CDSs in UBGs (Unit Ball Graphs) in distributed environments;

2) The approximation algorithms for minimum VBs in a distributed manner for 3D homogeneous wireless networks such as USNs.

In all these areas, we developed new algorithms, which improve the approximation ration for each problem. The research also provided opportunities for several graduate students and exchange scholars to be involved in the process of scientific research. Most of our research results have been published in various prestigious academic journals and conferences, such as IEEE Transaction on Mobile Computing, Theoretical Computer Sciences, Combinational Optimization, Database and Expert Systems Applications (DEXA), etc.

During the period from 9/1/2012 to 8/31/2013, we continuously studied coverage problems and connected dominating set problem in wireless sensor networks. Meanwhile, we did an extensive study on the data retrieval scheduling in wireless data broadcasting systems and optimal influence in social networks.

The connected dominating set (CDS) has been a well known approach for constructing a virtual backbone to alleviate the broadcasting storm in wireless networks. With the help of the CDS, average message burden of the network could be reduced so that routing becomes much easier and can adapt quickly to network topology changes. Furthermore, using a CDS as forwarding nodes can efficiently reduce the energy consumption, which is also a critical concern in wireless sensor networks. The problem of computing the minimum connected dominating set can be seen as a special case of coverage problem in wireless sensor networks where we look for a subset of sensors to cover (collect data from) all sensors and to connect them (deliver collected data) to a center.

Indeed, for a classic connected sensor coverage problem, we are given a set of sensors and a set of targets, and we are looking for the minimum number of sensors covering all targets and inducing a connected subgraph. In the case of connected dominating set, the set of sensors and the set of targets are identical.

There are two types of coverage problems, minimum cardinality and maximum lifetime. Given a set of sensors and a set of targets, for minimum cardinality, we are looking for the minimum number of sensors to cover all targets under certain constraints, while for maximum lifetime, we are looking a sensor sleep/activate scheduling to maximize the total time for all targets to be covered. These two types of problems have been found to have very interesting relationship about approximation algorithms. Last year, we designed a polynomial-time constant-approximation for a classic maximum lifetime coverage problem, which gives a positive solution for a long-standing open problem. Indeed, it was open for more than ten years whether this coverage problem has polynomial-time constant-approximation. We also extended this result to the maximum lifetime connected coverage problem in wireless sensor networks with two-active-phase sensors. This year, we give two interesting approximation algorithms for minimum connected sensor cover problem. One has performance ratio depending on network size, independent from the link radius and the other has performance ratio depending on the link radius independent from the network size. The existence of these two approximation solutions indicates some interesting open problems for further study.

We continued working on finding minimum VBs of networks problem which is abstracted as Minimum Connected Dominating Set (MCDS) problem. To improve the quality of CDS, we introduced routing cost constraints and obtained a sequence of results about MCDS under some routing cost constraint.

Data broadcasting is an interdisciplinary area between wireless communication, multimedia and data management. Data retrieval scheduling is an important research subject in the study of the data broadcasting. We obtained a sequence of results on complexity and approximations of data retrieval scheduling in one channel and multi-channel environments.

Above mentioned research works and others have been organized into 12 papers (papers 24-35) which are published or accepted by journals and conferences; most of them are prestigious, such as IEEE Transactions and INFOCOM.

Most of our research have graduate students and exchange scholars involved. Therefore, our research provided opportunities for graduate students and exchange scholars to get training in the process of scientific research. Especially, the discovery and research experience of the graduate students would help them to prepare their career in academia and industry. Indeed, we have one graduate student (Zaixin Lu) received his Ph.D. degree during this period. He started his working career in this Fall at a university. He was partially supported by this project and involved research work related to this project.

[31] Butenko, S., Ursulenko, O.: On minimum connected donimating set problem in unit-ball graphs. Elsevier Science, Amsterdam (2007)

- CLOSE

1) To improve the theoretical bound between the size of maximal independent set (MIS) and the size of minimum connected dominating set (MCDS) in unit disk graph.

Firstly, with the help of Voronoi division, we divide the plane into several convex polygons and calculate the area for each polygon under different situations. Then, we get a upper bound mis(G)≤ 3.453mcds(G)+4.839. Next, we use the Euler's Formula to modify the bound and get the following solution. If there are no holes in the area constructed by the MCDS, then mis(G) ≤ 3.399mcds(G) + 4.874. Actually, in the real world there may exist some place where the wireless signal cannot reach, and some holes in the area constructed by the MCDS. Final, we discuss the condition with holes and obtain

mis(G) ≤ 3.399 mcds(G) + 0.0790k + 4.874.

where k is the number of the holes.

2) To study the minimum connected dominating set in 3-dimensional wireless network (unit ball graph). Firstly, Butenko and Ursulenko[1] showed that the ratio between the size of the MIS and the size of MCDS can be bounded by 11opt+1, where the opt represents the size of MCDS. Based on this solution, using the greedy algorithm to interconnect the MIS, we obtain a new approximation algorithm with better approximation ratio:

Annual Report: 0829993

Page 3 of 5

|output|≤(13 + ln 10)opt + 1.

Then, in order to improve the upper bound for the size of an MIS in a UBG, we consider how many independent nodes can be contained in the union of two adjacent unit balls

We notice that this problem is closely related to the famous Gregory-Newton Problem concerning with kissing number. By transforming our problem to a geometric one dealing with a graph embedded on the surface and using the Euler's formula and plenty amount of calculus, we show that there can be at most 22 independent nodes inside two adjacent unit balls. Based on the solution, we improve the upper bound from 11opt + 1 to 10.917opt + 1.083. Final, we present a new algorithm to construct CDSs in UBGs, in which we connect them using a simple but very powerful greedy strategy. In our comprehensive analysis, we show that performance ratio is

|output|≤14.937opt+ 1.083.

3) To study the d-hop connected dominating set in unit disk graph (UDG). Firstly, we consider a special case when d=2. Under this case, the first step is to give a theoretical bounder for the size of 2-maximal independent set (2-MIS) and the size of 2-minimum connected dominating set (2-MCDS). The main method is using geometric method and Voronoi division, The result is 2-mis(G)≤ 5.807opt+17.152. The second step is to interconnect the 2-MIS using the spanning tree method and we obtain the approximation algorithm for the 2-MCDS with the approximation ratio:

|output|≤17.421opt + 51.456.

Then, we generalized the algorithm from 2-hop to d-hop and get the following solutions:

d-mis(G)≤ (0.335 r2 + 1.169 r)opt + (3.338 r2 -1.169 r) and

|output|≤ (0.335 r3 + 1.337 r2 + 0.585 r) opt + (3.338 r3 + 0.5 r2- 0.585 r), where r=d+0.5.

We have the following findings in research activities described as above:

(paper 16) This paper considers the problem of computing the optimal trajectories of multiple mobile elements (e.g. robots, vehicles, etc.) to minimize data collection latency in wireless sensor networks (WSNs). By relying on slightly different assumption, we define two interesting problems, the k-traveling salesperson problem with neighborhood (k-TSPN) and the k-rooted path cover problem with neighborhood (k-PCPN). Since both problems are NP-hard, we propose constant factor approximation algorithms for them. Our simulation results indicate our algorithms outperform their alternatives.

(paper 17) Wireless data broadcast is an efficient technique of disseminating data simultaneously to a large number of mobile clients. In many information services, the users may query multiple data items at a time. In this paper, we study the data retrieval scheduling problem from the client's point of view. We formally define the Largest Number Data Retrieval (LNDR) problem with the objective of downloading the largest number of requested data items in a given time duration, and the Minimum Cost Data Retrieval (MCDR) problem which aims at downloading a set of data items with the minimum energy consumption. When the time needed for channel switching can be ignored, a Maximum Matching optimal algorithm is exhibited for LNDR which requires only polynomial time; when the switching time cannot be neglected, LNDR is proven to be NP-hard and a greedy algorithm with constant approximation ratio is developed. We also prove that the MCDR problem is NP-hard to be approximated within to any nontrivial factor and a parameterized heuristic is devised to solve MCDR non-optimally.

(paper 18) Due to more and more customers keen on mobile services, we may face the mobile network congestion problem. Therefore, it is necessary to develop new data retrieval method to provide users with reliable and timely access to the data scourers. In this paper, we study the scheduling problem for retrieving data from multi-channel data broadcast environments. In general conditions, the most important two issues for queries in mobile computing systems are the energy cost and the query response time. In order to improve the query efficiency, we develop a randomized algebraic algorithm that takes both energy cost and access time into consideration to schedule the data retrieval process in multi-channel environments. It can be used in almost any broadcast environment, in which the data access frequencies, data sizes, and channel bandwidths can all be non-uniform.

(paper 19) Wireless data broadcast is an efficient way of disseminating data to users in the mobile computing environments. From the server's point of view, how to place the data items on channels is a crucial issue, with the objective of minimizing the average access time and tuning time. Similarly, how to schedule the data retrieval process for a given request at the client side such that all the requested items can be downloaded in a short time is also an important problem. In this paper we investigate the multi-item data retrieval scheduling in the push-based multi-channel broadcast environments. We prove the decision version of this problem is $\mathcal{NP}$-complete, and we devise an algebraic algorithm to search for the best solution. We also develop a heuristic that can employ the algebraic algorithm to download a large number of items efficiently. When there is no replicated item in a broadcast cycle, we show that an optimal retrieval schedule can be obtained in polynomial time. The performances of proposed algorithms are analyzed theoretically and evaluated through simulation. The experimental results show that our algorithms can significantly reduce the access time for multi-item requests.

(paper 20) In the minimum weighted dominating set problem (MWDS), we are given a unit disk graph with non-negative weight on each vertex. The MWDS seeks a subset of the vertices of the graph with minimum total weight such that each vertex of the graph is either in the subset or adjacent to some nodes in the subset. A weight function is called smooth, if the ratio of the weights of any two adjacent nodes is upper bounded by a constant. MWDS is known to be NP-hard. In this paper, we give the first polynomial time approximation scheme (PTAS) for MWDS with smooth weights on unit disk graphs, which achieves a (1+ε)-approximation for MWDS, for any ε>0.

(paper 21) When a large amount of sensors are randomly deployed into a field, how can we make a sleep/activate schedule for sensors to maximize the lifetime of target coverage in the field? This is a well-known problem, called Maximum Lifetime Coverage Problem (MLCP), which has been studied extensively in the literature. It is a long-standing open problem whether MLCP has a polynomial-time constant-approximation. The best-known approximation algorithm has performance ratio 1 + ln n where n is the number of sensors in the network, which was given by Berman et. al [1]. In their work, MLCP is reduced to Minimum Weight Sensor Coverage Problem (MWSCP) which is to find the minimum total weight of sensors to cover a given area or a given set of targets with a given set of weighted sensors. In this paper, we present a polynomial-time (4 + ∈)-approximation algorithm for MWSCP and hence we obtain a polynomial-time (4 + ξ)-approximation algorithm for MLCP, where ∈ > 0, ξ > 0.

(paper 22) A sensor with two active phrases means that active mode has two phases, the full-active phase and the semi-active phase, which require different energy consumptions. A full-active sensor can sense data packets, transmit, receive, and relay the data packets.

A semi-active sensor cannot sense data packets, but it can transmit, receive, and relay data packets. Given a set of targets and a set of sensors with two active phrases, find a sleep/active schedule of sensors to maximize the time period during which active sensors form a connected coverage set. In this paper, this problem is showed to have polynomial-time constant-approximations when all targets and sensors lie in the Euclidean plane and all sensors have the same sensing radius and the same communication radius which is at least twice of the sensing radius.

- CLOSE

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. This course is covering various research issues focusing the design and analysis of algorithms for optimization problems that occur in wireless networking environments. We have been continuously offering this course in Fall 2008, Fall 2009, Fall 2011, and Fall 2012.

- CLOSE

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, 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, 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.

- CLOSE

• 1. Algorithms for connected set cover problem and fault-tolerant connected set cover problem
  
  2. Construction of Strongly Connected Dominating Sets in Asymmetric Multihop Wireless Networks
  
  3. A Better Approximation Algorithm for Computing Connected Dominating Sets in Unit Ball Graphs
  
  4. Three Approximation Algorithms for Energy-Efficient Query Dissemination in Sensor Database System
  
  5. A New Constant Factor Approximation for Computing 3-Connected m-Dominating Sets in Homogeneous Wireless Networks
  
  6. Construction of Virtual Backbone with Multiple Factors Constraints in Wireless Ad-hoc Network
  
  7. Distributed Construction of Connected Dominating Sets with Minimum Routing Cost in Wireless Networks
  
  8. Construction of directional virtual backbones with minimum routing cost in wireless Networks
  
  9. Constant approximation for virtual backbone construction with Guaranteed Routing Cost in Wireless Sensor Networks
  
  10. New approximations for minimum-weighted dominating sets and minimum-weighted connected dominating sets on unit disk graphs
  
  11. Efficient Virtual Backbone Construction with Routing Cost Constraint in Wireless Networks Using Directional Antennas
  
  12. Efficient Algorithms for Topology Control Problem with Routing Cost Constraints in Wireless Networks
  
  13. Constant-approximation for target coverage in wireless sensor networks
  
  14. A Novel Hash-Based Streaming Scheme for Energy Efficient Full-Text Search in Wireless Data Broadcast
  
  15. Energy-Efficient Tree-Based Indexing Schemes for Information Retrieval in Wireless Data Broadcast
  
  16. Minimizing Data Collection Latency in Wireless Sensor Network with Multiple Mobile Elements
  
  17. Efficient Data Retrieval Scheduling for Multi-Channel Wireless Data Broadcast
  
  18. Algebraic Algorithm for Scheduling Data Retrieval in Multi-channel Wireless Data Broadcast Environments
  
  19. Optimal Data Retrieval Scheduling in the Multi-Channel Wireless Broadcast Environments
  
  20. A PTAS for the minimum weighted dominating set problem with smooth weights on unit disk graphs
  
  21. Constant-approximation for target coverage problem in wireless sensor networks
  
  22. Maximum Lifetime Connected Coverage with Two Active-Phase Sensors
  
  23. A Better Approximation Algorithm for Computing Connected Dominating Sets in Unit Ball Graphs
  
  24. Max-min weight balanced connected partition
  
  25. Algebraic data retrieval algorithms for multi-channel wireless data broadcast
  
  26. On Construction of Quality Fault-Tolerant Virtual Backbone in Wireless Networks
  
  27. CDS-Based Virtual Backbone Construction with Guaranteed Routing Cost in Wireless Sensor Networks
  
  28. New Approximation for Maximum Lifetime Coverage
  
  29. Approximations for Minimum Connected Sensor Cover
  
  30. CSI: Charged System Influence Model for Human Behavior Prediction
  
  31. Influence and Profit: Two Sides of the Coin
  
  32. Smart Print: A Cloud Print System for Office
  
  33. Minimizing Makespan and Total Completion Time in MapReduce-like Systems
  
  33. An Approximation Algorithm for Client Assignment in Client/Server Systems
  
  

- CLOSE