MANET中基于缓存的两阶段多连接查询方法

4 基于缓存的多连接查询处理
4.1 查询优化算法 对于一个查询节点来说，虽然已知其需要连接的关系集合，但是无法确定各关系间的连接顺序，而这一 连接顺序又直接影响查询的代价。由于连接的结果最终需汇总至查询节点，因此本文考虑以节点与查询节点
柳絮 等:MANET 中基于缓存的两阶段多连接查询技术研究
3
间的距离来建立连接顺序。但是对于一个多连接查询来说，不仅连接的顺序可以影响查询代价，而且不同的 执行顺序也将会产生不同的查询代价。因此，本节给出一种动态规划算法 Qop(Query Optimization) ，以确定 多连接查询的最优执行顺序，使得该查询的代价最小，进而最小化网络中的能量消耗。 令 Cost(R1~n) 为 R1 R2 … Rn 的最小代价。Qop 算法首先递归定义 Cost(R1~n) ，然后建立递归方程，以 Rk+1~ j) 。其中 Δ(Ri~ k Rk+1~j) 最小化查询代价。 Qop 的基本思想如下：由于 Cost (Ri~i)只涉及一个关系，因此 Cost( Ri~i) = 0 。根据最小代价 的最优子结构性质，可以推断， Cost(Ri~ j) = Cost(Ri~ k) + Cost (Rk+1~ j) +Δ(Ri~ k 是 Ri~ k Rk+1~ j 的代价，可以根据第 3 部分的 Soca 算法进行求解。只要从区间 [i ，j]中递归地寻找使得上述
的任何一个节点，就可以得到目标的整个轨迹。 由于连接查询在查询处理中的重要地位，使得研究人员对连接查询的关注越来越广泛。针对传感器网络 中的多连接查询，Ke 等人[5]提出了一个两阶段的查询优化方法，该方法首先以连接结果大小为代价，建立一 颗连接树，并将其划分成多个子查询，分发到相应的数据节点上进行查询。但该算法计算量过大。Zhu 等人
1 引言
在 MANET 的应用中，一般都离不开数据的处理和查询技术，而多连接查询作为查询处理技术中一项重 要而常见的查询，其在 MANET 环境下还存在着以下问题：1)数据产生的随机性导致被连接的多个关系分布 在多个不同节点上，要连接这些关系会产生大量通信量，增加连接查询难度。2) 多连接查询对应的关系较多， 计算量较大，连接这些关系不仅会造成网络拥塞，而且会增加网络的负载。因此，在 MANET 的连接查询中， 尽可能地减少数据通信量将会有效地节省网络中有限的能量资源，缓解网络拥塞，延长网络生存周期。 本文首先定义基于缓存的单连接查询问题，证明了该问题是 NP-完全问题，并给出一种多项式近似算法， 该算法采用贪心策略，在完成单连接查询的同时最大限度地减少网络中能量消耗。在此基础上，提出一种基 于缓存的两阶段多连接查询处理方法，该方法首先采用动态规划方法为多连接查询建立最优的执行顺序，并 将多连接查询划分成多个子查询，下发到各子查询节点，各节点使用单连接查询算法执行连接查询。实验结 果表明，本文提出的两阶段多连接查询方法，能够充分利用网内各节点的能量，有效地延长网络的生存周期。 本文后续部分安排如下：第 2 部分介绍相关工作；第 3 部分描述基于缓存的单连接查询处理方法；第 4 部分给出基于缓存的多连接查询处理方法；第 5 部分阐述实验及结果；最后在第 6 部分给出了本文的结论。
MANET 中基于缓存的两阶段多连接查询方法
柳絮，李金宝，郭龙江，范斌
( 黑龙江大学计算机科学技术学院 , 黑龙江哈尔滨 150080) ( 黑龙江省数据库与并行计算重点实验室 , 黑龙江哈尔滨 150080)


摘 要:
针对 MANET 环境下的连接查询问题，首先提出基于缓存的单连接查询问题，证明该问题是 NP-完全
问题，并给出一个多项式近似算法，该算法采用贪心策略，得到一个使得能量消耗小的近似解。然后考虑多连接 查询的代价， 提出一种基于缓存的两阶段多连接查询处理方法， 降低查询的响应时间， 最小化网络中的能量消耗。 理论分析及实验结果表明该算法能够有效地减少网络中能量消耗，延长网络生存周期，提高查询效率。 关键词: MANET; 连接查询; 多连接 文献标识码 : A 中图法分类号 : TP393
[6]
提出一种无线传感器网络中的多连接查询方法，该方法近似地定义水平路径和垂直路径，通过空间的限制
和扩大来合并连接。Stern 等人[7]提出一种有效的多连接处理方法，该方法首先收集被连接的两个关系中，公 共属性的所有值，建立一个过滤器，筛选所有不在结果中的数据，并将该过滤器广播到全网。节点收到该过 滤器后，使用该过滤器将需要的元组发送至 Sink。但该方法在建立过滤器的过程中消耗大量能量。 上述对连接查询的相关研究，大多需要数据仓库对数据进行集中式处理，主要采用一些启发式算法或集 中式算法，这些算法计算量大，操作复杂，对资源有限的 MANET 并不适用，因此很难得到较好的结果。因 此，本文引入缓存技术来处理多连接查询问题，减少网络中的通信量和计算量，有效延长网络生存周期。
2 相关工作
在对无线网络的研究中，数据缓存的思想被广泛用来解决数据处理等问题 [1, 2]，由此可见，对于缓存技 术的研究已经日趋完善。近年来，对于查询处理的研究也已经取得了不少研究成果，但是，在查询处理问题 中，对数据缓存的技术研究还很少见。 Chen 等人[3]提出了一种积累的轮廓查询处理方法，递增地查找轮廓点。 Zhou 等人[4]提出了一种对目标轨迹的处理和查询的方法，该方法根据时间及轨迹的连贯性查找到在该轨迹上
等式最小的 k 值，就可以确定使得 Cost( Ri~i)最小的多连接查询执行顺序。由于在 Qop 中，动态规划的选择以 能量消耗为代价，所以其确定的连接执行顺序一定使得连接的能量消耗最小。 4.2 基于缓存的多连接查询处理算法 当多连接查询的执行顺序确定后，查询节点下发查询消息至缓存节点以提取相应的数据项。但是，如果 所有的查询消息都由该查询节点下发，则有可能增加查询处理的延迟，造成该查询节点周围节点的能量消耗 过快， 导致网络死亡。 为了避免以上情况的发生， 本节将根据查询节点的集合和 Qop 的结果建立一棵查询树， 由各查询节点并行地执行连接查询，解决查询节点周围节点能耗过快问题，减少查询延迟。在该查询树中每 个叶节点均由查询节点组成，而内节点为两个查询节点存储关系的连接结果，根节点由主查询节点担任。 当查询树建立完成后，主查询节点下发查询消息，各查询节点接到查询消息后，根据其在查询树中的位 置并行地执行各自的查询任务，并将中间结果缓存至离主查询节点较近的节点，以使得网络中的数据传输量 最小。基于以上思想，本节给出 Moca 算法的执行过程。设 T1，T2，…，Tn 为缓存关系 R1，R2，…，Rn 的查 询节点，Tk 为主查询节点。Moca 首先按照 T1，T2，…，Tn 与 Tk 间的距离建立多连接，然后执行 Qop，获得 最优的连接执行顺序， 建立查询树。 每个查询节点 Ti 按照在查询树中的位置， 与其兄弟节点进行单连接操作。 对每个单连接操作，判断距离主查询节点的位置，并选择距离较近的节点作为中间结果缓存节点，以减少网 络中的传输量。各查询节点并行地执行相应查询任务，将最后结果汇总至 Tk。Moca 算法的描述如下。 算法 1 基于缓存的多连接查询处理算法 Moca 1： T={T1，T2，…，Tn }; 2： 按照 T1，T2，…，Tn 与 Tk 之间的距离建立多连接 R1 R2 … Rn; 3： Qop(R1 R2 … Rn); 4： 以 T1，T2，…，Tn 为叶节点，Tk 为根节点，建立查询树 ; 5： While (T={Tk}) 6： For i = 1 to n-1 par-do 7： If (Ti 与 Ti +1 互为兄弟) 8： If ( Ti 与 Tk 的距离< Ti+1 与 Tk 的距离) 9： Ti 运行 Soca ，连接 Ri+1 并缓存结果 ;设置 Ti 为其查询树中的父亲节点 ; T=T-{Ti+1}; 10： Else 11： Ti +1 运行 Soca ，连接 Ri 并缓存结果 ;设置 Ti+1 为其查询树中的父亲节点 ; T=T-{Ti };
3 基于缓存的单连接查询处理
对于本文研究的网络，做如下假设： (1) 节点均匀分布在一个二维平面区域且位置已知。(2) 节点已知其 他节点上缓存的数据。(3) 节点分为查询节点、缓存节点和普通节点三类。查询节点负责发送查询消息和返回 查询结果；缓存节点是为了提高查询效率而缓存某些查询频率较高数据的节点；普通节点负责数据的收集和 转发。(4) 每个查询节点均缓存一个相应关系的全部数据项。 (5)节点由于计算所消耗的能量忽略不计。 3.1 问题定义 定义 1： 基于缓存的单连接查询问题 SQBC (Single-join Query Based on Caching) 。 假设被连接的关系为 R， 当网络中存在一些缓存节点，其缓存一部分关系 R 中的数据项，那么，在能量消耗较小的条件下，选择若干 个缓存节点， 将其缓存数据传输至查询节点， 并在该节点上进行连接操作的问题称为 SQBC。 下面给出 SQBC 的形式化定义。已知被连接关系 R 的所有数据项 Z，所有缓存关系 R 的节点集 C，及其所缓存的数据项集 Data(C) ，令 Data( C) = { Data( Ci)| Data( Ci)为缓存节点 Ci 缓存的数据项}，Z =∪S ∈C Data( S) 。那么，SQBC 问 题就是寻找一个 Q C，满足：(1) Z =∪S ∈Q Data( S)，(2) Q 是使得连接查询代价最小的节点集合。这里的连 接查询代价是指将 Q 中所有节点相关的缓存数据转发至查询节点所消耗的能量。 3.2 基于缓存的单连接查询处理算法 由于在资源有限的 MANET 环境下，找到一个 SQBC 问题的最优解将会消耗网络中大量的能量。因此， 为了有效利用网络中的能量，延长网络生存周期，本节将给出一个 SQBC 问题的多项式近似算法 Soca，Soca 算法主要采用贪心策略，其基本思想如下：首先定义集合 U 为 Z 中尚未被收集的数据项集合，然后贪心地选 出使得 Data(Ci) 与集合 U 有最大交集的节点 Ci。但是，网络中除了 Ci 以外，存储关系 R 中所有数据项的查询 节点 r 也存储 Data(Ci)∩U 相关的数据项。那么，选择距离查询节点较近的节点转发 Data(Ci)∩U 相关的数据 项，则可以有效减少网络中的能量消耗。判断若 r 距离查询节点 q 较近，则 q 直接发送查询消息至 r，消息 中包括被连接的关系名称， 以及需要 r 转发的数据项集合 Data(Ci)∩U 等等。 当 r 收到 q 的消息后， 将 Data(Ci )∩U 转发至 q。否则若 q 与 Ci 较近，则 q 发送查询消息至 Ci ，Ci 将数据项 Data( Ci)∩U 发送至 q。重复上述过程， 直到 Data(Q) = Z。上述算法中，连接所有数据项的循环次数最多为 min(| Z| ，| C|) ，而从集合 C 中选择 Ci 需要 的时间为 O(|C| | Z|) ，所以算法 Soca 所需时间复杂度为 O(| C| | Z| min(|Z|，| C|)) 。