臺灣博碩士論文加值系統

在無線感測網路 ( Wireless Sensor Networks，WSNs ) 中，主要是利用仰賴電池的無線感測節點來執行任務，例如：傳輸、接收和計算。因此，設計一個省電的路由協定成為重要的議題，因為這可將有限電量運用至最佳化，減少不必要的電量消耗，達到延長整體網路存活時間 ( Network Lifetime )。以往在節省電量的研究主要是利用叢集方法 ( Clustering )，此方法使整個網路形成一個叢集架構並且所有的感測節點會劃分成多個虛擬群，稱為叢集。在這種架構中，只有部份節點允許參與代傳資料封包，故在設計一個具電量的叢集架構中重要的是如何確定適當的代傳節點。本論文考慮了剩餘電量和連結品質，提出一個具電量與連結有效性之叢集建構方法，稱為ELECT。ELECT以被動式叢集 ( Passive Clustering，PC ) 機制為基礎，每個候選代傳節點會根據自己的剩餘電量、連結品質和可成功傳輸的次數確定其優先權，並且利用此優先權競爭成為代傳節點。本研究以NS-2進行效能評估，模擬結果顯示ELECT與被動式叢集和其他方法比較下，不僅有較佳的封包到達率，同時也擁有較低的網路延遲和電量消耗。

In wireless sensor networks, sensor nodes depend on battery power to perform several tasks, such as transmitting, receiving, and computation. Thus, designing an energy efficient routing protocol becomes an important issue. Previous studies on efficient routing primarily exploit the clustering approach, in which the whole network forms a cluster structure, and all sensor nodes are divided into multiple logical groups, called clusters. In this structure, parts of nodes participate in forwarding data packets. In general, determining proper forwarding nodes is important to design an efficient cluster structure. This thesis considers both residual energy and link quality, and proposes an energy and link efficient clustering technique, called ELECT, to construct an effective cluster structure. The proposed ELECT is based on the passive clustering mechanism. In ELECT, each candidate forwarder determines its priority depending on its remaining energy, link quality, and the number of successive transmissions, and uses a strategy based on its priority to contend for a forwarder. Simulation results validate that, compared with the passive clustering mechanism and other approaches, ELECT significantly achieves a higher packet delivery ratio. In addition, ELECT causes lower transmission delay and less energy consumption than other approaches.

摘要 I
Abstract II
誌謝 III
目錄 IV
表目錄 VI
圖目錄 VII
第一章 緒論 1
第二章 文獻回顧 4
2.1 CH選擇 4
2.1.1節點ID 4
2.1.2節點連結度 5
2.1.3節點電量 6
2.1.4連結品質 ( Link Quality ) 8
2.2 被動式叢集架構 8
第三章 ELECT: ENERGY AND LINK EFFICIENT CLUSTERING TECHNIQUE 12
3.1 概觀 12
3.2 路由因子 ( Routing Metrics ) 12
3.2.1剩餘電量 ( Energy Remaining ) 12
3.2.2連結品質 ( Link Quality ) 14
3.2.3優先權計算 16
3.3 ELECT運作 18
第四章 模擬與分析 22
4.1 模擬環境假設 22
4.2 ELECT數據分析 23
4.2.1平均封包到達率 23
4.2.2平均剩餘電量 24
4.2.3平均網路延遲 26
第五章 結論 29
參考文獻 30

[1] A. A. Abbasi and M. Younis, “A Survey on Clustering Algorithms for Wireless Sensor Networks,” Elsevier Computer Communications, 2007, pp. 2826-2841.
[2] I. F. Akyildiz, W. Su, Y. Sankarasubramaniam and E. Cayirci, “A Survey on Sensor Networks,” IEEE Communications Magazine, vol. 40, no. 8, 2002, pp. 102-114.
[3] R. S. Chang and C. J. Kuo, “An Energy Efficient Routing Mechanism for Wireless Sensor Network,” 20th International Conference on Advanced Information Networking and Applications, vol. 2, 2006, pp. 308-312.
[4] C. C. Chen and T. K. Wu, “The Survey of Data Aggregation Techniques in Wireless Sensor Networks: Current Approaches and Future Directions,” International Conference on Digital Technology and Innovation Management, 2006, pp. 1105-1126.
[5] T. Clausen and P. Jacquet, “Optimized Link State Routing Protocol (OLSR),” Internet Request for Comments 3626, 2003, pp.1-53.
[6] D. Culler, D. Estrin and M. Srivastava, “Guest Editors' Introduction: Overview of Sensor Networks,” IEEE Computer, vol. 37, 2004, pp. 41-49.
[7] D. S. J. De Couto, D. Aguayo, J. Bicket and R. Morris, “A High-Throughput Path Metric Formulti-Hop Wireless Routing,” ACM Annual International Conference on Mobile Computing and Networking, 2003, pp. 134-146.
[8] R. Draves, J. Padhye and B. Zill, “Comparison of Routing Metrics for Static Multi-Hop Wireless Networks,” ACM Annual Conference of the Special Interest Group on Data Communication, 2004, pp. 133-144.
[9] R. Draves, J. Padhye and B. Zill, “Routing in Multi-Radio, Multi-Hop Wireless Mesh Networks,” ACM Annual International Conference on Mobile Computing and Networking, 2004, pp.114-128.
[10] E. J. Duarte-Melo and M. Liu, “Analysis of Energy Consumption and Lifetime of Heterogeneous Wireless Sensor Networks,” IEEE Global Telecommunication Conference, 2002, pp. 21-25.
[11] J. Ford, “Telecommunications with MEMS Devices: an Overview,” 14th Annual Meeting of the IEEE Lasers and Electro-Optics Society, vol. 2, no. 12, 2001, pp. 415-416.
[12] M. Gerla and J. T. Tsai, “Multiuser, Mobile, Multimedia Radio Network,” Wireless Networks, 1995, pp. 255-265.
[13] M. Gerla, T. J. Kwon and G. Pei, “On-Demand Routing in Large Ad Hoc Wireless Networks with Passive Clustering,” IEEE Wireless Communications and Networking Conference, 2000, pp. 100-105.
[14] M. J. Handy, M. Haase and D. Timmermann, “Low Energy Clustering Hierarchy with Deterministic Cluster Head Selection,” IEEE Mobile and Wireless Communications Networks, 2002, pp. 368-372.
[15] V. Handziski, A. Kopke, H. Karl, C. Frank and W. Drytkiewicz, “Improving the Energy Efficiency of Directed Diffusion Using Passive Clustering,” 1st European Workshop in Wireless Sensor Networks, vol. 2920, 2004, pp. 172-187.
[16] W. R. Heinzelman, A. P. Chandrakasan and H. Balakrishnam, “An Application-Specific Protocol Architecture for Wireless Microsensor Networks,” IEEE Transactions on Wireless Communications, vol. 1, 2002, pp. 660-670.
[17] T. C. Hou and T. J. Tsai, “Adaptive Clustering in A Hierarchical Ad Hoc Network,” International Computer Symposium, 1998, pp. 171-176.
[18] S. C. Huang and R. H. Jan, “Energy-Aware, Load Balanced Routing Schemes for Sensor Network,” 10th International Conference on Paralldl and Distributed Systems, 2004, pp. 419-425.
[19] J. M. Kahn, R. H. Katz and K. S. J. Pister, “Next Century Challenges: Mobile Networking for Smart Dust,” ACM International Conference on Mobile Computing and Networking, 1999, pp. 263-270.
[20] T. J. Kwon and M. Gerla, “Efficient Flooding with Passive Clustering (PC) in Ad Hoc Networks,” ACM SIGCOMM Computer Communication Review, 2002, pp. 44-56.
[21] K. Lee, J. Lee, H. Lee and Y. Shin, “A Density and Distance Based Cluster Head Selection Algorithm in Sensor Networks,” 12th International Conference on Advanced Communication Technology, 2010, pp. 162-165.
[22] C. R. Lin and M. Gerla, “Adaptive Clustering for Mobile Wireless Networks,” IEEE Journal on Selected Areas in Communications, vol. 15, no. 7, 1997, pp. 1265-1275.
[23] S. Lindsey, C. Raghavendra and K. Sivalingam, “Data Gathering in Sensor Networks Using the Energy Delay Metric,” 15th International symposium on IEEE Parallel and Distributed Processing, 2001, pp. 2001-2008.
[24] A. B. McDonald and T. F. Znati, “A Mobility-Based Framework for Adaptive Clustering in Wireless Ad Hoc Networks,” IEEE Journal on Selected Areas in Communications, vol. 17, no. 8, 1999, pp. 1466-1487.
[25] I. S. Misra, S. Dolui and A. Das, “Enhanced Energy-Efficient Adaptive Clustering Protocol for Distributed Sensor Networks,” 13th IEEE International Conference on Communication, vol. 1, 2005, pp. 1-6.
[26] L. Qing, Q. X. Zhu and M. W. Wang, “Design of a Distributed Energy-Efficient Clustering Algorithm for Heterogeneous Wireless Sensor Networks,” Computer Communications, vol. 29, 2006, pp. 2230-2237.
[27] C. Schurgers and M. B. Srivastava, “Energy Efficient Routing in Wireless Sensor Networks,” IEEE Military Communications Conference, vol. 1, 2001, pp. 357-361.
[28] G. Smaragdakis, I. Matta and A. Bestavros, “SEP: A Stable Election Protocol for Clustered Heterogeneous Wireless Sensor Networks,” 2nd International Workshopon Sensor and Actor Network Protocoland Applications, 2004, pp. 1-11.
[29] J. K. Taek, M. Gerla, V. K. Varma, M. Barton and T. R. Hsing, “Efficient Flooding with Passive Clustering-An Overhead-Free Selective Forward Mechanism for Ad Hoc/Sensor Network,” Proceedings of the IEEE, vol. 91, 2003, pp. 1210-1220.
[30] The Network Simulator：Ns-2, http：//isi.edu/nsnam/ns/.
[31] R. Virrankoski and A. Savvides, “TASC：Topology Adaptive Spatial Clustering for Sensor Networks,” 2nd IEEE International Conference on Mobile Ad Hoc and Sensor Systems, 2005, pp. 1-10.
[32] Y. Xu, J. Heidemann and D. Estrin, “Geography-Informed Energy Conservation for Ad Hoc Routing,” International Conference on Mobile Computing and Networking, 2001, pp. 1-15.
[33] 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.
[34] J. Zhu and S. Papavassiliou, “On the Energy-Efficient Organization and The Lifetime of Multi-Hop Sensor Networks,” IEEE Communications Letters, vol. 7, no. 11, 2003, pp. 537-539.