近年來，許多研究學者投入無線感測網路領域，它是由大量的低能耗、低成本及微小的感測節點組成，協助完成資料蒐集、目標監測和環境感測等任務，目前已經被應用於軍事、醫療和智能居家等領域。但能量有限是約束無線感測網路的關鍵因素之一，因此設計一個能量節能的無線感測路由方法是研究人員面臨的挑戰。而無線感測網路通常部署在惡劣環境中，節點無法獲得能量補充，再加上節點失效帶來的網路拓樸動態變化，因此無線感測網路需設計適應於自身特點的無線路由方法。本論文對無線感測網路的結構及特點進行研究，結合蟻群演算法的理論，以叢集式路由為基礎提出基於蟻群演算法之節能路由方法（Energy-efficient Routing of Wireless Sensor Network Based on Ant Colony Algorithm）。首先，透過節點自身的剩餘能量以及與基地台距離來調整叢集傳輸半徑，縮小靠近基地台的叢集半徑來減輕能量消耗，並利用叢集質心的概念作為選擇叢集首的依據，以平衡叢集內的傳輸距離，接著，在蟻群演算法中的轉移概率使用改進啟發式函數並考慮節點通訊傳輸距離和傳輸方向進行路徑方向引導，可以找到從來源節點到基地台的最佳路徑。同時為避免能量黑洞，定義修復螞蟻並結合回饋機制使路徑保持良好狀態。模擬結果表明，提出的方法可實現節省能量、可靠性路由，並可以均衡整體網路的能量消耗。經過大量的實驗與三種知名方法比較，顯示在平均剩餘能量方面平均至少提升9％，在感測節點存活數平均至少增加19％，最後在網路生命週期平均延長35％以上。

In recent years, many researchers have been devoted to the studying of wireless sensor networks. It consists of a number of low-energy, low-cost and small sensor nodes, which can be used to gather information, monitor target and sense environmental. It has been used in military, medical, intelligent home and environmental monitoring and other fields. However, limited energy is one of the key factors that constrain the wireless sensor network. Therefore, designing energy efficient routing methods for wireless sensor is a challenge for researchers. The sensor nodes of wireless sensor networks are usually deployed in harsh environments, in which situation the energy of the node cannot be added. In addition, sensor node failure brought about dynamic changes of the network topology. Therefore it is necessary to design a wireless sensor networks routing method to adapt to the characteristics of wireless sensor networks. In this thesis, the structure and characteristics of the wireless sensor networks are studied. Combining the theory of the ant colony algorithm, we proposed the Energy-efficient Routing of Wireless Sensor Network Based on Ant Colony Algorithm (ERACA) based on cluster routing. First, the cluster transmission radius is adjusted by the residual energy of the sensor nodes and the distances between sensor nodes and the base station. The cluster radius near the base station will be reduced for decreasing energy consumption. Moreover, we utilize the concept of cluster centroid to select cluster head (CH) in order to balance the transmission distance in the cluster. Then using the improved heuristic function, considering the node communication transmission distance and the between-nodes angle appropriately guides the path direction, thus an optimal path from the source node to the base station can be found. Meanwhile, to avoid energy hole, a repair ant is defined and combined with the feedback mechanism for ensuring that paths remain open. The simulation results show that the proposed method can realize energy-efficient and reliable routes, which helps to balance the energy consumption of the network. A large amount of experiments have been made for comparing the performance of the proposed method and the other three well-known methods. The experimental results reveal that the proposed method increases the average residual energy at least 9%, increases the average number of alive nodes at least 19%, and prolongs the average network lifetime more than 35%.

[1] J. N. Al-Karaki and A. E. Kamal, “Routing Techniques in Wireless Sensor Networks: A Survey,” IEEE Wireless Communications, vol. 11, no. 6, pp. 6-28, 2004.
[2] J. Alonso, A. Dunkels, and T. Voigt, “Bounds on the Energy Consumption of Routings in Wireless Sensor Networks,” Proc. 2nd Int. Workshop on Modeling and Optimization in Mobile Ad Hoc and Wireless Networks, pp. 62-70, 2004.
[3] G. Anastasi, M. Conti, M. D. Francesco, and A. Passarella, “Energy Conservation in Wireless Sensor Network: A Survey,” Ad Hoc Networks, vol. 7, no. 3, pp. 537-568, 2009.
[4] V.K. Arora, V. Sharma, and M. Sachdeva, “A Multiple Pheromone Ant Colony Optimization Scheme for Energy-efficient Wireless Sensor Networks,” Soft Computing, 2019.
[5] T. Camilo, C. Carreto, J. S. Silva, and F. Boavida, “An Energy-efficient Ant-based Routing Algorithm for Wireless Sensor Networks,” Proc. ANTS 5th Int. Workshop Ant Colony Optim. Swarm Intell., pp. 49-59, 2006.
[6] J.Y. Chang, “A Distributed Cluster Computing Energy-efficient Routing Scheme for Internet of Things Systems,” Wireless Pers. Commun., vol. 82, no. 2, pp. 757-776, 2014.
[7] B. Chen, K. Jamieson, H. Balakrishnan, and R. Morris, “Span: An Energy-efficient Coordination Algorithm for Topology Maintenance in Ad Hoc Wireless Networks,” Proc. 7th Ann. Int. Conf. Mobile Computing and Networking, pp. 85-96, 2001.
[8] D. Cheng, Y. Xun, T. Zhou, and W. Li, “An Energy Aware Ant Colony Algorithm for the Routing of Wireless Sensor Networks,” Int. Computing and Information Science, vol. 134, pp. 395-401, 2011.
[9] I. Demirkol, C. Ersoy, and F. Alagoz, “MAC Protocols for Wireless Sensor Networks: A Survey,” IEEE Communications Mag., vol. 44, no. 4, pp. 115-121, 2006.
[10] I. Dietrich and F. Dressler, “On the Lifetime of Wireless Sensor Networks,” ACM Trans. Sensor Networks, vol. 5, no. 1, pp. 1-39, 2009.
[11] M. Dorigo and T. Sttzle, “Ant Colony Optimization,” MA, Cambridge: MIT Press, 2004.
[12] S. C. Ergen and P. Varaiya, “TDMA scheduling algorithms for wireless sensor networks,” Wireless Netw., vol. 16, no. 4, pp. 985-997, 2010.
[13] Z. Han, J. Wu, J. Zhang, L. Liu, and K. Tian, “A General Self-organized Tree-based Energy-balance Routing Protocol for Wireless Sensor Network,” IEEE Trans. on Nucl. Sci., vol. 61, no. 2, pp. 732-740, 2014.
[14] M. Handy, M. Haase, and D. Timmermann, “Low Energy Adaptive Clustering Hierarchy with Deterministic Cluster-head Selection,” IEEE Conf. on Mobile and Wireless Communications Network, pp. 368-372, 2002.
[15] W.R. Heinzelman, A. Chandrakasan, and H. Balakrishnan, “An Application-specific Protocol Architecture for Wireless Microsensor Networks,” IEEE Trans. on Wireless Communications, vol. 1, no. 4, pp. 660-670, 2002.
[16] W.R. Heinzelman, A. Chandrakasan, and H. Balakrishnan, “Energy-efficient Communication Protocol for Wireless Microsensor Networks,” IEEE in Proc. 33rd Hawaii Int. Conference on System Sciences. pp. 4-7, 2000.
[17] C. Intanagonwiwat, R. Govindan, and D Estrin, “Directed Diffusion for Wireless Sensor Networking,” IEEE/ACM Trans. on Networking, vol. 11, no. 1, pp. 2-16, 2003.
[18] S. Kalantary and S. Taghipour, “A Survey on Architectures Protocols Applications and Management in Wireless Sensor Networks,” Journal of Advanced Computer Science & Technology, vol. 3, no. 1, pp. 1-11, 2014.
[19] X. Li, B. Keegan, and F. Japhet, “Ant Colony Clustering Routing Protocol for Optimization of Large Scale Wireless Sensor Networks,” IT&T, 2015.
[20] C. Li, M. Ye, G. Chen, and J. Wu, “An Energy-efficient Unequal Clustering Mechanism for Wireless Sensor Networks,” In Proc. 2th IEEE Int. Conference on Mobile Ad-hoc and Sensor Systems, pp. 597-604, 2005.
[21] Y. Liao, H. Qi, and W. Li, “Load-balanced Clustering Algorithm with Distributed Self-organization for Wireless Sensor Networks,” IEEE Sensors J., vol. 13, no. 5, pp. 1498-1506, 2013
[22] X. Liu, “An Optimal-distance Based Transmission Strategy for Lifetime Maximization of Wireless Sensor Networks,” IEEE Sensors J., vol. 15, no. 6, pp. 3484-3491, 2015.
[23] A. F. Liu, Z. H. Liu, N. Mohammed, X. Jin, and Z. G. Chen, “An Elaborate Chronological and Spatial Analysis of Energy Hole for Wireless Sensor Networks,” Computer Standards Interfaces, vol. 35, no. 1, pp. 132-149, 2013.
[24] A. Mathur, T. Newe, and M. Rao, “Healthcare WSN: Cluster Elections and Selective Forwarding Defense,” Proc. 9th Int. Conf. Next Generation. Mobile Appl. Services Technology, pp. 341-346, 2015.
[25] M. A. Mehaseb, Y. Gadallah, and H. El-Hennawy, “WSN Application Traffic Characterization for Integration within the Internet of Things,” Proc. IEEE Int. Conf. on Mobile Ad-hoc and Sensor Networks, pp. 318-323, 2013.
[26] N. A. Pantazis, S. A. Nikolidakis, and D. D. Vergados, “Energy-efficient Routing Protocols in Wireless Sensor Networks: A Survey,” IEEE Communications Surveys & Tutorials, vol. 15, no. 2, pp. 551-591, 2013.
[27] Y. C. Rao and S. Rani, “Energy Efficiency and Maximizing Network Lifetime for WSN Using ACO Algorithm,” International Journal of Innovative Technology and Exploring Engineering, vol. 5, no. 2, pp. 15-20, 2015.
[28] T. Rault, A. Bouabdallah, and Y. Challal, “Energy Efficiency in Wireless Sensor Networks: A Top-down Survey,” Computer Networks, vol. 67, pp. 104-122, 2014.
[29] H. Salarian, K.-W. Chin,and F. Naghdy, “An Energy-efficient Mobile-sink Path Selection Strategy for Wireless Sensor Networks,” IEEE Trans. on Veh. Technol., vol. 63, no. 5, pp. 2407-2419, 2014.
[30] P. Singh, N. Kaur, and R. Kaur, “A Review: Comparative Analysis of Routing Protocols in Wireless Sensor Network,” 2013
[31] Y. Song, L. Liu, H. Ma, and A. V. Vasilakos, “A Biology-based Algorithm to Minimal Exposure Problem of Wireless Sensor Networks,” IEEE Trans. Network Service Management, vol. 11, no. 3, pp. 417-430, 2014.
[32] Y. Sun, W. Dong, and Y. Chen, “An Improved Routing Algorithm Based on Ant Colony Optimization in Wireless Sensor Networks,” IEEE Communications Letters, vol. 21, no. 6, pp. 1317-1320, 2017.
[33] C. Wang, J. Shih, B. Pan, and T. Wu, “A Network Lifetime Enhancement Method for Sink Relocation and its Analysis in Wireless Sensor Networks,” IEEE Sensors J., vol. 14, no. 6, 2014.
[34] Y. Xue, X. Chang, S. Zhong, Y. Zhuang, “An Efficient Energy Hole Alleviating Algorithm for Wireless Sensor Networks,” IEEE Trans. on Consum. Electron., vol. 60, no. 3, pp. 347-355, 2014.
[35] J. Yan, M. Zhou, and Z. Ding, “Recent Advances in Energy-efficient Routing Protocols for Wireless Sensor Networks: A Review,” IEEE Access, vol. 4, pp. 5673-5686, 2016.
[36] Y. Yao, Q. Cao, and A.V. Vasilakos, “EDAL: An Energy Efficient, Delay-aware, and Lifetime-balancing Data Collection Protocol for Heterogeneous Wireless Sensor Networks,” IEEE/ACM Trans. Networking, vol. 23, no. 3, pp. 810-823, 2015
[37] M. Zorzi and R. R. Rao, “Geographic Random Forwarding (GeRaF) for Ad Hoc and Sensor Networks: Multihop Performance,” IEEE Trans. on Mobile Computing, vol. 2, no. 4, pp. 337-348, 2003.