在无线传感器网络中分布式Top-k查询方法

摘要

本发明涉及一种在无线传感器网络中分布式Top-k查询方法，其包括如下步骤：a、利用图形G表示无线传感器网络G=(V,E)；对所述图形G建立对应的联通支配子集C，并得到被统治节点集V′，所述联通支配子集C内包含若干统治节点；b、对上述联通支配子集C中所包含的所有统治节点，利用广度优先搜索方法，得到以汇聚节点v₁为根的BFS树；c、统治节点向所有被统治节点发布消息，以使得被统治节点将自身持有的数据发送给对应的统治节点，统治节点采集到的被自身统治的被统治节点的数据与所述统治节点自身持有的数据一起构成了数据集S；d、汇聚节点v₁以上述BFS树中所有统治节点获取的数据集S为依据，查询得到所需的Top-k个数据。本发明步骤操作方便，查询效率高，适应范围广。

主权项

一种在无线传感器网络中分布式Top‑k查询方法，其特征是，所述分布式Top‑k查询方法包括如下步骤：(a)、利用图形G表示无线传感器网络G＝(V,E)，其中，V为包含所有无线传感器网络节点的集合V＝{v₁,v₂,…,V_n}，E为包含所有无线传感器节点之间的边；对所述图形G建立对应的联通支配子集C，并得到被统治节点集V′，所述联通支配子集C内包含若干统治节点；(b)、对上述联通支配子集C中所包含的所有统治节点，利用广度优先搜索方法，得到以汇聚节点v₁为根的BFS树；(c)、统治节点向所有被统治节点发布消息，以使得被统治节点将自身持有的数据发送给对应的统治节点，统治节点采集到的被自身统治的被统治节点的数据与所述统治节点自身持有的数据一起构成了数据集S；(d)、汇聚节点v₁以上述BFS树中所有统治节点获取的数据集S为依据，查询得到所需的Top‑k个数据；所述步骤(a)中，对于图形G利用贪婪算法建立得到联通支配子集C；所述步骤(a)包括如下步骤：(a1)、设定图形G的子集C′为C′＝{v₁}，且集合V″＝V/{v₁}；(a2)、针对集合V″中所有的节点，按照度由大到小排列，将度最大的点v_m从集合V″中移除并加入到子集C′中，即C′＝C′∪{v_m}，集合V″＝V″/{v_m}；(a3)、将节点v_m所有的邻居节点从集合V″中移除，并将所有与节点v_m相关的边均从E中删除，所有由于节点v_m被选入子集C′中而导致自身从集合V″中移除的节点形成被统治节点，且所述被统治节点均以节点v_m作为统治节点；(a4)、重复上述步骤(a2)及步骤(a3)，直至集合V″中的节点都至少有一个邻居节点位于子集C′中，子集C′中所有的节点构成了图形G的支配子集；(a5)、利用贪婪算法从上述集合V″选择节点，并将选择的节点加入到子集C′中，使得子集C′中所有的节点成为一个联通的组件，得到联通支配子集C，通过集合V″得到被统治节点集V′。