欢迎光临本站!

典型的物联网搜索系统

来源:技术探讨    更新时间:2019-12-13 15:39:00    编辑:老王    浏览:434

  Snoogle/Microsearch

  由美国弗吉尼亚州立大学(彼得斯堡)的研究人员设计的Snoogle系统中[77, 78],对实体的描述是以一组关键字(文本信息)的形式存储在传感器节点中。Snoogle的系统架构如图2所示。

  该系统的思想是用关键字对连接到物理实体的传感器进行描述,用户通过关键字查询匹配的目标物理实体,系统将返回查询相匹配集中最相关的K个实体。该系统由2层mediator组成。底层的mediator称为索引点(IP, index point),每个IP维护管理一个特定范围的传感器(也即一个传感器属于唯一的IP)。顶层的mediator称为关键索引点(KeyIP, key index point),关键索引点维持着整个网络的聚合视图。传感器传送变化的文本描述信息到IP节点,所有的IP节点在把信息传送到关键KeyIP节点。当用户查询的是某个特定IP中的实体信息时,用户可以直接向该IP节点发送查询请求。用户也可以向一个KeyIP节点发送查询,查询全局范围内的实体信息。

  为了实现高效查询,IP和KeyIP都使用了倒排索引技术。大部分的研究工作致力于如何在典型的传感器节点的缓慢、页面结构的闪存中维持索引。移动节点的搜索是通过在IP节点之间使用交换协议实现的。IP节点周期性地发送信标信息,检测传感器的存在。当检测到传感器出现或者消失时,IP节点将更新其索引项,并通知KeyIP节点。为了压缩通信,提高通信效率,采用了Bloomfilter表示一个关键字集合。Bloom filter是一个mbit的二进制的向量。通过相互独立的n个散列函数将一个元素映射到Bloom filter向量中的nbit,映射位置被设置为”1”。为检查一个关键字是否属于Bloom filter集合,需要对这个关键字应用n次散列函数,如果所有映射位置都是”1”,则认为是属于Bloom filter集合。

  在判断一个关键字是否属于一个Bloom filter集合时有可能会把本不属于该Bloomfilter集合的元素误认为属于这个集合,但本身是属于集合中的元素是不会出现漏判的。当处理查询时,传感器将按照其包含的关键字的数量进行排序。为了在各IP之间标准化排名,关键字在一个IP包含的所有传感器中出现的总频率被纳入了排名计算中。进行局部查询时,查询请求直接发送到一个本地IP,IP利用倒排索引技术对匹配集合中传感器进行排名并返回排名最前的k个结果。对于全局查询而言,查询请求将被传送到KeyIP。

  KeyIP在计算全局最匹配的k个结果时并没有索取所有IP节点的全部匹配结果。首先,发送查询请求给所有IP并返回每个IP最高排名的传感器节点,并对这些节点进行排序,得到一个有序列表并存储在KeyIP中的全局列表中。在全局列表中排名最高的传感器作为全局查询结果的最高排名传感器返回给用户。为了得到排名第二的传感器,KeyIP继续发送查询请求给所有IP节点,但仅返回比全局排序表中排名第二的传感器排名分数高的传感器,并把这些结果依序插入到全局排名表中,这时全局排序表中排名第二的传感器就是所要找的结果再返回给用户。继续以此类推,直到向用户返回了排名最高的k个传感器。

  该系统的局限性有2点:首先,尽管采用了push方式及时地推送传感器数据到IP和KeyIP来解决元数据动态变化的问题,但这一方式显然无法应用于大规模的网络环境,因此该系统不支持动态的数据搜索,仅支持静态数据搜索和伪静态数据搜索;其次,由于KeyIP集中管理整个网络的完整视图,对于每一个全局查询KeyIP都需要查询索取所有IP节点,因此该系统不适合全球化的搜索。而Topk算法在减少通信开销的同时也产生了大量的消息;最后,Bloom filter压缩算法的使用导致查询结果是不精确的。

典型的物联网搜索系统

评论区

表情

共0条评论
  • 这篇文章还没有收到评论,赶紧来抢沙发吧~

相关内容

点击排行

随机新闻

评论排行榜