一種基于DPSO的無線傳感器網絡QoS路由算法*

何 筱，石為人，王小剛，鄧仲芬

(重慶大學自動化學院，重慶400030)

0 引言

隨著無線傳感器網絡的不斷快速發展，不同業務對其網絡服務質量(QoS)提出了更高的要求［1］，應用時往往會對延時，帶寬，丟失率，代價等多個性能參數同時提出要求。

有序分配路由SAR［2］是第一個面向WSNs提供QoS保證的路由算法。能量感知QoS路由EQR［3］，通過評估鏈路代價、擴展Dijkstra算法為節點找到符合QoS需求的最小代價路徑。文獻［4］提出一種滿足QoS帶寬需求的能量最優的無線傳感器網絡路由方案，文獻［5］提出一種保證服務質量的最小能量路由算法。目前提出的QoS路由算法大多僅考察個別性能指標，不能全面反映傳感器網絡的QoS需求，且需維護路由參數和網絡狀態信息的開銷較大，能量消耗快。所以，相對傳統QoS路由算法，設計滿足多QoS參數約束的智能算法具有重要意義。

粒子群優化(PSO)算法［6］是一種源于對鳥群捕食行為研究的新型進化計算方法。它通過群體中個體之間的協作和信息共享來尋找最優解，具有結構簡單、參數調整少、收斂速度快及易于實現等特點。本文提出的基于離散粒子群優化無線傳感器網絡QoS路由(DPSO-QR)算法，將不同的QoS參數定義為不同優化目標，對節點間通信的多個參數目標進行優化，從而為具有不同QoS需求的業務提供滿足其特有需求的優化路由，同時，降低網絡能耗、延長網絡壽命、提高網絡服務質量。

1 QoS路由問題的網絡模型

本文假設WSNs中節點位置固定，通信半徑為R，且具有唯一ID號，形成無向連通圖G=(V，E)，V 為網絡節點集合，E 為網絡鏈路集合，相鄰兩節點 vi，vj∈V，eij為節點 vi與vj之間的邊，每條邊包含4種QoS參數度量:帶寬B，時延D，丟包率L，傳播損耗C。求解滿足4個需求約束條件的問題屬于多目標優化問題，假設有一條從節點a到節點b的路徑Pab，對Pab路徑上的目標函數定義如下:

定義1:帶寬Bab取路徑所有組成邊中帶寬的最小值;時延Dab為鏈路時延之和;鏈路丟包率Lab見式(1);傳播損耗Cab的模型見式(2)

其中，ε為路徑損耗系數，取值為50 nJ/bit，k為發送數據包長度，kbit。

由于各參數度量數量級和量綱不同，采用參數適應度對各參數進行規范化處理，公式中帶下標up，low的參數分別代表參數需求上限和下限。

定義2:參數適應度定義如下，其中，丟包率適應度B'ab與時延適應度D'ab類似

式中 max Cab為路徑Pab中節點一跳通信范圍R內最大的能量傳播損耗，h為路徑Pab的跳數。

通過對路徑上目標函數及其適應度的定義，將任意一條路徑Pab∈E定義為相應的矢量集合，即目標空間fab=(B'ab，D'ab，L'ab，C'ab)，從而將無線傳感器網絡 QoS 路由優化問題抽象為多目標優化問題。本文采用算法簡單、尋優速度快的PSO算法求解多目標問題，以適應WSNs中節點計算能力較弱的特點和對算法速度的要求，并加入擾動操作解決PSO算法尋優過程中易陷入局部最優的問題。

2 基于離散粒子群的多目標優化策略(MDPSO)

2.1 改進的離散粒子群算法

基本PSO在傳統的連續域函數優化領域中，用速度和位置更新2個迭代公式來搜索求解。而多QoS參數約束單播路由問題是一個非線性組合優化問題，屬于離散問題［7］，因此，本文結合路由算法特點，對PSO算法進行改進，設計了一種基于離散空間的DPSO策略，改進公式如下

其中，X表示粒子，“⊕算子”是加法運算的擴展，Pi(n)為第n次迭代后粒子i的歷史Pareto最優解集Pi中的一個隨機解，G(n)為第n次迭代后全局Pareto最優解集G中的一個隨機解，λ1，λ2為加速因子，值域為［0，1］。

2.2 離散粒子群算法初始化

任意粒子Xi對應一條從源節點s到目標節點t的隨機路徑(ID序列)。設源節點粒子Xi群規模為m，迭代次數設為N，任意粒子Xi生成一個空的歷史Pareto最優解集Pi，全局生成一個空的全局Pareto最優解集G，G未被更新的迭代次數的閾值設為F。

2.3 加算子

⊕算子用以實現當前解對Pareto最優解的學習。設Pa為當前路徑，Pb是相對Pa較好的一條路徑，Pa路徑的源節點為s，終節點為t。以Pa⊕λPb為例，運算過程如下:

1)根據λ的大小在Pb上隨機選取一個路由子片段，長度由λ控制，記為Pb_sub，其源節點為s'，終節點為t'，現將Pb_sub插入Pa路徑中;

2)進行插入銜接

左向銜接:若路徑Pa中有與Pb_sub源節點s'相同的節點，則將Pa中s～s'的一段截取下來，記為Pa_sub0;若沒有與s'相同的節點，則求出一條s'～Pa的一條路徑，將此路徑的反向路徑記為Pnew0，將Pa中s到Pnew0的源節點s″的路徑截取下來，記為Pa_sub0;

右向銜接:若路徑Pa中有與Pb_sub終節點t'相同的節點，則將Pa中t'～t的一段截取下來，記為Pa_sub1;若沒有與t'相同的節點，求出一條t'～Pa的一條路徑，將路徑記為Pnew1，同樣將Pa中Pnew1的終節點t″到t的一段路徑截取下來，記為Pa_sub1;

3)將 Pa_sub0，Pnew0，Pb_sub，Pnew1，Pa_sub1連接，刪除路徑中重復的節點，就得到新路徑P'a。

2.4 擾動算子

基本PSO計算過程中容易出現群體陷入局部最優的現象。為保持粒子多樣性，提高搜索性能，將采用擾動操作對粒子進行變異。

設任意解的目標向量 U=(U1，U2，U3，U4)，其中，U1，U2，U3，U4分別對應 B，D，L，C 4 種 QoS 參數。當有解 X'要加入全局Pareto最優解集G時，先計算X'與G中解XG∈G之間目標向量的距離。當有‖Uk(X')－Uk(XG)‖＜δk時，δk為根據需求設定的閾值，認為可能陷入局部極小，對該粒子進行一次擾動操作。擾動操作為:放棄粒子當前路徑，重新獲取一條從源節點s到終節點t的隨機路徑。

2.5 MDPSO 流程

1)當節點有數據發送需求時，進行算法初始化;

2)利用式(6)、⊕運算，進行迭代計算;

3)每次迭代后，判斷各粒子當前解Xi與其歷史Pareto最優解集Pi中解XP的支配關系，當有XP＜Xi時，刪除XP;當﹁?XP＞Xi時，將Xi加入Pi中;

4)判斷所有當前解 Xi，i∈(1，2…，I)之間的支配關系，保留其中的非支配解X'i，再判斷X'i與G中解XG的支配關系，當有 XG＜X'i時，刪除XG;當﹁?XG＞X'i時，計算 X'i與XG的歐幾里德距離，判斷是否需要擾動，然后將X'i加入G中;

5)當迭代次數達到n或者G未被更新的迭代次數達到F，則輸出G;否則，返回步驟(2);

6)根據數據傳輸的QoS需求，按式(7)計算G中路徑適應度fitness，其中，w為數據傳輸時設定的QoS需求權重。計算完成后取fitness最小的路徑轉發數據

7)在計算出G后的時間ts內(2 min)，如有新數據發送，返回步驟(6)選擇路徑;超過ts后，如有新數據發送，返回步驟(1)重新初始化。

3 DPSO-QR整體流程

MDPSO完成了節點需轉發數據時路由的選取，但WSN中節點的計算、儲存能力都非常有限，若每個節點都使用MDPSO進行全局集中式路由計算，則參數更新將浪費大量的能量，極大限制DPSO-QR算法的擴展性。因此，DPSOQR在MDPSO基礎上，設計了局部區域網絡參數的獲取機制，形成局部集中的計算模式，以實現算法性能與能耗及擴展性之間的折中。

1)Sink節點進行全局網絡初始化廣播，每隔t's時間都將進行一次全網更新廣播;

2)網絡節點收到廣播后，在自己的通信范圍內進行初始化廣播，記錄H跳范圍內(本文H=3)所有路徑的適應值矢量集合f，建立局部區域的QoS參數表;

3)節點以自己所在局部區域中剩余能量最大的節點作為自身的局部目標節點，如果Sink在節點的H跳范圍內，則以Sink為目標節點;

4)當有數據發送需求時，節點用MDPSO計算出Pareto最優解集G。按待發送的數據對QoS的需求，結合式(7)，選出局部區域最佳路由進行轉發。在得到集合G后的時間ts內，將不再重新計算G。ts時間后有數據發送需求時，重新計算G，以適應網絡參數的變化;

5)每間隔時間ts，節點將自身和2跳范圍內的節點以及路徑QoS參數發生變化的部分參數打包，并發送給自己的鄰居節點，實現局部區域的QoS參數更新;

6)局部目標節點收到數據后，轉到步驟(3)，繼續搜索以其為源節點的局部區域最優路由，直至數據傳輸至Sink。

4 仿真實驗

在100 m×100 m的平面區域中隨機布撒100個無線傳感器節點，Sink節點位于右上角，節點初始能量為1J，最大無線通信半徑為20 m;仿真過程中，節點以一定周期產生長度為128 bytes的數據包向Sink節點發送。設網絡QoS路由參數度量需求的取值范圍為B∈(0，10)，D∈(0，10)，L∈(0，0.1)，且 Bup=6，Blow=3，Dup=20，Dlow=10，Lup=0.1，Llow=0.05。實驗中設置w=(0.15，0.3，0.15，0.4)。通過改變數據包發送速率，從1～10 pkt/s來模擬不同的網絡負載。仿真分別對DPSO-QR，SAR和EQR算法進行了10次仿真，網絡性能對比圖如圖1～圖4所示。

圖1 算法帶寬均值對比圖Fig 1 Comparison diagram of average bandwidth

從圖1可以看出:3種算法的路由帶寬均值較為接近。由于EQR有固定的帶寬閾值，其帶寬略優于DPSO-QR和SAR。而DPSO-QR在一定周期內可對環境狀態參數進行實時更新，其帶寬性能優于SAR。

圖2 算法時延均值對比圖Fig 2 Comparison diagram of average delay of the algorithm

圖2中隨著網絡數據包發送速率的增加，時延明顯增加。這是因為網絡中數據流量較大時，沖突碰撞和重傳次數增加。由圖可知，SAR與EQR算法的平均端到端時延性能接近，DPSO-QR算法的平均端到端時延比SAR和EQR約減少了26.3%，且隨著負載的增加上升較為緩慢。

圖3中當數據包發送速率較低時，3種算法的路由丟包率都較為接近。隨著發送速率增大，DPSO-QR算法的丟包率明顯小于SAR和EQR，比SAR約減少了34.4%，比EQR約減少了51.8%。說明DPSO-QR算法在一定程度上降低了丟包率。

圖4為不同網絡負載下的網絡壽命變化情況。本文將網絡壽命定義為網絡中第1個節點能量耗盡的時間。隨著網絡負載的增加，網絡壽命不斷下降，DPSO-QR算法的網絡壽命明顯比SAR和EQR長，是SAR的1.17倍，是EQR的1.08倍，且隨著負載的增加下降較為緩慢。這是因為DPSO-QR的局部集中計算模式有利于降低網絡節點能量消耗，有效避免節點快速死亡，延長了網絡壽命。

圖3 算法丟包率均值對比圖Fig 3 Comparison diagram of average packet loss rate of the algorithm

圖4 算法網絡生存時間均值對比圖Fig 4 Comparison diagram of average nework lifetime of the algorithm

5 結論

本文提出的DPSO-QR算法，以經典PSO算法為基礎，結合提出的加算子和擾動算子，設計出面向路由建立的多目標MDPSO，以實現QoS路由優化。DPSO-QR解決了當前大多數路由算法難以根據不同業務對QoS的不同需求提供相應保障的問題。仿真驗證表明:與SAR、EQR算法相比，DPSO-QR在可為網絡不同業務提供QoS保障的同時，有效減小了網絡平均端到端時延，降低了丟包率和網絡能量消耗，延長了網絡壽命。

［1］文 浩，林 闖，任豐原，等.無線傳感器網絡的QoS體系結構［J］.計算機學報，2009，32(3):432－440.

［2］Sohrabi K，Gao J，Ailawadhi V，et al.Protocols for self-organization of a wireless sensor network［J］.IEEE Personal Commmunications，2000，7(5):16－27.

［3］Akkaya K，Younis M.An energy-aware QoS routing protocol for wireless sensor networks［C］∥Proceedings of the IEEE Workshop on Mobile and Wireless Networks，Washington DC:IEEE Computer Society，2003:710－715.

［4］Lin C R，Liu J S.QoS routing in Ad Hoc wireless networks［J］.IEEE Journal on Selected Areas in Communications，1999，17(8):1426－1438.

［5］余 榮，孫 智，周海軍.保證服務質量的最小能量無線傳感器網絡路由算法［J］.清華大學學報，2007，47(10):1634－1637.

［6］Kenned Y J，Eberhart R.Particle swarm optimization［C］∥Proceedings of the 1995 IEEE International Conference on Neural Networks，1995:1942－1948.

［7］Kenned Y J，Eberhart R.A discrete binaey version of the particle swarm algorithm［C］∥Proceedings of the 1997 IEEE International Conference on Computational Cybernetics and Simulation，1997:4104－4108.