跳到主要內容

臺灣博碩士論文加值系統

(44.192.20.240) 您好!臺灣時間:2024/02/27 10:29
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

我願授權國圖
: 
twitterline
研究生:許仲辰
研究生(外文):Zhone-Chen Shu
論文名稱:以搜尋樹為基礎之無線感測網路繞徑演算法
論文名稱(外文):Search-Tree-Based Routing Algorithm on Wireless Sensor Networks
指導教授:周立德周立德引用關係
指導教授(外文):Li-Der Chou
學位類別:碩士
校院名稱:國立中央大學
系所名稱:資訊工程學系碩士在職專班
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2005
畢業學年度:93
語文別:英文
論文頁數:79
中文關鍵詞:搜尋樹感測器網路資料源氾濫式傳輸
外文關鍵詞:data sourcesensor networkSearch treeflooding
相關次數:
  • 被引用被引用:0
  • 點閱點閱:224
  • 評分評分:
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
由於處理器、記憶裝置及無線電技術的進步,促使低成本、低功率,具有感測外在環境、無線通訊及計算能力的感測器誔生。這種感測器構成的網路能夠相互合作來感測外在環境中如溫度、光度、聲音等的一些特定現象。本篇論文提出一種以搜尋樹為基礎的繞徑演算法來達成有效率且即時的協同傳輸模式。一般在感測器網路的繞徑演算法,因為無法知道資料源的位置,在第一次傳送詢問資料的訊息給資料源通常以濫氾式傳輸將訊息送達資料源,資料源再於發送端及目的地間的感測器中建立位置資訊以供資料源將資料回傳時使用。本論文提出以搜尋樹為基礎的演算法,用以加強感測器網路定點即時傳輸的能力。首先,建立樹狀的感測器網路,再分配給每個感測器一個位址,把感測器網路建立成搜尋樹架構。使用這個樹狀架構及給定的位址資訊,感測器可以由自己的位址資訊決定訊息繞徑的下一站。本演算法不需於每次傳送訊息前在各感測器上建立位置相關的資訊,因此,每個感測器能夠更有效率地將訊息傳送到目的地。在模擬實驗中,本演算法在不同網路大小及傳輸工作量的表現都很優越。本演算法亦實作於自動停車系統上,此系統為基於感測器網路而設計之一種應用。
For the progress in processing, memory, and radio techniques, sensor nodes with the integration of sensing, wireless communication, and computation have been developed. The network of such nodes can be coordinated to sense specific environmental phenomena such as thermo, light, and sound, etc. In this paper, a routing algorithm based on search tree is proposed to achieve efficient and real-time coordination. In general, the routing algorithm for sensor networks sends first query message from the sender to the data source node by flooding, for the lack of the location of the data source. Once the data source receives a message from the sender, the location information is generated in the sensor nodes among the sender and the data source. The data source then sends back the data with the location information to the sender. The proposed routing algorithm is able to support real-time transmissions for sensor networks. First, the tree-based sensor network is constructed. Then, a unique address is assigned to each node to build the tree as search tree. With the search tree architecture and the address assignment, sensor nodes decide the next hop for a message by node’s address information. The proposed routing algorithm does not need to build up location information for each message transmission from the source node to the sender and thus messages can be delivered efficiently. In the simulation, the proposed algorithm performs well in both different network size and workload. The proposed algorithm is also implemented in the automatic parking system which is an application designed in sensor network.
1. Introduction 1
1.1 Overview 1
1.2 Motivation and Contribution 2
1.3 Thesis Organization 4
2. Related Work 5
2.1 Directed Diffusion 5
2.2 TreeCast 7
3. Search-Tree-Based Routing Algorithm 10
3.1 Assumption 10
3.2 Concept 11
3.3 Tree Construction 14
3.3.1 Communication Link to Graph 14
3.3.2 Graph to Tree 16
3.4 Address Assignment 18
3.4.1 Prototype assignment 18
3.4.2 Multiple Expansion Assignment 20
3.5 Routing Messages 22
3.5.1 Query and Response 23
3.5.2 Response with Level Forwarding 24
3.6 Tree Maintenance 26
3.6.1 Protocol 26
3.6.2 Node Addition 27
3.6.3 Node Failure 32
4. Simulation Results and Discussions 33
4.1 Goals, Metrics, and Methodology 33
4.2 Network Size 35
4.3 Workload 38
4.4 Level Assignment 42
4.5 Routing under Failures 44
4.6 Maintenance 49
5. Application 53
5.1 Auto Parking System Overview 53
5.2 System Architecture 53
5.3 Emulation 58
5.3.1 Hardware 58
5.3.2 Parking Lot Deployment to Search Tree 60
6. Conclusions and Future Work 62
References 63
[1]I.F. Akyildiz, Weilian Su, Y. Sankarasubramaniam, and E. Cayirci, “A survey on sensor network,” Communication Magazine IEEE, vol. 40, iss 8, pp. 102-114, Aug. 2002.
[2]M. A. M. Vieira, C. N. Coelho. Jr, D.C. da Silva. Jr., and, J.M. da Mata, “Survey on wireless sensor network devices,” Proceedings of IEEE Conference on Emerging Technologies and Factory Automation 2003, ETFA 2003, vol. 1, iss 6, pp. 537-533, 16-19 Sep. 2003.
[3]S.Sense Wireless Sensors. http://www.digitalsun.com/html/products.html.
[4]http://www.sensicast.com.
[5]http://www.senera.com.
[6]Ting Yan, Tian He, and John A. Stankovic, “Differentiated surveillance for sensor networks,” Proceedings of the 1st International Conference on Embedded Networked Sensor System, pp. 51-62, 5-7 Nov. 2003.
[7]W. Steveb Cornet, Jasmeet Chhabra, Mark Yarvis, and Laskshman Krishnamurthy, “Experimental evaluation of synchronization and topology control for in-building sensor network applications,” Proceedings of the 2nd ACM International Conference on Wireless Sensor Networks and Applications, pp. 38-49, 19 Sep., 2003.
[8]Robert Szewczyk, Eric Osterwei, joseph Polastre, Michael Hamilton, Alan Mainwaring, and Deborah Estrin, “Habitat monitoring with sensor networks,” Communications of the ACM, pp. 38-49, 19 Sep., 2003.
[9]Lee Joo-Ho and H. Hashimoto, “Controlling mobile robots in distributed intelligent sensor network,” IEEE transactions on Industrial Electronics, vol. 50, iss 5, pp. 890-902, Oct., 2003.
[10]Choi. Jonghwa, Shin. Dongkyoo, and Shin. Dongil, “Research and implementation of the context-aware middleware for controlling home applications,” International Conference on Comsumer Electronics, 2005, ICCE. 2005 Digest of Technical Papers, pp. 161-162, 8-12 Jan. 2005.
[11]Anastassia Ailamaki, Christos Faloutos, Paul S. Fischbeck, Mitchell J. Small, and Jeanne VanBriesen, “An environmental sensor network to determine drinking water quality and security,” ACM SIGMON Record, vol. 32, iss 4, pp. 47-52, Dec., 2003.
[12]J-L C. Wu. and S-T Wang, “Comparison of power saving schemes for sink nodes in wireless sensor networks,” Proceedings of the 18th International Conference on Advanced Information Networking and Applications, 2004, AINA 2004, vol. 2, pp. 339-342, 2004.
[13]D-H Chane, H-H Han, K-S Lim, K-H Seo, K-H Won, W-D Cho, and S-H An, “Power saving mobility protocol for sensor network,” Proceedings of the 2nd IEEE Workshop on Software Technologies for Future Embedded and Ubiquitous Systems, 2004, pp. 122-126, 11-12 May, 2004.
[14]C. Guettier, G. Le Lann, and J.-F. Hermant, “Ad hoc sensor networks, constraint programming and distributed agreement,” Proceedings of International Conference on Information Technology: Research and Education, 2003, ITRE 2003, pp. 286-290, 11-13 Aug., 2003.
[15]M. Demirbas and H. Ferhatosmanoglu, “Peer-to-peer spatial queries in sensor networks,” Proceedings of the 3rd International Conference on Peer-to-Peer Computing, 2003, pp. 32-39, 1-3 Sep., 2003.
[16]S. Ray, D. Starobinski, A. Trachtenberg, and R. Ungrangsi, “Robust location detection with sensor networks,” IEEE journal on Selected Areas in Communications, vol. 22, iss 6, pp. 1016-1025, Aug., 2004.
[17]T.C. Karalar, S. Yamashita, M. Sheets, and I. Rabaey, “An Integrated, low power localization system for sensor networks,” The 1st Annual International Conference on Mobile and Ubiquitous Systems: Networking and Services, 2004, MOBIQUITOUS 2004, pp. 24-30, 22-26 Aug., 2004.
[18]J. Liu, Zhao Feng, and D. Petrovic, “Information-directed routing in ad hoc sensor networks,” IEEE journal on Selected Areas in Communications, vol. 23, iss 4, pp. 851-861, Apr., 2005.
[19]H. Sabbineni and K. Chakrabarty, “Location-aided flooding: an energy- efficient data dissemination protocol for wireless sensor networks,” IEEE Transactions on Computers, vol. 54, iss 1, pp. 36-46, Jan., 2005.
[20]I. Stojmenovic, A. Nayak, and J. Kuruvila, “Design guidelines for routing protocols in ad hoc and sensor networks with a realistic physical layer,” IEEE Communications Magazine, vol. 43, iss 3, pp. 101-106, Mar., 2005.
[21]J. N. Al-karaki and A. E. Kamal, “Routing techniques in wireless sensor networks: a survey,” IEEE Wireless Communications, vol. 11, iss 6, pp. 6-28, Dec. 2004.
[22]Jiang Qiangfeng and D. Manivannan, “Routing protocols for sensor networks,” 1st IEEE Consumer Communications and Networking Conference, 2004, CCNC 2004, pp. 93-98, 5-8 Jan., 2004.
[23]D. Niculescu, “Communication paradigms for sensor networks,” IEEE Communications Magazine, vol. 43, iss 3, pp. 116-122, Mar., 2005.
[24]D. Niculescu, “Positioning in ad hoc sensor networks,” IEEE Network vol. 18, iss 4, pp. 24-29, Jul.-Aug. 2004.
[25]C. Intanagonwiwat, R. Govindan, D. Estrin, J. Heidemann, and F. Silva, “Directed diffusion for wireless sensor networking,” IEEE/ACM Transactions on Networking, vol. 11, pp. 2-16, Feb. 2002.
[26]J. Kulik, W. R. Heinzelman, and H. Balakrishnan, “Negotiation-based protocols for disseminating information in wireless sensor networks,” Wireless Networks, vol. 8, iss 2/3, pp. 169-185, 2002.
[27]D. Braginsky and D. Estrin, “Rumor routing algorithm for sensor networks,” Proceedings of the 1s Workshop on Sensor Networks and Applications, Atlanta, GA, USA, pp. 22-31, Oct. 2002.
[28]Brad Karp and H.T. Kung, “GPSR: greedy perimeter stateless routing for wireless networks,” Proceedings of the 6th annual international conference on Mobile computing and networking, Boston, Massachusetts, USA, pp. 243-254, 6-11, Aug., 2000.
[29]S. P. Chaudhuri, S. Du, A. K. Saha, and D. B. Johnson, “TreeCast: a stateless addressing and routing architecture for sensor networks,” Proceedings of the 18th International Parallel and Distributed Processing Symposium, pp. 221, 26-30 April, 2004.
[30]T. H. Cormen, C. E. Leiserson, R. L. Rivest and C. Stein, Introduction to Algorithms, McGraw Hill Press, pp.449, 2001.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top