隨著科技的演進，無線通訊技術的發展已漸趨成熟，諸如手機、無線網路、地域監控等各個領域的應用也不斷推陳出新，讓我們的生活更加便利。在規劃無線通訊系統時，訊號的發送距離與所需資源，一直是人們關注的焦點，因此如何以較低的成本來覆蓋目標範圍，成了許多專家學者探討的議題。然而目前的相關研究，大多只針對單一訊號所涵蓋的區域進行探討，如果在通訊的過程中，有任何天線發生故障，造成特定區域的訊號無法正常發送，將有導致通訊中斷的可能，為了避免類似的情況發生，有學者提出在固定半徑下尋找兩點間二層覆蓋路徑的天線發送範圍規劃演算法。
然而在現實生活中，天線的發送範圍往往不只一種，為了解決可變半徑下的規劃問題，本論文提出了三種方法，分別為二層覆蓋區延伸規劃法TASP(2-Covered Area Stretching Planning)、半徑縮減規劃法RSP(Radii Shrinking Planning)以及圖形轉換規劃法(Graph Transformation Planning)。其中TASP是利用延伸的概念，將二層覆蓋區域由A點向B點擴展；RSP是先規劃最大半徑，再找出可以縮減的目標；GTP則是利用點集合與邊集合來記錄各天線的交集情況，再利用回溯(Backtracking)的技巧來搜尋可能的規劃方式。實驗結果顯示，規劃發送範圍所須的時間以RSP最短，TASP次之，GTP最長，總能量消耗(Power Consumption)則恰好相反，由小到大依序為GTP、TASP與RSP。

Since wireless communication technologies are getting better and better, a lot of applications such as mobile phone, wireless network, and regional surveillance are being developed in the last decade. As a consequence, our life has become much more convenient than ever before.
While planning a wireless communication system, the transmission ranges and resources are the most important things that we have to consider. How to cover the objectives with lower costs has become one of the most popular research issues consequently. However, most of the researches about covering problems only focus on single covering area. If any antenna fails, our communication might be interrupted. In order to avoid this situation, a scholar proposed an algorithm that can find 2-covered paths by a set of antennas with minimum power transmission range.
In real life situation, the transmission range of the antennas might be variable. For this reason, we propose three algorithms to solve this problem, namely TASP (2-covered area stretching planning), RSP (radii shrinking planning), and GTP (graph transformation planning) separately. TASP stretches the 2-covered area from the source point to the destination point. RSP plans each antenna using the biggest radius and shrinks the radii one by one. GTP uses nodes and edges to represent the intersection relations between antennas. Then GTP uses the backtracking technique to search for possible solutions.
Experimental results show that, from power consumption’s point of view, the solution of GTP is the best, TASP is the second, and RSP is the worst. Relatively, the execution time of RSP is the lowest and GTP requires a large amount of time to finish its planning algorithm.

[1]M. Abellanas, A. Bajuelos, G. Hernández, I. Matos, “Good illumination with limited visibility”, Proc. of the International Conference of Numerical Analysis and Applied Mathematics, pp. 35-38, 2005.
[2]M. Abellanas, A. Bajuelos, G. Hernández, I. Matos, B. Palop, “Minimum illumination range voronoi diagrams”, Proc. of the 2nd International Symposium on Voronoi Diagrams in Science and Engineering, pp. 231-238, 2005.
[3]M. Abellanas, A. L. Bajuelos, I. Matos, “2-Covered paths by a set of antennas with minimum power transmission range”, Information Processing Letters, Volume 109, Issue 14, pp. 768-773, 2009.
[4]M. Abellanas, A. Bajuelos, I. Matos, “Some problems related to good illumination” Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 4705 LNCS (PART 1), pp. 1-14, 2007.
[5]M. Abellanas, G. Hernandez, “Optimizacion de Rutas de Evacuacion”, in: Proceedings of the XII Encuentros de Geometria Computacional, pp. 273-280, 2007.
[6]A. Agnetis, E. Grande, P. B. Mirchandani, A. Pacifici, “Covering a line segment with variable radius discs”, Computers and Operations Research, 36 (5), pp. 1423-1436, 2009.
[7]G. Alexandris, I. Giannikos, “A new model for maximal coverage exploiting GIS capabilities”, European Journal of Operational Research, 202, pp. 328-338, 2010.
[8]P. Belleville, P. Bose, J. Czyzowicz, J. Urrutia, J. Zaks, “K-Guarding polygons on the plane”, in: Proceedings of the 6th Canadian Conference in Computational Geometry, pp. 381-386, 1994.
[9]J. Chen, X. Koutsoukos, “Survey on coverage problems in wireless ad hoc sensor networks”, IEEE SouthEastCon, 2007.
[10]L. Chen, D. Yuan, “Solving a minimum-power covering problem with overlap constraint for cellular network design”, European Journal of Operational Research, 203, pp. 714-723, 2010.
[11]E. W. Dijkstra, “A note on two problems in connexion with graphs”, Numerische Mathematik 1, pp. 269-271, 1959.
[12]M. Franceschetti, M. Cook, J. Bruck, “A geometric theorem for approximate disk covering algorithms”, Technical report, California Institute of Technology, 2001.
[13]M. L. Fredman, R. E. Tarjan, “Fibonacci heaps and their uses in improved network optimization algorithms”, Journal of the ACM, 34(3), pp. 596-615, 1987.
[14]F. Hoffmann, M. Kaufmann, K. Kriegel, “The art gallery theorem for polygons with holes”, In: 32nd Annual symposium on foundations of computer science, pp. 39-48, 1991.
[15]E. Horowitz, S. Sahni, S. Anderson-Freed, Fundamentals of data structures in C, W. H. Freeman, pp. 171-177, 1993.
[16]B. Kau˘ci˘c, B. Žalikm, “K-Guarding of polyhedral terrain”, International Journal Geographical Information Science, pp. 709-718, 2004.
[17]D. T. Lee, “On k-nearest neighbor Voronoi diagrams in the plane”, IEEE Transactions on Computers, 31 (6), pp. 478–487, 1982.
[18]J. O’Rourke, Art gallery theorems and algorithms, Oxford: Oxford University Press, 1987.
[19]J. Smith, W. Evans, “Triangle guarding”, Proc. of the 15th Canadian Conference on Computational Geometry, pp. 76-80, 2003.
[20]C. D. Tóth, “Guarding disjoint triangles and claws in the plane”, Computational Geometry, 25, pp. 51–65, 2003.
[21]J. Urrutia, Art gallery and illumination problems, Handbook of Computational Geometry, 2004.
[22]B. Xiao, Q. Zhuge, Y. Zhang, Edwin H. M. Sha, “Algorithms for disk covering problems with the most points”, In: Proceedings of the IASTED international conference on parallel and distributed computing and systems (IASTED PDCS), pp. 541–546, 2003.
[23]M. Loy、I. Sylla，「ISM頻帶與短距裝置天線基本原理：第1篇」，電子工程專輯，2008。