臺灣博碩士論文加值系統

近來由於數位電子及無線通訊等科技的發展，已經設計出便宜、低能源消耗、體積小又多功能的感測器裝置。這些感測器裝置被散佈在所要監控的地區，來量測周遭的環境狀況，如溫度、聲音、光線等等。這些感測器裝置互相合作以建立一個可以隨時隨地存取所監控區域的環境資料之無線感測網路。無線感測器網路已經應用在許多的領域。如健康照護、軍事戰場、安全議題、廠房自動化及環境生態監控等。一般來說，感測器裝置往往受限於計算能力、記憶容量以及電源，而無法提供強大的功能。尤其是電源的供應來源可能只是小小的鹼性電池而已，而且當感測器裝置散置在廣大且不易到達的區域時，若要更新電池其實是不易實行且不符合經濟效益。所以，如何在無線感測器網路中減少能源的消耗是一個很重要的課題。在無線感測器網路中能源的消耗大致可區分為兩大部分:通訊及非通訊(環境感測、資料運算)。而通訊部份通常是最大的能源殺手，一個好的路由機制可以減少通訊的次數頻率，進而節省所消耗的能源，以延長整個無線感測器網路的使用時間。
本研究開發一套新的叢集架構的路由協定，其結合了在叢集裡應用Table-driven的路由機制建立路由表以及在叢集之間應用On-demand的方式來交換原本存在叢集裡的路由資料。叢集架構的好處就是能把通訊的範圍限制在叢集裡，以此來減少封包在整個網路漫無目的地流竄所造成的能源消耗。而這新的路由機制的概念是源自傳統有線網路裡的網路遮罩及閘道概念。在傳統有線網路上，電腦與電腦的溝通是經由封包的傳遞，來建立彼此的溝通連結，透過與網路遮罩比對來判斷封包的目的地是屬於內部子網路抑或外部子網路，如果目的地為外部的子網路，就將封包透過閘道來把封包往外傳送,而若目的地為本地的子網路就不須通過閘道，直接將封包傳送至目的地。依據此觀念，我們將無線感測器網路分成數個不同的群組視為叢集(不管為甚麼形式，如格網狀、蜂巢狀、不規則狀…)，而每個感測器都有其可供辨識的id，可以依此判別出是屬於哪一個叢集。並以叢集外緣的其他叢集的感測器來當作通往其他叢集的閘道，進一步提供網路通訊時的路徑選擇參考。
叢集內路由的建立: 在叢集裡的感測器用table-driven的方式(如DSDV)來建立彼此的路由關係，並紀錄在每個感測器自己的路由表裡。而當內部路由更新的訊號傳到別的叢集的感測器時，感測器就不會將內部路由更新的訊號繼續廣播下去，藉此將廣播的範圍限制在叢集內及其外圍的下一個感測器範圍內，使定期性的內部路由更新的影響降至最低。並且如此可將叢集外緣非屬於此叢集的感測器加入內部路由表裡，進而成為通往其他叢集的路由，而這些非屬於此叢集的感測器也成為通往其他叢集的閘道感測器。而由於通往其他叢集的閘道感測器可能不只一個，依此可作為路徑選擇的備援路徑以及負載平衡的機制，而叢集間路由的建立: 當從叢集內部路由表裡我們可得知叢集與相鄰叢集之間的連結關係，這就成為叢集間路由的基礎，藉由叢集間訊息的溝通查詢以建立叢集間的路由。但我們並不事先建立起叢集間的路由，而是當需要時才建立，以減少建立、維護路由表的負擔。我們藉由叢集之間的溝通來交換建立叢集間的路由，並發佈更新給叢集內的其他感測器。
在無線感測器網路上應用本研究所提出的路由機制，可以有效的減少在整個網路廣播的封包流量並提升路由的效能。實驗模擬結果顯示，若與AODV與DSR相比較時，可以減少將近40%的路由控制封包，這大大減少了因通訊所造成的能源消耗，進而使得無線感測器網路獲得更佳的使用效率。

Recent advances in hardware and wireless communication technologies have designed low-cost, low-power, multifunctional sensor devices. These hundreds or thousands of sensor nodes are spread across a geographical area to monitor ambient condition such as temperature, sound and light. These sensor nodes cooperate with each other to establish a sensing network that can provide access to surrounding information anytime, anywhere. Wireless sensor network has been adopted in various applications (e.g., health, military, security, factory automation, environmental monitoring). The sensor nodes are typically restricted by energy, storage capacity and computing ability. They have finite energy supplied by batteries which can not be recharged owing to the scale of sensor network. Therefore, reducing power consumption is a critical issue in sensor networks. The power consumption in wireless sensor networks can be categorized into two parts: communication and computation. Communication is the major consumer of power. A good routing protocol can reduce the power consumption of communication and prolong the lifetime of sensor network.
In this thesis, we introduce a new cluster-based routing protocol that combines the table-driven intra-cluster routing and on-demand inter-cluster routing by changing the relationship between clusters for sensor networks. The advantages of cluster-based routing are to reduce the communication traffic and information storage and avoid frequent network topology changes. The proposed routing protocol is primarily based on the net mask and gateway of traditional network subnet. In traditional network environment, while the packets are sent to the Internet, the computer compares each packet’s destination by comparing it with net mask to determine whether it is in the local subnet. If the destination is in outer subnet, then the computer forwards packets to the outer subnet passing through the responsible gateway. Accordingly, the sensor nodes are split into several clusters as subnets, and the border nodes in the adjacent clusters around the local cluster acting as border gateways are responsible for the route to other adjacent clusters.
Applying the protocol in sensor networks can reduce packets flooding throughout the network and improve the routing efficiency. Simulation results showed that about 40% of control overhead can be diminished compared to Dynamic Source Routing protocol (DSR) and Ad hoc On-demand Distance Vector routing protocol (AODV).

摘要......................................................................I
Abstract .................................................................III
Chapter 1 Introduction ...................................................1
1.1 Motivation ...........................................................2
1.2 Organization of Thesis................................................5
Chapter 2 Background and Relative Work....................................6
2.1 Overview of Wireless Sensor Network...................................6
2.2 Difference between Wireless Sensor Network and Ad hoc Network.........9
2.3 Design of Wireless Sensor Networks ...................................9
2.4 Clustering in Wireless Sensor Networks ...............................11
2.5 Routing in Wireless Sensor Networks ..................................12
2.6 TinyOS ...............................................................14
Chapter 3 Proposed Routing Protocol.......................................17
3.1 Intra-cluster Routing.................................................17
3.2 Inter-cluster Routing.................................................21
3.3 The Role of BGP in Routing ...........................................24
Chapter 4 Simulation Analysis and Discussion..............................26
4.1 Simulation Environment................................................26
4.2 Packet Delivery Ratio and Control Overhead............................26
4.3 Average Latency.......................................................28
4.4 Throughput............................................................29
Chapter 5 Conclusions and Future Work ....................................31
5.1 Conclusions ..........................................................31
5.2 Future Work...........................................................31
References ...............................................................32

[1] I.F. Akyildiz, W. Su, Y. Sankarasubramaniam and E. Cayirci, "Wireless Sensor Networks: a Survey," Computer Networks, Vol.38, No.4, 2002, pp.393-422.
[2] C.T. Chong and S.P. Kumar, "Sensor Networks: Evolution, Opportunities, and Challenges," Proceedings of the IEEE, Vol.91, No.8, Aug. 2003, pp.1247-1256.
[3] http://www.xbow.com/Products/Wireless_Sensor_Networks.htm
[4] http://www.dust-inc.com/flash-index.shtml
[5] R. Dantu and S. Joglekar, "Collaborative Vision using Networked Sensors," Proceedings of the International Conference on Information Technology: Coding and Computing, Vol.2, April 2004, pp.395-399.
[6] A. Mainwaring, J. Polastre, R. Szewczyk, D. Culier and J. Anderson, "Wireless Sensor Networks for Habitat Monitoring," Proceedings of the 1st ACM International Workshop on Wireless Sensor Networks and Applications, September 2002, pp.88-97.
[7] L.M. Feeney, "An Energy-Consumption Model for Performance Analysis of Routing Protocols for Mobile Ad-hoc Networks," Mobile Netw. Applicat., Vol. 6, No. 3, June 2001, pp. 239-249.
[8] W.R. Heinzelman, A. Chandrakasan and H. Balakrishnan, "Energy-Efficient Communication Protocol for Wireless Microsensor Networks," Proceedings of the 33rd Annual Hawaii International Conference on System Sciences, vol.2, Jan. 2000, pp.10.
[9] 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, 2003. GLOBECOM '03. Vol.2, Dec. 2003, pp.1033-1037.
[10] A. Boukerche, "A Performance Comparison of Routing Protocols for Ad-hoc Networks," Proceeding of the 15th International Parallel and Distributed Processing Symposium, April 2001, pp.1940-1946.
[11] M. Hollick, I. Martinovic, T. Krop and I. Rimac, "A Survey on Dependable Routing in Sensor Networks, Ad-hoc Networks, and Cellular Networks," Proceedings of the 30th Euromicro Conference 2004, Sept. 2004, pp.495-502.[12] A. Boukerche, V. Sheetal and M.Choe, "A Route Discovery Optimization Scheme using GPS System," Proceedings of the 35th Annual Simulation Symposium 2002, April 2002, pp.20-26.
[13] http://robotics.eecs.berkeley.edu/~pister/SmartDust/
[14] A.A. Makarenko, T. Kaupp and H.F. Durrant-Whyte, "Scalable Human-Robot Interactions in Active Sensor Networks," Proceedings of the IEEE Conference on Pervasive Computing, IEEE, Vol.2, No.4, Oct.-Dec. 2003, pp.63-71.
[15] S.H. Choi, B.K. Kim, J. Park, C.H. Kang and D.S. Eom, "An Implementation of Wireless Sensor Network," IEEE Transactions on Consumer Electronics, Vol.50, No1, Feb. 2004, pp.236 - 244.
[16] T.T. Hsieh, " Using Sensor Networks for Highway and Traffic Applications," IEEE Potentials Magazine, Vol.23, No2, Apr-May 2004, pp.13-16.
[17] L. Guibas, "Sensing, Tracking, and Reasoning with Relations," IEEE Signal Processing Magazine, Vol.19, March 2002, pp.73-85.
[18] D. Estrin, R. Govindan, J. Heidemann and S. Kumar, "Next Century Challenges: Scalable Coordination in Sensor Networks," Proceedings of the 5th Annual ACM/IEEE International Conference on Mobile Computing and Networking, August 1999, pp.263-270.
[19] G. Gupta and M. Younis, "Load-balanced Clustering of Wireless Sensor Networks," Proceeding of the IEEE International Communications Conference 2003, Vol.3, May 2003, pp.1848-1852.
[20] 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, 2004, Vol.4, May 2004, pp.904-907.
[21] C.F. Chen, "Energy Efficient Routing for Clustered Wireless Sensors Network," Proceedings of the 29th Annual Conference of the IEEE Industrial Electronics Society 2003, Vol.2, Nov. 2003 pp.1437-1440.
[22] 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 2005, Jan. 2005, pp.324a - 324a.
[23] C.A. Lee, Y.C. Chang and J.L. Chen, "Intelligent Self-Organization Management Mechanism for Wireless Sensor Network," Proceedings of the 16th Annual International Conference on Wireless Communications, July 2004, pp.47-54.
[24] J.N. Al-Karaki, and A.E. Kamal, "Routing Techniques in Wireless Sensor Networks: a Survey," Wireless Communications, IEEE, Vol.11, No.6, Dec. 2004, pp.6-28.
[25] D. Petrovic, R.C. Shah, K. Ramchandran and J. Rabaey, "Data Funneling: Routing with Aggregation and Compression for Wireless Sensor Networks," Proceedings of the First IEEE 2003 International Workshop on Sensor Network Protocols and Applications, May 2003, pp.156-162.
[26] H.S. Kim and K.J. Han, "A Power Efficient Routing Protocol Based on Balanced Tree in Wireless Sensor Networks," Proceedings of the First International Distributed Frameworks for Multimedia Applications Conference, 2005, pp.138-143.
[27] C. Schurgers and M.B. Srivastava, "Energy Efficient Routing in Wireless Sensor Networks," Proceedings of the Military Communications Conference, Vol.1, Oct. 2001, pp.357-361.
[28] A. Manjeshwar and D. Agrawal, "TEEN: A Routing Protocol for Enhanced Efficiency in Wireless Sensor Networks," Proceedings of the 15th Parallel and Distributed Processing Symposium, 2001, pp. 2009-2015.
[29] M.A. Youssef, M.F. Younis and K.A. Arisha, "A Constrained Shortest-path Energy-aware Routing Algorithm for Wireless Sensor Networks," Proceedings of the Wireless Communications and Networking Conference 2002, Vol.2, March 2002, pp.794-799.
[30] "TinyOS", http://www.tinyos.net/.
[31] J. Broch, D.A. Maltz, D.B. Johnson, Y.C. Hu and J. Jetcheva "A Performance Comparison of Multi-Hop Wireless Ad Hoc Network Routing Protocols," Proceedings of the ACM/IEEE MobiCom, Oct. 1998, pp.85-87.
[32] Q.F. Jiang and D. Manivannan, "Routing Protocols for Sensor Networks," Proceedings of the Consumer Communications and Networking Conference, Jan. 2004, pp.93-98.
[33] Y. Rekhter and T. Li, RFC-1771 a border gateway protocol (bgp-4). Request for Comments, March 1995.