基于離散PSO的分層多鏈無線傳感器網絡路由算法*

范興剛，王 翊，介 婧，王萬良，侯佳斌

(浙江工業大學計算機科學與技術學院，杭州310023)

隨著傳感器技術、嵌入式技術以及低功耗無線通信技術的發展，生產一種聚集感應、無線通信和信息處理于一體的微型無線傳感器成為可能。這些廉價的、低功耗的傳感器節點可以大量部署在感興趣的區域，通過無線通信組織成無線傳感器網絡(WSN)，并采用協同合作方式來感知、采集和處理覆蓋區域中對象的信息，最終傳送各檢測數據給觀察者。通常，無線傳感器通過電池驅動，能量非常有限，但其工作的時間要求卻長達幾個月甚至幾年［1］，并且存在著部分關鍵路徑上節點能量消耗過快，整個網絡中各節點能量消耗不均的現象，最終導致網絡癱瘓，網絡的壽命受到限制。因此如何降低網絡能量消耗，延長網絡生存時間成為WSN研究中的熱點［2］，而改善網絡通信路由協議則成為解決問題的一個重要途徑［3－7］。

無線傳感器網絡從拓撲結構的角度可以分為兩類路由協議，分別是平面路由協議，如SPIN，Flooding，Directed Diffusion 等;層次路由協議，如 LEACH［3］，PEGASIS，TEEN等。LEACH協議是一種自適應分簇聚類路由算法，與一般的平面多跳路由算法相比，可以延長15%的生命周期。PEGASIS(Power-Efficient Gathering in Sensor Information Systems)［4］協議是由LEACH協議發展而來的基于“鏈”的路由協議，它的設計更加節能，其生存周期比LEACH提高1－3倍［5］。它假定組成網絡的傳感器節點是同構且靜止的，采用貪婪算法生成一條連接各個節點的距離最短的鏈，節點只需要與它最近的鄰居進行通信，并且隨機選擇一個節點作為簇頭與基站通信。但PEGASIS協議還存在著一些不足之處:

(1)貪婪算法是一種局部優化算法，容易陷入局部最優解，導致形成的鏈路較長;

(2)隨機選擇節點作為簇頭的方法，沒有考慮各節點能耗差別，導致各個節點負載不均衡，部分節點過早死亡;

(3)單簇頭節點可能產生瓶頸效應;

(4)當網絡規模增大時，單鏈模式增加網絡時延，可能造成數據過期，且一個節點出現問題可能會影響整個網絡。

針對這些不足，很多學者也提出了不同解決方法，主要是從路徑優化和分簇多鏈這兩方面來優化PEGASIS協議。GASA協議［6］采取模擬退火－遺傳混合算法替代貪婪算法的方式尋找一條總距離最短的路由鏈，它類似于解決一個TSP問題。但GASA協議仍然保持單鏈形式，因此并未從根本上解決PEGASIS協議存在的不足。ECR協議［7］采取劃分區域的方法，在區域內用C-W節約法組鏈，選擇各條鏈中能量最大的節點作為簇頭，并把這些簇頭組成一條簇頭鏈，選舉一個父簇頭與基站通信。這樣它有效地摒棄了單鏈帶來的缺陷，并使每條鏈中的距離相對較短。但是ECR協議在劃分區域時已經限制了組鏈節點的選擇，這樣的方式固然在區域內能找到比較短的鏈路，但是從全局上看未必最優。

粒子群算法(PSO)［8］自提出以來，以操作簡單，收斂速度快，解的質量高而普遍應用于電力，機械設計，神經網絡優化，通信，圖像處理等諸多領域。目前用離散粒子群算法(DPSO)來解決組合優化問題也是研究的一個熱點［9－11］。

針對PEGASIS及其優化協議的優缺點和PSO的優勢，本文提出一種基于離散粒子群優化算法的分層多鏈無線傳感器網絡路由算法(DPSOMCRA)。本算法考慮把PEGASIS的單鏈路形式分為多鏈路，這樣能降低通信時延，同時結合DPSO算法則能得到更短的全局最優路徑，最終使能量消耗的分布更加合理。通過仿真，與 PEGASIS，GASA，ECR協議算法進行比較，DPSO-MCRA算法能使得整個網絡有效生存周期顯著提高，能量消耗也更加均衡。

1 問題描述及算法介紹

1.1 問題描述

本文假設N個傳感器節點隨機分布在一個正方形區域A內，基站部署在A區域外，基站位置和節點位置都已知并固定，基站能量認為無窮大，無線發射功率可控，即節點可以根據距離調整發射功率大小，每輪節點能量消耗不統一。

本文的能耗模型參考文獻［4］中的設定:節點收發電路處理信號能量損耗Eelec=50 nJ/bit，信號發射放大器能量消耗 εamp=100 pJ/(bit·m－2)，信號發射所需的能量與收發節點間距離的平方即d2成正比，數據融合所消耗的能量為Efusion=5 nJ/bit。這樣發送kbit數據信息到相距為d的接收位置，所消耗的能量為:

接收kbit數據信息消耗的能量為:

融合kbit數據信息消耗的能量為:

1.2 算法介紹

本文采用分層多鏈的方式，把整個網絡分為高低兩層。低層由m條鏈構成，每個節點僅有一條鏈路通過，高層為這m條鏈的簇頭構成的一條簇頭鏈，并從中選出父簇頭與基站通信。

與PEGASIS類似，本算法由三個階段組成，分別是組鏈階段;簇頭節點選取階段;數據傳輸階段。

(1)組鏈階段

本階段通過DPSO算法來構建低層的節點間距離的平方和最小的鏈路。

(2)簇頭節點選取階段

考慮到父簇頭與基站的通信將消耗大量能量。在本階段為了保證能量消耗的均衡，節點自發地選擇整個網絡中剩余能量與到基站距離平方的比值最大的點作為父簇頭。父簇頭產生后，從它相鄰的鏈內選取距離父簇頭最近的一個節點作為鄰居鏈的簇頭，依次類推;每個被選舉的簇頭都把距離它最近的鄰鏈節點選取為鄰鏈的簇頭，最后，形成了一條簇頭鏈。這樣能保證得到一條相對較短的簇頭鏈。

(3)數據傳輸階段

本階段與PEGASIS數據傳輸階段類似。在數據傳輸階段，每條低層鏈的兩個端節點沿著鏈路將數據傳送給自己的鄰居節點。鄰居節點將自身數據和接收到的數據進行融合，然后將融合后的數據按同樣的方式傳輸給自己的鄰居節點。這一過程一直持續到鏈兩端的數據都到達簇頭節點。簇頭節點將自身的數據與接收到的數據融合后再按照上述方式沿高層的簇頭鏈傳遞給父簇頭。父簇頭將融合后的數據傳遞給基站。這樣，一輪通信過程結束。

2 問題模型

根據本文的算法要求，本問題模型定義 設點1，…，n表示m條鏈要經過的節點，定義變量:

Cij表示節點i，j之間距離的平方。目標函數

其中

約束條件

其中S表示鏈路起始點集合，T表示鏈路終結點集合。

在該模型中，式(1)表示使m條鏈的路徑平方和最小;式(2)表示各條鏈的路徑平方和;式(3)表示所有節點只有某一條鏈嚴格訪問一次;式(4)表示任意一條弧上的終點僅有一個起點與之相連，并且鏈路起始點不會出現在任何弧的終點上;式(5)表示任意一條弧上的起點僅有一個終點與之相連，并且鏈路終結點不會出現在任何弧的起點上。

3 基于離散粒子群算法的求解

粒子群優化算法(PSO)是一種基于群智能方法的演化計算技術，有較高的搜索效率，目前已被應用于多目標優化、模式識別、信號處理和決策支持等領域。本文分層多鏈問題的目標是把所有節點組合成多條鏈，且總距離最短。如把問題抽象起來看，則就是出發點不同的開放式多旅行商問題(MTSP)［9］，或是不考慮載重的開放式車輛路徑問題(OVRP)［12］。因此分層多鏈問題是一個組合優化問題，可以使用基于離散PSO算法對問題進行求解。目前對PSO算法的離散改造有很多種，M.Clerc［11］重新定義了運算符號和規則，黃嵐［13］等引入了交換子和交換序的概念，郭文忠［14］，王文鋒［10］等建立了局部極小區域的擾動機制。本文借鑒黃嵐等人定義的PSO速度和位置公式，并針對本問題的特點對其進行改造。

3.1 編碼方式

為支持尋找WSN內遍歷所有傳感器節點的最優多鏈的計算，本文的粒子采用“兩段式”整數編碼［15］，這種設計適合本問題的求解，并擁有較少的解空間。

設某粒子是一長度為n+m的整數S，由前后兩部分X和R組成。前段X表示鏈路按順序經過的節點序號，它由整數1到n的排列構成，長度為n;后段R中的每個數字分別表示第1條到第m條鏈路的長度，且這m個數的和等于節點總數n，R的長度為m。如圖1所示，有一個n=10，m=2的粒子，它有兩條長度分別為4和6的鏈路，鏈路1依次經過第1、5、8、7號節點，鏈路2依次經過第2、3、4、9、10、6 號節點。

圖1 “兩段式”整數編碼粒子

3.2 初始化種群

本文使用隨機方式生成初始解。首先，隨機生成網絡節點的排列;然后，把排列按照鏈路的數目隨機分為幾段;最后，把整個鏈路的序列按照本文的編碼方式映射到一個粒子上。如此重復，產生最初的種群。

3.3 啟發式算法

在求解WNS的路由中，為提高尋找最優解的速度，考慮使用一些啟發式算法，通過這些算法對解進行改進:

(1)消除鏈內交叉 真正的最優解中必定不包含交叉路徑，因此對于在一條鏈內出現交叉的情況，需要把它消除掉，如圖2所示。方法是找到兩個交叉的線段ab和ef后，拆除a與b、e與f的連接，改為a與e、b與f連，然后把原先夾在兩線段間的路徑倒序排列。

圖2 消除鏈內交叉

(2)消除鏈間交叉 雖然方法1保證鏈內不出現交叉，但在存在多條鏈路的區域中，鏈路之間還會遇到交叉的情況，如圖3所示。消除鏈間交叉的方法是:找到兩條交叉的線段(cd和mn)后，拆除c與d以及m與n的連接，改為c與n、d與m連。

圖3 消除鏈間交叉

(3)消除長路徑 在本算法中，把功耗較大的父簇頭與基站通信的任務讓某一剩余能量與到基站距離平方的比值最大的節點完成。在網絡中所有節點的剩余能量都在不停變化的情況下，這樣做可以使得每個節點都有機會擔任父簇頭，提高了網絡內節點能量分布的均衡性，延長網絡壽命。

在這種父簇頭選取的策略下，如果兩點間存在一條較長的線路，隨著輪數的增加，可能會遇到其他節點還有較多能量，但長路徑上的點過早把能量消耗完的情況。通過仿真發現大于平均長度的3倍的路徑較有可能出現這種情況。我們的方法是找到那些線段，在線段中增加中間節點，或者把該線段刪除另找其他路徑，如圖4。

圖4 消除長路徑

把上述的啟發式算法應用在DPSO中將提高整個算法的收斂速度，并保證解的質量。但與此同時也需要考慮它們在整個算法中應用的層面，因為如果應用在每個粒子的每輪更新中則會帶來較大的時間復雜度，效率并不高。

對此，考慮到DPSO的特點是所有粒子必須從種群最優點(pgbest)處學習，這樣對pgbest的改進能夠影響到所有粒子。因此上述的啟發式算法可以在pgbest更新時運行，這樣更為高效［9］。

3.4 自逃逸算法

PSO算法在理論上并不能保證一定能收斂到全局最優點，而是有可能僅收斂到種群最優點。當多數粒子的解都集中在某一個路由方案，并在幾輪中全局最優解都沒更新時，則可以認為粒子群可能找到全局最優解或者可能陷入局部最優區域，對于后者需要用某種策略來跳出，本文則采取自逃逸算法。自逃逸思想能夠在粒子群算法陷入局部區域時，讓種群自動逃離并尋找新的區域，同時還記著群體中的目前最好的位置［10］。

定義 設l為種群中所有粒子與各自pibest及pgbest的弧都重合的比率，即相似度;w’為pgbest連續沒有更新的輪數，如更新則歸零;ρ和w分別為l和w’所對應的閾值。

自逃逸算法可描述為:

其中:

這里，E(Pi)表示Pi的弧集合;|E(Pi)|表示E(Pi)中弧的數目;|Li|表示Pi的弧與pibest和pgbest都重合的弧的數目;n為網絡內節點總數;λ為種群中粒子總數。

當種群中大部分粒子都搜索某一區域內時，基本能保證找到局部最優解或次優解，再繼續收斂則可能陷入局部最優。對于這樣的情況，種群中的粒子就會被初始化的新粒子替代，以保持種群的多樣性，跳出局部最優區域。

3.5 適應度計算

在每次迭代粒子更新位置后，根據公式(1)計算出目標函數值Z，則適應度為:

3.6 求解步驟

在本算法設計中定義粒子為兩段式，且含義不同。因此需要在每次運算中分別計算粒子的前后兩段，這樣才能保證粒子既能進化各鏈中的位置又能進化各鏈的長度。

本文算法的步驟如下:

步驟1 初始化粒子群;

步驟2 計算每個粒子適應度值;

步驟3 比較適應度，選擇pibest和pgbest;

步驟4 使用啟發式算法改進pgbest;

步驟5 計算種群的相似度l，如果相似度大于閾值ρ且w’大于w，啟動逃逸算法;

步驟6 根據DPSO公式進行位置更新;

步驟7 判斷是否達到結束條件，是則結束，否則轉入步驟2。

4 實驗結果及分析

為了驗證DPSO-MCRA算法的性能，本文對該算法進行了Matlab仿真，并同時模擬PEGASIS、GASA、ECR算法與其進行對比。

仿真環境的設定:在100 m×100 m的正方形區域內隨機產生100個節點，Sink節點位于監測區域外的(50，150)，節點初始能量 E0=0.25 J，數據傳輸包大小k=2 000 bit，數據融合后包大小不變，采用按工作周期“輪”(Round)進行數據采集的方式運行整個網絡，并用輪數衡量網絡的壽命。

仿真中自逃逸參數ρ設為0.8，w為8。對于本算法分鏈數目m的選擇問題，我們分別對2，3，5，7，10條鏈路進行仿真，以50%節點死亡的生存周期為對比值，各運行20次取平均值，結果見圖5。

圖5 不同分鏈數m對比圖

從仿真結果看，當m取5時，網絡在50%節點失效的情況下輪數達到最高。隨著網絡m的減少，運行輪數迅速減小。這是由于鏈路的減少造成了相鄰節點選擇余地的減少，造成總路徑距離的增加。相反，當m增加時，輪數略微減少。這是由于雖然鏈路的增多能使相鄰節點的距離普遍減小，但鏈路中簇頭的增多卻帶來了更多的簇頭間的通信能耗。因此根據實際情況選擇適當的鏈路數目才能使節點及簇頭的能耗達到平衡。本文的仿真中均取m=5。

從通信距離看本算法得到的鏈路也是最短的，圖6是它們各自的通訊鏈路情況。從表1中可以看到PEGASIS的鏈路最長，比本算法大了3倍多;ECR雖然根據區域劃分為5條不交叉的鏈路，但由于未采用優化算法故距離要比GASA長;GASA在單鏈的情況下能找到一條最短的鏈路，但比本算法還是多了將近20%的距離。本算法采用多條鏈的形式，既降低網絡內鏈路距離，又減少傳遞延時，并采取策略消除長鏈，使各個節點能耗差別減小，有利于網絡能量消耗的平衡，防止節點過早死亡，延長網絡壽命。

表1 DPSO-MCRA與其他算法對比

圖6 各算法鏈路圖

本文對DPSO-MCRA算法生存周期進行仿真，分別與PEGASIS，GASA，ECR協議比較。比較結果見表2及圖7。

圖7 DPSO-MCRA與其他算法生存周期對比圖

表2 DPSO-MCRA與其他算法的生存周期對比

表2的結果顯示，本算法出現第一個節點死亡的輪數較晚，比PEGASIS的輪數提高近3倍。在能保證網絡有效性的20%、50%、80%節點死亡的情況下，本算法與PEGASIS，GASA，ECR協議的生存周期相比是最長的。這是因為首先本算法選取網絡中剩余能量與到基站距離的比值最大的節點作為父簇頭節點，使網絡的能量消耗均勻，有效延長了網絡中第一個死亡節點存活的時間;其次，采取多條鏈路的形式，并結合離散粒子群優化算法組建網絡通信路徑，得到總路徑平方和最小的路徑，減小每輪節點間信號傳輸的距離，降低能耗，并在整體上均衡能耗的分布，延長了網絡失效的時間。

值得一提的是，在圖7中，PEGASIS協議最后全部節點死亡的生存周期比本算法要長一些。這是因為其能耗分布不均衡致使部分節點消耗的能量比其他節點少，因而這些節點的存活壽命會相對較長。但當網絡中大部分節點死亡時，網絡監測就失去意義了，網絡的生命周期實際上已經結束。而本算法在50%節點開始死亡后整個網絡就在近20輪內迅速死亡，這是由于節點間剩余能量差異并不顯著，也是其網絡能耗分布均衡的表現。

在WSN設計中，保持能量的有效性所帶來的過高延遲也是實際情況中所需要避免的。因此必須尋求能量消耗和延遲兩者之間的一個折衷。本算法中描述的分層多鏈構建法能有效減少延遲。

假設一個節點將數據傳遞給另外一個節點所需的時間為一個時間單位。對于一個100個節點的網絡，PEGASIS協議和GASA協議每輪數據傳輸的時延都達到100個單位時間。ECR協議則與本算法的時延類似，按照分5條鏈來算，總共大概需要25個單位時間。表1顯示了PEGASIS，ECR，GASA協議和本算法的時延開銷比較，從中可以看出本算法在降低網絡時延上還是比較有效的。

與其他算法對比，本算法在優化能耗和降低時延這兩個問題上能做到兩者兼顧，既能保證較長的生存周期又擁有較低的通信時延。

5 結束語

本文在分析了 PEGASIS、GASA、ECR協議優缺點的基礎上，提出了基于離散粒子群優化算法的分層多鏈無線傳感器網絡路由算法DPSOMCRA。它把網絡分層后，采用離散粒子群優化算法并結合多種啟發式算法快速得到全局最優的多條鏈路的路徑，即降低能耗又減小延遲。同時改進簇頭選擇方法，有效地減少能耗并保證能耗的均衡，延長網絡壽命。仿真結果顯示，本算法比其他協議在20%—80%節點死亡的情況下，生存周期顯著提高。首節點死亡時的生存周期比PEGASIS協議提高了近3倍。

［1］Shih E，Cho S，Ickes N，et al.Physical Layer Driven Protocol and Algorithm Design for Energy-Efficient Wireless Sensor Networks［C］.Proceedings of ACM MobiCom’01，Rome，Italy，2001:272－287.

［2］Sohrabi K，Gao J，Ailawadhi V，et al.Protocols for Self-Organization of a Wireless Sensor Network［J］.IEEE Personal Communications，2000，7(5):16－27.

［3］Heinzelman W，Chandrakasan A，Balakrishnan H，et al.An Application-Specific Protocol Architecture for Wireless Microsensor Networks［C］//IEEE Trans，on Wireless Communications，2002，1(4):660－670.

［4］Lindsey S，Raghavendra C S.PEGASIS:Power-Efficient Gathering in Sensor Information Systems［J］.Aerospace Conference Proceddings，2002(3):1125 －1130.

［5］Al-Karaki JN，Kamal AE.Routing Techniques in Wireless Sensor Networks:a Survey［J］.IEEE Wireless Communications，2004，11(6):6－28.

［6］黃飛，金心宇，張昱，等.基于GASA的能耗均衡WSN路由協議［J］.傳感技術學報，2009(4):586－592.

［7］田瑩，王瑩，張淑芳，等.高效節能的鏈式分層無線傳感器網絡路由協議［J］.計算機工程與應用，2007，43(35):22－26.

［8］Kennedy J，Eberhart R C.Particle Swarm Optimization［C］//Proc IEEE International Conference on Neural Net-Works，IV.Piscataway，NJ:IEEE Service Center，1995:1942 －1948.

［9］Shi X H，Liang Y C，Lee H P，et al.Particle Swarm Optimization Based Algorithms for TSP and Generalized TSP［J］.Information Processing Letters，2007，103(5):169 －176.

［10］王文峰，劉光遠，溫萬惠，等.求解TSP問題的自逃逸混合離散粒子群算法研究［J］.計算機科學，2007(10):2478－2480.

［11］Clerc M.Discrete Particle Swarm Optimization，Illustrated by the Traveling Salesman Problem［C］//New Optimization Techniques in Engineering.Heidelberg，Germany，2004，219 －239.

［12］趙燕偉，吳斌，王萬良，等.Particle Swarm Optimization for Open Vehicle Routing Problem with Time Dependent Travel Time［C］//Proceedings of the 17 th IFAC World Congress，July.2008:12843－12848.

［13］黃嵐，王康平，周春光，等.粒子群優化算法求解旅行商問題［J］.吉林大學學報(理學版)，2003，41(4):477 －480.

［14］郭文忠，陳國龍.求解TSP問題的模糊自使用粒子群算法［J］.計算機科學，2006(6):161－162.

［15］歐陽杰平.使用遺傳算法解決MTSP問題的一種新的染色體設計［J］.艦船電子工程，2006(3):107－109.