PEJA: 传感器网络中渐进的能量有效的连接处理
PEJA: Progressive Energy-Efficient Join Processing for Sensor Networks
-
摘要: 近年来无线传感器网络(Wireless Sensor Networks) 逐渐成为国内外研究的热点。多个具有感知、数据处理、存储，以及无线通讯的微型节点通过多跳的方式组成一个自组织网络，并可广泛部署于从物理环境中搜集数据的应用中，如环境监测、交通控制、军事侦查等等。在这些应用里，不同区域的感知数据之间的联系和相关性可以很自然的用连接查询来表示。但是，传感器网络高度分布和资源受限的特性，使得对连接查询的处理富有挑战性。本文我们讨论了在传感器网络不同区域之间进行渐进的和能量有效的连接查询问题。对于连接查询，如果出现在最终结果集的元组都被传输到基站，而对结果无贡献的元组都能在网内过滤掉，我们称之为理想连接模型(Ideal Join Model)，其仅在极端情况存在。在多区域间的连接算法中，算法必有额外的开销来区分一条新元组是否能对最终结果产生贡献。额外开销的大小，是判断连接算法性能好坏的重要标准。此外，现有连接算法大都属于阻塞算法(blocking)，须待相关元组收集完毕后才能开始处理，且连接处理节点容易因储存不足而导致元组的丢弃。本文提出了一种新的处理区域间的渐进连接算法PEJA (Progressive Energy-efficient Join Algorithm)。PEJA的基本思想是尽可能减少连接处理中额外开销来提高算法效率，同时在网内进行连接处理，降低结果输出延迟并在本地删除部分元组来缓解存储紧张的状况。具体的说，PEJA首先把每个连接区域在逻辑上划分成多个子区域（格），并根据历史数据信息生成一个可更新的“值→格”的映射；新产生的元组根据该映射被路由到不同的格进行处理。格是连接处理的基本单位，属于同一范围但在不同连接区域中的格称为“映像格”(mirror grids)，属于同一对映像格之间的元组才可能匹配并产生最终连接结果。映像格之间采用事件驱动的策略，不仅快速输出可连接的元组，还能缓解查询时网内节点存储不足的问题。此外，PEJA算法还在连接区域中安置过滤器(filter)，在处理初始阶段即可快速去除那些无法匹配的元组，节省了大量没有必要的数据传输。和其他连接算法相比，PEJA大大减少了连接处理中除传输最小连接集外的额外开销。在合成数据集和真实数据集上的大量实验结果表明，PEJA算法优于其他的连接算法，能有效减少连接算法中总的传输量，同时减少连接算法中结果输出的延迟。对于未来工作，我们将首先把PEJA扩展为非等值连接算法，针对不同连接条件选择最优的算法；其次，将探讨高效的过滤器设计，提高算法对无法匹配元组的进一步过滤，从而减少连接处理中的额外开销；最后，由于传感器网络经常部署在复杂恶劣的环境下，我们也将研究在非可靠通讯网络中的处理方法，提高算法的鲁棒性。Abstract: Sensor networks are widely used in many applications to collaborativelycollect information from the physical environment. In theseapplications, the exploration of the relationship and linkage of sensingdata within multiple regions can be naturally expressed by joiningtuples in these regions. However, the highly distributed andresource-constraint nature of the network makes join a challengingquery. In this paper, we address the problem of processing join queryamong different regions progressively and energy-efficiently in sensornetworks. The proposed algorithm PEJA (Progressive Energy-efficient JoinAlgorithm) adopts an \it event-driven strategy to output the joiningresults as soon as possible, and alleviates the storage shortage problemin the in-network nodes. It also installs \it filters in the joiningregions to prune unmatchable tuples in the early processing phase,saving lots of unnecessary transmissions. Extensive experiments on bothsynthetic and real world data sets indicate that the PEJA schemeoutperforms other join algorithms, and it is effective in reducing thenumber of transmissions and the delay of query results during the joinprocessing.
下载: