請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/31622
完整後設資料紀錄
DC 欄位 | 值 | 語言 |
---|---|---|
dc.contributor.advisor | 呂學一(Hsueh-I Lu) | |
dc.contributor.author | Jui-Chieh Wu | en |
dc.contributor.author | 吳瑞傑 | zh_TW |
dc.date.accessioned | 2021-06-13T03:16:03Z | - |
dc.date.available | 2007-08-10 | |
dc.date.copyright | 2006-08-10 | |
dc.date.issued | 2006 | |
dc.date.submitted | 2006-07-30 | |
dc.identifier.citation | [1] M. Degermark, A. Brodnik, S. Carlsson, and S. Pink, “Small forwarding tables for
fast routing lookups,” in Proceeings of ACM SIGCOMM Conference (SIGCOMM), 10 1997, pp. 3–14. [2] D. Estrin, R. Govindan, J. Heidemann, and S. Kumar, “Next century challenges: Scalable coordination in sensor networks,” in Proceedings of the Fifth Annual Inter- national Conference on Mobile Computing and Networks (MOBICOM), Seattle, 8 1999. [3] R. Zhang and Y. C. Hu, “Hyper: A hybrid approach to efficient content-based publish/subscribe,” in ICDCS, 2005. [4] (2004) Micaz datasheet. Crossbow Technology. [Online]. Available: http://www.xbow.com/ [5] W. Weber, J. Rabaey, and E. Aarts, “Tinyos: An operating system for wireless sensor networks,” in Ambient Intelligence, 2005. [Online]. Available: http://www.tinyos.net/ [6] J. Heidemann, F. Silva, C. Intanagonwiwat, R. Govindan, D. Estrin, and D. Ganesan, “Building efficient wireless sensor networks with low-level naming,” in ACM Symposium on Operating Systems Principles (SOSP), 2001. [7] M. K. Aguilera, R. E. Strom, D. C. Sturman, M. Astley, and T. D. Chandra, “Fil- tering algorithms and implementation for very fast publish/subscribe systems,” in ACM SIGMOD, Santa Barbra, California, USA, 5 2001. [8] F. Fabret, H. Arno, J. Kenneth, and A. Ross, “Matching events in a content-based subscription system,” in Proceedings of the eighteenth annual ACM symposium on Principles of distributed computing, 1999. [9] A. Campailla, S. Chaki, E. Clarke, S. Jha, and H. Veith, “Efficient filtering in publish-subscribe systems using binary decision diagrams,” in ICSE, 2001. [10] A. Carzaniga and A. L. Wolf, “Forwarding in a content-based network,” in ACM SIGCOMM, Karlsruhe, Germany, 8 2003, pp. 163–174. [11] E. Ukkonen, “On-line construction of suffix trees,” in Algorithmica, 1995. [12] S. Kurtz, T. Fakultat, and U. Bielefeld, “Reducing the space requirement for suffix trees,” Journal of Software-Practice and Experience, 1999. [13] C. Intanagonwiwat, R. Govindan, and D. Estrin, “Directed diffusion: A scalable and robust communication paradigm for sensor networks,” in ACM MOBICOM, Boston, Massachussetts, USA, 8 2000. [14] A. Carzaniga, M. J. Rutherford, and A. L.Wolf, “A routing scheme for content-based networking,” in Proceedings of IEEE INFOCOM, 3 2004. [15] P. Costa and G. P. Picco, “Publish subscribe on sensor networks: A semi-probablistic approach,” in ICDCS, 2005. [16] U. Farooq, S. Majumdar, and E. W. Parsons, “Engineering mobile wireless pub- lish/subscribe systems for high performance,” in MASCOTS, 2005. [17] Y. Huang and H. Garcia-Molina, “Publish/subscribe in a mobile environment,” in Workshop on Data engineering for Wireless and Mobile Access, 2001. [18] Y. Chen and K. Schwan, “Opportunistic overlays: Efficient content delivery in mo- bile ad hoc networks,” Proceedings of Middleware, Grenoble, France, Tech. Rep., 2005. [19] M. J. J. H. Knuth D. E. and P. V. R., “Fast pattern matching in strings,” SIAM Journal on Computing, vol. 1, pp. 323–350, June 1977. [20] K. Mehlhorn, “Dynamic binary search,” SIAM Journal on Computing, vol. 2, pp. 175–198, August 1979. [21] P. Weiner, “Linear pattern matching algorithms,” Proc. 14th IEEE Annual Symp. on Switching and Automata Theory, pp. 1–11, 1973. [22] Q. D. Minglu Li, Xian He Sun and J. Ni, “Grid and cooperative computing,” in GCC, Shanhai, China, December 2003, pp. 26–33. [23] R. S. Joseph Polastre and D. Culler, “Telos: Enabling ultra-low power wireless research,” in ISPN, 2005. [24] Iar workbench, embedded development tools from iar systems. [Online]. Available: http://www.iar.com/ [25] The public domain portion of the project gutenberg etext of webster’s unabridged dictionary. [Online]. Available: http://www.translatum.gr/dictionaries/download- english.htm [26] J. G. Webster, Bioinstrumentation. Singapore: John Wiley and Sons, 2004. [27] H. Chen, P. Huang, C. Chen, H. Chen, and J. Luh, “Sensor data fusion for timely emergency alarm,” in International Conference on E-Health Networking Applications and Services (Healthcom 2006), New Delhi, India, August 2006. [28] The united states’ polular baby names of the 1980s’. [Online]. Available: http://www.babycenter.com/babyname/names80.html | |
dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/31622 | - |
dc.description.abstract | 在資料導向的無線感測器網路中,資料已不再藉由目的地位置來傳送。相反的,接收端藉由散播帶有自身興趣的額外封包到網路上,接著資料源以及中介的感測器再藉由這些資訊來進行資料的轉送。這樣的傳輸模式非常適用於無線感測網路,原因在於在這樣的模式下,感測器省下了傳輸網路位置的負擔,而在移動性高的環境下,網路位置可能會經常改變。然而,當資料接收端的個數變多了之後,由各個接收端訂定的路由條件也隨之增加,進而讓中介感測器的路由表變大。如此一來,資料轉送所需的運算也就更複雜,更花時間。有時花在路由上的時間,就比傳輸的時間還要長上數十倍。
路由表的搜尋一直是封包轉送效能的瓶頸所在,然而,在路由搜尋的程序中,最耗時的就是字串比對。為了要增進感測器網路資料路由的效能,我們研究並測試了數種演算法,其中包括了字尾樹在硬體資源有限的感測器上的應用,實驗的結果證實字尾樹比之前文獻中使用的三元搜尋樹的搜尋效能更好,對於相符字串的辨識速度最多提高了29%,對於不相符的字串辨識度最多改善了48%。此外,我們還提出了一個有效的字尾樹記憶體最佳化策略,可以讓字尾樹佔用的記憶體減少24%,這樣的最佳化使的字尾樹更適用於資源有限的感測器網路。 | zh_TW |
dc.description.abstract | In data-centric wireless sensor networks, data are no longer sent by the sink node's address. Instead, the sink node sends an explicit interest for a particular type of data. The source and the intermediate nodes then forward the data according to the routing states set by the corresponding interest. This data-centric style of communication is promising in that it alleviates the effort of node addressing and address reconfiguration. However, when the number of interests from different sinks increases, the size of the interest table grows. It could take 10s to 100s milliseconds to match an incoming data to a particular interest, which is orders of mangnitude higher than the typical transmission and propagation delay in a wireless sensor network.
The interest table lookup process is the bottleneck of packet forwarding delay and the most time consuming part is the repeated string matching involved. Motivated to enable fast sensor data forwarding, we study and evaluate the use of an efficient data structure, suffix tree (ST), for fast string matching in resource-limited sensor networks. Results of our experiments show that ST is faster than the state of the art by up to 29% for identifying a match and 48% for identifying a non-match. Further with a novel space optimization scheme, the memory space requirement for ST is reduced by up to 24% which makes ST feasible to run on resource-limited sensor nodes. | en |
dc.description.provenance | Made available in DSpace on 2021-06-13T03:16:03Z (GMT). No. of bitstreams: 1 ntu-95-R93922115-1.pdf: 569739 bytes, checksum: 7b4e8dc22660894ba9cd95576e2d5d62 (MD5) Previous issue date: 2006 | en |
dc.description.tableofcontents | 1 Introduction 1
2 Related Work 5 2.1 Data-Centric Communication . . . . . . . . . . . . . . . . . . . . . . . . 5 2.2 Publish/Subscribe Systems . . . . . . . . . . . . . . . . . . . . . . . . . . 6 2.3 Ad Hoc Publish/Subscribe Systems . . . . . . . . . . . . . . . . . . . . . 7 2.4 String Matching Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . 7 3 Algorithms 8 3.1 Hash . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 3.2 Ternary Search Tree (TST) . . . . . . . . . . . . . . . . . . . . . . . . . 9 3.3 Suffix Tree (ST) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 3.4 Suffix Tree with Space Improvement (ST+) . . . . . . . . . . . . . . . . . 14 4 Analytical Comparison 17 4.1 Definitions and Operations . . . . . . . . . . . . . . . . . . . . . . . . . . 17 4.2 Search Time . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 4.3 Insert Time . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 4.4 Memory Consumption . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 5 Experimental Design 20 5.1 Experimental Environment . . . . . . . . . . . . . . . . . . . . . . . . . . 20 5.2 Word Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 5.3 Metrics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 6 Experimental Results 23 6.1 Search Time . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 6.1.1 Search Time on x86-based Platform . . . . . . . . . . . . . . . . . 24 6.1.2 Search Time on Sensor-Node-Like Platform . . . . . . . . . . . . 27 6.2 Insert Time . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 6.2.1 Insert Time on x86-based Platform . . . . . . . . . . . . . . . . . 28 6.2.2 Insert Time on Sensor-Node-Like Platform . . . . . . . . . . . . . 29 6.3 Memory Consumption . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 6.3.1 Memory Consumption for x86-based Platform . . . . . . . . . . . 29 6.3.2 Memory Consump tion for Sensor-Node-Like Platform . . . . . . 30 7 Discussion 31 7.1 Word Set Dependency . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 7.2 Effect of Trade-off Between Memory Usage to Time . . . . . . . . . . . . 32 7.3 Effect of Hardware Limitation . . . . . . . . . . . . . . . . . . . . . . . . 32 8 Conclusion 33 Bibliography 34 | |
dc.language.iso | en | |
dc.title | 字尾樹在快速感測器資料傳送的應用 | zh_TW |
dc.title | Suffix Trees for Fast Sensor Data Forwarding | en |
dc.type | Thesis | |
dc.date.schoolyear | 94-2 | |
dc.description.degree | 碩士 | |
dc.contributor.coadvisor | 黃寶儀(Polly Huang) | |
dc.contributor.oralexamcommittee | 朱浩華,金仲達,陳伶志 | |
dc.subject.keyword | 感測器網路,演算法,內容導向路由, | zh_TW |
dc.subject.keyword | Sensor networks,Algorithm,Data centric forwarding, | en |
dc.relation.page | 37 | |
dc.rights.note | 有償授權 | |
dc.date.accepted | 2006-07-31 | |
dc.contributor.author-college | 電機資訊學院 | zh_TW |
dc.contributor.author-dept | 資訊工程學研究所 | zh_TW |
顯示於系所單位: | 資訊工程學系 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
ntu-95-1.pdf 目前未授權公開取用 | 556.39 kB | Adobe PDF |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。