以搜尋樹為基礎之無線感測網路繞徑演算法

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：7

、訪客IP：18.218.55.14

姓名

許仲辰(Zhone-Chen Shu) 查詢紙本館藏

畢業系所

資訊工程學系在職專班

論文名稱

以搜尋樹為基礎之無線感測網路繞徑演算法
(Search-Tree-Based Routing Algorithm on Wireless Sensor Networks)

相關論文

★ 無線行動隨意網路上穩定品質服務路由機制之研究	★ 應用多重移動式代理人之網路管理系統
★ 應用移動式代理人之網路協同防衛系統	★ 鏈路狀態資訊不確定下QoS路由之研究
★ 以訊務觀察法改善光突發交換技術之路徑建立效能	★ 感測網路與競局理論應用於舒適性空調之研究
★ 基於無線感測網路之行動裝置輕型定位系統	★ 多媒體導覽玩具車
★ 以Smart Floor為基礎之導覽玩具車	★ 行動社群網路服務管理系統－應用於發展遲緩兒家庭
★ 具位置感知之穿戴式行動廣告系統	★ 調適性車載廣播
★ 車載網路上具預警能力之車輛碰撞避免機制	★ 應用於無線車載網路上之合作式交通資訊傳播機制以改善車輛擁塞
★ 智慧都市中應用車載網路以改善壅塞之調適性虛擬交通號誌	★ 車載虛擬交通號誌環境下 Green Wave 之研究

檔案

[Endnote RIS 格式]

[Bibtex 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

至系統瀏覽論文 ( 永不開放)

摘要(中)

由於處理器、記憶裝置及無線電技術的進步，促使低成本、低功率，具有感測外在環境、無線通訊及計算能力的感測器誔生。這種感測器構成的網路能夠相互合作來感測外在環境中如溫度、光度、聲音等的一些特定現象。本篇論文提出一種以搜尋樹為基礎的繞徑演算法來達成有效率且即時的協同傳輸模式。一般在感測器網路的繞徑演算法，因為無法知道資料源的位置，在第一次傳送詢問資料的訊息給資料源通常以濫氾式傳輸將訊息送達資料源，資料源再於發送端及目的地間的感測器中建立位置資訊以供資料源將資料回傳時使用。本論文提出以搜尋樹為基礎的演算法，用以加強感測器網路定點即時傳輸的能力。首先，建立樹狀的感測器網路，再分配給每個感測器一個位址，把感測器網路建立成搜尋樹架構。使用這個樹狀架構及給定的位址資訊，感測器可以由自己的位址資訊決定訊息繞徑的下一站。本演算法不需於每次傳送訊息前在各感測器上建立位置相關的資訊，因此，每個感測器能夠更有效率地將訊息傳送到目的地。在模擬實驗中，本演算法在不同網路大小及傳輸工作量的表現都很優越。本演算法亦實作於自動停車系統上，此系統為基於感測器網路而設計之一種應用。

摘要(英)

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.

關鍵字(中)

★ 資料源
★ 感測器網路
★ 搜尋樹
★ 氾濫式傳輸

關鍵字(英)

★ data source
★ sensor network
★ Search tree
★ flooding

論文目次

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.

指導教授

周立德(Li-Der Chou)

審核日期

2005-7-22

推文