智能家居网络建模与路由算法仿真研究.pdf

收稿日期 倡基金项目 年度广东省自然科学基金 广州市 科技计划 年科学研究专项 作者简介 杨伟钧 男 广东梅州 博士生 讲师 主要研究方向为 物联网技术 自动控制技术 智能家居网络建模与路由算法仿真研究 倡 杨伟钧 广东工业大学自动化学院 广州 广州城市职业学院机电工程系 广州 摘 要 以智能家居系统中通信节点的组网为研究对象 分析了其通信节点组网的特点 通过建立相应的模型 提出一种近 似最优化的路由算法 离线计算节点间数据传输的路径 以提高网络的服务质量 论文设计的模型与路由算法方法在 上进行仿真 并在静态网络 上针对不同参数进行测试验证 仿真结果显示 该算法可以在 内找到近似最优路 径 适合智能家居系统的应用 关键词 智能家居 网络建模 最优化 近似算法 中图分类号 文献标识码 编码 Abstract Key words 引言 过去的十几年来 随着人们生活水平的提高 智能家居得 到了快速的发展 涌现出一批如华为 小米 海尔等优秀的 智能家居研发企业 而传统的家电制造企业包括美的 格力等 厂商也纷纷在转型升级背景下率先向智能家居的研发与制造 转型 智能家居中存在有线无线等多种复杂的通信方式 其 网络建模 节点间通信与服务质量的保证 正引起广大学者的 广泛关注与研究 高效的点对点通信保证 例如传感器 节点信息收发等 有效的点对多点通信应用 例如网页广 播 视频点播 视频会议 等 已经在互联网上得到极速 的发展 与传统的计算机网络建模与路由算法不同 智能家居中 节点之间既有有高速传输的有线通信又有方便布局的无线通 信 既有点对点的单播传输也有点对多点的多播传输 对其 网络模型研究 并针对不同业务提出高效的路由算法具有重 要的现实意义 其中一种有效的解决方案是 在满足不同服 务质量 的要求下 如时延 代价 带宽 丢包率等 寻找 最小代价的最优路径或最优多播路由树 在多种 约束条 件下 寻找最优路径问题被称为 问题 在多 约束条 件下寻找最优多播树 通常称为 树问题 这两者都已 被证明是一 完全问题 最近有很多学者在研究多约束条 件下的最优化确定性算法和启发式近似算法 并取得了重要 的突破 其中 确定性算法 如遗传算法 蚁群算法等在不 考虑时间状况下 能最终找到最优解 但其时间复杂度随网络 节点的数目呈现指数级增长 要求运算处理速度极快 并不适 应于网络单播或多播应用 而启发式算法不一定能找到最优 路径或 树 但他们能在较短的 合理时间内找到接近 最优解 因此在网络的应用中更具有实际价值和意义 智能家居的网络建模 定义 智能家居中的每个通信设备为网络中的一个节 点 相邻节点之间的通信方式是有线或无线的 无向的 给定 一个无向网络图 是图 的节点集合 是节 点数目 是图 的边集合 是边的数目或者链路数 边 的代价 费用 为 c ej 单播的源和目的节点分别是 和 多 播目的节点 dj的集合 D di D q 畅 单播路由算法 定义 单播路径最优算法为 在图 中寻找从源节点 到目的节点 的一条可行路径 记为 P VP EP 其中 s t VP VP彻V EP彻E 并使得路径 的代价 费用 C P 最小 即为 C P ej EP c ej 如果网络中每条边只有一个参数 如延时 带宽 丢包率 等其中一个 则已有的 算法能在最短的时间内找到 最优路径 如每条边的参数大于或等于 时 这一问题已被 证明是 完全问题 畅 多播 树 路由算法 定义 多播 生成树算法为 在图 中寻找覆盖 中所有节点的生成树 记为 T VT ET 其中 D彻VT彻V ET彻 E 并使得整棵树 的代价 费用 C T 最小 即 C T ej ETc ej 在 生成树 Tq上 以外的节点集合 D D 彻VT且 D D 除 称为非多播节点或 节点 任一节多播目 的节点 di i q 到生成树 Ti 的代价费用为 c di Ti min c di vk di D VTi vk VTi 对应的最短路径为 PATH di Ti 在集合 情况下 生成树问题即为求图 的最小生成树 算法在时间复杂度为 能找到最 优解 在 时 即为求两点之间最短路径 等算 法可以在多项式时间内得到最优解 除了以上两种情况以 外 这一问题被证明是 完全问题 智能家居在实际设计中因布线问题 施工要求以及无线 智能家居网络建模与路由算法仿真研究 杨伟钧 传感网应用的普及等 无线通信方式在整个网络中所占比较 越来越大 以上对智能家居网络单播和多播方式的建模 针 对无线通信具有时变 易受干扰的特点 离线计算路由路径需 要在尽量短的时间内完成 普遍的智能算法耗时较长 难于 胜任 一种路由近似算法 针对无线网络通信特点 文章提出了一种路由近似算法 在定义 中给出了针对智能家居网络的模型 节点之间连接的 边具有不同的代价参数 延时 跳数和丢包率等 这些参数之 间的标量单位是不统一的 要进行路由算法路径的计算 必须 要作出相应的变化 对此提出了归一化的近似处理算法如下 c ej c ej Li 如公式 所示 公式中的 Li为相应边的代价参数对应 的约束 整个公式代表了对每一条边都作归一化的处理 运算 后整个网络的模型参数具有一样的标量 c ej 榾c ej n 如公式 所示 公式中的 为根据实际情况调整的系 数 为整个网络的节点数目 其代表对每条边近似处理后 的权值 并作一定数量的缩放 经过以上对网络模型处理后 所有参数都是整形变量 作 为智能家居中运算能力较弱的节点 其处理运算速度将有极 大的提高 而最终离线获取的路由路径是一种近似路径 网络仿真研究 针对智能家居系统提出的网络模型及其近似路由算法 为了研究其性能情况 选择具有固定参数的静态无向网络 作为仿真对象 如图 所示 网络有 个节点和 条边 每条边的链接有三个参数 延时 代价和丢 包率 运行算法是在性能为 畅 内存为 的电脑上运行的 该网络的各项参数可以在以 下 网 络 地 址 中 找 到 图 网络拓扑结构 图 单播路由算法仿真 如图 所示 在静态网络 上进行单播路由算 法仿真研究 图中蓝色的节点代表路由节点 节点间黑色的连 线代表路径费用 延时 代价或丢包率 设置源节点序号为 图中为绿色圈代表的节点 目的节点序号为 图中为绿 色星号代表的节点 运行本文研究提出的近似算法 找到源 到目的近似最优路径 图中为红色代表的路径 图 多播路由算法仿真 如图 所示 在静态网络 上进行多播路由算 法仿真研究 设置源节点序号为 图中为绿色圈代表的节 点 目的节点序号为 图中为绿色星号代表的节点 运行本文研究提出的近似算法 找到源到目的近似最优路径 图中为红色代表的多播路径 根据仿真所采用的计算机设备性能 通过图 和图 在静 态网络上的路由算法研究显示 算法找到近似最优路径时间控 制在 内 因此 针对无线网络时变性 不确定性的特点 在 离线状态下 该算法能在合理的时间内找出合适的路径 结束语 论文针对智能家居中各种有线 无线设备进