覆蓋問題一直以來都是無線感測網路的主要研究議題之一，並隨著無線感測網路的發展，各式的覆蓋問題也相繼被提出。在過去的研究中，許多研究都將感測網路的建置環境視為平面，例如無線充電裝置的路徑規劃，基地台的選址問題，而這兩個問題也是本文的研究範疇。除了將感測網路的建置環境視為平面之外，也有研究考慮地表起伏的地形模型，其中 1.5 維地形看守問題是一個許多研究探討的相關問題之一。因此，本文對於平面模型和地型模型的覆蓋問題，分別探討無線充電裝置的路徑規劃、行動網路的基地台選址問題和 1.5 維地形看守問題。無線感測網路運用無線充電技術，以及移動無線充電裝置，使得網路壽命得以延長。在規劃無線充電裝置的移動路線時，我們考慮設置最少的充電地點和最小化總充電時間。首先，我們提出一個基於最佳解下限的佈署策略，並分析規劃結果與最少的充電地點數量和最少總充電時間的最大差距。此外，我們還提出一個 2 階段的設置策略。在 2 階段的設置策略中，我們先以最少停駐點數量為目標設置充電停駐點，再設置每個充電停駐點的充電時間。過去已有研究探討相同的最少充電停駐點問題，並提出以最小分團為基礎的停駐點設置方式。在模擬實驗中，當感測器分佈較為緊密時，我們的佈署策略能僅用以最小分團為基礎的設置方式的 60% 之停駐點數量以及停滯時間，替全部的感測器完成充電。
在以平面為感測網路建置環境研究中，我們也探討行動感測網路的基地台佈署問題。由於行動使用者的移動路線通常是規律性或可預測性，甚至是沿路而行，因此我們以折線表示行動使用者的移動軌跡。我們根據移動軌跡與基地台的通訊範圍，提出最少單位圓覆蓋線段問題 (Minimum Geometric Disk Cover for Line Segments, MGDCL)，藉此設立最少數量的基地台，並使得行動使用者和基地台之間能維持通訊。在本文中，我們證明 MGDCL 為 NP-hard 並提出一個 4 倍近似演算法。
在 1.5 維地形看守問題的研究中，我們我們對於雙側看守連續地形問題(Continuous Terrain Guarding with Two-sided Guards, CTG2G) 和正交地形看守問題提出線性時間演算法。CTG2G 問題的目的在於設置最少的守衛，使得 1.5 維地形上任一點 p 皆會被兩個不同的守衛看守，且這兩守衛的位置分別在 p 的左側和右側。對 CTG2G 而言，我們的演算法能在線性時間內找出最佳的守衛集合。另一方面，我們對於 1.5 維正交地形看守問題，提出一個線性時間的 2 倍近似演算法。在 1.5 維正交地看守問題的研究中，我們提出的演算法除了有最佳的時間複雜度之外，近似係數也是目前最低的。

Coverage is a major research topic in wireless sensor networks. With the continuous development of wireless sensor network technology, many coverage issues associated with wireless sensor networks have been identified. Previously, the construction environment of a sensor network has been regarded as a planar area in several studies, such as the planning of charging path of wireless chargers and the determination of location for a base station. These two issues belong to the research field explored in this study. In addition to treating the construction environment of the sensor network as a planar area, other studies have investigated the coverage problem of a sensor, where the detection range is affected by topographic relief. In particular, the 1.5-dimensional (1.5D) terrain guarding problem is a relevant one that has been investigated significantly. Therefore, in this thesis, we focus on the coverage problems of a planar model and terrain model. Specifically, we analyze the path planning of a wireless charging device, the site selection of base station for a mobile network, and the 1.5D terrain guarding problem. Charging schemes utilizing mobile wireless chargers can be applied to prolong the lifespan of a wireless sensor network. In considering charging schemes with mobile chargers, we aim to minimize both the number of charging locations and the total required charging time. The first plan was proposed based on the lower bound of the optimal solution. It was guaranteed that the total number of charging stops and the total charging time would not exceed seven times the best planning results. The second one is a two-phase plan, where the number of charging positions is first minimized, then minimum charging times are assigned to every position according to the charging requirements of the nearby sensors. Empirical studies show that compared with other MCP-based (minimal clique partition) methods, the proposed charging plan may save up to 60% in terms of both the number of charging positions and the total required charging time.
Inadditiontothechargingproblemfor2Dwirelesssensornetwork, we study the base station deployment problem with mobile user traces by finding a minimum disk cover. Since user traces are often simple, predictable or pre-determined, the moving traces are considered as polylines. We define the minimum geometric disk cover for line segments problem (MGDCL) and prove that the MGDCL problem is NP-hard. We develop a 4- approximation algorithm for MGDCL. Therefore, a satisfactory base station deployment plan can be constructed.
In the study of 1.5D terrain guarding problem, we consider the continuous terrain guarding with-side guards (CTG2G). To our knowledge, this is the first work on this problem. we provide an optimal algorithm determining a guard set with minimum cardinality that completely two-sided guards the terrain. Besides, we consider the problem of guarding the vertices of 1.5D orthogonal terrain using the vertex guards. The faster published algorithm, which uses sweep line algorithm and heap operations and runs in O(nlogm) time, where n and m are the sizes of input and output, respectively. In this work, we propose two linear time algorithms that are based on left-guarding algorithm.

[1] L. Kong, M. Zhao, X.-Y. Liu, J. Lu, Y. Liu, and M.-Y. Wu, “Surface coverage in sensor networks,” IEEE Transactions on Parallel and Distributed Systems, vol. 25, no. 1, pp. 234–243, 2014.
[2] M. Rebai, M. Berre, H. Snoussi, F. Hnaien, and L. Khoukhi, “Sensor deployment optimization methods to achieve both coverage and connectivity in wireless sensor networks,” Computers & Operations Research, vol. 59, pp. 11–21, 2015.
[3] S. He, D.-H. Shin, J. Zhang, J. Chen, and Y. Sun, “Full-view area coverage in camera sensor networks: Dimension reduction and near-optimal solutions,” IEEE Transactions on Vehicular Technology, vol. 65, no. 9, pp. 7448–7461, 2015.
[4] O. M. Alia and A. Al-Ajouri, “Maximizing wireless sensor network coverage with minimum cost using harmony search algorithm,” IEEE Sensors Journal, vol. 17, no. 3, pp. 882–896, 2016.
[5] H. Kim and S.-W. Han, “An efficient sensor deployment scheme for large-scale wireless sensor networks,” IEEE Communications Letters, vol. 19, no. 1, pp. 98–101, 2014.
[6] B. Xu, Y. Zhu, D. Li, D. Kim, and W. Wu, “Minimum (k, ω)-angle barrier coverage in wireless camera sensor networks,” International Journal of Sensor Networks, vol. 21, no. 3, pp. 179–188, 2016.
[7] C.-F. Cheng and K.-T. Tsai, “Distributed barrier coverage in wireless visual sensor networks with β-QoM,” IEEE Sensors Journal, vol. 12, no. 6, pp. 3408–3416, 2012.
[8] H. Ma, M. Yang, D. Li, Y. Hong, and W. Chen, “Minimum camera barrier coverage in wireless camera sensor networks,” in IEEE Conference on Computer Communications, pp. 217–225, 2012.
[9] C.-Y. Chang, C.-Y. Hsiao, and C.-T. Chang, “The k-barrier coverage mechanism in wireless visual sensor networks,” IEEE Wireless Communications and Networking Conference, pp. 2318–2322, 2012.
[10] G. Chen and S. Cui, “Relay node placement in two-tiered wireless sensor networks with base stations,” Journal of Combinatorial Optimization, vol. 26, no. 3, pp. 499–508, 2013.
[11] Ş. Kimençe and I. Bekmezci, “Weighted relay node placement for wireless sensor network connectivity,” Wireless networks, vol. 20, no. 4, pp. 553–562, 2014.
[12] J. Huang, Y. Meng, X. Gong, Y. Liu, and Q. Duan, “A novel deployment scheme for green internet of things,” IEEE Internet of Things Journal, vol. 1, no. 2, pp. 196–205, 2014.
[13] A. Srinivas, G. Zussman, and E. Modiano, “Construction and maintenance of wireless mobile backbone networks,” IEEE/ACM Transactions on Networking, vol. 17, no. 1, pp. 239–252, 2009.
[14] H. Cheng, X. Fei, A. Boukerche, and M. Almulla, “GeoCover: An efficient sparse coverage protocol for rsu deployment over urban vanets,” Ad Hoc Networks, vol. 24, no. 6, pp. 85–102, 2015.
[15] Y.-Y. Shih, W.-H. Chung, P.-C. Hsiu, and A.-C. Pang, “A mobility-aware node deployment and tree construction framework for zigbee wireless networks,” IEEE Transactions on Vehicular Technology, vol. 62, no. 6, pp. 2763–2779, 2013.
[16] W. Guo, X. Huang, and Y. Liu, “Dynamic relay deployment for disaster area wireless networks,” Wireless Communications & Mobile Computing - Wireless Technologies Advances for Emergency and Rural Communications, vol. 10, no. 9, pp. 1238–1252, 2010.
[17] T. Zou, W. Xu, W. Liang, J. Peng, Y. Cai, and T. Wang, “Improving charging capacity for wireless sensor networks by deploying one mobile vehicle with multiple removable chargers,” Ad Hoc Networks, vol. 63, pp. 79–90, 2017.
[18] L. Fu, L. He, P. Cheng, Y. Gu, J. Pan, and J. Chen, “ESync:energy synchronized mobile charging in rechargeable wireless sensor networks,” IEEE Transactions on Vehicular Technology, vol. 65, no. 9, pp. 7415–7431, 2016.
[19] Y. Shu, K. G. Shin, J. Chen, and Y. Sun, “Joint energy replenishment and operation scheduling in wireless rechargeable sensor networks,” IEEE Transactions on Industrial Informatics, vol. 13, no. 1, pp. 125–134, 2017.
[20] X. Rao, P. Yang, and Y. Yan, “Revisiting practical energy harvesting wireless sensor network with optimal scheduling,” in 12th International Conference on Mobile AdHoc and Sensor Networks, pp. 58–62, 2017.
[21] X. Rao, P. Yang, Y. Yan, H. Zhou, and X. Wu, “Optimal recharging with practical considerations in wireless rechargeable sensor network,” IEEE Access, pp. 4401–4409, 2017.
[22] J. Suo, Z. Yao, B. Zhang, and C. Li, “Charger mobility scheduling and modeling in wireless rechargeable sensor networks,” in 2016 International Wireless Communications and Mobile Computing Conference, pp. 953–957, 2016.
[23] L. Fu, P. Cheng, Y. Gu, J. Chen, and T. He, “Optimal charging in wireless rechargeable sensor networks,” IEEE Transactions on Vehicular Technology, vol. 65, no. 1, pp. 278–291, 2016.
[24] G. Han, X. Yang, L. Liu, and W. Zhang, “A joint energy replenishment and data collection algorithm in wireless rechargeable sensor networks,” IEEE Internet of Things Journal, vol. 5, no. 4, pp. 2596–2604, 2017.
[25] G. Han, X. Yang, L. Liu, and S. C. . W. Zhang, “A coverage-aware hierarchical charging algorithm in wireless rechargeable sensor networks,” IEEE Network, pp. 1–7, 2018.
[26] L. Khelladi, D. Djenouri, M. Rossi, and N. Badache, “MSR: Minimum-stop recharging scheme for wireless rechargeable sensor networks,” in Proceedings of the 2014 IEEE 11th Internanational Conference on Ubiquitous Intelligence and Computing, pp. 378–383, 2014.
[27] L. Khelladi, D. Djenouri, M. Rossi, and N. Badache, “Efficient on-demand multinode charging techniques for wireless sensor networks,” Computer Communications, vol. 101, pp. 44–56, 2017.
[28] C. Lin, G. Wu, M. S. Obaidat, and C. W. Yu, “Clustering and splitting charging algorithms for large scaled wireless rechargeable sensor networks,” Journal of Systems and Software, vol. 113, pp. 381–394, 2016.
[29] Y. Ma, W. Liang, and W. Xu, “Charging utility maximization in wireless rechargeable sensor networks by charging multiple sensors simultaneously,” IEEE/ ACM Transactions on Networking, vol. 26, no. 4, pp. 1591–1604, 2018.
[30] W. Xu, W. Liang, J. Peng, Y. Liu, and Y. Wang, “Maximizing charging satisfaction of smartphone users via wireless energy transfer,” IEEE Transactions on Mobile Computing, vol. 16, no. 4, pp. 990–1004, 2017.
[31] C. Moraes and D. Har, “Charging distributed sensor nodes exploiting clustering and energy trading,” IEEE Sensors Journal, vol. 17, no. 2, pp. 546–555, 2016.
[32] G. E. Forsythe, M. A. Malcolm, and C. B. Moler, “Computer methods for mathematical computations,” Englewood Cliffs, NJ, USA:Prentice-Hall, 1976.
[33] L. Xie, Y. Shi, Y. T. Hou, W. Lou, H. D. Sherali, and S. F. Midkiff, “On renewable sensor networks with wireless energy transfer: The multi-node case,” in 9th Annual IEEE Communications Society Conference on Sensor, Mesh and Ad Hoc Communications and Networks, pp. 10–18, 2012.
[34] L. Xie, Y. Shi, Y. T. Hou, W. Lou, H. D. Sherali, and S. F. Midkiff, “Multi-node wireless energy charging in sensor networks,” IEEE/ACM Transactions on Networking, vol. 23, no. 2, pp. 437–450, 2014.
[35] D. Zorbas and C. Douligeris, “Computing optimal drone positions to wirelessly recharge iot devices,” in IEEE Conference on Computer Communications Workshops, pp. 628–633, 2018.
[36] Y. Xiong, J. Ma, W. Wang, and D. Tu, “RoadGate: Mobility-centric roadside units deployment for vehicular networks,” International Journal of Distributed Sensor Networks, vol. 9, no. 4, pp. 1–10, 2013.
[37] Z. Shan and Q. Zhu, “Camera location for real-time traffic state estimation in urban road network using big gps data,” Neurocomputing, vol. 169, pp. 134–143, 2015.
[38] C. Bautista-Santiago, J. M. Díaz-Báñez, R. Fabila-Monroy, D. Flores-Peñaloza, D. Lara, and J. Urrutia, “Covering moving points with anchored disks,” European Journal of Operational Research, vol. 216, no. 2, pp. 278–285, 2012.
[39] Z. Liao, J. Wang, S. Zhang, J. Cao, and G. Min, “Minimizing movement for target coverage and network connectivity in mobile sensor networks,” IEEE Transactions on Parallel and Distributed Systems, vol. 26, no. 7, pp. 1971–1983, 2015.
[40] Z. Chen, X. Gao, F. Wu, and G. Chen, “A ptas to minimize mobile sensor movement for target coverage problem,” in 35th Annual IEEE International Conference on Computer Communications, pp. 1–9, IEEE, 2016.
[41] S. Bhattarai, S. Wei, S. Rook, W. Yu, D. Griffith, and N. Golmie, “Optimizing the location deployment of dynamic mobile base stations,” in 2015 International Conference on Computing, Networking and Communications, pp. 579–583, 2015.
[42] H. W. Kuhn, “The hungarian method for the assignment problem,” Naval research logistics quarterly, vol. 2, no. 1-2, pp. 83–97, 1955.
[43] J. King and E. Krohn, “Terrain guarding is np-hard,” SIAM Journal on Computing, vol. 40, no. 5, pp. 1316–1339, 2011.
[44] B. Ben-Moshe, M. J. Katz, and J. S. Mitchell, “A constant-factor approximation algorithm for optimal 1.5 d terrain guarding,” SIAM Journal on Computing, vol. 36, no. 6, pp. 1631–1647, 2007.
[45] J. King, “A 4-approximation algorithm for guarding 1.5-dimensional terrains,” in 7th Latin American Symposium, pp. 629–640, Springer, 2006.
[46] K. Elbassioni, E. Krohn, D. Matijević, J. Mestre, and D. Ševerdija, “Improved approximations for guarding 1.5-dimensional terrains,” Algorithmica, vol. 60, no. 2, pp. 451–463, 2011.
[47] M. Gibson, G. Kanade, E. Krohn, and K. Varadarajan, “An approximation scheme for terrain guarding,” in Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, pp. 140–148, Springer, 2009.
[48] S. Friedrichs, M. Hemmer, and C. Schmidt, “A ptas for the continuous 1.5d terrain guarding problem,” in 26th Canadian Conference on Computational Geometry, pp. 53:1–53:7, 2014.
[49] É. Bonnet and P. Giannopoulos, “Orthogonal terrain guarding is np-complete,” in 34th International Symposium on Computational Geometry, vol. 99, pp. 11:1–11:15, 2018.
[50] M. J. Katz and G. S. Roisman, “On guarding the vertices of rectilinear domains,” Computational Geometry, vol. 39, no. 3, pp. 219–228, 2008.
[51] F. Gavril, “Algorithms for minimum coloring, maximum clique, minimum covering by cliques, and maximum independent set of a chordal graph,” SIAM Journal on Computing, vol. 1, no. 2, pp. 180–187, 1972.
[52] Y. Lyu and A. Üngör, “A fast 2-approximation algorithm for guarding orthogonal terrains,” in 28th Canadian Conference on Computational Geometry, pp. 161–167, 2016.
[53] S. Durocher, P. C. Li, and S. Mehrabi, “Guarding orthogonal terrains,” in 27th Canadian Conference on Computational Geometry, pp. 220–227, 2015.
[54] F. Khodakarami, F. Didehvar, and A. Mohades, “1.5d terrain guarding problem parameterized by guard range,” Theoretical Computer Science, vol. 661, pp. 65–69, 2017.
[55] V. P. Stephan Friedrichs and C. Schmidt., “Altitude terrain guarding and guarding uni-monotone polygons,” in 34th European Workshop on Computational Geometry, pp. 41:1–41:6, 2018.
[56] M. Jin, G. Rong, H. Wu, L. Shuai, and X. Guo, “Optimal surface deployment problem in wireless sensor networks,” in IEEE Conference on Computer Communications, pp. 2345–2353, 2012.
[57] X.-Y. Liu, K.-L. Wub, Y. Zhua, L. Konga, and M.-Y. Wua, “Mobility increases the surface coverage of distributed sensor networks,” Computer Networks, vol. 57, no. 11, pp. 2348–2363, 2013.
[58] F. Li, J. Luo, W. Wang, and Y. He, “Autonomous deployment for load balancing k-surface coverage in sensor networks,” IEEE Transactions on Wireless Communications, vol. 14, no. 1, pp. 279–293, 2015.
[59] S. Eidenbenz, “Approximation algorithms for terrain guarding,” Information Processing Letters, vol. 82, no. 2, pp. 99–105, 2002.
[60] C.-Y. Chang, C.-C. Chen, and C.-C. Liu, “A novel approximation algorithm for minimum geometric disk cover problem with hexagon tessellation,” Advances in Intelligent Systems and Applications-Volume 1, vol. 20, pp. 157–166, 2013.
[61] M. Löffler, M. Saumell, and R. I. Silveira, “A faster algorithm to compute the visibility map of a 1.5d terrain,” in 30th European Workshop on Computational Geometry, pp. 1–4, 2014.