成功大學博碩士論文系統

簡易檢索 / 詳目顯示

回結果列表

研究生：	林世陵 Lin, Shi-Ling
論文名稱：	可支援行動元件的無線感測網路節能排程演算法 An Energy-Efficient Scheduling Algorithm with Mobility Support for Wireless Sensor Networks
指導教授：	林輝堂 Lin, Hui-Tang
學位類別：	碩士 Master
系所名稱：	電機資訊學院 - 電腦與通信工程研究所 Institute of Computer & Communication Engineering
論文出版年：	2005
畢業學年度：	93
語文別：	英文
論文頁數：	72
中文關鍵詞：	感測網路、通訊排程、行動元件支援、能源節省
外文關鍵詞：	Sensor Networks, Communication Scheduling, Mobility Support, Power Saving
相關次數：	點閱：70 下載：1
分享至:	分享至facebook 分享至twitter

查詢本校圖書館目錄查詢臺灣博碩士論文知識加值系統勘誤回報

　　無線感測網路已經被視為是一項未來的偵測技術。使用大量的無線感測元件可以提供許多廣泛的應用，例如: 追蹤小動物之活動、追蹤某種目標之狀態、環境之監測、週遭安全性之提升等等。通常感測元件用過即丟，且容易持續不斷地工作直到能源耗盡為止。因而，感測元件的能源是一項極其珍貴的資源，需要盡其所能地節省以延長整個元件的壽命。要節省能源最好的方式便是將元件的電源直接關閉，然而，被關閉的元件卻會因此而無法再屬於這個網路的一部分，導致無法幫助其他的元件傳遞資料。由此觀之，何時該關閉電源與何時該打開電源之間的權衡便顯得十分重要。在本論文當中，筆者針對連續偵測型的感測網路應用提出了一個新的排程演算法，企圖降低耗損在每個感測元件上的能源，藉以延長整個感測網路的壽命，同時利用最少的能源資源來支援網路上可行動的感測元件。這個方法對於每段經過感測元件偵測後所回傳的資料流都做了良好的排程規劃，使得它們可以在不需要忙碌的時候進入休息狀態，藉以節省能源。由於排程的建立十分迅速，因此這個排程方法非常適合應用在大型的感測網路。筆者透過模擬來評估此方法的優劣，其結果顯示無論是在建立排程時所需消耗的能源、網路所存活的時間、抑或是網路連結所存活的時間方面，此方法都優於模擬中的對照組 (也就是 Cross-Layer Scheduling Protocol 與Flexible Power Schedule Protocol)，其結果也顯示了在支援可行動的感測元件上，此方法僅僅需要額外負擔非常低的系統能源，便可達到支援網路上可行動元件的目的。

　Wireless sensor networks are considered the sensing technology of the future. Large numbers of untethered sensor nodes can be used for tracking small animals and targets, environmental monitoring, enforcing security perimeters, etc. Sensor nodes are typically disposable and expected to last until their energy drains. Therefore, energy is a very scarce resource for sensor networks and has to be conserved as far as possible in order to extend the life of the sensor nodes. The best way to conserve energy is to turn the sensor nodes off; however, since an inactive sensor node is no longer part of the network, the network can become disconnected. This creates a fundamental trade-off. In this thesis, we propose a novel scheduling algorithm for continuous monitoring application that attempts to reduce energy consumption of each sensor node and prolong lifetime of the network while providing energy-aware support of mobile nodes. The algorithm schedules flows of traffic on per time-slot basis in sensor networks. Thus, nodes can conserve energy by switching to a sleep state in slots in which they are not scheduled to be awake. The speed of schedule setup is very fast and thus appropriate for large-scale sensor networks. We evaluate the proposed approach through the use of simulations and show that the algorithm significantly outperforms comparable schemes (i.e., Cross-Layer Scheduling Protocol and Flexible Power Schedule Protocol) in terms of key metrics such as schedule setup overhead, network lifetime, and network survivability. Simulation result also shows that the overhead incurred by supporting mobile nodes is very low.

Abstract (Chinese)                                                          i
Abstract (English)                                                          iii
Acknowledgement                                                             v
Table of Contents                                                           vi
List of Tables                                                              viii
List of Figures                                                             ix
Chapter 1  Introduction                                                     1
Chapter 2  Backgrounds and Related Works                                    7
     2.1  Overview of Wireless Sensor Network                               7
          2.1.1  Sensor Networks VS. Traditional Ad-Hoc Networks            9
          2.1.2  Major Power Consumption Source                             10
          2.1.3  Major Application                                          11
     2.2  Several Significant Scheduling Schemes for Continuous Monitoring
          Sensor Networks                                                   13
          2.2.1  Energy-Aware TDMA-Based MAC Slot Assignment Protocol       13
          2.2.2  Max-Min Fair Collision-Free Scheduling Protocol            14
          2.2.3  Flexible Power Scheduling Protocol                         16
          2.2.4  Cross-Layer Scheduling Protocol                            18
     2.3  XYZ: A New Wireless Sensor Node Architecture based around the 
          2.4GHz IEEE 802.15.4 and Zigbee compliant Radio                   20
Chapter 3  An Energy-Efficient Scheduling Algorithm with Mobility Support   24
     3.1  The Proposed Approach                                             25
          3.1.1  The Basic Idea of the Proposed Algorithm                   29
          3.1.2  The Details of the Proposed Algorithm                      33
          3.1.3  Mobile Node Support Mechanism                              42
     3.2  The Advantages of the Proposed Approach                           52
Chapter 4  Performance Evaluation                                           54
     4.1  Simulation Environment and Parameters                             54
     4.2  Simulation Results and Analysis                                   57
          4.2.1  Schedule Setup Overhead                                    57
          4.2.2  Network Lifetime                                           59
          4.2.3  Network Survivability                                      61
          4.2.4  Mobile Node Support Overhead                               63
Chapter 5  Conclusions                                                      65
References                                                                  67
                                    

[1] V. Raghunathan, C. Schurgers, S. Park, and M. Srivastava,“Energy aware wireless microsensor networks,”in IEEE Signal Processing Magazine, pp. 40--50, Mar. 2002.

[2] Bult, K., A. Burstein, D. Chang, M. Dong, M. Fielding, E. Kruglick, J. Ho, F. Lin, T.-H. Lin, W.J. Kaiser, H. Marcy, R. Mukai, P. Nelson, F. Newberg, K.S.J. Pister, G. Pottie, H. Sanchez, O.M. Stafsudd, K.B. Tan, C.M. Ward, S. Xue, and J. Yao,“Low power systems for wireless microsensors,”1996. Pp. 17–21 in Proceedings of IEEE International Symposium on Low Power Electronics and Design, Monterrey, California.

[3] Khaled Arisha, Moustafa Youssef, and Mohamed Younis,“Energy-Aware TDMA-Based MAC for Sensor Networks,”Proceedings of the IEEE Integrated Management of Power Aware Communications, Computing and Networking (IMPACCT 2002), New York City, New York, May 2002.

[4] Sridharan and B. Krishnamachari,“Max-min fair collision-free scheduling for wireless sensor networks,”to be presented at the Workshop on Multihop Wireless Networks (MWN’04) to be held in conjunction with the IEEE International Performance Computing and Communications Conference (IPCCC), April 2004.

[5] Barbara Hohlt, Lance Doherty, Eric Brewer,“Flexible Power Scheduling for Sensor Networks,”Proceedings of the third international symposium on Information Processing in Sensor Networks (IPSN), Oral presentation session III, Pages: 205 - 214, 2004.

[6] Mihail L. Sichitiu,“Cross-Layer Scheduling for Power Efficiency in Wireless Sensor Networks,”in Proceedings of IEEE INFOCOM, 2004, (Hong Kong, PRC), March 2004.

[7] Embedded Networks and Applications Laboratory Yale University. http://www.eng.yale.edu/enalab/.

[8] Inc. Cogent Computer Systems. http://www.cogcomp.com/.

[9] F. Akyildiz, W. Su, Y. Sankarasubramaniam, and E. Cayirci,“A survey on sensor networks,”IEEE Communications Magazine, 40(8):102-114, August 2002.

[10] Wei Ye, John Heidemann, Deborah Estrin,“An Energy-Efficient MAC Protocol for Wireless Sensor Networks,”In 21st Conf. of the IEEE Computer and Communications Soc. (INFOCOM 2002), pages 1567--1576, June 2002.

[11] Chipcon CC2420 datasheet, http://www.chipcon.com/.

[12] D. Lymberopoulos and A. Savvides,“XYZ A Motion-Enabled, Power Aware Sensor Node Platform for Distributed Sensor Network Applications,”Work in Progress, ENALAB, Yale University, 2005.

[13] F. Akyildiz, W. Su, Y. Sankarasubramaniam, and E. Cayirci,“Wireless Sensor Networks: A Survey,”Computer Networks, 38(4):393–422, March 2002.

[14] Mainwaring, J. Polastre, R. Szewczyk, and D. Culler,“Wireless sensor networks for habitat monitoring,”in Proceedings of the First ACM International Workshop on Wireless Sensor Networks and Applications, Atlanta, GA, Sept. 2002.

[15] Cerpa, J. Elson, D.Estrin, L. Girod, M. Hamilton, and J. Zhao,“Habitat monitoring: Application driver for wireless communications technology,”in Proceedings of the ACM SIGCOMM Workshop on Data Communications in Latin America and the Caribbean, 2001.

[16] R. Min, M. Bhardwaj, N. Ickes, A. Wang, and A. Chandrakasan,“The hardware and the network: Total-system strategies for power aware wireless microsensors,”in Proceedings of the IEEE CAS Workshop on Wireless Communications and Networking, Pasadena, CA, USA, Sep. 2002.

[17] Sinha, A. Chandrakasan,“Dynamic power management in wireless sensor networks,”IEEE Design and Test of Computers (2001) 62–75.

[18] OKI semiconductor: 32-bit ARM Based General Purpose Microcontrollers ML67Q5002. http://www2.okisemi.com/us/docs/intro-9980.html.

[19] T. van Dam and K. Langendoen,“An Adaptive Energy-Efficient MAC Protocol for Wireless Sensor Networks,”in ACM SenSys 2003, November 2003.

[20] K. Sohrabi, J. Gao, V. Ailawadhi, and G. J. Pottie,“Protocols for Self-Organization of a Wireless Sensor Network,”IEEE Personal Communications, vol. 7, no. 5, pp. 16–27, October 2000.

[21] V. Rajendran, K. Obraczka, and J. J. Garcia-Luna-Aceves,“Energy-Efficient, Collision-Free Medium Access Control for Wireless Sensor Networks,”in ACM SenSys 2003, November 2003.

[22] A. Cerpa and D. Estrin,“ASCENT: Adaptive Self-Configuring sEnsor Networks Topologies,”in Proceedings of IEEE INFOCOM 2002, June 2002.

[23] C. Guo, L. C. Zhong, and J. M. Rabaey,“Low Power Distributed MAC for Ad Hoc Sensor Radio Networks,”in IEEE GlobeCom 2001, November 2001.

[24] J. M. Rabaey, J. Ammer, T. Karalar, S. Li, B. Otis, M. Sheets, and T. Tuan,“PicoRadios for Wireless Sensor Networks — The Next Challenge in Ultra-Low Power Design,”in IEEE International Solid-State Circuits Conference (ISSCC) 2002, February 2002.

[25] C. Schurgers, V. Tsiatsis, S. Ganeriwal, and M. Srivastava,“Topology Management for Sensor Networks: Exploiting Latency and Density,”in ACM MobiHoc 2002, June 2002.

[26] C. Schurgers, V. Tsiatsis, S. Ganeriwal, and M. Srivastava,“Optimizing Sensor Networks in the Energy-Latency-Density Design Space,”IEEE Transactions on Mobile Computing, vol. 1, no. 1, pp. 70–80, January-March 2002.

[27] M. J. Miller and N. H. Vaidya,“Minimizing Energy Consumption in Sensor Networks Using a Wakeup Radio,”in IEEE WCNC 2004, March 2004.

[28] M. J. Miller,“Minimizing Energy Consumption in Sensor Networks Using a Wakeup Radio,”Master’s thesis, University of Illinois at Urbana-Champaign, November 2003.

[29] S. R. Madden, M. J. Franklin, J. M. Hellerstein, and W. Hong,“The design of an acquisitional query processor for sensor networks,”in Proceedings of SIGMOD’03, San Diego, CA, June 2003.

[30] A. Mainwaring, J. Polastre, R. Szewczyk, D. Culler, J. Anderson,“Wireless sensor networks for habitat monitoring,”in WSNA 2002, Atlanta, GA, USA, September 2002.

[31] W. S. Conner, L. Krishnamurthy, and R. Want,“Making everyday life a little easier using dense sensor networks,”in Proceedings of ACM Ubicomp 2001, Atlanta, GA, Oct. 2001.

[32] Sensicast Systems: http://www.sensicast.com/.

[33] Digital Sun, Inc.: http://digitalsun.com/.

[34] C. Florens and R. McEliece,“Scheduling algorithms for wireless ad-hoc sensor networks,”in Proceedings of the IEEE Global Telecommunications Conference 2002, Nov. 2002.

[35] C. Florens and R. McEliece,“Packet distribution algorithms for sensor networks,”in Proceedings of IEEE INFOCOM 2003, April 2003.

[36] J. M. Rabaey, M. J. Ammer, J. L. da Silva Jr., D. Patel, and S. Roundy,“PicoRadio Supports Ad Hoc Ultra-Low Power Wireless Networking,”IEEE Computer, July 2000.

[37] R. Shah and J. Rabaey,“Energy Aware Routing for Low Energy Ad Hoc Sensor Networks,”in the. Proceedings of the IEEE Wireless Communications and Networking Conference (WCNC), Orlando, FL, March 2002.

[38] A. Boukerche, X. Cheng, and J. Linus,“Energy-Aware Data-Centric Routing in Microsensor Networks,”in Proceedings of ACM MSWiM, pp. 42-49, 2003.

[39] ZigBee Alliance: http://www.zigbee.org/.

[40] G. J. Pottie, W. J. Kaiser,“Wireless Integrated Network Sensors,”Communications of the ACM, vol. 4, no. 5, May 2000.

[41] D. Tian and N. D. Georganas,“A Coverage-Preserving Node Scheduling Scheme for Large Wireless Sensor Networks,”in Proceedings of the first ACM international workshop on Wireless sensor networks and applications 2002, October 2002.

[42] Chalermek Intanagonwiwat, Ramesh Govindan, Deborah Estrin, John Heidemann, Fabio Silva,“Directed Diffusion for Wireless Sensor Networking,”IEEE/ACM Transactions on Networking, Vol. 11, No. 1, February 2003 pp.2-16.

[43] Charles E. Perkins and Elizabeth M. Royer,“Ad hoc On-Demand Distance Vector Routing,”in Proceedings of the 2nd IEEE Workshop on Mobile Computing Systems and Applications, New Orleans, LA, February 1999, pp. 90-100.

[44] D. Braginsky and D. Estrin,“Rumor routing algorithm for sensor networks,”in First ACM International Workshop on Wireless Sensor Networks and Applications, 2002.

[45] Chris Karlof and David Wagner,“Secure Routing in Wireless Sensor Networks: Attacks and Countermeasures,”to appear First IEEE International Workshop on Sensor Network Protocols and Applications, May 2003.

[46] M. A. Youssef, M. F. Younis, K. A. Arisha,“A constrained shortest-path energy-aware routing algorithm for wireless sensor networks,”in Proceedings of the IEEE Wireless Communications and Networking Conference 2002 (WCNC 2002), vol. 2, pp. 794-799, March 2002.

[47] D. Tian and N. D. Georganas,“Energy Efficient Routing with Guaranteed Delivery in Wireless Sensor Networks,”in Proceedings of the IEEE Wireless Communications and Networking Conference (WCNC2003), New Orleans, March 2003.

[48] Dragan Petrovic, Rahul C. Shah, Kannan Ramchandran and Jan Rabaey,“Data Funneling: Routing with Aggregation and Compression for Wireless Sensor Networks,”IEEE Sensor Network Protocols and Applications (SNPA) 2003, Anchorage, AL, May 2003.

[49] W. R. Heinzelman, A. Chandrakasan, and H. Balakrishnan,“Energy efficient communication protocol for wireless microsensor networks,”in 33rd Annual Hawaii International Conference on System Sciences, 2000, pp. 3005–3014.

[50] Jan Blumenthal, Matthias Handy,“Wireless Sensor Networks - New Challenges in Software Engineering,”in Proceedings of the IEEE Emerging Technologies and Factory Automation, 2003 (ETFA '03), Volume: 1, Sept. 16-19, 2003.

校內：2008-09-06公開
校外：2008-09-06公開

簡易檢索 / 詳目顯示

相關論文