In-Network Execution of External Join for Sensor Networks
Recently there have been growing interests in the applications of wireless sensor networks such as traffic tracking, environmental surveillance, and network monitoring. In these applications, the exploration of the relationship and linkage of sensing data with other data sources can be naturally expressed by the external join, where the sensory tuples join with an external table at the base station. However, executing such kind of join queries in a highly distributed and resource-constraint sensor network is a challenging task. In this paper, we propose a partition-based algorithm called NEJA (in-Network External Join Algorithm) for the external join processing in sensor networks. NEJA organizes the sensory data of the network through an optimized “value-to-storage mapping, according to which each storage point stores the tuples that belong to the same subrange on the joint attribute. Then the subrange of each storage point is further partitioned into unit ranges, and tuples in the same unit range wisely choose their joining point that incurs the least communication cost based on a cost metric according to the latest historical statistics. Also, NEJA adopts some optimization techniques to handle the changes of sensory data and uses approximate approaches to cut down the maintenance cost of the mechanism. The experimental results indicate that our scheme is effective in reducing the amount of transmissions for the realtime external join processing, especially when the external table has a relatively large size.
Yongxuan Lai Yilong Chen Hong Chen
School of Information,Renmin University of China,Beijing,P.R.China;Key Laboratory of Data Engineering and Knowledge Engineering,MOE
国际会议
The Ninth International Conference on Web-Age Information Management(第九届web时代信息管理国际会议)(WAIM 2008)
张家界
英文
2008-07-20（万方平台首次上网日期，不代表论文的发表时间）