肖 剛，賈國輝，周忠良

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

?

一種基于二進制差分算法的WSN多約束路由算法

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

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

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

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

0 引 言

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

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

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

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

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

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

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

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

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

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

(1)

(2)

(3)

帶寬約束：

(4)

時延約束：

(5)

能耗約束：

(6)

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

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

2 二進制差分算法原理

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

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

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

(7)

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

(8)

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

(9)

3 二進制差分算法的WSN多約束算法描述

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

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

(3) 令t=1。

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

(10)

(11)

(12)

(13)

(14)

(15)

(16)

(17)

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

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

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

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

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

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

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

圖3 BDE算法和ACO算法費用比較

圖4 BDE算法和ACO算法時延比較

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

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

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

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

表1 2種算法50次實驗的平均指標

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

5 結(jié)束語

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

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

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

[3] 胡細．移動自組織網(wǎng)絡(luò)中若干問題的建模與分析[D]．上海：上海大學，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.計算群體智能基礎(chǔ)[M].譚營譯．北京：清華大學出版社，2009．

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

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

[10]蔡慧，劉洪波.基于K均值聚類的隨機網(wǎng)絡(luò)拓撲模型[J].計算機工程與設(shè)計，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