近年來，無線感測網路技術因具有低建置成本的優點，而被廣泛使用於各種應用之中。基於感測器有限電力的特性，目前已有許多研究探討如何在有限電量下，延長無線感測網路生命週期。其中，以法團系統(Quorum System)設計感測器醒睡排程機制，除了可達到感測器的節能的效果之外，感測器間更能不經溝通而確保彼此的會面機會。然而，感測器根據Quorum System執行感測任務的過程中，將存在會面閒置的問題。為了提升感測器的省電效率，本論文設計一電量平衡會面機制，除了可確保感測器間的會面機會外，更可根據感測器的剩餘電量與彼此間的會面方式(直接會面或間接會面)，平衡感測器間的剩餘電量，並改善傳統Quorum System的省電效益。根據實驗顯示，相較於傳統的Quorum System排程機制，本論文所提出的電量平衡會面機制，可有效減少感測器會面閒置時槽的數量，並藉由感測器剩餘電量的平衡，延長無線感測網路生命期。

In recent years, Wireless sensor network technology has the advantage of low construction costs, therefore, is widely used in a variety of applications. Characteristics of sensor based on limited power, there are already many studies on how to extend wireless sensor network life cycle under the limited power. Including, the scheduling mechanism of sensors designed by the Quorum System, In addition to sensors energy saving effects can be achieved, between the sensors without communication still can make sure each other's meetings. However, the sensor in accordance with Quorum System, which carries out sensing tasks in the process, there will be meeting problems. In order to improve the sensor's power efficiency, in this paper, we design Energy Balanced Rendezvous Mechanisms for Wireless Sensor Networks. Apart from the meeting opportunity of between sensors making sure, also, according to the remaining energy and the way of meeting with each other (meet directly or indirectly). Mechanisms can balance the remaining energy of sensors, and improve energy efficiency of traditional Quorum System. An experiment shows that compared to the traditional Quorum System scheduling mechanism, we proposed Energy Balanced Rendezvous Mechanisms can effectively reduce the number of sensors of the idle time slots, and by the balance of remaining energy of sensors, to extend the lifetime of wireless sensor networks.

目錄
圖目錄	V
表目錄	VII
第一章、簡介	1
第二章、網路環境與問題描述	5
2.1	網路環境	5
2.2	問題描述	7
第三章、概述	11
第四章、EBRM演算法	19
4.1	初始階段	19
4.2	會面安排階段	23
第五章、ELRM演算法	35
第六章、模擬實驗	41
6.1	模擬環境	41
6.2	模擬結果	42
第七章、結論	54
參考文獻	55
附錄-英文論文	57

圖目錄
圖1. Grid-based Quorum System的結構範例。	6
圖2. Grid-based Quorum System 的範例。	12
圖3. Quorum System特性，保證感測器彼此會面的示意圖。	13
圖4. 基於圖2，採用EQS [3]後，具「間接傳輸」概念的Grid-based Quorum System。	14
圖5. 接續圖4，s_l與s_i間接資料轉傳之會面示意圖。	15
圖6. 基於圖2，採用本研究EBRM演算法後，具「間接會面」及「電量平衡」特性的Grid-based Quorum System。	17
圖7. 基於具「間接會面」特性之Quorum System運作模式，感測器採用EQS[3]與EBRM機制後，各感測器之剩餘生命週期趨勢圖。	18
圖8. EBRM機制設計概念。	20
圖9. Grid-based Quorum系統與感測器剩餘電量。	22
圖10. 排序感測器彼此間的會面路徑。	23
圖11. 相仿Quorum圖與會面路徑相關示意圖。	25
圖12. 基於電量平衡會面機制的會面路徑資訊。	30
圖13. 基於電量平衡會面機制的第二回合評估示意圖。	33
圖14. Algorithm for EBRM。	34
圖15. 在ELRM中所強調的鏈結傳輸品質示意圖。	36
圖16. Algorithm for ELRM。	40
圖17. Quorum Size 3×3時，鄰近感測器密度對初始耗能的比較。	43
圖18. Quorum Size 5×5時，鄰近感測器密度對初始耗能的比較。	44
圖19. Quorum Size 3×3時，封包遺失率對耗能的比較。	45
圖20. Quorum Size 5×5時，封包遺失率對耗能的比較。	46
圖21. Quorum Size 3×3時，可調式權重值對網路電量平衡的比較。	47
圖22. Quorum Size 5×5時，可調式權重值對網路電量平衡的比較。	48
圖23. Quorum Size 3×3時，可調式權重值對延長網路生命週期的比較。	50
圖24. Quorum Size 5×5時，可調式權重值對延長網路生命週期的比較。	51
圖25. Quorum Size 3×3、4×4、5×5時，鄰近感測器密度對發現延遲時間的比較。	52
圖26. Quorum Size 3×3、4×4、5×5時，鄰近感測器密度對發現延遲耗能的比較。	53

表目錄
表 1：模擬相關參數	41

[1]	Y. C. Tseng, C. S. Hsu, and T. Y. Hsieh, “Power-Saving Protocols for IEEE 802.11-Based Multi-Hop Ad Hoc Networks,” IEEE INFOCOM, Jun. 2002.
[2]	C. M. Chao and J. P. Sheu, “An Adaptive Quorum-Based Energy Conserving Protocol for IEEE 802.11 Ad Hoc Networks,” IEEE Transactions on Mobile Computing, vol. 5, no. 5, pp. 560–570, May 2006.
[3]	D. Zhang, T. He, F. Ye, Ganti, R. K. Ganti, and H. Lei, “EQS: Neighbor Discovery and Rendezvous Maintenance with Extended Quorum System for Mobile Sensing Applications,” IEEE ICDCS, Jun. 2012.
[4]	M. Maekawa, “A Square Root N Algorithm for Mutual Exclusion in Decentralized Systems,” ACM Transactions on Computer Systems, vol. 3, no. 2, pp. 145–159, May 1985.
[5]	W. S. Luk and T. T. Wong, “Two New Quorum based Algorithms for Distributed Mutual Exclusion,” IEEE ICDCS, May 1997.
[6]	S. D. Lang and L. J. Mao, “A Torus Quorum Protocol for Distributed Mutual Exclusion,” IEEE ICDCS, Oct. 1998.
[7]	D. Malkhi and M. K. Reiter, “Byzantine Quorum Systems,” ACM STOC, May 1997.
[8]	D. Malkhi, M. K. Reiter, and R. N. Wright, “Probabilistic Quorum Systems,” ACM PODC, Aug. 1997.
[9]	W. Ye, J. Heidemann, and D. Estrin, “An Energy-Efficient MAC Protocol for Wireless Sensor Networks,” IEEE INFOCOM, Jun. 2002.
[10]	T. van Dam, and	 K. Langendoen, “An Adaptive Energy-Efficient MAC Protocol for Wireless Sensor Networks,” ACM SenSys, Nov. 2003.
[11]	B. Das and V. Bharghavan, “Routing in Ad-hoc Networks Using Minimum Connected Dominating Sets,” IEEE ICC, Jun. 1997.
[12]	J. Wu and M. Gao, “On Calculating Power-Aware Connected Dominating Sets for Efficient Routing in Ad Hoc Wireless Networks,” IEEE ICPP, Sep. 2001.
[13]	D. Skeen, “A Quorum-Based Commit Protocol,” Cornell University, Feb. 1982.