屈 巍, 趙 晶, 洪 洋

(1. 沈陽(yáng)師范大學(xué) 科信軟件學(xué)院, 沈陽(yáng) 110034;2. 巴斯大學(xué) 科學(xué)學(xué)院, 巴斯 BA27AY)

?

一種基于蟻群優(yōu)化的動(dòng)態(tài)節(jié)能路由選擇策略

屈 巍1, 趙 晶1, 洪 洋2

(1. 沈陽(yáng)師范大學(xué) 科信軟件學(xué)院, 沈陽(yáng) 110034;2. 巴斯大學(xué) 科學(xué)學(xué)院, 巴斯 BA27AY)

針對(duì)無線傳感器網(wǎng)絡(luò)中尋找最優(yōu)路徑的問題,考慮網(wǎng)絡(luò)的節(jié)能需求,提出了一種基于蟻群優(yōu)化的動(dòng)態(tài)節(jié)能路由選擇策略。蟻群算法在進(jìn)行過一段時(shí)間后,受轉(zhuǎn)移概率公式影響易于陷入局部最優(yōu)解,因此在提出的基于蟻群優(yōu)化的動(dòng)態(tài)節(jié)能路由選擇策略中設(shè)計(jì)了動(dòng)態(tài)狀態(tài)轉(zhuǎn)移優(yōu)化規(guī)則,合理的增加了新節(jié)點(diǎn)的搜索概率,從而達(dá)到快速有效的尋找全局最優(yōu)解的目的;此外,基于蟻群優(yōu)化的動(dòng)態(tài)節(jié)能路由選擇策略設(shè)計(jì)了獎(jiǎng)罰機(jī)制,進(jìn)一步節(jié)省搜索時(shí)間的同時(shí)增加最優(yōu)路徑搜索概率,極大的延長(zhǎng)了網(wǎng)絡(luò)生存時(shí)間。仿真實(shí)驗(yàn)及分析表明,通過動(dòng)態(tài)狀態(tài)轉(zhuǎn)移優(yōu)化規(guī)則及獎(jiǎng)懲機(jī)制的動(dòng)態(tài)調(diào)整極大的增加了全局最優(yōu)解的搜索概率,快速有效地實(shí)現(xiàn)了全局最優(yōu)解的獲得,節(jié)省了節(jié)點(diǎn)能量消耗,有利于延長(zhǎng)網(wǎng)絡(luò)生存時(shí)間。

無線傳感器網(wǎng)絡(luò); 蟻群算法; 狀態(tài)轉(zhuǎn)移優(yōu)化規(guī)則; 獎(jiǎng)懲機(jī)制

0 引 言

無線傳感器網(wǎng)絡(luò)由大量具有感知能力、計(jì)算能力和通信能力的傳感器節(jié)點(diǎn)以自組織的方式構(gòu)成,被廣泛的應(yīng)用于軍事及民用領(lǐng)域[1-3]。由于一般工作在無人值守的監(jiān)控環(huán)境中,網(wǎng)絡(luò)節(jié)點(diǎn)電池更換成本較高,因此無線傳感器網(wǎng)絡(luò)的路由設(shè)計(jì)更多關(guān)注于節(jié)點(diǎn)能量消耗的最小化[4-9]。出于這些原因,節(jié)點(diǎn)在較短的時(shí)間內(nèi)找到最短的路徑進(jìn)行通信不僅利于有效降低節(jié)點(diǎn)能耗、延長(zhǎng)網(wǎng)絡(luò)生存時(shí)間,也大大提高了無線傳感器網(wǎng)絡(luò)的工作效率,這是目前傳感器網(wǎng)絡(luò)路由設(shè)計(jì)的一個(gè)重要研究方向。由Dorigo M等在1991年首次提出的蟻群算法成為解決此問題的一類典型研究方法,近年來受到廣泛研究[10-13]。蟻群算法就是模擬螞蟻群體覓食行為,后繼螞蟻通過判斷前繼螞蟻留下信息素濃度來選擇路徑。每只螞蟻根據(jù)自己周圍的局部環(huán)境做出反應(yīng)并影響于自己周圍,單只螞蟻的行為是隨機(jī)的,但整個(gè)蟻群可以通過自組織過程形成高度有序的群體行為。相同路徑上走過的螞蟻越多,積累的信息量越大,該路徑就越容易被選擇;信息量會(huì)隨著走過時(shí)間而揮發(fā),走過的時(shí)間越久,信息量越小,被選擇的概率也就越小。基本蟻群算法就是基于這種自適應(yīng)機(jī)制,使得蟻群算法不需要對(duì)所求問題的每一方面都詳細(xì)認(rèn)知,而達(dá)到從無序到有序的演化。應(yīng)用在無線傳感器網(wǎng)絡(luò)中,節(jié)點(diǎn)不需要對(duì)全局節(jié)點(diǎn)位置有全部的了解,只需要保存它附近的節(jié)點(diǎn)路由,就可以實(shí)現(xiàn)整個(gè)網(wǎng)絡(luò)的最佳路徑尋徑。這大大減少了節(jié)點(diǎn)的通信負(fù)擔(dān),也節(jié)省了節(jié)點(diǎn)的能量消耗。但基本蟻群算法在實(shí)際應(yīng)用中出現(xiàn)了收斂較快和易于陷入局部最優(yōu)解的問題,導(dǎo)致全局最優(yōu)解被忽視[14-15]。本文提出了一種基于蟻群優(yōu)化的動(dòng)態(tài)節(jié)能路由選擇策略,通過動(dòng)態(tài)狀態(tài)轉(zhuǎn)移規(guī)則的設(shè)計(jì),合理的增加了新節(jié)點(diǎn)的搜索概率,快速的實(shí)現(xiàn)了全局最優(yōu)解的獲得;通過獎(jiǎng)懲機(jī)制的合理設(shè)計(jì),進(jìn)一步節(jié)省了搜索時(shí)間的同時(shí)增加了最優(yōu)路徑搜索概率,極大的延長(zhǎng)了網(wǎng)絡(luò)生存時(shí)間。

1 基于蟻群優(yōu)化的動(dòng)態(tài)節(jié)能路由選擇策略

1.1 相關(guān)假設(shè)

傳感器網(wǎng)絡(luò)隨機(jī)部署于二維矩形平面內(nèi),使用全向天線,節(jié)點(diǎn)的通信半徑為Rc,節(jié)點(diǎn)感知半徑為Rs且Rc=2Rs,從而保證了網(wǎng)絡(luò)的連通性[16]。若節(jié)點(diǎn)i與節(jié)點(diǎn)j之間的歐式距離d(i,j)滿足d(i,j)≤Rc,則i和j互為鄰居節(jié)點(diǎn),可進(jìn)行直接通信。

1.2 狀態(tài)轉(zhuǎn)移優(yōu)化規(guī)則

1.2.1 蟻群優(yōu)化前期概率模型

(1)

(2)

其中: α為信息式因子, 反映螞蟻在運(yùn)動(dòng)過程中積累的信息素對(duì)于指導(dǎo)蟻群搜索過程中所占有的重要程度; β為期望啟發(fā)式因子, 反映在指導(dǎo)蟻群搜索過程中啟發(fā)式信息所占有的重要程度; ηik(t)為啟發(fā)函數(shù), dij表示2個(gè)鄰居節(jié)點(diǎn)之間的距離, 該啟發(fā)函數(shù)用于表示螞蟻k從節(jié)點(diǎn)i轉(zhuǎn)移到節(jié)點(diǎn)j的期望程度。

為避免殘留信息素過多淹沒啟發(fā)信息的情況出現(xiàn),當(dāng)m螞蟻完成對(duì)所有n個(gè)節(jié)點(diǎn)的遍歷后,需要對(duì)殘留信息進(jìn)行更新。t+tn時(shí)刻在路徑(i,j)上的信息量調(diào)整如公式(3)所示。

(3)

其中:ρ為信息素?fù)]發(fā)系數(shù), 1-ρ為信息素殘留因子,為防止信息無限積累,ρ的取值范圍為[0,1)。Δτij(t)為本次循環(huán)中路徑(i,j)上的信息素增量,初始時(shí)取為0即,Δτij(t)=0。Δτij,k(t)為第k只螞蟻在本次循環(huán)中t時(shí)刻殘留在路徑(i,j)上的信息量,則有

(4)

其中:Q為信息素強(qiáng)度;Lk為第k只螞蟻在本次循環(huán)中走過的所有路徑的長(zhǎng)度和。

1.2.2 蟻群優(yōu)化后期概率調(diào)整規(guī)則

蟻群算法在進(jìn)行過一段時(shí)間后,受轉(zhuǎn)移概率公式影響易于陷入局部最優(yōu)解。所以,在算法進(jìn)行一段時(shí)間后,應(yīng)該采取動(dòng)態(tài)擴(kuò)大轉(zhuǎn)移概率的方法,以便擴(kuò)大搜索空間,增加找到更優(yōu)解的幾率。

狀態(tài)轉(zhuǎn)移優(yōu)化規(guī)則首先設(shè)計(jì)平衡參數(shù)q0,以此來平衡“探索”新路徑和“利用”己有信息之間的相對(duì)重要程度。當(dāng)q>q0時(shí)進(jìn)行新路徑的探索,當(dāng)q

首先,算法開始運(yùn)行時(shí),主要以信息素作為選路參考。迭代NC次后,為了防止陷入局部最優(yōu)解,改變q0值,并設(shè)計(jì)隨機(jī)函數(shù)rad()產(chǎn)生一個(gè)隨機(jī)數(shù)滿足rand(min(pij)≤rad≤max(pij)),當(dāng)pij≥rad時(shí),節(jié)點(diǎn)i選擇下一跳節(jié)點(diǎn)j從而開辟新路徑,擴(kuò)大搜索空間,防止算法陷入局部?jī)?yōu)化。最后,主要以信息素為參考,再次改變q0值,直到運(yùn)行結(jié)束。

接下來,在α和β方面,狀態(tài)轉(zhuǎn)移優(yōu)化規(guī)則設(shè)計(jì)了動(dòng)態(tài)調(diào)整,可以有針對(duì)性的解決算法易陷入局部最優(yōu)解的問題。具體地,α反映螞蟻在運(yùn)動(dòng)過程中積累的信息素在指導(dǎo)蟻群搜索過程中的重要程度,α取值不易過大,否則容易導(dǎo)致局部正反饋?zhàn)饔幂^強(qiáng),從而導(dǎo)致算法出現(xiàn)收斂過早的現(xiàn)象。

β則反映在指導(dǎo)蟻群搜索過程中的距離的重要程度。β值越大,螞蟻在局部點(diǎn)上選擇局部最短路徑的可能性越大,算法極易快速收斂于局部最優(yōu),換言之,極易陷入局部最優(yōu)。

所以,狀態(tài)轉(zhuǎn)移優(yōu)化規(guī)則設(shè)計(jì)了根據(jù)迭代所在的階段,動(dòng)態(tài)調(diào)整α和β的機(jī)制,調(diào)整如下:

1) 依據(jù)迭代所在階段來初始化q0、α和β的值。并采用隨機(jī)函數(shù)rad()產(chǎn)生一個(gè)隨機(jī)數(shù)賦值給q,且滿足0≤q≤1,初始化模型如公式(5)所示。其中,N0為第一階段迭代次數(shù),N1為第二階段迭代次數(shù),Nc為當(dāng)前迭代次數(shù),Nc_max為最大迭代次數(shù),U、U0、U1為時(shí)變q0的值。

(5)

2) 當(dāng)q>q0時(shí),節(jié)點(diǎn)i在待選節(jié)點(diǎn)集合j[]中隨機(jī)選擇下一跳節(jié)點(diǎn),從而開辟新路徑,擴(kuò)大搜索空間;否則,依據(jù)狀態(tài)轉(zhuǎn)移概率與下一跳由信息素濃度決定。狀態(tài)轉(zhuǎn)移概率調(diào)整模型如公式(6)。

(6)

式中Ln是節(jié)點(diǎn)n的鄰居節(jié)點(diǎn)數(shù)。

1.3 獎(jiǎng)懲機(jī)制

蟻群算法在進(jìn)行信息素更新時(shí),走過的路徑上的信息素會(huì)得到一定程度的加強(qiáng),同時(shí)信息素會(huì)隨著時(shí)間的推移不斷揮發(fā),因此蟻群算法容易受到早期發(fā)現(xiàn)解的影響而陷入局部最優(yōu)?？紤]到以上問題,基于蟻群優(yōu)化的動(dòng)態(tài)節(jié)能路由選擇策略設(shè)計(jì)了獎(jiǎng)罰機(jī)制,獎(jiǎng)勵(lì)與懲罰規(guī)則如下:

1) 當(dāng)前迭代t=1時(shí),信息素濃度正常更新,即節(jié)點(diǎn)間的Δτij(t)在原來基礎(chǔ)上進(jìn)行獎(jiǎng)勵(lì),即:

(7)

2) 當(dāng)前迭代t≥2時(shí),記錄從開始到上一次為止所有迭代中最短路徑長(zhǎng)度Lall_best,依據(jù)路徑長(zhǎng)度對(duì)信息素濃度實(shí)施獎(jiǎng)懲。如果當(dāng)前螞蟻路徑長(zhǎng)度Lnow≤Lave[NC](Lave[NC]為當(dāng)前迭代所有路徑平均長(zhǎng)度),則節(jié)點(diǎn)間的Δτij(t)按照公式(7)進(jìn)行獎(jiǎng)勵(lì);如果當(dāng)前螞蟻路徑長(zhǎng)度Lnow>Lave[NC],則節(jié)點(diǎn)間的Δτij(t)在原來基礎(chǔ)上公式(8)進(jìn)行懲罰;如果當(dāng)前螞蟻路徑長(zhǎng)度Lnow≤Lall_best,則節(jié)點(diǎn)間的Δτij(t)在原來基礎(chǔ)上按照公式(9)進(jìn)行獎(jiǎng)勵(lì)。

(8)

(9)

其中:L(ant)為當(dāng)前螞蟻在一個(gè)迭代里走完的路徑總長(zhǎng);Ck為懲罰參數(shù);Cbest為獎(jiǎng)勵(lì)參數(shù)。

1.4 蟻群優(yōu)化動(dòng)態(tài)選擇策略實(shí)施步驟

Step 1 確定起始節(jié)點(diǎn)S(非信標(biāo)節(jié)點(diǎn)),通過信標(biāo)節(jié)點(diǎn)到未知節(jié)點(diǎn)的跳數(shù)矩陣找到距離未知節(jié)點(diǎn)S最近的一個(gè)信標(biāo)節(jié)點(diǎn)D,記錄它們之間的跳數(shù)為S_hop,并將禁忌表Tabu[]中第一個(gè)節(jié)點(diǎn)賦值為S,Tabu[]記錄m只螞蟻按次序走過的節(jié)點(diǎn)編號(hào)。

Step2 NC初始值設(shè)置為1,并進(jìn)行第NC次迭代。

Step 3 第m只螞蟻尋徑開始(m初始值設(shè)置為1),禁忌表目前已走過的跳數(shù)Tc初始設(shè)置為1。

Step4 螞蟻從節(jié)點(diǎn)S開始,將當(dāng)前已訪問的節(jié)點(diǎn)放入visited[]中,且初始將visited[]置為目前Tabu[]中第m行1到Tc列的節(jié)點(diǎn)的下標(biāo)。

Step 5 在S的可通信范圍內(nèi)的節(jié)點(diǎn)中,把與信標(biāo)節(jié)點(diǎn)D之間的跳數(shù)小于S_hop的節(jié)點(diǎn)索引下標(biāo)放入J_tmp[]中。

Step6 在J_tmp[]中選出與S跳數(shù)差值最大的節(jié)點(diǎn)索引,即最靠近信標(biāo)節(jié)點(diǎn)D的節(jié)點(diǎn)索引下標(biāo)放入j[]中,作為待跳節(jié)點(diǎn)的索引。

Step 7 進(jìn)行蟻群優(yōu)化的后期概論模型調(diào)整,依據(jù)公式(5)判斷此時(shí)的迭代次數(shù)是處于初步、中間還是結(jié)束階段。依據(jù)所在階段來初始化q0,α和β的值。采用隨機(jī)函數(shù)rad()產(chǎn)生一個(gè)隨機(jī)數(shù)賦值給q,且滿足0≤q≤1。

Step8 當(dāng)q>q0時(shí),節(jié)點(diǎn)的狀態(tài)轉(zhuǎn)移概率p均一樣,即在j []中隨機(jī)選擇下一跳節(jié)點(diǎn);否則,依據(jù)狀態(tài)轉(zhuǎn)移調(diào)整概率公式(6)進(jìn)行,即下一跳由信息素濃度大小決定。選好的下一跳放入to_visit中,再將to_visit放入Tabu[]第m行的第Tc++列中。

Step 9 判斷to_visit是否為信標(biāo)節(jié)點(diǎn)D。若不是,將to_visit置為S,回到步驟4;若是,將m+1置為m,回到步驟3。

Step10 所有螞蟻尋徑結(jié)束,算出每只螞蟻路徑總長(zhǎng)L(ant)。

Step 11 記錄本次迭代的最佳路徑長(zhǎng)度,放在L_best[]中。記錄本次最佳路徑,放在R_best[]中。記錄本次平均路徑長(zhǎng)度,放在L_ave[]中。

Step12 重置本次迭代中的信息素變化矩陣Δτij(t)。

Step 13 在搜索過程中,將發(fā)現(xiàn)的路徑與本次迭代平均路徑長(zhǎng)度和以往最優(yōu)解進(jìn)行比較,如果優(yōu)于以往最優(yōu)解則分別進(jìn)行不同的獎(jiǎng)勵(lì),否則進(jìn)行一定的懲罰。判斷當(dāng)NC=1時(shí),信息素濃度按照公式(7)正常更新,在原先基礎(chǔ)上進(jìn)行獎(jiǎng)勵(lì);否則,記錄從開始到上一次為止所有迭代中最短路徑長(zhǎng)度Lall_best,依據(jù)路徑長(zhǎng)度對(duì)信息素濃度實(shí)施獎(jiǎng)懲。如果當(dāng)前螞蟻路徑長(zhǎng)度Lnow≤Lave[NC](Lave[NC]為當(dāng)前迭代所有路徑平均長(zhǎng)度),則節(jié)點(diǎn)間的Δτij(t)按照公式(7)進(jìn)行獎(jiǎng)勵(lì);如果當(dāng)前螞蟻路徑長(zhǎng)度Lnow>Lave[NC],則節(jié)點(diǎn)間的Δτij(t)在原來基礎(chǔ)上按照公式(8)進(jìn)行懲罰;如果當(dāng)前螞蟻路徑長(zhǎng)度Lnow≤Lall_best,則節(jié)點(diǎn)間的Δτij(t)在原來基礎(chǔ)上按照公式(9)進(jìn)行獎(jiǎng)勵(lì)。

Step14 依據(jù)信息素更新公式更新信息素矩陣Δτij(t)。

Step 15 禁忌表Tabu[]清零。將NC+1置為NC。

Step16 判斷NC是不是大于NC_max。若不是,回到步驟2;若是,迭代結(jié)束。

2 仿真實(shí)驗(yàn)

2.1 實(shí)驗(yàn)數(shù)據(jù)

采用MATLAB為仿真平臺(tái),對(duì)所設(shè)計(jì)的蟻群優(yōu)化動(dòng)態(tài)路由選擇策略下的節(jié)點(diǎn)路徑選擇性能進(jìn)行驗(yàn)證,仿真實(shí)驗(yàn)中各參數(shù)取值如表1所示。

表1 參數(shù)設(shè)置

2.2 蟻群優(yōu)化動(dòng)態(tài)選擇策略與原算法的仿真性能對(duì)比

仿真實(shí)驗(yàn)中對(duì)于蟻群優(yōu)化動(dòng)態(tài)選擇策略與原蟻群算法采用一致的節(jié)點(diǎn)分布、相同的起始源節(jié)點(diǎn)和終點(diǎn)信標(biāo)節(jié)點(diǎn)。在相同的起始原點(diǎn)與終點(diǎn)信標(biāo)之間進(jìn)行路徑搜尋,進(jìn)行了10次獨(dú)立的隨機(jī)拓?fù)鋵?shí)驗(yàn),分別考察了“最終最佳路徑長(zhǎng)度”“NC次迭代最佳路徑平均長(zhǎng)度”和“第一次找到最佳路徑的迭代次數(shù)”的性能,并針對(duì)性能展開重點(diǎn)分析。

表2 最終最佳路徑長(zhǎng)度性能

表3 第一次找到最佳路徑的迭代次數(shù)性能

表4 NC次迭代最佳路徑平均長(zhǎng)度性能

由表2可知,每次實(shí)驗(yàn)采用蟻群優(yōu)化動(dòng)態(tài)選擇策略獲得的最終最佳路徑長(zhǎng)度都保持為49.471 3,而原蟻群算法獲得的最終最佳路徑長(zhǎng)度波動(dòng)較大,可見蟻群優(yōu)化動(dòng)態(tài)選擇策略在最終最佳路徑長(zhǎng)度方面獲得全局最優(yōu)解的性能較穩(wěn)定。

圖1 NC次迭代中最佳路徑平均長(zhǎng)度與最終最佳路徑長(zhǎng)度差別性能

由表3可知,原蟻群算法在10次隨機(jī)實(shí)驗(yàn)下找到最優(yōu)路徑的最短迭代次數(shù)為10.3,蟻群優(yōu)化動(dòng)態(tài)選擇策略則為3,可見蟻群優(yōu)化動(dòng)態(tài)選擇策略可以在更短的迭代次數(shù)內(nèi)找到最優(yōu)解,極大地縮短了搜尋路徑的時(shí)間,從而有效地降低節(jié)點(diǎn)能耗,有利于延長(zhǎng)網(wǎng)絡(luò)生存時(shí)間。

由表2及表4可知,2種算法在NC次迭代中最佳路徑平均長(zhǎng)度與最終最佳路徑長(zhǎng)度相比均有差距,從具體數(shù)值上進(jìn)行比較,原蟻群算法獲得的差距較大,約為1.616 9,采用蟻群優(yōu)化動(dòng)態(tài)選擇策略獲得的差距較微小,為0.211,性能比較具體如圖1所示,采用蟻群優(yōu)化動(dòng)態(tài)選擇策略獲得的差距微小約為原蟻群算法下獲得差距的13%。

3 結(jié) 語(yǔ)

本文以避免陷入局部最優(yōu)解、加快搜索速度為優(yōu)化目標(biāo),研究了無線傳感器網(wǎng)絡(luò)中尋找最優(yōu)路徑的問題,提出了一種基于蟻群優(yōu)化的動(dòng)態(tài)節(jié)能路由選擇策略,并對(duì)其進(jìn)行了理論分析與實(shí)驗(yàn)驗(yàn)證。仿真實(shí)驗(yàn)表明,該策略通過動(dòng)態(tài)狀態(tài)轉(zhuǎn)移規(guī)則,有效的增加了新節(jié)點(diǎn)的搜索概率,實(shí)現(xiàn)了快速有效的尋找全局最優(yōu)解的目的;通過獎(jiǎng)懲機(jī)制的設(shè)計(jì),節(jié)省時(shí)間同時(shí)進(jìn)一步增加了最優(yōu)路徑搜索概率,有效的降耗,延長(zhǎng)了網(wǎng)絡(luò)的生存時(shí)間。

[ 1 ]QU Wei, LIN Hai, WANG Jinkuan. A dynamic energy-efficient routing scheme in Wireless Sensor Networks[J]. ICIC-EL ,2014,8(11):3113-3119.

[ 2 ]KARIMI M, NAJI H R. Optimize cluster-head selection in wireless sensor networks using genetic algorithm and harmony search algorithm[C]∥20th Iranian Conference on Electrical Engineering, 2012:706-710.

[ 3 ]張國(guó)印,唐濱,孫建國(guó),等. 面向內(nèi)容中心網(wǎng)絡(luò)基于分布均勻度的蟻群路由策略[J]. 通信學(xué)報(bào), 2015,36(6):1-12.

[ 4 ]曲大鵬,王興偉,黃敏. 移動(dòng)對(duì)等網(wǎng)絡(luò)中的感知蟻群路由算法[J]. 計(jì)算機(jī)學(xué)報(bào), 2013,36(7):1456-1464.

[ 5 ]AL-ALI R, RANA O, WALKER D W, et al. G-QoSM: grid service discovery using QoS properties[J]. China J Comput, Comput Inf, 2012,21(4):363-382.

[ 6 ]陳志泊,徐孝成. 一種改進(jìn)的基于跳數(shù)的無線傳感器網(wǎng)絡(luò)路由算法[J]. 計(jì)算機(jī)科學(xué), 2013,40(4):83-85.

[ 7 ]AMALDI E, CAPONE M, FILIPPINI I. Design of wireless sensor networks for mobile target detection[J]. IEEE/ACM Transactions on, 2012,20(3):784-797.

[ 8 ]KARABOGA D, OKDEM S, OZTURK C. Cluster based wireless sensor network routing using artificial bee colony algorithm[J]. Wireless Networks, 2012,18(7):847-860.

[ 9 ]OKDEM S, OZTURK C, KARABOGA D. A comparative study on differential evolution based routing implementations for wireless sensor networks[C]∥Innovations in Intelligent Systems and Applications(INISTA), 2012 International Symposium on, 2012:1-5.

[10]COLORNI A, DORIGO M, MANIEZZO V, et al. Distributed optimization by ant colonies[C]∥Proceedings of European Conference on Artificial Life,1991:134-142.

[11]梁華為,陳萬(wàn)明,李帥,等. 一種無線傳感器網(wǎng)絡(luò)蟻群優(yōu)化路由算法[J]. 傳感技術(shù)學(xué)報(bào), 2007,20(11):2450-2455.

[12]李領(lǐng)治,鄭洪源,丁秋林. 一種基于改進(jìn)蟻群算法的選播路由算法[J]. 電子與信息學(xué)報(bào), 2007,29(2): 340-344.

[13]朱思峰,劉方.柴爭(zhēng)義. 一種基于蟻群優(yōu)化的無線傳感器網(wǎng)絡(luò)路由算法[J]. 北京理工大學(xué)學(xué)報(bào), 2010,30(11):1295-1300.

[14]楊新峰,劉克成. 基于改進(jìn)蟻群算法的WSN路徑優(yōu)化[J]. 計(jì)算機(jī)與現(xiàn)代化, 2012,6(6):102-105.

[15]吳慶洪,張穎,馬宗民. 蟻群算法綜述[J]. 微計(jì)算機(jī)信息, 2011,27(3):1-5.

[16]屈巍,李喆. 無線傳感器網(wǎng)絡(luò)中一種分布式冗余檢測(cè)算法[J]. 小型微型計(jì)算機(jī)系統(tǒng), 2010,31(4):577-582.

A dynamic energy-saving routing strategy based on ant colony optimization in wireless sensor networks

QUWei1,ZHAOJing1,HONGYang2

(1. Software College, Shenyang Normal University, Shenyang 110034, China; 2. Department of Science, University of Bath, Bath BA27AY，The United Kingdom of Great Britain and Northern Ireland)

Focus on the problem of finding the optimal path in wireless sensor networks(WSN), and energy saving requirement, a dynamic energy-saving routing strategy based on ant colony optimization(ACO) was proposed . Because of being influenced by the transition probability formula，the algorithm of ACO is easy to fall into local optimal solution after running for a period of time. Thus, in this paper, our strategy designs the optimization rule of dynamic state transformation, which increases the search probability of the new node, so as to achieve the purpose of searching the global optimal solution quickly and effectively.In addition, our strategy introduces the mechanism of rewards and penalties, which further saves the search time and increase the probability of optimal path search, and prolongs the network survival time greatly. Simulation and theoretical analysis showed that the searching probability of a global for the optimal solution is increased by dynamic adjustment of the dynamic state transition rule and the mechanism of rewards and punishments, and the global optimal solution is obtained quickly and effectively. Furthermore the energy consumption of the nodes is saved, and will extend the lifetime of network greatly.

Wireless sensor networks(WSN); ant colony optimization(ACO); optimization rule of dynamic state transformation; the mechanism of rewards and penalties

2015-11-23。

國(guó)家自然科學(xué)基金資助項(xiàng)目(61403073)。

屈 巍(1982-),女,遼寧鐵嶺人,沈陽(yáng)師范大學(xué)講師,博士。

1673-5862(2016)02-0234-06

TP393

A

10.3969/ j.issn.1673-5862.2016.02.022