基于人工免疫算法和蟻群算法的協(xié)同控制方法研究

張春黎

(黃山職業(yè)技術(shù)學(xué)院 工業(yè)與財貿(mào)系， 安徽 黃山 245000)

無線傳感執(zhí)行網(wǎng)絡(luò)(wireless sensor and actor networks，WSANs)是近期信息科學(xué)和自動化技術(shù)研究的熱點[1]，它在環(huán)境監(jiān)測、軍事偵察、智能家居、動物定位和跟蹤、智能交通、城市管理等領(lǐng)域有著廣闊的應(yīng)用前景[2-3]。典型的無線傳感執(zhí)行網(wǎng)絡(luò)通常包括傳感器節(jié)點(sensor nodes)、執(zhí)行節(jié)點(actor nodes) 、接收發(fā)送器(sink)和任務(wù)管理節(jié)點[4]。為了提高網(wǎng)絡(luò)的檢測和反應(yīng)能力,需要在傳感器節(jié)點和執(zhí)行節(jié)點中添加協(xié)調(diào)機制,比如傳感器節(jié)點與傳感器節(jié)點之間的協(xié)調(diào)、傳感器節(jié)點與執(zhí)行器節(jié)點之間的協(xié)調(diào)、執(zhí)行器節(jié)點與執(zhí)行器節(jié)點之間的協(xié)調(diào)[5]。成國營等[6]針對傳感器與執(zhí)行器協(xié)同和執(zhí)行器與執(zhí)行器協(xié)同問題，提出了基于生物免疫機制的傳感器與執(zhí)行器自適應(yīng)路由協(xié)同算法。易軍等[7]利用熵權(quán)的任務(wù)分派算法解決了執(zhí)行器節(jié)點任務(wù)并發(fā)執(zhí)行的能耗問題。王艷等[1]采用昆蟲生物種群協(xié)作機制減少了執(zhí)行器間的協(xié)作能耗。然而，這些方法主要針對執(zhí)行器間或傳感器與執(zhí)行器間的協(xié)作問題，且能耗較高。本研究針對無線傳感執(zhí)行網(wǎng)絡(luò)的傳感器節(jié)點與執(zhí)行器節(jié)點間的協(xié)作，提出了一種WSANs智能傳感器節(jié)點間協(xié)調(diào)機制，使多個傳感器和多個執(zhí)行器能在無線傳感執(zhí)行網(wǎng)絡(luò)中合理有效地進行合作，以完成對各種事件的處理，在一致性方面達(dá)到快速收斂，提高整個任務(wù)的執(zhí)行效率。

1 WSANs協(xié)同控制

1.1 WSANs的基本組成

一個典型的WSANs由傳感器、執(zhí)行器、接收發(fā)送器和任務(wù)管理器等節(jié)點組成，如圖1所示。傳感器負(fù)責(zé)從環(huán)境中感知信息并收集數(shù)據(jù)，執(zhí)行器接收傳感器發(fā)送過來的數(shù)據(jù)并根據(jù)數(shù)據(jù)進行操作，接收發(fā)送器負(fù)責(zé)監(jiān)控整個網(wǎng)絡(luò)，并且和任務(wù)管理器通信。與傳統(tǒng)的無線傳感網(wǎng)絡(luò)相比，WSANs加入了執(zhí)行器節(jié)點。執(zhí)行器節(jié)點能量較為充足，具有較強的計算能力，并且具備移動性。加入這類特殊的節(jié)點，可使WSANs具有監(jiān)測功能、控制功能和執(zhí)行功能，能夠更好地與環(huán)境動態(tài)交互[1]。

圖1 WSANs基本結(jié)構(gòu)Fig.1 Basic structure of WSANs

1.2 引入蟻群算法

將蟻群算法引入無線傳感執(zhí)行網(wǎng)絡(luò)中，每個節(jié)點都擁有一個信息素表。使用2個種類的螞蟻，分別稱為前向螞蟻和反向螞蟻[8]。前向螞蟻攜帶4種信息：所需要的傳感器類型；相關(guān)傳感器區(qū)域；數(shù)據(jù)傳輸速率；相關(guān)時間段。傳感器的能量非常有限，考慮最佳路徑不僅僅要求距離，更要考慮路徑的能量水平，例如選擇距離較長但能量水平高比選擇距離較短但能量水平低的路徑要好。算法中的每只螞蟻根據(jù)狀態(tài)轉(zhuǎn)移規(guī)則發(fā)現(xiàn)它的下一步跳轉(zhuǎn)，同時每只螞蟻可根據(jù)局部校正規(guī)則和全局校正規(guī)則迅速找出最短路徑。

1.2.1狀態(tài)轉(zhuǎn)移規(guī)則

假設(shè)q是均勻分布在[0，1]的隨機數(shù)，q0是(0，1)的一個恒定數(shù)，螞蟻被隨機放置在i節(jié)點，螞蟻選擇下一個節(jié)點j的概率可根據(jù)公式(1)、(2)求出。

當(dāng)q≤q0時，則

j=arg max{[τi， j(t)]α[ηi，k(t)]β}。

(1)

當(dāng)q>q0時，則

(2)

式中：j∈Ni；τi， j(t)表示節(jié)點i與j之間路徑的信息素；Ni表示螞蟻尚未經(jīng)過的節(jié)點集合；α和β是控制信息素和路徑距離之間的相對重要性參數(shù)；ηi， j(t)是節(jié)點i與節(jié)點j之間的距離倒數(shù)。

1.2.2局部校正規(guī)則

當(dāng)螞蟻在節(jié)點間移動時，更新邊界上的信息素τi，j(t)：

τi，j(t+1)=(1-ρ)τi，j(t)+ρΔτi，j(t)，

(3)

式中：ρ表示局部信息素衰減參數(shù)；Δτi，j(t)表示節(jié)點i與節(jié)點j之間的信息素增量。

當(dāng)新增信息素含量為m只螞蟻在初始節(jié)點i與終點節(jié)點j路徑上留下的信息素總和時，信息素增量可表示為

(4)

(5)

1.2.3全局校正規(guī)則

當(dāng)一個節(jié)點有一個來自鄰居節(jié)點的反向螞蟻經(jīng)過時，它的信息素就會更新。一旦所有螞蟻全部完成一次運作，就需要全局校正。這里使用雙向融合戰(zhàn)略，只有最好的和最差的路徑會更新螞蟻的信息素：

τi，j(t+n)=(1-α)τi，j(t)+αΔτi，j(t)，

(6)

(7)

式中：α是局部信息素衰減參數(shù)；Q1和Q2的值是恒定的。

1.3 引入人工免疫算法

在WSANs中，選取參與協(xié)作的最優(yōu)執(zhí)行器問題是一類目標(biāo)優(yōu)化問題，使用人工免疫算法可以快速搜索出全局最優(yōu)值，它的記憶功能可保留親和力較高的多個個體，避免了盲目尋優(yōu)。假定一個無線傳感執(zhí)行網(wǎng)絡(luò)的某一區(qū)域中，有4×5個執(zhí)行器接收到任務(wù)信息。執(zhí)行器接收到任務(wù)信息后，經(jīng)過初步分析，此任務(wù)需要由8個執(zhí)行器節(jié)點共同協(xié)作完成。用xij(i=1，2，3，4；j=1，2，3，4，5)表示執(zhí)行器節(jié)點，若xij=0，則表示執(zhí)行器為睡眠模式，未參加任務(wù)；若xij=1，則表示執(zhí)行器參與任務(wù)。執(zhí)行器分布情況如矩陣(包括能量矩陣A和處理能力矩陣B)所示：

(8)

首先要確定執(zhí)行器群體，包括指標(biāo)(執(zhí)行器的計算處理能力η和可利用能量E)和參數(shù)k1、k2的大??；然后選定初始抗體群，并且計算它們的親和力，根據(jù)克隆規(guī)則淘汰親和力小的，對親和力大的再次進行克??；最后利用設(shè)定的變異規(guī)則，生成新的抗體群之后進行變異操作。重復(fù)上述步驟T次，當(dāng)大于或等于設(shè)定的閾值時停止操作，否則繼續(xù)重復(fù)操作。操作結(jié)束后，所求出的最優(yōu)解就是最適合執(zhí)行目標(biāo)任務(wù)的執(zhí)行器，由這些執(zhí)行器共同協(xié)作完成任務(wù)。

2 仿真與分析

2.1 基于蟻群算法的傳感器協(xié)同機制仿真及分析

將基于蟻群算法的WSANs智能傳感器節(jié)點間協(xié)同機制放在MATLAB 2012環(huán)境中進行仿真，主要仿真的是傳感器之間在數(shù)據(jù)協(xié)作傳輸時，通過蟻群算法選定最優(yōu)路徑及最佳跳轉(zhuǎn)節(jié)點的節(jié)能問題和傳輸效率。仿真時有以下設(shè)置：①將傳感器節(jié)點隨機放置在1 000 m×1 000 m的區(qū)域中；②操作初始時，每個傳感器節(jié)點被賦予1個單位的能量；③假定傳感器發(fā)射和接收分別損耗0.005個單位和0.000 5個單位；④無線電的有效傳輸范圍是250 m；⑤參數(shù)M=30，Q=100，Q1=Q2=10，α=β=1,ρ1=ρ2=0.7，τi,j(t)=10，Nmax=200。

為了更直觀地看出基于蟻群算法的智能傳感器節(jié)點間協(xié)同機制的優(yōu)越性，將仿真結(jié)果與文獻[9]中的ARA算法和文獻[10]中的LEACH算法進行了比較。圖2所示為算法的平均能耗情況，其中橫坐標(biāo)表示傳感器節(jié)點的個數(shù)，節(jié)點數(shù)在20～120，每次增加20個，縱坐標(biāo)表示剩余能量百分比。由圖2可看出：當(dāng)節(jié)點數(shù)為20時，3種算法具備相似的能耗，剩余能量百分比在97%左右；隨著節(jié)點密度的增加，即節(jié)點擁有更多的鄰居節(jié)點，可選擇性變大，3種算法的剩余能量與節(jié)點密度正相關(guān)；當(dāng)節(jié)點數(shù)達(dá)到120時，3種算法的剩余能量百分比分別為99.4%(蟻群算法)、98.2%(ARA算法)和96.8%(LEACH算法)。可以看出，在算法能量損耗上蟻群算法少于ARA算法和LEACH算法。蟻群算法提供了更好的性能，使傳感器協(xié)作傳輸過程節(jié)省更多的能量，說明蟻群算法有助于傳感器數(shù)據(jù)協(xié)同傳輸能量利用率提高。

圖2 算法的平均能耗Fig.2 Average energy consumption of the algorithm

蟻群算法、ARA算法和LEACH算法的數(shù)據(jù)包傳輸率見圖3。

圖3 數(shù)據(jù)包傳輸率Fig.3 Packet transmission rate

由圖3可看出，在節(jié)點數(shù)為20～80時，隨著節(jié)點數(shù)目的增加，蟻群算法數(shù)據(jù)包傳輸率逐漸提高，而ARA算法和LEACH算法的數(shù)據(jù)傳輸率基本不變，在75%左右；當(dāng)節(jié)點數(shù)大于80時，3種算法的數(shù)據(jù)包傳輸率與節(jié)點數(shù)正相關(guān)，按數(shù)據(jù)傳輸率由大到小排列分別為蟻群算法、LEACH算法、ARA算法；在節(jié)點數(shù)為120時，蟻群算法的數(shù)據(jù)包傳輸率達(dá)到最大值95%，明顯優(yōu)于另外兩個算法，并且收斂速度加快，說明蟻群算法使傳感器在協(xié)同合作進行數(shù)據(jù)包傳輸時極大地提高了數(shù)據(jù)包傳輸率。綜上所述，基于蟻群算法的WSANs智能傳感器協(xié)調(diào)機制使傳感器在協(xié)同合作進行數(shù)據(jù)傳輸過程中，節(jié)約了更多能量，數(shù)據(jù)包傳輸率也有很大提升，總體上提高了協(xié)作效率。

2.2 基于人工免疫算法的多執(zhí)行器協(xié)同機制仿真及分析

在MATLAB 2012仿真環(huán)境中進行基于人工免疫算法的多執(zhí)行器協(xié)作方法仿真。仿真數(shù)據(jù)包括4×5執(zhí)行器的可利用能量矩陣A和4×5執(zhí)行器的計算處理能力矩陣B：

其中，目標(biāo)函數(shù)中K1=15，K2=0.1。將數(shù)據(jù)進行200次迭代運算得出最終結(jié)果，繪制出了人工免疫算法親和力值的變化曲線，如圖4所示。

圖4 人工免疫算法親和力值變化曲線Fig.4 Variation curve of affinity value calculated by artificial immunity

由圖4可以看出，人工免疫算法經(jīng)過60次迭代運算后，圖像趨于穩(wěn)定，親和力值最大(約147.5)并且不再變化，說明此時已經(jīng)達(dá)到最優(yōu)解。綜合考慮計算處理能力和可利用的能量，用親和力值(147.5)表示。最優(yōu)解x13、x14、x15、x32、x33、x34、x35、x43狀態(tài)為1，說明這8個執(zhí)行器共同協(xié)作完成這項任務(wù)是最完美的選擇。經(jīng)過60次迭代就可求出最優(yōu)解，充分說明人工免疫算法的尋優(yōu)能力明顯縮短了確定最優(yōu)執(zhí)行器的時間。當(dāng)?shù)螖?shù)小于60時，親和力值逐步上升，主要是因為克隆和變異使得子代具有更大的優(yōu)勢，從而導(dǎo)致親和力值逐步上升，最重要的是保證了收斂速度。使用人工免疫算法，可以使參與協(xié)作的執(zhí)行器快速達(dá)到最優(yōu)，從而提高協(xié)作效率。

3 結(jié)語

本研究針對傳感器之間的協(xié)作問題，提出了一種基于蟻群算法的智能傳感器協(xié)同機制，在傳感器之間協(xié)作傳輸數(shù)據(jù)時，利用蟻群算法可以找出最優(yōu)路徑，縮短協(xié)作時間，并且可以節(jié)約能量。通過仿真驗證發(fā)現(xiàn)，在數(shù)據(jù)傳輸效率和能量損耗方面，蟻群算法優(yōu)于ARA算法和LEACH算法。同時，針對執(zhí)行器節(jié)點間的協(xié)作，提出了一種基于人工免疫算法的智能執(zhí)行器協(xié)同機制。經(jīng)過仿真驗證可知，在迭代次數(shù)為60時協(xié)調(diào)機制達(dá)到收斂狀態(tài)，親和力最大值為147.5，極大提高了執(zhí)行器之間的協(xié)作效率。