总第２４８期 计算机与数字工程 Ｃｏｍｐｕｔｅｒ＆Ｄｉｇｉｔａｌ Ｅｎｇｉｎｅｅｒｉｎｇ Ｖｏ１．３８ Ｎｏ．６ ２２ ２０１０年第６期 优化型蚁群算法在旅行商问题中的应用研究 于海平杨艳霞 武汉４３００８３） （武汉科技大学城市学院信息工程学部摘要针对基本蚁群算法的搜索时间长和局部收敛等现象，提出一种用于求解旅行商问题（ＴＳＰ）的优化型蚁群算 法，该算法有效地将最大最小蚁群算法（ＭＭＡＳ）和遗传算法（ＧＡ）相结合，一方面在很大程度上缩短了算法的寻优时间；另 一方面有效地避免了算法的早熟停滞现象。利用ＭＡＴＬＡＢ对多种ＴＳＰ问题进行仿真研究，实验结果证明了优化型蚁群 关键词最大最小蚁群算法；信息素；旅行商问题；遗传算法 ＴＰ３０１．６；ＴＰ１８ 算法在性能上优于ＭＭＡＳ和ＧＡ。 中图分类号Ｒｅｓｅａｒｃｈ ｏｎ Ａｐｐｌｙｉｎｇ Ｏｐｔｉｍｉｚａｔｉｏｎ—ｂａｓｅｄ Ａｎｔ Ｃｏｌｏｎｙ Ａｌｇｏｒｉｔｈｍ ｉｎ ｔｈｅ Ｔｒａｖｅｌｉｎｇ Ｓａｌｅｓｍａｎ Ｐｒｏｂｌｅｍ Ｙｕ Ｈａｉｐｉｎｇ Ｙａｎｇ Ｙａｎｘｉａ （Ｄｅｐａｒｔｍｅｎｔ ｏｆ Ｉｎｆｏｒｍａｔｉｏｎ Ｅｎｇｉｎｅｅｒｉｎｇ，Ｗｕｈａｎ Ｕｎｉｖｅｒｓｉｔｙ ｏｆ Ｓｃｉｅｎｃｅ ａｎｄ Ｔｅｃｈｎｏｌｏｇｙ Ｃｉｔｙ Ｃｏｌｌｅｇｅ，Ｗｕｈａｎ ４３００８３） Ａｂｓｔｒａｃｔ Ａｉｍｉｎｇ ａｔ ｔｈｅ ｐｈｅｎｏｍｅｎａ ｓｕｃｈ ａｓ ｓｅａｒｃｈｉｎｇ ｆｏｒ ａ ｌｏｎｇ ｔｉｍｅ ａｎｄ ｔｈｅ ｌｏｃａｌ ｃｏｎｖｅｒｇｅｎｃｅ ｏｆ ａｎｔ ｃｏｌｏｎｙ ａｌｇｏ— ｒｉｔｈｍ，ｔｈｉｓ ｐａｐｅｒ ｐｒｅｓｅｎｔｓ ａ ｎｅｗ ｏｐｔｉｍｉｚａｔｉｏｎ ａｎｔ ｃｏｌｏｎｙ ａｌｇｏｒｉｔｈｍ ｔｏ ｓｏｌｖｅ ｔｒａｖｅｌｉｎｇ ｓａｌｅｓｍａｎ ｐｒｏｂｌｅｍ．Ｉｔ ｅｆｆｅｃｔｉｖｅｌｙ ａｎｔ ｃｏｌ— ｏｎｙ ａｌｇｏｒｉｔｈｍ ａｎｄ ｇｅｎｅｔｉｃ ａｌｇｏｒｉｔｈｍ ｃｏｍｂｉｎｅｄ，ｏｎ ｔｈｅ ｏｎｅ ｈａｎｄ ａ ｌａｒｇｅ ｅｘｔｅｎｔ，ｔｈｅ ａｌｇｏｒｉｔｈｍ ｏｐｔｉｍｉｚａｔｉｏｎ ｔｏ ｓｈｏｒｔｅｎ ｔｈｅ ｔｉｍｅ；ｔｈｅ ｏｔｈｅｒ ｈａｎｄ，ｔｈｅ ａｌｇｏｒｉｔｈｍ ｗａｓ ｅｆｆｅｃｔｉｖｅ ｉｎ ａｖｏｉｄｉｎｇ ｐｒｅｍａｔｕｒｅ ｓｔａｇｎａｔｉｏｎ．Ｕｓｉｎｇ ｍａｔｌａｂ ｓｉｍｕｌａｔｉｏｎ ｏｆ ｔｈｅ ＴＳＰ，ｔｈｅ ｅｘｐｅｒｉｍｅｎｔ ｐｒｏｖｅｓ ｔｈｅ ａｌｇｏｒｉｔｈｍ ｉＳ ｂｅｔｔｅｒ ｔｈａｎ ＭＭＡＳ ａｎｄ ＧＡ． Ｋｅｙ Ｗｏｒｄｓ ｍａｘ－ｍｉｎ ａｎｔ ｓｙｓｔｅｍ，ｐｈｅｒｏｍｏｎｅ，ｔｒａｖｅｌｉｎｇ ｓａｌｅｓｍａｎ ｐｒｏｂｌｅｍｓ，ｇｅｎｅｔｉｃ ａｌｇｏｒｉｔｈｍ Ｃｌａｓｓ Ｎｕｍｂｅｒ ＴＰ３０１．６：ＴＰ１８ ｌ 引言 蚁群算法（Ａｎｔ Ｃｏｌｏｎｙ Ｏｐｔｉｍｉｚａｔｉｏｎ）又称蚂 路径信息，最终将找出最优路径。 蚁群算法是一个关于信息素的正反馈过程。 它具有较强的鲁棒性、并行性以及易于与其他启发 算法相结合等优越性，被广泛应用于解决各种具有 ＮＰ难度的问题［】］，如旅行商问题（ＴＳＰ）、图形着色 问题（ＧＣＰ）和网格分割问题。 蚁算法，是一种用来在图中寻找优化路径的机率型 算法。它是意大利学者Ｍａｒｃｏ Ｄｏｒｉｇｏ等人首先提 出来的。具体过程如下：根据仿生学家的长期研究 发现蚂蚁并没有视觉，但在运动过程中会留下一种 ２Ｏ世纪９０年代以来，研究人员对蚁群算法进 行了不断的研究和改进，蚁群算法虽然可以解决诸 特殊的分泌物一信息素，后面的蚂蚁可根据前边走 过的蚂蚁所留下的信息素选择其要走的路径。一 条路径上的信息素越多，蚂蚁选择这条路径的概率 就越大。因此，在整个寻找最短路径过程中，虽然 如ＴＳＰ问题，但是普遍存在收敛速度慢、求解结果 容易陷入局部最优等缺陷。基于以上原因，本文提 出了一种新的优化型蚁群算法，并结合经典的ＴＳＰ 单个蚂蚁的选择能力有限，但通过信息素的作用， 蚂蚁群具有非常高的自组织性，蚂蚁之间通过交换 问题，找出了最优ＴＳＰ路径，相对于基本的蚁群算 法和遗传算法极大地缩短了算法的搜索时间。本 ＊收稿日期：２０１０年１月１９日，修回日期：２０１０年２月２３日 作者简介：于海平，女，硕士，讲师，研究方向：人＿Ｔ智能、数据挖掘。杨艳霞，硕士，讲师。 ２０１０年第６期 计算机与数字工程 文通过在ＭＡＴＬＡＢ７．０的平台下验证了这一算法 的有效性。 ２ ＴＳＰ问题描述 旅行商问题是一个经典的组合优化问题Ｅ ，问 题要求得到一条遍历所有给定城市的最短闭合路 径。属于ＮＰ难问题。随着城市数目的不断增加， 导致求解空间成指数级增长，通过穷举法根本无法 求解，因此用优化算法解决ＴＳＰ问题就十分必要。 下面是ＴＳＰ问题的提出。 ＴＳＰ问题可以简单描述如下：对于Ｎ个城市， 它们之间的距离已知，有一旅行商要从某一城市出 发走遍所有的城市，且每一个城市只能经过一次， 最后回到出发城市，问如何选择路线可使他所走过 的路程最短。该问题可以表示为：设有Ｎ个城市Ｃ 一｛Ｃ ，Ｃ ，Ｃ。，… ｝，给定Ｃ中任意两个城市问的 距离ｄ（Ｇ，Ｃｓ）一 ，１ Ｘ，Ｙ Ｎ，现在要找出一 个城市的排列，使得闭合路径长度为最小。 ３ 蚁群算法与最大最小蚁群算法 ３．１基本蚁群算法 蚂蚁是一种群体生活的昆虫，在巢穴和食物之 间，大部分蚂蚁总是往返于巢穴和食物之问最近的 路径上，那么蚂蚁是如何得知哪一条路径最短的 呢？经生物学家们的研究得知，蚂蚁在行进中不断 释放称之为信息素的东西，利用这种信息素，蚂蚁 可以相互通信、协同工作：路径上经过的蚂蚁越多， 信息素数量就越大，则该路径就越容易被选中；不 过，时间越长，信息素数量就越小，则该路径就不容 易被选择。最终所有蚂蚁就选择了最短路径，下面 以求解平面上ｎ个城市的ＴＳＰ问题为例，来具体 说明基本蚁群算法的原理ｌ＿５ 。 ｚ只蚂蚁在初始时刻，各条路径上的信息量均 相等（设为常数ｃ），蚂蚁在运动过程中根据各条路 径上的信息量决定转移方向，移动概率为： ，（ ）一｛ ∑［矗（ ） ・［ （ 若 ∈ｄ／ａｕｅｄ（ｋ） ￣ｋａｕｄ（ｋ） ） ０， 否则 （１） 从以上公式中可以看出：蚂蚁在选择转移路径 的时候，一方面选择路径较短，并且信息素浓度较 高的路径，随着时间的推移，以前留下的信息素逐 渐消逝，其中ｐ是轨迹的持久性（在０～１范围内）， 参数（１一ｐ）表示信息消逝的程度，经过 个时刻， 信息素要做如下调整： （ ＋ ）一（１－－ｐ）・△ ＋ｐ‘ （￡） （２） △ 一∑△ （３） 一１ △ 一 ｌ Ｌ ｋ ，若第ｋ只蚂蚁在本次循环中经过巧 【０， 否则 （４） 其中 表示各条路径上的初始信息素浓度值。 最终蚂蚁将按照移动概率选择城市，最后形成 一条封闭路径。当所有的蚂蚁完成闭合路径选择 后，则一次迭代结束，利用全局信息素更新路径的 信息量，再进行下一次的迭代，直到收敛或达到最 大迭代次数为止。下面是针对以上算法给出了主 要的参数说明如下： １）？ＩＦ／：蚂蚁的数目； ２） ：城市总数； ３）ｄ（ｉ，Ｊ）：城市ｉ和城市Ｊ之问的距离； ４） （￡）：ｔ时刻城市ｉ与城市Ｊ间的路径（ ，Ｊ） 上的信息素浓度。其中 （Ｏ）一Ｃ； ５） （ ）：状态转移概率。其中：ａｌｌｏｗｅｄ（ｋ） 一｛０，１，２，３，…， ～１｝一ｔａｂｕ（尼）表示蚂蚁下一步 允许选择的城市。Ｔａｂｕ（是）记录蚂蚁ｋ当前所走 过的城市；７７ ，（￡）表示路径（ ，Ｊ）距离ｄ（ ，Ｊ）的倒 数；ａ、 分别表示信息素和路径信息对转移概率的 影响程度。 ３．２最大最小蚁群算法（ＭＭＡＳ） 利用最优解信息能够改进算法性能，但是蚁群 优化算法中的贪婪式搜索却容易造成搜索的早期 停滞现象。为了既能改进算法性能，又能尽量避免 搜索停滞，Ｔｈｏｍａｓ Ｓｔｕｔｚｌｅ提出了ＭＭＡＳ算 法 ，并通过实验验证了它的性能。ＭＭＡＳ算 法是在基本蚁群算法基础上进行了许多改进之后 的算法，相对于基本的蚁群算法主要在下面三方面 不同： １）在算法运行期间为了找到最优解，更多地 利用最优解信息，即每次迭代后仅允许一只最优的 蚂蚁增加信息素，该最优蚂蚁可以是当前代最优 的，也可以是全局最优的。 ２）为了尽量避免搜索停滞现象，该算法对信 息素进行了，信息素 ∈［ ，Ｔｒｉｍ ］。 ３）此外，该算法将信息素初始化为 ，有利 于算法在最初阶段搜索到更多的解。 在搜索最短路径的过程中，基本蚁群算法有以 ２４ 于海平等：优化型蚁群算法在旅行商问题中的应用研究 第３８卷 下不足之处： 变异时就是把它变成０，反之亦然。 １）搜索时间较长，蚁群中每个个体的运动是 随机的，虽然通过信息素的交换能向着最优路径进 ＴＳＰ问题是典型的、易于描述却难以处理的组 合优化问题，遗传算法解决这类问题是比较有效 的。但是，在实际应用中遗传算法受编码、迭代次 数、种群规模的，造成种群多样性和选择性压 化，但当群体规模较大的时候，很难再杂乱无章的 路径中找出一条最优路径。 ２）蚁群算法容易出现早熟停滞现象。这样就 造成了不利于发现更优的解空间。 针对以上两点的不足之处，提出了一种优化型 力的冲突，即强选择性压力导致遗传搜索过早收 敛，强种群多样性导致遗传搜索效率低下，因此需 要研究更好的方法来解决ＴＳＰ问题。 混合蚁群算法（Ｏｐｔｉｍｉｚｅｄ Ｈｙｂｒｉｄ Ａｎｔ Ｃｏｌｏｎｙ， ＯＨＡＣ）。 ３．３遗传算法 遗传算法（Ｇｅｎｅｔｉｃ Ａｌｇｏｒｉｔｈｍ，ＧＡ）［６－７，１０］的基 本思想是基于Ｄａｒｗｉｎ进化论和Ｍｅｎｄｅｌ的遗传学 说的。它是计算数学中用于解决最优化的搜索算 法，是进化算法的一种。其主要特点是群体搜索策 略和群体中个体之问的信息交换，搜索不以梯度信 息为基础。它尤其适用于处理传统搜索方法难于 解决的复杂和非线性问题，可广泛应用于组合优 化、机器学习、自适应控制、规划设计和人工生命等 领域。 遗传算法ＧＡ把问题的解表示成“染色体”，在 算法中也即是以二进制编码的串。并且，在执行遗 传算法之前，给出一群“染色体”，也即是假设解。 然后，把这些假设解置于问题的“环境”中，并按适 者生存的原则，从中选择出较适应环境的“染色体” 进行复制，再通过交叉，变异过程产生更适应环境 的新一代“染色体”群。这样，一代一代地进化，最 后就会收敛到最适应环境的一个“染色体”上，它就 是问题的最优解。 遗传算法的三个重要步骤是： １）选择（Ｓｅｌｅｃｔｉｏｎ） 这是从群体中选择出较适应环境的个体。这 些选中的个体用于繁殖下一代。故有时也称这一 操作为再生（Ｒｅｐｒｏｄｕｃｔｉｏｎ）。由于在选择用于繁 殖下一代的个体时，是根据个体对环境的适应度而 决定其繁殖量的，故而有时也称为非均匀再生（ｄｉｆ— ｆｅｒｅｎｔｉａｌ ｒｅｐｒｏｄｕｃｔｉｏｎ）。 ２）交叉（Ｃｒｏｓｓｏｖｅｒ） 这是在选中用于繁殖下一代的个体中，对两个 不同的个体的相同位置的基因进行交换，从而产生 新的个体。 ３）变异（Ｍｕｔａｔｉｏｎ） 这是在选中的个体中，对个体中的某些基因执 行异向转化。在串ｂｉ中，如果某位基因为ｌ，产生 ４优化型混合蚁群算法 ４．１ ０ＨＡＣ算法思想 （）ＨＡＣ算法思想就是在蚁群算法的基础上结 合最大最小信息素算法（ＭＭＡＳ）和遗传算法，来弥 补以上基本蚁群算法的缺陷。最大最小信息素算 法在每次迭代路径上增加的最大信息素为１／Ｌ （ ），其中Ｌ（ｓ ）为对应全局最好解的路径长度， 更新最好解时，同时更新 。 ，Ｚ＇ｍａ ，其中Ｚ＇ｍａ 与轨迹 的持久性 以及Ｌ（ｓ ）成反比，而与精英蚂蚁的 数目成正比，这样就可以解决基本蚁群算法带来的 早熟停滞现象。另一方面，针对遗传算法中的三个 过程：选择、交叉、变异来进行局部调整，之前遗传 算法中的交叉式按照一定概率选中种群中的多个 染色体，对个体基因型进行两两交叉，如果需要交 叉的染色体是奇数，则舍去，也就是说在交叉的过 程中交叉片段相同，与蚁群算法结合后，选取的交 叉片段选取一个随机数。这样有利于提高染色体 的应变能力，在解决ＴＳＰ问题上可以缩短问题搜 索的时间，从而提高搜索效率。 ４．２ ＯＨＡＣ算法的基本步骤 ＯＨＡＣ算法的步骤如下： １）状态初始化，初始化参数种群：１００；最大迭 代数：５０００；交叉概率：０．５；变异概率：０．１，ａ一３， 一１，ｚ＇０—０．０００１，ｐ一０．６；Ｑ＝３ｏｏ； ２）将蚂蚁随机放置各个城市节点上，并将第志 只蚂蚁的出发城市加入ｔａｂｕ（走）表； ３）启用状态转移规则，使用上面式（２）更新信 息素。直到所有蚂蚁均完成解路径的构造； ４）记录当前迭代产生的最优解；并形成新的 蚂蚁群体； ５）给出随机函数，执行遗传算法的交叉操作， 同时实施最有保留策略； ６）应用全局信息素更新规则； ７）判断是否满足算法终止条件，如果满足则 停止，否则转２）。 ２０１０年第６期 计算机与数字工程 ２５ ５ 仿真结果 选择的原则是蚂蚁总数是城市总数的２／３，ｃｉｔｙ＝＝＝ ３３，ａｎｔ＝＝＝２２；ｃｉｔｙ一７５，ａｎｔ一５０；ｃｉｔｙ一１００，ａｎｔ一 本次实验的运行环境如下：ＡＭＤ Ａｎｔｈｏｎ ７０。仿真实验结果如图１～图３所示。 ３．０Ｈｚ，４Ｇ内存，Ｗｉｎｄｏｗｓ ＸＰ Ｐｒｏｆｅｓｓｉｏｎａｌ系统； 表１仿真ＴＳＰ实验数据 用Ｍａｔｌａｂ７．０版本仿真实现。仿真实例中的参数 配置如下：信息挥发率选取０．４，交叉概率：０．５；变 异概率：０．１，信息指数和启发式指数分别选取３， １，初始化信息素浓度取值为０．５，迭代次数选取 ２００。根据城市数目不同，选取的蚂蚁个数也不同， １Ｏ０ ８０ ６０ ４０ ２０ ０ 图１ ＯＨＡＣ算法发现的 图２ ＯＨＡＣ算法发现的 图３ ＯＨＡＣ算法发现的 ３３个城市路径 ７５个城市路径 ｉ００个城市的路径 ６ 结语 ｒｅｃｅｎｔ ｔｒｅｎｄｓ［Ｊ］ Ｐｈｙｓｉｃｓ ｏｆ Ｌｉｆｅ Ｒｅｖｉｅｗｓ，２００５，２（４） ３４３～３７３ 本文结合经典的ＴＳＰ问题设计了优化型蚁群 Ｅ５］ＳＴＢＴＺＩ Ｅ Ｔ，ＨＯＯＳ Ｈ，Ｈ．ＭＡＸ２Ｍ ＩＮ ａｎｔ ｓｙｓｔｅｍ 算法，通过仿真实验证明，此算法对于旅行商问题 ［Ｊ］．Ｆｕｔｕｒｅ Ｇｅｎｅｒａｔｉｏｎ Ｃｏｍｐｕｔｅｒ Ｓｙｓｔｅｍｓ，２０００，１６ 具有比较高的性能。同时也有效的弥补了基本蚁 （８）：８８９～９１４ 群算法中带来的搜索时间长、容易陷入局部最优等 ［６］黄立君，许永花．遗传算法和蚁群算法融合求解ＴＳＰ 不足。但是改进的蚁群群算法还有待于更细致的 ［Ｊ］．东北农业大学学报，２００８，３９（４）：１。９～１１３ ［７］Ｃｈｒｉｓｔｏｐｈｅｒ Ｍａｒｋ Ｃｏｌｅｍａｎ．Ｉｎｖｅｓｔｉｇａｔｉｏｎ ｏｆ Ｓｉｍｕｌａｔｅｄ 研究，比如说，在实验中的一些参数的设置上，参数 Ａｎｎｅａｌｉｎｇ，Ａｎｔ－Ｃｏｌｏｎｙ Ｏｐｔｉｍｉｚａｔｉｏｎ，ａｎｄ Ｇｅｎｅｔｉｃ Ａ１一 取值不同，对收敛的速率上影响很大。因此在以后 ｇｏｒｉｔｈｍｓ ｆｏｒ Ｓｅｌｆ＿Ｓｔｒｕｃｔｕｒｉｎｇ Ａｎｔｅｎｎａｓ［Ｊ］． ＩＥＥＥ 的工作中还有待于做详细的研究。 Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ ａｎｔｅｎｎａｓ ａｎｄ Ｐｒｏｐａｇａｔｉｏｎ，２００４，５２ 参考文献 （４）：１００７￣１０１３ Ｅ１］段海滨．蚁群算法原理及其应用［Ｍ］．北京：科学出版 ｒ－８］Ｒ．Ｔｅｈｒａｎｉ，Ｆ．Ｋｈｏｄａｙａｒ．Ｏｐｔｉｍｉｚａｔｉｏｎ ｏｆ ｔｈｅ Ａｒｔｉｆｉ 社，２００５：２０￣４５ ｃｉａｌ Ｎｅｕｒａｌ Ｎｅｔｗｏｒｋｓ ｕｓｉｎｇ Ａｎｔ Ｃｏｌｏｎｙ Ａｌｇｏｒｉｔｈｍ ｔｏ ［２３ Ｃｏｍｐｕｔａｔｉｏｎ ａｎｄ Ｓｉｍｕｌａｔｉｏｎ Ａｎａｌｙｓｉｓ ｏｆ ａ Ｋｉｎｄ ｏｆ Ｍｕｌ— Ｐｒｅｄｉｃｔ ｔｈｅ Ｖａｒｉａｔｉｏｎ ｏｆ Ｓｔｏｃｋ Ｐｒｉｃｅ Ｉｎｄｅｘ［Ｊ］．Ｊｏｕｒｎａｌｓ ｔｉｐｌｅ Ｔｒａｖｅｌｉｎｇ Ｓａｌｅｓｍａｎ ｐｒｏｂｌｅｍＥＪ］．Ｊｏｕｒｎａｌ ｏｆ Ｓｙｓ— ｏｆ Ａｐｐｌｉｅｄ Ｓｃｉｅｎｃｅｓ，２０１０，１０（３）：２２１～２２５ ｔｅｒｎ Ｓｉｍｕｌａｔｉｏｎ。２００９（２０）：４５～５Ｏ ［９］－ｒ．Ｓｔｉｉｔｚｌｅ，Ｈ．Ｈ．Ｈｏｏｓ．Ｍａ￣Ｍｉｎ Ａｎｔ Ｓｙｓｔｅｍ［Ｊ］．Ｆｕ— Ｅ３］李将军，叶仲泉，宫子风．改进蚁群算法及其仿真研究 ｔｕｒｅ Ｇｅｎｅｒａｔｉｏｎ Ｃｏｍｐｕｔｅｒ Ｓｙｓｔｅｍｓ，２０００，１６（８）：８８９￣９１４ ［Ｊ］．计算机应用，２００８（２８）：９４￣９６ ［１Ｏ］周明，孙树栋．遗传算法原理及应用ＥＭ］．北京：国防工 ｒ４］ＢＩ ＵＭ Ｃ．Ａｎｔ ｃｏｌｏｎｙ ｏｐｔｉｍｉｚａｔｉｏｎ：Ｉｎｔｒｏｄｕｃｔｉｏｎ ａｎｄ 业出版社，２０００：４５￣５０ 钸｛ ； ’；． ．铞 秘 尔 带 乖 乖 绵 蟛 矫 铈 （上接第ｌ８页） ［４］张晓丽，韩芳溪，王睿．基于Ｖｏｒｏｎｏｉ图的无线传感器网 参考文献 络的节点调度机制［Ｊ］．计算机应用，２００６（６）：１９９￣２００ ［１］周培德．计算几何一算法设计与分析［Ｍ］．第２版．北 ［５］Ｌｉ ＸＹ，Ｗａｎ ＰＪ，Ｆｒｉｅｄｅｒ Ｏ．Ｃｏｖｅｒａｇｅ ｉｎ ｗｉｒｅｌｅｓｓ ａｄ 京：清华大学出版社，２００６ ｈｏｃ ｓｅｎｓｏｒ ｎｅｔｗｏｒｋｓ［Ｊ］．ＩＥＥＥ Ｔｒａｎｓ．ｏｎ Ｃｏｍｐｕｔｅｒｓ， ｒ２］ＡＫＹＩＩ Ｄ ＩＺ ＩＦ，ＳＵ ＷＩ ，ＳＡＮＫＡＲＡＳＵＢＲＡＭＡＮ ２００３，５２（６）：７５３～７６３ ＩＡＭ Ｙ，ｅｔ ａ１．Ａ ｓｕｒｖｅｙ ｏｎ ｓｅｎｓｏｒ ｎｅｔｗｏｒｋｓ［Ｊ］．ＩＥＥＥ ［６］张文哲，李明禄，伍民友．一种基于局部Ｖｏｒｏｎｏｉ图的目 ＣｏｍｍｕｎｉｃａｔｉｏｎｓＭａｇａｚｉｎｅ，２００２，４０（８）：１０２～１１４ 标穿越算法［Ｊ］．软件学报，２００７，１８（５）：１２４６￣１２５３ ［３］孙利民，李建中，等．无线传感器网络［Ｍ］．北京：清华大 Ｅ７］李克清．基于Ｄｅｌａｕｎａｒｙ三角剖分的目标穿越算法［ｊ］． 学出版社，２００５ 常熟理工学院学报，２００９（２）：９８～１００
