第３４卷 第ｌ９期 １１ｏＬ３４ ・计算机工程 ２００８年１Ｏ月 Ｏｃｔｏｈｅｒ ２ＯＯ８ Ｎｏ．１９ Ｃｏｍｐｕｔｅｒ Ｅｎｇｉｎｅｅｒｉｎｇ １毫士论文・ 文章编号：１００ｔｌ－－３４２８（２００８）１９－－－－００１２，－－４１３ 文献标识码：Ａ 中田分类号；ＴＰ３０１．６ 无线传感器网络异构驱动路由算法 杨挺 ，孙雨耕 ，张志东 ，杨郁 （１．天津大学电气与自动化工程学院，天津３０００７２；２．天津市电力公司电力通信分公司，天津３０００１０） 摘要：融合表驱动路由和按需驱动路由的优点提出一种异构驱动的无线传感器网络路由算法，以实现无线传感器网络监测数据的高效汇 集。算法将无线传感器网络的原有单一汇聚节点（Ｓｉｎｋ节点）扩充为一组无环连通点集，称为虚拟槽节点以覆盖全网。感知节点采用按需驱 动路由策略将监测数据在短距离内传递给虚拟槽节点，随后数据在虚拟槽节点内部依照表驱动路由实现高速汇集。通过理论计算确定最优 虚拟槽节点选取方式，并提出两跳邻居算法实现路由。经仿真实验，算法可保证网络内任意节点两跳可达虚拟槽节点，并通过分析仿真数 据论证算法的有效性。 关健诃：无线传感器网络；虚拟槽节点；按需路由；表驱动路由；生成树 Ｗｉｒｅｌｅｓｓ Ｓｅｎｓｏｒ Ｎｅｔｗｏｒｋ Ｈｅｔｅｒｏｇｅｎｅｏｕｓ Ｄｒｉｖｅｎ Ｒｏｕｔｉｎｇ Ａｌｇｏｒｉｔｈｍ ＹＡＮＧ Ｔｉｎｇ ，ＳＵＮ Ｙｕ＇ｇｅｎｇ ，ＺＨＡＮＧ Ｚｈｉ．ｄｏｎｇ ，ＹＡＮＧ Ｙｕ （１．Ｓｃｈｏｏｌ ｏｆ Ｅｌｅｃｔｒｉｃａｌ ａｎｄ Ａｕｔｏｍａｔｉｏｎ Ｅｎｇｉｎｅｅｒｉｎｇ，Ｔｉａｎｊｉｎ Ｕｎｉｖｅｒｓｉｔｙ，Ｔｉａｎｊｉ￣３０００７２； ２．Ｅｌｅｃｔｒｉｃ Ｐｏｗｅｒ Ｃｏｍｍｕｎｉｃａｔｉｏｎ Ｓｕｂｓｉｄｉａｒｙ Ｃｏｍｐａｎｙ，Ｔｉａｎｊｉｎ Ｅｌｅｃｔｒｉｃ Ｐｏｗｅｒ Ｃｏｒｐｏｒａｔｉｏｎ，Ｔｉａｎｊｉｎ ３０００１０） ［Ａｂｓｔｒａｃｔ］Ｉｎｔｅｇｒａｔｉｎｇ ｔｈｅ ａｄｖａｎｔａｇｅｓ ｏｆ ｔｈｅ ｔａｂｌｅ ｄｒｉｖｅｎ ｒｏｕｔｉｎｇ ａｎｄ ｔｈｅ ｄｅｍａｎｄ ｒｏｕｔｉｎｇ，ｔｈｉｓ ｐａｐｅｒ ｐｒｏｐｏｓｅｓ ａ ｎｅｗ ｗｉｒｅｌｅｓｓ ｓｅｎｓｏｒ ｎｅｔｗｏｒｋ ｒｏｕｔｉｎｇ ａｌｇｏｒｉｔｈｍ．Ｂａｓｅｄ ｏｎ ｓｐａｎｎｉｎｇ ｔｒｅｅ ｔｈｅｏｒｉｅｓ，ｔｈｅ ａｌｇｏｒｉｔｈｍ ｅｘｔｅｎｄｓ ｔｈｅ ｏｒｉｇｉｎａｌ ｓｉｎｇｌｅ ｓｉｎｋ ｎｏｄｅ ｔＯ ａ ｓｅｔ ｏｆ ｃｏｎｎｅｃｔｉｖｅ ｎｏｄｅｓ ｗｉｈｏｕｔｔ ｌｏｏｐ， ｃａｌｌｅｄ ｔｈｅ ｖｉｒｔｕａｌ ｓｉｎｋ，ｗｈｉｃｈ ｏｖｅｒｌａｙｓ ｔｈｅ ｗｈｏｌｅ ｎｅｔｗｏｒｋｓ．Ｍｏｎｉｔｏｒｉｎｇ ｄａｔａ ｃａｎ ｂｅ ｆａｓｔ ｇａｎｓ￣ｔｗｄ ｆｒｏｍ ｔｈｅ ｓｅｎｓｏｒ ｎｏｄｅｓ ｔＯ ｔｈｅ ｖｉｔｕａｌｒ ｓｉｎｋ ｉｎ ｓｈｏｒｔ—ｒａｎｇｅ ｗｉｈ ｔｔｈｅ ｄｅｍａｎｄ ｒｏｕｔｉｎｇ．Ａｎｄ ｔｈｅｎ ａｌｌ ｏｆ ｈｅｓｅ ｄａｔｔａ ａｒｅ ｅｆｆｅｃｔｉｖｅｌｙ ｇａｔｈｅｒｅｄ ｔｏ ｔｈｅ ｒｅａｌ ｓｉｎｋ ｎｏｄｅ ｂｙ ｔｈｅ ｔａｂｌｅ ｄｒｉｖｅｎ ｒｏｕｔｉｎｇ．Ｔｈｅ ｐａｐｅｒ ｓｔｕｄｉｅｓ ｔｈｅ ｏｐｔｉｍａｌ ｍｅｔｈｏｄ ｔＯ ｓｅｌｅｃｔ ｈｅ ｖｉｔｒｔｕａｌ ｓｉｎｋ，ａｎｄ ｐｒｏｐｏｓｅｓ ｔｈｅ“ｔｗｏ—ｈｏｐ ｄｉｓｔａｎｃｅ ｎｅｉｇｈｂｏｒ＇’ａｌｇｏｒｉｔｈｍ ｔＯ ｉｍｐｌｅｍｅｎｔ ｈｅ ｔｒｏｕｔｉｎｇ．Ｕｓｉｎｇ ｈｅ ｔｓｉｍｕｌａｔｉｏｎ，ｅａｃｈ ｎｏｄｅ ｍｕｓｔ ｒｅａｃｈ ｈｅ ｔｖｉｔｕａｌｒ ｓｉｎｋ ｉｎ ｔＷＯ ｈｏｐｓ．Ｔｈｅ ａｌｇｏｒｉｈｍ ｔｉｓ ｆｅａｓｉｂｌｅ ｎｄ ｐｒｅｆｅｒａｂｌａｅ ｂｙ ｃｏｍｐｕｔｅｒ ｓｉｍｕｌａｔｉｏｎ． ［Ｋｅｙ ｗｏｒｄｓｌ ｗｉｒｅｌｅｓｓ ｓｅｎｓｏｒ ｎｅｔｗｏｒｋ；ｖｉｒｔｕａｌ ｓｉｎｋ；ｄｅｍａｎｄ ｒｏｕｔｉｎｇ；ｔａｂｌｅ ｄｒｉｖｅｎ ｒｏｕｔｉｎｇ；ｓｐａｎｎｉｎｇ ｔｒｅｅ １概述 无线传感器网络（Ｗｉｒｅｌｅｓｓ Ｓｅｎｓｏｒ Ｎｅｔｗｏｒｋ，ＷＳＮ）综合传 寻找到１￣２跳范围内邻居虚拟槽节点，而虚拟槽节点与槽节 点按已有的表驱动模式实现数据的快速汇聚。本文通过理论 感技术、嵌入式技术、分布式信息处理技术和无线通信技术， 能够协作地实时监测、感知并采集各种监测对象的信息，并 对其进行处理，传送到这些信息的用户。因此，传感器网络 在军事、工业、环境、商业等领域有着巨大的应用价值 。 。 但传感器节点计算能力弱以及网络能量、资源有限的特 性使得无线传感器网络有着诸多的问题需要深入研究。其中， 在计算和存储能力较弱传感器节点上设计有效网络划分和路 计算以确定最优虚拟槽节点选取方式，并通过仿真实验验证 该优化选择保证网络内任意节点两跳可达虚拟槽节点的概率 为９７％，因此传感器节点无需存储大量的路由信息亦能实现 快速高效路由。 ２无线自组织网络路由算法研究现状 在ＷＳＮ中，各传感器节点采用自组织方式形成网络。 目前，自组织网络路由协议可分为２类：表驱动路由（ｔａｂｌｅ ｄｒｉｖｅｎ ｒｏｕｔｉｎｇ）和源发起按需驱动路由（ｓｏｕｒｃｅ ｉｎｉｔｉａｔｅｄ ｏｎ ｄｅｍａｎｄ ｒｏｕｔｉｎｇ）。 由协议以实现可靠数据通信成为学术界研究热点，对实现健 壮可靠的无线传感器网络服务具有重要的理论意义和实际 价值 。 使用表驱动路由协议，网络中的每个节点维持一个或多 个路由表来存储其他节点的路由信息，通过周期性广播更新 网络信息来保持路由表信息与网络拓扑的变化之间的一致 性。因此，表驱动路由协议具有快速建立到信宿节点的路由 的优点，但也存在信号拥塞和路由过程中能量过度消耗的缺 目前，无线传感器网络路由协议可分为表驱动路由和源 发起按需驱动路由两类。表驱动路由协议可快速获得到信宿 节点的路由，但存在信号拥塞和路由过程中能量过度消耗的 缺点；按需路由协议可有效节省ＷＳＮ网络的能量和通信资 源，但每次路由建立过程都需要一定规模的泛洪查找，使得 路由建立存在延时。 本文基于生成树理论提出适用于无线传感器网络的基于 异构驱动策略的无线传感器网络路由算法（Ｈｅｔｅｒｏｇｅｎｅｏｕｓ Ｄｒｉｖｅｎ Ｒｏｕｔｉｎｇ Ａｌｇｏｒｉｔｈｍ ｉｎ Ｗｉｒｅｌｅｓｓ Ｓｅｎｓｏｒ Ｎｅｔｗｏｒｋｓ， 点。并且协议所需存储网络路由信息随网络规模的扩大快速 基金项目：教育部博士点基金资助项目（２００３ｏ０５６００７）；博士后科学 基金资助项目（２００６０４００１８） 作者简介：杨研究生；杨挺（１９７９一），男，讲师、博士，主研方向：无线传感 郁，工程师、硕士 Ｅ－ｍａｉｌ：ｙａｎｇｔｉｎｇ＠ｔｊｕ．ｅｄｕ．ｃｎ ＨＤＲＡ—ＷＳＮ）。算法将无线传感器网络的原有单一汇聚节点 Ｓｉｎｋ节点扩充为一组无环连通点集，称为虚拟槽节点以覆盖 全网。当数据汇报时，数据源节点采用按需路由策略可快速 一器网络；孙雨耕，教授、博士生导师；张志东，高级工程师、博士 牧稿日期：２００７一ｌ １－２８ ｌ２～ 增长，可扩展性较差。 按需路由协议无需像表驱动路由协议那样实时地维持每 个节点的路由信息，而只在源节点需要路由的时候才发起路 由：信源节点首先广播路由请求（ＲＲＥＱ）分组，其邻居节点收 半径为 的圆形区域 内节点均一跳可达Ｓｉｎｋ节点，计算 圆域内的感知节点到Ｓｉｎｋ的距离的期望： Ｎ ＇竹ｙ ， ￡（／Ｌ）＝∑ ｐ ＝ ×二 ｉ＝三 ＝１兀 （ ｊ （１） 到广播后传递该ＲＲＥＱ（丢弃重复的ＲＲＥＱ），直到信宿节点为 可简化模型，将 区域内均匀分布的节点简化为分布在 距Ｓｉｎｋ节点２Ｒ／３，宽度为ＡＲ的圆环上，则第１层虚拟槽节 点也位于此圆环上。 、 止，完成路由建立。因此降低了由于路由表维护而对网络带 宽和能量的过度消耗。但路由建立过程中的泛洪查找使得每 次路由建立存在较大延时，并且大规模广播ＲＲＥＱ仍将消耗 一基于第１层虚拟槽节点计算第２层：由于传感器节点通 信半径为Ｒ，则以２Ｒ／３为内径（２Ｒ／３＋Ｒ）为外径的圆环中节点 可与第１层虚拟槽节点连接。第２层节点距离 ／３圆环的距 离的期望是 定程度的资源。 无线传感器网络从网络结构到应用需求均与现有自组织 网络，如Ａｄ Ｈｏｃ，有所不同。从网络结构分析，无线传感器 网络包含传感器节点数目众多，网络规模大，并且要求路由 协议可扩展性强。同时，从传感器网络应用角度分析，ＷＳＮ 是任务感知型网络，传感器节点感知的数据多以汇聚形式上 报Ｓｉｎｋ节点，与ＡｄＨｏｃ网络不同，较少存在点对点的通信。 因此，单纯的表驱动或按需路由方式都无法适应。 本文将融合驱动路由策略和源发起按需驱动路由策略设 计ＶＡＳ路由算法以适用于无线传感器网络。 ３模型建立 传感器网络系统可数学抽象为有向赋权图Ｇ＝（ Ｅ）。其 中， ｛Ｖｓｉｎｋ￣ｖｌ， ２，…，ｖ ｝为网络节点集；Ｅ＝｛ｅｌ，ｅ２，…，ｅ ｝为节点 问通信链路集。每个节点有唯一标识符，ｖ 为网络Ｇ的固 有槽节点， １，２，…， 为感知节点。 中各节点的有效传输 距离＾０相等，则 ＝｛ｅｉＩＤ（ｖｊ，ｖ ）≤Ａ０，ｖ，， ∈Ｖ１。且相邻节点ｖ，， 共享同一无线介质 】。 ＨＤＲＡ—ＷＳＮ通过对网络固有槽节点ｖ 的合理扩充构 建传感器虚拟槽节点Ｇｌ，显然Ｇｌ是Ｇ的一个连通子图。传 感器节点通过虚拟槽节点最终与Ｓｉｎｋ节点实现可靠通信。因 此虚拟槽节点的构建将决定网络划分和路由的有效性，有以 下２个需求： （１）虚拟槽节点尽可能覆盖整个网络：节点通过按需路由 与虚拟槽节点进行通信，因此虚拟槽节点所包含节点个数需 要足够多以保证可通信区域应覆盖所有传感器节点。 （２）虚拟槽节点中包含节点数尽可能少：由于构成虚拟槽 节点的节点需承担更多的数据转发任务，在网络运行中将消 耗更多能量，随着能量耗尽而失效。因此减少虚拟槽节点中 节点个数将有助于提高ＨＤＲＡ—ＷＳＮ运行稳定性。 需求１和需求２之间存在内在联系和矛盾。本文对优化 虚拟槽节点、确定虚拟槽节点中所包含节点数目进行研究。 ４虚拟槽节点的优化选取 问题提出：虚拟槽节点Ｇ一中的元素是网络中相互连通的 节点。故需要寻找适合的中继节点集，其在网络中分布合理， 并支配尽可能多的节点。由分析可知，感知节点与虚拟槽节 点的距离期望和虚拟槽节点中分支个数及分布将决定 ＨＤＲＡ—ＷＳＮ性能。因此，在数学模型上最小化感知节点到虚 拟槽节点距离期望。 ４．１感知节点与虑拟槽节点的距离期望 感知节点与虚拟槽节点的距离期望决定了感知节点探测 虚拟槽节点的难易程度。距离期望越小，说明感知节点到虚 拟槽节点的平均距离越短，越容易探测到虚拟槽节点。 设在圆形区域内随机抛散传感器节点，槽节点位于圆心 的位置。若虚拟槽节点中包含ｎ条分支，则用 条半径将圆 分成等份。 由于网络中所有传感器节点同构，设通信半径２ｏ＝Ｒ，则 ｒ３ｊ｝ Ⅱ（２ｊ ＋ ）（ 一； 一Ⅱ（：：： ）．！．．．．．．．２ｊ．． ．．．Ｒ）一 （２） 则第２层节点可简化为分布在距Ｓｉｎｋ节点２Ｒ／３＋４Ｒ／７＝ ２６Ｒ／２１，宽度为ＡＲ的圆环上，则第２层虚拟槽节点也位于 此圆环上。同理可确定每层虚拟槽节点分布位置。 ４．２每层虚拟槽节点个数选取 当确定每层虚拟槽节点的位置后，需要确定每层所需虚 拟槽节点的个数，保证虚拟槽节点具有更高的分散性。 由虚拟槽节点结构可知，其是以Ｓｉｎｋ节点为根的原网络 图的生成树子图。因此，尽量避免同层节点为尽量减少虚拟 槽节点中节点的个数。 对于第１层被选虚拟槽节点，若任选取该圆环上一点作 为下 跳节点，其与Ｓｉｎｋ同构通信半径为Ｒ，则该点的通信 范围内覆盖的圆环弧度为 １ １ （ Ｒ） ＋（三月） 一Ｒ 一２ｘＡｒｃＣｏｓ（ —＿＝ Ｌ 一） （３） ２ｘ兰Ｒ×兰Ｒ ３ ３ 计算得该弧长为３．３９，占整个圆环的比例为５４％。而在 虚拟槽节点的各个分支中，同层节点问无需相邻，故两节点 间应该在圆弧上相距大于周长的２７％，则需要圆环上存在ｋ 个相距为圆周长的２７％的点，ｋｍａｘ＝３，虚拟槽节点第１层分 支数为３。 同理，第２层槽节点个数计算公式为 １ ＋ １。一 ：２ｘＡｒｃＣｏｓ（ ）：１．６６２ ９ （４） ２× Ｒ× Ｒ ２１ ２ｌ 它占整个圆环的比重为１．６６２ ９／２ｘ＝２６．５％。求得０．２６５￣ （ｎ—１）０．５ Ｘ０．２６５＞１的最小整数解为７。所以，第２层骨干网需 要７个中继节点。 以此类推，则各层骨干节点选取如表１所示。 表１各层骨干节点的选取 由上述理论分析可知，分支的形成，即中继节点的选取， 总是优先选取与自己距离远的邻居。中继节点的个数仅仅与 每个节点的通信半径和节点分布区域的面积有关而与节点总 数目没有必然联系，从而保证ＨＤＲＡ—ＷＳＮ算法不会有过度 的节点参与组建虚拟槽节点。 １３— ５虚拟槽节点的构建 上文对虚拟槽节点的优化选取进行了理论分析，但这种 应用整个网络拓扑信息并进行集总式的理论计算在ＷＳＮ实 际网络应用中是难以实现的。在实际ＷＳＮ网络运行中，各 个传感器网络节点仅获知周围邻居节点信息，自组织地完成 感知和传送任务。因此，基于虚拟槽节点的构建原理，设计 “两跳邻居”算法构建虚拟槽节点。 算法从槽节点开始，向外进行ｋ条射线并行探测。当某 节点ｖ 发送网络结构探测包的时候，他的邻居中距离他最远 的节点ｖｊ最有可能成为下一跳节点，随后ｖ，继续广播网络结 构探测包，在他的邻居中选择一个距离自己最远的节点 作 为下一跳节点，同时被选中的节点 应保证不是父亲节点的 上级节点ｖ 的邻居。两跳邻居算法伪码如下所示： Ｓｕｐｐｏｓｅ Ｖｉ，Ｖｊ∈ＶＳ，ｖｊ．ｆａｔｈｅｒ＝Ｖｉ Ｉｆ（ｖｋ ｉｓ ｖｊ’Ｓ ｎｅｉｇｈｂｏｒ＆＆ ＩＶｋ Ｖｊ Ｉ＝ｍａｘ｛［ｖ Ｉ，Ｖ ｉｓ Ｖｊ’Ｓ ｎｅｉｇｈｂｏｒ｝＆＆ Ｖｋ ｉｓ ｎｏｔ Ｖｉ’Ｓ ｎｅｉｇｈｂｏｒ） Ｔｈｅｎ ｆｌａｇ Ｖｋ∈ＶＳ； 在ＨＤＲＡ—ＷＳＮ算法执行中，每层虚拟节点向外层延伸 时所需分支个数ｋ可由表１中第４列所计算的比例确定，以 更符合理论分析中确定的各层虚拟槽节点优化个数。 当某节点无法找到符合条件的下一跳节点，或者达到规 定的最大跳数，一条虚拟槽节点的分支即建立完成。 ６仿真试验 本文通过仿真试验以论证ＨＤＲＡ—ＷＳＮ有效性：（１）在不 同仿真环境生成虚拟槽节点；（２）计算虚拟槽节点中分支数和 中继节点数量；（３）分析网络运行数据包总量，并与ＬＥＡＣＨ 算法比较。 在１００ｍ×１００ｍ监测范围内随机抛洒同构节点，通信半 径２５ ｍ。仿真节点数由５０增加到２００个ＨＤＲＡ—ＷＳＮ的网络 按需路由情况，如图１、图２所示。 图１ ５０节点网络拓扑图 固２ ２００节点网络拓扑图 一１４一 由图可知，虚拟槽节点生成的各层分支数都与理论计算 相吻合，且成员节点均可在两跳内找到虚拟槽节点（其中一跳 成功概率ｐ＞７６％）。 由分析可知，虚拟槽节点的中继节点总数将影响整个网 络的能耗。分析抛洒节点个数与生成虚拟槽节点中节点个数 关系，如图３所示。图中在监测区域面积和节点通信半径不 变的情况下，虚拟槽节点数不随抛洒节点变化，保持恒定， 仅和节点通信半径以及抛散区域的面积有关。 籁 《 缸 魏 导 节点个数 图３节点总数与中筮节点数关系曲线 最后，对ＨＤＲＡ．ＷＳＮ和ＬＥＡＣＨ算法进行仿真，比较 两算法进行一次组网所需数据总量。在此忽略因重传而所需 的额外数据。由图４可得，采用ＨＤＲＡ—ＷＳＮ算法，网络中 传输的数据包数量随节点数呈线性增长，增长速率较ＬＥＡＣＨ 平缓。这是因为算法仅需构建虚拟槽节点便完成组网过程， 而无需全网节点参与。与之相比，ＬＥＡＣＨ算法每轮选取簇头 过程都需要全网节点参与，因此ＨＤＲＡ—ＷＳＮ算法有效降低 了控制类数据包转发数量，从而节省节点转发能量，延长网 络生存周期。 、 咖ｉ 珀 皿 辎 图４节点数与传输数据包总量关系曲线 ７结束语 本文提出一种网络划分算法ＨＤＲＡ—ＷＳＮ，该模型把单一 的槽节点扩充为一个连通的点集合一一虚拟槽节点。当传感 器节点进行数据汇报时，源节点通过按需路由策略经虚拟槽 节点与槽节点实现通信，从而有效控制网络数据包的转发数 量，降低网络能耗，延长网络生存周期。 参考文献 【１１ Ａｋｙｉｌｄｉｚ Ｉ Ｓａｎｋａｒａｓｕｂｒａｍａｎｉａｍ Ｙ，Ｃａｙｉｒｃｉ Ｅ．Ｗｉｒｅｌｅｓｓ Ｓｅｎｓｏｒ Ｎｅｔｗｏｒｋｓ：Ａ Ｓｕｒｖｅｙ［Ｊ］Ｃｏｍｐｕｔｅｒ Ｎｅｔｗｏｒｋｓ，２００２，３８（４）：３９３—４２２． ［２］任丰原，黄海宁，林 闯．无线传感器网…．软件学报，２００３， １４（７）：１２８２—１２９１． （下转第４３页） ４．３最筒决策规则获取 根据定义７和定理４，综合属性值约筒思想，结合决策 表矩阵与决策矩阵可以找到一种直接从决策表中获取所有最 ｆｘ４，ａ５） ｛ｘ４，ｘ５１ （ｘ３） ｛ｘ３，ｘ４） ｛ｘ４） （ｘ３｝ ｛吐 ） ｛ｘ３，ｘ４】 ｛扎砣） （ｘ３｝ （ 】 ¨ 砣 Ｉ譬 如 胛 简决策规则的方法。分为２类情况：（１）决策矩阵空集元素对 ｛ｘＬｘ２，ｘ５） ｆ五删 ｆ扎ｘＺｘ４｝ ｘＺｘ５，ｘ６） ｛ｘｌ｝ 应单属性决策规则，即Ａ ＝ ，可得到最筒决策规则 ａｉ，＿÷ｄｉ。根据定理４，以表１第２行为例可以得到单属性规 ｛ ） 皿ｎｘ４］ ｛ ） ｛札皿船， ｝ ｍ正ｎ觯｝ 则ｂ２Ｖｃ３ ｌ。（２）决策矩阵非空集元素，根据最少元素交集 为空集的原则获取最简规则。最少元素交集为空是指元素集 合中减少任何一个元素，交集都不为空。根据它们对应的决 策表矩阵获取相应最简规则。例如，决策矩阵第２行ｆ １， ３｝， 则有 Ｓｔｅｐ３根据空集原则获取规则。以决策矩阵第１行为例， Ｏ Ｏ Ｏ Ｏ ０ Ｏ ２ ＡＩｌ：｛ｘ４，ｘＳ｝，Ａ２＝｛ｘ３），Ａｔ３：［ｘ３，ｘ４｝，ＡＩ４＝｛ ４） ｛ ４】，ｉ ４）。因为只有ｆ １， ３）ｎ｛ｘ４｝：研｛ｘｌ，ｘ３）ｎ｛ ４｝＝ ，所 以得到的约简规则为ａｌＡｂｌ ｄ２和ａｌ ｃ２＿÷ｄ２。集合运算 在同行元素之间进行。 其中没有空集，可知最少元素交集是空集的组合为 Ａｌｌｎ＾２＝Ｊ４Ｉ２ ｒ、ＡＩ４＝ 对应的最筒规则为 （ａｌＡｂ０）ｖ（ｂ０Ａｄ１）— ４．４算法描述 根据上述分析，可以得到一个决策表最简规则获取算法， 算法描述如下： Ｓｔｅｐｌ求决策表矩阵。 以此类推，可以得到全部最简决策规则集为 （ａｌＡｔ，０）ｖ（ｂ０＾ｄ１）Ｖ（ａｌＡｄ０） Ｐ１ ａ０Ｖ（ｂｌＡｄ１１ ０．ａ２Ｖｂ２Ｖｃ２Ｖｄ２ Ｐ２ Ｓｔｅｐ２求决策矩阵。将决策表矩阵中的元素换成相应对 象集合，即非同决策类的等价类。 Ｓｔｅｐ３根据决策矩阵提取决策规则，一般先提取单条件 属性决策规则，即决策矩阵中空集对应的规则，然后查找其 他最少元素交集为空的对应组合，以获取其他规则。 Ｓｔｅｐ４删除重复规则，合并同类规则，输出结果。 采用其他方法可以得到类似结果。 ５．２算法分析 本算法是建立在定义７所形成规则基础上的一种最筒规 则获取方法。本文算法比原有方法简单，整个过程具有良好 的理论基础。其主要时间开销集中在找到最少元素交集为空 集的元素集合，而此过程与属性个数及决策矩阵中的空集个 数有关。若决策矩阵是一个稀疏矩阵，则本文方法可以取得 很好的效果。在实际应用中，一般情况下最简规则的前件一 ５实例说明与算法分析 ５．１实例说明 表２描述了一个实例决策表，其中，ａ，ｂ，Ｃ和ｄ是条件属 性；ｅ是决策属性。 表２实倒决策表 般含项不多，因此，寻找最少元素交集为空的元素集合所需 时间很少，使用本文算法可以得到较理想的结果。 ６结束语 粗糙集理论与应用研究是目前数据挖掘和机器学习等领 域的重要工作之一，近年来取得了许多重要成果，但属性值 Ｏ 约简算法的相关研究很少。本文以属性值约简思想为基础， 建立决策矩阵，根据决策表矩阵和决策矩阵之间的对应关系 直接获取最简规则，减小了时间复杂度。 Ｏ ０ 参考文献 ［１］Ｐａｗｌａｋ Ｚ．Ｒｏｕｇｈ Ｓｅｔｓ［Ｊ］．Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｊｏｕｎａｌ ｏｆ Ｉｎｆｏｒｍａｔｉｏｎ ａｎｄ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ，１９８２，１ １（５）：３４１—３５６． ［２］Ｚｄｚｉｓｌａｗ Ｐ．Ｒｏｕｇｈ Ｓｅｔｓ ａｎｄ Ｉｎｔｅｌｌｉｇｅｎｔ Ｄａｔａ Ａｎａｌｙｓｉｓ［Ｊ］．Ｉｎｆｏｒｍａｔｉｏｎ Ｓｃｉｅｎｃｅｓ，２００２，１４７（１，４）：１—１２． ［３】张文修，梁２００３． 怡．信息系统与知识发现［Ｍ］．北京：科学出版社， （４】王国胤．Ｒｏｕｇｈ集理论与知识获取【Ｍ】．西安：西安交通大学出版 寻找表２描述的实例决策表全部最筒规则的步骤如下 Ｓｔｅｐ１ 求决策表矩阵。 社，２００１． ［５］苗夺谦，胡桂荣．知识约简的一种启发式算法【Ｊ１ｌ计算机研究与 发展，ｌ９９９，３６（６）：６８１－６８４． Ｓｔｅｐ２构造相应的决策矩阵，即 （上接第ｌ４页） ［３】孙雨耕，张静，孙永进，等．无线自组传感器网络［Ｊ】．传感技 栋，等．无线传感器网络适应ＱｏＳ机制的 ［５］杨挺，孙雨耕，杨郁．无线传感器网络中一种节省资源的快 术学报，２００４，２２（２）：３３１－３３５． 【４］王毅，张德运，张速重路由算法［Ｊ１．传感技术学报，２００５，１８（３）：４４５—４４８． 【６］Ｂｏｏｌｏｂａｓ Ｂ．Ｍｏｄｅｒｎ Ｇｒａｐｈ Ｔｈｅｏｒｙ［Ｍ］．Ｎｅｗ Ｙｏｒｋ：Ｓｐｒｉｎｇｅｒ－Ｖｅｒｌａｇ， 网络模型【Ｊ］．计算机工程，２００７，３３（７）：９６—９８． ２００１．