0311(物联网搜索)66

1、物联网搜索物联网搜索2022-4-111INTRODUCTION TO THEReal-Time Search for Real-World Entities2022-4-112ubiquitous computingMark Weiser (1991) 提出了普适运算the father of ubiquitous computing (1988)a chief scientist at Xerox PARC (施施乐乐帕克帕克研研究中究中心心)in the United States2022-4-113ubiquitous computing 普适运算并非将基础技术全盘翻新，普适运算技术运

2、用了无线电网络的科技，让人们在不受时空限制的环境下享用资讯透过整合式无缝科技技术，让人们使用起来更便利，省时。2022-4-1141面向物联网的面向物联网的搜索服务描述搜索服务描述2022-4-115基本要素及实现过程特点及面临的挑战2022-4-116物理世界实体物理世界实体2022-4-117物理世界实体与实体相连感知其状态的传感器用户提出的对实体状态或指定状态实体的查询接收查询、处理并返回查询状态或与查询相符实体的搜索引擎基本要素及实现过程2022-4-118面向物联网的搜索示意图面向物联网的搜索示意图2022-4-119特点及面临的挑战VS2022-4-1110搜索对象的比较由传感器自

3、动生成的快速变化 的结构化内容2022-4-1111搜索对象的比较主要指因特网上的网页及PDF、 DOC等由人工输入、静态或缓慢变化的非结构化内容2022-4-1112面向物联网的搜索特点及面临的挑战2022-4-1113搜索内容的时空性强庞大的数据量数据的高度动态性传感器节点的资源受限传感器节点的移动性安全和隐私问题2022-4-1114搜索内容的时空性强只需在指定区域查找实体需要检索的信息具有高度的时效性， 只有实时或预测将来的数据才有意义安静的餐厅安静的餐厅不拥塞的道路不拥塞的道路2022-4-1115庞大的数据量随着物联网的广泛推广，物联网搜索信息量与现有的网页数量相比，将会发生数量级

4、的飞跃。2022-4-1116数据的高度动态性 实体特征数据每分每秒都在变化，传感器实时对这些高度动态变化的信息进行检测存储，针对网页设计的索引方法，几乎无法适用，因此，创建一种对实时信息创建索引的方法很重要2022-4-1117数据的高度动态性2022-4-1118传感器节点的资源受限传统的网页搜索内容均是由资源丰富的PC终端等输入，内容生成及发送次数一般不受限制，而传感器终端因为能量受限，节点的频繁通信是不允许的。2022-4-1119传感器移动性受限附着在实体之上的传感器，会随着实体的移动而移动，这使在网络中始终维持注册最新信息成为一个很大的挑战。2022-4-1120安全和隐私问题人们

5、可以不选择使用网页、或不频繁更新网页或设置网页不可搜索，但是，当传感器成为每个实物如一双鞋的附属物时，用户可能都不知道它们的存在。2022-4-1121安全和隐私问题2022-4-1122面向物联网搜索的基本策略22022-4-1123主动发送与被动索取信息发布/订阅使用中介节点倒排索引压缩技术建立模型实体评分与排名Top-k查询2022-4-1124主动发送与被动索取pull and push 在分布式环境中，实体搜索功能的实现需要描述实体状态的数据存储在某位置等待用户的查询。有如下三种方式2022-4-1125主动发送与被动索取pull and push Push：实体主动将数据发送到用户

6、方，将数据存储在用户系统中，查询功能在用户本地实现。2022-4-1126主动发送与被动索取pull and push Pull：实体本地存储数据，查询时用户向实体发送查询语句后将数据取回2022-4-1127主动发送与被动索取pull and push Push和Pull混合的方法：数据被发送到某一位置，用户从该位置取回数据(mediators)，并且有一些频繁被查询到的数据直接被Push到用户端，而另一些很少被查询到的数据则留在实体一端等待用户Pull出。2022-4-1128信息发布/订阅Publish/Subscribe建立实体与用户间的明确关系对连续查询时很有用的。例如实体数据可以仅

7、被Push到满足潜在匹配查询的用户处，或用户查询只对潜在匹配实体进行Pull操作。Publish/Subscribe是当用户只对某些实体或数据感兴趣时的常用技术，它可以只将与订阅内容相匹配的数据交付给用户。2022-4-1129信息发布/订阅Publish/Subscribe2022-4-1130使用中介节点(mediators)Mediators是一个逻辑上处于实体与用户之间的概念成分，通常用来维护一个实体的聚合视图(aggressive view)。例如，发送到一个mediator的查询无须Pull所有实体的数据即可实现。Mediator可以在集中或分散（如一个Mediator层次结构，上

8、级中介super-mediator具有子中介sub-mediator的聚合视图）下实现。2022-4-1131倒排索引inverted index维持一个实体集聚合视图的mediator要能有效地根据查询要求指定的某种状态查找出对应实体。inverted index就是满足这样要求的一种数据结构，它可以高效地从实体集中查找出生成某种数据的实体。这种索引表中的每一项都包括一个属性值和具有该属性值的各记录的存储位置。2022-4-1132压缩技术Compression用来减少数据和查询所需的存储和通信量，如mediators通常存储经过压缩的实体数据聚合视图。使用无损压缩不会对系统的基本操作造成影

9、响。而使用有损压缩则只能维持一个近似的视图，在这种情况下，查询结果或者为启发式的，或者将近似视图用在确定实体或用户子集，以便随后执行Push或Pull操作获得准确结果。2022-4-1133建立模型Models使用模型可以在没有实际交流的情况下，推断与用户或实体有关的信息。实体集可以通过用户模型来决定该用户是否对某个实体感兴趣，从而将数据只Push到对其感兴趣的用户处。2022-4-1134建立模型Models通常依据过去的信息来构建模型，如关于一个实体状态的统计模型可以由该实体以前的状态来构建。与压缩技术一样，基于模型的技术或导致启发式查询剖析，或用来确定实体或用户集，以便Push或Pull

10、操作，最终获得准确结果。2022-4-1135实体评分与排名Scoring and Ranking2022-4-1136实体评分与排名Scoring and RankingScoring是根据实体与查询的相关度对实体评分，ranking根据该分数对实体进行排名。使用scoring和ranking有两个目的。2022-4-1137实体评分与排名Scoring and Ranking给用户提供与查询需求最相关的实体可以据此首先对排名靠前的实体进行Push、Pull操作等操作以提到效率。一个统一的评分方式是实现实体间直接比较的重要前提。例如，在基于关键词的搜索中一般考虑关键词的总频率，高频词会较低频

11、词给予更高的权重。2022-4-1138Top-k查询top-k querytop-k查询是指返回查询结果返回集中K个最相关的实体，因为一般的查询无须将所有匹配实体都返回。有时可以不考虑所有实体而直接找到Top-k实体，这与找到所有实体然后返回其子集的蛮力方法相比可以大大提高查询效率。2022-4-11392022-4-1140现有主要系统分析32022-4-1141SnoogleDyser2022-4-1142snoogle基本思想：把对实体的文本描述以关键词的形式存储到传感器节点中以待用户查询，如一本书的附属节点中含有关键词”书“。用户提出由一组关键词组成的Ad hoc查询后，系统经过对比

12、返回匹配列表的前K项，其中列表中内容匹配度依次递减，K由用户指定。2022-4-1143snoogle系统架构示意图系统架构示意图2022-4-1144两级mediator结构下层称为索引点（index points），每个IP维护一个一定地理范围内所有传感器节点的聚合视图。上层的mediator称为关键索引点（Key IP），它负责维护整个网络的聚合视图。2022-4-1145搜索过程移动节点的搜索由IPs间的移交协议实现。一般地，由IP周期性地发送信标信息来检测节点是否在其范围内，当有节点移入或移出时更新其索引并通知KeyIP。也可以使用计时器方法，由节点发送保持活动消息，同时IP维护一个

13、计时器。若一段时间内没有收到节点的消息，IP将其从索引表中删除，其他检测到节点消息的IP将节点加入到索引表中。2022-4-1146通信压缩系统采用Bloom filter方法实现通信压缩，将一组关键词由n bit向量表示。该方法是一种空间效率很高的随机数据结构，它利用位数组很简洁地表示一个集合，并能判断一个元素是否属于这个集合。2022-4-1147如何排序局域搜索时，查询消息直接发到IP，IP根据其倒排索引计算出匹配传感器的排序列表并将前K个结果返回。2022-4-1148如何排序查询时，系统根据匹配关键词的数量对传感器进行排序，为统一不同IP的排序，需要把关键词在一个IP包含的所有节点中

14、出现的总频率纳入到排序算法中。2022-4-1149如何排序查询时，系统根据匹配关键词的数量对传感器进行排序，为统一不同IP的排序，需要把关键词在一个IP包含的所有节点中出现的总频率纳入到排序算法中。2022-4-1150如何排序全局搜索时：Key IP收到查询请求后，采取如下方法：向所有IPs查询并返回当地级别最高的传感器节点，将这一列表存储在全局排序表中。为获得级别第二的节点，KeyIP向所有IPs发送查询请求，要求仅返回分数高于全局排序中级别第二的节点。将其插入到全局排序表中第二的位置，依此类推，直至获得用户要求的K个节点。最后将结果返回2022-4-1151总结snoogle系统是第一

15、个基于传感器网络的物理世界信息检索系统，Bloom filter压缩算法，分布式Top-k查询算法的使用减少了通信开销，安全隐私管理保障了用户的信息安全。2022-4-1152总结但是，该系统仅支持伪静态元数据的搜索，KeyIP的集中性质不适于全球搜索，而且Bloom filter的使用会导致查询结果不准确，Top-k算法在减少通信开销的同时也会产生大量的中间数据。2022-4-1153DyserDyser是一个针对物联网的实体实时搜索引擎，它充分利用现有的Internet网络设施，实现了对快速变化内容的可伸缩式搜索。系统可以根据用户指定的当前状态搜索实体，如可搜索一栋大厦里现在空闲的房间，某

16、区域目前较安静的地方等。2022-4-1154Dyser系统架构示意图系统架构示意图2022-4-1155系统架构介绍传感器sensor和实体entity时模型中的两个关键元素，每个传感器和实体都与一个由网页地址URL确定、通过HTTP协议访问的Web资源对应。所有这些Web资源又有一个HTML表示，通常称其为传感器页（sensor page）和实体页（entity page）。2022-4-1156系统架构介绍除了非结构化文本，页面中还包含一些如传感器类型、可能读数等结构化信息。传感器与实体之间是多对多的关系。图中解析器用来处理用户查询、索引存储传感器和实体的索引元数据。索引器类似网络蜘蛛抓

17、取传感器和实体网页。2022-4-11572022-4-1158建模及排序系统采用传感器排名sensor ranking方法对传感器排序，以便进行选择性的搜索。排序基于预测模型实现，由模型返回在一特定时间传感器读数为指定值的概率值，该模型由传感器或传感器网关创建，并发布在相应的传感器页上。2022-4-1159建模及排序可以根据不同场合选择不同的预测模型，Dyser系统中提出汇总预测模型（APM）、单周期预测模型（SPPM）、多周期预测模型（MPPM）三种模型。2022-4-1160搜索过程搜索时，搜索引擎首先从索引表中获得含有请求类型传感器的实体，根据实体与搜索的匹配度计算出实体的匹配概率（该值为与实体相关符合匹配的传感器的概率值和）；根据概率值由大到小对实体进行进行排序后从头开始核对实体的状态与要求值是否相同。当一个实体所有状态都相符时，输出实体并继续审阅下一