臺灣博碩士論文加值系統

近幾年來，由於微機電系統和無線通訊技術的日益發展，使得我們已經可以生產出體積越小且成本越低廉，而且功能越多的無線感測器（Wireless sensor）,為數眾多的無線感測器可以佈署成一個無線感測器網路，依不同的需求，應用在環境監控、居家照護或保全以及軍事上。

無線感測器網路運作的根本是在能源，通常都是將電池嵌入在無線感測器內部，但是受限於所處的環境，無法再行充電。現行存在的路由協定可分為主動式（Proactive routing protocol）、被動式（Reactive routing protocol）和複合式（Hybrid routing protocol）三種。無論那一種路由協定都有其優缺點，不管那一種路由協定，都是在無線感測器網路運行之同時就開始運作，直到運行中的路由協定無法再支持整個無線感測器網路為止，也就是代表壽命終止。但是，這裡產生一個問題：就是原先施行在無線感測器網路的路由協定因為原始設計的已有的缺點或是已經達到預期無線感測器網路的壽命而告結束。只是路由協定無法支持無線感測器網路的運作，不代表所有的無線感測器的電源已經全數耗損完畢。而且依需求無線感測器本身電源低於能發送資料的能力時，即便是能繼續感測資訊，但是也等於是處於無用狀態，且無法負責轉送資料的任務。無論那一種路由協定，就有可能會發生當由觀察者對遠端的無線感測器發出查詢信號後，最後卻會發生查詢到的資料無法回傳。

本文提出的策略係利用Redundancy node和Dual routing protocol協定技術，以確保資訊傳輸之可靠性。Redundancy node是指當我們在佈署無線感測器網路時，可以將無線感測器網路區分成兩個部份，並且使用不同的路由協定。一部份是當無線感測器網路一開始佈署上去就會運行的路由協定；另一部份則是處於休眠（sleep）狀態的無線感測器，只有當有需要的時後，才會喚醒這些休眠中的無線感測器。Dual routing protocol是將兩種不同的路由協定分別設計在這兩部份的無線感測器內，利用這兩種不同路由協定的優點，來完成資訊正確傳送的任務。

我們設定的環境是當無線感測器網路經過長時間的使用之後，會造成這些無線感測器的保有的電源並不相同。可能有的無線感測器因為任務過於頻繁以致電源消耗的很快，有的無線感測器可能工作量比較少，所以擁有較高的電源。假如我們查詢對遠端的無線感測器發出查詢信號後所使用的路由路徑，很不幸有一個無線感測器以上，可能因為電源不足，而只能將查詢到的資料，從觀察者傳到目標感測器。此時，目標感測器會根據，從觀察者到目標感測器之間傳送查詢訊息時，所順便收集這條路徑所有無線感測器的電源儲存狀況，做為判斷。假如經過判斷，目標無線感測器無法再利用原來的路由路徑將資料回傳到觀察者。此時，目標無線感測器就會發出廣播訊息給鄰居。當鄰居中，有一個是休眠狀態而且又是跑第二種路由協定時。此時這個休眠無線感測器就會被喚醒。這個被喚醒的無線感測器就會建立出一條路由路徑，以確保資料能由目標無線感測器將資料回傳到觀察者。由實驗模擬結果顯示，我們提出的方法和單一路由協定(DSDV)比較增加了44%的封包傳送率，進而延長了無線感測網路的壽命。

In recent years, thanks to the daily development of micro-electro-mechanical-system (MEMS) and wireless communication technology, we are able to produce the small volume, low cost and multi-function wireless sensors, we are also able to gather the mass wireless sensor and deploy them into a wireless sensor network. According to their different needs, we may apply them to environmental monitor, domestic care, security, or even military.

The operation of wireless sensor network is rooted in energy. We embed the battery in the inner part of wireless sensor, but the battery can not be recharged restricted by the surrounding. The existed routing protocol can be divided into proactive routing protocol, reactive routing protocol and hybrid routing protocol. Each routing protocol has its merits and shortcomings, and starts its operation as long as the wireless sensor network begins to work. The lifetime will end when the working routing protocol can no longer support the whole wireless sensor network. The original route of wireless sensor network comes to an end because of the existed flaws in the original design, or because it has reached the default lifetime of the wireless sensor network. The fact that the routing protocol can not support the operation of the wireless sensor network does not mean all the power of wireless sensor is used up. When the power of wireless sensor itself is lower than the threshold to send the data, even if the information can continually be detected, the wireless sensor can not be responsible of transferring the data. No matter which kind of routing protocol, it happens when the sink sends a query to the source node, the information found can not be returned.

The method adapts the mechanism of both redundancy node and dual routing protocol. Redundancy node, when wireless sensor network is being deployed, can divide the wireless sensor network into two parts, and can use the different routing protocol. One part is the routing protocol functioning as soon as the sensor network is deployed. The other part is the sleeping node; only when there is a need will the sleeping nodes be awake. Only when there is a need will we wake up these sleeping wireless sensors. Dual routing protocol individually designs two kinds of different routing protocols in the wireless sensor, using the merits of these two different kinds of routing protocols to accomplish the mission of sending the data.

The scenario we set up is when the wireless sensor network has been used for a long time; the power kept in these wireless sensors is different. It is possible that some wireless sensor contains lower power because the heavy load of work, and some with more power because of less work load. After we send a query to the source node and unfortunately find out there is more than one wireless sensor in the routing path, and if there is power shortage, we can only query a message to send the sink to the source node. At the meantime, the source node will judge the storing condition of the power in all the wireless sensors when sending the query from the sink to the source node. Then the target wireless sensor will send a broadcast to all the neighbors. If there is a sleeping node in the neighbor and if we run a second kind of routing protocol, the sleeping wireless sensor will wake up. The woken wireless sensor will build up a path to ensure the data get sent from the source to the sink. Simulation results showed that proposed mechanism is about 44% of packet delivery ratio can be increased compared to single routing protocol (DSDV).

摘要 I
Abstract III
Chapter 1
Introduction 1
1.1 Sensor Networks Overview 1
1.2 Energy Management 3
1.3 Motivation 6
1.4 Organization of This Thesis 8
Chapter 2
Background Knowledge and Related Work 9
2.1 Architecture of Sensor Network 9
2.2 Routing Protocol 11
2.2.1 Proactive Routing Protocol 12
2.2.2 Reactive Routing Protocol 15
2.2.3 Hybrid Routing Protocol 18
2.3 Other Related Protocols 18
Chapter 3
Proposed Mechanism 19
3.1 Backup Routing Path 19
3.2 Redundancy Node and Dual Routing Protocol 22
3.3 Source Node and Destination Node 23
3.4 Advantages 25
Chapter 4
Simulation Analysis and Discussion 27
4.1 Scenario 27
4.2 Simulation Environment 28
4.3 Average Latency 28
4.4 Packet Delivery Ratio 30
4.5 System Lifetime 31
Chapter 5
Conclusion and Future Work 33
5.1 Conclusion 33
5.2 Future Work 33
References 34

[1] I.F. Akyildiz, W.Su, Y. Sankarasubramaniam and E. Cayirci, “Wireless Sensor Networks: a Survey,” Computer Networks, Vol.38, No.4, pp.393–422, 2002.
[2] I.F. Akyildiz, W.Su, Y. Sankarasubramaniam and E. Cayirci, “A Survey on Sensor Network,” IEEE Communications Magazine, Vol.40, pp.102-114, August 2002.
[3] M. Kochhal, L. Schwiebert and S. Gupta, “Role-base Hierarchical Self Organization for Wireless Ad hoc Sensor networks,” Proceedings of the 2nd ACM International Conference on Wireless Sensor networks and Applications, pp. 98-107, September 2003.
[4] A. Perrig, J. Stankovic and D. Wagner, “Security in Wireless Sensor Networks”, Communications of the ACM on Wireless sensor networks SPECIAL ISSUE,” Vol.47, pp.53–57, June 2004.
[5] W. Heinzelman, A. Chandrakasan and H. Balakrishnan, “Energy-Efficient Communication Protocol for Wireless Microsensor Networks,” Proceedings of the Hawaii International Conference on Systems Science, Vol.2, pp.1-10, January 2000.
[6] D. Estrin, L. Girod, G. Pottie and M. Srivastava, “Instrumenting The World with Wireless Sensor Networks,” Proceedings of IEEE International Conference, Vol.4, pp.2033-2036, 2001.
[7] K. Sohrabi, J. Gao, V. Ailawadhi and G. J. Pottie, “Protocols for Self-organization of A Wireless Sensor Network,” IEEE Personal Communications, Vol.7, pp.16-27, October 2000.
[8] K. Sohrabi, G. Pottie, “Performance of A Novel Self-organization Protocol for Wireless Ad-hoc Sensor Networks,” Vehicular Technology Conference, Vol.2, pp.1222-1226, 1999.
[9] C. Schurgers, M. Srivastava and V. Tsiatsis, “STEM: Topology Management for Energy Efficient Sensor Networks,” Proceedings of the IEEE Aerospace Conference, Vol.3, pp.1099-1108, 2002.
[10] W. Ye, J. Heidemann and D. Estrin, “An Energy-Efficient MAC Protocol for Wireless Sensor Networks”, In Proceedings of INFOCOM2002, April 2002.
[11] S. Tilak, A. Murphy, W. Heinzelman, “Non-uniform Information Dissemination for Sensor Networks”, Proceedings of IEEE International Conference, pp.295–304, November 2003.
[12] J. Macker and S. Corson, “Mobile Ad hoc Networks(MANET)”, IETF WG Character. http://www.ietf.org/manet-charter.html.
[13] T. Hou and T. Tsai, “Adaptive Clustering in a Hierarchical Ad hoc Network,” Proceedings of the Workshop on Computer Networks, December 1998.
[14] E. Royer and C. Toh, “A Review of Current Routing Protocols for Ad hoc Mobile Wireless Networks,” IEEE Personal Communications Magazine, pp.46-55, April 1999.
[15] C. Perkins and P. Bhagwat, “Highly Dynamic Destination-Sequenced Distance-Vector Routing(DSDV) for Mobile Computers,” Proceedings of the ACM SIGCOMM’94, pp.234-244, October 1994.
[16] C. Perkins, E. Royer and S. Das, “Ad Hoc On-demand Distance Vector(AODV) Routing,” Internet Draft, draft-ietf-manet-adov-13.txt, February 2003.
[17] C. Perkins and E. Royer, “Ad hoc On-Demand Distance Vertor Routing,” Proceedings of IEEE WMCSA, February 1999.
[18] Z. Haas and M. Pearlman, "The Performance of Query Control Schemes for the Zone Routing Protocol," ACM/IEEE Transactions on Networking, Vol.9, No.4, pp.427-438, August 2001.
[19] M. Pearlman and Z. Haas, “Determining the Optimal Configuration for the Zone Routing Protocol,” IEEE Journal on Selected Areas in Communications, Vol.17, No.8, pp.1395-1414, August 1999.
[20] Z. Haas and M. Pearlman, “The Zone Routing Protocol (ZRP) for Ad Hoc Networks,” Internet Draft, draft-ietf-manet-zone-zrp-02.txt, June 1999
[21] N. Nikaein, H. Labiod and C. Bonnet, “DDR-Distributed Dynamic Routing Algorithm for Mobile Ad hoc Networks,” Proceedings of IEEE Mobile and Ad Hoc Networking and Computing, pp.19–27, August 2000.
[22] Y. Chang, T. Chang and T. Hsieh, “Hierarchical Cellular-based Management for Mobile Hosts in Ad-hoc Wireless Networks,” Proceedings of IEEE International Conference on Information Networking, pp.843 -848, February 2001.
[23] S. Coleri and P. Varaiya, “Fault Tolerance and Energy Efficiency of Data Aggregation Schemes for Sensor Networks,” Proceedings of the IEEE 60th Vehicular Technology Conference, Vol.4, pp.2925-2929, 26-29 September 2004.
[24] D.B. Johnson and D.A. Maltz, “The Dynamic Source Routing Protocol (DSR) for Mobile Ad Hoc Networks,” IETF Draft. July 2004.
[25] F. Bertocchi, P. Bergamo, G. Mazzini and M. Zorzi, “Performance Comparison of Routing Protocols for Ad-hoc Networks,” Proceedings of the IEEE Global Telecommunications Conference, Vol.2, pp.1033-1037, December 2003.
[26] K. Seada and A. Helmy, “An Overview of Geographic Protocols in Ad Hoc and Sensor Networks,” Proceedings of the 3rd ACS/IEEE International Conference on Computer Systems and Applications, pp.62-69, 2005.
[27] M. Hempel, H. Sharif and P. Raviraj, ”HEAR-SN: A New Hierarchical Energy-Aware Routing Protocol for Sensor Networks,” Proceedings of the 38th Annual Hawaii International Conference on System Sciences, pp.324-331, January 2005.
[28] Z.W. Zheng, Z.H. Wu and H.Z. Lin, “Clustering Routing Algorithm using Game-theoretic Techniques for WSNs,” Proceedings of the 2004 International Symposium on Circuits and Systems, Vol.4, pp.904-907, May 2004.
[29] J. Hornsberger and G.C. Shoja, “Geographic Grid Routing for Wireless Sensor Networks,” Proceedings of the IEEE Networking, Sensing and Control Conference, pp.484-489, 19-22 March 2005.
[30] C. Intanagonwiwat, R. Govindan, D. Estrin, J. Heidemann, and F. Silva, “Directed Diffusion for Wireless Sensor Networking,” IEEE/ACM Networking Transactions, Vol.11, No.1, pp.2-16, February 2003.
[31] H. Sabbineni and K. Chakrabarty, “Location-aided Flooding: An Energy Efficient Data Dissemination Protocol for Wireless Sensor networks,” IEEE Transactions on Computers, Vol.54, No.1, pp.36-46, January 2005.
[32] R.C. Luo, L.C. Tu and O. Chen, “Auto-Deployment of Mobile Nodes in Wireless Sensor Networks Using Grid Method,” Proceedings of IEEE International Conference on Industrial Technology, pp.359-364, 14-17 December 2005.
[33] F. Ye, H. Luo, J. Cheng, S. Lu and L. Zhang, “Sensor Networks: A Two-Tier Data Dissemination Model for Large-scale Wireless Sensor Networks,” Proceedings of the 8th Annual ACM/IEEE International Conference on Mobile Computing and Networking, pp.148-159, September 2002.
[34] S. Kim, S.H Son, J.A. Stankovic, S. Li and Y. Choi, “SAFE: A Data Dissemination Protocol for Periodic Updates in Sensor Networks,” Proceedings of 23rd Internatonal Conference on Computing Systems, pp.228-234, 2003.
[35] H.L. Xuan and S. Lee, “A Coordination-based Data Dissemination Protocol for Wireless Sensor Networks,” Proceedings of the Intelligent Sensors, Sensor Networks and Information Processing Conference, pp.13-18, 14-17 December 2004.
[36] Q. Li and D. Rus, “Global Clock Synchronization in Sensor Networks,” IEEE Transactions on Computers, Vol.55, No.2, pp.214-226, February 2006.
[37] N. Bulusu, J. Heidemann and D. Estrin, “Gps-less Low Cost Outdoor Localization for Very Small Devices,” IEEE Personal Communications Magazine, Vol.7, No.5, pp.28-34, October 2000.
[38] J. Albowicz, A. Chen and L. Zhang, “Recursive Position Estimation in Sensor Networks,” Proceedings of IEEE Internation Conference on Network Protocols (ICNP’01), pp.35-41, November 2001.
[39] Y. Xu, J. Heidemannn and D. Estrin, “Geography-informed Energy Conservation for Ad Hoc Routing,” Proceedings of the 7th Annual ACM/IEEE International Conference on Mobile Computing and Networking, Rome, Italy, pp.70-84, 16-21 July 2001.
[40] M. Mamun-Or-Rashid, C.S. Hong and C.H. In, “Passive Cluster Based Clock Synchronization in Sensor Network,” Proceedings of Advanced Industrial Conference on Telecommunications/Service Assurance with Partial and Intermittent Resources, pp.340-345, July 2005.
[41] NS2 Simulator, http://www.isi.edu/nsnam/ns/
[42] NS2 Simulator, http://www.isi.edu/nsnam/dist/
[43] NS2 Simulator, http://140.116.72.80/~smako/ns2/ns2.htm