概述
　　通过集中式的大规模存储设施 物 联 网 中 传 感 器 采 集 到的大量信息可以被综合处理分 析 和 归 类 并分发给任何感兴趣 的 使 用 者 而使用者不必和传感器网络的制造搭 建 者 直 接联 系 高效实现数据的聚合和分发机制需要存储系统提供合适 的 数 据 接 口 最常用的数据接口是查询这 种 方 法 被 现 有的各种存储系统广泛支持 却有一个严重的缺点 查 询 过 程 必须由用户主动发起 但在物联网应用中 经 常 会 出 现 以 下 问题 使用者需要接收某些数据 但无法事先得知数据的到达时刻 某些紧急数据不能等待查询才传递给使用者 而 是 一旦出现就要尽快传递给使用者 连续性的数据应该被自动且连续地传递给使用者 而不需要用户反复查询
　　发 布订 阅 机 制 实 现 了 数据或 消 息生产者和消费者之间的解耦使 数 据或 消 息的生产者和消费者都不需要知道对方的具体信息 订 阅 者 通 常只对特定的数据感兴趣并且只接收感兴趣的数据 在 基 于内容的数据订阅 发 布 模 型 中 精确符合订阅者的订阅条件的数据会被主动推送给订阅者 发 布订阅模型可以实现大量物联数据的有效分发
　　现有大规模存储系统设计允许数千或者更多具有一定计算资源的存储节点构成网络 另 一 方 面 由 于 需 要 分 发的 数 据 量 巨 大 因此需要构建数据分发网络分布处理海量数据 的 分 发 如 果 将 这 两 个 网 络 合 并不仅可以降低系统硬件投 入还会减少不必要的网络间流量提高存储系统的性能
　　面向大数据量的分布式基于内容的发布订阅算法及分发网络在多篇论文中已有论述 但直接将其和支撑物联网的大规模存储系统合并会造成 由于物联网中传感器种类丰 富数据的动态性很强 不同种类数据到达的流量等随时间分 布 不 均 匀 简单的分布无法应对复杂多变的物联网环境如果直接将数据分发网络和节点存储网络合并 没 有 合 适的节点负载和资源调节机制数据分发可能会影响存储系统的 正 常 运 作
　　本文提出一种将基于内容的发布订阅网络和已有大规模存储系统中节点网络相结合的方案 该方案提供了负载调节和资源调配的功能 通过收集利用大规模存储系统节点网络中不同计算节点上零散的计算资源 来高效完成物联数据基于内容的分发任务 在节省系统流量的同时降低了系统的总成 本
　　本 文 第 节 给 出 基 于 内 容 发 布 订阅系统的相关定义和术 语第 节阐述设计目标 第 节首先给出数据分发的基本流 程 和 总 体 框 架 然后对该方案提供的各种机制和为实现设计目标所采取的算法分别进行了详细阐述和讨论第 节 给出一种具体的基于布隆过滤器的数据分发算法最 后 对 全 文进 行 总 结
　　定义
　　一 个对 象包括数据和表述数据特征的一系列键值对属性 例如一个摄像头采集的图片可能会附加一些数据来标识采集地点和采集时间等信息 此类描述性的信息被称为元信 息 其中每个键被称为 属 性订 阅是事先注册在系统中的一系列条件 一 个订 阅包括一系列断言组成的析取范式以及一个 目 标 地 址 例如对于以下给出的一个订阅的例子其 含 义 为每 个 满 足 或的对象将被推送给一 个断 言 包 括 一 个 约 束 和一个属性名称 例 如是一个包含约束 和 属 性 名称 的 断 言 约 束是测试数据时的最小单元 包 括一 个 值 和 一 个 操 作 符 不同数据类型有不同的操作符但每个操作符都是双目的 并生成一个布尔值后文将多次出现 断 言和约 束 这里对其进行特别说明 约 束是 针 对 属 性 的 而断 言是 针 对 对 象 的 因 此某属 性 符 合 约 束 即表示某对象符合一个包含该属性的断言后文 为 叙 述 方 便 将在针对特定属性的语境中直接使用约束来表达一个包含该属性的断言本文只考虑两种数据类型 数 字和字 符 串 因 为 布尔型可以被数字或字符串标识 本文并不单独考虑布尔型对于 数 字 类 型 定 义大 于 小 于 和等 于 而 对于 字 符 串 类 型 考 虑等 于 前 缀 和包 含 与其 中包 含 与操作检查字符串是否属于一个给定的字符串集合 此 外在 本 文 的 方 案 中 订阅格式虽然是一个合取范式但可以被拆分为多个具有相同目标地址的析取式 为 方 便 描述本文只讨论订阅条件中仅包含单个析取式的订阅设计目标大规模存储系统由大量节点构成 将数据分发网络直接整合到存储系统中可以 避免数据在两个系统之间频繁交换以 降 低 通 信 量 充分利用存储系统中已有硬件资源降低 硬 件 投 入 从而降低整个系统的总拥有成本 但大规模存储系统为方案设计提出一些不同的设计目标大规模存储系统中 整个系统的性能通常更加依赖于数据 的 复 制路 由移动等存储相关过程 数 据 分 发 过 程 必 须 非常小 心否则会影响正常的存储过程 换 言 之数 据 分 发 方 案需要具有节点负载自动调节能力 这样可以在存储过程中需要较多计算资源时自动释放计算资源 而不影响存储系统性能 同 时存储系统中的节点数目虽然众多但 每 个 计 算 能 力通 常 并 不 强 大 为了充分利用每个节点有限的硬件资源负载调节能力的调节粒度必须尽可能细另 外物联网通常包括大量不同种类的传感器 各 传 感 器产生数据的时间 种类和特点也各不相同 加上不同数据的分发需求千差万别 导致分发机制要处理的数据流量类 别 等 难以 预 计 需要设计提供健壮的自调节能力使得系统可以根据需求动态调配不同的分发任务所需的资源 从而高效完成分发 任 务方案设计数据分发基本流程对象到达存储系统时会被分配一个全局唯一的标识分发过程只使用对象的元信息和 流 程 结 束 时 所有匹配成功的订阅中的目标地址将会收到该在本文的方案中 参与整个分发过程的角色包括一个协调 者多个测试工作者以及一个匹配工作者 基 本 流 程 如 图所 示图 基 本 流 程对 象 到 达 存 储 系 统 后 和元信息被发送给协调者同时对象交给存储系统存储协调者将元信息分割为不同的属性和值并 分 配 不 同的测试工作者完成测试工作测试工作者检查并计算出一个包含该属性值所满足所有 约 束 的 集 合 测试工作者完成任务后 缓存结果并通知协调者全部工作者完成任务后协调者指定一个匹配工作者完 成 匹 配 工 作匹配工作者从不同的测试工作者收集计算出的集合在已注册的订阅信息中查找相关匹配并 将 对 象 推 送 给 所有匹配成功的订阅者详细设计和相关机制为 叙 述 方 便 下 文 将 一 次 找出某个属性所满足的所有约束 集 合的操作称为一个 任 务工作者是一个一次可以容纳一个任务执行的容器 现 有商用硬件通常包含多个独立计算核心 将一个物理节点划分成多个工作者可以更有效地利用计算资源 但 设 计 中 物 理 节点上容纳工作者的数量和计算核心数之间并没有严格的对应关系因为还要考虑到不占用计算资源的 操 作 和 需 要 保证计算资源的存储过程的存在 一个节点上可用工作者的数量可以在一定程度上反映该节点可用计算资源的多寡 工 作者可以根据需要被动态创建或终止 因此工作者的存在为节点负载调节提供了机制在每个工作者中 完成实际任务的是功能块 而 工 作 者 只提供功能块运行时的环境工作者和功能块的概念一定程度是受系统虚拟化 和云计算中基础设施即服务 概念的 启 发 工作者为功能块提供执行时的虚拟环境 功 能 块是执行具体任务的代码和数据的组合 工作者执行的任务种类由其中容纳的功能块种类决定 测试功能块负责对某一个特定属性的值进行测试找出其所有满足的约束 匹 配 功 能块收集测试功能块的结果对结果进行整合并最终查找出所有满足条件订阅的目标地址 图 说 明 了 物 理 节 点 工 作 者和功能块之间的关系图 工作者与功能块本 文 设 计 中 功 能 块 由可 执 行 镜 像简 称 提 供 的 代 码 和 数 据 镜 像 简 称 提供的数据组合而成 对 测 试 功 能 块 来 说 中 实 现 针 对 特 定数 据 类 型 的 测 试 则存储特定数据结构比 如 一 棵 包 含 所有 属性相关约束中出现字符串的三叉树 通 过 动态 组 合 不 同 的 和 可以获得特定功能的测试功能块例 如从实现字符串相关测试的 启 动并 附 加 属 性相 关 的 测 试 功 能 块 能够检查所有值为字符串的属 性 相 关 约 束 而 对 于 匹 配 功 能 块 的 功 能 是 收 集 测 试 功能块结果并查找出所有符合条件订阅的目标地址 则 包 含所有订阅相关信息 实际上只包含订阅对应的布隆过滤器和相 应 目 标 地 址 这些信息对匹配算法来说已经足够 基 于 布隆过滤器的具体数据分发算法将在下节详述一个工作者装载的功能块并不是固定的工 作 者 可 以 动态装载不同的功能块从而完成角色的转变 这 种 机 制 允 许整个网络中各种功能块的比例动态变化 即处理不同任务的能 力 动 态 变 化 为实现不同任务之间计算资源的动态调节提供 了 机 制所有工作者启动时都是空工作者 即 没 有 装 载 任 何 功 能块 的 工 作 者 增加一个空工作者意味着节点认为有资源同时可以执行一项新任务 但将具体资源分配工作延后到实际需要 时会使得节点负载调节机制和资源调配机制相独立协调者负责管理并分配任务给不同的工作者 测 试 工 作者按所能处理的属性名称组织成多个空闲队列 匹 配 工 作 者和空工作者也分别按队列维护 协调者还可以通过指令要求一个工作者装载指定功能块 在 分 配任务或要求工作者装载新功能块后 工作者将从对应队列中删 除工作者完成任务或装载 切换功能块完成后将给协调者发 送 一 条 信 息其中包括工作者当前装载的功能块标识考虑到系统的灵活性 协调者可以在任何时刻加入或 停止并在其他节点上重新启动工作者也可以随时加入和离开网 络 为实现协调者和工作者的动态协作给 出 如 下 协 议协调者和工作者在启动时都会广播一个数据包通知网络中所有节点自己的存在 称 之 为 包协调者收到工作者的 包 后会将该工作者加入自己 相 应 的 队 列 同时再广播一个 包 之所以在这里仍使用广播而不是单播 是 因 为 广播可能会丢包 人 为 地 增加一些消息可以保证所有工作者都会最终在某一时刻被加入网 络工作者在收到协调者的 包 之 后会用协调者的信息更新现有协调者信息 协 调 者 会 在 包中附带一个随机 字 段功能块通过该字段判断这个协调者是否是一个新的协 调 者负 载 调 节资 源 调 配容错及相关讨论节点的负载调节由所在节点负责 节 点 会 监 视 自 己 的 资源 利 用 率若资源利用率超过某一个上限阈值守 护 进 程 会 终止所有空闲工作者以防止被分配更多的计算任务若 利 用 率低于某个下限阈值 守护进程会启动一些新的空工作者一个工作者中的任务实际上划分了算法中可分布进行运算 的 最 小 单 元 元信息中不同的属性可以独立地进行测试而不 会 互 相 依 赖 而对同一属性的测试则不应被分开 这 是 因为约束之间通常具有包含关系很多运算是不必要的 例 如满足 约 束 的 属 性 值 一定也满足约束 因 此 这种以工作者为单位的调节机制提供了最细粒度的负载调节能力计算资源的动态调配能力指系统中某种类型任务的数量增加时可以获得更多的系统资源 例如当某种类型数据大量到 达 时负责对应属性相关测试工作者的数量也需要增加为实现这种资源动态调节协调者在分配任务时若发现当前没有对应的工作者 则 会若系统中还有空工作者则命令一个空工作者装载对应任务的功能块若系统中已无空工作者则从目前最长的空闲队列中取出一个工作者将之切换到当前任务若当前系统中已无任何空闲工作者说 明 系 统 已 满 负荷再增加任务会影响到正常存储过程因此什么都不做缓 存 任 务等待下一个可用工作者 工 作 者 装 载 功 能 块完成会主动通知协调者复杂系统中硬件或软件失效在所难免需 要 提 供 合 适 的容 错 机 制 这里仅考虑数量较多的工作者失效情况由于工作者可以在自己变为可用时主动报告状态协 调者只需要鉴别出已失效工作者并将之从队列中删除即可 工作者的失效主要分为两种任务分发给工作者之后工作者失效不 能 完 成 接 收 到的 任 务工作者在空闲时失效即工作者虽然仍在协调者的空闲 队 列 中但 已 失 去 响 应对于前一种情况 由于每种工作者完成任务相同协 调 者可以统计完成任务的平均时间 如果协调者发现一个工作者在超出平均时间很长时间内未有回应则认为节点已经失效会将任务重新分配给其他工作者 而对后一种情况 在 分 配任务到工作者之前 协调者和工作者之间会握手进行确认若失 败则直接删除该工作者 再分配任务给列表中的下一个工作 者而如果工作者由于网络中断等原因被协调者判断为已失效该工作者不会再收到任何任务 这种工作者不占用计算资 源因此并不需要立即被清理掉所在的物理节点负责定期清理那些长期没有任务的工作者即可基于布隆过滤器的测试和匹配算法布 隆 过 滤 器布 隆 过 滤 器 是一种概率性数据结构 通常用来测试一个元素是否在集合中 它的空间效率和时间效率都远远超过一 般 的 算 法 但存在一定的误识别率 即将不在集合中的元素判 断 为 在 集 合 中 布隆过滤器用一个长度为 的 位 数 组 来表 示 一 个 集 合 初始时数组的所有元素都为 布 隆 过 滤 器通 过 个哈希函数将一个元素映射到数组中的 个 位 置 添加 元 素 时将 这 个 位 置 都 置 为 检查一个元素是否在集合 中 时检 查 这 个位置是否全部为 若 全 部 为 则 说 明元素很有可能在集合中否则元素一定不在集合中 布 隆 过滤器中插入和检测运算的时间复杂度都是 在 允 许 一定误算率的情况下 布隆过滤器具有很高的时间和空间效率此 外布隆表达式还可以通过 位 操 作 和 位 操 作 快 速地实现集合的并和交本文给出的方案实质上是由测试工作者求出对象每个属性满足的所有约束的集合再由匹配工作者求出这些集合的并集并与已注册的订阅进行匹配 一个订阅也可以看成一个断 言 的 集 合 匹配一个对象和一个订阅 即是检查一个订阅的断言集合是否包含于对象满足的断言集合 布 隆 过 滤 器 可 以快速地对集合进行运算因此本算法使用布隆过滤器来表示集 合即每个测试功能块产生的结果是一个表示某属性满足所有约束集合的布隆过滤器每个订阅的条件看成断言的集合 用 一 个 布 隆 过 滤 器来 表 示每个断言对应一个只包含一个元素集合的布隆过滤器布隆过滤器的问题是有一定的误判率但 我 们 认 为 这 些误判不会造成严重的影响 因 为大规模存储系统中存在少量分发错误是允许的订 阅者在接受时进行简单判断即可判断数据匹配订阅的过程是判断一个集合是否是另一个 集 合 的 子 集 而不只是一个元素是否属于一个集合这 大 大降低了误判效率 同时考虑到实际应用中不同的订阅通常针对 不 同 的 数 据 不同的对象也拥有不同的属性订 阅 的 集 合 之间以及不同对象满足断言的集合之间都相对分离发 生 误 判的概率微乎其微如果不能容忍任何的误判 可 以 在 计 算 断 言 位 置 时 检测 并 避 免 冲 突 计算断言位置的运算实际上只在新的断言注册到系统中时做一次 其代价是能够容忍的数 字 类 型 测 试对于数字类型的属性 下面给出一个快速测试算法对于 每 个 属 性 算 法 维 护 一 个 行 列 的 表其 中 是这个属性相关的所有约束的总数 表 的 第 列 记 录 所 有 约 束中 出 现 过 的 值 第 列 到 第 列各对应一种运算 这 样 表 中第 列 到 第 列中的每一个位置都对应一个约束 我 们 给 每一个位置填充一个布隆过滤器 设 表 示 表 格 中 运算对应的列中的第 个 元 素 则 位 置 对 应 一 个 约 束其 中 为 表 格 中 第 列 第 行 的 值 令 表 示位 置 的 值 表 示 位 置 所 表 示 的 约 束 对 应的布 隆 过 滤 器 如果约束不存在则对应一个全 的 布 隆 过 滤器 则表格中的值满足如下关系即 为 一 个 表 示 所 有 对应约束满足情况下满 足 的 包 含 操作约束集合的布隆过滤器图 数字测试样例及数据结构以 图 为 例如 果 要 检 查 值 满 足 哪 些 约 束 首 先 通 过二 分 法 找 到 的 位 置即 和 之 间位置的布隆过滤器表示的集合包含所有 操 作 相 关 约 束 中数 值 可 以 满 足 的 约 束 同 时 位 置 的 布 隆 过滤器表示的集合包含数值 满 足 的 所 有 操 作 相 关 的 约束 在对这两个值进行 位 操 作 之 后 便可以得到表示数值 满足的所有约束集合的布隆过滤器 如 图 中可以获得布隆过滤器这个布隆过滤器表示集合即 数 值 满足所有约束的集合将不同的运算集中在一张表中可以获得更好的时间和空间 效 率使单次查找过程的时间复杂度是 假 设 对于 某 个 属 性 其 种运算对应的约束数量分别为 则有若分别组织成表 则 所 需 查 找 次 数 为大 于 另 一 方 面 对拥有相同数值不同 操 作 的 约 束 也要多存储几次数值字符串类型测试定义在字 符 串 上 的 和 种 操 作 也 可 以 同时进行测试 对于每一个 属 性 算法维护一棵三叉树约束中出现的每个字符串以 结尾存储在三叉树中 包 含 字符的节点称为 节 点 树 中的每个节点包含 部 分 信 息当前节点表示的字符 个 布 隆过 滤 器 以 及 棵 子 树 从 树 根 到 某 个 节点的路径可以表示一 个 字 符 串 到 某 个 非 节点的路径可以表示一个字符串的前缀 若某个节点表示的字符串为 对 非 节 点其 布 隆 过滤器 表 示 约 束 而 对 节 点其布隆过滤器包含约束和 所 有 的 其 中 在 集 合 中测 试 时算 法 首 先 生 成 一 个 全 布 隆 过 滤 器 在 搜 索 过程 中搜索路径上每一个匹配的节点中的布隆过滤器都被更新 到 结 果 中 使 用 操 作 如 图 全 布隆过滤器被省略所 示如 果 搜 索 字 符 串 将会得到布隆过滤器即 集 合图 字符串测试样例及数据结构该字符串测试算法的速度是 其 中 是 树的 高 度 由 于 树相对固定且在建树时就已获得全部信息因此可以使用二分法等方法创建最优树以提高算法效率订 阅 匹 配对所有属性进行测试之后将产生一系列的布隆过滤器对这些布隆过滤器进行集合的并操作 按 位 可 以 得 到 一个新的布隆过滤器 该布隆过滤器表示的集合包含该对象满足的 所 有 断 言 一个订阅是其中所有断言的集合 要 计 算 一个对象是否满足一个订阅的全部条件 只需要计算订阅对应的断言集合是否是对象满足所有断言集合的子集 设 订 阅 的布 隆 过 滤 器 为 算法生成的布隆过滤器为 匹 配 结 果 为则 有其 中 和 是 按 位 取 非 按位与和异或操作若 结 果 为 则 匹 配 失 败 反之则匹配成功获得了一个表示对象满足所有断言集合的布隆过滤器之后匹配功能块将该布隆过滤器和所有订阅的布隆过滤器进行 匹 配 找出匹配的订阅并推送对象 给 其 目 标 地 址在 匹 配 订 阅 时 本文设计不使用 提 出 的或 而是直接进行逐条匹配 因 为在实际应用场景中 被匹配的订阅数量经常很多例 如某一传感器数据被多方应用 如果将所有订阅组织成或 需 要 在 树 中 往 复 遍 历 增加了算法和实现的复杂度尽管要进行匹配的订阅数量较多 但 计 算 只 是 基 本 的位 操 作 的 组 合 实际计算速度很快值 得 注 意 的 是 匹配过程中几乎全部运算都是简单的位运算算法代码过程中不涉及分支 接下来的研究工作中我们 考 虑 使 用 甚至设计专用硬件直接进行并行计算以 为 例对于大量数据的相同运算 可 以 获 得远 高 于 的 运 算 速 度 这里的匹配算法便是这种情况考虑到显存和内存的数据交换是性能瓶颈 可以将相对固定的众多订阅的布隆过滤器存放在显存中 以减少显存和内存之间的数据传送量 每次将新获得的布隆过滤器传入显存并行地与各个订阅的布隆过滤器进行比较 并输出匹配成功的订 阅 索 引结 束 语 本文提出了一种数据分发网络及相应算法 方案借用大规模存储系统节点网络构建数据分发网络 通 过 收集存储系统中众节点上有限的计算资源 为应用于物联网场景的存储系统引入了基于内容的数据分发机制使 得 各 种 传感数据能够更有效地聚合和分发 受系统虚拟化技术和云计算 的 启 发本文引入工作者和功能块的设计通 过 工 作 者 和 功能块的动态装配组合实现了计算节点的负载自动调节和计算资源在不同任务间的自动配置 最 后本 文 还 给 出 了 基 于 布隆表达式的一种快速约束测试和匹配算法参 考 文 献文献 中所提方法由于只重视链路的拥塞且 没 有 依 据时 间 与 拓 扑 的 动 态 变 化 因 此 如 图 图 所 示当 网 络 流 量较 少 时普通优化由于只重视拥塞控制因此在负载均衡上的性能优于本算法 但当网络流量逐渐增加时 本 算 法 也 逐 渐 重视 拥 塞双方负载均衡能力相当 且本算法的传输代价一直小于 普 通 算 法 因此本算法在处理多拓扑动态多目标负载均衡上 有 一 定 优 势图 链路利用率方差图 各时段传输代价
　　结 束 语
　　本文根据网络流量动态变化的特点 提 出 一 种子层链路权值优化算法 该算法根据时段不同设置相应的业务量矩阵 且因为网络流量不同 对拥塞和传输代价的偏 重 程 度 也 不 同 因此该算法为不同的时段设置了不同的拥塞传 输 代 价 权 重 因 子 使 得 网 络 子层可以在不同时段拥有一套适应该时段业务需求的链路权值 为 了 避 免 一 般 优化算法容易出现陷入局部最优的问题 该算法使用小生境粒子群算法进行寻优 以保证搜索的范围能够覆盖全局 实 验证 明该算法能够实现子层中流量的负载均衡 在 后 续 研 究中将对拥塞造成的代价函数进行优化使其更加适应网络环境
    参 考 文 献于 涛陈 山 枝李 昕等一种通过优化链路权值来增强网络生存性 的 方 案 高 技 术 通 讯吴 静郭 成 城晏 蒲 柳等基于动态流量矩阵的网络链路权值调整 方 法 华中科技大学学报袁 荣 坤孟 相 如李 明 迅等基于粒子群权值优化的网络可生存性 增 强 方 法 计 算 机 应 用黄 赫王 晟多 拓 扑 路 由 实 现 网络区分服务的优化算法计算机应用研究徐 明 伟杨 芫李 琦域内自愈路由研究综述 电 子 学 报