《0311(物联网搜索)66》由会员分享，可在线阅读，更多相关《0311(物联网搜索)66（66页珍藏版）》请在金锄头文库上搜索。
1、*0311(物联网搜索)661物联网搜索*0311(物联网搜索)662INTRODUCTION TO THEReal-Time Search for Real-World Entitiesubiquitous computingMark Weiser (1991) 提出了普适运算the father of ubiquitous computing (1988)a chief scientist at Xerox PARC (施乐乐帕克研究中心)in the United States0311(物联网搜索)662021/11/223ubiquitous computing 普适运算并非将基础技术
2、全盘翻新，普适运算技术运用了无线电网络的科技，让人们在不受时空限制的环境下享用资讯透过整合式无缝科技技术，让人们使用起来更便利，省时。0311(物联网搜索)662021/11/224*0311(物联网搜索)6651面向物联网的搜索服务描述基本要素及实现过程特点及面临的挑战0311(物联网搜索)662021/11/226物理世界实体0311(物联网搜索)662021/11/227物理世界实体与实体相连感知其状态的传感器用户提出的对实体状态或指定状态实体的查询接收查询、处理并返回查询状态或与查询相符实体的搜索引擎基本要素及实现过程0311(物联网搜索)662021/11/228面向物联网的搜索示意
3、图0311(物联网搜索)662021/11/229特点及面临的挑战VS0311(物联网搜索)662021/11/2210搜索对象的比较由传感器自动生成的快速变化 的结构化内容0311(物联网搜索)662021/11/2211搜索对象的比较主要指因特网上的网页及PDF、 DOC等由人工输入、静态或缓慢变化的非结构化内容0311(物联网搜索)662021/11/2212面向物联网的搜索特点及面临的挑战0311(物联网搜索)662021/11/2213搜索内容的时空性强庞大的数据量数据的高度动态性传感器节点的资源受限传感器节点的移动性安全和隐私问题0311(物联网搜索)662021/11/2214搜
4、索内容的时空性强只需在指定区域查找实体需要检索的信息具有高度的时效性， 只有实时或预测将来的数据才有意义安静的餐厅不拥塞的道路0311(物联网搜索)662021/11/2215庞大的数据量随着物联网的广泛推广，物联网搜索信息量与现有的网页数量相比，将会发生数量级的飞跃。0311(物联网搜索)662021/11/2216数据的高度动态性 实体特征数据每分每秒都在变化，传感器实时对这些高度动态变化的信息进行检测存储，针对网页设计的索引方法，几乎无法适用，因此，创建一种对实时信息创建索引的方法很重要0311(物联网搜索)662021/11/2217数据的高度动态性0311(物联网搜索)662021/
5、11/2218传感器节点的资源受限传统的网页搜索内容均是由资源丰富的PC终端等输入，内容生成及发送次数一般不受限制，而传感器终端因为能量受限，节点的频繁通信是不允许的。0311(物联网搜索)662021/11/2219传感器移动性受限附着在实体之上的传感器，会随着实体的移动而移动，这使在网络中始终维持注册最新信息成为一个很大的挑战。0311(物联网搜索)662021/11/2220安全和隐私问题人们可以不选择使用网页、或不频繁更新网页或设置网页不可搜索，但是，当传感器成为每个实物如一双鞋的附属物时，用户可能都不知道它们的存在。0311(物联网搜索)662021/11/2221安全和隐私问题03
6、11(物联网搜索)662021/11/2222*0311(物联网搜索)6623面向物联网搜索的基本策略2主动发送与被动索取信息发布/订阅使用中介节点倒排索引压缩技术建立模型实体评分与排名Top-k查询0311(物联网搜索)662021/11/2224主动发送与被动索取pull and push 在分布式环境中，实体搜索功能的实现需要描述实体状态的数据存储在某位置等待用户的查询。有如下三种方式0311(物联网搜索)662021/11/2225主动发送与被动索取pull and push Push：实体主动将数据发送到用户方，将数据存储在用户系统中，查询功能在用户本地实现。0311(物联网搜索)6
7、62021/11/2226主动发送与被动索取pull and push Pull：实体本地存储数据，查询时用户向实体发送查询语句后将数据取回0311(物联网搜索)662021/11/2227主动发送与被动索取pull and push Push和Pull混合的方法：数据被发送到某一位置，用户从该位置取回数据(mediators)，并且有一些频繁被查询到的数据直接被Push到用户端，而另一些很少被查询到的数据则留在实体一端等待用户Pull出。0311(物联网搜索)662021/11/2228信息发布/订阅Publish/Subscribe建立实体与用户间的明确关系对连续查询时很有用的。例如实体数
8、据可以仅被Push到满足潜在匹配查询的用户处，或用户查询只对潜在匹配实体进行Pull操作。Publish/Subscribe是当用户只对某些实体或数据感兴趣时的常用技术，它可以只将与订阅内容相匹配的数据交付给用户。0311(物联网搜索)662021/11/2229信息发布/订阅Publish/Subscribe0311(物联网搜索)662021/11/2230使用中介节点(mediators)Mediators是一个逻辑上处于实体与用户之间的概念成分，通常用来维护一个实体的聚合视图(aggressive view)。例如，发送到一个mediator的查询无须Pull所有实体的数据即可实现。Me
9、diator可以在集中或分散（如一个Mediator层次结构，上级中介super-mediator具有子中介sub-mediator的聚合视图）下实现。0311(物联网搜索)662021/11/2231倒排索引inverted index维持一个实体集聚合视图的mediator要能有效地根据查询要求指定的某种状态查找出对应实体。inverted index就是满足这样要求的一种数据结构，它可以高效地从实体集中查找出生成某种数据的实体。这种索引表中的每一项都包括一个属性值和具有该属性值的各记录的存储位置。0311(物联网搜索)662021/11/2232压缩技术Compression用来减少数据
10、和查询所需的存储和通信量，如mediators通常存储经过压缩的实体数据聚合视图。使用无损压缩不会对系统的基本操作造成影响。而使用有损压缩则只能维持一个近似的视图，在这种情况下，查询结果或者为启发式的，或者将近似视图用在确定实体或用户子集，以便随后执行Push或Pull操作获得准确结果。0311(物联网搜索)662021/11/2233建立模型Models使用模型可以在没有实际交流的情况下，推断与用户或实体有关的信息。实体集可以通过用户模型来决定该用户是否对某个实体感兴趣，从而将数据只Push到对其感兴趣的用户处。0311(物联网搜索)662021/11/2234建立模型Models通常依据过
11、去的信息来构建模型，如关于一个实体状态的统计模型可以由该实体以前的状态来构建。与压缩技术一样，基于模型的技术或导致启发式查询剖析，或用来确定实体或用户集，以便Push或Pull操作，最终获得准确结果。0311(物联网搜索)662021/11/2235实体评分与排名Scoring and Ranking0311(物联网搜索)662021/11/2236实体评分与排名Scoring and RankingScoring是根据实体与查询的相关度对实体评分，ranking根据该分数对实体进行排名。使用scoring和ranking有两个目的。0311(物联网搜索)662021/11/2237实体评分与
12、排名Scoring and Ranking给用户提供与查询需求最相关的实体可以据此首先对排名靠前的实体进行Push、Pull操作等操作以提到效率。一个统一的评分方式是实现实体间直接比较的重要前提。例如，在基于关键词的搜索中一般考虑关键词的总频率，高频词会较低频词给予更高的权重。0311(物联网搜索)662021/11/2238Top-k查询top-k querytop-k查询是指返回查询结果返回集中K个最相关的实体，因为一般的查询无须将所有匹配实体都返回。有时可以不考虑所有实体而直接找到Top-k实体，这与找到所有实体然后返回其子集的蛮力方法相比可以大大提高查询效率。0311(物联网搜索)66
13、2021/11/22390311(物联网搜索)662021/11/2240*0311(物联网搜索)6641现有主要系统分析3SnoogleDyser0311(物联网搜索)662021/11/2242snoogle基本思想：把对实体的文本描述以关键词的形式存储到传感器节点中以待用户查询，如一本书的附属节点中含有关键词”书“。用户提出由一组关键词组成的Ad hoc查询后，系统经过对比返回匹配列表的前K项，其中列表中内容匹配度依次递减，K由用户指定。0311(物联网搜索)662021/11/2243snoogle系统架构示意图0311(物联网搜索)662021/11/2244两级mediator结构
14、下层称为索引点（index points），每个IP维护一个一定地理范围内所有传感器节点的聚合视图。上层的mediator称为关键索引点（Key IP），它负责维护整个网络的聚合视图。0311(物联网搜索)662021/11/2245搜索过程移动节点的搜索由IPs间的移交协议实现。一般地，由IP周期性地发送信标信息来检测节点是否在其范围内，当有节点移入或移出时更新其索引并通知KeyIP。也可以使用计时器方法，由节点发送保持活动消息，同时IP维护一个计时器。若一段时间内没有收到节点的消息，IP将其从索引表中删除，其他检测到节点消息的IP将节点加入到索引表中。0311(物联网搜索)662021/1
15、1/2246通信压缩系统采用Bloom filter方法实现通信压缩，将一组关键词由n bit向量表示。该方法是一种空间效率很高的随机数据结构，它利用位数组很简洁地表示一个集合，并能判断一个元素是否属于这个集合。0311(物联网搜索)662021/11/2247如何排序局域搜索时，查询消息直接发到IP，IP根据其倒排索引计算出匹配传感器的排序列表并将前K个结果返回。0311(物联网搜索)662021/11/2248如何排序查询时，系统根据匹配关键词的数量对传感器进行排序，为统一不同IP的排序，需要把关键词在一个IP包含的所有节点中出现的总频率纳入到排序算法中。0311(物联网搜索)662021
16、/11/2249如何排序查询时，系统根据匹配关键词的数量对传感器进行排序，为统一不同IP的排序，需要把关键词在一个IP包含的所有节点中出现的总频率纳入到排序算法中。0311(物联网搜索)662021/11/2250如何排序全局搜索时：Key IP收到查询请求后，采取如下方法：向所有IPs查询并返回当地级别最高的传感器节点，将这一列表存储在全局排序表中。为获得级别第二的节点，KeyIP向所有IPs发送查询请求，要求仅返回分数高于全局排序中级别第二的节点。将其插入到全局排序表中第二的位置，依此类推，直至获得用户要求的K个节点。最后将结果返回0311(物联网搜索)662021/11/2251总结snoogle系统是第一个基于传感器网络的物理世界信息检索系统，Bloom filter压缩算法，分布式Top-k查询算法的使用减少了通信开销，安全隐私管理保障了用户的信息安全。0311(物联网搜索)662021/11/2252总结但是，该系统仅支持伪静态元数据的搜索，KeyIP的集中性质不适于全球搜索，而且Bloom filter的使用会导致查询结果不准确，Top-k算法在减少通信开销的同时也会产生
