用于传感器网络周期性数据收集的自协商分时MAC协议.doc

2008 年 11 月Journal on CommunicationsNovember 2008 第 29 卷第 11 期通 信 学 报Vol 29 No 11 用于传感器网络周期性数据收集的自协商分时 MAC 协议 曾益 胡波 刘顺佳 复旦大学 电子工程系 上海 200433 摘 要 针对传感器网络周期性数据收集的数据流特点 提出了基于自协商时隙分配机制的自协商分时 MAC 协 议 该时隙分配机制无需集中式处理 具有自适应 分布式 本地化等特点 仿真结果表明 本协议的有效数 据收集率及最大数据延时与增添 ACK 重传机制后的 TAG 协议相当 而能耗却仅为后者的 1 30 关键词 无线传感器网络 自协商 周期性数据收集 MAC 协议 分时 中图分类号 TP393 文献标识码 A 文章编号 1000 436X 2008 11 0031 09 Auto negotiation time division MAC protocol for periodical data gathering in sensor networks ZENG Yi HU Bo LIU Shun jia Department of Electronic Engineering Fudan University Shanghai 200433 China Abstract On the analysis of data flow characteristics in periodical data gathering applications in wireless sensor networks an auto negotiation time division MAC protocol based on auto negotiation slot allocation scheme was proposed The slot allocation is carried out in the adaptive distributed and localized manner The simulation shows that power consumption in our protocol has been decreased to the one thirty of that in TAG protocol with extended ACK re transmission scheme while delivery ratio and maximum data latency suffer no deterioration Key words wireless sensor networks auto negotiation periodical data gathering MAC protocol time division 1 引言 无线传感器网络 1 由大量具备无线传输能力 的传感器节点组成 一般分布在指定区域用于监 测外部环境 主要应用于环境监测 国防军事 医疗卫生及科学研究等领域 在这些应用中 传 感器节点首先将环境参数如温度 湿度等通过模 数转换器 ADC 变换为二进制数据 随后通过无 线射频模块将传感数据传输至指定接收节点 又 称为 sink 节点 Sink 节点可采用有线或无线方式 进一步与外部网络连接 通过该节点 远程用户 可进一步对传感器网络进行管理和控制 环境数 据采样有两种方式 周期性采样或事件触发采样 目前 大多数的应用场景 如水环境监测 医疗 看护系统等应用 都使用周期性采样的方式 周 期性数据采样要求对采样数据进行周期性的收集 如何有效地进行周期性采样数据的收集是决定传 感器网络性能的关键问题 本文所研究的正是如 何在周期性数据收集应用下设计高效的媒体访问 控制 MAC 协议 本文首先分析了周期性数据收集场景中数据 流的主要特点 随后提出了一种节点间自动协商 收稿日期 2008 06 11 修回日期 2008 10 20 基金项目 国家自然科学基金 60672047 上海市科学技术委员会基金资助项目 07dz15013 07dz12061 Foundation Items The National Natural Science Foundation of China 60672047 Science and Technology Commission of Shanghai Municipality 07dz15013 07dz12061 32 通 信 学 报第 29 卷 的分时 MAC 协议 该协议主要包括以下内容 1 根据节点到 sink 节点的跳数将网络分为不 同的层次 level 节点越靠近 sink 节点则对应 level 值越小 即层次越高 为降低数据传输延时 并使用数据汇聚技术 将上层节点的发送时间段 分配于下层节点的发送时间段之后 2 发送时间段由一定数目的发送子时隙组成 子时隙的长度恰好适合于发送单个最长数据包并 接收单个 ACK 消息包 3 提出双竞争窗机制 同层节点利用该机制 实现自动协商以获取所需数目的发送子时隙并保 证节点间无碰撞地发送 整个时隙分配无需集中 式处理 具有自适应 分布式 本地化等特点 最后 本文从数据收集延时 能耗及有效数 据传输率三方面对协议性能进行了评估 仿真结 果表明 相比其他协议而言 在满足最大单采样 周期时延的条件下 本协议具有较高的有效数据 收集率及极低的能耗 因此更加适用于周期性的 数据收集场景中 2 问题描述及数据流特点 2 1 问题描述 假定某传感器网络由 N 个传感器节点组成 其中节点 0 为 sink 节点 若节点 i i 1 N 1 每 隔 Tp时间对外部环境进行一次采样从而产生长度 为 Li的待发送采样数据 则数据收集协议的设计 目标为 保证所有节点的采样数据在指定时间内 传输至 sink 节点 即 sink 节点接收到的数据长度 应为 对某中间节点 j 而言 其除了发送自 1 1 N i i L 身的采样数据 Lj 外还需转发来自其他节点的待发 送数据 假定接收的数据总长度为 Ljr 则总的发 送数据长度应为 Lj Ljr 评价数据收集协议的性能参数主要有 总能 耗 有效数据收集率及最大数据时延 2 假定节点 i 消耗的能量为 Ei Li长度的采样数据的传递延时 为 Di 则总能耗 Ea可表示为 1 0 N ai i EE 最大数据时延 Dmax可表示为 2 max max 1 i DDiN 假定 sink 节点接收到的有效数据长度为 Lr 则有效数据收集率可表示为 3 1 r N i i L L 2 2 数据流特点 与一般的数据流不同 周期性数据收集场景 中的数据流具有以下特点 1 定向路由 由于所有采集数据均需传输至 sink 节点 因此节点的路由具有很强的方向性 节 点间的传输路径组成了一个以 sink 为根节点的树 状结构 又称为数据收集树 data gathering tree 2 其中 节点的下一跳路由必定从上一层节点中选 取 在传感器网络中 跨层设计已被公认为是提 高协议性能的有效方法 MAC 协议的设计应充分 利用定向路由这一特性 2 相对恒定的数据流量 由于数据采样的周 期性 每轮数据收集中节点的待发送数据长度恒 定 若节点拓扑结构及传输路由不变 每轮的数 据传输便具有很强的相似性 本文的自协商时隙 分配机制设计时便利用了该特性 3 累积的数据长度 数据收集树中的非叶 节点除发送自身采样数据外还需转发来自其他节 点的有效数据包 因此节点的待发送的数据量将 沿着数据采集树向 sink 节点方向逐步累积 传统 的网络协议需对每个缓存数据包进行单独转发 由此造成节点待发送数据包数目的指数型增长 一般来说单个节点的采样数据量较低 而发送大 量数目的短包会降低发送效率 影响网络的整体 性能 实际上 传感器网络是以数据为中心 data centric 因此可以利用数据汇聚 data aggregation 技术 3 将多个较短的数据包拼接为单 个更长的数据包 并不会造成数据损失 从而大 幅度降低待发送数据包数目 当然单个数据包也 不宜过长 否则可能由于丢包率的上升造成无法 正常接收 图 1 显示了同一个拓扑结构下使用及 未使用数据汇聚时 网络每轮所需发送的数据包 个数 其中单个节点产生的数据长度为 4 单个 数据包的最大有效传输长度为 16 即 4 个短数据 包可拼接为单个数据包传输 可以发现 使用数 据汇聚之后总数据包个数仅为未使用数据汇聚时 的 8 17 为最大程度上支持数据汇聚 上层节点 应在接收完所有下层节点的数据包并完成数据汇 第 11 期曾益等 用于传感器网络周期性数据收集的自协商分时 MAC 协议 33 聚后进入发送状态 图 1 使用及未使用数据汇聚时全网络每周期发送的数据包数目 3 相关工作介绍 迄今为止 国内外科研人员已提出不少传感 器网络专用的 MAC 协议 其中 大部分协议如 SMAC 4 TMAC 5 等设计时更注重协议的通用性 因而未能充分考虑周期性数据收集中数据流的上 述特点 在周期性数据收集应用中表现不佳 例 如 SMAC 协议会造成数据转发停顿 DFI 问题 2 导致较大的数据时延 Samuel Madden 于 2002 年在 TAG 3 协议中提 出利用定向路由的特点 将节点的接收时间及发 送时间按节点到 sink 节点的跳数进行交错排列 保证了下层节点的发送时间与上层节点的接收时 间重合 从而有效地减轻了 DFI 问题 降低了数 据传输延时 然而由于同一层节点在发送时间段 内使用 CSMA 机制竞争信道 而 CSMA 协议采用 随机二进制退避技术 因此节点在每轮数据收集 中的发送次序不确定 为接收所有来自子节点的 数据包 接收节点须在接收时间段内一直保持接 收状态 即使有效的数据接收时间很短 为使 用数据汇聚技术 TAG 协议还要求接收时间段足 够长以保证所有下层节点均能完成数据发送 在 实际使用中 为容忍一定程度的拓扑结构变化需 设定较长的接收时间段 如此则导致了长时间的 空闲监听 降低了能源利用率 Gang Lu 于 2004 年提出了 DMAC 2 协议 与 TAG 协议不同 DMAC 中单个发送时间段仅够完 成一次数据传输 当节点需发送多个数据包或多 个节点需发送数据包时必须使用 CSMA 机制竞争 信道 并同时利用数据预测 data prediction 或 More To Send 消息包分别隐性或显性地通知链路 上所有上层节点在 4 个时间段后重新进入接收状 态 相比 TAG 协议而言 DMAC 协议能够根据数 据流量自适应调整节点的接收时间段的个数 从 而降低了空闲监听时间 但在周期性数据收集中 节点每轮至少需发送一个数据包 由于数据包的 累积特性 中间节点需发送更多的数据包 在此 情况下 一旦数据包丢失或发生碰撞 DMAC 所 使用的上述两个机制便会失效并导致能耗增加甚 至数据转发停顿 因此协议性能依然有待提高 除此之外 由于上层节点并非在接收完所有下层 子节点后才进入发送状态 DMAC 协议还存在无 法使用数据汇聚技术的问题 上述两协议均使用 CSMA 机制 根据分析 CSMA 机制下节点须在接收时间段内保持接收状 态 引发长时间的空闲监听 相反 时分接入 TDMA 机制中节点仅在必要的发送或接收时 隙中工作 能有效降低空闲监听 因此在传感器 网络中越来越受到重视 TDMA 的主要难点在于 如何进行时隙分配 尤其是如何自适应 本地化 地进行时隙分配 文献 6 7 分别提出了一种集中式 的时隙分配方案 根据网络的拓扑结构为节点分 配相应的发送时隙以保证更小的时延及能耗 但 在集中式的分配方案中 根节点需随时获取最新 的全局拓扑信息并将分配方案向下广播至所有节 点 带来了大量额外的能量损耗且难以适应传感 器网络复杂多变的网络环境 另外 全局拓扑信 息的获取和更新等问题本身尚未得到很好的解决 Nicolas Burri 于 2007 年在 Dozer 协议 8 中提 出了一种利用父节点管理其子节点时隙分配的方 法 在一定程度上实现了时隙分配的本地化 但 由于父节点间时隙分配的独立性 这种分配方式 可能造成同一碰撞域内不同父节点管理下的子节 点间的时隙重叠 导致数据包碰撞 另一方面 由于缺乏统筹的时隙安排 节点数据在向 sink 34 通 信 学 报第 29 卷 节点传送过程中仍然可能发生 DFI 问题 导致较 大的时延 综上所述 采用 TDMA 接入机制可大幅度降 低空闲监听时间 较 CSMA 机制而言具有更高的 能源效率 但使用 TDMA 需首先解决两个关键问 题 一为时钟同步 二为时隙分配机制 FTSP 9 及 TDFS 10 协议已经成功地解决了时钟同步问题 而现有的时隙分配机制却仍然存在一定的不足 针对该问题 本文将提出一种基于自协商的自适 应 分布式 本地化时隙分配机制 并在此基础 上设计自协商分时 MAC 协议 4 自协商分时 MAC 协议 4 1 设计目标 本协议的设计目标包括 1 保证父节点的发送时隙位于所有子节点的 发送时隙之后 以有效进行数据汇聚并确保更小 的传输时延 参见文献 6 中的定理 3 1 2 保证节点分配到所需数目的发送子时隙 以确保更低的能耗和更高的有效数据收集率 分 配机制需具有自适应 分布式 本地化等特点 该分配机制是本文的主要创新点 为实现设计目标 1 本文借鉴 TAG 协议的思 想 首先根据节点到 sink 节点的跳数将网络分为 不同的层次 level 节点越靠近 sink 节点则层次越 高而对应 level 值越小 然后按照倒序方式为第 d 层次的节点分配长度为 TLd的发送时间段 该发送 时间段与第 d 1 层节点的接收时间段重合 为实 现设计目标 2 进一步将长度为 TLd的发送时间段 划分 Nd个长度为 Ts 的发送子时隙 其中每个发送 子时隙的长度恰好足够发送单个最长数据包并接 收单个 ACK 消息包 如图 2 所示 图 2 协议的分时结构 4 2 自协商时隙分配机制 观察位于层次 d 的某节点 i 假定其每周期所 需的发送子时隙个数为 Li 与其发生碰撞的同一 层节点的集合 简称碰撞域 为 i 则时隙分配 问题可描述如下 定义节点的占有时隙集合为 i 则最优时隙集合元素个数应大于 Li且满足 i 4 i ij j ss 为满足式 4 集中式的时隙分配方案需已 知所有节点的碰撞域集合 i i 1 N 1 这在节 点规模巨大的传感器网络是不现实的 本文所提 出的自协商时隙分配机制允许节点间通过一定的 交互协商机制自动调整占有时隙集合 i 从而在 短时间内收敛至满足式 4 的有效解 在传统的 TDMA 协议中 节点在其占有子时 隙内直接进入发送状态而无需执行随机退避 而 在本协议中 为实现节点间的协商 在子时隙内 引入了双竞争窗机制 其中竞争窗 A 范围为 0 W1 而竞争窗 B 范围为 W1 1 W2 子时 隙的组成如图 2 所示 在子时隙内节点需遵守如 下发送规则 节点在竞争窗 A 或 B 中在随机选 择某数值 保护间隔过后 节点切换到载波检 测状态并持续监听载波能量 若 T0 T0为单 位竞争窗所表示的时间 后仍未检测到有效载波 则代表信道空闲 随后节点切换至发送状态进行 发送 否则取消发送 规定 若子时隙 则节点 i 在该时隙中 i s 从竞争窗 A 中选择退避值 否则从竞争窗 B 中选 择退避值 定理 1 对某时隙 S 而言 若且 i s s 则即使所有节点均在该时隙中尝试发送 i j j 节点 i 仍将无碰撞地成功发送 证明 节点i 选取的退避值为 节点j i 选取的退避值为 由于且 i j j i s 则满足 i j j s 112 01 ij WWW 因此 节点 i 将在时间后检测到信道空 0i T 闲并随后开始发送 而其他节点则检测到信道忙 并取消发送 证毕 由定理 1 可知 采用双竞争窗机制在实现传 统 TDMA 的分时接入功能的同时又无需限制其他 节点的发送行为 子时隙的占有节点通过在竞争 第 11 期曾益等 用于传感器网络周期性数据收集的自协商分时 MAC 协议 35 窗 A 中选择退避值来保证发送优先权 规定 若 但节点 i 在该时隙中发送失 i s 败 检测到其他节点正在发送 则节点从占有时 隙集合中将 S 删除 即执行 i ii S 在上述规定下 可推出定理 2 定理 2 在某轮数据收集中 若子时隙 且 则一定周期后该子时隙占有情 i s i j j s 况将收敛至以下两种状态之一 1 且 i s 2 i j j s i s 证明 假定在第 n 轮数据收集中 某子时隙 且 即除节点 i 外 子时隙 i s 1 j sjl S 还是其他 l 个节点的占有子时隙 在该子时隙中 所有 l 1 个节点均从竞争窗 A 中随机选择退避值 分别记为及 若 i j 1 jl min ij 则节点 i 将成功发送 而其他 l 个 1 jl 节点将取消发送同时在占有集合中删除 S 即到达 状态 1 若存在min ji 则节点 i 将取消发 送 并在其占有集合中删除 S 即到达状态 2 若 min ji 则在本轮内仍然存在多个节点同时 成功发送的情况 尽管如此 下一轮数据收集中 节点仍将重复上述操作 一旦出现min ji 的 情况 时隙占有将收敛至定理 2 中的两个状态 理论上连续 n 轮数据收集出现 的概率min ji 小于 当 n 趋近无穷时该概率趋近于零 因 1 n W 此时隙占有终将收敛至以上两种状态 证毕 从定理 2 可知 通过一定周期的自协商可避 免同一碰撞域的多个节点占有同一子时隙 即满 足式 4 为完成时隙分配 节点的占有时隙集合 维数还须不小于其所需的发送子时隙个数 Li i 网络刚启动时 节点占有时隙为空 为逐步占有 子时隙 本文定义候选子时隙集合为 并规定 i 若某时隙且 节点将从竞争窗 B 中选 i s i s 择退避值 并尝试在该子时隙进行数据发送 若 节点 i 在该时隙中成功发送 则将 S 加入到其占有 时隙集合中即执行 并将 S 从 i ii S 中删除 否则仅将 S 从中删除 在该规定下 i i 只要发送子时隙总数足够多 总能生成维数不小 于 Li的占有时隙集合 因此该自协商时隙分配 i 机制可以满足时隙分配的要求 虽然时隙占有需要一定周期才能收敛 但由 于周期性数据收集场景中的数据流相对恒定 一 旦时隙占有收敛后便不会发生较大的改变 因而 自协商过程中带来的占有子时隙的暂时重叠并不 会对网络性能造成影响 4 3 自协商分时 MAC 协议 本文的自协商分时 MAC 协议使用了上节所提 到的自协商时隙分配机制 除此之外 其还包括 以下内容 4 3 1 ACK 重传机制 由于无线网络链路的不稳定性 数据包容易 丢失 为提高有效数据收集率 本协议使用了 ACK 重传机制 节点在数据包发送完成后 还需 等待接收节点发来的 ACK 包以确认本次传输成功 发送子时隙的总长度已经包含了 ACK 包的接收时 间 见 4 1 节 目的节点接收到数据包需等待一 段时间 保证最大长度的数据包发送完成 后向 源节点发送 ACK 包 以通知数据包接收正常 若 发送节点在本发送子时隙结束前仍未接收到 ACK 包 它将在其他占有子时隙或候选子时隙中重新 发送该数据包 若数据包连续发送失败 如连续 失败 3 次 节点将丢弃该数据包 数据包重传只 发生在同轮数据收集中 发送时间段结束时 节 点将丢弃所有在本轮中未能成功传送的数据包 4 3 2 包格式 协议中使用的包格式如图 3 所示 其中 包类型 低 7bit 表示该消息包的类 型 0 x00 表示为一般数据包 而 0 x01 表 示 ACK 包 需要注意的是 ACK 包不存在 下 个子时隙 数据长度 及 有效数据 等字段 包类型 最高比特为 表示该数据包为本 轮数据收集中源节点发送至目的节点的最后一个 数据包 最高比特为 则表示源节点还有其 他数据包需发送至目的节点 下个子时隙 字段中指示了来自源节点的 下个数据包可能的发送子时隙号 若该数据包为 本轮数据收集中源节点发送至目的节点的最后一 个数据包 则该字段表示下轮数据收集中首个来 自该源节点的数据包的发送子时隙号 接收节点 可利用该字段推算下个监听子时隙的位置 4 3 3 候选子时隙集合的选择 i 由于发送时间段位于接收时间段之后 因此 节点 i 可在发送时间段起始时刻根据接收到的数据 图 3 包格式 36 通 信 学 报第 29 卷 包个数 计算出待发送的数据包数目 即所需的 发送子时隙数目 Li 假定此时节点的占有子时隙 集合元素个数为 候选子时隙集合元素个 i i i 数为 若则节点无需更多的占有子时隙 i ii L 此时可将候选子时隙集合置空 若 i iii L 则节点无需更多的候选子时隙 若 则 iii L 节点还需从发送子时隙中随机选择个候 iii L 选子时隙 在发送时间段中 若节点在某候选子时隙中 成功发送 则该子时隙将被放入占有子时隙集合 中 否则 节点将把接下来的第一个非候选子时 隙或占有子时隙的发送子时隙加入至候选子时隙 集合中 以保证剩余的占有子时隙数目加上候选 子时隙数目等于此时还需发送的数据包数目 由 于协议使用了 ACK 重传机制 当未收到 ACK 确 认包时 节点需要增加占有子时隙数目以对相应 数据包进行重传 此时节点同样会将接下来的第 一个非候选子时隙或占有子时隙的发送子时隙加 入至候选子时隙集合中 4 3 4 监听子时隙集合 Ri的选择 在本小节中 将介绍节点如何确定在哪些接 收子时隙中切换至接收状态 即确定监听子时隙 集合 监听子时隙的选择是降低节点空闲监听 提高能源利用率的关键 节点应在不丢失数据包 的前提下选择尽量少的子时隙进行监听 CSMA 协议正是由于无法确定监听子时隙集合 因而必 须监听所有接收子时隙 造成能源利用率的下降 在本协议中 由于节点仅在占有子时隙集合及候 选子时隙集合中尝试发送数据包且数据包中包含 了 下个子时隙 字段 选择少数必要的子时隙 进行监听成为了可能 在网络起始的前几轮中 由于网络的占有时 隙分配未收敛 所有节点都将持续监听其接收时 间段内的全部接收子时隙并在该阶段中建立以下 集合 节点 i 收到的数据包的源节点集合 i P 各源节点首个数据包所对应的接收子时 i F 隙号集合 待时隙分配基本稳定后 节点将依照以下规 则选择监听子时隙集合 i R 1 即节点必须在所对应的接收子 ii FR i F 时隙号中切换至接收状态 2 假定某接收子时隙 若节点 i 在该子 i SR 时隙中成功接收到数据包 则数据包中 下个子 时隙 字段所对应的接收子时隙将被加入至监听 子时隙集合中 若此数据包为本轮数据收集中 i R 来自源节点的最后一个数据包 节点则根据 下 个子时隙 字段所对应的接收子时隙号更新 i F 若节点在该子时隙未接收到来自相应源节点的数 据包 节点将持续监听随后的接收子时隙 直至 重新接收到来自源节点的数据包 接收时间段结束时 节点检查是否所有来自 集合的数据包均被正确接收 检查接收数据包 i P 中 包类型 字段的最高位 若全部正确接收 节点将在下轮数据采集中仍然依照规则 1 和 2 选 择监听子时隙集合 否则节点将在下轮数据采集 中监听所有接收子时隙并更新及 i P i F 4 3 5 子时隙个数 Nd的选择 在本协议中 发送子时隙个数 Nd对协议的性 能有一定的影响 减小 Nd有利于降低数据时延 但若 Nd过小又可能造成占有子时隙分配不足 导 致有效数据收集率下降 相反 增大 Nd将增加数 据时延但能保证节点占有充分的子发送子时隙 在 TAG 协议中 增大 Nd还将加剧能耗 由于加 剧了空闲监听 但在本协议中 由于节点仅选择 必要的子时隙进行监听 无需监听所有接收子时 隙 所以能耗变化不大 理想情况下 Nd应根据 网络的节点密度及数据流量等信息进行动态调整 从而选取最优值 然而这在实际应用中往往难以 实现 本文推荐在网络布置前对网络的规模及密 度进行预测 在满足可容忍的最大数据延时情况 下 选取足够大的 Nd值以保证较高的有效数据收 集率 4 3 6 数据收集周期 数据收集周期的选择与节点的采样周期及期 望的最大数据延时有关 一般来说 期望的最大 数据延时大于节点的单个采样周期 因此数据收 集周期则可设置为节点的采样周期 倘若期望的 最大数据延时远大于节点的单个采样周期 也可 以将数据收集周期选择为采样周期的整数倍 需 要注意的是 数据收集周期最小值受到网络最大 吞吐量的限制 例如网络最大跳数为 n 每层节 点的发送时间段长度为 TLd 则数据收集周期应 第 11 期曾益等 用于传感器网络周期性数据收集的自协商分时 MAC 协议 37 大于 n d d TL 1 5 协议性能分析 为分析协议性能 使用 ns 2 对自协商分时 MAC 协议进行了仿真 并从总能耗 有效数据收 集率及最大数据时延这三方面进行了分析 协议 仿真中所使用的部分仿真参数见表 1 表 1物理信道参数及协议设置 物理信道参数参数值协议设置设置值 传输模型TwoRayGround最大有效数据长度48byte 载波频率433MHz 节点单周期采样数 据长度 2byte 传输码率19 2kbit s 第一层发送子时隙 数量 N1 70 接收范围20m 其他层发送子时隙 数量 Nd 35 载波检测范围60m竞争窗 W134 捕捉阈值10竞争窗 W269 接收状态电流20mA采样及数据收集周期60s 发射状态电流27mA仿真时间1h 仿真场景中 225 个节点有规则地分布在 168m 168m 的区域中 节点间水平及垂直距离为 12m sink 节点位于网络中央 5 1 有效数据收集率 图 4 给出了自协商分时 MAC 协议及 TAG 3 协议中 原始的 TAG 协议不包含 ACK 重传机 制 为方便比较 这里为其添加了重传机制 不 同最大重传次数及误包率情况下 仿真期间网络 的有效数据收集率 从图中可以看出 当未采用 ACK 重传机制时 即使误包率为零 TAG 协议 的有效数据收集率仍然只有 87 左右 CSMA 竞争机制所造成的数据包碰撞是导致低数据收集 率的主要原因 而在自协商分时 MAC 协议中 节点通过自协商机制获得满足式 4 的占有子 时隙集合 基本避免了数据包碰撞的发生 因而 取得了 99 99 的有效数据收集率 误包率逐步 上升后 两协议的有效数据收集率均开始下降 但相比 TAG 协议而言 自协商分时 MAC 协议 一直保持着更高的有效数据收集率 随着误包率 的上升后 数据包碰撞所造成的丢包占所有丢包 的比重越来越小 因此两协议间的差距呈现缩小 的趋势 使用 ACK 重传机制后 有效数据收集率有了 很大的提升 而且随着最大重传次数的上升 丢 包率对有效数据收集率的影响也越来越小 当最 大重传次数为 1 时 尽管丢包率为 10 TAG 协 议仍取得 93 4 的有效数据收集率 而自协商分时 MAC 协议也达到 89 相比未采用 ACK 重传机 制而言 有效数据收集率提高了近 40 当最大 重传次数增加时 有效数据收集率也随之增加 进一步可以发现 当丢包率小于 1 时 自协商分 时 MAC 协议比 TAG 协议具有更小的数据丢失率 而当丢包率大于在 5 时 TAG 协议则略优于自协 商分时 MAC 协议 原因在于 高丢包率情况下 节点需要更加频繁地申请新的占有子时隙 然而 自协商时隙分配需要一定周期以达到占有子时隙 分配的稳定性 在协商阶段可能造成数据包的碰 撞 导致网络有效数据收集率的下降 图 4 各协议在不同误包率及最大重传次数下的有效数据收集 该仿真表明 在传感器网络中 为实现可靠 的数据传输 ACK 重传机制是十分必要的 总 体而言 自协商分时 MAC 协议的有效数据收集 率与 TAG 协议相当 在较低丢包率下甚至比 TAG 更高 5 2 总能耗 图 5 图 6 分别给出了自协商分时 MAC 协议 及 TAG 协议中不同的误包率及最大重传次数情况 下 节点平均每轮数据收集中处于接收状态 包 括空闲监听及载波检测 及发送状态的时间 可以看出 在 TAG 协议中 由于节点需要在 每轮数据收集中监听整个接收时间段 因而节点平 均接收时间很高 达到了1 233ms 然而大部分接 收时间中 节点均处于空闲监听 idle listen 或串听 overhearing 状态 能源利用率较低 在自协商 38 通 信 学 报第 29 卷 分时 MAC 协议中 虽然节点处于接收状态的时间 随着误包率的上升有所增加 但均维持在30ms 左右 图 5 节点平均每轮数据收集中处于接收状态的时间 仅为 TAG 协议的 1 41 接收时间的大幅度缩减 得益于自协商时隙分配机制 该机制保证了节点 占有足够数目的发送子时隙 使得接收节点能够 仅在必要时切换至接收状态 从而基本杜绝了空 闲监听 idle listen 及 overhearing 另外 在自协 商分时 MAC 协议中 最大重传次数越大接收时 间反而最低 这是因为协议中规定 某轮中若节 点未能正确接收所有的数据包 其将在下轮收集 周期中持续监听整个接收时间段 最大重传次数 越大 数据包正确传输率则越高 因此减小了节 点监听整个接收时间段的次数 从而降低了平均 接收时间 从图 6 可以看出 两协议的平均发送时间基 本相同 均在 11ms 左右 当误包率小于 1 时 自协商分时 MAC 协议的平均发送时间比 TAG 协 议略低 这同样是由 TAG 协议中 CSMA 竞争机制 造成的数据包碰撞而引发的重传造成的 图 6 节点平均每轮数据收集中处于发送状态的时间 在大多数传感器网络硬件平台如 mica telos 等平台中 节点处于发送状态与接收 状态时所消耗的能 量相近 当使用 CC1020 芯 片时 处于接收状态时电流为20mA 而处于 发送状态时电流为 27mA 10dBm 发射功率时 在此参数下 自协商分时 MAC 协议的总体能 耗约为 TAG 协议的 1 30 5 3 最大数据延时 在自协商分时 MAC 协议和 TAG 协议中 由 于数据收集逐层展开 且节点将丢弃所有在本轮 中未能成功传送的数据包 因此在每层节点的发 送时间段确定的情况下 最大数据延时上限为 其中 n 为网络的最大跳数 TLd为第 d 层 n d d TL 1 节点的发送时间段长度 在仿真中 最大跳数为 7 第一层节点的发送时间段长度为 70 35ms 其 他层节点的发送时间段长度为 35 35ms 因此数 据延时上限为 9 8s 一般来说 足够满足采样周期 为 60s 的传感器网络应用中对数据时延的要求 缩 减 Nd可进一步降低最大数据延时 6 结束语 本文首先对应用于周期性数据收集场景中的 已有相关协议进行了总结 通过分析发现 现有 协议或基于 CSMA 竞争机制 造成严重的空闲监 听 或使用 TDMA 方式却未提出分布式 本地 化的时隙分配机制 导致难以适应复杂多变的网 络条件 因而仍然存在一定的不足 本文针对 这一现状并充分考虑周期性数据收集场景中数据 流的主要特点 提出了一种自适应 分布式 本 地化的自动协商时隙分配机制 并在此基础上设 计了自协商分时 MAC 协议 ns 2 仿真结果表明 自协商分时 MAC 协议与添加 ACK 重传机制后 的 TAG 协议具有相当的最大数据延时及有效数 据收集率 而能耗却仅为后者的 1 30 因而更加 适合应用于周期性的数据收集场景中 当然 本 协议仍然存在许多有待改进之处 如无法动态调 整 Nd等 在接下来的工作中 将对协议进行更深 一步的分析 参考文献 1 AKYILDIZ I F SU W SANKARASUBRAMANIAN Y A survey 第 11 期曾益等 用于传感器网络周期性数据收集的自协商分时 MAC 协议 39 on sensor networks J IEEE Communications Magazine 2002 40 8 102 114 2 SAMUEL M MICHAEL J F JOSEPH M H TAG a tiny aggregation service for ad hoc sensor networks A 5th Annual Symposium on Operating Systems Design and Implementation C 2002 131 146 3 ANT