覆盖网络在普适传感器管理中的应用

### 覆盖网络在普适传感器管理中的应用 #### 1. 引言 随着传感器技术的发展和互联网的全球普及，大量异构传感器网络在全球范围内发展并相互连接，以共享普适传感数据。同时，现代传感设备变得更加智能，价格也迅速下降。为了在全球范围内共享传感数据，一个具有可扩展性和多属性搜索功能的去中心化系统至关重要。 #### 2. BATON与BATON* 在数据库领域，B - 树是创建数据索引的主要方法。BATON通过管理平衡树结构支持范围查询。在这种树结构中，每个节点（如机架式机器、台式PC）对应树的一个节点，且每个节点被分配一个值的范围，该范围需在其左子树管理范围的右侧，且小于其右子树管理的范围。这种索引结构基于名为T - 树的主内存索引。 BATON的节点除了管理与父节点和子节点的链接外，还管理与同一层其他节点的多个链接。通过这些同一层的链接，节点可以通过O(log N)条消息访问其他节点。例如，若节点A搜索与‘74’相关的数据，查询可以通过四条消息到达节点B。与Skip Graph和SkipNet相比，BATON通过平衡树结构改善了负载平衡，并支持范围查询，但维护树拓扑会产生额外成本。 BATON*是BATON的扩展，用于支持多属性查询。它对属性进行优先级排序，并使用希尔伯特空间填充曲线将三个低优先级属性简化为一维索引。与Mercury相比，BATON*通过减少属性数量降低了管理ID空间的成本。 #### 3. Live E!项目 Live E!使用树拓扑结构，传感器所有者添加Live E!服务器来管理传感器数据，并可通过服务器控制数据访问。这种树拓扑适合在分布式环境（如DNS）中实现认证机制。然而，在传感器网络中，需要从多个站点收集传感器数据并回复用户查询，在大规模且管理着来自全球数十个站点的多种不同类型传感器数据的环境中，进行多属性搜索较为困难。 Live E!服务器分别管理传感器设备的配置文件和传感器数据，并定期从子站点接收这些配置文件。每个服务器根据这些配置文件创建索引表，并将其用作路由表，以支持多属性搜索和分布式环境中的认证机制。但支持多属性搜索的成本较高，响应性能不佳，因为此类查询需要通过不同国家的多个服务器进行传递和计算。 #### 4. Mill方法 ##### 4.1 ID空间管理 Mill是一种基于地理位置的覆盖网络，旨在提高Live E!项目的性能。它将二维空间按纬度和经度划分为网格单元，每个网格单元是一个小正方形区域。若每个网格单元用64位ID表示地球表面，其大小可达毫米级，足以表示普适传感环境中的小区域和大区域。 为简单说明ID管理方法，假设每个单元分配一个4位标识符。Mill将这些ID作为一维循环ID进行管理，每个Mill节点负责部分循环ID。单元ID通过交替x和y位生成，例如，若x位为‘00’，y位为‘11’，则单元ID为‘0101’，这种方法称为“Z排序”。在实际应用中，Mill的ID空间（地球表面）由64位表示。 Mill将正方形区域表示为连续的单元ID，并可通过一个查询搜索正方形区域中的目标数据。它通过少量查询即可搜索任何区域大小的位置相关信息，从而减少与地理位置相关的查询。例如，在搜索目标区域时，不同覆盖网络的搜索成本如下： - DHTs仅支持精确匹配查询，搜索成本为2i × log N，其中i是位数，N是节点数。 - 支持多属性搜索的覆盖网络独立管理每个属性，搜索成本为2 log N + 2m×232/2i/2，其中m是目标区域中的节点数。 - Mill网络中，节点可以同时搜索顺序ID，搜索成本为logN + m。 当i = 54，m = 20，N = 20480时： - DHTs：254 × log 20480 = 2.58 × 1017 - 多属性：2 × log 20480 + 2 × 20 × 232/227 = 1309 - Mill：1/2 log 20480 + 20 = 27 为支持多属性搜索，Mill分两步回复查询：首先搜索管理与查询相关区域的节点，然后该节点查询其他属性并将结果发送给用户。 ##### 4.2 覆盖网络的实现方法 为提高重复查询的性能，Mill使用带有迭代路由的跳表作为路由信息的缓存。在Mill网络中，节点根据地理位置管理传感器数据。用户若持续检查特定区域的当前状态，会不断与同一节点通信。通过迭代路由的跳表创建的路由信息缓存，可使查询和传感器数据在特定局部区域动态聚类，节点和传感设备可以直接连接到目标节点。 传感设备也以同样方式直接将数据上传到目标节点。迭代路由的缓