第２６卷第３期 ２０１３年６月 四川理工学院学报（自然科学版） Ｊｏｕｍａｌ ｏｆ Ｓｉｃｈｕａｎ Ｕｎｉｖｅｒｓｉｔｙ ｏｆ Ｓｃｉｅｎｃｅ＆Ｅｎｇｉｎｅｅｒｉｎｇ（Ｎａｔｕｒａｌ Ｓｃｉｅｎｃｅ Ｅｄｉｔｉｏｎ） Ｖｏ１．２６ Ｎｏ．３ Ｊｕｎ．２０１３ 文章编号：１６７３－１５４９（２０１３）０３－００５０４３４ ＤＯＩ：１０．３９６９／ｊ．ｉｓｓｎ．１６７３・１５４９．２０１３．０３．０１２ 一种基于簇树结构的ＺｉｇＢｅｅ网络最大生存期方法研究 陈宁，徐显秋 （重庆科技学院，重庆４０１３３１） 摘要：提出了一种基于簇树结构的ＺｉｇＢｅｅ网络最大化生存时间的方法，该簇树主要针对实时传感 应用，且每个数据流应确保端到端的生存期。该方法将全网范围内的优化问题分解成每个簇的优化问 题来解决，找到了一种低复杂度的优选方案。 关键词：最大生存期；簇树；ＺｉｇＢｅｅ网络 中图分类号：ＴＰ３９３ 文献标志码：Ａ 引言 Ｚｉｇｂｅｅ是一种短距离、低速率的无线传感器网络的 流数据的生命周期前提下，使整个网络的生存时间最大 化。 （２）对优化问题建模，尽可能考虑丫节点的各种特 性，如电能、节点类型等。 （３）通过将全局性的优化问题分解为基于簇的一 系列本地问题，提出了一种启发式算法，以低复杂度优 化配置ＺｉｇＢｅｅ参数。 技术标准，其ＰＨＹ层和ＭＡＣ层协议为ＩＥＥＥ８０２．１５．４ 协议标准 。主要特性是低速率、近距离、低功耗、低复 杂度和低成本。 在家用和工业方面的实时传感控制领域，ＺｉｇＢｅｅ簇 树结构网络是一种兼顾成本和效率的选择。在本文中， １ 问题描述 ＩＥＥＥ８０２．１５．４发布的簇Ｃ 中Ｂ， 和ＳＤ 的结构由 如下公式定义： 曰 ＝ａＢＳＦＤ・２肋 、 主要针对基于簇树结构的ＺｉｇＢｅｅ网络，在确保端到端传 感控制报文的生命周期前提下，如何最大化网络的生存 时间。 一个簇树网络包括多个簇，每个簇有簇头、边界节 点和普通节点。簇头每隔一定时间通过广播信标的方 式来同步簇中的各节点。信标间歇期间：为了节省能 耗，只有超帧阶段，簇中节点和簇才进行通信，其余时间 处于休眠状态。作为边界节点，在连接的各个簇中均要 处于激活状态。一旦给定簇树结构的网络，数据流的传 输路径就被该树的结构所确定下来。至于如何优化簇 ＳＤ ＝ａＢＳＦＤ・２ 仉｝ ０≤ＳＯＫ≤ＢＯ ≤１４ Ｊ （１） 在ＳＤ中，对于非实时数据，竞争访问期（ＣＡＰ）以基于竞 争的方式被访问，对于实时数据而言，自由竞争期 （ＣＦＰ）被分派给保证时间时隙（ＣＴＳｓ）节点。为了给非 实时数据报文提供服务，给ＣＡＰ预留载荷时，ＧＴＳｓ被分 树结构的问题不在本文探讨的范围之内，这里仅以一个 预先定义好的簇树结构网络，来研究给定簇树网络中 ＺｉｇＢｅｅ参数的优化配置，主要包含如下内容： （１）通过对ＺｉｇＢｅｅ参数的优化，在保证端到端实时 配在ＳＤ 之外。 簇实际上是一个逻辑节点组，不同簇中两个节点有 可能相互干扰 。为了避免这种簇间冲突，多个簇中的 Ｂｌｓ和ＳＤｓ要很好的安排以免交叠。这种安排在一些文 收稿日期：２０１３－０３—１７ 基金项目：重庆市石油与天然气学会资助项目（ＫＪ２０１１００４） 作者简介：陈宁（１９７３一），男，重庆人，工程师，硕士，主要从事无线传感网方面的研究，（Ｅ－ｍａｉｌ）ｎｉｎｇｃｈｅｎ６６０＠ｓｉｎａ．ｃｏｉｎ Ⅳ 舭 第２６卷第３期 陈宁等：一种基于簇树结构的ＺｉｇＢｅｅ网络最大生存期方法研究 ５ｌ Ⅳ献 中有涉及。然而，在ＺｉｇＢｅｅ簇树网络中，满足实 案，但在０（１５ ）的高复杂度下，造成了可量测性问题。 为解决全局无遗漏搜索的问题，本文提出了一种启发式 算法，在明显减少复杂度的前提下，同时提供最优解决 时性的前提下，怎样优化配置Ｂ／ｓ和ＳＤｓ仍然是个难题。 那么我们要解决的问题就是对于一个给定的含有Ｋ簇 的簇树网络和数据流集Ｆ，通过优化各簇中的Ｂｌｋ和ＳＤ 以满足端到端的生存期条件。同时，在考虑能量储备和 每个节点类型情况下，使网络的生存时间最大化。 先定义每个节点的能耗，节点的能耗被它所属簇的 负载循环所确定，即ＳＤ／ＢＩ。由于节点可能属于多个簇， 如边界节点，将连接到所有簇的负载循环相加 （＝∑ ，见表１）。考虑到每个节点的电能 不同，基于电能对节点的能耗做了规范化处理。我们尽 量将节点能耗的最大值变小以延长整个系统的生存时 间。如果任一节点能源耗尽，整个系统会受影响。这 样，得到度量值Ｍ… 。 １ （２） 由此，优化问题即转变为最小化 … 的问题。其 中约束条件如下： 条件１：对于每个数据流 ，最坏情况下，端到端时 延应当小于等于它的生存周期。 条件２：为避免簇间冲突，所有（ＢＩｋ，ＳＤ ）对，应按照 无ＳＤ交叠来安排。 条件３：确保非实时数据包的ＣＡＰ服务。 表１公式中的符号释义 符号 释 义 节点集 节点ｎ所属的簇集 第ｋ簇 在ｃ 中，分派到节点ｎ的ＧＴＳ时隙数 在簇 中，ＣＡＰ服务的时隙数 在簇 中，所求ＣＡＰ的最小时隙数 在簇 中，ＣＡＰ服务的载荷 在ｃ ＝∑ ＾ 等 时的Ｇ１［＿ｓ载荷 在Ｃ ＝【， ＋ｆ， 时的所有载荷 节点ｎ的电能 第ｉ个实时流（由ＳＦＣ ，ｄｓｔ ，Ｐ ，ｂ Ｄ ）表达。 在簇 中，本地化的每簇生存期 沿着 路径的簇集 沿着簇ｃ 传播的流集 最坏情况下 的端到端时延 给定曰，ｋ值，在ｃ 中 最坏情况下的一跳时延 ２算法分析 对于给定的含Ｋ个簇的簇树结构的网络，遍历所有 （（ ，。，ｓＤ ），…，（ＢＩ ，ＳＤ ））的可能组合以找到最优方 方案。其基本理念是将全局问题“智能”分解成如下的 若干本地问题： 第一步，将属于多个簇的簇内边界节点分解成簇内 的虚节点集。 第二步，将端到端的生存期分解成基于簇的单跳生 存期集。 第三步，估算每簇最坏情况单跳时延。 第四步，基于上述步骤为每个簇选择 和ＳＤ。 由于本地化，可以优化配置每个簇Ｃ 的曰， 和 ＳＤ 。该启发式算法的复杂度为０（１５ Ｋ），与０（１５ ） 相比复杂度明显降低。 ２．１边界节点分解 将簇内的边界节点分解成一个虚节点集，并使每个 虚节点仅属于一个簇。原边界节点的能量根据簇的载 荷按比例分成了两部分，如公式（３）。每部分分派给新 创建的虚节点。 Ｕ＾ … Ｐ 盯 Ｐ ｎ — ｌ＿ （ｊ Ｖ Ｅ 公式（３）中， 是边界节点ｎ的虚节点集， 属于簇 Ｃ 的虚节点集 。 ２．２端到端的生存期分解 对于给定的数据流 ，把端到端的生存期Ｄｉ分解到 基于簇的本地生存期中。基本策略是分派较长的本地 生存期给一个高载荷、低能量的簇。通过这样处理，可 以获得大ＢＩｋ，该值可以减少“被浪费的时隙部分”，接着 减少负载循环， 。这就是“生存期能量平衡”。在 ＺｉｇＢｅｅ系统中，分派带时间资源的每个节点如多时隙一 样，没有连续的时间周期。这个特性导致了分派的一些 时隙被浪费，以致未真正用到传输中，特别是当Ｂ，尺寸 很小时 。生存期划分的详细过程如下： （１）计算权重１，０ ，对于每簇中考虑了载荷和能量的 ｋ如下： ‘ 蒜 （４） 式（４）中簇的能量（ＣｌｕｓｔｅｒＰｏｗｅｒ ）定义成所有节点 中（包括虚节点）的最小能量级别。如果ＯＬ》 ，意味着 本地生存期完全成比例的将载荷和能量进行了分派。 反之，如果 《 则不管每簇的载荷和能量，直接进行平 均分派。本文中，设定 ： 以适应所有策略。 ５２ 四川理工学院学报（自然科学版） ２０１３年６月 （２）计算每簇的生存期，ｄ ，该值与前面的权重因 素Ｗ 有关： ＳＤ ／１６（在∞中的时隙数是１６，按照ＩＥＥＥ规范…）。 Ｇ ｓ ：ｌ ㈦ ｄ Ｄ — （５） ２一 ｉ Ｖ Ｅ Ｒｏｕｔｅ ２．３最坏时延估算 最大端到端时延，即数据流 中的ＷＤ 通过添加最 差单跳时延来获取，每簇中的ＷＤ：（ＢＩ ）沿着路径呈现。 由于对簇 而言，最坏情况下的单跳时延受曰， 影响， 所以它是关于 ， 的函数。在计算ＷＤ （曰， ）时，考虑 这样的场景，在ｃ 中，数据流 的多个报文没有一次能 全部确定下来。在这种情况下，刚开始的前ｑ个报文最 差情况下的时间１１） （ｑ）按如下公式计算： ＝ｌ ｓ ＝ 巩㈩ 公式（６）含义如下：传输ｇ个数据报文的时间是 ｑ・ｂ／Ｒ，在每个Ｂ， 中ｓ 被提供给数据流 ， 【ｌ Ｉ 就是要求的Ｓ 的数目。对于有着Ｓ 数目的 数据流 的整个最坏时间是ｌＩ １．曰 。由于第ｑ 个数据报文到达时间是（ｑ一１） Ｐ ，相对于它的到达时 间的一跳时延就是 （ｑ）一（ｑ一１）Ｐ 。在ｇ：１，２…．． 所有可能值时，ＷＤ （ ）是 （ｑ）一（ｑ一１）Ｐ 中的最 大值。已有文献证明了在ｑ＝１，２…．Ｑ时，这个最大值 存在。Ｑ是满足 （ｑ）≤Ｑ・Ｐ 的第一个整数。ＷＤ （ＢＩ ）按如下公式计算： ＷＤ （Ｂ， ）＝ｍ．．ａｘ ｗ （ｑ）一（ｇ一１）Ｐ （７） 最后，计算最坏情况下的端到端时延ＷＤ ，通过沿 着数据流 的路径添加ＷＤ （ＢＩ ）。如果ＷＤ ≤Ｄ ，所 有 中的数据包可以保证在生存期内到达目的地。 ２．４ ＢＩ和ＳＤ选择 一旦确定了每个数据流的每簇生存期集，对于每个 簇ｃ 而言，就可以通过检验，获取本地簇中最佳Ｂｌｋ值。 对于每个簇，我们考虑了１５种Ｂ，值的可能性，并计算了 相关的ｓ，值。得到给出最小 值的最佳Ｂｌｋ值，即当 保持最坏情况下单跳时延小于每个流 的每簇本地生 存期时，该流经过了 （例如，ＷＤ （日， ）＜ｄ ）。如果 没有曰， 值满足这个本地条件，Ｂ， 就设置为最小值（如 果超过一个簇，ＢＯ 在公式（１）中应该比０大）。 一旦Ｂ， 确定，５Ｄ 就能计算出来。首先，对于属于 ｃ 的节点ｎ，为其服务的ＧＴＳ流量，ＧＴＳ：按公式（８）计 算。ＧＴＳ：是时隙长度的整数倍数，时隙长度ＳｌｏｔＬｅｎ ＝ ｌ— Ｉ此外，对于非实时数据包，ＳＤ 必须包含ＣＡＰ 。 ＣＡＰ 也是时隙的整数倍，要求的ＣＡＰ 所需要的时隙最 小数按如下公式求出： ＭＩＮ＿ＣＡＰｋ ｃ ｓ ＝Ｉ Ｉ 这个时隙数目，Ｔ（ＳＤ ）在公式（９）中被定义，其值 不大于ｌ６。ＳＤ 由满足公式（９）的最小如 值确定（一 旦ＳＤ 被公式（９）确定，ＣＡＰ 的值通过１６一 ∑ 属于 ＧＴＳ＇；（ＳＤ ）计算而确定）： （ＳＤ＾）＝ＭＩＮ＿ＣＡＰ （ＳＤ＾）＋∑ＧＴＳ￣（ＳＤ ）≤１６ （９） ３测试评估 评价本文提出的启发式算法基于两个参考标准： （１）可行性；（２）负载循环。其详细的评估网络和参数 设置描述，见表２。 表２测试场景：４个簇，１１个节点，７个数据流 为检测本地化优化方法对可行性的影响，模拟了 基于表２的１２ ６５８个随机测试集，并针对提出的启发 式算法计算了能找到满足时序和生存期条件的解决方 案的测试集数目 。根据整个系统载荷，将这个集分 成两类，即ＬＯＷ—Ｌｏａｄ和ＨＩＧＨ—Ｌｏａｄ。在模拟过程中， 当整个载荷少于５０％时，提出的启发式算法９９％能找 到ＢＩ和ＳＤ的组合解决方案（例如，７０２４个测试集中 有６９５６个）。另一方面，可行性在高载荷系统中明显 降低，对于大部分ＺｉｇＢｅｅ应用而言这种情况不常见。 表３和图１是部分实验结果。 表３方案比较：可行性 为检验所提出算法在平衡每个节点的能耗方面的 第２６卷第３期 陈宁等：一种基于簇树结构的ＺｉｇＢｅｅ网络最大生存期方法研究 参考文献： ５３ ［１］ＺｉｇＢｅｅ—Ａｌｌｉａｎｃｅ．ＺｉｇＢｅｅ／Ｓｐｅｃｉｉｆｃａｔｉｏｎｓ［ＥＢ／ＯＬ］．ｈｔｔｐ：／／ 萎 蓥 ｉ｛ｑ｛４ ｚｉｇ—ｂｅｅ．ｏｒｇ／２０１２ ［２］孙静。基于ＺｉｇＢｅｅ的簇树协议分析［Ｊ］．网络与信息， ２０１０，２４（１ １、：５０． 崔 主 ［３］史品，郑萍．基于ｚｉｇＢｅｅ的ＰＬＣ无线数据采集系统 设计［Ｊ］．西华大学学报：自然科学版，２０１０，２９（６）：２８— ３１． ￣Ｌｐ ａｐ胛ｃｈⅢ＿ｐ０ｗｅ岫 蝴Ａｌ＿） ［４］乐英高，曹莉，曾黄麟．基于ＺｉｇＢｅｅ和ＭＳＰ４３０无线 图１ …的比较 温度控制系统设计［Ｊ］．四川理工学院学报：自然科 学版，２０１２，２５（１）：５２－５５． ［５］Ｋｏｕｂａａ Ａ，Ａｌｖｅｓ Ｍ，Ａｔｔｉａ Ｍ．Ｃｏｌｌｉｓｉｏｎ－ｆｒｅｅ ｂｅａｃｏｎ ｓｃｈｅｄｕｌｉｎｇ ｍｅｃｈａｎｉｓｍｓ ｆｏｒ ＩＥＥＥ ８０２．１ ５．４ ｇｂｅｅ ｃｌｕｓ— 优势，考虑了每个节点不同电能的情况，图１基于 … 对７０２４个低载荷测试集进行了评测。与基准线方法类 似，我们提出了图示为ＮＡＩＶＥ一０…．．，ＮＡＩＶＥ一９的方 法，它们分派了同样的Ｂｊ值给所有簇，但未考虑个别流 功能和每个节点的电能。例如，ＮＡＩＶＥ一０将ＢＯ ＝０分 派给所有簇。在图中， 轴表示 … （＝ ｔｅｒ—ｔｒｅｅ ｗｉｆｅｌｅｓｓ ｓｅｎｓｏｒ ｎｅｔｗｏｒｋｓ［Ｃ］／／Ｌｕｉｓ Ｍ．７ｔｈ Ｉｎｔｅｒ－ ｎａｔｉｏｎａｌ Ｗｏｒｋｓｈｏｐ ｏｎ Ａｐｐｌｉｃａｔｉｏｎｓ ａｎｄ Ｓｅｒｖｉｃｅｓ ｉｎ Ｗｉｒｅｌｅｓｓ Ｎｅｔｗｏｒｋｓ（ＡＳＷＮ），Ｃａｎｔａｂｒｉａ，Ｓｐａｉｎ，Ｍａｙ ２４— ２５，２００７：１－８． … ，等 ＯＰＴＩＭＡＬ （ ） ），Ｙ轴是测试样本数目。对于‘ 。 ［６】Ｋｏｕｂａａ Ａ，Ａｌｖｅｓ Ｍ，Ｔｏｖａｒ Ｅ．ＧＴＳ ａｌｌｏｃａｔｉｏｎ ａｎａｌｙｓｉｓ ｉｎ ＩＥＥＥ ８０２．１５．４ ｆｏｒ ｒｅａｌ—ｔｉｍｅ ｗｉｒｅｌｅｓｓ ｓｅｎｓｏｒ ｎｅｔｗｏｒｋｓ ９４％的样本而言，在电能消耗的优化能力方面，启发式 与优化解决方案一样，显示出了同样的水准。另一方 面，原有方法与启发式方案相比，其能耗较差。 ［ｅｌ／／ＩＥＥＥ．Ｐｒｏｃ．Ｏｆ ２０ｔｈ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｐａｒａｌｌｅｌ ａｎｄ Ｄｉｓ— ｔｒｉｂｕｔｅｄ Ｐｒｏｃｅｓｓｉｎｇ Ｓｙｍｐｏｓｉｕｍ，Ｒｈｏｄｅｓ Ｉｓｌａｎｄ，Ｇｒｅｅｃｅ， Ａｐｒｉｌ ２５—２９，２００６：１—８． ４结束语 本文提出了一种启发式方案以优化配置ＺｉｇＢｅｅ网 络簇树的参数，在确保所有实时周期数据流的生存期前 提下，达到最大化网络生存时间。实验研究表明该方案 在低载荷测试集的情况下，在最大化网络生存时间时， 能提供时序化、满足生存期的解决方案。 ［７】Ｈａｒｔ Ｊ，Ｃｈｏｉ Ｓ，Ｐａｒｋ Ｔ．Ｍａｘｉｍｉｉｚｎｇ ｌｉｆｅｔｉｍｅ ｏｆ ｃｌｕｓｔｅｒ—ｔｒｅｅ ｉｇｂｅｅ ｎｅｔＺｗｏｒｋｓ ｕｎｄｅｒ ｅｎｄ・・ｔｏ－－ｅｎｄ ｄｅａｄｌｉｎｅ ｃｏｎｓｔｒａｉｎｔｓ ［Ｊ］．Ｃｏｍｍｔｍｉｃａｔｉｏｎｓ Ｌｅｔｔｅｒｓ，ＩＥＥＥ，２０１０，１４（３）：２１４－２１６． ［８】Ｃａｓｅｙ Ｐ Ｒ，Ｔｅｐｅ Ｋ Ｅ，Ｋａｒ Ｎ．Ｄｅｓｉｇｎ ａｎｄ ｉｍｐｌｅｍｅｎｔａｔｉｏｎ ｏｆ Ｔｅｓｔｂｅｄ ｆｏｒ ＩＥＥＥ ８０２．１５．４（ｚｉｇｂｅｅ）ｐｅｒｆｏｒｍａｎｃｅ ｍｅａｓｕｒｅｍｅｎｔｓ［Ｊ】．ＥＵＲＡＳＩＰ Ｊｏｕｒｎａｌ ｏｎ Ｗｉｒｅｌｅｓｓ Ｃｏｍ－ ｍｕｎｉｃａｔｉｏｎｓ ａｎｄ Ｎｅｔｗｏｒｋｉｎｇ，２０１０（Ｓ）：１６０—１７０． Ｍａｘｉｍｕｍ Ｌｉｆｅｔｉｍｅ Ｒｅｓｅａｒｃｈ ｏｆ ＺｉｇＢｅｅ Ｎｅｔｗｏｒｋｓ Ｂａｓｅｄ ｏｎ Ｃｌｕｓｔｅｒ—Ｔｒｅｅ ＣＨＥＮ Ｎ ｇ，ＸＵＸｉａｎ—ｑｉｕ （Ｃｈｏｎｇｑｉｎｇ Ｕｎｉｖｅｒｓｉｔｙ ｏｆ Ｓｃｉｅｎｃｅ＆Ｔｅｃｈｎｏｌｏｇｙ，Ｃｈｏｎｇｑｉｎｇ ４０１３３１，Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ａ ｍｅｔｈｏｄ ｔｏ ｍａｘｉｍｉｚｅ ｔｈｅ ｌｉｆｅｔｉｍｅ ｏｆ ａ ＺｉｇＢｅｅ ｎｅｔｗｏｒｋ ｂａｓｅｄ ｏｎ ｃｌｕｓｔｅｒ．ｔｒｅｅ ｉｓ ｐｒｏｐｏｓｅｄ，ｕｎｄｅｒ ｔｈｅ ｃｏｎｓｔｒａｉｎｔ ｔｈａｔ ｅｖｅｒｙ ｄａｔａ ｆｌｏｗ ｓｈｏｕｌｄ ｄｅｔｅｒｍｉｎｉｓｔｉｃａｌｌｙ ｍｅｅｔ ｉｔｓ ｅｎｄ—ｔｏ—ｅｎｄ ｄｅａｄｌｉｎｅ ｆｏｒ ｒｅａｌ—ｔｉｍｅ ｓｅｎｓｉｎｇ ａｐｐｌｉｃａｔｉｏｎｓ．Ｉｔ ｄｅｃｏｍｐｏｓｅｓ ｔｈｅ ｎｅｔｗｏｒｋ—ｗｉｄｅ ｏｐｔｉｍｉｚａｔｉｏｎ ｐｒｏｂｌｅｍ ｉｎｔｏ ａ ｓｅｔ ｏｆ ｐｅｒ－ｃｌｕｓｔｅｒ ｏｐｔｉｍｉｚａｔｉｏｎ ｐｒｏｂｌｅｍｓａｎｄ ｈｅｎｃｅ ａ ｏｐｔｉｍａｌ ｓｏｌｕｔｉｏｎ ｗｉｔｈ ａ ｌｏｗ ．ｃｏｍｐｌｅｘｉｔｙ ｉｓ ｆｏｕｎｄ． Ｋｅｙ ｗｏｒｄｓ：ｍａｘｉｍｕｍ ｌｉｆｅｔｉｍｅ；ｃｌｕｓｔｅｒ—ｔｒｅｅ；ＺｉｇＢｅｅ Ｎｅｔｗｏｒｋｓ