３年９月 第２卷第 期 ２０１网络新媒体技术 Ｖ０Ｌ Ｓ２ Ｎｏ．５ ｅｐ．２０１３ 无线传感器网络分簇路由协议综述 徐世武 王 平２ 施文灶２ 苏国栋２ （ 福建师范大学协和学院信息技术系福州３５０１０８ 福州３５０００７） 福建师范大学 医学光电科学与技术教育部重点实验室摘要：无线传感器网络不同于传统的无线通信技术，传统的路由协议无法直接运用于无线传感器网络中，而分簇路由协议拓 扑结构简单，簇内成员节点无需维护大量的路由表，簇型的路由结构有利于数据的传输与融合处理，符合无线传感器网络以 数据为中心，因此分簇路由协议成了国内外关于无线传感器网络路由协议研究的重点。本文详细分析了典型的分簇路由协 议，并对这些协议进行了比较与分析，最后探讨了未来可能的发展趋势。 关键词：无线传感器网络。分簇路由协议，簇首的选举，数据的传输与融合 Ｔｈｅ Ｒｅｖｉｅｗ ｏｆ Ｃｌｕｓｔｅｒ－－ｂａｓｅｄ Ｒｏｕｔｉｎｇ Ａｌｇｏｒｉｔｈｍｓ ｆｏｒ Ｗｉｒｅｌｅｓｓ Ｓｅｎｓｏｒ Ｎｅｔｗｏｒｋｓ ＸＵ Ｓｈｉｗｕ ，ＷＡＮＧ Ｐｉｎｇ ，ＳＨＩ Ｗｅｎｚａｏ ，ＳＵ Ｇｕｏｄｏｎｇ （ Ｃｏｎｃｏｒｄ Ｃｏｌｌｅｇｅ Ｄｅｐａｒｔｍｅｎｔ ｏｆ ｉｎｆｏｒｍａｔｉｏｎ ｔｅｃｈｎｏｌｏｇｙ，Ｆｕｊｉａｎ Ｎｏｒｍａｌ Ｕｎｉｖｅｒｓｉｔｙ，Ｆｕｚｈｏｕ ３５０１０８，Ｃｈｉｎａ， Ｋｅｙ Ｌａｂｏｒａｔｏｒｙ ｏｆ ＯｐｔｏＥｌｅｃｔｒｏｎｉｃ Ｓｃｉｅｎｃｅ ａｎｄ Ｔｅｃｈｎｏｌｏｇｙ ｆｏｒ Ｍｅｄｉｃｉｎｅ ｏｆ Ｍｉｎｉｓｔｒｙ ｏｆ Ｅｄｕｃａｔｉｏｎ， Ｆｕｊｉａｎ Ｎｏｍａｌｒ Ｕｎｉｖｅｒｓｉｔｙ，Ｆｕｚｈｏｕ ３５０００７，Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｗｉｒｅｌｅｓｓ Ｓｅｎｓｏｒ Ｎｅｔｗｏｒｋｓ（ＷＳＮｓ）ｉｓ ｄｉｆｆｅｒｅｎｔ ｆｒｏｍ ｔｒａｄｉｔｉｏｎａｌ ｗｉｒｅｌｅｓｓ ｃｏｍｍｕｎｉｃａｔｉｏｎ ｔｅｃｈｎｏｌｏｇｙ，ｔｒａｄｉｔｉｏｎａｌ ｒｏｕｔｉｎｇ ｐｒｏｔｏ— ｃｏｌｓ Ｃａｎ ｎｏｔ ｂｅ ｄｉｒｅｃｔｌｙ ａｐｐｌｉｅｄ ｔｏ ＷＳＮｓ．Ｔｈｅ ｔｏｐｏｌｏｇｙ ｏｆ ｃｌｕｓｔｅｒ—ｂａｓｅｄ ｒｏｕｔｉｎｇ ｐｒｏｔｏｃｏｌ ｉｓ ｓｉｍｐｌｅ，ｃｌｕｓｔｅｒｉｎｇ ｎｏｄｅｓ ｄｏ ｎｏｔ ｎｅｅｄ ｔｏ ｍａｉｎｔａｉｎ ｌａｒｇｅ ｒｏｕｔｉｎｇ ｔａｂｌｅｓ，ｃｌｕｓｔｅｒｉｎｇ ｓｔｒｕｃｔｕｒｅ ｃｏｎｄｕｃｉｖｅ ｔｏ ｔｈｅ ｔｒａｎｓｆｅｒ ａｎｄ ｉｎｔｅｇｒａｔｉｏｎ ｏｆ ｄａｔａ．ＷＳＮ ｉｓ ｄａｔａ—ｃｅｎｔｒｉｃ ｎｅｔｗｏｒｋ，ＳＯ ｃｌｕｓｔｅｒ—ｂａｓｅｄ ｒｏｕｔｉｎｇ ｐｒｏｔｏｃｏｌｓ ｈａｖｅ ｂｅｅｎ ａｎ ｉｍｐｏｒｔａｎｔ ｒｅｓｅａｒｃｈ ｉｎ ＷＳＮｓ．Ｉｎ ｔｈｉｓ ｐａｐｅｒ，ｃｌｕｓｔｅｒｉｎｇ ａｌｇｏｒｉｔｈｍｓ ｆｏｒ ＷＳＮｓ ａｘｅ ａｎａｌｙｚｅｄ， ｗｅ ａｌｓｏ ｃｏｍｐａｒｅ ｔｈｅｓｅ ｃｌｕｓｔｅｒ—ｂａｓｅｄ ｒｏｕｔｉｎｇ ｐｒｏｔｏｃｏｌｓ．Ｆｉｎａｌｌｙ，ｗｅ ｐｒｏｐｏｓｅｄ ｔｈｅ ｆｕｔｕｒｅ ｒｅｓｅａｒｃｈ ｄｉｒｅｃｔｉｏｎｓ． Ｋｅｙｗｏｒｄｓ：Ｗｉｒｅｌｅｓｓ ｓｅｎｓｏｒ ｎｅｔｗｏｒｋ，Ｃｌｕｓｔｅｒ—ｂａｓｅｄ ｒｏｕｔｉｎｇ ｐｒｏｔｏｃｏｌ，Ｃｌｕｓｔｅｒ ｈｅａｄ ｅｌｅｃｔｉｏｎ，Ｄａｔａ ｔｒａｎｓｍｉｓｓｉｏｎ ａｎｄ ｉｎｔｅｇｒａｔｉｏｎ 无线传感器网络集成了传感器技术、计算机技术和通信技术等，在军事、环境、健康、家庭、商业等许多方 面有着巨大的潜在应用前景。然而节点大都需要在无人看管、不更换电池或者几乎不可能更换电池的条件 下长时间的工作，因此高效、低功耗路由算法在无线传感器网络中就显得十分重要…。目前对于无线传感 器网络的路由协议大体可以分为平面路由协议与分簇路由协议，平面路由协议中的节点地位平等，管理简 单，然而其网络中各个节点的能耗极其不均匀，会导致网络过早的瘫痪，如直接传送协议，每个节点直接与基 站通信，容易导致距基站较远的节点过早死亡，而且不利于大规模网络的构建，还有传统的最小跳距或最小 跳数平面路由协议，距基站越少跳数的节点，不但自身要采集数据，还要存储转发下一跳节点传输过来的数 据，虽然减轻了远距离节点的负担，但会导致越靠近基站的节点越容易死亡。而分簇路由协议，根据需要将 本文于２０１２—１０—０８收到。 ｝基金项目：福建省自然科学基金资助项目编号（２ｏｏ８ｊｏ２ １）福建省教育厅项目编号ＪＢ０９０７１、ＪＢ０９０７６。 ２ 网络新媒体技术 ２０１３矩 整个网络随机动态的划分成不同规模的簇，每个簇拥有一个簇首节点以及多个簇内成员节点，且每个簇可以 根据相应的协议对簇内的数据进行融合处理，簇首节点将融合后的数据传输给基站，减少了大量的数据传 输，簇内节点的功能比较简单，无需像簇首节点那样维护大量的路由表，无需工作的节点可以处于休眠状态， 协议运行一段时间后再次更换簇首节点，通过这样的方式均衡整个网络中节点的能耗，相比于平面路由协 议，分簇路由协议拓扑结构更易管理，拓展性能好，更加适合无线传感器网络的发展需求。 １ 无线传感器网络分簇路由协议设计常见问题 （１）网络节点的动态性。无线传感器网络分簇路由协议大体包括三类节点，基站，簇首节点以及簇内成 员节点，通常情况下设计的路由协议都是假设节点是静态的，如温室环境监测等，而无线传感器网络在一些 运用场合节点存在移动性，如目标追踪等，静态的拓扑结构相对较简单，而动态的拓扑结构相对较复杂，因此 必须根据实际需要设计相应的路由协议。 （２）网络节点的部署问题。无线传感器网络不同于其他的无线通信协议，大部分情况下，节点的位置事 先是不知道的，整个网络节点分布不均匀，因此有效合理的选择簇首节点，簇首节点的个数以及位置对均衡 整个网络的功耗起到决定性的作用。 （３）网络节点的构造问题。早期的无线传感器网络路由协议假设节点是同构的，即每个节点拥有相同 的能量，相同的存储、处理能力，相同的通信能力等。然而即使刚开始节点同构，簇首节点以及远距离节点能 量消耗相对较快，一段时间后也会出现异构现象，而且在网络布置一些高能量节点，以及存储能力较强的节 点可以有效的延长网络的生存期。在一些场合，各个节点所需要采集的信息也可能不一样，如光、湿度、温度 以及有害气体检测等，根据实际需要每个节点采集数据的速率、周期可能存在不一致等，因此设计异构的路 由协议显得非常重要。 （４）网络节点的数据处理与融合问题。无线传感器网络节点数据的采集可以是周期性的采集，也可以 是事件驱动性，有事件驱动的情况下采集数据，否则处于休眠状态。无线传感器网络中布置着大量的节点， 如果每个节点对采集到的数据不进行处理而直接传输给上一级节点，大量的数据在无线信道中传输就会出 现数据碰撞、冲突等，因此节点有效的处理数据，可以减少大量的冗余数据，相似性数据，提高带宽的利用率 以及减少能量的消耗。 （５）网络节点的容错能力。无线传感器网络节点可能布置在恶劣的环境中，以及可能存在一些自然的 破坏以及人为的攻击等，也可能存在部分节点硬件的故障以及能量的耗尽等，因此在出现这些情况下，就要 求路由协议具有一定的重构性以及节点具有一定的数据容错能力。 ２无线传感器网络典型的分簇路由协议 无线传感器网络分簇路由协议的形成大体分成两个阶段，第一阶段为簇首节点的确定，簇型结构的形 成，第二阶段为稳定阶段，即数据的传输与融合阶段。 ２．１簇首节点的选择与簇型结构的构建 （１）ＬＥＡＣＨ分簇路由算法。为了提高整个网络的的生存时间，将功耗均衡的分配到网络中的每个节 点，麻省理工学院的Ｗｅｎｄｉ Ｒａｂｉｎｅｒ Ｈｅｉｎｚｅｌｍａｎ等人提出了一种低功耗的自适应路由协议，ＬＥＡＣＨ协议（Ｌｏｗ —Ｅｎｅｒｇｙ Ａｄａｐｔｉｖｅ Ｃｌｕｓｔｅｒｉｎｇ Ｈｉｅｒａｒｃｈｙ）Ｅ ２］。在ＬＥＡＣＨ协议中，每个传感节点都有机会充当簇头节点，簇头 节点的选择主要依据网络中所需要的簇头节点个数与到目前为止每个节点已经充当簇头节点的次数来判定 的。网络中每个节点在０到１之间随机选择一个数，如果选择的数小于规定阀值Ｔ（ｎ），则该节点就充当为 簇首节点。ＬＥＡＣＨ算法通过设置Ｔ（１１）值，以保证每个节点在每回合内都有机会充当一次簇头节点，从而平 衡了节点的能量消耗。簇首节点确定后，簇内节点选择接收信号强度最强的簇首，加入该簇，ＬＥＡＣＨ协议的 作者根据ＬＥＡＣＨ算法中每轮产生的簇头数与位置的随机性，提出ＬＥＡＣＨ—Ｃ算法 ，该协议是ＬＥＡＣＨ算 ５期 徐世武等：无线传感器网络分簇路由协议综述 ３ 法的集中式控制版本，采用模拟退火算法获得更优的簇头选举策略，ＬＥＡＣＨ—Ｃ算法可以把每个节点的地理 位置以及节点当前的能量报告给基站。基站把所有节点的能量取平均，当网络中某些节点的能量低于平均 值时，将不能成为候选簇头节点，从而更加有效的解决了低能量节点成为簇头节点的概率。 （２）基于模糊逻辑学的分簇路由协议。文献［４］采用模糊逻辑学的原理来选择簇首节点，采用了三个参 数来判断节点成为簇首的概率，即节点的剩余能量，分成低、中、高三个等级，节点的密集性，分成低、中、高三 个等级，节点距基站的距离，分成近、适中、远三个等级。模糊逻辑学根据三个参数，每个参数拥有三个等级， 最终输出２７种结果，即根据２７个等级来判断节点成为簇首的概率。例如一个节点的能量等级高，密集性 高，距离近，则该节点成为簇首的概率最大，通过实验表明，相比于ＬＥＡＣＨ协议，该协议有效的延长了节点 的生存时间。然而在该文献中为了选择簇首，基站必须收集每个节点的位置与距离，造成一定的能量开销， 为了克服这个缺陷，文献［５］提出了ＣＨＥＦ协议，ＣＨＥＦ协议由每个节点自身判断是否成为簇首，而不是由基 站决定的，首先每个节点在（０，１）之间随机产生一个值，当该值小于指定概率时，该节点采用模糊理论计算 自己成为簇首的几率，ＣＨＥＦ采用两个模糊变量，即节点的剩余能量，该节点在ｒ距离范围内一跳节点距离 的总和，ｒ为簇首节点在整个区域中的平均通信距离。通过两个参数，剩余能量采用低、适中、高三个变量， 距离的总和采用近、适中、远三个变量，通过模糊理论后输出９种等级结果。通过这样的方式选择节点剩余 能量最多，局部最优化的节点成为簇首，相比于ＬＥＡＣＨ协议，ＣＨＥＦ有效的延长了２２．７％的生存时间。 （３）基于遗传学的分簇路由协议。文献［６］中采用遗传学选择簇首节点，每个节点代表一个染色体位， 簇首用１表示，成员节点用０表示，适应度函数包含了５个参数，①成员节点直接与基站通信的距离和；②成 员节点与对应的簇首距离总和加上该簇首节点与基站的距离；③簇距离的标准差；④能量消耗，包括，成员节 点传输数据到对应簇首的能量消耗，簇首接收成员节点发送过来数据的能量消耗，以及簇首融合成员数据传 输到基站的能量消耗；⑤网络中节点传输数据量的大小。通过适应度函数不断调整最优的簇首集，均衡簇规 模的大小，以及网络能量消耗的最小化。文献［７］中也采用遗传学选择最优的数据聚合点，并结合梯度算法 优化结果，目标在于使整个网络的生命期最大化。 （４）基于博弈论的分簇路由协议。博弈论一种处理竞争与合作问题的数学决策方法，博弈论中主要体 现决策人，局中人，策略等几个因素，无线传感器网络中节点为了保留能量可以自私的拒绝存储与转发下级 节点的数据，因此，节点一旦加入数据的存储与转发就会消耗他们的部分能量，减少其生存时间，效用函数可 以是通过不合作的方式来到达存储能量，因此博弈论非常适用于无线传感器网络的能量效应路由协议与数 据传输、融合机制中 Ｊ。文献［１０］中基于贝叶斯博弈论提出ＢＧＣＲＡ分簇路由协议，该协议采用异构网络， 网络中拥有两类节点，能量高的与能量低的，采用贝叶斯博弈论让能量高的竞选成为簇首节点，该协议假设 邻居节点服从泊松分布，簇首节点竞选效用函数主要与节点初始能量度量，路径能量损耗有关，即节点的初 始能量越高，与邻居节点的通信能量越低，该节点成为簇首的概率越大。该协议作者通过实验表明，相比于 ＬＥＡＣＨ协议，该协议在簇首分布的均匀性以及节点的生存时间等都优于ＬＥＡＣＨ协议。 （５）异构多级网络分簇路由协议。根据整个网络中节点初始能量的不同，ＧＥＯＲＧＩＯＳ ＳＭＡＲＡＧＤＡＫＩＳ 等人提出了一种异构的无线传感器网络ＳＥＰ算法… ，ＳＥＰ采用与ＬＥＡＣＨ类似的分簇方法，不过ＳＥＰ协议 将整个网络分成两类节点，能量较高的节点称为高能量节点，能量低的称为正常节点，高能量节点与正常节 点分别采用各自的簇首选择阈值，两类节点成为簇首的概率不同，高能量节点成为簇首节点的机会大于低能 量节点。高能量节点成为簇首每回合的轮数低于正常节点，即高能量节点成为簇首的概率、频率高于低能量 节点，相较于ＬＥＡＣＨ算法，在异构网络中，ＳＥＰ均衡了两类节点的生存时间，从而充分利用了整个网络的功 耗。ＳＥＰ协议虽然考虑了节点初始能量两级的异构性，但不适合更多级能量的异构性，文献［１２］中针对节 点初始能量不同，即正常节点，高能量节点，超级能量节点，提出了一种的三级异构ＥＥＨＣ分簇协议，三级节 点采用各自的簇首的选择阈值，三级节点成为簇首的概率不同，即超级节点成为簇首的概率与频率最高， ＥＥＨＣ可以平衡三级节点的生存时间。在文献［１３］中，作者提出了一种针对节点初始能量多级的异构网络 ４ 网络新媒体技术 ２０１３矩 ＤＥＥＣ协议，在选择簇首节点时，同时考虑了节点的剩余能量，即节点成为簇首的轮转周期随节点的初始能 量与剩余能量不同而变化。拥有更高的初始能量与剩余能量的节点成为簇首的概率与频率更大，剩余能量 采用估算的方式获得。实验表明，在异构的网络中，采用多级的分簇协议可以有效的均衡网络各类节点的生 存时间。 （６）混合能量与通信代价的ＨＥＥＤ分簇协议。文献［１４］中提出结合节点的剩余能量与通信代价的 ＨＥＥＤ分簇路由协议，该协议在选取簇首节点的时候只要依据两个参数，第一参数为节点的剩余能量，根据 节点的剩余能量情况选举初始的簇首节点，节点能否成为最终的簇首依据节点竞选簇首过程中的迭代次数， 即节点剩余能量越高的节点在簇首竞选过程中的迭代次数越少，越容易竞选成为簇首。第二参数为簇内通 信代价，用来判断重叠区域节点，即在多个簇首节点通信范围内的节点归属问题，判断的依据为簇内平均可 达能量，即簇内节点到达簇首节点的平均能量消耗。相比于ＬＥＡＣＨ协议，ＨＥＥＤ协议分簇更均匀，簇首选举 速度更快，节点能耗更均匀。 （７）ＥＥＰＡ分簇协议。文献［１５］针对大规模的无线传感器网络提出一种新的能量效应动态分簇路由协 议，ＥＥＰＡ协议，通过接收到邻居节点的信号功率，每个节点实时统计活动节点数量以及自身成为簇首的概 率。该协议具体的实现方法，首先统计网络中活动节点数，设置隔离度，隔离度越高代表节点越孤立，每个节 点测量在通信范围内所有邻居节点的信号功率和，每个节点估算网络中活动节点数量，每个节点可以根据阈 值来判断是否更新簇首选择处理过程，如果最后一个簇更新超过预先设置值，激活簇更新进程。每个节点更 新自身成为簇首的概率，ＥＥＰＡ通过动态的调整簇首总量与簇内成员集，将能量较均衡的消耗在每个节点 上，延长了网络的工作寿命，且每个节点完全自主的进行簇的更新过程。当节点数为２０００时，该协议的能量 消耗是ＨＥＥＤ的二分之一，是ＬＥＡＣＨ的三分之一。 （８）Ｈａｕｓｄｏｆｆｆ分簇路由协议。文献［１６］中提出了Ｈａｕｓｄｏｆｆｆ分簇路由协议，首先结合节点的位置，通信 效率以及网络的链接性采用Ｈａｕｓｄｏｆｆｆ测距技术 将整个网络分成不同的簇，其次结合节点的剩余能量与 节点邻居的密集程度，采用贪婪算法选举簇首节点，最后簇首节点收集簇内节点采集的数据、融合后采用 Ｄ￣ｋｓｔｒａ最短路由优先算法将数据传输给基站，如果存在多条路径的话，采用节点剩余能量较多的路径传输。 相比于ＨＥＥＤ协议，Ｈａｕｓｄｏｆｆｆ分簇过程能量开销更小。 （９）ＴＡＢＵ—ＲＣＣ分簇路由协议。文献［１８］中提出ＴＡＢＵ—ＲＣＣ分簇协议，该协议考虑了事件监测区域 节点的覆盖问题与网络的连通性问题。在每个事件区域内都有足够有效的节点采集数据，簇首节点之间可 以构成一个有效的生成树，保证整个网络节点之间的连通性。为了平衡每个节点的能耗，选择簇首时，该协 议定义了一个节点线性组合函数分值，该函数的分值主要取决于两个因素，节点的剩余能量与节点所处状态 （激活，休眠，簇首）所需要消耗的能量，通过该函数来平衡网络中节点的能耗，当然该函数也有一些前提约 束条件，必须保证每个事件监测区域至少有一个有效节点可采集数据，每个有效的传感节点在通信范围内至 少有一个簇首节点，每个簇成员节点具有一定的上限，所有簇首节点之间可构成一个有效的生成树，保证整 个网络的连通性。 （１０）ＫＯＣＡ重叠式分簇路由协议。文献［１９］中提出了重叠式分簇路由协议，ＫＯＣＡ协议，通常的分簇协 议中，一个成员节点只属于一个簇首，而ＫＯＣＡ协议定义了三类节点，簇首节点，正常节点，边界节点，正常 节点只属于一个簇首节点的成员节点，而边界节点可以成为多个簇首节点的成员节点。ＫＯＣＡ采用分布式 协议，初始情况下，每个节点都以概率Ｐ竞选成为簇首。竞选成为簇首的节点广播告知周围的邻居节点，广 播消息中包含发送节点的ＩＤ号，簇首节点的ＩＤ号，允许成员节点加入该簇首节点的最大跳数Ｋ，如果一个 节点在Ｋ跳内无法寻找一个簇首节点，则该节点就成为簇首，每个成员节点也维护一个信息表，该表包含了 该成员节点归属的簇首ＩＤ，该成员节点的ＩＤ，到达该簇首的跳数ＨＣ，如果成员节点接收到新的簇首发送的 消息，选择ＨＣ小的加入该簇，如果一个节点同时拥有几个簇首节点，那说明该节点为多个簇的交集、边界节 点，否则为正常成员节点，ＫＯＣＡ协议得到平均簇规模大小Ｅ（Ｎ ）＝ｄｋ ，各个簇的平均重叠度ＡＯＤ＝ｄｋ ／４， ５期 徐世武等：无线传感器网络分簇路由协议综述 ５ 簇首节点的通信开销Ｍ 。：Ｏ（ｄｋ ），成员节点的通信开销Ｍ＿ＩＲＥｏ＝Ｏ（ｄｋ ），式中ｄ表示每个节点的邻居 集，ｋ与簇首节点的通信距离有关。通过实验表明ＫＯＣＡ协议能够保证整个网络的连通性，均衡每个簇规模 的大小。 （１ １）非均匀分簇路由协议。大部分作者的研究都考虑均衡每个簇规模的大小，以均衡每个簇的能耗， 但是并没有考虑簇首节点的能耗问题，通常情况下，靠近基站的簇首节点不但要处理本簇节点收集过来的数 据，还有处理下一级簇首节点的数据，因此功耗较大，为了均衡每个簇首节点的能耗，文献［２Ｏ］中首次针对 多跳路由协议中的“热区”问题，提出了ＵＣＳ非均衡分簇协议，该协议采用不均衡分簇的方式，靠近基站的簇 规模相对较小，减轻靠近基站的簇首节点处理本簇数据的能耗，让其拥有更多的剩余能量处理下一级簇传输 过来的数据。该协议采用的是以基站为圆心的两层同心圆结构，即第一层簇首位于以Ｒ１为半径的圆内，第 二层簇首位于以Ｒ１到Ｒ２区域内，第一层内的簇首不但要处理本簇的数据，还要处理转发下一级簇首转发 的数据。为了均衡两级簇首节点的能耗，因此需要通过减小第一层的簇成员数目来降低其在簇内处理中消 耗的能量。文献［２１］中也提出了ＵＣＲ非均匀分簇协议，该协议假设传感节点布置在一个方形区域内，基站 位于该区域外，首先每个节点以预先设置的概率阈值试探性的成为候选簇首，如果一个节点竞选获胜，则在 该节点的通信范围内其他的候选簇首将不能成为最终的簇首，为了减少靠近基站的簇规模大小，靠近基站的 候选簇首的竞争半径相对较小，候选节点的竞争半径与网络中节点到基站的最远距离、最近距离，以及候选 簇首节点到基站距离有关。候选簇首根据节点的剩余能量高低竞争选出最终的簇首。相比于ＨＥＥＤ协议， ＵＣＲ协议有效的延长了网络的生存时间。 （１２）事件触发的分簇路由协议。文献［２２］中提出了基于事件触发的分簇路由协议，ＥＳＤＣ协议，即在事 件触发区域的节点参与簇型结构的构建与数据的融合传输，没有事件触发区域的节点处于休眠状态，从而减 少整个网络的能耗，在事件触发区域，节点成为簇首的概率主要与四个因素有关，与节点到基站的距离成反 比，与节点到事件触发区域的中心成反比，所谓的事件触发区域中心指该区域中所有节点坐标的平均坐标位 置，与节点的剩余能量成正比，与节点周围处于事件触发状态的节点个数成正比。当成员节点同时在几个簇 首节点的通信范围内时，选择与基站通信距离最小的簇首并加入该簇。ＥＳＤＣ协议通过避开没有事件触发 区域的节点参与簇型的构造与数据的处理，减少了能耗与数据传输的碰撞等。实验表明，相比与ＬＥＡＣＨ协 议，ＥＳＤＣ算法在节点的生存时间较好，数据传输延迟较小。 ２．２分簇路由协议的数据传输与融合 无线传感器网络中布置着大量的传感器网络，通过这些节点采集到用户所需要的数据，如果不对这些数 据进行处理而直接传输到基站，就会造成数据传输过程中的碰撞、冲突，造成大量数据的冗余等，因此节点必 须对这些数据进行融合处理，所谓数据融合，是指将大量的数据或者信息进行处理，去除其中的冗余信息，只 将少量的有意义的处理结果传输给汇聚节点，得到一些更高效、更可靠、更符合用户需求的数据的过程。本 文主要讨论的是基于簇型结构的数据聚合方式，通常的簇型路由协议采用的是集中式的数据融合机制，即整 个网络分成簇型结构，簇首节点收集完所有的簇内节点传输过来的数据后，簇首对这些数据融合处理后传输 给基站 ］。 ＬＥＡＣＨ，文献［４］，ＳＥＰ，ＣＨＥＦ，ＥＥＨＣ，ＤＥＥＣ等协议数据传输方式采用两级的结构，即簇内节点将采集 到的数据传输给相应的簇首节点，簇首节点收集完所有对应的簇内节点数据后，经过融合处理后传输给基 站。然而该类协议并没有提出具体的融合方式。Ｍａｎｊｅｓｈｗａｒ Ａ等人提出了ＴＥＥＮ算法 ，ＴＥＥＮ算法与 ＬＥＡＣＨ算法较大的不同点是，在数据传输过程中，该协议设置了两个阈值，分别为硬阈值、软阈值两个参数， 硬阈值是被检测数据不能超过的数值，而且软阈值决定了被测数据的波动范围，只有当被监测数据超过硬阈 值且被监测数据的变化幅度大于软阈值时，节点才会传送最新的监测数据，并设置为新的硬阈值。相对于 ＬＥＡＣＨ算法，ＴＥＥＮ算法能够较大的减少节点之间数据传送的次数，从而有效的减少了整个网络的功耗，延 长整个网络的寿命。ＡＰＴＥＥＮ算法 则结合了ＬＥＡＣＨ与ＴＥＥＮ两种算法，是一种主动型与响应型混合的 ６ 网络新媒体技术 ２０１３年 数据传输模式，当网络中有突发事件时，数据传输模式将会采用与ＴＥＥＮ相同的模式（响应型模式），只不过 ＡＩ：ｒＦＥＥＮ算法多了一个计数器，节点每传送一次数据，对应的计数器将清零，当计数器的时间到达的时候，将 采取主动型发送这个数据，不再判断软、硬门限值。在ＬＥＡＣＨ算法中，整个网络最大跳距为两跳，这样就会 导致远离基站的簇首节点，能量消耗太大而过早的死亡，影响到整个网络的性能，ＳＩＶＡ Ｄ．ＭＵＲＵＧＡ． ＮＡＴＨＡＮ等人提出了ＢＣＤＣＰ多跳分簇算法 ，簇首节点的选择由基站来控制，基站首先将每个节点的当前 能量取平均，只有大于平均值的节点才有机会成为簇首节点，这样就避开了低能量节点成为簇首节点的可 能，当簇首节点与基站的距离超过一定时，不直接与基站通信，而是借助其他簇首节点转发到基站，选择其他 簇首节点采用的是最小生成树算法，这样就减轻了远离基站簇首节点的负担，也扩展了整个网络的规模。在 一些报警事件中，用户只需要及时、准确的知道预警结果，而不是传感节点采集的原始数据信息，文献［２９］ 中提出了ＴＥＫＷＥＭ协议，定义两类节点，一类传感节点，一类网关节点，网关节点拥有更大的能量以及通信 能力，每一层拥有网关节点，下一层节点采集的数据通过上一层的网关节点转发，网关将融合处理后的预警 结果传输给用户，减少数据传输的延迟。目的在于传输延迟最小化，网络生存最大化，算法包括事件监测模 型与报警传输模型，在事件监测中，传感节点综合考虑自身采集的数据值是否超过阈值，只有超过的情况下 才将数据传输给对应的网关节点，在传感区域中包括４类节点，根据不同类别来决定其作用，目的是为了实 现报警的最小延迟，报警传输选择的路径尽量做到传输延迟最小化，网络生存最大化。ＥＥＰＡ协议在多跳传 输数据阶段，源节点向基站泛洪路由请求消息，路径节点统计源节点到该节点的路径消耗，最后基站统计每 条路径的能量消耗，并选择多条路径作为候选路径，如果路径中的节点能量低于最低设置的阈值时，该节点 所在的候选路径将被移除。通过这样选择从源节点到基站能量消耗较低，路径节点剩余能量较高的路径。 Ｈａｕｓｄｏｆｆｆ协议簇首节点收集簇内节点采集的数据、融合后采用Ｄｉｊｋｓｔｒａ最短路由优先算法将数据传输给基 站，如果存在多条路径的话，采用节点剩余能量较多的路径传输。ＵＣＲ协议在数据传输阶段，如果簇首节点 到基站的距离小于指定的阈值，则直接与基站通信，如果超过阈值，则该簇首节点需借助网络通信开销最小， 簇首剩余能量最多的节点做为上一级节点来转发数据。ＥＳＤＣ协议在数据通信阶段，在有事件监测区域内 簇首收集成员节点数据，传输给基站或借助其他节点传输给基站，在多跳的过程中，主要借助于基站的最小 通信距离节点作为转发节点，判断节点是否能够成为转发节点的依据为，假设两个簇首节点１与２，簇首２ 是簇首１的下一级簇首，在两个簇首节点的通信范围内有共同节点Ｃ，且Ｃ到基站的距离大于簇首１到基站 的距离，则节点Ｃ就可以成为两个簇的转发节点。 ３比较与分析 由于无线传感器网络节点能量的，拓扑结构的不稳定性等，传统的路由协议无法直接运用于无线传 感器网络中，必须对其进行专门的研究，而分簇路由协议拓扑结构更易管理，拓展性能好，非常适合于无线传 感器网络中，经过十多年的发展，目前国内外已有较多的分簇路由协议，不同的协议可能针对的场景不同，解 决的问题不同，如ＬＥＡＣＨ等协议针对的是同构的网络环境，而ＳＥＰ等针对的是异构的环境，ＴＡＢＲ—ＲＣＣ重 点解决事件监测区域节点的覆盖问题与网络的连通性问题，ＫＯＣＡ重点解决多个簇重叠式问题，ＥＳＤＣ考虑 的事件触发区域节点与无事件触发区域节点的问题，ＵＣＲ协议则考虑了簇首节点的能耗均衡问题，ＴＥＥＮ， ＡＰＴＥＥＮ侧重于数据的传输与融合方式。因此很难直截了当的判断某种算法的优劣程度，下面我们从几种 主要性能指标来比较各种算法的性能。表一中，Ａ代表节点的构造，可以分为同构与异构，通常的异构指节 点的计算能力异构，链路通信异构，电源能量异构，传输频率异构等，加入部分异构节点可以延长整个网络的 生存时间，减少数据量的传输，提高数据传输的可靠性＿１。‘ ’加川，当然同样也增加了一定的成本。Ｂ代表该 协议的理论前提与实验仿真条件，Ｃ代表节点选择成为簇首的几率，Ｄ代表簇首节点与基站的通信跳数，Ｅ 代表节点是否需要测量距离，即节点是否需要ＧＰＳ定位设备支持，或定位算法估算坐标与距离。Ｆ代表簇规 模的均匀性，Ｇ代表是否构造簇型结构，Ｈ代表是否提起数据的传输方式，Ｉ代表算法的复杂度，Ｊ代表簇头 ５期 徐世武等：无线传感器网络分簇路由协议综述 ７ 的选举速度，Ｋ代表参与簇首竞选或数据传输的节点分布。表一中横线代表文中未提，或是无法判断，从表 一中可以看出大部分协议的仿真场景都是静态的，都需要测量节点的距离，进而估算出能耗。 表一无线传感器网络的分簇路由协议的比较与对照 ４总结与展望 进几年，无线传感器网络备受各个国家的高度重视，对无线传感器网络基础协议的研究成了各个国家关 于无线传感器网络研究的重点也是难点，而路由协议则是无线传感器网络其它协议研究的前提条件，也是其 核心技术之一，采用分簇的路由结构成了目前关于无线传感器网络路由协议研究的重点，本文分析了近几年 关于无线传感器网络经典的分簇路由协议，并对这些协议进行了比对与分析，从总体上看，无线传感器网络 分簇路由协议的核心在于簇型结构的形成，以及数据的传输与融合两个阶段，从以上对各种经典协议的分析 中，我们可以看出，对簇首节点的选择不能只简单的依据某个因素，如节点剩余能量，与其他节点的距离等， 而必须综合考虑各个因素，合理的簇首比例与簇首分布位置都对均衡整个网络的能耗起到至关重要的作用， 应该尽量减少簇型结构形成过程中所需的能耗，使节点剩余更多的能耗来处理数据的传输与融合，在数据传 输阶段，应选择合理的传输路径，减少数据传输的延迟，提高融合的精度。随着传感节点硬件的不断发展，关 于路由协议的研究也必须考虑节点传输语音、图像等多媒体数据流的问题 。 参考文献 ［１］Ｒ．Ｖ．Ｋｕｌｋａｒｎｉ，Ａ．Ｆｏｒｓｔｅｒ，ａｎｄ Ｇ．Ｋ．Ｖｅｎａｙａｇａｍｏｏｒｔｈｙ．Ｃｏｍｐｕｔａｔｉｏｎａｌ Ｉｎｔｅｌｌｉｇｅｎｃｅ ｉｎ Ｗｉｒｅｌｅｓｓ Ｓｅｎｓｏｒ Ｎｅｔｗｏｒｋｓ：Ａ Ｓｕｒｖｅｙ． ＩＥＥＥ Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ Ｓｕｒｖｅｒｓ＆Ｔｕｔｏｒｉａｌｓ，２０１ １，１ ３（１）：１—２９ ［２］Ｈｅｉｎｚｅｌｍａｎ Ｗ Ｂ，Ｃｈａｎｄｒａｋａｓａｎ Ａ，Ｂａｌａｋｒｉｓｈｎａｎ Ｈ．Ｅｎｅｒｇｙ－－Ｅｆｆｉｃｉｅｎｔ ｃｏｍｍｕｎｉｃａｔｉｏｎ ｐｒｏｔｏｃｏｌ ｆｏｒ ｗｉｒｅｌｅｓｓ ｍｉｃｒｏｓｅｎｓｏｒ ｎｅｔｗｏｒｋｓ． Ｉｎ：Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ ３３ｒｄ Ａｎｎｕａｌ Ｈａｗａｉｉ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｂｃｅ ｏｎ Ｓｙｓｔｅｍ Ｓｃｉｅｎｃｅｓ．Ｍａｕｉ：ＩＥＥＥ Ｃｏｍｐｕｔｅｒ Ｓｏｃｉｅｔｙ．２０００．３００５ —３０１４ ［３］Ｈｅｉｎｚｅｌｍａｎ Ｗ Ｂ，Ｃｈａｎｄｒａｋａｓａｎ Ａ Ｐ，Ｂａｌａｋｒｉｓｈｎａｎ Ｈ．Ａｎ ａｐｐｌｉｃａｔｉｏｎ—ｓｐｅｃｉｆｉｃ ｐｒｏｔｏｃｏｌ ａｒｃｈｉｔｅｃｔｕｒｅ ｆｏｒ ｗｉｒｅｌｅｓｓ ｍｉｃｒｏｓｅｎｓｏｒ ｎｅｔ— ８ 网络新媒体技术 ２０１３ ｗｏｒｋｓ［Ｊ］．ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｗｉｒｅｌｅｓｓ Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ，２００２，１（４）：６６０—６７０ ［４］Ｉ．ＧＵＰＴＡ。Ｄ．Ｒ１ＯＲＤＡＮ，ＡＮＤ Ｓ．ＳＡＭＰＡＬＬＩ．Ｃｌｕｓｔｅｒ—ｈｅａｄ ｅｌｅｃｔｉｏｎ ｕｓｉｎｇ ｆｕｚｚｙ ｌｏｇｉｃ ｆｏｒ ｗｉｒｅｌｅｓｓ ｓｅｎｓｏｒｎｅｔｗｏｒｋｓ．Ｉｎ Ｐｒｏｃｅｅｄ— ｉｎｇｓ ｏｆ ｔｈｅ ３ｒｄ Ａｎｎｕａｌ Ｃｏｍｍｕｎｉｃａｔｉｏｎ Ｎｅｔｗｏｒｋｓ ａｎｄ Ｓｅｒｖｉｃｅｓ Ｒｅｓｅａｒｃｈ Ｃｏｎｆｅｒｅｎｃｅ（ＣＮＳＲ’０５）．ＩＥＥＥ，Ｈａｌｉｆａｘ，Ｃａｎａｄａ，２００５， ２５５—２６０ ［５］Ｊ．Ｍ．Ｋｉｍ，Ｓ．Ｈ．Ｐａｒｋ，Ｙ．Ｊ．Ｈａｎ，Ｔ．Ｍ．Ｃｈｕｎｇ，ＣＨＥＦ：ｃｌｕｓｔｅｒ ｈｅａｄ ｅｌｅｃｔｉｏｎ ｍｅｃｈａｎｉｓｍ ｕｓｉｎｇ ｆｕｚｚｙ ｌｏｇｉｃ ｉｎ ｗｉｒｅｌｅｓｓ ｓｅｎｓｏｒ ｎｅｔｗｏｒｋｓ，ｉｎ：Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ ＩＣＡＣＴ，Ｆｅｂｒｕａｒｙ ２００８，ＰＰ．６５４—６５９ ［６］Ｓ．Ｈｕｓｓａｉｎ，Ａ．Ｗ．Ｍａｔｉｎ，ａｎｄ Ｏ．Ｉｓｌａｍ，“Ｇｅｎｅｔｉｃ ａｌｇｏｒｉｔｈｍ ｏｒｆ ｅｎｅｒｇｙ ｅｉｃｉｆｅｎｔ ｃｌｕｓｔｅｒｓ ｉｎ ｗｉｒｅｌｅｓｓ ｓｅｎｓｏｒ ｎｅｔｗｏｒｋｓ，”ｉｎ Ｆｏｕｒｔｈ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｉｎｆｏｒｍａｔｉｏｎ Ｔｅｃｈｎｏｌｏｇｙ：Ｎｅｗ Ｇｅｎｅｒａｔｉｏｎｓ（ＩＴＮＧ ２００７），Ａｐｒｉｌ ２００７． ［７］唐伟，郭伟．无线传感器网络中的最大生命期基因路由算法［Ｊ］．软件学报，２０１０，２１（７）：１６４６—１６５６ ［８］Ｒ．Ｋａｎｎａ，Ｓ．Ｓ．Ｉｙｅｎｇａｒ．Ｇａｍｅ ｔｈｅｏｒｅｔｉｃ ｍｏｄｅｌｓ ｆｏｒ ｒｅｌｉａｂｌｅ ｐａｔｈ—ｌｅｎｇｔｈ ａｎｄ ｅｎｅｒｇｙ ｃｏｎｓｔｒａｉｎｅｄ ｒｏｕｔｉｎｇ ｗｉｔｈ ｄａｔａ ａｇｇｒｅｇａｔｉｏｎ ｉｎ ｗｉｒｅｌｅｓｓ ｓｅｎｓｏｒ ｎｅｔｗｏｒｋｓ．ＩＥＥＥ Ｊｏｕｒｎａｌ ｏｎ Ｓｅｌｅｃｔｅｄ Ａｒｅａｓ ｉｎ Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ，２００４，２２（６）：１ １４１—１ １５０ ［９］Ｇ．Ｖ．Ｃｒｏｓｂｙ，Ｎ．Ｐｉｓｓｉｎｏｕ，Ｅｖｏｌｕｔｉｏｎ ｏｆ ｃｏｏｐｅｒａｔｉｏｎ ｉｎ ｍｕｌｔｉ—ｃｌａｓｓ ｗｉｒｅｌｅｓｓ ｓｅｎｓｏｒ ｎｅｔｗｏｒｋｓ，ｉｎ：Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ ３２ｎｄ ＩＥＥＥＣｏｎｆｅｒｅｕｃｅ ｏｎ Ｌｏｃａｌ Ｃｏｍｐｕｔｅｒ Ｎｅｔｗｏｒｋｓ，２００７，ＰＰ．４８９—４９５ ［１０］Ｇｅｎｇｚｈｏｎｇ Ｚｈｅｎｇ，Ｓａｎｙａｎｇ Ｌｉｕ，ａｎｄ Ｘｉａｏｇａｎｇ Ｑｉ．Ｃｌｕｓｔｅｒｉｎｇ ｒｏｕｔｉｎｇ ａｌｇｏｒｉｔｈｍ ｏｆ ｗｉｒｅｌｅｓｓ ｓｅｎｓｏｒ ｎｅｔｗｏｒｋｓ ｂａｓｅｄ ｏｎ Ｂａｙｅｓｉａｎ ｇａｍｅ．Ｊｏｕｒｎａｌ ｏｆ Ｓｙｓｔｅｍｓ Ｅｎｇｉｎｅｅｒｉｎｇ ａｎｄ Ｅｌｅｃｔｒｏｎｉｃｓ．２０１２，２３（１）：１５４—１５９ ［１ １］Ｇ．Ｓｍａｒａｇｄａｋｉｓ，Ｉ．Ｍａｔｔａ ａｎｄ Ａ．Ｂｅｓｔａｖｒｏｓ．ＳＥＰ：Ａ Ｓｔａｂｌｅ Ｅｌｅｃｔｉｏｎ Ｐｒｏｔｏｃｏｌ ｏｒｆ ｃｌｕｓｔｅｒｅｄ ｈｅｔｅｒｏｇｅｎｅｏｕｓ ｗｉｒｅｌｅｓｓ ｓｅｎｓｏｒ ｎｅｔｗｏｒｋｓ ［Ｊ］．２ｎｄ Ｉｎｔ１．Ｗｏｒｋｓｈｏｐ ｏｎ Ｓｅｎｓｏｒ ａｎｄ Ａｃｔｏｒ Ｎｅｔｗｏｒｋ Ｐｒｏｔｏｃｏｌｓ ａｎｄ Ａｐｐｌｉｃａｔｉｏｎｓ，２００４． ［１２］Ｄ Ｋｕｍａｒ，Ｔ Ｃ Ａｓｅｒｉ，Ｒ Ｂ Ｐａｔｅ１．ＥＥＨＣ：Ｅｎｅｒｙ ｇｅｆｉｃｉｆｅｎｔ ｈｅｔｅｒｏｇｅｎｅｏｕｓ ｃｌｕｓｔｅｒｅｄ ｓｃｈｅｍｅ ｏｒｆ ｗｉｒｅｌｅｓｓ ｓｅｎｓｏｒ ｎｅｔｗｏｒｋｓ．Ｃｏｍｐｕｔｅｒ Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ ３２（２００９）：６６２—６６７ ［１ ３］Ｌｉ Ｑｉｎｇ，Ｑｉｎｇｘｉｎ Ｚｈｕ，Ｍｉｎｇｗｅｎ Ｗａｎｇ．Ｄｅｓｉｇｎ ｏｆ ａ ｄｉｓｔｉｒｂｕｔｅｄ ｅｎｅｒｙ—ｅｆｇｉｃｆｉｅｎｔ ｃｌｕｓｔｅｒｉｎｇ ａｌｇｏｒｉｔｈｍ ｏｆｒ ｈｅｔｅｒｏｇｅｎｅｏｕｓ ｗｉｒｅｌｅｓｓ ｓｅｎｓｏｒ ｎｅｔｗｏｒｋｓ［Ｊ］．Ｃｏｍｐｕｔｅｒ Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ ２９（２００６）：２２３０—２２３７ ［１４］Ｏ．Ｙｏｕｎｉｓ，Ｓ．Ｆａｈｍｙ，ＨＥＥＤ：Ａ Ｈｙｂｒｉｄ，Ｅｎｅｒｇｙ—Ｅｆｉｃｉｆｅｎｔ，Ｄｉｓｔｉｒｂｕｔｅｄ ｃｌｕｓｔｅｒｉｎｇ ａｐｐｒｏａｃｈ ｆｏｒ Ａｄ Ｈｏｃ ｓｅｎｓｏｒ ｎｅｔｗｏｒｋｓ，ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｍｏｂｉｌｅ Ｃｏｍｐｕｔｉｎｇ，２００４，３（４）：３６６—３７９ ［１５］Ｍ Ｙ，Ｓｅｎｉｏｒ，Ｋ Ｋ．Ｌｅｕｎｇ，ａｎｄ Ａ Ｍａｌｖａｎｋａｒ．Ａ Ｄｙｎａｍｉｃ Ｃｌｕｓｔｅｒｉｎｇ ａｎｄ Ｅｎｅｒｙ ｇＥｆｆｉｃｉｅｎｔ Ｒｏｕｔｉｎｇ Ｔｅｃｈｎｉｑｕｅ ｏｒｆ Ｓｅｎｓｏｒ Ｎｅｔｗｏｒｋｓ． ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ ｗｉｒｅｌｅｓｓ ｃｏｍｍｕｎｉｃａｔｉｏｎｓ，２００７，６（８）：３０６９—３０７９ ［１６］Ｘ．Ｚｈｕ，Ｌ．Ｓｈｅｎ，ａｎｄ Ｔ．Ｐ．Ｙｕｍ，“Ｈａｕｓｄｏｒｆｆ Ｃｌｕｓｔｅｒｉｎｇ ａｎｄ Ｍｉｎｉｍｕｍ Ｅｎｅｒｙ Ｒｏｕｔｇｉｎｇ ｏｒｆ Ｗｉｒｅｌｅｓｓ Ｓｅｎｓｏｒ Ｎｅｔｗｏｒｋｓ，”ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎｓ Ｖｅｈｉｃｕｌａｒ Ｔｅｃｈｎｏｌｏｇｙ，２００９，５８（２）：９９０—９９７ ［１７］Ｄａｎｉｅｌ Ｐ．Ｈｕｔｔｅｎｌｏｃｈｅｒ，Ｇｒｅｇｏｒｙ Ａ．Ｋｌａｎｄｅｒｍａｎ，ａｎｄ Ｗｉｌｌｉａｍ Ｊ．Ｒｕｃｋｌｉｄｇｅ．Ｃｏｍｐａｒｉｎｇ Ｉｍａｇｅｓ Ｕｓｉｎｇ ｔｈｅ Ｈａｕｓｄｏｒｆｆ Ｄｉｓｔａｎｃｅ． ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎｓ Ｐａｔｔｅｒｎ Ａｎａｌｙｓｉｓ ａｎｄ Ｍａｃｈｉｎｅ Ｉｎｔｅｌｌｉｇｅｎｃｅ，１９９３，１５（９）：８５０—８６３ ［１ ８］Ａ．Ｃｈａｍａｍ，ａｎｄ Ｓ．Ｐｉｅｒｒｅ．Ｏｎ ｔｈｅ Ｐｌａｎｎｉｎｇ ｏｆ Ｗｉｒｅｌｅｓｓ Ｓｅｎｓｏｒ Ｎｅｔｗｏｒｋｓ：Ｅｎｅｒｇｙ—Ｅｆｉｃｉｆｅｎｔ Ｃｌｕｓｔｅｒｉｎｇ ｕｎｄｅｒ ｔｈｅ Ｊｏｉｎｔ Ｒｏｕｔｉｎｇ ａｎｄ Ｃｏｖｅｒａｇｅ Ｃｏｎｓｔｒａｉｎｔ．ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ ｍｏｂｉｌｅ ｃｏｍｐｕｔｉｎｇ，２００９，８（８）：１０７７—１０８６ ［１９］Ｍ．Ａ．Ｙｏｕｓｓｅｆ，Ａ．Ｙｏｕｓｓｅｆ，ａｎｄ Ｍ．Ｆ．Ｙｏｕｎｉｓ．Ｏｖｅｒｌａｐｐｉｎｇ ｍｕｈｉｈｏｐ ｃｌｕｓｔｅｒｉｎｇ ｏｒｆ ｗｉｒｅｌｅｓｓ ｓｅｎｓｏｒ ｎｅｔｗｏｒｋｓ．ＩＥＥＥ Ｔｒａｎｓａｃ・ ｔｉｏｎ ｏｎ Ｐａｒａｌｌｅｌ ａｎｄ Ｄｉｓｔｉｒｂｕｔｅｄ ｓｙｓｔｅｍｓ，２００９，２０（１２）：１８４４—１８５６ ［２０］Ｓ．Ｓｏｒｏ ａｎｄ Ｗ．Ｈｅｉｎｚｅｌｍａｎ，Ｐｒｏｌｏｎｇｉｎｇ ｔｈｅ ｌｉｆｅｔｉｍｅ ｏｆ ｗｉｒｅｌｅｓｓ ｓｅｎｓｏｒ ｎｅｔｗｏｒｋｓ ｖｉａ ｕｎｅｑｕａｌ ｃｌｕｓｔｅｒｉｎｇ，ｉｎ：Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ １９ｔｈ ＩＥＥＥ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｐａｒａｌｌｅｌ ａｎｄ Ｄｉｓｔｉｒｂｕｔｅｄ Ｐｒｏｃｅｓｓｉｎｇ Ｓｙｍｐｏｓｉｕｍ（ＩＰＤＰＳ）（Ａｐｒｉｌ ２００５） ［２１］Ｇｕｉｈａｉ Ｃｈｅｎ，Ｃｈｅｎｇｆａ Ｌｉ，Ｍａｏ Ｙｅ，ＪｉｅＷｕ．Ａｎ ｕｎｅｑｕａｌ ｃｌｕｓｔｅｒ—ｂａｓｅｄ ｒｏｕｔｉｎｇ ｐｒｏｔｏｃｏｌ ｉｎ ｗｉｒｅｌｅｓｓ ｓｅｎｓｏｒ ｎｅｔｗｏｒｋｓ．Ｗｉｒｅｌｅｓｓ Ｎｅｔｗ （２００９）１５：１９３—２０７ ［２２］Ｂｅｒｅｋｅｔｌｉ，Ａ．Ａｋａｎ，Ｏ．Ｂ．Ｅｖｅｎｔ—ｔｏ—Ｓｉｎｋ Ｄｉｒｅｃｔｅｄ Ｃｌｕｓｔｅｒｉｎｇ ｉｎ Ｗｉｒｅｌｅｓｓ Ｓｅｎｓｏｒ Ｎｅｔｗｏｒｋｓ．Ｉｎ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ ＩＥＥＥ Ｗｉｒｅ— ｌｅｓｓ Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ ａｎｄ Ｎｅｔｗｏｒｋｉｎｇ Ｃｏｎｆｅｒｅｎｃｅ（ＷＣＮＣ’０９），Ｂｕｄａｐｅｓｔ，Ｈｕｎｇａｒｙ，５—８ Ａｐｒｉｌ ２００９；１—６ 『２３ １ Ｎａｋａｍｕｒａ Ｅ Ｆ．Ｌｏｕｒｅｉｒｏ Ｐ Ａ Ｆ。Ｆｒｅｒｙ Ｐ Ｃ．Ｉｆｏｒｎｍａｔｉｏｎ ｆｕｓｉｏｎ ｆｏｒ ｗｉｒｅｌｅｓｓ ｓｅｎｓｏｒ ｎｅｔｗｏｒｋｓ：ｍｅｔｈｏｄｓ，ｍｏｄｅｌｓ，ａｎｄ ｃｌａｓｓｉｆｉｃａｔｉｏｎｓ． ＡＣＭ Ｃｏｍｐｕｔｉｎｇ Ｓｕｒｖｅｙｓ，２００７，３９（３）：１—５５ ［２４］Ｃｕｎｑｉｎｇ Ｈｕａ ａｎｄ Ｔａｋ—Ｓｈｉｎｇ Ｐｅｔｅｒ Ｙｕｍ．Ｏｐｔｉｍａｌ Ｒｏｕｔｉｎｇ ａｎｄ Ｄａｔａ Ａｇｇｒｅｇａｔｉｏｎ ｏｆｒ Ｍａｘｉｍｉｚｉｎｇ Ｌｉｆｅｔｉｍｅ ｏｆ Ｗｉｒｅｌｅｓｓ Ｓｅｎｓｏｒ Ｎｅｔ— ｗｏｒｋｓ．ＩＥＥＥ／ＡＣＭ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ ｎｅｔｗｏｒｋｉｎｇ，２００８，１６（４）：８９２—９０３ ［２５］Ｆｏｒｅｒｏ，Ｐ．；Ｃａｕｏ，Ａ．；Ｇｉａｎｎａｋｉｓ，Ｇ．Ｄｉｓｔｒｉｂｕｔｅｄ ｃｌｕｓｔｅｒｉｎｇ ｕｓｉｎｇ ｗｉｒｅｌｅｓｓ ｓｅｎｓｏｒ ｎｅｔｗｏｒｋｓ．ＩＥＥＥ Ｊ．Ｓｅ１．Ｔｏｐ．Ｓｉｇｎａｌ Ｐｒｏｃｅｓｓ． ２０１１，５，７０７—７２４ （下转第２ｌ页） ５期 存消耗，如表３所示。 李长路等：基于ＨＩ３７１６Ｍ的嵌入式ＧＵＩ设计与实现 ２１ 可见，在进行视频播放的改进之后，不仅提高了播放效率，同时还节约了播放视频时的资源。 ５总结及展望 本文提供了智能终端图形用户界面的一个实现方案，并在海思平台上合理搭建，经过分析及运行测试， 证明性能基本满足用户体验要求。系统实现侧重于对更多应用的支持，并有效管理，保障系统稳定性。让视 频播放越过Ｘ Ｗｉｎｄｏｗ直接操作平台ＳＤＫ，解决了ｘ系统带来的视频播放效率偏低问题，取得明显效果。该 系统仍有进一步裁剪、优化的空间。 参考文献 ［１］许勇，陈蜀宇．基于ＡＲＭ的嵌入式Ｌｉｎｕｘ图形界面的研究与实现［Ｊ］．计算机系统应用，２０１ １，２０（１０）：１３７—１４１ ［２］吴晓烁，陈蜀宇，刘巍．嵌入式Ｌｉｎｕｘ环境下高效率ＧＵＩ的设计与实现［Ｊ］．重庆工学院学报：自然科学版，２００９，（２）：１３６— １４１ ［３］阳富民，肖世杰，涂刚．基于ＥＰ７３１２的嵌入式Ｘ Ｗｉｎｄｏｗ［Ｊ］．计算机工程与科学，２００４，２６（１０）：３７—４０ ［４］Ｄ．Ｃｒｉｓｕ，Ｓ．Ｄ．Ｃｏｔｏｆａｎａ，Ｓ．Ｖａｓｓｉｌｉａｄｉｓ，Ｐ．Ｌｉｕｈａ ＧＲＡＡＬ—Ａ Ｄｅｖｅｌｏｐｍｅｎｔ Ｆｒａｍｅｗｏｒｋ ｆｏｒ Ｅｍｂｅｄｄｅｄ Ｇｒａｐｈｉｃｓ Ａｃｃｅｌｅｒａｔｏｒｓ ［Ｊ］．ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｄｅｓｉｇｎ ａｕｔｏｍａｔｉｏｎ ａｎｄ ｔｅｓｔ．２００４，２．２１３６６ ［５］Ｌｕｏ Ｑｉ，Ｌｕｏ Ｌｅｉ．Ａ ｕｎｉｖｅｒｓａｌ ｓｏｌｕｔｉｏｎ ｏｆ ａｎ ｅｍｂｅｄｄｅｄ ｍｕｈｉｔａｓｋｉｎｇ ＧＵＩ Ｓｙｓｔｅｍ［Ｊ］．Ｅｍｂｅｄｄｅｄ Ｓｏｆｔｗａｒｅ ａｎｄ Ｓｙｓｔｅｍｓ，２００５，Ｓｅｅ— ｏｎｄ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ．２００５．１６—１８ 作者简介 李长路，男，（１９８７生），中科院声学所，博士研究生，研究方向：信号与信息处理。 （上接第８页） ［２６］Ｍａｎｊｅｓｈｗａｒ Ａ．Ｇｒａｗａｌ ＤＰ．ＴＥＥＮ：Ａ ｐｒｏｔｏｃｏｌ ｆｏｒ ｅｎｈａｎｃｅｄ ｅｆｉｆｃｉｅｎｃｙ ｉｎ ｗｉｒｅｌｅｓｓ ｓｅｎｓｏｒ ｎｅｔｗｏｒｋｓ．Ｉｎ：Ｐｒｏｃ ｏｆ ｔｈｅ １５ Ｐａｒａｌｌｅｌ ａｎｄ Ｄｉｓｔｒｉｂｕｔｅｄ Ｐｒｏｃｅｓｓｉｎｇ Ｓｙｍｐ．ＩＥＥＥ Ｃｏｍｐｕｔｅｒ Ｓｏｃｉｅｔｙ．２００１，２００９－－２０１５ ［２７］Ｍａｎｊｅｓｈｗａｒ Ａ．Ａ．ｇｒａｗａｌ ＤＰ．ＡＰＴＥＥＮ：Ａ ｈｙｂｒｉｄ ｐｒｏｔｏｃｏｌ ｆｏｒ ｅｆｉｆｃｉｅｎｔ ｒｏｕｔｉｎｇ ａｎｄ ｃｏｍｐｒｅｈｅｎｓｉｖｅ ｉｎｆｏｒｍａｔｉｏｎ ｒｅｔｒｉｅｖａｌ ｉｎ ｗｉｒｅｌｅｓｓ ｓｅｎｓｏｒ ｎｅｔｗｏｒｋｓ．Ｉｎ：Ｐｒｏｃ．ｏｆ ｔｈｅ ２ｎｄ Ｉｎｔ’ｌ Ｗｏｒｋｓｈｏｐ ｏｎ Ｐａｒａｌｌｅｌ ａｎｄ Ｄｉｓｔｉｒｂｕｔｅｄ Ｃｏｍｐｕｔｉｎｇ Ｉｓｓｕｅｓ ｉｎ Ｗｉｒｅｌｅｓｓ Ｎｅｔｗｏｒｋｓ ａｎｄ Ｍｏ— ｂｉｌｅ Ｃｏｍｐｕｔｉｎｇ．ＩＥＥＥ Ｃｏｍｐｕｔｅｒ Ｓｏｃｉｅｔｙ，２００２．１９５—２０２ ［２８］ＳＩＶＡ Ｄ．ＭＵＲＵＧＡＮＡＴＨＡＮ，ＤＡＮＩＥＬ Ｃ．Ｆ．ＭＡ，ＲＯＬＬＹ Ｉ．ＢＨＡＳＩＮ．Ａ Ｃｅｎｔｒｌｉａｚｅｄ Ｅｎｅｒｇｙ—Ｅｆｉｆｃｉｅｎｔ Ｒｏｕｔｉｎｇ Ｐｒｏｔｏｃｏｌ ｆｏｒ Ｗｉｒｅｌｅｓｓ Ｓｅｎｓｏｒ Ｎｅｔｗｏｒｋｓ．ＩＥＥＥ Ｒａｄｉｏ Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ．２００５．Ｓ８—１３ ｌ２９］Ｙ Ｓ Ｌｉ，，Ｃ Ａｉ，ＣＴ．Ｖｕ，Ｙ Ｐａｎ，ａｎｄ Ｒ Ｂｅｙａｈ．Ｄｅｌａｙ—Ｂｏｕｎｄｅｄ ａｎｄ Ｅｎｅｒｙ—Ｅｆｇｆｉｃｉｅｎｔ Ｃｏｍｐｏｓｉｔｅ Ｅｖｅｎｔ Ｍｏｎｉｔｏｒｉｎｇ ｉｎ Ｈｅｔｅｒｏ— ｇｅｎｅｏｕｓ Ｗｉｒｅｌｅｓｓ Ｓｅｎｓｏｒ Ｎｅｔｗｏｒｋｓ，ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ ｐａｒａｌｌｅｌ ａｎｄ ｄｉｓｔｒｉｂｕｔｅｄ ｓｙｓｔｅｍｓ，２０１０，２１（９）：１３７３—１３８５ ［３０］Ｈ．Ｌ．Ｒｅｎ．Ｇａｍｅｓ—ｔｈｅｏｒｅｔｉｃ ｍｏｄｅｌｉｎｇ ｏｆ ｊｏｉｎｔ ｔｏｐｏｌｏｇｙ ｃｏｎｔｍｌ ａｎｄ ｐｏｗｅｒ ｓｃｈｅｄｕｌｉｎｇ ｆｏｒ ｗｉｒｅｌｅｓｓ ｈｅｔｅｒｏｇｅｎｅｏｕｓ ｓｅｎｓｏｒ ｎｅｔ— ｗｏｒｋｓ．ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ａｕｔｏｍａｔｉｏｎ Ｓｃｉｅｎｃｅ ａｎｄ Ｅｎｇｉｎｅｅｒｉｎｇ，２００９，６（４）：６１０—６２５ ［３１］Ｙａｎ Ｊｉｎ，Ｌｉｎｇ Ｗａｎｇ，Ｊｕ—Ｙｅｏｎ Ｊｏ．ＥＥＣＣＲ－Ａｎ Ｅｎｅｒｙ—Ｅｆｇｉｃｉｆｅｎｔ ｍ—Ｃｏｖｅｒａｇｅ ａｎｄ ｎ—Ｃｏｎｎｅｃｔｉｖｉｔｙ Ｒｏｕｔｉｎｇ Ａｌｇｏｒｉｔｈｍ Ｕｎｄｅｒ Ｂｏｒｄｅｒ Ｅｆｆｅｃｔｓ ｉｎ Ｈｅｔｅｒｏｇｅｎｅｏｕｓ Ｓｅｎｓｏｒ Ｎｅｔｗｏｒｋｓ．ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ ｖｅｈｉｃｕｌａｒ ｔｅｃｈｎｏｌｏｇｙ，２００９，５８（３）：１４２９—１４４２ ［３２］周灵，王建新．无线多媒体传感器网络路由协议研究［Ｊ］．电子学报，２０１１，３９（１）：１４９—１５６ 作者简介 徐世武，（１９８６一），男，福建莆田，助教，主要研究方向：无线传感器网络。 王平，（１９５５～），男，福建福州，教授，研究领域为通信网络新技术，无线传感器网络。 施文灶，（１９８２一），男，福建泉州，在读博士生，研究方向为无线传感器网络。 苏国栋，（１９８９一），男，福建泉州，在读硕士生，研究方向为无线传感器网络路由协议。
