Constant Approximation for the Lifetime Scheduling Problem of p-Percent Coverage

References

• Bar-Yehuda R (2001) Using homogeneous weights for approximating the partial cover problem. J. Algorithms 39(2):137–144.Crossref, Google Scholar
• Berman P, Calinescu G, Shah C, Zelikovsky A (2005) Efficient energy management in sensor networks. Pan Y, Xiao Y, eds. Ad Hoc and Sensor Networks, Wireless Networks and Mobile Computing, vol. 2 (Nova Science Publishers, Hauppauge, NY).Google Scholar
• Cardei M, Thai MT, Li Y, Wu W (2005) Energy-efficient target coverage in wireless sensor networks. Makki K, Knightly E, eds. Proc. 24th Annual Joint Conf. IEEE Comput. Comm. Soc., vol. 4 (IEEE, Piscataway, NJ), 1976–1984.Google Scholar
• Dai D, Yu C (2009) A (5+ε)-approximation algorithm for minimum weighted dominating set in unit disk graph. Theoret. Comput. Sci. 410(8–10):756–765.Crossref, Google Scholar
• Du D, Ko K, Hu X (2012) Design and Analysis of Approximation Algorithms (Springer-Verlag, New York).Crossref, Google Scholar
• Du H, Pardalos PM, Wu W, Wu L (2013) Maximum lifetime connected coverage with two active-phase sensors. J. Global Optim. 56(2):559–568.Crossref, Google Scholar
• Erlebach T, Mihalák M (2009) A (4+ε)-approximation for the minimum-weight dominating set problem in unit disk graphs. Bampis E, Jansen K, eds. Proc. 7th Internat. Conf. Approximation Online Algorithms (Springer-Verlag, Berlin), 135–146.Google Scholar
• Gandhi R, Khuller S, Srinivasan A (2004) Approximation algorithms for partial covering problems. J. Algorithms 53(1):55–84.Crossref, Google Scholar
• Gao S, Wang X, Li Y (2008a) p-Percent coverage schedule in wireless sensor networks. Makki K (co-chair), Makki S (co-chair), eds. Proc. 17th Internat. Conf. Comput. Comm. Networks (IEEE, Piscataway, NJ), 1–6.Google Scholar
• Gao X, Huang Y, Zhao Z, Wu W (2008b) (6+ε)-Approximation for minimum weight dominating set in unit disk graphs. Hu X, Wang J, eds. Proc. 14th Annual Internat. Conf. Comput. Combin. (Springer, Berlin), 551–557.Google Scholar
• Garg N, Könemann J (1998) Faster and simpler algorithms for multicommodity flow and other fractional packing problems. Proc. 39th Annual Sympos. Foundations Comput. Sci. (IEEE Computer Society, Los Alamitos, CA), 300–309.Google Scholar
• Huang Y, Gao X, Zhao Z, Wu W (2009) A better constant-factor approximation for weighted dominating set in unit disk graph. J. Combin. Optim. 18(2):179–194.Crossref, Google Scholar
• Kearns M, Ortiz L (2003) Algorithms for interdependent security games. Thrun S, Saul L, Schölkopf B, eds. Advances in Neural Information Processing Systems, vol. 16 (MIT Press, Cambridge, MA), 288–297.Google Scholar
• Khalil N, Abid MR, Benhaddou D, Gerndt M (2014) Wireless sensors networks for Internet of Things. 2014 IEEE 9th Internat. Conf. Intelligent Sensors, Sensor Networks Inform. Processing (IEEE, Piscataway, NJ), 1–6.Google Scholar
• Könemann J, Parekh O, Segev D (2011) A unified approach to approximating partial covering problems. Algorithmica 59(4):489–509.Crossref, Google Scholar
• Li Y, Ai C, Cai Z, Beyah R (2011a) Sensor scheduling for p-percent coverage in wireless sensor networks. Cluster Comput. 14(1):27–40.Crossref, Google Scholar
• Li Y, Vu C, Ai C, Chen G, Zhao Y (2011b) Transforming complete coverage algorithms to partial coverage algorithms for wireless sensor networks. IEEE Trans. Parallel Distributed Systems 22(4):695–703.Crossref, Google Scholar
• Liu C, Cao G (2012) Distributed critical location coverage in wireless sensor networks with lifetime constraint. 2012 Proc. IEEE INFOCOM (IEEE, Piscataway, NJ), 1314–1322.Google Scholar
• Liu C, Du H (2021) t, K-Sweep coverage with mobile sensor nodes in wireless sensor networks. IEEE Internet Things J. 8(18):13888–13899.Crossref, Google Scholar
• Lu Z, Li WW, Pan M (2015) Maximum lifetime scheduling for target coverage and data collection in wireless sensor networks. IEEE Trans. Vehicular Tech. 64(2):714–727.Crossref, Google Scholar
• Meguerdichian S, Koushanfar F, Potkonjak M, Srivastava M (2001) Coverage problems in wireless ad-hoc sensor networks. Proc. 20th Annual Joint Conf. IEEE Comput. Comm. Soc., vol. 3 (IEEE, Piscataway, NJ), 1380–1387.Google Scholar
• Mukhopadhyay SC, Tyagi SKS, Suryadevara NK, Piuri V, Scotti F, Zeadally S (2021) Artificial intelligence-based sensors for next generation IoT applications: A review. IEEE Sensors J. 21(22):24920–24932.Crossref, Google Scholar
• Navulur S, Sastry ASCS, Prasad MNG (2017) Agricultural management through wireless sensors and Internet of Things. Internat. J. Electr. Comput. Engrg. 7(6):3492–3499.Google Scholar
• Ran Y, Huang X, Zhang Z, Du D (2021a) Approximation algorithm for minimum power partial multi-coverage in wireless sensor networks. J. Global Optim. 80(3):661–677.Crossref, Google Scholar
• Ran Y, Zhang Z, Ko K, Liang J (2016) An approximation algorithm for maximum weight budgeted connected set cover. J. Combin. Optim. 31(4):1505–1517.Crossref, Google Scholar
• Ran Y, Zhang Z, Tang S, Du D (2021b) Breaking the rmax barrier: Enhanced approximation algorithms for partial set multicover problem. INFORMS J. Comput. 33(2):774–784.Abstract, Google Scholar
• Ren S, Li Q, Wang H, Chen X, Zhang X (2007) Design and analysis of sensing scheduling algorithms under partial coverage for object detection in sensor networks. IEEE Trans. Parallel Distributed Systems 18(3):334–350.Crossref, Google Scholar
• Rossi A, Singh A, Sevaux M (2011) Column generation algorithm for sensor coverage scheduling under bandwidth constraints. Networks 60(3):141–154.Crossref, Google Scholar
• Shi Y, Ran Y, Zhang Z, Willson J, Tong G, Du D-Z (2019) Approximation algorithm for the partial set multi-cover problem. J. Global Optim. 75(4):1133–1146.Crossref, Google Scholar
• Slavík P (1997) Improved performance of the greedy algorithm for partial cover. Inform. Processing Lett. 64(5):251–254.Crossref, Google Scholar
• Vu C, Chen G, Zhao Y, Li Y (2009) A universal framework for partial coverage in wireless sensor networks. Proc. IEEE 28th Internat. Performance Comput. Comm. Conf. (IEEE, Piscataway, NJ), 1–8.Google Scholar
• Wang L, Yang J, Lin Y, Lin W (2014) Keeping desired QoS by a partial coverage algorithm for cluster-based wireless sensor networks. J. Networks 9(12):3221–3229.Crossref, Google Scholar
• Willson J, Wu W, Wu L, Ding L, Du D (2014) New approximations for maximum lifetime coverage. Optimization 63(6):839–847.Crossref, Google Scholar
• Wu W, Zhang Z, Lee W, Du D (2020) Optimal Coverage in Wireless Sensor Networks (Springer, Cham, Switzerland).Crossref, Google Scholar
• Wu Y, Ai C, Gao S, Li Y (2008) p-Percent coverage in wireless sensor networks. Li Y, Huynh DT, Das SK, Du D-Z, eds. Proc. 3rd Internat. Conf. Wireless Algorithms Systems Appl. (Springer, Berlin), 200–211.Google Scholar
• Zhang Z, Zhou J, Tang S, Huang X, Du D (2018) Computing minimum k-connected m-fold dominating set in general graphs. INFORMS J. Comput. 30(2):217–224.Link, Google Scholar
• Zhang Z, Willson J, Lu Z, Wu W, Zhu X, Du D-Z (2016) Approximating maximum lifetime k-coverage through minimizing weighted k-cover in homogeneous wireless sensor networks. IEEE/ACM Trans. Networking 24(6):3620–3633.Crossref, Google Scholar
• Zhou J, Zhang Z, Tang S, Huang X, Du D (2018) Breaking the o(lnn) barrier: An enhanced approximation algorithm for fault-tolerant minimum weight connected dominating set. INFORMS J. Comput. 30(2):225–235.Link, Google Scholar
• Zhu X, Chen G, Tang S, Wu X, Chen B (2016) Fast approximation algorithm for maximum lifetime aggregation trees in wireless sensor networks. INFORMS J. Comput. 28(3):417–431.Link, Google Scholar
• Zou F, Wang Y, Xu X, Li X, Du H, Wan P, Wu W (2011) New approximations for minimum-weighted dominating sets and minimum-weighted connected dominating sets on unit disk graphs. Theoret. Comput. Sci. 412(3):198–208.Crossref, Google Scholar