臺灣博碩士論文加值系統

在無線感測器網路(WSN)中，環境監控(monitoring)程式是很常見的應用，透過取樣環境中所需的資訊，進一步分析並還原出觀測對象的變化，像是戰場上藉由聲音判斷敵軍動向，或是觀測某地區氣象資訊，例如溫度或濕度等等。
為了保證監控程式能正確還原出觀測的資訊，每段時間內整個網路的取樣資料總數一定至少要滿足某個下限；此外，當網路中有某顆節點(node)耗盡電量，就可能會造成網路連結中斷，導致某些取樣資料無法順利回傳，為了延後這種現象發生的時間點，延長整個系統的使用壽命，如何平衡每顆感測器上的剩餘電量就是個非常重要的議題；因此，本篇論文中針對這兩點提出了問題：如何在滿足監控程式所需取樣總數的前提之下，藉由妥善分配每顆感測器上的取樣數目，來平衡整個網路的剩餘電量。
為了解決此問題，論文中提出了幾個解法，設法做出最佳分配來平衡整個網路的電量，並降低求解過程中在CPU運算量、記憶體、封包傳送上所需的額外負擔；在論文中同時透過證明，保證解法一定能得到最佳解(optimal solution)，即使在無法得到最佳解的情況下也能找出誤差的上限(error bound)。
最後透過模擬實驗的結果，印證出此篇論文提出的解法確實能做出最佳分配來平衡網路中每顆感測器的電量，並有效降低運算過程所需的額外負擔。

ABSTRACT ii
Table of Contents iii
List of Figures iv
Chapter 1 Introduction 1
Chapter 2 The Data Collection Problem 5
2.1 System Model 5
2.2 Problem Statement 8
Chapter 3 MCE-p Algorithm 9
3.1 Energy Table and Decision Table 10
3.2 Distributed Computation 10
3.3 Sampling Schedule Assignment 12
3.4 Design Considerations 16
Chapter 4 Performance Analysis 18
4.1 Optimality Proof 18
4.2 Error Bound Analysis 22
4.3 Time Complexity Analysis 27
Chapter 5 Performance Improvement 30
5.1 Q-MCE 31
5.2 Optimality Proof 34
Chapter 6 Experiment 38
6.1 Simulation Setup 38
6.2 Performance Evaluation of Centralized Algorithm 39
6.3 Performance Evaluation of Distributed Algorithm 42
Chapter 7 Related Work 44
Chapter 8 Conclusion 46
Bibliography 47

[1] T. He, S. Krishnamurthy, L. Luo, T. Yan, L. Gu, R. Stoleru, G. Zhou, Q. Cao, P. Vicaire, J. A. Stankovic, T. F. Abdelzaher, J. Hui, and B. Krogh, “Vigilnet: An integrated sensor network system for energy-efficient surveillance,” ACM TOSN, vol. 2, no. 1, pp. 1–38, 2006.
[2] N. Xu, S. Rangwala, K. K. Chintalapudi, D. Ganesan, A. Broad, R. Govindan, and D. Estrin, “A wireless sensor network for structural monitoring,” in SenSys 2004.
[3] “Tropical atmosphere ocean project,” http://www.pmel.noaa.gov/tao/proj over/sampling.html.
[4] A. J. Jerri, “The shannon sampling theorem - its various extensions and applications: A tutorial review,” Proceedings of the IEEE, vol. 65, no. 11, pp. 1565–1596, 1977.
[5] Y. Yu and V. K. Prasanna, “Energy-balanced task allocation for collaborative processing in wireless sensor networks,” Mobile Networks and Applications, vol. 10, no. 1-2, pp. 115–131, 2005.
[6] M. Ma and Y. Yang, “Clustering and load balancing in hybrid sensor networks with mobile cluster heads,” in QShine 2006, 2006.
[7] Edward T.-H. Chu, Huang-Yi Yu, Tai-Yi Huang, Hsin-Ju Lee, Chung-Ta King, "Energy-Balanced Sampling Workload Allocation in Wireless Sensor Networks", Technical Report, 2006. http://edwardchu.tw.googlepages.com/sensor.pdf
[8] V. Shnayder, M. Hempstead, B. Chen, G. W. Allen, and M. Welsh, “Simulating the power consumption of large-scale sensor network applications,” in SenSys ’04: Proceedings of the 2nd international conference on Embedded networked sensor systems. New York, NY, USA: ACM, 2004, pp. 188–200.
[9] P. Levis, N. Lee, M. Welsh, and D. Culler, “Tossim: accurate and scalable simulation of entire tinyos applications,” in SenSys ’03: Proceedings of the 1st international conference on Embedded networked sensor systems. NewYork,NY, USA: ACM, 2003, pp. 126–137.
[10] Y.-F. Wong, L.-H. Ngoh, and W.-C. Wong, “An adaptive wakeup scheme to support fast routing in sensor networks,” in PE-WASUN ’05: Proceedings of the 2nd ACM international workshop on Performance evaluation of wireless ad hoc, sensor, and ubiquitous networks. New York, NY, USA: ACM, 2005, pp. 18–24.
[11] A. Okura, T. Ihara, and A. Miura, “Branch aggregation multicast (bam): An energy efficient and highly compatible multicast protocol for wireless sensor networks,” IEICE - Transactions on Information and Systems, vol. E89-D, no. 5, pp. 1633–1643, 2006.
[12] A. T. Hoang and M. Motani, “Collaborative broadcasting and compression in cluster-based wireless sensor networks,” ACM Transactions on Sensor Networks, vol. 3, no. 3, p. 17, 2007.
[13] W. R. Heinzelman, A. Chandrakasan, and H. Balakrishnan, “Energy-efficient communication protocol for wireless microsensor networks,” in HICSS ’00: Proceedings of the 33rd Hawaii International Conference on System Sciences. Washington, DC, USA: IEEE Computer Society, 2000, p. 8020
[14] V. Srinivasan, C. Chiasserini, and P. S. Nuggehalli, “Optimal rate allocation for energy-efficient multipath routing in wireless ad hoc networks,” IEEE TWC, vol. 3, no. 3, pp. 891–899, 2004.
[15] J. Zhu, S. Chen, B. Bensaou, and K. Hung, “Tradeoff between lifetime and rate allocation in wireless sensor networks: A cross layer approach.” in INFOCOM 2007.
[16] J. Li and S. Dey, “Lifetime optimization for multi-hop wireless sensor networks with rate distortion constraints,” in SPAWC 2006.
[17] J. Chang and L. Tassiulas, “Maximum lifetime routing in wireless sensor networks,” IEEE/ACM TON, vol. 12, no. 4, pp. 609–619, 2004.
[18] R. Madan and S. Lall, “Distributed algorithms for maximum lifetime routing in wireless sensor networks,” IEEE TWC, vol. 5, no. 8, pp. 2185–2193, 2006.
[19] X. Wang, G. Xing, Y. Zhang, C. Lu, R. Pless, and C. Gill, “Integrated coverage and connectivity configuration in wireless sensor networks,” in SenSys 2003.
[20] H. Liu, P., and X. Jia, “Maximal lifetime scheduling for sensor surveillance systems with k sensors to one target,” IEEE TPDS, vol. 17, no. 12, pp. 1526–1536, 2006.