基于改進(jìn)克隆算法的WSN 的QoS 路由研究

肖 剛，謝 紅

(哈爾濱工程大學(xué) 信息與通信工程學(xué)院，哈爾濱 150001)

無線傳感器網(wǎng)絡(luò)(Wireless Sensor Network，WSN)是一種由大量隨機(jī)分布的微小傳感器節(jié)點，以自組織的方式構(gòu)成的大規(guī)模、無人值守、能量受限的分布式網(wǎng)絡(luò)，其傳感節(jié)點包含傳感器、數(shù)據(jù)處理單元和通信模塊.無線傳感網(wǎng)絡(luò)具有廣闊的應(yīng)用前景，但其自身也存在著環(huán)境等約束問題，并且其在通信交互過程中傳輸、路由等也受到各種約束［1］.因此，只有綜合考慮平衡各種約束才能客觀解決實際問題，才能最優(yōu)地選擇更適合的傳感器節(jié)點，保證在最優(yōu)路徑選擇基礎(chǔ)上，節(jié)約了通信成本.提高服務(wù)質(zhì)量(QoS)成了WSN 設(shè)計中的一個主要問題.在WSN 中，QoS 路由的目的就是在網(wǎng)絡(luò)中尋找滿足系統(tǒng)對路徑的帶寬、時延、丟包率、費用要求的路由，而基于多個不相關(guān)可加度量的QoS 路由問題是NP 完全問題.

本文在克隆選擇算法和蟻群算法融合的基礎(chǔ)上，提出了一種克隆蟻群算法，克隆選擇算法在搜索的初期具有較高向最優(yōu)解收斂的速度，可以快速對解空間全局搜索，將更優(yōu)秀的解保存在記憶庫，更快地引導(dǎo)蟻群系統(tǒng)找到全局最優(yōu)解.但伴隨著搜索的持續(xù)進(jìn)行，由于針對系統(tǒng)中的反饋信息利用不足會導(dǎo)致大量無用的冗余迭代，使求最優(yōu)解的效率顯著降低［2］.而蟻群算法在搜索的初期受限于信息素的缺乏，使得搜索速度相對緩慢，只有當(dāng)積累信息素到一定的強(qiáng)度后，通過信息素的累積和更新收斂最優(yōu)路徑解，將最優(yōu)解的收斂的速度顯著提高.本文將該算法應(yīng)用于QoS 路由研究中，仿真結(jié)果表明，克隆蟻群算法的求解性能要明顯優(yōu)于常規(guī)的蟻群算法.

1 克隆選擇算法原理

克隆選擇算法是一種由無性繁殖過程中生物獲得免疫進(jìn)化來的優(yōu)化算法，當(dāng)免疫細(xì)胞持續(xù)產(chǎn)生基因突變，細(xì)胞的多樣性得到了極大豐富.當(dāng)生物體內(nèi)免疫細(xì)胞的多樣性到達(dá)了某種程度后，每種抗原入侵機(jī)體都能被機(jī)體識別，并且機(jī)體能可以克隆出相應(yīng)的免疫細(xì)胞并激活，分化和增殖，進(jìn)行免疫應(yīng)答，進(jìn)而最后消滅抗原.克隆算法分別在抗體種群和優(yōu)秀抗體記憶集中實現(xiàn)克隆選擇操作，全面地模擬了生物免疫系統(tǒng)克隆選擇的過程，更好地保持了抗體種群的多樣性［3］.算法描述如下:

1)抗體初始化:首先確定抗原，然后隨機(jī)產(chǎn)生若干個抗體，Ad為抗體集合，其由臨時抗體集Ad{r}和記憶抗體集Ad{m}兩個集合組成.

2)抗體親合力計算:計算Ad 中每個抗體的親合力.

3)抗體選擇:從Ad 中連續(xù)選擇n個親和力最高的抗體，生成臨時抗體集Ad{r}.

4)抗體克隆:分別對已選擇的n個抗體進(jìn)行克隆復(fù)制，按照抗體親合力高低，成一定比例進(jìn)行抗體的克隆復(fù)制.

5)抗體變異:對克隆后的抗體集進(jìn)行變異操作.

6)抗體選擇:再次計算變異后的新抗體集的親合力，評估變異后的抗體［4－5］，如果抗體親合力優(yōu)于Ad{r}中抗體的親合力，則用新抗體替換原抗體，產(chǎn)生記憶抗體集Ad{m}.

7)抗體記憶:利用m個新產(chǎn)生的抗體替換Ad中親合力較低的m個抗體，保護(hù)了抗體的多樣性.

8)判斷是否達(dá)到進(jìn)化條件:評估是否達(dá)到進(jìn)化條件，如不達(dá)標(biāo)，轉(zhuǎn)2)，執(zhí)行下一輪進(jìn)化，否則，轉(zhuǎn)9).

9)抗體解碼，輸出問題的解.

2 蟻群算法原理

蟻群算法是一種應(yīng)用于組合優(yōu)化問題的啟發(fā)式仿生優(yōu)化算法，螞蟻在覓食的活動中，可以在其途徑的路徑上留下信息素，并且螞蟻是通過路徑上的信息素強(qiáng)度來決定選擇該路徑的概率.路徑上的信息素是根據(jù)選擇這條路徑螞蟻的多少來按比例增加的，信息素強(qiáng)的路徑被后繼螞蟻選擇的概率也高，進(jìn)而該路徑的信息素強(qiáng)度持續(xù)增強(qiáng).信息素越強(qiáng)會吸引越多的螞蟻，這種自發(fā)的集體行為產(chǎn)生了一種信息正反饋機(jī)制.在此機(jī)制下，螞蟻可以找到巢穴和食物源之間的最短路徑.

蟻群算法的優(yōu)點是良好的分布式計算機(jī)制，靈敏的正反饋性，較強(qiáng)的穩(wěn)健性，易于與其他算法融合等特點.不過蟻群算法因為易早熟，初始搜索比較盲目，運算時間較長等缺點，造成了其使用范圍受限.為了更好的解決這些缺點，很多學(xué)者針對不同切入點和情況，將蟻群算法和其他算法結(jié)合，創(chuàng)造出了性能更優(yōu)越的復(fù)合算法，改進(jìn)信息素更新策略，制定選擇策略，加入其他算法算子等方式，都是目前主要對蟻群算法改進(jìn)的方向.

3 WSN 網(wǎng)絡(luò)QoS 組播路由模型

QoS 路由問題是在滿足一個或多個QoS 條件基礎(chǔ)上，尋找傳播路徑的問題，可以將其抽象成求最小值的數(shù)學(xué)模型.Steiner 樹是一棵連接所有節(jié)點的總代價最小的分布樹，它使連接特定圖中的特定組成員所需的鏈路數(shù)最少.已知求解Steiner 樹是一種P=NP 的NPC 問題，但因為在實際的無線傳感器網(wǎng)絡(luò)中存在各種限制條件，所以高復(fù)雜度算法不適用于求解WSN 中的QoS 問題，故采用啟發(fā)式算法求解Steiner 樹.

在無線傳感器網(wǎng)絡(luò)中，一般從以下兩方面考慮QoS 組播路由:業(yè)務(wù)方面和網(wǎng)絡(luò)能耗.其中業(yè)務(wù)方面需要滿足業(yè)務(wù)提出的帶寬，延遲、時延抖動，丟包率等QoS 要求;而網(wǎng)絡(luò)能耗方面為了能延長網(wǎng)絡(luò)節(jié)點使用壽命.

網(wǎng)絡(luò)模型可以表示成賦權(quán)圖G(V，E)，式中V是圖中所有網(wǎng)絡(luò)節(jié)點的集合，E 是網(wǎng)絡(luò)雙向路徑的集合［6］，每一條邊代表每2個節(jié)點之間的通信路徑，假設(shè)網(wǎng)絡(luò)是對稱的.T(s，M)表示組播樹，其中s∈V為源點，M∈{V－{s}}為終點.

組播樹T(s，M)中，存在下列關(guān)系:

其中:PT(s，t)是組播樹T(s，M)上源點s和終點t 間的路由［7］.

其中:DL、BW、PL 分別為業(yè)務(wù)對網(wǎng)絡(luò)時延、帶寬、和包丟失率的約束限制.在多數(shù)現(xiàn)實情況中，時延和包丟失率是最需要優(yōu)先考慮的，故本文只綜合考慮時延和包丟失率，帶寬等約束.

4 克隆蟻群算法設(shè)計

4.1 克隆選擇算法關(guān)鍵部分

4.1.1 初始抗體的生成和新群體的產(chǎn)生

對網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)進(jìn)行精簡處理，本文中通過刪除不滿足指定帶寬約束的鏈路，將網(wǎng)絡(luò)精簡成新的，高效的網(wǎng)絡(luò)，若源點s和終點t 處于同一連通分量，即把此連通分量作為算法研究的基圖［8］.以下的研究將忽略帶寬約束，只考慮延遲、丟包率和費用度量.

4.1.2 抗體的評價

抗體與抗原間的親和度作為抗體的優(yōu)劣是判斷依據(jù)，其親和度定義為:

其中:A，B，C 分別為fpl，fbw，fdl的加權(quán)系數(shù)，分別表示包丟失率、帶寬和延時在目標(biāo)函數(shù)中所占的比重.其值根據(jù)系統(tǒng)情況具體設(shè)置，在本系統(tǒng)中，由于更側(cè)重信息的安全性，分別設(shè)置A=1，B=0.8，C=0.8，Θpl，Θbw，Θdl是包丟失率，帶寬，時延的懲罰函數(shù)，當(dāng)滿足各自約束條件時值為1，否則為0.5.

4.1.3 克隆，交叉，變異

依據(jù)式(8)計算出全部個體的親和度，從中選擇n個親和度最高的個體;克隆規(guī)模根據(jù)親和度高低按正比比例復(fù)制選出的個體，形成一個臨時種群C.對于臨時種群C，首先執(zhí)行概率的交叉操作，為了避免產(chǎn)生不合理路徑，本文采用單點交叉方法.從群體中隨機(jī)選擇兩條路徑，從中隨機(jī)選擇兩個節(jié)點a、b，交換a，b 之間的部分，然后刪除路徑中重復(fù)部分.然后對其進(jìn)行高頻變異，隨機(jī)選取一個路徑，在該路徑中隨機(jī)找一個節(jié)點k，然后以k為起點，以原目的節(jié)點為終點，隨機(jī)搜索一條不含k 之前所有節(jié)點的節(jié)點取代k.獲得一個變異后的抗體群C .記憶單元M 由改進(jìn)的克隆個體組成，并添加到候選解集中，作為新一代候選解集P.依據(jù)更新概率，最后隨機(jī)產(chǎn)生了一些新的抗體替換d個親合度低的舊抗體，保證了抗體的多樣性.

4.1.4 結(jié)束條件

判斷是否達(dá)到循環(huán)終止條件.將親和度的最大閾值或最大允許的迭代次數(shù)設(shè)為循環(huán)終止條件［9］.如果滿足，將當(dāng)前的記憶集保存，結(jié)束循環(huán).否則，轉(zhuǎn)第3 步.

4.2 蟻群算法關(guān)鍵部分

4.2.1 路徑的選擇

假設(shè)螞蟻k 由當(dāng)前城市i 選擇下一個要走的節(jié)點j，則所依據(jù)的概率轉(zhuǎn)換規(guī)則為:

其中:α 表示第k 只螞蟻在運動過程中積累的信息素濃度，β 表示啟發(fā)因子在螞蟻選擇路徑中的重要程度，allowedk包含著螞蟻k 下一步允許轉(zhuǎn)移的節(jié)點子集，ηij(t)代表搜索路徑中的啟發(fā)信息，τij(t)表示在t 時刻鏈路(i，j)上的信息素量.

4.2.2 局部信息素的更新規(guī)則

為避免信息素殘留導(dǎo)致啟發(fā)信息被淹沒，當(dāng)螞蟻成功完成路徑選擇后，要對路徑上的信息素按如下公式進(jìn)行局部更新:

其中:0 ＜p1＜1，表示信息素?fù)]發(fā)系數(shù)，cost(PT(s，t))為第k 只螞蟻在一次循環(huán)中所花費的總費用，由于在程序中對帶寬進(jìn)行了約束處理，所以cost(PT(s，t))并不包含fbw.D，E 是時延和丟包率的加權(quán)系數(shù)，考慮到丟包率在實際系統(tǒng)中的值比較小，通過控制加權(quán)系數(shù)使時延和丟包率維持相對平衡，在本系統(tǒng)中，D=0.5，E=100.Q 是常量，用于調(diào)整信息素強(qiáng)度.當(dāng)沒有局部更新時，螞蟻將在上一次選擇的最佳路徑的相鄰區(qū)域內(nèi)搜索.

5 仿真實驗及結(jié)果

實驗仿真如圖1所示.仿真過程中，網(wǎng)絡(luò)拓?fù)淠Ｐ褪墙⒃?0 km×20 km 的正方形區(qū)域內(nèi)，由基于C－均值聚類的隨機(jī)網(wǎng)絡(luò)拓?fù)渖善麟S機(jī)在該區(qū)域內(nèi)隨機(jī)生成50個節(jié)點，其鏈路帶寬在［1，20］之間、節(jié)點能量在［1，20］之間隨機(jī)產(chǎn)生，其中時延的取值為兩節(jié)點間的距離除以2/3 光速，單位為ms，帶寬單位為MB/s.通過多次試驗，選出拓?fù)鋱D最好的作為研究環(huán)境［10－11］，見圖1，各個邊的特性用三元組(b，d，r)描述，其中b、d、r 分別表示帶寬、延時和丟包率.同時，選出源節(jié)點S=1和目的節(jié)點集Des=［6 9 10 15 20 24 31 36 42 48］.

圖1 仿真使用的網(wǎng)絡(luò)拓?fù)淠Ｐ?/p>

通過把CSACO(克隆蟻群算法)與ACO(蟻群算法)仿真結(jié)果進(jìn)行對比，評價費用和端到端時延這兩個性能指標(biāo)參數(shù).如圖2所示，可見總費用隨著迭代次數(shù)增加，CSACO 與ACO 的費用都有所下降，但CSACO 要稍好，這是因為CSACO 在數(shù)據(jù)傳輸時，在保證丟包率和時延基礎(chǔ)上，可以極大程度選擇更好的路徑進(jìn)行傳輸，提高了成功率.

圖2 CSACO 與ACO 總費用比較圖

如圖3所示，時延隨著迭代次數(shù)的變化情況逐步下降.其中CSACO 算法比ACO 算法在時延方面表現(xiàn)出更好的性能.這是因為CSACO 將時延作為QoS 約束條件之一，所以會在選擇路由過程中挑選時延參數(shù)更合理的路徑.

圖3 端對端時延比較圖

由圖2、3 可以看出，隨著迭代次數(shù)的增加，時延和費用的變化不是遞減的，而費用值是逐漸減小的，直到收斂于恒定值，符合QoS 多約束的規(guī)律.

表1 中，Max 代表運行50 次實驗最小費用Cost 的最大值，Min 代表最小值，Average 代表平均值，Var 代表方差，Diedai 代表找到最小費用Cost的平均迭代次數(shù)，Time 代表運行50 次的總時間.從表1 中的數(shù)據(jù)可以看出，CSACO 算法得到最小費用Cost 的平均值、平均迭代次數(shù)和方差都比較小，故性能穩(wěn)定.

表1 50 次實驗，算法平均指標(biāo)比較

6 結(jié)語

針對WSN 網(wǎng)絡(luò)QoS 組播路由問題，提出了一種基于改進(jìn)克隆算法的QoS 組播路由算法.本算法在蟻群算法基礎(chǔ)上融合了克隆選擇算法的快速隨機(jī)的全局搜索能力，解決了常規(guī)蟻群算法的收斂速度慢、易過早局部最優(yōu)等缺點.仿真結(jié)果表明，CSACO 算法提高了路由搜索速度，在保證最優(yōu)路徑選擇基礎(chǔ)上，節(jié)約了通信成本.

［1］于海斌，曾 鵬，梁 韋.智能無線傳感器網(wǎng)絡(luò)系統(tǒng)［M］.北京:科學(xué)出版社，2006:30－40.

［2］肖 偉，全惠云，劉 楓.基于蟻群算法的多路徑多約束QoS路由的研究［J］.計算機(jī)工程與應(yīng)用，2008，30(7):89－94.

［3］焦李成.多目標(biāo)優(yōu)化免疫算法、理論和應(yīng)用［M］.北京:科學(xué)出版社，2010:150－184.

［4］畢曉君.信息智能處理技術(shù)［M］.北京:電子工業(yè)出版社，2010:310－314.

［5］［南非］ENGELBRECHT A P，著.計算群體智能基礎(chǔ)［M］.譚營，譯.北京:清華大學(xué)出版社，2009:344－356.

［6］胡 細(xì).移動自組織網(wǎng)絡(luò)中若干問題的建模與分析［D］.上海:上海大學(xué)，2007.

［7］孫利民，李建中，陳 渝，等.無線傳感器網(wǎng)絡(luò)［M］.北京:清華大學(xué)出版社，2005:248－254.

［8］SALAMA H F.Multicast routing for real－time communication of high－speed networks［D］.Raleigh:North Carolina State University，2006:28－37.

［9］［美］STALLINGS W.無線通信與網(wǎng)絡(luò)［M］.何 軍，譯.北京:電子工業(yè)出版社，2006:267－278.

［10］蔡 慧，劉洪波.基于K 均值聚類的隨機(jī)網(wǎng)絡(luò)拓?fù)淠Ｐ停跩］.計算機(jī)工程與設(shè)計，2009，30(5):1089－1901.

［11］那成亮，周廷顯，蘆東昕.基于博弈的無線傳感網(wǎng)絡(luò)功控算法收斂性分析［J］.哈爾濱商業(yè)大學(xué)學(xué)報:自然科學(xué)版，2007，23(1):92－95.