近年來，物聯網裝置成長迅速，以及對相關的應用需求的提升，越來越多的應用進入生活及產業中，智慧家電、農業環境監測、油田的環境監測等等。在物聯網技術的幫助下，能夠更即時的獲取監測點上連續的資料，物聯網裝置需要將收集的資料透過網際網路回傳到中央伺服器，裝置間也時常需要彼此溝通，而目前對於這種應用下的網路環境架設，通常以無線網狀網路作為物聯網裝置間的網路架構，無線網狀網路不需要受限於網路纜線的限制，節點的佈置也不需要考慮網路孔位，僅需讓每個節點都被任一節點訊號範圍涵蓋即可，但如何用最少節點來涵蓋各個感測器裝置一直都是一個研究的議題，要解決這個問題，常見的演算法有基因演算法(Genetic Algorithm，GA)、禁忌搜尋演算法(Tabu Search，TS)等等演算法，但是多數相關研究研究考慮的是單一面向的問題，本論文提出一套基於A*演算法，能夠處理複雜情境，並加以優化以適用於無線網狀網路下的網狀節點佈置問題。

In recent years, IoT devices have grown rapidly, and the demand for related applications has increased. More and more applications have entered life and industry, such as smart home appliances, agricultural environmental monitoring, environmental monitoring of oil fields, etc… With the help of Internet of Things technology, it is possible to obtain continuous data on the monitoring point more instantaneously, but the IoT device needs to transmit the collected data to the central server through the Internet, and the devices frequently need to communicate with each other. Wireless Mesh Networks could be the best network environment for these applications, a wireless mesh network does not need to be limited by the network cable, and the node arrangement does not need to consider the position of network socket. It is only necessary to have each node covered by any node signal range. How to cover each sensor device with a minimum number of nodes is always a research topic. Compared to past research studies that only consider the specific scenarios, we propose a method based on A* algorithm can solve the node placement problem in the wireless mesh network for common scenarios.

[1] Gartner, Inc., "Gartner Says 8.4 Billion Connected "Things" Will Be in Use in 2017, Up 31 Percent From 2016" February 2017.
[2] Bahl, P., & Padmanabhan, V. N. (2000). RADAR: An in-building RF-based user location and tracking system. In INFOCOM 2000. Nineteenth Annual Joint Conference of the IEEE Computer and Communications Societies. Proceedings. IEEE (Vol. 2, pp. 775-784). Ieee.
[3] Wang, C. S., & Kao, L. F. (2012, August). The optimal deployment of wi-fi wireless access points using the genetic algorithm. In Genetic and Evolutionary Computing (ICGEC), 2012 Sixth International Conference on (pp. 542-545). IEEE.
[4] Lee, J. H., Han, B. J., Lim, H. J., Kim, Y. D., Saxena, N., & Chung, T. M. (2009). Optimizing access point allocation using genetic algorithmic approach for smart home environments. The Computer Journal, 52(8), 938-949.
[5] Leu, F. Y., & Liu, P. S. (2010, September). A channel assignment and AP deployment scheme for concentric-hexagon based multi-channel wireless networks. In Network-Based Information Systems (NBiS), 2010 13th International Conference on (pp. 504-509). IEEE.
[6] Raniwala, A., & Chiueh, T. C. (2005, March). Architecture and algorithms for an IEEE 802.11-based multi-channel wireless mesh network. In INFOCOM 2005. 24th Annual Joint Conference of the IEEE Computer and Communications Societies. Proceedings IEEE (Vol. 3, pp. 2223-2234). IEEE.
[7] Landa-Torres, I., Gil-Lopez, S., Del Ser, J., Salcedo-Sanz, S., Manjarres, D., & Portilla-Figueras, J. A. (2011, November). A Grouping Harmony Search approach for the Citywide WiFi deployment problem. In Intelligent Systems Design and Applications (ISDA), 2011 11th International Conference on (pp. 1026-1031). IEEE.
[8] Kar, K., & Banerjee, S. (2003, March). Node placement for connected coverage in sensor networks. In WiOpt'03: Modeling and Optimization in Mobile, Ad Hoc and Wireless Networks (pp. 2-pages).
[9] Eisenblatter, A., Geerdes, H. F., & Siomina, I. (2007, June). Integrated access point placement and channel assignment for wireless LANs in an indoor office environment. In World of Wireless, Mobile and Multimedia Networks, 2007. WoWMoM 2007. IEEE International Symposium on a (pp. 1-10). IEEE.
[10] Maolin, T. A. N. G. (2009). Gateways placement in backbone wireless mesh networks. International Journal of Communications, Network and System Sciences, 2(01), 44.
[11] Aoun, B., Boutaba, R., Iraqi, Y., & Kenward, G. (2006). Gateway placement optimization in wireless mesh networks with QoS constraints. IEEE Journal on Selected Areas in Communications, 24(11), 2127-2136.
[12] Rabaey, C. S. J., & Langendoen, K. (2002, June). Robust positioning algorithms for distributed ad-hoc wireless sensor networks. In USENIX technical annual conference (pp. 317-327).
[13] Zhang, X., Ludwig, A., Sood, N., & Sarris, C. D. (2018). Physics-based optimization of access point placement for train communication systems. IEEE Transactions on Intelligent Transportation Systems, (99), 1-11.
[14] Politi, A. A., Zamboni, L. C., Pasti, R., & de Castro, L. N. (2015, October). An optimization model for the indoor access point placement problem with different types of obstacles. In Computational Intelligence (LA-CCI), 2015 Latin America Congress on (pp. 1-4). IEEE.
[15] Ismail, A. H., Tasaki, R., Kitagawa, H., & Terashima, K. (2016). Optimum Placement of Wireless Access Point for Mobile Robot Positioning in an Indoor Environment. Journal of Robotics and Mechatronics, 28(2), 162-172.
[16] Alsmady, A., & Awad, F. (2017, April). Optimal Wi-Fi access point placement for RSSI-based indoor localization using genetic algorithm. In Information and Communication Systems (ICICS), 2017 8th International Conference on (pp. 287-291). IEEE.
[17] Puspitasari, N. F., Al Fatta, H., & Wibowo, F. W. (2015, December). Implementation of Greedy and Simulated Annealing Algorithms for Wireless Access Point Placement. In Artificial Intelligence, Modelling and Simulation (AIMS), 2015 3rd International Conference on (pp. 165-170). IEEE.