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

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

0 引言

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

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

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

1 QoS路由問題的網(wǎng)絡模型

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

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

其中，ε為路徑損耗系數(shù)，取值為50 nJ/bit，k為發(fā)送數(shù)據(jù)包長度，kbit。

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

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

式中 max Cab為路徑Pab中節(jié)點一跳通信范圍R內(nèi)最大的能量傳播損耗，h為路徑Pab的跳數(shù)。

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

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

2.1 改進的離散粒子群算法

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

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

2.2 離散粒子群算法初始化

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

2.3 加算子

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

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

2)進行插入銜接

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

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

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

2.4 擾動算子

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

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

2.5 MDPSO 流程

1)當節(jié)點有數(shù)據(jù)發(fā)送需求時，進行算法初始化;

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

3)每次迭代后，判斷各粒子當前解Xi與其歷史Pareto最優(yōu)解集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)當?shù)螖?shù)達到n或者G未被更新的迭代次數(shù)達到F，則輸出G;否則，返回步驟(2);

6)根據(jù)數(shù)據(jù)傳輸?shù)腝oS需求，按式(7)計算G中路徑適應度fitness，其中，w為數(shù)據(jù)傳輸時設定的QoS需求權重。計算完成后取fitness最小的路徑轉(zhuǎn)發(fā)數(shù)據(jù)

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

3 DPSO-QR整體流程

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

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

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

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

4)當有數(shù)據(jù)發(fā)送需求時，節(jié)點用MDPSO計算出Pareto最優(yōu)解集G。按待發(fā)送的數(shù)據(jù)對QoS的需求，結合式(7)，選出局部區(qū)域最佳路由進行轉(zhuǎn)發(fā)。在得到集合G后的時間ts內(nèi)，將不再重新計算G。ts時間后有數(shù)據(jù)發(fā)送需求時，重新計算G，以適應網(wǎng)絡參數(shù)的變化;

5)每間隔時間ts，節(jié)點將自身和2跳范圍內(nèi)的節(jié)點以及路徑QoS參數(shù)發(fā)生變化的部分參數(shù)打包，并發(fā)送給自己的鄰居節(jié)點，實現(xiàn)局部區(qū)域的QoS參數(shù)更新;

6)局部目標節(jié)點收到數(shù)據(jù)后，轉(zhuǎn)到步驟(3)，繼續(xù)搜索以其為源節(jié)點的局部區(qū)域最優(yōu)路由，直至數(shù)據(jù)傳輸至Sink。

4 仿真實驗

在100 m×100 m的平面區(qū)域中隨機布撒100個無線傳感器節(jié)點，Sink節(jié)點位于右上角，節(jié)點初始能量為1J，最大無線通信半徑為20 m;仿真過程中，節(jié)點以一定周期產(chǎn)生長度為128 bytes的數(shù)據(jù)包向Sink節(jié)點發(fā)送。設網(wǎng)絡QoS路由參數(shù)度量需求的取值范圍為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)。通過改變數(shù)據(jù)包發(fā)送速率，從1～10 pkt/s來模擬不同的網(wǎng)絡負載。仿真分別對DPSO-QR，SAR和EQR算法進行了10次仿真，網(wǎng)絡性能對比圖如圖1～圖4所示。

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

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

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

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

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

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

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

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

5 結論

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

［1］文 浩，林 闖，任豐原，等.無線傳感器網(wǎng)絡的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］余 榮，孫 智，周海軍.保證服務質(zhì)量的最小能量無線傳感器網(wǎng)絡路由算法［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.