徐 昕，顧云麗，張嫣娟

（1.南京信息工程大學(xué)江蘇省網(wǎng)絡(luò)監(jiān)控中心，南京210044；2.南京信息工程大學(xué)計(jì)算機(jī)與軟件學(xué)院，南京210044）

基于磷蝦群算法的無(wú)線傳感器網(wǎng)絡(luò)QoS任播路由算法*

徐 昕1，2*，顧云麗1，2，張嫣娟2

（1.南京信息工程大學(xué)江蘇省網(wǎng)絡(luò)監(jiān)控中心，南京210044；2.南京信息工程大學(xué)計(jì)算機(jī)與軟件學(xué)院，南京210044）

無(wú)線傳感器網(wǎng)絡(luò)多約束QoS任播路由問(wèn)題是一個(gè)NP難題，提出一種基于磷蝦群算法的優(yōu)化策略來(lái)解決該路由問(wèn)題。該算法采用適應(yīng)度函數(shù)和全局最優(yōu)個(gè)體位置更新方法來(lái)尋找無(wú)線傳感器網(wǎng)絡(luò)中滿足多QoS約束的最優(yōu)任播路由，并加入遺傳繁殖機(jī)制中的交叉與變異操作以加快優(yōu)化速度。實(shí)驗(yàn)驗(yàn)證了該算法的有效性，實(shí)驗(yàn)數(shù)據(jù)表明相比較粒子群優(yōu)化算法，該算法在算法效率和可擴(kuò)展性性能上具有較好的性能；具有較快的收斂速度，從而適用于對(duì)路由選擇有時(shí)延敏感的網(wǎng)絡(luò)。

無(wú)線傳感器網(wǎng)絡(luò)；路由算法；磷蝦群算法；任播

磷蝦群算法KH（Krill Herd Optimization）是近年來(lái)由Gandomi［1］提出的一種新型的元啟發(fā)式群體智能優(yōu)化算法。該算法的主要思想是模仿磷蝦個(gè)體在食物位置和磷蝦群密度等因素影響下的移動(dòng)過(guò)程，因此具有在連續(xù)空間的非線性優(yōu)化性能。

磷蝦群算法提出后，收到一些學(xué)者的極大關(guān)注并應(yīng)用于各個(gè)科研領(lǐng)域。Deng［2］采用磷蝦群算法優(yōu)化移動(dòng)服務(wù)共享組合問(wèn)題；針對(duì)損耗和饋線超載等問(wèn)題，Rostami［3］通過(guò)磷蝦群算法優(yōu)化電動(dòng)汽車(chē)充電負(fù)荷；Younesi［4］采用磷蝦群算法優(yōu)化永磁同步電機(jī)的轉(zhuǎn)速和轉(zhuǎn)矩控制器參數(shù)，以盡量減少穩(wěn)定狀態(tài)下速度跟蹤誤差；Sultana［5］研究關(guān)于磷蝦群算法在配電網(wǎng)電容器中的優(yōu)化應(yīng)用。在應(yīng)用中，有學(xué)者還對(duì)磷蝦群算法進(jìn)行了改進(jìn)。如Mukherjee［6］提出一種混沌磷蝦群算法，并用來(lái)最優(yōu)化處理無(wú)功優(yōu)化調(diào)度電力系統(tǒng)問(wèn)題；王磊［7］構(gòu)造一種啟發(fā)式二次對(duì)立搜索算子以提高磷蝦群算法的全局探索能力；Fattahi［8］提出一種模糊磷蝦群算法，該算法可以動(dòng)態(tài)地調(diào)節(jié)每一輪探索過(guò)程中磷蝦的探索范圍；Bulatovic［9］對(duì)磷蝦群算法中交叉因子進(jìn)行改進(jìn)從而加快尋優(yōu)速度，并將其應(yīng)用在四連桿結(jié)構(gòu)優(yōu)化設(shè)計(jì)問(wèn)題中。

由于磷蝦群算法比較新穎，以往的研究主要集中在工程優(yōu)化領(lǐng)域中。本文嘗試將磷蝦群算法應(yīng)用到無(wú)線傳感器網(wǎng)絡(luò)WSN（Wireless Sensor Networks）多約束QoS任播路由領(lǐng)域中。

WSN節(jié)點(diǎn)能量受限于有限電源（電池），節(jié)點(diǎn)傳輸能力較弱，監(jiān)控范圍較大。因此，為了節(jié)能和能耗均衡等目的，在WSN中往往部署多個(gè)基站（Sink），節(jié)點(diǎn)可以根據(jù)路由狀況將監(jiān)測(cè)信息任播（Anycast）至任一基站處。WSN往往對(duì)路由能耗、傳輸時(shí)延等有服務(wù)質(zhì)量QoS（Quality of Service）約束，這種多約束路由問(wèn)題是一個(gè)NP難題［10］。以往有學(xué)者采用遺傳算法、蟻群算法、粒子群算法等智能算法解決多約束QoS網(wǎng)絡(luò)路由問(wèn)題［11-13］，本文嘗試采用磷蝦群算法來(lái)解決多約束QoS路由問(wèn)題。

1 問(wèn)題描述

WSN拓?fù)浣Y(jié)構(gòu)抽象表示為連通圖G（V，E）。其中，V為所有傳感器節(jié)點(diǎn)的集合，共N個(gè)節(jié)點(diǎn)，E為節(jié)點(diǎn)間有向通信鏈路的集合。本文標(biāo)記：A為某任播地址；G（A）為共享A的通信組成員集合（即Sink節(jié)點(diǎn)集合）；Ai為G（A）中第i個(gè)組員；M為G（A）組員數(shù)目。為保證監(jiān)測(cè)數(shù)據(jù)分組能安全迅速到達(dá)任一Sink，本文規(guī)定發(fā)送節(jié)點(diǎn)s需同時(shí)向k個(gè)Sink進(jìn)行傳輸，因此需尋找k條任播路徑。

與傳統(tǒng)網(wǎng)絡(luò)的QoS需求略有不同，WSN由于節(jié)點(diǎn)受能量限制，其路由的重要指標(biāo)之一是節(jié)省能耗。而且，WSN路由還要盡量保證能耗均衡，這是由于一旦有節(jié)點(diǎn)快速耗盡能量，該節(jié)點(diǎn)區(qū)域?qū)o(wú)節(jié)點(diǎn)負(fù)責(zé)監(jiān)測(cè)和轉(zhuǎn)發(fā)分組，從而導(dǎo)致網(wǎng)絡(luò)分割；由于WSN節(jié)點(diǎn)傳輸能力較弱，要求能在低能耗以及不穩(wěn)定的網(wǎng)絡(luò)情況下仍能提供安全可靠的數(shù)據(jù)傳輸。除此以外，WSN往往用于軍事、環(huán)境監(jiān)控，因此還要求數(shù)據(jù)具有時(shí)效性，對(duì)網(wǎng)絡(luò)傳輸延遲有著嚴(yán)格的要求，超時(shí)傳送到Sink節(jié)點(diǎn)的數(shù)據(jù)將毫無(wú)意義，甚至成為擾亂信息影響整個(gè)系統(tǒng)監(jiān)測(cè)。

本文WSN路由QoS衡量體系設(shè)定為：節(jié)點(diǎn)能耗E，路徑剩余能量比C，端對(duì)端時(shí)延D，分組丟失率L和路徑延遲抖動(dòng)J。討論如下：

①節(jié)點(diǎn)能耗

傳輸監(jiān)測(cè)數(shù)據(jù)分組至Sink處導(dǎo)致路徑上各節(jié)點(diǎn)能耗E計(jì)算如下：

式中，E[p(s,Ai)]是路徑p(s,Ai)上各節(jié)點(diǎn)能耗之和。而

式中，Es是節(jié)點(diǎn)t傳輸監(jiān)測(cè)分組的能耗，Er是節(jié)點(diǎn)t接收監(jiān)測(cè)分組的能耗。在此不討論節(jié)點(diǎn)串聽(tīng)和空閑等待能耗（即便沒(méi)有監(jiān)聽(tīng)數(shù)據(jù)分組傳輸任務(wù)，這部分能耗仍然需要消耗）。發(fā)送和接收k比特?cái)?shù)據(jù)的能耗計(jì)算如下：

其中，n為衰減指數(shù)，本文設(shè)定為2；d為發(fā)送節(jié)點(diǎn)與接收節(jié)點(diǎn)之間的距離；節(jié)點(diǎn)發(fā)送分組時(shí)，需要放大訊號(hào)發(fā)送，其能耗參數(shù)記為Eamp；發(fā)送或接收分組時(shí)在電路運(yùn)作方面有一定的能耗，記為Eelec。

②路徑剩余能量比

在WSN中，有些節(jié)點(diǎn)會(huì)出現(xiàn)能耗過(guò)快的現(xiàn)象，從而使得網(wǎng)絡(luò)生存期較短（網(wǎng)絡(luò)生存期定義為到第一個(gè)節(jié)點(diǎn)失效的時(shí)間）。為避免或減輕該現(xiàn)象，本文采用路徑剩余能量比指標(biāo)C來(lái)盡量減少對(duì)能量較低的節(jié)點(diǎn)的使用。

其中，E(t)是節(jié)點(diǎn)t當(dāng)前剩余能量，Einit(t)是節(jié)點(diǎn)t的初始能量。本文設(shè)置能量比低于閾值C′的節(jié)點(diǎn)只參與到自己主動(dòng)發(fā)起的監(jiān)測(cè)數(shù)據(jù)匯報(bào)至Sink的傳輸任務(wù)，但不再參與到其他節(jié)點(diǎn)發(fā)起的分組轉(zhuǎn)發(fā)任務(wù)中。

③端對(duì)端時(shí)延

傳輸監(jiān)測(cè)數(shù)據(jù)分組到達(dá)Sink的端對(duì)端時(shí)延D計(jì)算如下：

式中，D[p(s,Ai)]是分組在路徑p(s,Ai)上各節(jié)點(diǎn)的時(shí)延。而

式中，Ds(t)是監(jiān)測(cè)分組在節(jié)點(diǎn)t的傳輸時(shí)延；Dq(t)是監(jiān)測(cè)分組在節(jié)點(diǎn)t的排隊(duì)等待時(shí)延。

④分組丟失率

在WSN中，往往由于無(wú)線鏈路質(zhì)量問(wèn)題導(dǎo)致數(shù)據(jù)傳輸失敗。除此以外還存在隱終端問(wèn)題（hidden terminal problems）的傳遞碰撞導(dǎo)致分組傳遞失敗。

傳輸監(jiān)測(cè)數(shù)據(jù)分組到達(dá)Sink的分組丟失率計(jì)算如下：

式中，L[p(s,Ai)]是路徑p(s,Ai)上分組丟失率。

式中，L(t)是在節(jié)點(diǎn)t的分組丟失率。

⑤延遲抖動(dòng)

傳輸監(jiān)測(cè)分組至Sink處延遲抖動(dòng)J計(jì)算如下：

式中，路徑p(s,Ai)的延遲抖動(dòng)J[p(s,Ai)]計(jì)算如下：

其中，J（l）是鏈路l的延遲抖動(dòng)。

將WSN多約束QoS任播路由問(wèn)題轉(zhuǎn)化為一個(gè)最優(yōu)化數(shù)學(xué)問(wèn)題。優(yōu)化目標(biāo)是在滿足以約束條件下尋找到能耗最小的優(yōu)化目標(biāo)。

將上述多約束優(yōu)化問(wèn)題轉(zhuǎn)化為如下無(wú)約束優(yōu)化問(wèn)題：

其中，

式中，C′，D′，L′和J′分別是路徑剩余能量比、端對(duì)端時(shí)延、分組丟失率和延遲抖動(dòng)的QoS約束值；ω0，ω1，ω2，ω3，ω4是歸一化系數(shù)，取值范圍在[0,1]。

由于f0，…，f4等值計(jì)量單位不一致，數(shù)值之間差距較大，為方便給出各自的權(quán)值系數(shù)，采用最小-最大規(guī)范化方法將各自的實(shí)驗(yàn)值映射到[0,1]區(qū)間，如f0被映射到f0'的計(jì)算過(guò)程如下：

由此，優(yōu)化問(wèn)題轉(zhuǎn)為

Minimize：

2 磷蝦群算法優(yōu)化

磷蝦群算法是近年來(lái)根據(jù)磷蝦個(gè)體的群集行為提出的一種啟發(fā)式算法。在磷蝦群整體遷移過(guò)程中，每個(gè)個(gè)體磷蝦都在一定范圍內(nèi)受到相鄰磷蝦的吸引或排斥。以磷蝦個(gè)體的位置為設(shè)計(jì)變量，給定適應(yīng)度函數(shù)，磷蝦群算法從而可以在多維搜索空間尋找食物（優(yōu)化值）。

根據(jù)磷蝦的位置移動(dòng)變化情況，其算法的主要步驟如下：

①趨光性群集運(yùn)動(dòng)

在種群中，每只磷蝦的移動(dòng)使得整個(gè)磷蝦群的位置時(shí)時(shí)刻刻都在發(fā)生變化。磷蝦i的移動(dòng)方向?qū)⑹艿狡溧徑孜r、最優(yōu)個(gè)體以及種群排斥效應(yīng)的影響。磷蝦i的移動(dòng)向量計(jì)算如下：

式中，Vmax是磷蝦群體最大引導(dǎo)速度；表示磷蝦i的上一次位置變化；ωn是權(quán)值，取值在［0，1］之間。為鄰近磷蝦個(gè)體對(duì)磷蝦i的誘導(dǎo)方向向量；為群體最優(yōu)個(gè)體對(duì)磷蝦i的誘導(dǎo)方向向量，其計(jì)算分別如下：

其中，Ni是鄰近磷蝦個(gè)體的數(shù)量；fi，fj，fworst和fbest分別是磷蝦i，磷蝦j，當(dāng)前最差和最好的目標(biāo)函數(shù)值；Xi和Xj分別是磷蝦i和磷蝦j的位置；ξ是取值在［0，1］之間的隨機(jī)值；I和Imax分別是算法當(dāng)前和最大迭代次數(shù)。

②覓食行為

磷蝦i的覓食行為描述如下：

式中，F(xiàn)i為磷蝦i覓食導(dǎo)致的位置變化；ωx為權(quán)值；Vf為覓食速度；βi為磷蝦i覓食方向向量。

③隨機(jī)游動(dòng)行為

磷蝦i的隨機(jī)游動(dòng)行為描述如下：

式中，Dmax為磷蝦個(gè)體最大擴(kuò)散速度；δ為隨機(jī)方向向量。

④位置更新

式中，Zi為磷蝦i的位置矢量，Δt為時(shí)間間隔。

算法中，對(duì)網(wǎng)絡(luò)中所有節(jié)點(diǎn)編碼，將從源節(jié)點(diǎn)到任播組組員的一條路徑序列編碼設(shè)為一個(gè)可行解。設(shè)任播組員數(shù)目為M，源節(jié)點(diǎn)至組員Ai共有j條可行路徑，其中第k條路徑（解）表示為Pik，該解是一個(gè)數(shù)字序列。因此，至組員Ai的解為向量Pi=(Pi1,Pi1,…,Pij)。由此可知，算法解集空間是一個(gè)M維的向量空間P1,P2,…,PM。如圖1中，路徑P11=S-n1-n2-n3-n4-n5-A1可以編碼表示為0-1-2-3-4-5-11，P12=S-n6-n7-n3-n4-n5-A1可以編碼表示為0-6-7-3-4-5-11，向量P1=(P11,P12)，算法解集空間為(P1,P2)。

初始磷蝦群（初始解）可通過(guò)圖的深度優(yōu)先搜索算法隨機(jī)產(chǎn)生，即將隨機(jī)找到的Np條從源節(jié)點(diǎn)到任播組員的路徑（解）作為磷蝦群的初始位置。

圖1 交叉和變異示意圖

為加快優(yōu)化速度提高優(yōu)化能力，磷蝦群算法還將遺傳繁殖機(jī)制應(yīng)用到優(yōu)化過(guò)程中，主要包括交叉和變異兩個(gè)操作。

①交叉操作

磷蝦個(gè)體以一定概率同挑選出的優(yōu)秀個(gè)體進(jìn)行交叉操作，操作如下：

式中，crossover（）表示交叉操作；Xgood是挑選出的優(yōu)秀個(gè)體。

②變異操作

磷蝦個(gè)體以一定概率基因變異，操作如下：

以圖1為示意圖舉例說(shuō)明交叉和變異操作。設(shè)已尋找到任播路徑P11=S-n1-n2-n3-n4-n5-A1，P21=S-n6-n7-n3-n8-n9-A2，如圖中黑線所示，通過(guò)交叉可以生成任播路徑P22=S-n1-n2-n3-n8-n9-A2，P12=S-n6-n7-n3-n4-n5-A1，如圖中紅虛線所示。任播路徑P21通過(guò)變異操作可以生成任播路徑P23=S-n6-n7-n10-n8-n9-A2。

算法具體流程如下：

輸入：網(wǎng)絡(luò)結(jié)構(gòu)圖G=（V，E）；k值；最大擴(kuò)散速度Dmax，時(shí)間間隔Dt，最大迭代次數(shù)Imax；權(quán)值ω0,…ω4,ωn和ωx；發(fā)送和接k比特?cái)?shù)據(jù)的能耗分別為ES和Er；種群規(guī)模NP。

Step 1 通過(guò)圖的深度優(yōu)先搜索算法隨機(jī)產(chǎn)生的Np條路徑，編碼生成解集空間；

Step 2 計(jì)算每個(gè)磷蝦的適應(yīng)度，確定當(dāng)前最優(yōu)個(gè)體；

Step 3 根據(jù)磷蝦趨光性群集運(yùn)動(dòng)、覓食運(yùn)動(dòng)和隨機(jī)游動(dòng)等行為（式（25）～式（29）），計(jì)算磷蝦個(gè)體位置變化；

Step 4 更新磷蝦群個(gè)體位置（式（30）），計(jì)算新的適應(yīng)度值；

Step 5 分別按照概率α和β，執(zhí)行交叉和變異操作，評(píng)估新產(chǎn)生磷蝦個(gè)體的適應(yīng)度值；

Step 6 IfI＜ImaxI=I+1；goto Step 2.

Else 算法結(jié)束.

輸出：最優(yōu)磷蝦個(gè)體對(duì)應(yīng)的路徑（最優(yōu)解）

4 實(shí)驗(yàn)設(shè)計(jì)與分析

以粒子群算法作為對(duì)照算法來(lái)驗(yàn)證本文所提算法的有效性及其效率。

4.1 對(duì)照算法介紹及算法性能比較分析

粒子群優(yōu)化算法PSO（Particle Swarm Optimization）將每個(gè)個(gè)體看作是N維搜索空間中的一個(gè)沒(méi)有體積的微粒，該粒子的位置對(duì)應(yīng)于優(yōu)化問(wèn)題在搜索空間的一個(gè)可行解。粒子在搜索空間中以一定的速度飛行，這個(gè)速度根據(jù)該粒子本身的飛行經(jīng)驗(yàn)和同伴的飛行經(jīng)驗(yàn)來(lái)動(dòng)態(tài)調(diào)整。其第i個(gè)微粒表示為Xi=(xi1,xi2,…xiN)，其經(jīng)歷過(guò)的最好位置記為pbest，群體中所有粒子經(jīng)歷過(guò)的最好位置為gbest。

粒子群算法的主要思想是：在每一輪迭代中，（a）粒子根據(jù)加速因子更新自己的速度和位置；（b）對(duì)每個(gè)粒子，將它的適應(yīng)值和它經(jīng)歷過(guò)的最好位置pbest作比較，如果前者較好，則將其作為當(dāng)前的最好位置pbest；（c）對(duì)每個(gè)粒子，將它的適應(yīng)值和全局所經(jīng)歷最好位置gbest的作比較，如果前者較好，則重新設(shè)置gbest的索引號(hào)。

由此可知，粒子群算法主要是通過(guò)不斷更新粒子的位置來(lái)尋優(yōu)，這與磷蝦群算法在優(yōu)化過(guò)程中有很大的相似之處（兩者在移動(dòng)過(guò)程中，都以當(dāng)前個(gè)體最優(yōu)位置和全局最優(yōu)位置作為其中一個(gè)參考對(duì)象）。

但粒子群算法對(duì)粒子移動(dòng)的算法設(shè)計(jì)比較簡(jiǎn)單，而磷蝦群算法的移動(dòng)規(guī)則更加復(fù)雜且符合真實(shí)世界中磷蝦實(shí)際移動(dòng)規(guī)律［1］；粒子群算法缺乏磷蝦群算法中覓食行為和隨機(jī)游動(dòng)等操作；相比較磷蝦群算法，傳統(tǒng)粒子群算法沒(méi)有交叉和變異操作，算法比較簡(jiǎn)單，因此在搜索解空間時(shí)，有時(shí)會(huì)出現(xiàn)粒子在全局最優(yōu)解附近振蕩的現(xiàn)象，從而有時(shí)無(wú)法找到全局最優(yōu)解。文獻(xiàn)［1］等其他文獻(xiàn)給出數(shù)十個(gè)算例證明磷蝦群算法優(yōu)化效果優(yōu)于傳統(tǒng)粒子群算法。

將粒子群算法應(yīng)用到多約束QoS路由問(wèn)題已有較多的研究成果［11-12］，本文仿真實(shí)驗(yàn)比較磷蝦群算法在多約束QoS路由問(wèn)題中的算法性能。

4.2 仿真實(shí)驗(yàn)和分析

以圖1所示的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)進(jìn)行仿真實(shí)驗(yàn)來(lái)評(píng)價(jià)本文算法有效性。

圖1中五元組(E,C,D,L,J)分別表示該節(jié)點(diǎn)的接收和傳輸能耗，剩余能量比，接收和傳輸時(shí)延，分組丟失率L和延遲抖動(dòng)。QoS約束(C′,D′,L′,J′)設(shè)置為（3，35，0.4，20）。ω0，ω1，ω2，ω3，ω4設(shè)為0.2，初始磷蝦群為路徑P11，P21和P21。很顯然，初始路徑都無(wú)法滿足給定QoS要求。

源節(jié)點(diǎn)至任播組員路徑的(E,C,D,L,J)值和f[p(s,A)]值如表1所示。

表1 各路徑的(E,C,D,L,J)值和f[p(s,A)]值

由表1可知，路徑P22的適應(yīng)度函數(shù)值最佳。以初始路徑P11，P21和P21為初始磷蝦種群，通過(guò)磷蝦群算法的交叉、變異和移動(dòng)等操作，不斷尋找更佳f[p(s,A)]值，30輪迭代優(yōu)化后，找到最優(yōu)解P22=S-n1-n2-n3-n8-n9-A2。該路徑具有最佳適應(yīng)度函數(shù)值且滿足給定QoS要求。

模擬一個(gè)具有N個(gè)（N=100）節(jié)點(diǎn)的網(wǎng)絡(luò)，均勻分布在100 m×100 m的矩形區(qū)域內(nèi)；節(jié)點(diǎn)傳輸半徑r=30 m；指定Sink（基站、任播組員），設(shè)置任播組員（Sink）數(shù)目M=6；設(shè)定任播時(shí)需向k個(gè)Sink匯報(bào)（k=2）；Eamp=100 pJ/（bit/m2），Eelec=50 nJ/bit；傳感器節(jié)點(diǎn)以參數(shù)λ=0.05的泊松分布匯報(bào)監(jiān)測(cè)事件至任意k個(gè)Sink，監(jiān)測(cè)數(shù)據(jù)分組大小為1 kbyte；QoS約束(C′,D′,L′,J′)設(shè)置為（10，20，0.3，30）。以基于傳統(tǒng)粒子群算法優(yōu)化的多約束QoS路由算法作為對(duì)照算法，來(lái)評(píng)價(jià)本文算法的優(yōu)化效率。

尋找滿足QoS約束條件的k條任播路徑，觀察適應(yīng)度函數(shù)f[p(s,A)]的收斂情況。實(shí)驗(yàn)結(jié)果如圖2所示。

圖2 適應(yīng)度函數(shù)f[p(s,A)]與迭代次數(shù)

從圖2中可知，在約第60次迭代后，適應(yīng)度函數(shù)f[p(s,A)]的平均值在連續(xù)迭代過(guò)程中幾乎沒(méi)有變化，表明算法已經(jīng)收斂到最優(yōu)路徑。從實(shí)驗(yàn)結(jié)果看，相比較粒子群算法，本文算法適應(yīng)度函數(shù)f[p(s,A)]值略微占優(yōu)。這是由于相比較傳統(tǒng)粒子群算法，磷蝦群算法中磷蝦移動(dòng)規(guī)則更加貼近實(shí)際磷蝦移動(dòng)規(guī)律，磷蝦除群集運(yùn)動(dòng)以外，還有覓食行為和隨機(jī)游動(dòng)行為，因此算法更加復(fù)雜。除此以外，磷蝦群算法還增加遺傳繁殖機(jī)制的交叉和變異操作，算法尋優(yōu)能力較強(qiáng)，不易陷入局部最優(yōu)。而且算法具有較快的收斂速度，從而在對(duì)路由選擇有時(shí)延敏感的網(wǎng)絡(luò)中具有更好的表現(xiàn)。

由于WSN往往規(guī)模很大，因此其路由算法應(yīng)該具有較好的可擴(kuò)展性。本文不斷調(diào)節(jié)網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)目N（40-100），網(wǎng)絡(luò)矩形區(qū)域也相應(yīng)調(diào)整。觀察不同網(wǎng)絡(luò)規(guī)模下適應(yīng)度函數(shù)的值，結(jié)果如圖3所示。

由圖3可知，隨著網(wǎng)絡(luò)規(guī)模增大，兩者算法的適應(yīng)度函數(shù)f(p(s,A))的值也隨之增長(zhǎng)，增長(zhǎng)曲線比較平穩(wěn)。與粒子群算法相比，本文算法在不同網(wǎng)絡(luò)規(guī)模下都有較好的優(yōu)化值。這是由于相比較傳統(tǒng)粒子群算法，磷蝦群算法在復(fù)雜問(wèn)題下仍具有較好的全局尋優(yōu)能力［1］，而傳統(tǒng)粒子群算法則較容易在陷入局部最優(yōu)，從而影響其優(yōu)化表現(xiàn)。

圖3 適應(yīng)度函數(shù)f[p(s,A)]與節(jié)點(diǎn)數(shù)

以適應(yīng)度函數(shù)f[p(s,A)]值在連續(xù)迭代中方差小于0.001為終止條件，本文繼續(xù)觀察不同網(wǎng)絡(luò)規(guī)模下所需優(yōu)化時(shí)間，結(jié)果如圖4所示。

圖4 優(yōu)化時(shí)間與節(jié)點(diǎn)數(shù)

由圖4可知，隨著網(wǎng)絡(luò)規(guī)模增大，兩者算法的優(yōu)化時(shí)間也隨之增長(zhǎng)。與傳統(tǒng)粒子群算法相比，磷蝦群算法在復(fù)雜問(wèn)題環(huán)境下，仍具有較強(qiáng)的算法尋優(yōu)能力和收斂速度［1］。因此，在不同網(wǎng)絡(luò)規(guī)模下，相比較粒子群算法，磷蝦群算法優(yōu)化時(shí)間較占優(yōu)。

5 結(jié)語(yǔ)

針對(duì)磷蝦群算法具有非線性優(yōu)化的特點(diǎn)，提出一種基于磷蝦群算法優(yōu)化的WSN多約束QoS任播路由算法。該算法采用適應(yīng)度函數(shù)來(lái)尋找WSN中滿足QoS約束的最優(yōu)任播路由，并加入遺傳繁殖機(jī)制中的交叉與變異操作以加快優(yōu)化速度。實(shí)驗(yàn)數(shù)據(jù)表明，相比較基于傳統(tǒng)粒子群算法的多約束QoS路由算法，本文算法在算法效率和可擴(kuò)展性上占優(yōu)。而且本文算法具有較快的收斂速度，從而在對(duì)路由選擇有時(shí)延敏感的網(wǎng)絡(luò)中具有較好的表現(xiàn)，但有時(shí)也有必要對(duì)其進(jìn)行改進(jìn)以避免早熟收斂。

［1］Gandomi A H，Alavi A H.Krill Herd：A New Bio-Inspired Optimization Algorithm［J］.Communications in Nonlinear Science and Numerical Simulation，2012，17（12）：4831-4845.

［2］Deng S，Huang L，Taheri J，et al.Mobility-Aware Service Composition in Mobile Communities［J］.IEEE Transactions on Systems，Man，and Cybernetics：Systems，2016，PP（99）：1-14.

［3］Rostami M A，Kavousi-Fard A，Niknam T.Expected Cost Minimization of Smart Grids With Plug-In Hybrid Electric Vehicles Using Optimal Distribution Feeder Reconfiguration［J］.IEEE Transactions on Industrial Informatics，2015，11（2）：388-397.

［4］Sultana S，Roy P K.Oppositional Krill Herd Algorithm for Optimal Location of Capacitor with Reconfiguration in Radial Distribution System［J］.International Journal of Electrical Power and Energy Systems，2016，74（2016）：78-90.

［5］Mukherjee A，Mukherjee V.Solution of Optimal Reactive Power Dispatch by chaotic Krill Herd Algorithm［J］.IET Generation，Transmission&Distribution，2015，9（15）：2351-2362.

［6］王磊，張漢鵬，張東寧.基于對(duì)立搜索和混沌變異的磷蝦覓食優(yōu)化算法［J］.控制與決策，2015，30（9）：1617-1622.

［7］Fattahi E，Bidar M，Kanan H R.Fuzzy Krill Herd（FKH）：An Improved Optimization Algorithm［J］.Intelligent Data Analysis，2016，20（1）：153-165.

［8］Bulatovic R R，Miodragovic G，Boskovic M S.Modified Krill Herd（MKH）Algorithm and Its Application in Dimensional Synthesis of a Four-Bar Linkage［J］.Mechanism and Machine Theory，2016，95（2016）：1-21.

［9］EkbataniFard G H，Monsefi R，Akbarzadeh-T M R.A Multi-Objective Genetic Algorithm Based Approach for Energy Efficient QoS-Routing in Two-Tiered Wireless Sensor Networks［C］//Proc of the 5th IEEE International Symposium on Wireless Pervasive Computing，2010：80-85.

［10］Cheng L，Niu J，Cao J，et al.QoS Aware Geographic Opportunistic Routing in Wireless Sensor Networks［J］.IEEE Transactions on Parallel and Distributed Systems，2013，25（7）：1864-1875.

［11］Sun J，F(xiàn)ang W，Wu X，et al.QoS Multicast Routing Using a Quantum-Behaved Particle Swarm Optimization Algorithm［J］.Engineering Application of Artificial Intelligence，2011，24（1）：123-131.

［12］解志斌，于謙，沈斌，等.一種新的基于粒子群優(yōu)化的雙簇頭分簇路由算法［J］.傳感技術(shù)學(xué)報(bào)，2013，26（8）：1135-1139.

［13］王鎮(zhèn)，劉學(xué)軍.WSN中基于蟻群算法的QoS路由協(xié)議［J］.傳感技術(shù)學(xué)報(bào)，2011，24（11）：1625-1631.

徐 昕（1975-），男，江蘇省南京市人，博士，南京信息工程大學(xué)計(jì)算機(jī)與軟件學(xué)院副教授，主要研究方向?yàn)闊o(wú)線傳感器網(wǎng)絡(luò)路由技術(shù)，xuxin@nuist.edu.cn；

顧云麗（1978-），女，江蘇省連云港人，博士，南京信息工程大學(xué)計(jì)算機(jī)與軟件學(xué)院講師，主要研究方向?yàn)闊o(wú)線傳感器網(wǎng)絡(luò)路由技術(shù)，guyunli@nuist.edu.cn。

A QoS Anycast Routing Algorithm for Wireless Sensor Networks Based on Krill Herd Optimization*

XU Xin1，2*，GU Yunli1，2，ZHANG Yanjuan2
（1.Jiangsu Engineering Center of Network Monitoring，Nanjing University of Information Science and Technology，Nanjing210044，China；2.College of Computer and Software，Nanjing University of Information Science and Technology，Nanjing210044，China）

Since the multiple constrained QoS anycast routing algorithm for wireless sensor networks（WSN）is a NP-complete problem，a routing algorithm based on krill herd optimization is proposed for this problem.By using the fitness function and updating the global best position in WSN，the proposed algorithm finds the optimal anycast routes which meet QoS constraints.Moreover，crossover and mutation operators in genetic reproduction mechanisms are adopted for accelerating optimization speed.Experimental results show that the algorithm is effective.In comparison with the optimization scheme based on particle swarm optimization，simulation experiments results show that the performances of efficiency and scalability of the proposed algorithm is better；the proposed algorithm has a faster convergence speed，thus it is especially applicable to the network which is delay-sensitive to route selection.

wireless sensor networks；routing algorithm；krill herd optimization；anycast

TP393

A

1004-1699（2016）12-1893-06

??6150P

10.3969/j.issn.1004-1699.2016.12.019

項(xiàng)目來(lái)源：南京信息工程大學(xué)大學(xué)生科技創(chuàng)新項(xiàng)目（201610300212）

2016-04-20修改日期：2016-07-28