群體編程技術發展研究

趙冰陽

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.