Suffix Trees for Fast Sensor Data Forwarding
Date Issued
2006
Date
2006
Author(s)
Wu, Jui-Chieh
DOI
en-US
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.
Subjects
感測器網路
演算法
內容導向路由
Sensor networks
Algorithm
Data centric forwarding
Type
thesis