盧毅，徐夢(mèng)穎，周杰

（石河子大學(xué)信息科學(xué)與技術(shù)學(xué)院，新疆 石河子 832003）

1 引言

隨著無線通信技術(shù)的迅速發(fā)展，無線傳感器網(wǎng)絡(luò)（WSN,wireless sensor network）已成為研究熱點(diǎn)之一。由于其低能耗、低成本、數(shù)據(jù)存儲(chǔ)能力強(qiáng)、無線通信能力強(qiáng)、自組織等特點(diǎn)，WSN 的應(yīng)用領(lǐng)域越來越廣，包括智能家居、交通、農(nóng)田監(jiān)測(cè)等[1]。

無線傳感器網(wǎng)絡(luò)由眾多具備信號(hào)傳輸與計(jì)算性能的傳感器節(jié)點(diǎn)通過自組織網(wǎng)絡(luò)的形式構(gòu)成，其主要特點(diǎn)是以數(shù)據(jù)為中心，且具備一定的網(wǎng)絡(luò)規(guī)模與拓?fù)浣Y(jié)構(gòu)以滿足感知信息的傳輸、處理、存儲(chǔ)、顯示、記錄和控制要求[2-3]。在農(nóng)業(yè)方面，WSN 主要應(yīng)用于溫室大棚的溫濕度采集控制、節(jié)水灌溉、土壤pH 值測(cè)量、動(dòng)植物種群復(fù)雜度的監(jiān)測(cè)等。

服務(wù)質(zhì)量（QoS,quality of service）優(yōu)化是無線傳感器網(wǎng)絡(luò)單播路由優(yōu)化中待解決的一項(xiàng)難題，該問題是一個(gè)NP 完全問題，傳統(tǒng)的算法在優(yōu)化該問題時(shí)效果并不理想[4-5]。研究人員希望有限的無線傳感器網(wǎng)絡(luò)能量能夠被網(wǎng)絡(luò)系統(tǒng)高效使用，使數(shù)據(jù)在鏈路中的傳輸能耗最小，同時(shí)不影響傳輸鏈路的其他指標(biāo)。這也是單播路由優(yōu)化問題中的一個(gè)重要任務(wù)。然而，QoS 受許多因素的影響，包括時(shí)延、鏈路帶寬、時(shí)延抖動(dòng)、分組丟失率等[6-8]。實(shí)時(shí)無線通信過程中數(shù)據(jù)的傳輸受到上述因素的限制，可能會(huì)影響用戶的視覺體驗(yàn)和聽覺體驗(yàn)[9]。無線傳感器網(wǎng)絡(luò)可以抽象為圖論中的有向圖，節(jié)點(diǎn)與節(jié)點(diǎn)之間存在許多鏈路。鏈路上的數(shù)據(jù)受時(shí)延、鏈路帶寬、時(shí)延抖動(dòng)、分組丟失率的影響，源節(jié)點(diǎn)與終端節(jié)點(diǎn)之間存在多條可行路徑，所以優(yōu)化的目的是在滿足以上約束條件的前提下找到一條能量損耗最小的路徑。

在過去的研究中，研究人員通過多種智能仿生算法解決和優(yōu)化上述問題，例如遺傳算法（GA,genetic algorithm）、蟻群優(yōu)化（ACO,ant colony optimization）算法、粒子群優(yōu)化（PSO,particle swarm optimization）算法等[10-12]。文獻(xiàn)[13]提出了一種用于單播多約束優(yōu)化的遺傳算法，但是在算法的迭代過程中，交叉和變異步驟沒有進(jìn)行改進(jìn)，產(chǎn)生的路徑極可能為不可行路徑，從而無法找到有效解。文獻(xiàn)[14]提出一種蟻群優(yōu)化算法進(jìn)而優(yōu)化帶約束的服務(wù)質(zhì)量路由問題，但是該算法計(jì)算復(fù)雜度較高。在無線傳感器網(wǎng)絡(luò)中，為了保證服務(wù)質(zhì)量，路徑要滿足傳輸損耗最小的條件，同時(shí)保證通信質(zhì)量。文獻(xiàn)[15]提出了一種改進(jìn)的螢火蟲算法用于保證電力通信，該算法用于優(yōu)化網(wǎng)絡(luò)鏈路帶寬、時(shí)延和分組丟失率，通過混沌編碼提高種群的多樣性，實(shí)驗(yàn)結(jié)果表明，該方法有效地優(yōu)化了網(wǎng)絡(luò)資源，能夠找到一條滿足電力通信業(yè)務(wù)的有效路由。針對(duì)多約束條件下的路由選擇問題，文獻(xiàn)[16]提出了一種新的路由選擇算法，該方法在螢火蟲算法的基礎(chǔ)上結(jié)合了量子進(jìn)化算法，有效解決了無線路由協(xié)議中的路由選擇問題，但隨著問題規(guī)模的增加，計(jì)算時(shí)間大大增加。

蛙跳算法（SFLA,shuffled frog leaping algorithm）是近年來被提出的仿生學(xué)優(yōu)化算法，它具備概念簡(jiǎn)單、參數(shù)極少、計(jì)算速度快、優(yōu)秀的全局搜索能力、實(shí)現(xiàn)簡(jiǎn)便等優(yōu)點(diǎn)[17-19]。SFLA 自從被提出之后就受到普遍關(guān)注，現(xiàn)已經(jīng)應(yīng)用于水資源節(jié)能灌溉、電線電纜的排序等領(lǐng)域。SFLA 通過種群編碼、種群初始化、計(jì)算適應(yīng)度、子種群劃分、局部搜索和全局搜索來提高求解質(zhì)量。在算法操作過程中，種群被分為幾個(gè)子種群，不同的子種群具有不同的信息，對(duì)每一個(gè)子種群進(jìn)行局部搜索，通過子種群的進(jìn)化求優(yōu)化解，經(jīng)過一定時(shí)間的進(jìn)化和跳躍過程，最后進(jìn)行全局搜索，直到收斂或者達(dá)到標(biāo)準(zhǔn)。

為了優(yōu)化QoS 單播路由問題，本文建立了數(shù)學(xué)模型，路由選擇需要滿足傳輸路徑上產(chǎn)生的時(shí)延抖動(dòng)、分組丟失率、時(shí)延、鏈路帶寬等限制條件，在此基礎(chǔ)上找到一條數(shù)據(jù)從源節(jié)點(diǎn)出發(fā)到終端節(jié)點(diǎn)間所需能量損耗最低的路徑。為了找到最優(yōu)路徑，本文提出了一種改進(jìn)的免疫克隆蛙跳算法（IICSFLA,improved immune clonal shuffled frog leaping algorithm），該算法結(jié)合了傳統(tǒng)蛙跳算法與免疫克隆算法的優(yōu)點(diǎn)。對(duì)于優(yōu)化復(fù)雜問題，所提算法可以加快算法收斂速度，并避免局部最優(yōu)，在搜索過程中通過結(jié)合變異算子不斷向最優(yōu)解靠近，保證了算法的穩(wěn)健性、收斂性、自適應(yīng)性。在仿真實(shí)驗(yàn)中，將改進(jìn)的免疫克隆蛙跳算法的性能與自適應(yīng)遺傳算法和自適應(yīng)蟻群算法的性能進(jìn)行了對(duì)比，仿真結(jié)果顯示，所提算法有效地降低了數(shù)據(jù)在傳輸路徑上的能耗，同時(shí)滿足了其他多項(xiàng)約束條件。

2 系統(tǒng)模型

本節(jié)介紹多條件限制的QoS 單播路由優(yōu)化模型。無線傳感器網(wǎng)絡(luò)的圖論模型可以看作一組傳感器的節(jié)點(diǎn)集合和節(jié)點(diǎn)之間的鏈路集合，用G(V,E)表示。用圖論方法表示源節(jié)點(diǎn)、終端節(jié)點(diǎn)、多個(gè)中繼節(jié)點(diǎn)和鏈路時(shí)，節(jié)點(diǎn)集合包括源節(jié)點(diǎn)v1、終端節(jié)點(diǎn)vn和多個(gè)中繼節(jié)點(diǎn)v2→ …→vn?1，源節(jié)點(diǎn)為第1個(gè)節(jié)點(diǎn)，中繼節(jié)點(diǎn)為第2～第n?1 個(gè)節(jié)點(diǎn)，終端節(jié)點(diǎn)則為第n個(gè)節(jié)點(diǎn)。從源節(jié)點(diǎn)至終端節(jié)點(diǎn)的鏈路可以表示為p(v1,vn)={v1→v2→ …→vn}。

每一段鏈路都由2 個(gè)節(jié)點(diǎn)構(gòu)成，假設(shè)相鄰的2 個(gè)節(jié)點(diǎn)序號(hào)為i和j，e={vi→v j}(i≠j)。數(shù)據(jù)在每條鏈路上的傳輸情況都受到時(shí)延抖動(dòng)、分組丟失率、時(shí)延、鏈路帶寬這4 個(gè)參數(shù)的限制。每條鏈路上的能量損耗為C(e)，抖動(dòng)為D(e)，鏈路帶寬為B(e)，時(shí)延抖動(dòng)為D_J(e)，分組丟失率為P_L(e) 。

2.1 能量損耗模型

在2 個(gè)相鄰節(jié)點(diǎn)i和j之間的鏈路上，能量損耗由傳輸數(shù)據(jù)能量和接收數(shù)據(jù)能量構(gòu)成，則2 個(gè)相鄰節(jié)點(diǎn)間的總能量損耗C(e) 為

其中，Cs為2 個(gè)相鄰節(jié)點(diǎn)間的傳輸數(shù)據(jù)所消耗的能量，Cr為2 個(gè)相鄰節(jié)點(diǎn)間的接收數(shù)據(jù)的能量。

當(dāng)2 個(gè)相鄰傳感器節(jié)點(diǎn)之間的距離為l，傳輸數(shù)據(jù)量為k時(shí)，傳輸數(shù)據(jù)能耗為

其中，l0為2 個(gè)相鄰傳感器節(jié)點(diǎn)之間的距離閾值傳輸數(shù)據(jù)，Eelec為電能參數(shù)，放大器能量由功率放大參數(shù)εamp1決定，路徑上能量衰落由εamp2決定。本文設(shè)Eelec=50 nJ/bit，εamp1=10 nJ/(bit ?m2)，εamp2=0.015 nJ/(bit ?m4)，l0=1m。

當(dāng)接收數(shù)據(jù)量為k時(shí)，需要的能量Cr(k)為

當(dāng)2 個(gè)傳感器節(jié)點(diǎn)相距0.5 m，k=1 Mbit 時(shí)，由式(3)計(jì)算可得Cr(k)=Eeleck=50 nJ/bit ×106bit=0.05 J 。

2.2 路徑參數(shù)

1) 能量損耗函數(shù)

數(shù)據(jù)從節(jié)點(diǎn)v1傳輸?shù)焦?jié)點(diǎn)vn時(shí)，鏈路p(v1,vn)的能量損耗為

2) 時(shí)延函數(shù)

數(shù)據(jù)從節(jié)點(diǎn)v1到節(jié)點(diǎn)vn產(chǎn)生的總時(shí)延為

3) 鏈路帶寬函數(shù)

數(shù)據(jù)從節(jié)點(diǎn)v1到節(jié)點(diǎn)vn產(chǎn)生的總鏈路帶寬為

4) 時(shí)延抖動(dòng)函數(shù)

數(shù)據(jù)從節(jié)點(diǎn)v1到節(jié)點(diǎn)vn產(chǎn)生的總時(shí)延抖動(dòng)為

5) 分組丟失率函數(shù)

數(shù)據(jù)從節(jié)點(diǎn)v1到節(jié)點(diǎn)vn產(chǎn)生的總分組丟失率為

2.3 目標(biāo)函數(shù)

在無線傳感器中，多條件限制的QoS 單播路由模型可以由圖模型構(gòu)成。假設(shè)該圖中有V個(gè)傳感器節(jié)點(diǎn)、E條鏈路，則該圖可以表示為G(V,E)，在相鄰節(jié)點(diǎn)的鏈路上將受時(shí)延、鏈路帶寬、分組丟失率、時(shí)延抖動(dòng)、能量損耗的影響。基于這些限制條件，QoS 單播路由問題的目標(biāo)函數(shù)為找到一條從源節(jié)點(diǎn)至終端節(jié)點(diǎn)數(shù)據(jù)傳輸所需的能量損耗最低的路徑。

適應(yīng)度（fitness）是依據(jù)生物對(duì)于大自然生存環(huán)境的適應(yīng)程度，針對(duì)事件中所有個(gè)體呈現(xiàn)出的不同表現(xiàn)的一種監(jiān)測(cè)方法。適應(yīng)度函數(shù)即實(shí)際問題中的所有基本單位與其自身適應(yīng)度的一一對(duì)應(yīng)關(guān)系，通常情況下它是一個(gè)常量函數(shù)。用fitness 表示能量損耗對(duì)應(yīng)的適應(yīng)度，目標(biāo)函數(shù)如式(9)所示。

2.4 約束條件

該模型是為了找到一條能量損耗最小的最優(yōu)路徑，由源節(jié)點(diǎn)v1開始傳輸數(shù)據(jù)，直到終端節(jié)點(diǎn)vn結(jié)束數(shù)據(jù)的傳輸，這條路徑上的各個(gè)相鄰節(jié)點(diǎn)間的分鏈路需要滿足以下條件。

其中，Dmax為鏈路上所能接受的最大時(shí)延，Bmin為鏈路上的最小鏈路帶寬，Jmax為鏈路上所能接受的最大時(shí)延抖動(dòng)，Lmax為最大分組丟失率。

3 QoS 路由優(yōu)化算法設(shè)計(jì)

蛙跳算法是受青蛙捕食行為的啟發(fā)而提出的優(yōu)化算法，該算法綜合了變異算子的搜索特點(diǎn)，擁有較好的搜索解的能力。傳統(tǒng)的蛙跳算法包含以下幾個(gè)步驟[20-21]：種群編碼、種群初始化、計(jì)算適應(yīng)度、子種群劃分、局部搜索、全局搜索。

針對(duì)多條件限制的QoS 單播路由優(yōu)化問題，本文提出一種改進(jìn)的免疫克隆蛙跳算法優(yōu)化QoS 路由，該算法結(jié)合了免疫克隆算子的優(yōu)點(diǎn)，克服了早熟收斂的缺點(diǎn)，維持了抗體種群的多樣性。

II CSFLA 的主要思路如下。任意生成N只青蛙構(gòu)成一個(gè)最初部落種群，X={X1,X2,…,Xi,…,XN}，D維空間中的第i只青蛙可以表示為Xi={xi1,xi2,…,xiD}。假設(shè)初始蛙群可分為I個(gè)子種群，每個(gè)子種群中有J只青蛙，則初始部落種群與子種群之間滿足N=IJ。產(chǎn)生最初部落種群以后，首先把部落種群內(nèi)青蛙按照規(guī)定的適應(yīng)度升序排列。在QoS 路由選擇優(yōu)化問題中，青蛙按照從源節(jié)點(diǎn)到終端節(jié)點(diǎn)間的能量損耗由小到大排序，并且記青蛙種群中具備最低能耗的青蛙個(gè)體為Xg_min。例如，當(dāng)種群FROGS 中有40 只青蛙，每只青蛙代表路由能耗時(shí)，適應(yīng)度升序排列仿真內(nèi)容和仿真結(jié)果如圖1 所示。

由圖1 可以看出，經(jīng)過排序個(gè)體按照從源節(jié)點(diǎn)到終端節(jié)點(diǎn)間的能量損耗由小到大依次排序，在1號(hào)位置的青蛙能耗最小。

其次把全部青蛙種群分成子種群，記錄下每個(gè)子種群中能耗最小的青蛙Xb_min和子種群中能耗最大的青蛙Xb_max。首先對(duì)子種群進(jìn)行局部搜索，若改進(jìn)后的青蛙較原來子種群中的青蛙更優(yōu)異，那么改進(jìn)后的青蛙將替代子種群中的原始青蛙。例如，在局部搜索過程中，種群中的40 只青蛙被分成4 個(gè)子種群，每個(gè)子種群10 只青蛙，則一次局部搜索的仿真結(jié)果如圖2 所示。

如圖2 所示，局部搜索后子種群中能耗最大的青蛙（能耗為0.734 2 J）被改進(jìn)，得到的新青蛙能耗降為0.703 2 J。

如果沒有任何優(yōu)化，則隨機(jī)選取一只新的青蛙來替代部族中原始的青蛙，反復(fù)進(jìn)行上述局部搜索操作genmax次，直至完成局部搜索所有操作指令后，將經(jīng)過上述操作的所有子種群內(nèi)的青蛙重新組合并排列順序，再實(shí)行全局搜索操作。如此重復(fù)操作，直至達(dá)到規(guī)定的收斂要求，從而達(dá)到全局變量最優(yōu)化的目的。

3.1 種群編碼

在多條件限制的QoS 路由優(yōu)化問題中，數(shù)據(jù)傳輸?shù)穆窂奖硎緸?/p>

假設(shè)有n個(gè)傳感器節(jié)點(diǎn)，節(jié)點(diǎn)的最大出度個(gè)數(shù)設(shè)為Smax，則每個(gè)個(gè)體的基因位長(zhǎng)度T等于所有節(jié)點(diǎn)最大出度個(gè)數(shù)的對(duì)數(shù)的向上取整值，如式(14)所示。

圖1 適應(yīng)度升序排列仿真內(nèi)容和仿真結(jié)果

圖2 局部搜索仿真結(jié)果

數(shù)據(jù)由節(jié)點(diǎn)vi傳向相鄰節(jié)點(diǎn)vj時(shí)，(e={vi→v j}(i≠j))，兩節(jié)點(diǎn)之間路徑上的二進(jìn)制編碼取決于節(jié)點(diǎn)的出度。當(dāng)某一傳感器節(jié)點(diǎn)的出度為1 時(shí)，表示由該節(jié)點(diǎn)引出的鏈路個(gè)數(shù)為1，即可選擇的路徑只有一條。當(dāng)傳感器節(jié)點(diǎn)的出度為2 時(shí)，表示由該節(jié)點(diǎn)引出的鏈路個(gè)數(shù)為2，即可選擇的路徑有2 條，通過采用二進(jìn)制編碼表示路徑的選擇，一條路徑用0 編碼，則另外一條路徑用1 來編碼。例如，當(dāng)傳感器節(jié)點(diǎn)的出度為4 時(shí)，用2 個(gè)二進(jìn)制比特位來表示路徑的選擇，分別是00、01、10、11。將基因位上的二進(jìn)制數(shù)轉(zhuǎn)換成十進(jìn)制整數(shù)，然后根據(jù)該十進(jìn)制整數(shù)選擇鏈路。如果其超過了當(dāng)前節(jié)點(diǎn)的出度的最大值，則算法取整除出度所得的余數(shù)作為鏈路編號(hào)。如果在個(gè)體上的所有基因位之前完成了鏈路選擇，則剩下的基因位將忽略不計(jì)。最后將個(gè)體的二進(jìn)制編碼轉(zhuǎn)化為由節(jié)點(diǎn)序號(hào)組成的路徑p(v1,vn)，通過該方式生成一條路徑。

3.2 種群初始化

在D維空間問題解的集合，隨機(jī)產(chǎn)生N只青蛙（問題的解）為最初的部族，初始種群可以表示為X={X1,X2,…,X,…,XN}，第i只青蛙表示為，將青蛙種群按照數(shù)據(jù)在傳輸鏈路上產(chǎn)生的能量損耗的適應(yīng)度排序，選取出能量損耗最低的青蛙編碼為Xg_min。

3.3 計(jì)算適應(yīng)度

多條件限制的QoS 單播路由選擇優(yōu)化問題中，在滿足時(shí)延、鏈路帶寬、分組丟失率、抖動(dòng)時(shí)延條件的情況，適應(yīng)度函數(shù)可通過式(9)計(jì)算，從而得出種群中每一只青蛙在數(shù)據(jù)傳輸過程中產(chǎn)生的能耗，能耗越小，說明青蛙被遺傳到下一代的可能性越高。

3.4 子種群劃分

將全體青蛙群體分為J個(gè)子種群，每個(gè)子種群中有I個(gè)青蛙個(gè)體，子種群按照以下規(guī)則劃分：第1 只青蛙屬于第1 子種群，第2 只青蛙屬于第2 個(gè)子種群，第3 只青蛙屬于第3 個(gè)子種群，第J+1 只青蛙放入第1 個(gè)子種群,第J+2 只青蛙放入第2 個(gè)子種群，依次類推，直至所有子種群中都有I只青蛙。記錄每個(gè)子種群中能耗最小的青蛙Xb_min和能耗最大青蛙Xb_max。

3.5 局部搜索

局部搜索僅針對(duì)子種群內(nèi)的青蛙進(jìn)行更新。針對(duì)每個(gè)子種群，找到子種群中數(shù)據(jù)傳輸能耗最高的個(gè)體Xb_max，個(gè)體的更新方式如式(15)和式(16)所示。

其中，rand 為0～1 的隨機(jī)小數(shù)，Xb_min為子種群中能耗最小的青蛙，Xb_max為子種群中能耗最大的青蛙，Ri為青蛙的步長(zhǎng)，每一步的步長(zhǎng)不能超過最大步長(zhǎng)，即?Rmax≤Ri≤Rmax。

若更新后的適應(yīng)度小于子種群內(nèi)的最優(yōu)適應(yīng)度，則用更新后的個(gè)體取代當(dāng)前最差個(gè)體，若沒有任何優(yōu)化，則隨機(jī)任意選取一個(gè)新的青蛙代替部族中原始的青蛙，反復(fù)進(jìn)行上述局部搜索操作genmax次，genmax為子種群的最大迭代次數(shù)。

3.6 全局搜索

經(jīng)過局部搜索后，重新計(jì)算更新后的所有青蛙個(gè)體的數(shù)據(jù)傳輸鏈路能耗，并由小到大進(jìn)行排序。例如，當(dāng)種群中有40 只青蛙，每只青蛙代表路由能耗時(shí)，一次全局排序的仿真結(jié)果如圖3 所示，方框中數(shù)字為局部搜索新生成的青蛙能耗。

將全局能耗最低的個(gè)體設(shè)為Xg_min，該青蛙作為全局最優(yōu)青蛙保存在每一代中，全局最差青蛙為Xb_max，全局搜索針對(duì)整個(gè)種群的最差適應(yīng)度個(gè)體進(jìn)行更新，全局更新式如式(17)和式(18)所示。

3.7 克隆免疫算子

圖3 全局排序仿真結(jié)果

免疫克隆算子是結(jié)合免疫生物學(xué)說與抗體克隆的優(yōu)勢(shì)而提出的一種新型算子。在免疫克隆算子中，一個(gè)抗體對(duì)應(yīng)QoS 路由優(yōu)化問題的一個(gè)可行路徑，適應(yīng)度對(duì)應(yīng)路徑上的能量損耗。該算子有效保證了種群的多樣性，并保證算法有效收斂。例如，當(dāng)種群中最優(yōu)青蛙（能耗為0.706 4）被克隆變異10 份后，一次仿真結(jié)果如圖4 所示。

由圖4 可以看出，克隆變異后部分青蛙能耗低于原青蛙，而部分青蛙則高于原青蛙。

3.8 算法流程

IICSFLA 算法具體流程如下。

步驟1算法參數(shù)的初始化。初始化青蛙的種群大小N，搜尋空間的維數(shù)為D，子種群數(shù)為J，每一組子種群中包括I只青蛙(N=IJ)，每一個(gè)青蛙個(gè)體的位置變化最大值（步長(zhǎng)）為Rmax，局部查找的次數(shù)為genmax，全局變量的迭代周期為MAXGEN。

步驟2青蛙群體的編碼及初始化。隨機(jī)產(chǎn)生一個(gè)由N只青蛙個(gè)體構(gòu)成的原始部族。

步驟3將個(gè)體的二進(jìn)制編碼轉(zhuǎn)化為由節(jié)點(diǎn)序號(hào)組成的路徑p(v1,vn)。

步驟4計(jì)算適應(yīng)度。通過式(9)計(jì)算適應(yīng)度函數(shù)值，將青蛙群體按照適應(yīng)度升序依次排列，選取并記錄具備最低能耗的青蛙個(gè)體。

步驟5克隆種群中路徑損耗最低的二進(jìn)制個(gè)體，如果找到好的二進(jìn)制個(gè)體，用該個(gè)體更新種群中最優(yōu)個(gè)體。

步驟6子種群的產(chǎn)生。將N分割成J個(gè)子種群，每個(gè)子種群均包括I個(gè)個(gè)體，將子種群的個(gè)體按照適應(yīng)度由小到大排序，并進(jìn)行個(gè)體與子種群間的公平分配，選取并記錄具備最佳適應(yīng)度及具有最差適應(yīng)度的青蛙個(gè)體。

步驟7子種群的進(jìn)化（局部搜索）。針對(duì)子種群中選取出的最差個(gè)體，讓其按照蛙跳算法規(guī)則實(shí)行局部搜索操作，新的位置改進(jìn)取決于式(16)，經(jīng)過計(jì)算，得出其青蛙個(gè)體的適應(yīng)度。記錄改進(jìn)后的青蛙部族子種群中最差個(gè)體與最優(yōu)個(gè)體。

步驟8子種群的重新混合（全局搜索）。將進(jìn)化后的子種群中的青蛙群體進(jìn)行重新組合，對(duì)新的種群集合依據(jù)其適應(yīng)度升序排列，選出最優(yōu)與最差個(gè)體，并對(duì)最差個(gè)體通過式(17)與式(18)進(jìn)行更新。

步驟9算法結(jié)束條件。若達(dá)到最大迭代次數(shù)，結(jié)束更新蛙群，并輸出最優(yōu)解；否則，返回步驟3。

4 仿真與實(shí)驗(yàn)

仿真實(shí)驗(yàn)通過MATLAB 2012a 完成。假設(shè)一個(gè)區(qū)域范圍內(nèi)有20 個(gè)傳感器節(jié)點(diǎn)，數(shù)據(jù)通過這些節(jié)點(diǎn)進(jìn)行傳輸，數(shù)據(jù)在相鄰節(jié)點(diǎn)間傳輸將會(huì)受時(shí)延、時(shí)延抖動(dòng)、分組丟失率、鏈路帶寬的影響。假設(shè)Eelec=50 nJ/bit，εamp1=10 pJ/(bit ?m2)，εamp2=0.0015 pJ/(bit ?m4)，k=1Mbit，d0=1m。設(shè)最大時(shí)延為105 ms，最小鏈路帶寬為8 Mbit/s，最大時(shí)延抖動(dòng)為36 ms，最大分組丟失率設(shè)為1%。

在仿真中，將IICSFLA 和自適應(yīng)遺傳算法（AGA,adaptive genetic algorithm）、自適應(yīng)蟻群優(yōu)化（AACO,adaptive ant colony optimization）算法進(jìn)行對(duì)比，AGA 和AACO 的參數(shù)的初始設(shè)置根據(jù)經(jīng)驗(yàn)獲得，并在算法運(yùn)行過程中自適應(yīng)調(diào)整，3 種算法的迭代次數(shù)為100 次，參數(shù)如表1～表3 所示。

表1 IICSFLA 初始參數(shù)

表2 AGA 初始參數(shù)

表3 AACO 初始參數(shù)

在QoS 單播路由問題中，在多約束條件下找到一條從源節(jié)點(diǎn)到終端節(jié)點(diǎn)間所需能量損耗最低的路徑。在優(yōu)化數(shù)據(jù)傳輸?shù)逆溌窌r(shí)，能量損耗作為優(yōu)化目標(biāo)，時(shí)延、分組丟失率、鏈路帶寬、時(shí)延抖動(dòng)只作為約束條件，且必須保持在約束條件以內(nèi)。

圖4 免疫克隆算子仿真結(jié)果

在傳輸數(shù)據(jù)之前，所有節(jié)點(diǎn)都處于休眠狀態(tài)，此時(shí)不消耗能量，根據(jù)傳感器的鏈路帶寬、時(shí)延、分組丟失率、時(shí)延抖動(dòng)的條件限制找到一條能量消耗最小的路徑，并將該路徑上的節(jié)點(diǎn)設(shè)為開啟狀態(tài)，此后數(shù)據(jù)的傳輸皆在此路徑上進(jìn)行。

圖5～圖8 分別對(duì)比了基于IICSFLA、AGA、AACO 的鏈路帶寬、時(shí)延、時(shí)延抖動(dòng)和分組丟失率?？梢钥闯?，3 種算法鏈路帶寬皆大于最小帶寬，時(shí)延均小于最大時(shí)延，時(shí)延抖動(dòng)均小于最大時(shí)延抖動(dòng)，分組丟失率均小于最大分組丟失率。

圖5 為3 種算法的鏈路帶寬對(duì)比。在路由過程中，鏈路帶寬越大通信質(zhì)量越好?？梢钥闯?，3 種算法迭代后的鏈路帶寬均大于最小鏈路帶寬8 Mbit/s，經(jīng)過IICSFLA 迭代后的鏈路帶寬為9.066 Mbit/s，AGA和AACO 迭代后的鏈路帶寬分別為8.809 Mbit/s和8.624 Mbit/s，即經(jīng)過IICSFLA 迭代后的鏈路帶寬最大。

圖5 鏈路帶寬對(duì)比

圖6 時(shí)延對(duì)比

圖6 為3 種算法的時(shí)延對(duì)比。在路由過程中，時(shí)延越小通信質(zhì)量越好?？梢钥闯?，3 種算法迭代后的時(shí)延均小于最大時(shí)延為105 ms。IISFLA 迭代后時(shí)延最小，為67.05 ms；AGA 和AACO 迭代后時(shí)延較大，分別為69.16 ms 和71.06 ms。

圖7 為3 種算法的時(shí)延抖動(dòng)對(duì)比，時(shí)延抖動(dòng)越小通信質(zhì)量越好。3 種算法迭代后的時(shí)延抖動(dòng)均小于最大時(shí)延抖動(dòng)36 ms。IICSFLA、AGA、AACO迭代后的時(shí)延抖動(dòng)分別為19.04 ms、21.17 ms 和23.06 ms，即IICSFLA 迭代后時(shí)延抖動(dòng)最小。

圖7 時(shí)延抖動(dòng)對(duì)比

圖8 為3 種算法的分組丟失率對(duì)比。3 種算法迭代后的分組丟失率均小于最大分組丟失率1%。IICSFLA、AGA、AACO 迭代后的分組丟失率分別為0.230 5%、0.252 6%和0.271 1%，即IICSFLA 迭代后的分組丟失率最小。

圖8 分組丟失率對(duì)比

圖9 為節(jié)點(diǎn)數(shù)量為20 時(shí)，3 種算法在迭代100次后的能耗對(duì)比。由圖9 可知，當(dāng)傳感器節(jié)點(diǎn)數(shù)量為20 時(shí)，100 次迭代后IICSFLA、AGA、AACO的能耗分別為0.662 2 J、0.692 2 J 和0.716 6 J，AGA 和AACO 能耗比IICSFLA 分別高出4.53%和8.22%。由此可知，IISFLA 在加入了克隆免疫算子后，將能耗較低的青蛙個(gè)體當(dāng)成記憶細(xì)胞以較大的概率保留到下一代種群中，相反，能耗較高的青蛙個(gè)體被遺傳至下一代的概率較低。在時(shí)延、分組丟失率、鏈路帶寬、時(shí)延抖動(dòng)都滿足條件的情況下，能夠有效找到一條能耗最低的路徑，體現(xiàn)了強(qiáng)穩(wěn)健性，也提高了算法的收斂速度。

圖9 節(jié)點(diǎn)數(shù)為20 時(shí)的能耗對(duì)比

圖10 為節(jié)點(diǎn)數(shù)量為30 時(shí)，3 種算法在迭代100次后的能耗對(duì)比。由圖10 可知，當(dāng)傳感器節(jié)點(diǎn)數(shù)量為30 時(shí)，100 次迭代后IICSFLA、AGA 和AACO的能耗分別為0.851 7 J、0.889 2 J 和0.9237 J。初始參數(shù)不變的情況下，AGA 和AACO 比IICSFLA的能耗分別高出4.40%和8.45%。

圖10 節(jié)點(diǎn)數(shù)為30 時(shí)的能耗對(duì)比

圖11 為節(jié)點(diǎn)數(shù)量為40 時(shí)，3 種算法在迭代100次后的能耗對(duì)比。由圖11 可知，當(dāng)傳感器節(jié)點(diǎn)數(shù)量為40 時(shí)，IICSFLA、AGA、AACO 在100 次迭代后的能耗分別為1.304 J、1.370 J、1.429 J。100 次迭代后的AGA 和AACO 能耗比IICSFLA 分別高出5.06%和9.59%。

由上述仿真結(jié)果可知，混合免疫克隆算法的IICSFLA 具有更強(qiáng)的全局搜索能力，有效降低了路徑上的能量損耗。

圖11 節(jié)點(diǎn)數(shù)為40 時(shí)的能耗對(duì)比

5 結(jié)束語

針對(duì)多條件限制的QoS 路由優(yōu)化問題，本文首先設(shè)計(jì)了系統(tǒng)模型，在時(shí)延、鏈路帶寬、分組丟失率、時(shí)延抖動(dòng)這些條件的限制下，計(jì)算數(shù)據(jù)在傳輸鏈路上的能量損耗。為了優(yōu)化路由選擇，提出了一種改進(jìn)的免疫克隆蛙跳算法，該算法結(jié)合了傳統(tǒng)蛙跳算法和免疫克隆算法的優(yōu)點(diǎn)，在對(duì)IICSFLA 進(jìn)化過程中，進(jìn)行種群編碼、種群初始化、種群劃分、局部搜索、全局搜索，通過加入克隆免疫算子，將能耗較低的青蛙個(gè)體以較大的概率遺傳至下一代抗體群，使進(jìn)化后的SFLA 具備更加全面的全局搜索的能力。在仿真中，將所提算法與AACO與AGA 進(jìn)行對(duì)比，結(jié)果顯示，所提算法具有更快的收斂速度，能更有效地找到一條能耗最小的傳輸路徑。