在無線感測網路中設計一個Top-k查詢方法

在無線感測網路中有許多重要的應用像是在軍事、環境監控和物件追蹤。有一個應用已經被提出叫做top-k的查詢。在top-k的查詢中我們只關心在我們感測的區域top-k的感測值。由於感測器的電力有限，在無線感測網路中如何有效利用有限的電量是一個很重要的議題。在本篇論文中我們提出一個在top-k查詢中有效率儲存資料的方法。在我們的方法裡首先我們會將資料正規化成[0, 1]區間的值。根據維度d，感測網路會被切割成多個虛擬的網格。維度的大小是根據感測器數量的多寡以及資料產生的頻率來決定。每一個網格都有一個網格領導點在網格內的中央。網格領導點也是資料的儲存點，感測器將會傳送資料儲存在儲存點中。在感測網路中網格的編號會像是蛇行一樣，每個儲存點都擁有一個資料範圍。如果網格的數量是n，我們可以切割資料範圍[0, 1]成為n個均等的子範圍區間。資料將會儲存在屬於它子範圍區間的資料儲存點裡，我們會從資料範圍最高的儲存點開始查詢。這樣的做法可以有效率的查詢top-k的資料並且節省查詢的成本並且延長網路的生命周期。我們模擬我們以及現存top-k的方法FILA。實驗結果顯示我們方法的效能比現存的方法表現較佳。

關鍵字

top-k ；無線感測網路；資料儲存

並列摘要

Wireless sensor network has many important and useful applications like military, environment monitoring and object tracking. There is an application that already proposed call top-k query. In top-k query we are mainly focus on the top-k highest value in the specified sense area. Since sensor nodes have limed capability in energy. In network management wireless sensor networks energy efficient is a very important factor. In this paper, we propose an efficient data storage method for top-k query. With the method this paper use, we normalize the sense readings and change them to fall [0, 1]. The sensor network can be divided into many grids base on the number of dimension d. Dimension can be determinate dependent on number of sensor nodes and data generation frequency. Each grid has a grid head at the center of each grid. Grid head are the storage nodes and sensor nodes will transmit data to store in them. The grid number is placed like snake in the sensor network. Each storage node owns a data sub-range. If the number of grids are n, we divide data range [0, 1] into n sub-range equally. Each grid head own its sub-range and data will store to the grid head which data fall in the sub-range. We can query top k value from the highest sub-range of the grid head node. By this way we can query top-k value efficient and reduce the query cost and prolong network lifetime. We simulate the performance with the existing top-k query processing algorithms FILA. Our experimental results show that the network lifetime of our method is prolonged over the existing method.

並列關鍵字

wireless sensor networks ； data storage ； top-k

參考文獻

[2] P. Andreou, D.Z. Yazti, M. Vassiliadou, P.K. Chrysanthis, and G. Samaras, “KSpot: Effectively Monitoring the K Most Important Events in a Wireless Sensor Network,” IEEE International Conference on Data Engineering, 2009.

[3] M. Bajracharya and M. Chen, “Dynamic Update System for K Queries in Wireless Sensor Networks,” IEEE International Conference on Wireless Communications, Networking and Mobile Computing, 2008.

[6] S. Ishihara and T. Suda, “Replica arrangement scheme for location dependent information on sensor networks with unpredictable query frequency,” IEEE International Conference on International Communications Conference, 2009.

[8] H.-C. Le, H. Guyennet, and N. Zerhouni, “Mobile Effect Reduction in Data-Centric Storage for Wireless Sensor Networks,” IEEE International Conference on Intelligent Environments, 2007.

[9] W.-H. Liao and C.-C. Chen, "A Multi-Dimensional Data Storage Algorithm in Wireless Sensor Networks," IEEE International Conference on Network Operations and Management Symposium, 2010.

國際替代計量

在無線感測網路中設計一個Top-k查詢方法

未授權

主題瀏覽