在無線感測網路 (Wireless Sensor Network)中，感測節點常以多躍代傳的方式將感測資料傳送至 Sink，導致 Sink 附近的感測節點因代傳大量的感測資料而提早耗盡電池的電量，進而縮短網路的生命期。為了解決此電量消耗不平衡的問題，本論文針對一隨機佈建的感測網路，提出一分散式二階段之演算法，以期達到電量平衡的目標。在第一階段中，本論文考量 Sensor 的剩餘電量，建構一電量平衡的資料收集樹狀拓樸，使剩餘電量較高的 Sensor 能執行較多的資料代傳工作，進而達到樹狀拓樸中同層 Sensor 間的電量平衡。在第二階段中，本論文針對 Sensor 之代傳資料量提出一可調式感測範圍的控制技術，以平衡網路拓樸中各層 Sensor 的電量消耗，以期達到剩餘電量平衡及全區覆蓋的雙重目的。最後，模擬結果顯示此電量平衡演算法在多躍資料代傳及可調式感測範圍的環境下皆能有效平衡網路中各 Sensor 之電量，並延長網路生命期。

In the Wireless Sensor Network (WSN), data collection from all sensors to the sink node is usually achieved in a multi-hop transmission manner. This leads to the energy imbalanced problem where sensors closer to the sink exhaust their energy earlier, reducing the network lifetime. This paper proposes a two-phase algorithm aiming at prolonging the network lifetime of a given WSN. The first phase constructs a tree-based topology which takes into consideration the remaining energy and transmission load of each sensor. In the constructed tree topology, sensors with higher remaining energy connect to more children such that energy balancing is achieved for all sensors in the same level of the tree. To balance the lifetime of sensors belonging to different tree levels, the second phase further adjusts the sensing range such that both full coverage and energy balance purposes can be achieved. Simulation results reveal that the proposed energy balancing algorithm outperforms existing works in terms of energy balance and network lifetime.

目錄 	IV
圖目錄 	VI
表目錄 	VIII
第一章、 簡介 	1
第二章、 相關研究 	5
第三章、 網路環境與問題描述 	11
3.1 Network Environment 	11
3.2 Problem Formulation 	12
第四章、 EFFICIENT ENERGY-BALANCING MECHANISM 	16
4.1 Basic Concept 	16
4.2 Topology Control 	18
4.3 Adjustable Sensing Range Adjusting 	23
4.3.1 Weighted Voronoi Diagram 的建構 	23
4.3.2 感測半徑調整 	27
4.3.3 延長網路生命期 	31
第五章、 模擬實驗 	34
5.1 Average Energy Consumption 	34
5.2 Network Lifetime 	35
5.3 Average Network Lifetime 	36
5.4 Average Remaining Energy 	37
5.5 Average Sensing Range 	38
5.6 Coverage Ratio 	39
第六章、 結論 	41
參考文獻 	42
附錄-英文論文	44

 
圖目錄
圖1: Energy Imbalanced Problem in One Level of Data Gathering Tree 	6
圖2: Energy Imbalanced Problem within Transmission Paths 	7
圖3: Delaunay-Triangulation-Based Scheme for Full Coverage 	8
圖4: Energy Imbalanced Problem in Delaunay-Triangulation-Based Scheme 	9
圖5: Energy Imbalance vs. Energy Balance 	17
圖6: Adjustable Sensing Range for Energy Balance 	18
圖7: Hierarchical Neighbor Graph 	19
圖8: Energy Balanced Topology Control 	22
圖9: Sensing Range Adjustment 	25
圖10: WVC 	26
圖11: WVD 	26
圖12: Special Area (SA) 	26
圖13: Division Point (DP) 	26
圖14: Overlap 	29
圖15: Overlap of Adjustable Sensor 	30
圖16: Reduce Radius of Adjustable Sensor 	30
圖17: 最小剩餘電量 	33
圖18: 空洞 	33
圖19: Average Energy Consumption 	35
圖20: Network Lifetime 	36
圖21: Average Network Lifetime 	37
圖22: Average Energy Level 	38
圖23: Average Sensing Range 	39
圖24: Coverage Ratio 	40

 
表目錄
Table 1. Simulation Setup 	34

[1] G. J. Pottie and W. J. Kaiser, “Wireless Integrate Network Sensors,” ACM Communications, vol. 43, no.5, May 2002, pp. 551–558.
[2] D. Estrin, L. Girod, G. Pottie, and M. Strivastava, “Instrumenting the World with Wireless Sensor Networks,” The 2001 IEEE International Conference on Acoustics, Speech, and Signal Processing (IEEE ICASSP), May 2001.
[3] D. Estrin and R. Govindan, “Next Century Challenges: Scalable Coordination in Sensor Networks,” The 1999 ACM International Conference on Mobile Computing and Networking (ACM MobiCom), Aug. 1999.
[4] C. Schurgers, V. Tsiatsis, S. Ganeriwal, and M. Srivastava, “Topology Management for Sensor Networks: Exploiting Latency and Density,” The 2002 ACM International Symposium on Mobile Ad Hoc Networking & Computing (ACM MobiHoc), June 2002.
[5] K. Sohrabi, J. Gao, V. Ailawadhi, and G. Pottie, “Protocols for Self-Organization of a Wireless Sensor Network,” IEEE Personal Communications Magazine, vol. 7, no. 5, Oct. 2000, pp. 16–27.
[6] A. Woo and D. Culler, “A Transmission Control Scheme for Media Access in Sensor Networks,” The 2001 ACM International Conference on Mobile Computing and Networking (ACM MobiCom), July 2001.
[7] B. Chen, K. Jamieson, H. Balakrishnan, and R. Morris, “Span: An Energy-Efficient Coordination Algorithm for Topology Maintenance in Ad Hoc Wireless Networks,” The 2001 ACM International Conference on Mobile Computing and Networking (ACM MobiCom), July 2001.
[8] C. Barrett, A. Marathe, M. Marathe, and M. Drozda, “Characterizing the Interaction Between Routing and MAC Protocols in Ad Hoc Networks,” The 2002 ACM International Conference on Mobile Computing and Networking (ACM MobiCom), June 2002.
[9] H. Yang, F. Ye and B. Sikdar, “A Dynamic Query-tree Energy Balancing Protocol for Sensor Networks,” The 2004 IEEE Wireless Communications and Networking Conference (IEEE WCNC), March 2004
[10] F. Wang and J. Liu., “Duty-Cycle-Aware Broadcast in Wireless Sensor Networks,” The 2000 IEEE Computer and Communications Societies (IEEE InfoCom), April 2009.
[11] P. Andreou, A. Pamboris, D. Zeinalipour-Yazti, P.K. Chrysanthis, and G. Samaras, “ETC: Energy-Driven Tree Construction in Wireless Sensor Networks,” The 2009 IEEE International Conference on Mobile Data Management: Systems, Services and Middleware (IEEE MDM), May 2009.
[12] T. V. Chinh and Y. Li “Delaunay-Triangulation Based Complete Coverage in Wireless Sensor Networks,” The 2009 IEEE Conference on Pervasive Computing and Communications (IEEE PerCom), March 2009.
[13] J. Wang, S. Medidi, and M. Medidi, “Energy-Efficient k-Coverage for Wireless Sensor Networks with Variable Sensing Radii,” The 2009 International Conference on Global Communications (IEEE GlobeCom), Nov. 2009.
[14] Jiong Wang, and Sirisha Medidi, “Energy Efficient Coverage with Variable Sensing Radii in Wireless Sensor Networks,” The 2007 Wireless and Mobile Computing, Networking and Communications (IEEE WiMob), Oct. 2007.
[15] F. Aurenhammer, “Voronoi Diagrams – A Survey of a Fundamental Geometric Data Structure,” ACM Computing Surveys (ACM CSUR), vol. 23, no. 3, 1991, pp. 345–405.