打印本文 打印本文  关闭窗口 关闭窗口  
研究发现蚂蚁群行为酷似互联网传输协议
作者:常丽君  文章来源:科技日报  点击数  更新时间:2012/9/5 22:04:43  文章录入:ahaoxie  责任编辑:ahaoxie

  表面上,蚂蚁和互联网好像没什么共同之处,但二者之间却存在惊人的相似性。

  据物理学家组织网近日报道,斯坦福大学研究人员发现,一种叫做收获蚁的蚂蚁在决定派多少蚂蚁出去找食物时,所用方法和互联网TCP(传输控制协议)确定还有多少带宽可用来传输数据的方法极为相似。相关论文发表在《公共科学图书馆·计算生物学》杂志上。

  斯坦福大学生物学教授黛博拉·戈登与计算机科学教授、研究网络文件传输的专家巴拉基·普拉巴卡尔合作,研究一个蚁群在派觅食蚁出去找食物时,它们是怎样做决定的。“从本质上说,蚂蚁确定能得到多少食物的方法,和传输文件时TCP确定还有多少带宽可用的算法是一样的。”普拉巴卡尔说。

  TCP是在互联网上管理数据、控制拥堵的一种算法,在整体上允许早期网络从几十个结点扩增到今天的数十亿用户。其工作原理是:A作为源头,传一份文件到目的地B,此文件被分解为若干小包,B每接到一个小包,发送一个确认给A,表示文件已经到达。

  这种反馈回路让TCP能畅通运行而避免拥堵:如果返回确认的速度比数据发送速度慢,表示已没有多少带宽,源头控制的数据传输就会相应地慢下来;如果返回确认更快,源头就会加快传输速度。这一过程决定了还有多少带宽和数据传输速度。

  收获蚁的觅食行为与此很相似。戈登发现,收获蚁离开巢穴出去觅食的速度和能获得的食物多少有关(相当于可用带宽)。一般情况,觅食蚁只有找到食物才会回巢。如果食物丰富,它们返回的速度快,就会有更多同伴出去觅食;如果觅食速度变慢,甚至有些同伴开始空手而归,觅食就可能停止。

  普拉巴卡尔写下了一只蚂蚁觅食的算法(TCP—影响算法),并预测觅食行为取决于可找到的食物数量,戈登则通过实验来控制觅食蚁返回的速度。他们发现,TCP—影响算法几乎与实验中蚂蚁的行为精确吻合。

  他们还发现,蚂蚁还遵循TCP的两个阶段。一个叫缓慢启动,用于描述源头在开始发送一个大波包时需要计算的带宽;同样,收获蚁在开始觅食时,会先派些蚂蚁去看看能找到的食物多不多,然后再根据情况增加或减少外派蚂蚁的速度。另一阶段叫超时,此时数据传输连接中断,源头停止发送文件包;同样,如果一些觅食蚁返回巢穴的速度超过20分钟,就没有蚂蚁再出去。

  “蚂蚁早就发现了我们现在所知的算法,它们一直这么做了上百万年。”普拉巴卡尔说,如果上世纪70年代发现这一点的话,那时TCP还没写出来,收获蚁就能影响互联网的设计。

  戈登认为研究蚁群行为有助于我们设计互联网系统。地球上的蚂蚁有1.1万种,它们生活在不同的地方,处理着各种生态问题。“蚂蚁已经进化出了处理我们意想不到的问题的能力。从计算的角度来说,每一只蚂蚁的能力是有限的,但蚁群集体却能完成复杂的任务。蚂蚁算法必然是简单的、分布式的而且可升级,这正是我们在大型分布式设计系统中所需要的特性。理解蚂蚁如何管理自身行为,有助于发现更多对互联网算法有益的应用。”戈登说。(常丽君)

打印本文 打印本文  关闭窗口 关闭窗口