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

肖 剛，賈國輝，周忠良

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

?

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

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

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

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

無線傳感器網絡；二進制差分算法；多約束

0 引 言

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

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

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

1 WSN網絡多約束路由模型

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

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

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

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

帶寬: 指節點間在單位時間內能通過鏈路的數據量。在WSN網絡中，帶寬參數主要由終端節點的自身特性決定，具體有業務帶寬和路徑帶寬，前者取決于WSN網絡的工作內容，后者則由參與傳輸的節點的自身帶寬決定[5]。

時延: 一個節點從開始發送數據包到數據包發送完畢所需要的全部時間，在WSN中，時延主要受數據傳輸中的環境干擾、傳輸競爭、網絡堵塞、數據處理等多方面因素的影響。

(1)

(2)

(3)

帶寬約束：

(4)

時延約束：

(5)

能耗約束：

(6)

式中：BW、DL、EL分別為網絡帶寬、時延和能耗的約束限制。

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

2 二進制差分算法原理

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

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

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

(7)

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

(8)

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

(9)

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

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

(2) 剔除不滿足約束限制的鏈路，簡化網絡拓撲結構。

(3) 令t=1。

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

(10)

(11)

(12)

(13)

(14)

(15)

(16)

(17)

式中：A，C，F分別為fel，fbw，fdl的權重系數，表示節點能耗、帶寬和時延在適應度中的比重，由于本網絡比較關注能耗問題，所以權重系數設置如下：A=1，C=0.6，F=0.6。

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

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

(7) 結束判定。若t

4 仿真實驗及結果

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

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

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

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

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

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

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

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

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

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

5 結束語

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

[1] 于海斌，曾鵬，梁韋.智能無線傳感器網絡系統[M].北京：科學出版社，2006.

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

[3] 胡細．移動自組織網絡中若干問題的建模與分析[D]．上海：上海大學，2007．

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

[5]WilliamStallings．無線通信與網絡[M].北京：電子工業出版社，2006.

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

[7]EngelbrechtAndriesP.計算群體智能基礎[M].譚營譯．北京：清華大學出版社，2009．

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

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

[10]蔡慧，劉洪波.基于K均值聚類的隨機網絡拓撲模型[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