一種基于二進(jìn)制差分算法的WSN多約束路由算法

肖 剛，賈國輝，周忠良

(1.中國電子科技集團(tuán)公司第20研究所，西安 710068；2.國防信息學(xué)院，武漢 430010；3. 中航工業(yè)成都凱天電子股份有限公司，成都 610031)

?

一種基于二進(jìn)制差分算法的WSN多約束路由算法

肖 剛1，賈國輝2，周忠良3

(1.中國電子科技集團(tuán)公司第20研究所，西安 710068；2.國防信息學(xué)院，武漢 430010；3. 中航工業(yè)成都凱天電子股份有限公司，成都 610031)

針對(duì)無線傳感器網(wǎng)絡(luò)(WSN)中多約束路由算法問題，側(cè)重考慮WSN在軍事應(yīng)用中的主要約束因素，利用二進(jìn)制差分(BDE)算法良好的魯棒性和記憶性，提出了一種基于BDE算法的路由算法。仿真實(shí)驗(yàn)表明該算法提升了尋找最優(yōu)路由的時(shí)間，減少了網(wǎng)絡(luò)的能耗，是一種有效的尋優(yōu)方式。

無線傳感器網(wǎng)絡(luò)；二進(jìn)制差分算法；多約束

0 引 言

在現(xiàn)代戰(zhàn)場(chǎng)環(huán)境下，數(shù)據(jù)信息的實(shí)時(shí)采集傳輸逐漸成為影響戰(zhàn)局的重要因素，而無線傳感器網(wǎng)絡(luò)憑借其成本低、規(guī)模大、自組織性和隱蔽性好等多方面特性正越來越多地應(yīng)用到軍事領(lǐng)域中，比如軍情偵察、戰(zhàn)場(chǎng)實(shí)時(shí)監(jiān)控、目標(biāo)定位追蹤、核化攻擊等多方面應(yīng)用，尤其是在數(shù)據(jù)鏈的終端數(shù)據(jù)采集方面，無線傳感器網(wǎng)絡(luò)(WSN)可以通過其組網(wǎng)方式和可靠性來應(yīng)對(duì)戰(zhàn)爭(zhēng)中某些傳感器節(jié)點(diǎn)被摧毀的情況，使網(wǎng)絡(luò)可以繼續(xù)工作，所以如何讓W(xué)SN擁有更好的可靠性和更長的使用壽命是WSN網(wǎng)絡(luò)在戰(zhàn)場(chǎng)應(yīng)用中的一個(gè)重要研究方向。

路由算法是無線傳感器網(wǎng)絡(luò)中的一個(gè)主要的研究內(nèi)容，WSN通過路由算法來尋找到達(dá)目的節(jié)點(diǎn)的最佳路徑。在無線傳感器網(wǎng)絡(luò)的實(shí)際應(yīng)用中，最佳路徑的選擇會(huì)受到多方面因素的制約，只有綜合考慮各種因素的路由算法才能在現(xiàn)實(shí)應(yīng)用中取得預(yù)想的效果。針對(duì)戰(zhàn)場(chǎng)環(huán)境和數(shù)據(jù)鏈的應(yīng)用要求，能耗問題、帶寬問題和丟包率問題是本文關(guān)注的主要約束條件[1]。

二進(jìn)制差分算法具有不錯(cuò)的收斂特性和魯棒性，并且具有記憶能力，本文將其應(yīng)用在多約束路由問題中，實(shí)驗(yàn)結(jié)果表明，二進(jìn)制差分路由算法的尋優(yōu)能力強(qiáng)于目前常用的蟻群算法[2]。

1 WSN網(wǎng)絡(luò)多約束路由模型

能量的最大效能使用是無線傳感器網(wǎng)絡(luò)極其重要的設(shè)計(jì)標(biāo)準(zhǔn)，而隨著WSN應(yīng)用范圍的擴(kuò)大，應(yīng)用場(chǎng)景的多樣化，在例如高質(zhì)量的戰(zhàn)場(chǎng)場(chǎng)景中，丟包率和時(shí)延等服務(wù)質(zhì)量參數(shù)也變成重要的衡量設(shè)計(jì)的標(biāo)準(zhǔn)，這就要求現(xiàn)實(shí)應(yīng)用中無線傳感器網(wǎng)絡(luò)的路由算法滿足多種約束條件，使算法更靈活，更具有實(shí)際應(yīng)用價(jià)值。但低丟包率和低時(shí)延有可能會(huì)導(dǎo)致能耗增加，進(jìn)而降低網(wǎng)絡(luò)的使用壽命，所以對(duì)于面向?qū)嶋H應(yīng)用的無線傳感器網(wǎng)絡(luò)，如何通過平衡優(yōu)化路由算法來達(dá)到多約束條件下的能耗最少變得極為重要。

為了更好地研究該問題，需要建立一個(gè)可量化、易衡量的路由模型。在無線傳感器網(wǎng)絡(luò)中，節(jié)點(diǎn)間的能量差異性，通信能力的不同，信息傳播環(huán)境的差別，這些因素都會(huì)影響最優(yōu)路由的選擇，這些差異性就導(dǎo)致在建立路由模型的過程中要考慮到這些約束條件。多約束路由問題就是在多個(gè)約束條件的制約下，找到最優(yōu)路徑的問題，進(jìn)而可以讓該問題抽象成求最小Steiner樹問題。Steiner樹是一棵連接所有節(jié)點(diǎn)的總代價(jià)最小的分布樹，其連接特定圖中的特定組成員所需的鏈路數(shù)最少，其中Steiner樹的求解是一種P=NP的NPC問題，又由于在實(shí)際的WSN中存在多種約束條件，故復(fù)雜度高的算法不利于解決WSN中的多約束路由算法，而采用啟發(fā)式算法求解Steiner樹[3]。

在WSN中，主要考慮2個(gè)方向的約束條件，即業(yè)務(wù)指標(biāo)和網(wǎng)絡(luò)能耗。業(yè)務(wù)指標(biāo)主要包括丟包率、時(shí)延、帶寬以及時(shí)延抖動(dòng)等指標(biāo)，這些指標(biāo)主要用來衡量服務(wù)質(zhì)量的水平。網(wǎng)絡(luò)能耗則包括了節(jié)點(diǎn)間傳遞帶來的能量消耗以及節(jié)點(diǎn)自身維持工作所需要的能量[4]。

能耗:主要包括兩方面：一是指節(jié)點(diǎn)單位時(shí)間內(nèi)自身工作消耗的能量，二是指節(jié)點(diǎn)間傳輸單位大小的數(shù)據(jù)所消耗的能量。實(shí)際應(yīng)用中，WSN中往往采用體積小巧的電池作為供電源，但其儲(chǔ)電量有限，也就制約了網(wǎng)絡(luò)的工作時(shí)間。若網(wǎng)絡(luò)中作為樞紐的節(jié)點(diǎn)能量耗盡，容易對(duì)整體網(wǎng)絡(luò)的持續(xù)生存造成威脅，所以平衡網(wǎng)絡(luò)所有節(jié)點(diǎn)的使用情況十分重要。

帶寬: 指節(jié)點(diǎn)間在單位時(shí)間內(nèi)能通過鏈路的數(shù)據(jù)量。在WSN網(wǎng)絡(luò)中，帶寬參數(shù)主要由終端節(jié)點(diǎn)的自身特性決定，具體有業(yè)務(wù)帶寬和路徑帶寬，前者取決于WSN網(wǎng)絡(luò)的工作內(nèi)容，后者則由參與傳輸?shù)墓?jié)點(diǎn)的自身帶寬決定[5]。

時(shí)延: 一個(gè)節(jié)點(diǎn)從開始發(fā)送數(shù)據(jù)包到數(shù)據(jù)包發(fā)送完畢所需要的全部時(shí)間，在WSN中，時(shí)延主要受數(shù)據(jù)傳輸中的環(huán)境干擾、傳輸競(jìng)爭(zhēng)、網(wǎng)絡(luò)堵塞、數(shù)據(jù)處理等多方面因素的影響。

(1)

(2)

(3)

帶寬約束：

(4)

時(shí)延約束：

(5)

能耗約束：

(6)

式中：BW、DL、EL分別為網(wǎng)絡(luò)帶寬、時(shí)延和能耗的約束限制。

以上3種約束是本文主要討論的約束條件，本文在該3種約束條件限制下對(duì)路由算法進(jìn)行討論研究。

2 二進(jìn)制差分算法原理

二進(jìn)制差分算法(BDE)是一種源自生物圈中“優(yōu)勝劣汰”思想的啟發(fā)式智能算法。因?yàn)槠渚哂休^強(qiáng)的全局搜索能力和健碩的魯棒性，而且算法的運(yùn)算簡單，所以近些年BDE被越來越多的研究人員所關(guān)注和研究，并應(yīng)用到眾多領(lǐng)域中去。區(qū)別于差分進(jìn)化算法主要針對(duì)連續(xù)空間函數(shù)尋找最優(yōu)解，二進(jìn)制差分算法主要是針對(duì)離散空間的最優(yōu)解問題[6]，使差分進(jìn)化的思想應(yīng)用到更廣的范圍中去。

BDE算法根據(jù)問題解個(gè)體間的差別重新組合成一個(gè)新的解空間，通過新解空間和初代解空間的比較，擇優(yōu)選出更優(yōu)秀的個(gè)體，組成下一代的解空間，迭代運(yùn)算，直到解空間趨近于最優(yōu)解[7]。

BDE算法區(qū)別于基本差分算法，其解空間通過二進(jìn)制編碼，若只通過簡單變異行為得到新個(gè)體有一定概率不滿足解空間的約束條件，為了能滿足取值范圍，需先將解向量映射到[0,1]之間[8]，即：

(7)

而對(duì)于經(jīng)過變異后，但不在范圍內(nèi)的解按照sigmoid函數(shù)映射到[0,1]之間，如公式(8)所示：

(8)

再將解空間按照公式(9)的分段函數(shù)，組成由0和1組成的解空間，最后執(zhí)行交叉操作[9]：

(9)

3 二進(jìn)制差分算法的WSN多約束算法描述

(1) 設(shè)置參數(shù)?？s放因子P，交叉概率常數(shù)CR，衰減因子α，迭代次數(shù)上限tmax，解個(gè)數(shù)k。

(2) 剔除不滿足約束限制的鏈路，簡化網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)。

(3) 令t=1。

(4) 適應(yīng)度評(píng)價(jià)。適應(yīng)度定義為：

(10)

(11)

(12)

(13)

(14)

(15)

(16)

(17)

式中：A，C，F(xiàn)分別為fel，fbw，fdl的權(quán)重系數(shù)，表示節(jié)點(diǎn)能耗、帶寬和時(shí)延在適應(yīng)度中的比重，由于本網(wǎng)絡(luò)比較關(guān)注能耗問題，所以權(quán)重系數(shù)設(shè)置如下：A=1，C=0.6，F(xiàn)=0.6。

(5) 變異、交叉操作。依據(jù)式(10)計(jì)算出全部個(gè)體的適應(yīng)度，隨機(jī)選取2條不同的等節(jié)點(diǎn)數(shù)的路徑，將2條路徑中除了源點(diǎn)和終點(diǎn)以外的點(diǎn)做差，乘縮放因子P加到路徑Q的各節(jié)點(diǎn)上，作為新的路徑。其中，路徑Q為隨機(jī)選出的第3個(gè)路徑或種群最優(yōu)路徑。

(6) 差分選擇。將(5)操作后的新路徑，與Q進(jìn)行比較，選擇競(jìng)爭(zhēng)勝利的路徑進(jìn)入下一代。

(7) 結(jié)束判定。若t

4 仿真實(shí)驗(yàn)及結(jié)果

分析用二進(jìn)制差分算法和蟻群算法的求解最優(yōu)解的性能，如圖2、圖3、圖4所示，分別從費(fèi)用、時(shí)延、能耗三方面對(duì)2種算法進(jìn)行比較。

圖2 BDE算法和ACO算法能耗比較

圖3 BDE算法和ACO算法費(fèi)用比較

圖4 BDE算法和ACO算法時(shí)延比較

根據(jù)仿真結(jié)果分析，在算法運(yùn)行的前18次，BDE算法可以迅速縮小最優(yōu)解的搜索范圍，而ACO算法在前期相對(duì)速度有些緩慢，原因是ACO算法尋找新解的效率不高，不能提高種群的多樣性，相反BDE算法通過交叉變異生成新解，通過競(jìng)爭(zhēng)產(chǎn)生下一代種群，可使種群的適應(yīng)度水平明顯提高。

當(dāng)運(yùn)行到18～63次的時(shí)候，BDE算法進(jìn)入穩(wěn)定搜索階段，此時(shí)解的質(zhì)量相對(duì)較高，所以迭代運(yùn)算對(duì)于解質(zhì)量的提升速度減緩，ACO算法也相比早期階段進(jìn)入相對(duì)緩慢的階段，2種算法都在這個(gè)階段取得接近最優(yōu)解的路徑。

最后運(yùn)行至100次期間，BDE算法的迭代效果不明顯，取得了最優(yōu)解。而ACO算法幾乎停滯了迭代，但只得到了局部最優(yōu)解，優(yōu)化效果不理想。

對(duì)2種算法分別進(jìn)行50次算法運(yùn)算，將50次運(yùn)算結(jié)果取平均值進(jìn)行比較，如表1所示。

表1 2種算法50次實(shí)驗(yàn)的平均指標(biāo)

由表1可知，BDE算法整體求解能力和尋優(yōu)效率優(yōu)于ACO算法，尤其是在費(fèi)用和能耗方面優(yōu)勢(shì)明顯。ACO算法和BDE算法的平均迭代次數(shù)相差不大，但ACO算法得到的結(jié)果往往只是局部最優(yōu)解，而BDE算法全局搜索能力更好，生成新解能力強(qiáng)，可以擴(kuò)大路徑的選擇范圍，因而BDE算法比ACO算法具有更好的求解能力。仿真結(jié)果表明，該網(wǎng)絡(luò)最佳路徑為(1→8→14→23→33→36→45)，對(duì)應(yīng)的費(fèi)用為61.75。

5 結(jié)束語

本文在分析WSN路由評(píng)價(jià)模型的基礎(chǔ)上，提出一種基于二進(jìn)制差分算法的多約束路由算法。仿真結(jié)果表明，該算法比傳統(tǒng)算法有更好的尋找最優(yōu)解的能力，其在多方面有較突出的性能指標(biāo)。

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

[2] 肖偉，全惠云．基于蟻群算法的多路徑多約束QoS路由的研究[J]．計(jì)算機(jī)工程與應(yīng)用，2008，30(7)：89-94．

[3] 胡細(xì)．移動(dòng)自組織網(wǎng)絡(luò)中若干問題的建模與分析[D]．上海：上海大學(xué)，2007．

[4]HusseinFarouekSalama．MulticastRoutingforReal-timeCommunicationofHigh-speedNetworks[D].Raleigh:NorthCarolinaStateUniversity,2006.

[5]WilliamStallings．無線通信與網(wǎng)絡(luò)[M].北京：電子工業(yè)出版社，2006.

[6] 畢曉君．信息智能處理技術(shù)[M]．北京：電子工業(yè)出版社，2010.

[7]EngelbrechtAndriesP.計(jì)算群體智能基礎(chǔ)[M].譚營譯．北京：清華大學(xué)出版社，2009．

[8]DengCS,ZhaoBY,YangYL,etal.Novelbinarydifferentialevolutionalgorithmfordiscreteoptimization[A].ProceedingofFifthInternationalConferenceonNaturalComputation[C],2009:346-349.

[9] 畢曉君,王義新.多模態(tài)函數(shù)優(yōu)化的擁擠差分進(jìn)化算法[J].哈爾濱工程大學(xué)學(xué)報(bào),2011,32(2):223-227.

[10]蔡慧，劉洪波.基于K均值聚類的隨機(jī)網(wǎng)絡(luò)拓?fù)淠Ｐ蚚J].計(jì)算機(jī)工程與設(shè)計(jì)，2009，30(5)：1089-1901．

A WSN Multi-constraint Routing Algorithm Based on Binary Difference Evolution Algorithm

XIAO Gang1，JIA Guo-hui2，ZHOU Zhong-liang3

(1.The 20th Research Institute of CETC,Xi’an 710068，China;2.College of National Defense Information Science,Wuhan 430010，China;3.Chengdu CAIC Electronics Co.Ltd,Chengdu 610031，China)

Aiming at the problem of multi-constraint routing algorithm in wireless sensor network (WSN),this paper considers the main constraint factors of WSN applied to military,uses the perfect robustness and memory of binary difference evolution (BDE) algorithm to present a routing algorithm based on BDE algorithm.The simulation experiments show that this algorithm can improve the time of searching for optimal routing and reduces the energy consumption of network,so the routing algorithm in this paper is an effective optimization method.

wireless sensor network;binary difference evolution algorithm;multiple constraint

2014-12-10

TN915

A

CN32-1413(2015)02-0056-04

10.16426/j.cnki.jcdzdk.2015.02.015