近年來，微型製造的發展使得通訊與電池技術縮減了通訊設備大小，可將感測、通訊及資料處理原件組成一個感測節點，並將大量的感測節點構成無線感測網絡（Wireless Sensor Networks，WSNs），由於感測節點本身的能量是有限的，並不容易獲得能量，為了要提高整體網路生命週期，改善的關鍵便是能源效率。
　　本研究針對改善無線感測網路資料傳輸方式，藉由改善傳輸方式來節省能量消耗，提高整體網路生命週期。LEACH 協議(Low-Energy Adaptive Clustering Hierarchy) 以叢集基礎架構為基礎，使節點間能源消耗平衡進而延長網路生命週期，因此有效的叢集建置策略對於無線感測網路是具有意義的。然而，傳統的叢集架構對選取叢集區塊大小難以控制，並讓叢集首(cluster head) 發生長距離傳輸，增加能源消耗，縮短整體網路生命週期。
　　本研究提出不同的叢集切割策略SCGP  ，能處理地理區域差異性過大、平衡叢集內的能源負載並避免叢集節點間長距離傳輸，另外使用蟻群演算法(Ant-Colony Optimization，Aco) 找尋叢集首傳輸到SINK node  的最短路徑，避免長距離傳輸造成多餘能量消耗。

In recent years, the development of micro-manufacture, communication and battery technologies has reduced the size of that, we can compose the sensor, wireless communication, and date processing units into a sensor node which is the basis of Wireless Sensor Networks(WSNs). WSNs contains a large number of sensor nodes. Since the energy of nodes is limited, and environment is not easy to get energy, the energy efficiency is a key design that needs to be enhanced in order to improve the life-time of the network.

　　This study is to improve the transmission of WSNs data path to reduce energy consumption. In  LEACH （Low-Energy Adaptive Clustering Hierarchy） is based on the cluster structure, facilitate to balance the energy consumption, among sensor nodes and enlarge the system life-time, providing an efficient cluster construction strategy for WSNs is vitally meaningful. However, the conventional cluster constructions are difficult to control the geographical area of a cluster. The methods usually generate long-distance intra-cluster routing and can not keep the energy efficiency.

　　We use different cluster cutting strategies were proposed to deal with the large geographical differences, balance the energy load in the cluster and avoid the long-distance transmission between internal cluster nodes. In addition, in the cluster first transmission to the base station path selection, we use the Ant-Colony Optimization (Aco) finds the shortest path from the cluster-heads to the base station, that can be avoided long-distance intra-cluster data delivery. Simulation results demonstrate our strategy are efficient.

目錄
目錄	IV
圖目錄	VI
表目錄	VII
第一章 研究背景與目的 1
1.1 研究背景 1
1.2 研究目的 3
1.3 論文架構 4
第二章 研究相關 6
2.1 Wireless Sensor Networks 6
2.2 叢集化感測網路 8
2.3 Low-Energy Adaptive Clustering Hierarchy 9
2.3.1 叢集設定時期(Cluster set-up phase) 10
2.3.2 叢集穩定時期(Steady-state phase) 11
2.4 蟻群演算法 12
2.4.1 路徑建構(Construct Solution) 13
2.4.2 費洛蒙更新(Pheromone Updating) 14
第三章 叢集配置策略 16
3.1 叢集重組 16
3.2 叢集設定 18
3.3 資料傳輸 22
第四章 系統模擬與分析討論	29
4.1 模擬軟體介紹	29
4.2 環境模擬與參數 33
4.3 實驗結果 37
第五章 結論及未來發展 41
5.1 結論 41
5.2 未來發展方向	42
參考文獻 43
附錄-英文論文46
圖目錄
圖2-1 Wireless Sensor Networks 基本架構圖 7
圖2-2 LEACH叢集化流程 9
圖2-3 LEACH叢集設定時期 10
圖2-4 LEACH分布圖 11
圖2-5 蟻群演算法示意圖 13
圖3-1 叢集重組流程 17
圖3-2 設定叢集流程 21
圖3-3 節點傳送比較 23
圖3-4 叢集化架構圖 24
圖3-5 蟻群流程 25
圖3-6 蟻群演算法流程 28
圖4-1 NAM 模擬結果 30
圖4-2 NS2 架構 31
圖4-3 NS2 網路模擬流程圖 32
圖4-4 一階無線電能源模型架構圖(First order radio model) 33
圖4-4 不同感測網路區域大小的整體網路生命週期比較 37
圖4-5 不同節點數量下整體網路生命週期比較 38
圖4-6 初始能量為1J±0.1~1J±0.5 焦耳整體網路生命週期比較 39
表目錄
表4-1 實驗環境相關參數 36

[1]U.Lee,E.O.Magistretti; B.O.Zhou; M.Gerla; P.Bellavista; A.Corradi. "Eifficient Data Harvesting in Mobile Sensor Platforms." Pervasive Computing and Communication(PerCom)Workshops.2006
[2]S. Olariu; I. Stojmenovic. "Design Guidelines for Maximizing Lifetime and Avoiding Energy Holes in Sensor Networks with Uniform Distribution and Uniform Reporting." IEEE International Conference on Computer Communications(INFOCOM), 2006,1-12
[3]J. Yick, B. Mukherjee; D. Ghosal. "Wireless Sensor Network Survey.  ComputerNetworks."2008,Volme：52, No.12,2292-2330
[4]M. Cardei, Y. Yang; J. Wu. Non-uniform. "Sensor Deployment in Mobile Wireless Sensor Networks." IEEE World of Wireless, Mobile and Multimedia Networks (WoWMoM), 2008,1-8
[5]G. Wang, G. Cao; T. F. LaPorta. "Movement-assisted Sensor Deployment. IEEE Transactions on Mobile Computing." 2006, Volume：5, No. 6,640-652
[6]R. Subramanian； F. Fekri. "Sleep Scheduling and Lifetime Maximization in Sensor Networks: Fundamental Limits and Optimal Solutions."  ACM International Conference on Information Processing in Sensor Networks (IPSN’06), 2006.
[7]W.B.Heninzelman; A.P.Chandrakasan; H.Balakrishnan. "An application-specific protocol architecture for wireless microsensor networks." 2002 IEEE Transactions on Wireless Communications .2002  Volume: 1, Issue: 4,660-670
[8]W.Heinzelman. "Application-specific protocol architectures for wireless networks." Ph.D.thesis,Massachusetts Institute of Technoiogy. 2000
[9]Huei-Wen Ferng; Jing-Shiaun Chuang. "Area-partitioned clustering and cluster head rotation for wireless sensornetworks." 2017 International Conference on Machine Learning and Cybernetics (ICMLC).2017,Volume：2, 593-598
[10]Qi-Ye Zhang；Ze-Ming Sun；Feng Zhang. "A clustering routing protocol for wireless sensor networks based on type-2 fuzzy logic and ACO  Fuzzy Systems." 2014 IEEE International Conference on.2014,1098-7584
[11]Gang Xin. "Research on the routing protocol in wireless sensor networks based on genetic algorithm."  2011 2nd International Conference on Artificial Intelligence, Management Science and Electronic Commerce (AIMSEC),2011,3313-3316
[12]Furat AL-Obaidy; Hossein Zereshkian; Farah A. Mohammadi."A energy-efficient routing algorithm in ZigBee-based cluster tree Wireless Sensor Networks." 2017 IEEE 30th Canadian Conference on Electrical and Computer Engineering (CCECE).2017,1-5
[13]M. Dorigo; M. Birattari; T. Stutzle. "Ant Colony Optimization. Computational Intelligence Magazine." IEEE. 2006, vol. 1, pp. 28-39
[14]K.-H. Li, J.-S. Leu, and J. Hošek, "Ant-based On-demand Clustering Routing Protocol for Mobile Ad-hoc Networks," presented at the The 3rd International Workshop on Ad Hoc and Ubiquitous Computing (AHUC 2013), 2013.
[15]T. Camilo, C. Carreto, J. Silva, and F. Boavida. "An Energy-Efficient Ant-Based Routing Algorithm for Wireless Sensor Networks." ed, 2006, pp.49-59.
[16]K. Subhadra; M. Shashi; Abhishek Das. "Extended ACO based document clustering with hybrid distance metric." 2015 IEEE International Conference on Electrical, Computer and Communication Technologies (ICECCT). 2015,1-6
[17]Yongjun Sun; Wenxin Dong; Yahuan Chen. "An Improved Routing Algorithm Based on Ant Colony Optimization in Wireless Sensor Networks." 2017, Volume: 21, Issue: 6,1317-1320
[18]Yanfei Wu; Yanqin Zhu; Zhe Yang. "Routing algorithm based on ant colony optimization for mobile socialnetwork", 2017, 297-302
[19]V.Raghunathan； C.Schurgers; S. Park; M. B. Srivastava."Energy-Aware Wireless Microsensor Networks." IEEE Signal Processing Magazine,2002, Vol. 19, No. 2, pp. 40-50.
[20]O. Younis and S. Fahmy.“HEED: A Hybrid, Energy-efficient, Distributed Clustering Approach for Ad hoc Sensor Networks.” IEEE Transaction on Mobile Computing, 2004, pp. 660-669.
[21]J. Zhu and S. Papavassiliou, “On the Energy-efficient Organization and the Lifetime of Multi-hop Sensor Networks, ”IEEE Communications. Letters,2003, Vol. 7, No. 11, pp. 537-539.
[22]A. Mainwaring, D. Culler, J. Polastre, R. Szewczyk and J.Anderson,“Wireless Sensor Networks for Habitat Monitoring, ”Proceedings of The First ACM International Workshop on Wireless Sensor Networks and Applications, 2002, Georgia.
[23]R.-S. Chang and S.-H. Wang, “Hexagonal Collaboration Groups in Sensor Networks,” Proceedings of Consumer Communications and Networking Conference, 2008, pp. 358-359.
[24]M. Dorigo, M. Birattari, and T. Stutzle, "Ant Colony Optimization," Computational Intelligence Magazine, IEEE,2006 , vol. 1, pp. 28-39.