隨著科技發展日新月異，以機器對機器(Machine-to-Machine, M2M)技術為通訊基礎的物聯網(Internet of Things, IoT)之應用相當廣泛，機器們透過連接至網路來達到更多使用上的需求，也更貼近人類使用的習慣。然而，這些IoT應用之設備數量將逐漸增加且廣泛地應用於生活週遭，部分應用之設備將會根據各自不同的需求而有不同傳輸資料的頻率來進行資料的搜集，且設備本身的設計可能有著不同的協定，此時做為設備與網路之間橋樑的閘道器就扮演一個重要的角色。若使用目前極為普及的無線網狀網路(Wireless Mesh Network, WMN)來做為通訊網路，將以無線多重跳躍(Wireless Multi-Hop)的方式來傳遞資訊，故設備間可能需要路由器的介接來幫助傳送資料到所屬的閘道器。在有眾多具備自動傳送訊息的IoT設備之環境中，若閘道器部署位置不理想將造成設備的資料傳輸次數龐大，就需要額外使用更多能源來完成資料傳送。因此，本研究提出適用於無線網狀網路中閘道器部署演算法，其在滿足基本服務品質(Quality of Service, QoS)需求前提下，不僅可平衡各閘道器間的負擔，又可有效地降低資料傳送的次數，以因應IoT時代的來臨，透過充分之模擬比較，本研究所提之演算法在負擔平衡及資料傳送次數方面確實有其功效且優於文獻上之相關演算法並值得推薦於無線網狀網路中使用。

With the advancement of the machine-to-machine (M2M) communication technology, more and more devices do not stand alone but are interlinked. Nowadays, lots of applications, such as Internet of things (IoT) use this technology. Because the applications of IoT are quite diverse and applied to our daily life, the number of M2M devices will be raised gradually. In the past, most of papers employed a wireless mesh network (WMN) to implement the M2M communication. In a WMN, the wireless multi-hop communication is applied to transmit information from the source to the gateway to access the Internet. However, the devices of different IoT applications have different frequencies of data transmission and different protocols as well. Therefore, gateways play an important role and act as communication bridges between the WMN and the Internet, showing the importance of gateway deployment. If gateways are not selected appropriately, additional energy will be consumed for data transmission. To touch the aforementioned issue properly, a gateway deployment algorithm in a WMN is proposed in this thesis. Such an algorithm can not only meet the basic quality-of-service (QoS) requirement but also balance the load among gateways successfully and reduce the transmission times effectively. Through extensive simulations, we successfully show that the proposed algorithm can indeed balance the load among gateways and reduce the transmission times effectively. It outperforms the closely related algorithms in the literature for sure and is highly recommended for use in a WMN.

[1] B. He, B. Xie, and D. P. Agrawal, “Optimizing the internet gateway deployment in a wireless mesh network,” in Proc. IEEE International Conference on Mobile Adhoc and Sensor Systems (MASS), pp. 1–9, Oct. 2007.
[2] C. C. Lin, T. H. Chen, and H. H. Chin, “Adaptive router node placement with gateway positions and QoS constraints in dynamic wireless mesh networks,” Journal of Network and Computer Applications, vol. 74, pp. 149–164, Oct. 2016.
[3] T. N. Vidanagama, D. Arai, and T. Ogishi, “M2M gateway selection scheme for smart wireless devices,” in Proc. 18th International Conference on Intelligence in Next Generation Networks (ICIN), pp. 176–183, Feb. 2015.
[4] D. Niyato, L. Xiao, and P. Wang, “Machine-to-machine communications for home energy management system in smart grid,” IEEE Communications Magazine, vol. 49, no. 4, pp. 53–59, Apr. 2011.
[5] I. Gravalos, P. Makris, K. Christodoulopoulos, and E. A. Varvarigos, “Efficient gateways placement for internet of things with qos constraints,” in Proc. IEEE Global Communications Conference (GLOBECOM), pp. 1–6, Dec.2016.
[6] S. Nastic, S. Sehic, M. Vögler, H. L. Truong, and S. Dustdar, “PatRICIA – A novel programming model for IoT applications on cloud platforms,” in Proc. IEEE 6th International Conference on Service-Oriented Computing and Applications, pp. 53–60, Dec. 2013.
[7] J. Gubbi, R. Buyya, S. Marusic, and M. Palaniswami, “Internet of things (IoT): A vision, architectural elements, and future directions,” Future generation computer systems, vol. 29, no. 7, pp. 1645–1660, Sep. 2013.
[8] A. M. Ahmed, A. H. Abdalla, and I. El-Azhary, “Gateway placement approaches in wireless mesh network: Study survey,” in Proc. International Conference on Computing, Electrical and Electronic Engineering (ICCEEE), pp. 545–547, Aug. 2013.
[9] Q. Liu, S. Leng, Y. Mao, and Y. Zhang, “Optimal gateway placement in the smart grid machine-to-machine networks,” in Proc. IEEE GLOBECOM Workshops (GCWkshps), pp. 1173–1177, Dec. 2011.
[10] A. Ghasempour, “Optimum packet service and arrival rates in advanced metering infrastructure architecture of smart grid,” in Proc. IEEE Green Technologies Conference (GreenTech), pp. 1–5, Apr. 2016.
[11] J. Tingting and Z. Junhui, “Optimal gateway deployment in the smart grid machine-to-machine networks,” in Proc. 9th International Conference on Communications and Networking in China, pp. 407–411, Aug. 2014.
[12] A. Ghasempour and T. K. Moon, “Optimizing the number of collectors in machine-to-machine advanced metering infrastructure architecture for internet of things-based smart grid,” in Proc. IEEE Green Technologies Conference (GreenTech), pp. 51–55, Apr. 2016.
[13] A. Ghasempour, “Optimized advanced metering infrastructure architecture of smart grid based on total cost, energy, and delay,” in Proc. IEEE Power Energy Society Innovative Smart Grid Technologies Conference (ISGT), pp. 1–6, Sep. 2016.
[14] C. C. Lin, L. Shu, and D. J. Deng, “Router node placement with service priority in wireless mesh networks using simulated annealing with momentum terms,” IEEE Systems Journal, vol. 10, no. 4, pp. 1402–1411, Dec. 2016.
[15] C. C. Lin, “Dynamic router node placement in wireless mesh networks: A PSO approach with constriction coefficient and its convergence analysis,” Information Sciences, vol. 232, pp. 294–308, May 2013.
[16] F. Xhafa, C. Sánchez, A. Barolli, and M. Takizawa, “Solving mesh router nodes placement problem in wireless mesh networks by Tabu Search algorithm,” Journal of Computer and System Sciences, vol. 81, no. 8, pp. 1417–1428, Dec. 2015.
[17] M. Souissi and A. Meddeb, “Modelling of clustering with relay nodes in wireless sensor networks,” in Proc. IEEE 7th Annual Computing and Communication Workshop and Conference (CCWC), pp. 1–6, Jan. 2017.
[18] A. M. Ahmed, A. H. Abdalla, and I. El-Azhary, “Gateway placement approaches in wireless mesh network: Study survey,” in Proc. International Conference on Computing Electrical and Electronic Engineering (ICCEEE), pp. 545–547, Aug. 2013.
[19] Y. Li, S. Huang, R. Fan, Z. Zhang, and Y. Zhou, “Research on gateway deployment of WMN based on maximum coupling subgraph and PSO algorithm,” Soft Computing, vol. 21, no. 4, pp. 923–933, Feb. 2017.
[20] U. Ashraf, “Energy-aware gateway placement in green wireless mesh networks,” IEEE Communications Letters, vol. 21, no. 1, pp. 156–159, Jan. 2017.
[21] S. Avallone and A. Banchs, “A channel assignment and routing algorithm for energy harvesting multiradio wireless mesh networks,” IEEE Journal on Selected Areas in Communications, vol. 34, no. 5, pp. 1463–1476, May 2016.
[22] S. Huang and M. Tao, “Competitive swarm optimizer based gateway deployment algorithm in cyber-physical systems,” Sensors, vol. 17, no. 1, p. 209, Jan. 2017.
[23] A. Barolli, T. Oda, M. Ikeda, L. Barolli, F. Xhafa, and V. Loia, “Node placement for wireless mesh networks: Analysis of WMN-GA system simulation results for different parameters and distributions,” Journal of Computer and System Sciences, vol. 81, no. 8, pp. 1496–1507, Dec. 2015.
[24] B. Aoun, R. Boutaba, Y. Iraqi, and G. Kenward, “Gateway placement optimization in wireless mesh networks with QoS constraints,” IEEE Journal on Selected Areas in Communications, vol. 24, no. 11, pp. 2127–2136, Nov. 2006.
[25] Y. Bejerano, “Efficient integration of multihop wireless and wired networks with QoS constraints,” IEEE/ACM Transactions on Networking, vol. 12, no. 6, pp. 1064–1078, Dec. 2004.
[26] M. Seyedzadegan, M. Othman, B. M. Ali, and S. Subramaniam, “Zero-degree algorithm for internet gateway placement in backbone wireless mesh networks,” Journal of Network and Computer Applications, vol. 36, no. 6, pp. 1705–1723, Nov. 2013.
[27] T. Maolin, “Gateways placement in backbone wireless mesh networks,” International Journal of Communications, Network and System Sciences, vol. 2, no. 1, pp. 44–50, Feb. 2009.