現在，無線通訊以及電力儲存發展已經做出低價位的無線感測網路（Wireless Sensor Networks），在不同的應用上有許多不同的技術分別致力研發當中。目的都是為了在無線感測網路當中，利用感測器(Sensor)低微的計算能力和電力達到較好的應用與降低錯誤率。但實際上感測器的製作成本雖然已經降到很低，但要使用在普及以及大量的應用上，綜合的成本還是相當的高，所以Pan等人[21]提出了無線感測網路的分層架構，由感測器形成多群(Cluster)的感測器組，每一感測器組最少擁有一個應用節點(Application Node)，此應用節點的功能是負責收集感測器所偵測到的訊號以及應用節點與應用節點間溝通和路由(Route)，而所有的應用節點最後再把資料全部傳送到基地工作站(Base-Station)做整體資料統計以及運算配置。如此的分層架構可以使最底層的感測器在大量使用上，成本可以降低，但是相對在應用節點的開發及使用成本就比感測器來的高。本篇論文提出了一套貪婪佈置演算法，可使無線感測網路應用在封閉環境的環境，應用節點的使用個數以及配置的位置都可以達到較佳的效果，平均應用節點使用個數可以降到[(3n-1)/7] (n為簡單多邊形的邊數)以內，且依然保證無線感測網路內部的通訊不中斷。

Recent advances in low-power devices and strong radio transceivers have enabled the rapid development of wireless sensor networks (WSNs) in the last few years. Using WSNs in daily lives has become practical.
In this paper, we consider the problem of deploying network nodes in constrained environments, for example, a building. We suggest to use a two-tiered wireless sensor network structure [21] to position sensors. We devise a greedy positioning algorithm to minimize the number and optimize the location of application nodes (AN) that relay communication between sensors themselves and between sensors and the base station.. The algorithm adds additional application nodes to ensure a connected network. Our simulations show that the algorithm can effectively extend the lifespan of the network, while the number of used application nodes is about half of the proved sufficient number[(3n-1)/7](n is the number of walls in the constrained environment).

[1]A. Aggarwal “The art gallery problem: It’s variations, applications, and algorithmic aspects” Johns Hopkins Univ., Baltimore, MD, 1984.
[2]A.M. Andrew “Another efficient algorithm for convex hulls in two dimensions” Inform. Process. Lett., pages 216-219, 1997.
[3]C. Fabiana, Chiasserini and E. Magli “Energy consumption and image quality in wireless video surveillance networks” Proc. 13th IEEE PIMRC, 2002.
[4]CGAL(Computational Geometry Algorithm Library), http://www.cgal.org/
[5]Conference on Mobile Computing and Networking, pages 286-299, ACM Press, New York, NY, 14-19 September 2003.
[6]D. T. Lee “On Finding the Convex Hull of a Simple Polygon” International Journal of Computer and Information Sciences, Vol. 12, No. 2, pages 87-98, 1983.
[7]D. H. Greene. “The decomposition of polygons into convex parts” In Franco P. Preparata, editor, Computational Geometry, volume 1 of Adv. Comput. Res., pages 235-259, 1983.
[8]E. M. Arkin, J. S.B. Mitchell, and S. Suri, 1992. “Optimal link path queries in a simple polygon” In Proceedings of the Third Annual ACM-SIAM Symposium on Discrete Algorithms (Orlando, Florida, United States). Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics, Philadelphia, PA, pages 269-279, 1992.
[9]F. Nielsen and R. Nock “Approximating Smallest Enclosing Disks” Canadian Conference on Computational Geometry (Montreal, Canada), pages 124-127, 2004.
[10]I. J. Balaban “An optimal algorithm for finding segment intersections.” In Proc. 11th Annu. ACM Sympos. Comput. Geom., pages 211-219, 1995.
[11]I.F. Akyildiz, W. Su, Y. Sankarasubramaniam, and E. Cayirci, “Wireless sensor networks: a survey,” Computer Networks, Elsevier Science, Vol. 38, No. 4, pages 393-442, 2002.
[12]J. M. Keil. “Decomposing a polygon into simpler components”. SIAM J. Comput., Vol. 14, No. 4, pages 799-817, 1985.
[13]J. O'Rourke “Art gallery theorems and algorithms” Oxford International Series Of Monographs On Computer Science, 1987.
[14]J. O'Rourke “Computational Geometry in C” New York: Cambridge Univ. Press, 1994.
[15]J. O'Rourke, J.E. Goodman “Handbook of Discrete and Computational Geometry”, Chapter 25, pages 467-480, CRC Press LLC, Boca Raton, FL, 1997.
[16]J. Liu, Si-Qing Zheng “A simplified optimal algorithm for constructing the convex hull of a simple polygon” In Proceedings of the 30th Annual Southeast Regional Conference, pages 453-456, ACM Press, New York, NY, 08-10 April 1992.
[17]J. Pan, Y. T. Hou, L. Cai, Y. Shi, S. X. Shen "Topology control for wireless sensor networks" In Proceedings of the 9th Annual international, 2001.
[18]J. Urrutia “Art Gallery and Illumination Problems” in Handbook on Computational Geometry, pages 973-1027, Elsevier Science Publishers, Amsterdam, 2000.
[19]L. J. Guibas and J. Hershberger “Optimal shortest path queries in a simple polygon” In Proceedings of the Third Annual Symposium on Computational Geometry (Waterloo, Ontario, Canada, 08–10 June 1987). Ed. SCG '87. ACM Press, New York, NY, pages 50-63, 1987.
[20]M. D. Berg, M. V. Kreveld, M. Overmars, O. Schwarzkopf “Computational Geometry : Algorithms and Applications”
[21]M. Shamos "Problems in Computational Geometry" Ph.D. dissertation, Computer ScienceDepartment, Yale University, 1978.
[22]R.L. RAHAM, F. FRANCESYAO “Finding the Convex Hull of a Simple Polygon" Journal of Algorithms, Vol. 4, No. 4, pages 324-331, 1983.
[23]S. Slijepcevic, M. Potkonjak "Power Efficient Organization of Wireless Sensor Networks" IEEE International Conference on Communications , Helsinki, Finland, June 2001.
[24]T. S. Michael, Val Pinciu “Art gallery theorems for guarded guards” Computational Geometry, pages 247-258, 3 November 2003.
[25]T. C. SHERMER "Recent results in art galleries" Proceedings of the IEEE, pages 1384-1399, September 1992.
[26]W. Feng, J. Walpole, W. Feng, C. Pu “Moving towards massively scalable video-based sensor networks” Proc. Workshop on New Visions for Large-Scale Networks: Research and Applications, 2001.
[27]Y.J. Chiang, R. Tamassia “Optimal shortest path and minimum-link path queries between two convex polygons in the presence of obstacles” Report CS-9403, Comput. Sci. Dept.,Brown Univ., Providence, RI, 1994.