字尾樹在快速感測器資料傳送的應用

Abstract

在資料導向的無線感測器網路中，資料已不再藉由目的地位置來傳送。相反的，接收端藉由散播帶有自身興趣的額外封包到網路上，接著資料源以及中介的感測器再藉由這些資訊來進行資料的轉送。這樣的傳輸模式非常適用於無線感測網路，原因在於在這樣的模式下，感測器省下了傳輸網路位置的負擔，而在移動性高的環境下，網路位置可能會經常改變。然而，當資料接收端的個數變多了之後，由各個接收端訂定的路由條件也隨之增加，進而讓中介感測器的路由表變大。如此一來，資料轉送所需的運算也就更複雜，更花時間。有時花在路由上的時間，就比傳輸的時間還要長上數十倍。 路由表的搜尋一直是封包轉送效能的瓶頸所在，然而，在路由搜尋的程序中，最耗時的就是字串比對。為了要增進感測器網路資料路由的效能，我們研究並測試了數種演算法，其中包括了字尾樹在硬體資源有限的感測器上的應用，實驗的結果證實字尾樹比之前文獻中使用的三元搜尋樹的搜尋效能更好，對於相符字串的辨識速度最多提高了29%，對於不相符的字串辨識度最多改善了48%。此外，我們還提出了一個有效的字尾樹記憶體最佳化策略，可以讓字尾樹佔用的記憶體減少24%，這樣的最佳化使的字尾樹更適用於資源有限的感測器網路。

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.