一种无线传感器网络MAC协议优化算法_刘云璐.doc

《一种无线传感器网络MAC协议优化算法_刘云璐.doc》由会员分享，可在线阅读，更多相关《一种无线传感器网络MAC协议优化算法_刘云璐.doc（11页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、 ） ） ） ） 第 卷 第 期 年 月 计 算 机 学 报 一种无线传感器网 络 协议 优化算 法 刘云璐 蒲菊华 方维维 熊 璋 ） （ 北 京 航 空 航 天 大 学 计 算 机 科 学 与 工 程 学 院 北 京 ） ） （ 北 京 交 通 大 学 计 算 机 与 信 息 技 术 学 院 北 京 ） 摘 要 在 无线传感器网络 中 ， 各 节 点 采 集 的 信 息 以 多 跳 的 方 式 传 送 到 汇 聚 点 从 各 节 点 到 汇 聚 点 形 成 一 棵 以 汇 聚 点 为 根 的 传 输 树 文 中 在 对 无 线 传 感 器 网 络 传 输 特 点 分 析 的 基 础 上 ，

2、 剖 析 了 基 于 （ 载 波 多 路 监 听 冲 突 避 免 ） 的 协 议 在 树 状 结 构 无线传感器 网 络 中 的 弊 端 ， 提 出 了 一 种 基 于 的 协 议 优 化 算 法 算 法 基 于 节 点 在 传 输 树 中 的 位 置 信 息 调 整 其 信 道 接 入 分 配 ， 将 采 用 的 各 节 点 均 等 竞 争 信 道 的 方 法 优 化 为 各 节 点 依 据 在 传 输 树 中 的 位 置 情 况 竞 争 信 道 的 方 式 ， 这 一 优 化 提 高 了 节 点 公 平 性 ， 使 信 道 接 入 分 配 与 树 状 结 构 的无线传感器网络传 输 特 点

3、 相 契 合 ， 解 决 了 基 于 的 协 议 与 树 状 结 构 无线传感器网 络 不 匹 配 的 问 题 ， 从 而 减 少 了 信 道 资 源 浪 费 ， 提 高 了 网 络 传 输 效 率 ， 降 低 了 能 耗 实 验 结 果 表 明 该 算 法 在 网 络 丢 包 率 、 吞 吐 量 和 能 耗 方 面 的 性 能 均 有 较 大 改 进 关 键 词 物 联 网 ； 无线传感器网 络 ； 传 输 树 ； 协 议 中 图 法 分 类 号 号 ： ） ） ） ） ） （ ， ， ） ） （ ， ， ） （ ） ， ， ， （ ） ， ， ， ， ， ； ； ； 收 稿 日 期 ： ；

4、 最 终 修 改 稿 收 到 日 期 ： 本课题得到国 家 自 然 科 学 基 金 （ ） 、 国 家 教 育 部 博 士 点 专 项 基 金 （ ） 、 国 家 “ 八 六 三 ” 高 技 术 研 究 发 展 计 划 项 目 基 金 （ ） 资 助 刘 云 璐 ， 女 ， 年 生 ， 博 士 研 究 生 ， 主 要 研 究 方 向 为 无 线 网 络 及 无线传感器网 络 ： 蒲 菊 华 ， 女 ， 年 生 ， 博 士 ， 副 教 授 ， 主 要 研 究 方 向 为 无 线 传 感 器 网 络 、 容 迟 网 络 方 维 维 ， 男 ， 年 生 ， 博 士 ， 主 要 研 究 方 向 为 无

5、 线 网 络 、 无线传感器网 络 、 嵌 入 式 系 统 熊 璋 ， 男 ， 年 生 ， 教 授 ， 博 士 生 导 师 ， 主 要 研 究 领 域 为 无线传感器网 络 、 分 布 式 系 统 、 多 媒 体 处 理 及 网 络 工 程 计 算 机 学 报 年 引 言 无 线 传 感 器 网 络 是 物 联 网 的 支 撑 技 术 之 一 ， 具 有广阔的应用前景和许多不同于传统无线网络的特 点 典型的 无 线 传 感 器 网 络 采 用 汇 聚 点 （ ） 收 集网络中的数 据 ， 各 节 点 采 集 的 数 据 通 过 其 它 节 点 转发以多跳的 方 式 最 终 传 输 到 汇 聚

6、点 ， 整 个 网 络 的 信息向汇聚点传输的过程形成一棵以汇聚点为根的 传输树 ， 这种网 络 模 式 是 传 感 器 网 络 最 主 要 的 信 息 传 输模式之 一 在传输树中 ， 上层节点承 载 的 传 送 任务不仅包括 节 点 本 身 的 数 据 采 集 ， 还 包 括 下 层 节 点的数 据 转 发 因 此 ， 网 络 负 载 会 在 上 层 节 点 处 累 积 一般地基 于 的 无 线 协 议 为 网 络中每个节点 提 供 同 等 的 信 道 访 问 机 会 ， 这 种 策 略 比较适用于传统 的 网 络 在 传 统 的 网络中 ， 每个节点都可以是信息传输的目标节点 ， 网 络

7、负载的分布 没 有 一 定 的 规 律 ， 平 等 的 信 道 访 问 机 会对各节点是 公 平 适 用 的 但 是 在 树 状 传 感 器 网 络 中信息传输有 固 定 的 目 标 汇 聚 点 ， 上 层 节 点 负 载 较 重 ， 同等的信道访问机会平均到每条信息 ， 则每条 信 息在上层节点处的发送概率将明显低于其在下层节 点处的发送概率 并 且 当 网 络 在 一 段 时 间 内 持 续 繁 忙时 ， 上层节点处的信息由于发送概率低而累积 ， 下 层节点的信息持续传送到上层节点处并逐渐在上层 节 点处形成拥塞 ， 甚 至 被 丢 弃 显 然 ， 用 于 发 送 这 些 最终被丢弃信息

8、的 资 源 （ 包 括 信 道 、 能 量 等 ） 被 浪 费 了 这一问题 是 由 基 于 的 无 线 协 议和树状传输结构的传感器网络的传输 特点不相符 造成的 本 文 针 对 上 述 问 题 ， 基 于 树 状 传 输 结 构 的 无 线 传感器网络 应 用 ， 提 出 一 种 基 于 的 无 线 协议 的 优 化 算 法 和 信 道 抢 占 解 决 方 案 本 文 第 节给出相 关 领 域 的 研 究 现 状 ， 介 绍 本 文 工 作 的 特点和贡献 ； 第 节 描 述 本 文 工 作 采 用 的 网 络 模 型 和相关定义 ； 第 节 讨 论 树 状 传 感 器 网 络 的 传 输

9、 特 点 ， 并给出算法的数学推导和证明 ； 第 节阐述本 文 算法的流程 ； 第 节给出算法在丢包率 、 吞吐量和 能 耗方面的性能实验验证与分析 ； 最后是本 文 的结论 相关工作 近 年 来 ， 各 国 学 者 针 对 传 感 器 网 络 的 高 效 传 输 问题 ， 做 了 很 多 研 究 ， 包 括 从 层 、 路 由 层 到 传 输层的优化改进 ， 有效地降低了网络丢包率和能耗 ， 增 强 了 网 络 的 可 靠 性 本 文 着 重 分 析 层 的 解 决 方 案 传 感 器 网 络 协 议 根 据 信 道 分 配 方 式 可以分为三类 ： 基 于 的协 议 、 调度协议 和 混

10、合 协 议 基 于 的 协 议 不 存 在 网 络同步问题 ， 扩 展 性 好 调 度 协 议 能 有 效 利 用 资 源 ， 但一般需要中 央 节 点 调 度 ， 在 复 杂 网 络 情 况 下 部 署 有效的调度协 议 被 证 明 是 问 题 ， 并 且 以 协议族 为 代 表 的 调 度 协 议 通 常 有 时 钟 同 步 要求 ， 时钟同步需 要节点频繁交换控制信息 ， 这将 大 大增加网络能耗 因此 ， 由于传感 器 节点及网络布 设 的局限性 ， 以 协 议 族 为 代 表 的 调 度 协 议 较 少 在 传 感 器 网 络 中 直 接 采 用 混 合 协 议 结 合 了 上 述两

11、种协 议 的 优 点 ， 但 通 常 比 较 复 杂 ， 难 以 配 置 基 于 的 协 议 是 传 感 器 网 络 中 比 较 常 用 的一种 方 式 ， 研 究 也 最 为 活 跃 ， 下 面 我 们 对 该 领 域 的代表性成果加以 分 析 一 般 基 于 的 传 感 器网 络 协议是在采 用 （ 分布协调功 能 ） 的 的基础上进行的优化和改进 ， 其 信 道竞争的核心思想是 ： 当节点发送数据时 ， 先监听 信 道是否繁忙 如果繁忙 ， 节点等待一定时间后再尝 试 发送 ； 如果再次发生冲突 ， 节点按一定的策略重发 信 息， 直 到 信 息 发 送 成 功 或 放 弃 （ ） 是第

12、一个完全针 对 传 感 器 网 络 设 计 的 基 于 的 协议 ， 它的重要 贡 献 是 引 入 了 节点休眠机制 ， 即节点定期休眠 ， 相邻节点休眠调 度 周期同步 是 在 基 础 上 的 改 进 ， 对 节点休眠的策 略 进 行 了 适 度 的 调 整 ， 例 如 根 据 网 络 状况动 态 调 整 节 点 休 眠 时 间 以 提 高 协 议 效 率 、 、 和 协 议 在 协议的基 础 上 ， 采 用 前 导 序 列 技 术 提 高 了 休 眠 唤 醒 决 策 的 精 度 ， 无 需 节 点 同 步 协 议 根 据 网 络 流 量 自 适 应 地 调 整 休 眠 调 度 协 议 针对

13、 事 件 驱 动 的 传 感 器 网 络 应 用 ， 当 多 个 节 点 同 时检测到同一个事件 ， 只保证 其中的部分节点发 送 检测信 息 ， 一 定 程 度 上 降 低 了 网 络 冲 突 的 概 率 ， 但 协 议基于 严格的时钟同步 协议提出根据网 络 传输 的树状结构 ， 调整休 眠 调 度 策 略 ， 使 得 下 层 节 点 的发送时间 与 上 层 节 点 的 接 收 时 间 相 对 应 所 述 的 传 感 器 网 络 协 议 的 信 道 接 入 机 制 均 沿 用 协 议 的 机 制 ， 本 文 称 它 们 属 于 协 议 族 它 们 主 要 从 休 眠 调 度 策 略 方 面

14、 对 协 议 进 行 优 化 改 进 ， 没 有 针 对 本 文 所 述 的树状传输结构网络所存在的信道分配问题提出解 期 刘 云 璐 等 ： 一种无线传感器网 络 协 议 优 化 算 法 决方案 调度协 议 以 协 议 族 为 代 表 ， 下 面 介 绍调度协议相关研究成果 协 议 提 供 了 根据 流 量 预 先 分 配 时 间 槽 的 无 冲 突 通 信 ， 它 属 于 协议族 ， 时间同步及时 间 槽 分 配 调 度 的 资 源 耗费是这类算法应用的瓶颈 ， 且这类算法复杂 、 实 现 难 度 大 本 文 算 法 属 于 基 于 的 协 议 ， 但 根据网络结构调整了信道 接 入 概

15、率 参 数 ， 与 协议族相比 ， 本 文 算 法 由 于 没 有 涉 及 到 时 间 槽 调 度 算法 ， 总体上 规 避 了 协 议 族 的 局 限 （ 如 时 钟 同 步 ） 混 合 协 议 是 基 于 的 协 议 与 调 度 协议的结合 ， 与本文算法解决的问题不同 本文算 法 的目标是 解 决 传 感 器 网 络 树 状 传 输 结 构 引 入 的 问 题 ， 即在传输树中 ， 由于信息在上层节点处的发送 概 率低于在下层节点处的发送概率而造成的传输效率 低 下及信 道 和 能 量 资 源 浪 费 等 问 题 以 为 代表的混合协议解决的 是 层 单 跳 信 息 发 送 冲 突 的

16、问 题 ， 并 没 有 考 虑 传 感 器 网 络 结 构 引 入 的 传 输 问 题 在 全 网 采 用 协 议 ， 在汇 聚 点 周 围 的 漏 斗 区 域 按 需 采 用 协 议 ， 虽然 将 协 议 仅 限 制 在 汇 聚 点 附 近 ， 并 由 汇聚点 实 施 时 间 槽 调 度 ， 避 免 了 协 议 时 间 槽调度算法在 传 感 节 点 难 以 部 署 的 问 题 ， 但 随 网 络 规模的增大 ， 漏斗区范围扩大 ， 时间槽调度的复杂 度 和向各 节 点 周 期 性 部 署 的 耗 费 都 随 之 大 大 增 加 ， 协议的时钟同步问题 也 并 未 避 免 时 钟 同 步 信息

17、的交互耗费对能耗要求极高的传感器网络 是不 容小视 的 负 担 ， 也 是 本 文 算 法 不 考 虑 类 协 议的重要原因之一 在一些 涉 及 层 优 化 的 算 法 中 ， 采 用 了 优 先 级 设 置 方 案 ， 根 据 设 计 目 标 ， 在 层 为 信 息 设 置 不 同 的 优 先 级 文 献 通 过 调 整 层延 迟 等 待 窗 口 ， 给 予 拥 塞 节 点 更 多 的 信 道 占有机会 ， 以帮助缓解拥塞 文 献 针对无固定 汇 聚 点 的 无 线 网 络 应 用 ， 给 予 数 据 流 不 同 的 层 优先级 文 献 在网格结构的网络 中 ， 给予等候 信 道时间较长的

18、节 点 更 多 的 信 道 抢 占 几 率 这 些 算 法 分别是根据不 同 的 网 络 传 输 结 构 需 要 提 出 的 层优化算法 ， 但极少涉及本文所述的问题 本文针 对 树 状 结 构 的 传 感 器 网 络 应 用 ， 优 化 基 于 的无 线 协 议 与 以 上 所 述 方 法 不 同 ， 本 文 算 法 采用设 置 层 最 小 竞 争 窗 口 的 方 法 来 实 现 信 道 的非均等分配 ， 并 非 设 置 信 息 或 节 点 的 优 先 级 ， 即 不 干 预 网 络 运 行 的 动 态 参 数 ， 节 点 或 信 息 没 有 优 先 等 级 算法优化 了 在 信 息 碰 撞

19、 情 况 下 的 信 道 分 配 方 式 ， 因此具有较 高 的 自 适 应 性 ： 在 网 络 轻 载 情 况 下 ， 由 于 不 存 在 信 息 拥 塞 和 不 公 平 问 题 ， 算 法 运 行 与 协议相近 ； 在 网 络 重 载 情 况 下 ， 算 法 通 过 调 整 层 最 小 竞 争 窗 口 给 予 节 点 不 同 的 信 道 接 入 概 率 ， 以解决 前 面所述 的 协议族与树状 传 感器网络应用不匹配的问题 网络模型 本文描述的网络模型针对上行传输的树状传感 器网络 应 用 ， 如图 所示 我们对网络 模 型给出以 下 假设 ： （ ） 网络中 节 点 静 止 ， 在 初

20、始 网 络 部 署 后 ， 传 感 器节点和汇聚点静止 ； （ ） 在节点 传 输 半 径 范 围 内 的 点 ， 是 可 连 通 点 ， 整个网络为连 通 网 络 ， 即 从 汇 聚 点 可 以 通 过 多 跳 的 方式与任一节点通信 ； （ ） 节点能量主要消耗 在 通信中 ， 根据文 献 中 的测量 ， 设定发 送 信 息 消 耗 的 能 量 为 接 收 信 息 消 耗 的能量的两倍 图 网 络 图 在检测区域中 ， 给 定 个传感 器 节 点 和 汇 聚 点 构 成 连 通 网 络 ， 用 无 向 图 （ ， ） 表 示 ， 表 示 传感器节点的集合 ， 是节点间双向链路 集 合 以

21、汇 聚点为根节点在 中 可 以 生 成 一 棵 层 的 传 输 树 如 图 所 示 ， 为 一 棵 以 汇 聚 点 为 根 的 上 行 传 输树 在 以上所述的网络 模 型 中 ， 传 输 树 中 的 任 一 非叶节点既要 发 送 自 己 检 测 的 信 息 ， 又 承 担 了 子 节 点数据的 转 发 工 作 在 传 输 树 中 ， 距 汇 聚 点 越 近 且子节点越多的节点 ， 承载的发送任务就相应越重 我们称这种情况为无线传感器网络的 非均衡传输特 计 算 机 学 报 年 点 ， 描述如下 ： 在 上行传输的树状无线传感器网 络 中 ， 非叶节 点 的负载量不少于它的所有子节点的负载量的

22、总和 对于任一节 点 ： （ ） 若 在 中距汇聚点的跳数 为 ， 则 在 中 的 层次 为 或 （ ） ； 所 有 层 次 为 或 （ ） 的 节 点 集 合 为 或 （ ） ； （ ） 子节点 集 合 为 ； 层 或 （ ） 的 子 节 点 集 合 （ 层 中 所 有 节 点 的 子 节 点 组 成 的 集 合 ） 为 或 （ ） ， ； 层 或 （ ） 的 平 均 子 节 点 数 （ 层 中 所 有 节 点 子节点数的平均 值 ） 为 珡 或 珡 （ ） ； 网 络 总 平 均 子 节 问题描述及理论分析 信道分 配 基 于 的 无 线 网 络 协 议 （ 以 为例 ， 如 图 所 示

23、） ， 其信道分配 的 基本原理是 ： 节点在发送信息前监听信道 ， 如果信 道 繁忙 ， 则随机等待一个时间段 ， 等待的时间段大小 是 从 到竞争窗 口 大 小 之 间 的 随 机 数 每 当 网 络 空 闲 时间 达 到 （ ） 时 间段长度时 ， 延迟计数器 减 ， 直到延迟计数器为 ， 节点开始发送数据 ， 当发送冲突时 ， 竞争窗口按一 定 点数 为 珡 ； 的规律增加 ， 信息重新等待发送 ， 直到竞争窗口大 小 烄 （ 珡 （ ） ） ， 珡 （ ） 达到最大竞争 窗 口 值 网 络 中 节 点 的 竞 争 窗 口 初 始 （ ） 子 节 点系数 为 烅 ， 烆 ， 珡 （ ）

24、 值取统一设置 的 最 小 竞 争 窗 口 值 ， 保 证 了 节 点 拥 有 即子节点数与层 平 均 子 节 点 数 的 比 值 ， 当 为 叶 子 节点时 ， 珡 （ ） ， 系数为 均 等 的 信 道 抢 占 机 会 ， 这 是 一 种 公 平 的 信 道 竞 争 机制 图 信 道 分 配 机 制 在无 线 网 络 中 ， 由 于 目 标 节 点 分 散 ， 网 络负载是无规 律 分 布 的 ， 因 此 这 种 公 平 的 信 道 竞 争 机制能够得到 比 较 好 的 效 果 本 文 所 述 的 无 线 传 感 器网络模型 ， 在传输 树 中 父 节 点 和 子 节 点 的 关 系 固定

25、 ， 并存在上节所述的非均衡传输特点 ， 即父节 点 的负载量不少 于 它 所 有 子 节 点 负 载 量 的 总 和 ， 当 信 道持续繁忙一 段 时 间 ， 由 于 父 节 点 只 能 和 子 节 点 以 相同的概率抢占信道 ， 导致信息在父节点处累积 ， 以 至于信息极易 由 于 缓 存 溢 出 而 被 丢 弃 子 节 点 成 功 抢占信道发送到父节点处的信息会进一步加重父节 点 负担和丢包率 ， 同 时 ， 子 节 点 的 这 种 无 效 发 送 ， 还 浪费了带宽和能量资源 因此 ， 均等信道抢占机制 并 不完全适用于 本 文 所 述 的 网 络 模 型 ， 应 给 予 父 节 点

26、相 对 于子节点更多的信道抢占 机 会 最小竞争窗口 的 大 小是决定信道抢占概率的一 个重要参 数 ， 本文着 重 探讨怎样针对所述网络模型为 中节点设置最小 竞 争 窗口值 ， 以合理分配信道使其 符合树状网络模型 的 传输特点 如 第 节 所述 ， 基 于 的传感 器 网 络 协 议 众 多 ， 但 信 道 接 入 方 法 主 要 是 基 于 协议 的 算 法 ， 因 此 本 文 算 法 基 于 协议 的 最小竞争窗口计算方 法 由 前 面 的 分 析 可 知 ， 对 在 树 状 结 构 的 无 线 传 感 器网络进 行 层传输控 制 的 核 心 是 分 配 给 父 节 点相对于子节 点

27、 更 多 的 信 道 抢 占 机 会 而 从 整 个 传 输 树 来看 ， 越 上 层 的 节 点 负 载 越 重 ， 相 对 信 道 占 有率应该越高 在源负载均匀分布的情况下 ， 节点 的 总负载量取决 于 它 转 发 的 信 息 量 ， 节 点 的 转 发 信 息 量与节点在 中的层次和 子 节 点 的 数 量 密 切 相 关 设每个节点源信 息 量 为 单 位 ， 如 图 所 示 的 传 输 树结构负载分 布 显 示 ： 越 靠 近 汇 聚 点 且 子 节 点 数 量 越多 ， 其负载 量 就 越 大 在 源 负 载 不 均 衡 的 情 况 下 ， 仅考虑根据负载量来调整信道分配难以满足节点公 平性的要求 ： 按 负 载 量 调