臺灣博碩士論文加值系統

　　無線感測網路是近幾年來在學術界最熱門的研究議題之一。由於應用環境通常是惡劣且不易置換電池的，所以如何省電已達到最長網路存活時間是無線感測網路的一個非常重要的議題。

　　連續偵測是無線感測網路的眾多應用之ㄧ，網路中每個感應器節點必須定期傳輸一個自身偵測到的事件回到基地台做資料處理。在論文中，針對無線感測網路的連續偵測應用我們提出了一個新的省電且無碰撞的排程演算法，讓網路中每個感應器節點在每個回合中，只有在需要時才處於運作狀，其他時間則可以處於耗電量較低的睡眠模式已達到省電的效果。

　Wireless sensor networks is one of the hottest academic topics in recent years. In usually, it’s hard to replace the batteries due to its tough application environment. So, energy-saving is one of the important issues in wireless sensor network research field.

　Continuous monitoring is one of application for wireless sensor networks. In this application, each sensor node should send its sensing data forward base station in a cycle round periodically. We propose a novel energy-efficient and collision free scheduling algorithm for continuous monitoring application in this thesis. We schedule the working duration for each sensor node and let it be at active mode just when needed and save energy by letting each sensor node to be at sleep mode which consumes less energy than active mode in the other leisure time.

Abstract (English)--------i
Abstract (Chinese)--------iii
Acknowledgement--------iv
Table of Contents--------v
List of Figures--------vii
Chapter 1--------1
Chapter 2--------4
2.1 Distance Vector Protocol [30]--------4
2.2 Packets Distribution Algorithms for Wireless Sensor Networks [8]--------5
2.2.1 Mirroring the schedule--------7
2.3 Application : continuous monitoring [1]--------8
2.4 Cross-Layer Schedule--------9
2.4.1 The state diagram of a sensor node--------9
2.4.2 The result of Cross-Layer Schedule--------14
2.4.3 The drawbacks of Cross-Layer Schedule--------14
2.5 Problem : transmission collision--------16
Chapter 3--------17
3.1 Topology : spanning tree with shortest path--------17
3.2 The presupposition of the scheduling algorithm--------18
3.3 Schedule table--------18
3.3.1 States in the schedule table--------19
3.4 Schedule rule--------20
3.5 A novel Energy-Efficient and Collision-Free scheduling algorithm for wireless sensor networks--------20
3.5.1 Communication Unit--------21
3.5.2 An example of a network with EECF schedule--------25
3.5.3 Schedule setup phase--------25
Chapter 4--------47
4.1 Bi-directional transmission mechanism--------47
4.1.1 Bi-directional transmission scheme in a cycle--------48
4.1.2 How to mirror EECF schedule--------48
4.1.3 Why we can just mirror EECF schedule as data distribution--------50
4.1.4 Compare the mirroring performance with Packet Distribution Algorithm--------51
4.2 Retransmission mechanism--------52
4.3 Reconfiguration mechanism--------52
4.4 Support mobile nodes--------56
4.5 The performance about transmission without Communication Unit--------59
Chapter 5: Simulation Result--------62
5.1 Assumptions 62
5.1.1 Parameters assumptions 63
5.2 Simulation result 64
5.2.1 Time slots consumption per cycle 65
5.2.2 Collision times per cycle 67
5.2.3 Network lifetime 67
5.2.4 Mobile node support mechanism overhead--------74
Chapter 6--------76
Reference --------78

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

[2]Azzedine Boukerche, Xiuzhen Cheng, and Joseph Linus, “Energy-Aware Data-Centric Routing in Microsensor Networks” MSWiM’03, September 19, 2003, San Diego, California, USA.2003 ACM.

[3]D. Estrin, et. al., http://nesl.ee.ucla.edu/tutorials/mobicom02

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

[5]Jim Chou, Dragan Petrovic, Kannan Ramchandran, “A Distributed and Adaptive Signal Processing Approach to Reducing Energy Consumption in Sensnor Networks, ” IEEE Infocom, San Francisco, CA, March 30 - April 3, 2003.

[6]H‥useyin ‥Ozg‥ur Tan and ˙Ibrahim K‥orpeoˇglu, “Power Efficient Data Gathering and Aggregation in Wireless Sensor Networks” ACM SIGMOD Record, Volume 32, Issue 4 December 2003.

[7]Mihail L. Sichitiu, “Cross-Layer Scheduling for Power Efficiency in Wireless Sensor Networks,” INFOCOM 2004, Mar., pp. 1740 – 1750, vol.3

[8]C’edric Florens and Robert McEliece, “Packet Distribution Algorithm for Sensor Networks” (Infocom2003)

[9]Venkatesh Rajendran, Katia Obraczka, J.J. Garcia-Luna-Aceves, “Energy-Efficient, Collision-Free Medium Access Control for Wireless Sensor Networks”,SenSys’03, November 5–7, 2003, Los Angeles, California, USA. pp.181-192.

[10]Wei Ye, John Heidemann, and Deborah Estrin, “An Energy-Efficient MAC Protocol for Wireless Sensor Networks” (IEEE INFOCOM 2002)

[11]D. E. Culler, J. Hill, P. Buonadonna, R. Szewczyk, and A. Woo,“A network-centric approach to embedded software for tiny devices,” in Proc. of the First International Workshop on Embedded Software (EMSOFT), Oct. 2001.

[12]Dimitrios Lymberopoulos and Andreas Savvides. ”XYZ:A Motion-Enabled, Power Aware Sensor Node Platform”

[13]Amit Sinha and Anantha Chandrakasan, ”Dynamic Power Management in Wireless Sensor Networks”, (IEEE Design & Test of Computers)

[14]Andrej Bogdanov Elitza Maneva? Samantha Riesenfeld, ”Power-aware Base Station Positioning ”, IEEE INFOCOM 2004

[15]Chiranjeeb Buragohain, Divyakant Agrawal, and Subhash Suri, ”Power Aware Routing for Sensor Databases”, Proceedings of IEEE INFOCOM 2005, March 13-17, 2005 Miami

[16]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.

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

[18]Moustafa A. Youssef*, Mohamed F. Younis* and Khaled A. Arisha, ”A Constrained Shortest-Path Energy-Aware Routing Algorithm for Wireless Sensor Networks”, Proceedings of Wireless Communications and Networking Conference, 2002. WCNC2002. 2002 IEEE,17-21 March 2002 , pp.794 - 799 vol.2 ,Volume: 2.

[19]Naoto Kimura, Shahram Latifi. ”A Survey on Data Compression in Wireless Sensor Networks, ” itcc, vol. 02, no. 2, pp. 8-13, International 2005.

[20]D. Petrovic, R. C. Shah, K. Ramchandran, and J. Rabaey, "Data Funneling: Routing with Aggregation and Compression for Wireless Sensor Networks," IEEE ICC Int. Workshop on Sensor Network Protocols and Applications, 2003 (submitted).

[21]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

[22]Jeremy Elson , Kay Romer, ”Time Synchronization for Wireless Sensor Networks”, Wireless sensor networks: a new regime for time synchronization, ACM SIGCOMM, Computer Communication Review, v.33 n.1, p.149-154, January 2003

[23]Jana van Greunen, Jan Rabaey, ”Lightweight Time Synchronization for Sensor Networks”, Proceedings of the 2nd ACM international conference on Wireless sensor networks and applications, September 2003.

[24]A. Woo and D. E. Culler, “A transmission control scheme for media access in sensor networks,” in Proc. ACM MOBICOM, July 2001.

[25]S. R. Madden, M. J. Franklin, J. M. Hellerstein, and W. Hong, “The design of an acquisitional query processor for sensor networks,” in In Proc. of (SIGMOD’03), San Diego, CA, June 2003. [Online]. Available: http://www.cs.berkeley.edu/ madden/acqp.pdf

[26]S. Singh, M. Woo, and C. S. Raghavendra, “Power-aware routing in mobile ad hoc networks,” in Mobile Computing and Networking, 1998, pp. 181–190. [Online]. Available: citeseer.nj.nec.com/singh98poweraware.html

[27]M. W. Subbarao, “Dynamic power-conscious routing for MANETS: an initial approach,” in IEEE Vehicular Technology Conference, 1999, pp.1232–1237.

[28]Charles Song, “IEEE 802.11 MAC Simulator with DCF and Power Saving Mode”. Available: http://www.cs.umd.edu/Honors/reports/falcon-research.pdf

[29]K. Xu, M. Gerla, and S. Bae, “How effective is the IEEE 802.11 RTS/CTS handshake in ad hoc networks?” in Proc. of IEEE Globecom 2002, Taipei, Taiwan, R.O.C., Nov. 17-21 2002.

[30]http://www.internetworktraining.com/kbase/routing_protocols/distance_vector.html

[31]http://en.wikipedia.org/wiki/Link-state_routing_protocol