群体编程技术发展研究

赵冰阳

0 引言

群体智能这个概念来自对自然界中昆虫群体的观察，群体通过协作表现出的宏观智能行为特征被称为群体智能（swarm intelligence）。在计算机领域中，把一群具有计算和通信能力，在复杂物理环境中，完成特定任务的设备集合为群体（swarm）。对设备群体的行为预测和控制称为群体智能。群体智能的概念自1989年提出以来，各方面都出现了进展。

在算法方面， Dorigo在2004 年提出了由对受蚁群行为启 ACO（Ant colony optimization）算法， Karaboga 在 2005年提出了受蜂群行为启发的 ABC（Artificial bee colony algorithm）算法。PSO（particle swam optimization）算法由Eberhart博士和Kennedy博士基于鸟群觅食行为而提出，该算法概念简明、实现方便、收敛速度快、参数设置少，是 一种高效的搜索算法，近年来受到学术界的广泛重视。

在硬件平台方面，MEMS技术发展迅速。伯克利在99年就已经制造出毫米级别的机器人，这种机器人自我供电，拥有计算和通信能力，非常适合作为群体中的节点设备。

在编程方面，面对群体计算中的种种问题，人们的解决方式与1950解决传统编程中问题的方法相似。针对某种特定设备和特定环境，研究者都需要费力的去开发相关的程序，并且花大量的时间和经历反复测试以保证其性能。然而设备和需求一旦改变，就需要花大量经历重新进行开发和测试。这样的开发方式越来越无法跟上设备更新的速度。随着设备的价格越来越低而性能愈发强大，开发程序的开销开始代替设备开销，成了开发大规模群体程序的主要开销。开发者需要一套规范化的语言，开发方法和开发工具来应对群体程序开发的需求。群体编程语言需要能够描述一个群体的整体行为整体行而不过多的去关注每一个设备区实现这个过程的细节。它还需要让开发者在开发测试，以及使用的过程中能对非功能性属性比如能源消耗进行监控和调配。同时，研究者希望这种开发工程具有强大的可移植性以应对环境和设备的变化。

1 群体编程及语言的定义

群体的特性决定了群体编程语言与传统编程语言相比拥有自己的特性：

(1)分布性

群体是由海量的设备组成的，这些设备各自拥有一定的计算，存储和通信能力。群体程序的目的为了让群体中的所有设备协作完成一个共同目标。然而这些个体为了完成群体目标所做的动作又是不同的。如果以传统方式逐个进行编程，从时间花销和工作量上看都是低效的。通过分布式计算的任务分发方式（例如map reduce）的思路可以改善这个问题。但是个体间互动的性质无法通过简单的任务分配来反映。比如一个散布操作，要把很多个体散布在一个区域中并且保证每两个个体的距离都大于d。利用传统式分布式编程很难在有效时间给出这个问题的解。

(2)异步性

群体程序的执行基本都是异步的，即每台设备执行哪个程序，执行到哪一步，都是由设备本身和周围环境决定的。群体程序执行是保持同步十分困难。维护群体的同步性需要通过广播的方式来调配各个设备的运行状态，信息的广播由于产生的开销非常大，在群体计算中式需要尽量避免的。

(3)环境敏感性

传统程序分析中常常假设所有硬件正常工作，并且认为环境因素具有可预测性。在群体编程中研究人员更多是面对客观世界，气候，生物和其他设备的动作都会影响到程序的运行。开发者试图通过建模来模拟客观事件的种种特性，以增强群体程序的鲁棒性。但是考虑到客观世界的不可预测性决定了研究者不可能预知所有意外情况。这要求群体程序具备一定的弹性（resiliancy），保证系统要在恶劣的环境影响中保证合理的健壮性，避免落入极端境地。

(4)能源敏感性

在传统计算中时间和空间是两大主要限制因素，编写程序要在时间空间的占用上进行权衡。然而在群体中，要考虑更多。比如在嵌入式移动设备组成的群体中，设计者必须考虑能源因素。程序运行的速度和结果精确度都必须跟能源消耗做出权衡。在群体程序语言设计中，必须对这些能源以及类似的非功能属性进行考量。

这样一种分布式，异步性，环境敏感，能源敏感的程序设计方法就是群体编程。群体编程工具的设计目标是：当开发者想要让某一个群体实现某个功能的时候，首先他利用群体编程语言将一些基本的群体操作进行整合，设定相应的参数；然后群体编程开发工具会把开发者编写的高级群体程序分解为细节的动作（这个过程类似于从高级语言到汇编语言），最后开发工具按要求分发这些任务给群体的各个成员节点，让这些节点实现功能，完成任务。开发者不再需要对中间过程和每个节点上运行的程序进行考虑，大大提高程序编写的效率。如图1所示[1]：

图1 群体编程的模型 （McEachrom 2002）

2 群体语言设计

为了开发一套群体编程的语言、方法和工具。必须先要解答任何语言设计中都要面对的几大主要问题。David Evans在2000年提出了群体编程的几大核心问题[2]：1如何规定群体程序的功能性指标，2如何为环境和设备建模，3群体计算的元语是什么，4如何把群体编程中的元语操作结合组成一个完整的群体程序，5抽象级别问题，6 如何实现和对群体程序进行测试。这6个问题其实可以归结为两个根本问题：1元语操作与元语组合，2建模与评估。

2.1 元语操作与元语组合

元语是计算机程序设计中的基本单位，传统计算理论的元语操作并不能直接映射到群体编程中去。即使是像过程调用和赋值这样一些简单概念在群体编程中，都不能找到明显的类比。群体编程环境中的元语与类库需要抓住群体行为的特点与精髓并给出原则性的定义。在群体编程中的元语主要有：

散布：把设备在一块区域中分散开来，要求最终状态满足没有任意两台设备之间的距离小于某特定值d。

成簇：设备聚集成块。最终状态是几乎所有设备都满足条件在d范围内至少有n台邻居设备。

群移：群体的所有成员想同一个方向移动而互不干扰，就像自然界中的迁徙行为，最终全部到达目的地。

扫描：用设备覆盖一块区域。目标区域内每一块 r半径的区域内都至少有一台设备出现过。

广播：对群体内的所有设备发送消息。

分播：对群体内满足条件的个体进行消息发送。

通过元语的组合，就可以实现大量的功能。比如，一个搜救任务可以定义为由扫描和吸引操作的组合。

对以上每一种元语都有多种实现方式以权衡弹性（在恶劣环境和设备故障的影响下实现功能的好坏程度），效率（消耗资源的量），和速度（达到近似解的快慢程度）。

群体编程中的元语如何定义一直困扰着研究者。是否像传统编程一样，存在几种有限的基本操作可以涵盖所有的应用？这个问题还有待解决。但是就目前而言由于群体与生俱来的复杂性。即使给出很多基本的操作也不能确定能够实现所有的应用目标。

2.2 建模与评估

群体计算的环境敏感性决定了建模在群体编程中的重要程度。在为不同的环境建立模型和完善相应的类库的基础上才能对对群体程序进行测试，保证群体程序能够正确实现功能。建立的模型如果不能准确的反应现实，群体程序的评估与测试就失去了参考价值。

建模中最关键的问题是模型的粒度。设备和环境的属性都是无穷多的。比如设备的移动速度、体积大小、发射功率，物理环境中的气候、生物等的影响都应该被考虑到。理论上，建模的粒度越细，反应现实的程度也就越高，模拟仿真的时候效果也会越好。但是过于细粒度的环境建模也会带来显著的开销，采集数据的过程也是十分复杂的。所以必须在建模粒度方面做出权衡。

一种思路是把群体程序的执行看成是全局状态的序列，每个全局状态都包含了每个个体设备的状态。个体设备的状态包括了位置信息，内部状态信息和正在运行的程序

问题。群体程序的执行状态几乎无时无刻都在变化，以至于只有无限细粒度的描述才能描述整个群体的行为。显然，研究者不可能对无限多的状态进行分析。David Evans提出对全局状态进行归类[2]，系统的状态在全局状态标记未发生改变的前提下都可以认为是不变的。这样，一个群体程序的规定就可以通过全局状态的时序逻辑来进行定义。

群体程序的仿真测试是基于环境和设备建模的。良好的评估环节能够帮助研究者在群体编程的研究中，更好的搭建和理解群体计算系统。就目前而言，相比已经有着比较完善测试评估体系的传统编程来说，群体编程的测试还处在发展中。最初，研究者们通过已有的平台（如 MATLAB）来做一些仿真测试。随着需求的增加，也使用了一些其他领域的测试工具来进行群体编程的仿真测试，比如最初用于无限通信的仿真工具GloMoSim。对群体程序的评估一般是由评估元语开始的。藉由评估环节来更好的理解和完善元语操作，进而理解完善由元语组合成的简单的群体程序，最后循序渐进达到对大型，复杂群体程序进行研究的目的。

Cuvelier在2002年[3]Seth在2003年[4]分别在不同实验平台上对于多种散布算法的效率进行了评估，展示了群体编程研究的一些基本思路。

3 总结

使用群体编程的方法将大大提高对大规模环境敏感分布式系统编程的效率。在认知网络[5]，传感网络[6]，UAV无等。由于没有时间同步性，全球状态的粒度产生了很严重的人机控制[7]等领域都出现了对群体编程工具的所需求。语言设计是计算机科学中难度和挑战最大的部分，目前对群体编程的研究还处在起始阶段，许多有价值的问题还有待今天的研究者来研究和完善。群体智能技术的前景已经被公众认可，群体编程的语言、工具和理论的研究将大大的影响群体智能，群体计算技术的发展和实际应用，对未来人们的生活产生深远的影响。

[1]Errol Charles McEachron. A SYSTEM [M]FOR SYNTHESIZING SWARM PROGRAMS. 2002.

[2]David Evans. Programming the Swarm. 2000.

[3]MJ Cuvelier . Communication Aware Swarm Dispersion Primitives. 2002.

[4]Ankush Seth. SCALABILITY AND COMMUNICATION WITHIN SWARM COMPUTING. 2003.

[5]M PERALTA, S MUKHOPADHYAY. COGNITIVE NETWORKS. 2009.

[6]K Shenai, S Mukhopadhyay - Microelectronics . Cognitive sensor networks. 2008.

[7]DM Hart, PA Craig-Hart-Aerospace Conference . Reducing swarming theory to practice for UAV control. 2004.