维普资讯 http://www.cqvip.com 第７期 ０ ７ ２ ０年９月 计算机技术与发展 （Ｘ３ＭＰＵＴＥＲ ＴＥＣＨＮＯＩ￣￣Ｙ ＡＮＤ ＤＥＶＥＬＯＰＭＥＮＴ Ｖｏ１．１７ Ｎｏ．９ Ｓｅｐ． ２００７ 自组网分簇算法仿真设计 郭晓莲 ，林志伟２，黄榕宁２ （１．福建工程学院计算机与信息科学系，福建福州３５００１４； ２．福建师范大学数学与计算机科学学院，福建福州３５０００７） 摘要：自组网是一种由移动节点自组织形成的、不需要任何基础设施的网络，针对其随机的拓扑结构研究人员提出了基 于分簇结构的拓扑机制，用于网络路由优化和安全控制。然而，这些算法在不同的移动环境中面临着不同的挑战，因而所 表现出来的性能也各不相同，为进一步验证这些算法在不同移动环境中的有效性，文中使用Ｄｅｌｐｈｉ设计了自组网的几个 典型分簇算法，通过随机环境的仿真实验，得到相关仿真数据，分析比较了这些算法的性能，为进一步的研究提供依据。 关键词：自组网；分簇；连通支配集 中图分类号：１］Ｐ３９３ 文献标识码：Ａ 文章编号：１６７３—６２９Ｘ（２００７）０９—００９２—０３ Ｓｉｍｕｌａｔｉｏｎ Ｄｅｓｉｇｎ ｏｆ Ｃｌｕｓｔｅｒ Ａｌｇｏｒｉｔｈｍ ｉｎ Ａｄ Ｈｏｃ Ｎｅｔｗｏｒｋ ＧＵＯ Ｘｉａｏ－ｌｉａｎ ，ＬＩＮ Ｚｈｉ—ｗｅｉ ，ＨＵＡＮＧ Ｒｏｎｇ—ｎｉｎｇｚ （１．Ｄｅｐａｒｔｍｅｎｔ ｏｆ Ｃｏｍｐｕｔｅｒ ａｎｄ Ｉｎｆｏｒｍａｔｉｏｎ，Ｆｕｊｉｎ ａＵｎｉｖｅｒｓｉｔｙ ｏｆ Ｔｅｃｈｎｏｌｏｇｙ，Ｆｕｚｈｏｕ ３５００１４，Ｃｈｉｎａ； ２．Ｓｃｈｏｏｌ ｏｆ Ｍａｔｈｅｍａｔｉｃｓ ｎｄ Ｃａｏｍｐｕｔｒ ｅｃｉＳｅｎｃｅ，Ｆｕｊｉｎ ａＮｏｒｍａｌ Ｕｎ￣ｅｓｉｒｔｙ，Ｆｕｚｈｏｕ ３５０００７，Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ａｄ Ｈｏｃ ｎｅｔｗｏｒｋ ｉｓ ａ ｓｅｌｆ—ｏｒｇａｎｉｚｅｄ ｎｅｔｗｏｒｋ，ｃｏｎｓｉｓｔｉｎｇ ｏｆ ｍｏｂｉｌｅ ｎｏｄｅｓ ｗｉｔｈｏｕｔ ａｎｙ ｉｎｆｒａｓｔｒｕｃｔｕｒｅ．Ｃｌｕｓｔｅｒ—ｂａｓｅｄ ｔｏｐｏｌｏｇｙ ｏｎｔｒｃｏｌ ｓｔｒａｔｅｇｉｅｓ ｈａｖｅ ｂｅｅｎ ｐｍｐｏ￣ｔｏ ｍｅｅｔ ｔｏ ｍｕｔｉｎｇ ｏｐｔｉｍｉｚａｔｉｏｎ ｎｄ ｓｅｃｕｒｉａｔｙ ｃｏｎｔｒｏｌ ｄｕｅ ｔｏ ｔｈｅ ｒａｎｄｏｍ ｅｎｖｉｒｏｎｍｅｎｔ ｏｆ Ａｄ Ｈｏｃ ｎｅｔ． ｗｏｒｋ．Ｂｕｔ ｔｈｅｓｅ ａｌｇｏｒｉｔｈｍｓ ｖａｒｙ ｉｎ ｐｅｒｆｏｒｍａｎｃｅ ｗｈｅｎ ｆａｃｉｇ ｄｉｎｆｆｅｒｅｎｔ ｍｏｂｉｌｅ ｅｎｖｉｍｎｒｎｅｎｔ．Ｓｏｍｅ ｐｍｐｏ￣ｄ ｃｌｕｓｔｅｒ ａｌｇｏｒｉｔｈｍｓ ｗｅｒｅ ｄｅ． ｓｉｇｎｅｄ ｂｙ ｕｓｉｇ ｔｈｅ ｔｎｏｏｌ ｏｆ Ｄｅｌｐｈｉ ｔｏ ｔｓｔｅ ｔｈｅｍ．Ｔｈｅ ｄａｔａ ｗｅｒｅ ａｎａｌｙｚｅｄ ｉｎ ａ ｒａｎｄｏｍ ｓｉｍｕｌａｔｉｏｎ ｅｎｖｉｒｏｎｍｅｎｔ ａｎｄ ｔｈｅ ａｌｇｏｒｉｔｈｍ’Ｓ ｐｅｒｆｏｒ． ｉ＇ｆｌａｎｃｅｓ ｗｅｒｅ ｃｏｍｐａｒｅｄ ｉｎ ｔｈｉｓ ｐａｐｅｒ，ｆｒｏｍ ｗｈｉｃｈ ｔｈｅ ｆｕｔｕｒｅ ｓｔｕｄｙ ｃａｎ ｂｅｎｅｆｉｔ． Ｋｅｙｗｏｒｄｓ：ＡｄＨｏｃ ｎｅｔｗｏｒｋ；ｃｌｕｓｔｅｒ；ｏｎｎｅｃｔｃｄ ｅｄｏｍｉｎａｔｉｇｓｎｅｔ Ｏ引 言 自组网 Ｊ是在不需要预先部署任何基础设施的情 况下，无线终端以随机方式构成的一种分布式的自组 织网络环境。自组网中的每个无线节点分享网络构造 的任务，它们以服务者和被服务对象的身份，通过分布 式点对点协同工作的方式实现数据传输功能，因此，自 组网具有自组织、自管理和可配置的能力。由于自组 性、延时、吞吐量、能耗和冲突等。为了减小冲突，提高 网络容量和路由性能，并进而达到节点能量保护和延 长网络生存时间等目的，研究人员提出了基于虚拟主 干网技术的自组网拓扑控制策略 Ｊ，它通过分布式分 簇算法把网络划分为各个独立的子网（也称为簇），每 个子网由一个簇头负责簇内成员的维护；子网之间通 过分布式网关选取策略，选取尽可能少的节点作为网 关，连接不同的子网，从而构造出具有分层结构的虚拟 主干网，实现网络全局连通。为了实现网络性能的优 网随机动态部署，节点可移动，无中心，不需要任何的 基础设施，使得其在战地通信、抗震救灾、交通管理和 环境监测等领域具有广阔的应用前景。 在自组网环境中，网络拓扑扮演着重要的角色，拓 化，通常要求分簇算法的开销尽可能小，即通过尽可能 少的节点消息交换，在较小的时间复杂度保证下，分布 扑信息的准确性直接影响到网络中为进行传输、寻路 和广播所使用的算法的性能，并进而影响网络的连通 收稿日期：２００６一ｌ１—１４ 基金项目：国家自然科学基金（６０５０２０４７）；福建省教育厅项目 式地求解出尽可能少的主干节点形成虚拟主干网。 文中在文献［３］的基础上，使用Ｄｅｌｐｈｉ对４种典型 的分簇算法进行仿真设计，采集相关数据进行仿真性 能的分析，并在此基础上进行理论分析。 （ＪＡＯ５２０８）；福建工程学院科研发展基金（ＧＹ—Ｚ０６６１） 作者简介：郭晓莲（１９７８一），女，甘肃嘉峪关人，助教，研究方向为计 算机网络。 １模型假设和算法描述 自组网中的无线节点等同于图论中的顶点，分簇 维普资讯 http://www.cqvip.com 第９期 郭晓莲等：自组网分簇算法仿真设计 ・９３・ 所形成的虚拟主干网实质上就是图论中的极小连通支 配集。为了更好地对算法加以数学描述和方便仿真设 计，因此，首先给出相关的数学模型： 定义１图Ｇ＝（Ｖ，Ｅ， ）为单位圆图（ＵｎｉｔＤｉｓｋ 应，调整出最佳通讯状态。与上述三个分簇算法仅考 虑单一的网络特性相比，文献［４］提出了自适应分簇算 法，它把节点能量、移动速度等因素加以考虑，通过自 适应机制，提高分簇的性能。 Ｇｒａｐｈ），其中ｖ和Ｅ分别代表顶点集和边集，ｄ表示以 顶点集ｖ中顶点为圆心的圆的半径甘Ｖ １， ２∈Ｖ， 若边（ １， ２）∈Ｅ，则 １， ２两顶点间的距离ｌ １一 ２ ２算法仿真设计和性能分析 ２．１移动模型 ｌ ｄ。为了方便，以下将单位圆图Ｇ＝（Ｖ，Ｅ， ）简 称为图Ｇ：（Ｖ，Ｅ）。 自组网仿真中，节点的移动策略有多种方案。文 中选取通用的Ｒａｎｄｏｍ Ｗａｙｐｏｉｎｔ模型 ］。其思想是在 定义２（连通支配集）对于给定的图Ｇ＝（Ｖ，Ｅ）， 一个给定的二维移动区域内，节点在到达一个目标位 集合Ｓ是一个支配集当且仅当Ｇ—Ｓ中的节点同Ｓ中 置后，随机选择下一个移动目标Ｄ，并在预先设定的最 至少一个节点相连接。而当删掉Ｓ中的任意一个节点 大速率（Ｍａｘ Ｓｐｅｅｄ）和最小速率（Ｍｉｎ Ｓｐｅｅｄ）中随机选 时，Ｓ不再是一个支配集，则此时称Ｓ为极小连通支配 取一个速率，以此速率匀速前进，到达该目标Ｄ后随 集。在Ｓ中添加有限个节点，使得Ｓ中的节点构成连通 机等待Ｔ时间，丁是０与最大停留时间ＰａｕｓｅＴｉｍｅ之 子图，此时Ｓ称为连通支配集。 间的随机数。利用设定不同的最大、最小速率和最大 基于上述定义，下面给出４种典型算法的描述： 停留时间这三个参数，可以调整出不同的移动模型来 （１）最小ＩＤ算法：最小ＩＤ算法是一种简单的分簇 模拟自组网。 算法。每个节点分配唯一的ＩＤ，相邻节点中具有最小 ２．２参数设置和评价参数 ＩＤ的节点作为簇头。这种分簇算法计算量小，实现方 在对上述４个算法进行仿真测试中，设置的节点 便，算法收敛较快。最小ＩＤ算法的簇头更新的频率较 个数为３０个，节点的最小移动速度为１（单位距离／单 慢，维护簇所需花费的开销较小。该算法的缺点是较 位时间），节点的最大移动速度为３０（单位距离／单位 小ＩＤ的节点频繁作为簇头，将使这些节点能量很快耗 时间），最大停留时间为５（单位时间），而节点的传输 尽，从而构成网络出现分割，该算法不具有扩展能力。 范围从５到８０（单位距离）变化，程序运行１００个单位 （２）最大连通度算法：该算法可以尽可能地减少簇 时间后把采集到的簇头数Ｃ、单位时间内节点重人簇 的数目。节点之间通过交互信息掌握邻居节点的数 的次数 、单位时间内簇头构成的支配集更新的次数 目，即节点的度。再以最小ＩＤ式算法为基础，把具有 Ｕ记人数据库中。图１为仿真程序运行的界面。 最大度的节点备选为簇头，当度数相同时则选择ＩＤ最 ２．３性能分析 小的节点作为簇头。该算法的优点在于簇 的数目较少，有利于减少分组时延。但是 对于部分簇内成员密度较大，由于共享信 道，就会造成每个用户可用的带宽非常有 限，从而使整体的网络性能并不理想。 （３）基于节点权重分簇算法：每个节点 按照约定计算自己的权重，并通告给其邻 居，节点之间按照权重最大原则选取节点 作为簇头。典型的计算权重方法是根据节 点的移动速率，移动速度越快，分配的权重 越低。基于移动速率的算法可以明显减少 簇头更新频率。但此类算法的缺点是为了 节点权重的更新，需要频繁地计算和更新 权重，从而增加开销。 （４）自适应分簇算法：影响网络性能的 因素是多方面的，比如带宽、能量等，因此， 需要一种自适应的机制来实现联合的优 化，使得节点能对网络状态的变化及时响 图１仿真界面 维普资讯 http://www.cqvip.com ・９４・ 计算机技术与发展 第ｌ７卷 参考文献［３］中采用的仿真性能评价参数，我们在 仿真中同样考虑了分簇的簇头数Ｃ、单位时间内节点 运行，将最终结果进行平均，得到了几个算法的性能仿 真结果，并进行了分析。研究也表明，分簇算法在自组 网的性能优化、节能策略、密钥分配和管理等多个领域 重入簇的次数Ｊ和单位时间内簇头构成的支配集更新 的次数Ｕ。 有重要的应用，我们将根据这些仿真数据开展下一阶 通过设置随机种子，对程序进行了５０次的仿真实 段新的研究。 验，并取平均值。从图２看出，簇头数随节点 ３０．００ 传输范围的增加而减少，并且当传输范围大 ， 。。 于８０后，簇头数的变化速度变慢，最终会收 敛到１。因为节点的传输范围越大，簇的覆乞 盖范围也越大，最终一个簇头将覆盖所有节蒙坫・ｏｏ 点。此外，ＭＡＸＤＥＧＲＥＥ算法的簇头数明显 １０．００ 低于其他算法。 ５．ｏｏ 再观测节点的传输范围对节点重入簇 ０．００ 次数Ｊ的影响，如图３所示。从图中看出，Ｊ ０ ５ １０ Ｉ５ ２０ ２５ ３０ ３５ ４０ ４５ ５０ ５５ ６０ ６５ ７０ ７５ ８０ 随传输范围的增加先变大后变小。因为当节 传输范围（米） 点传输范围较低时，簇数目较多，簇内节点 图２簇头数随传输范围的变化 很少，甚至只有一个簇头，此时节点离开原 。・４。 簇的概率较小。当传输范围增加并在传输范 。・３５ 围为１５～２５之间时达到最大值。此时簇内 ０＿３０ 节点的关联度较低，随后Ｊ开始下降。这是 ０．２５ 因为簇的覆盖范围逐渐增大，节点移出原簇 鬓 。 ｏ．－ｓ 的概率减少，该仿真结果同文献［３］在数值 。・ｌ。 上有所不同，但其基本趋势是一致的。 。・０５ 从图４可以看出，在所有算法下单位时 ０．００ 间内支配集更新次数Ｕ的变化规律相同： ５ １０ Ｉ５ ２０ ２５ ３０ ３５ ４０ ４５ ５０ ５５ ６０ ６５ ７０ ７５ ８０ 当节点传输范围很小时，Ｕ很小，随着传输 传输范围（米） 范围增加，Ｕ也逐渐增大，当传输范围达到 图３重入簇次数随传输范围的变化 ５～１５之间时，Ｕ达到最大值；当传输范围 Ｉ＿００ ０．９Ｏ 继续增加时，Ｕ开始减小并逐渐趋向于０。 ｎ ８０ ，， Ｉ＼Ｉ 一 曲 造成Ｕ这种变化的原因如下：当节点传输 ｎ ７０ ｆ ＼、． ＋。 范围很小时，很大比例的节点成为簇头，并 ｎ ６ｏ ｆ 且簇内的节点数很少（很多簇只有一个簇头 ｎ ５０ ｆ ＼一刖ｗ 节点）。在这种情况下，节点移出原簇构成的 毒０．４０ ／ｔ 统治集的覆盖范围（统治域）的概率很小， ０．３０ Ｘ ． — 支配集更新频率很低。当传输范围增加时， ０．２０ Ｉ：： ０．１０ 一 簇头数减少，簇头能够覆盖所有节点的能力 一．．．．．．．．．．．．．． 圣 也随之降低，较容易移出支配集。但是随着 ｎ ００ ｌ ５ ｌ０ ｌ５ ２０ ２５ ３０ ３５ ４０ ４５ ５０ ５５ ６ｏ ６５ ７０ ７５ ８０ 传输范围的持续增加，尽管簇头数减少了， 传输范 米） 簇头的覆盖范围增加的更为明显，节点移出 图４ 支配集更新次数随传输范围的变化 支配集的概率开始减小，并最终趋向于０。 参考文献： ３ 总 结 ［１】 Ａｂｏｌｈａｓａｎ Ｍ，Ｗｙｓｏｃｋｉ Ｔ，Ｄｕｔｋｉｅｗｉｃｚ Ｅ，ｅｔ ａ１．Ａ ｒｅｖｉｅｗ ｏｆ ｒｏｕｔｉｎｇ ｐｒｏｔｏｃｏｌｓ ｆｏｒ ｍｏｂｉｌｅ ａｄ ｈｏｃ ｎｅｔｗｏｒｋｓ［Ｃ］／／Ａｄ Ｈｏｃ 文中通过Ｄｅｌｐｈｉ设计了自组网的一个典型分簇算 Ｎｅｔｗｏｒｓｋ．【ｓ．１．］：Ｅｌｓｅｖｉｅｒ Ｐｒｅ．￣，２００４：ｌ一２２． 法，即基于最小ＩＤ、最大连接度、节点权值和自适应按 １２ Ｊ Ｒｕｂｉｎ Ｉ，Ｂｅｈｚａｄ Ａ，Ｊｕ Ｈ，ｅｌ ａ１．Ａｄ Ｈｏｃ Ｗｉｒｅｌｅｓｓ Ｎｅｔｗｏｒｋｓ 需加权分簇算法。通过算法的设计，经过多次的仿真 （下转第９８页） 维普资讯 http://www.cqvip.com ・９８・ 计算机技术与发展 第ｌ７卷 表３基于ＧＡ算法的ＳＶＭ参数选择结果 数据集 ｂａｎａｎａ ｓｐｌｉｃｅ ４ 总 结 采用蚁群算法来进行ＳＶＭ模型的参数选择。从 实验的结果可以看出，蚁群算法较之遗传算法具有更 好的效果，不论是分类准确率还是效率上都有一定的 最优ｃ，ｙ 最优分类 准确率 ８７ １４％ ６ｌ ９３％ 平均运 行时问 ８３６．５Ｓ ４６Ｉｓ （４９６ ０００，ｌ Ｏ６３３） （１３８．６０９．０，１００１） ｎ ｗａｖｅｔｏｍｌ ｍ眯 （２７７ ３８２，０．２４８５） （１１７．５００，０．１） （１５４．５００，０．１１９８） ８６．９５％ ８８ ９１％ ９７．８２％ １０５６．１Ｓ ｌｏ３．５ｓ １４２３ ３ｓ 提高。下一步的工作是尝试采用其他的性能估计方法 如：ＧＡＣＶ，Ｒａｄｉｕｓ～Ｍａｒｇｉｎ ｂｏｕｎｄ等作为目标函数，进 行进一步的比较研究。 参考文献： ［１］ＣｈｅｎＰｅｎｇ—Ｗｅｉ，Ｗａｎｇ Ｊｕｎｇ—Ｙｉｎｇ，ＬｅｅＨａｌｍ—Ｍｉｎｇ．Ｍｏｄ． ｅｌ Ｓｅｌｃｔｅｉｏｎ ｏｆ Ｓ Ｍｓ Ｕｓｉｎｇ ＧＡ Ａｐｐｒｏａｃｈ［Ｃ］／／Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｊｏｉｎｔ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｎｅｕｒａｌ Ｎｅｔｗｏｒｋｓ ２００４． Ｈｕｎｇａｒｙ：ＩＥＥＥ，２００４：２０３５—２０４０． 群算法进行ＳＶＭ模型选择取得了较好的效果，它能 在较短的时间寻找到最优参数，而且最终所得的分类 准确率与采用ＧＡ算法所得到的最优分类准确率相 当，在大部分情况下还有所提高。 图２是在ｔｒｅｅ数据集上，利用遗传算法和蚁群算 法１０次寻参后，所得分类器分类准确率的比较图。 ＯＯ． ［２］Ｘｕ Ｐ，Ｃｈａｎ Ａ Ｋ．Ｓｕｐｐｏｎ ｖｅｃｔｏｒ ｍａｃｈｉｎｅ ｆｏｒ ｍｕｌｔｉ—ｄａｓｓ ｓｉｇ． 分 类 准 ｈａｌ ｃｌａｓｓｉｉｆｃａｔｉｏｎ ｗｉｔｈ ｕｎｂａｌａｎｃｅｄ ｓａｍｐｌｅｓ［Ｃ］／／Ｐｒｏｃｅｅｄｉｇｓｎ ｏｆ ｔｈｅ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｊｏｉｎｔ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｎｅｕｒａｌ Ｎｅｔｗｏｒｋｓ ２００３． Ｐｏｒｔｌａｎｄ：ＩＥＥＥ，２００３：１１１６—１１１９． ８Ｏ． ６０． ４０． 确 室 ２Ｏ．Ｏ． ［３］ Ｘｕ Ｐ，Ｃｈａｎ Ａ Ｋ．Ａｎ ｅｆｆｉｃｉｅｎｔ ａｌｇｏｒｉｔｈｍ ｏｎ ｍｕｌｔｉ—ｃｌａｓｓ ｓｕｐ． １ ２ ３ ４ ５ ６ ７ ８ ９ １Ｏ ｐｏｒｔ ｖｅｃｔｏｒ ｍａｃｈｉｎｅ ｍｏｄｅｌ ｓｅｌｃｔｅｉｏｎ［Ｃ］／／Ｐｒｏｃｅｅｄｉｇｓｎ ｏｆ ｔｈｅ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｊｏｉｎｔ Ｃｏｒｄｅｒｅｎｃｅ ｏｎ Ｎｅｕｒａｌ Ｎｅｔｗｏｒｋｓ ２００３． Ｐｏｒｔｌｎｄ：ＩａＥＥＥ，２００３：３２２９—３２３２． ■ＧＡ算法 ■蚁群算法 运行次数 图２遗传算法和蚁群算法寻参比较图 从图中可以看出，１０次运行中利用蚁群算法所得 ［４］黄景涛，马龙华，钱积新．一种用于多分类问题的改进支持 向量机［Ｊ］．浙江大学学报：工学版，２００４，３８（１２）：１６３３— １６３６． 的ＳＶＭ分类器，最优分类准确率和平均分类准确率 都要优于用遗传算法所得的结果。 除此之外，在实验当中还发现使用Ｊｏａｃｈｉｍｓ方法 的Ｅ 作为目标函数估算错误率时较为准确，仍然 以ｔｒｅｅ数据集为例，图３是在其上用蚁群算法寻找参 数时的估算错误率与测试错误率（实际错误率）的曲线 图。从图中可以看出两者的变化趋势基本一致。 １００．００％ ，、， ［５］董春曦，饶鲜，杨绍全，等．支持向量机参数选择方法研 究［Ｊ］．系统工程与电子技术，２００４，２６（８）：１１１７—１１２０． 【６ Ｊ Ｊｏａｅｈｉｍｓ Ｔ．Ｅｓｔｉａｔｉｍｇ ｔｈｅ ｇｅｎｅｒａｌｎｉｚａｔｉｏｎ ｐｅｒｆｏｒｍａｎｃｅ ｏｆ ａｎ ＳＶＭ ｅｉｃｆｉｅｎｔｌｙ［Ｃ］／／Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ １７ｔｈ Ｉｎｔｅｒｎａｔｉｏｎａｌ ｏｎＣｆｅｒｅｎｃｅ ｏｎ Ｍａｃｈｉｎｅ Ｌｅａｒｎｉｇ．Ｓａｎ Ｆｒａｎｎｃｉｓｃｏ：Ｍｏｒｇａｎ， ２０００：４３１—４３８． ［７］ 贺益君，俞欢军，陈德钊．基于募集机制的连续蚁群系统及 其应用［Ｊ］．浙江大学学报：工学版，２００６，４０（５）：７４８～７５２． ［８］孙学勤，刘丽，付萍，等．一种连续空间优化问题的蚁 ８０．００％ ６０．００％ 群算法及应用［Ｊ］．计算机工程与应用，２００５，４１（３４）：２１７ 茹４０．００％ ２０．００％ ０．００％ ２２０． ［９］Ｋｅｅｒｔｉｈ Ｓ Ｓ．Ｂｅｎｃｈｍａｒｋ ｄａｔａｓｅｔｓ［ＥＢ／ＯＬ］．２００１—０９—１２． ｈｔｔｐ：／／ｇｕｐｐｙ．ｍｐｅ．ｎｔｉｓ．ｅｄｕ．ｓｇ／ｍｐｅｓｓｋ／ｃｏｍｐａｒｉｓｏｎ．ｓｈｔｍ１． 二：＝ 基霆耋１ 。４ —８¨０ ” 。姒 ■一测试错误率 ［１０］Ｊａｃｏｉｈｒｎｓ Ｔ．ＳＶＭｌｉｇｈｔ Ｓｕｐｐｏｒｔ Ｖｅｃｔｏｒ Ｍａｃｈｉｎｅ［ＥＢ／ＯＬ］． ２００４～０２—０９．ｈｔｔｐ：／／ｓｖｒｎｌｉｇｈｔ．ｊａｃｈｏｉｍａ．ｏｒｇ． 图３ ｔｒ＆数据集上预测误差与测试误差的曲线图 —－ 一＋—＋－＋ －＋一＋一—‘ 一＋一＋ ＋－＋—＋一＋－＋－＋－＋－＋－＋－＋－＋—＋ ＋一＋－＋－＋ －—‘ —‘ ＋一＋一＋－＋－＋－＋ （上接第９４页） ｗｉｔｈ Ｍｏｂｉｌｅ Ｂａｃｋｂｏｎｅｓ［Ｃ］／／ｐｒｏｃｅｅｄｉｇｓｎ ｏｆ ＩＥＥＥ Ｉｎｔｅｍａ ｔｉｏｎａｌ Ｓｙｍｐｏｓｉｕｍ ｏｎ Ｐｅｒｓｏｎａｌ，Ｉｎｄｏｏｒ ａｎｄ Ｒａｄｉｏ Ｃｏｍｍｕｎｉａ．ｃ ｒｉｔｈｍ（ｗＣＡ）ｆｏｒ Ａｄ ｈｏｅ ｎｅｔｗｏｒｋｓ［Ｃ］／／ｐｒｏｃｅｅｄｉｇｓｎ ｏｆ ＩＥＥＥ ＧＵ）ＢＥ（ ｌＭ ２０００．Ｓａｎ Ｆｒａｎｃｉｓｃｏ：ＩＥＥＥ Ｐｒｅｓｓ，２０００： １６９７—１７０１． ｔｉｏｎｓ（ＰＩＭＲＣ） Ｂａｒｃｅｌｏｎａ，Ｓｐａｉｎ：ＩＥＥＥ Ｐｒｅｓｓ，２００４：５６６— ５７３． 【５】 Ｂｅｔｔｓｔｅｔｔｅｒ Ｃ，Ｒｅｓｔａ Ｇ，Ｓａｎｔｉ Ｐ． Ｆｈｅ Ｎｏｄｅ Ｄｉｓｔｒｉｂｕｔｉｏｎ ｏｆ ｔｈｅ Ｒａｎｄｏｍ Ｗａｙｐｏｉｎｔ Ｍｏｂｉｌｉｔｙ Ｍｏｄｅｌ ｆｏｒ Ｗｉｒｅｌｅｓｓ Ａｄ Ｈｏｅ Ｎｅｔ． ［３］王海涛．移动Ａｄ ｈｏｅ网络的分簇算法及性能比较［Ｊ］．北京 邮电大学学报，２００４，２７（１）：９３—９７． 【４ Ｊ Ｃｈａｔｔｅｒｊｅｅ Ｍ，Ｄａｓ Ｓ Ｋ，Ｔｕｒｇｕｔ Ｄ．Ａ ｗｅｉｇｈｔｅｄ ｃｌｕｓｔｅｒｉｎｇ ａｌｇｏ． ｗｏｒｋｓ［Ｊ］．ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｍｏｂｉｌｅ Ｃｏｍｐｐｔｉｇ。ｎ２００３．２ （３）：２５７—２６９．