摘 要： 聚合樹是無線傳感器網絡（WSN）中的一種典型的數據聚合技術。針對多目標約束的Steiner樹問題（MCSTP），提出一種基于雙層編碼機制（TE）和跳躍粒子群優(yōu)化（JPSO）的啟發(fā)式算法構建最優(yōu)樹結構。首先，選擇總能耗、網絡壽命、收斂時間和通信干擾作為優(yōu)化約束目標。然后，根據提出的雙層編碼方案對生成樹的解進行編碼，同時利用跳躍粒子群優(yōu)化算法尋找帕累托最優(yōu)解。最后，利用提出的混合適應度函數找出近似最優(yōu)樹結構。實驗結果表明，JPSO?TE方法可以產生近似最優(yōu)的樹結構，具有高效性和可行性。

關鍵詞： 無線傳感器網絡； 多約束Steiner樹； 跳躍粒子群優(yōu)化； 雙層編碼

中圖分類號： TN911?34 文獻標識碼： A 文章編號： 1004?373X（2016）13?0015?04

Abstract： The aggregation tree is a typical data aggregation technology in wireless sensor network （WSN）. To solve the multi?constraint optimization Steiner tree problem （MCSTP）， a heuristic algorithm based on two?layer encoding （TE） mechanism and jump particle swarm optimization （JPSO） algorithm is proposed to construct the optimal tree structure. The total energy consumption， network lifetime， convergence time and communication interference are selected as the optimal constraint targets. And then， the TE scheme is used to encode the solution of spanning tree， and the JPSO algorithm is used to find the Pareto optimal solution. The proposed hybrid fitness function is used to find out the approximately?optimal tree structure. The experimental results show that the JPSO?TE method can generate the approximately?optimal tree structure， and has high efficiency and feasibility.

Keywords： WSN； multi?constraint Steiner tree； JPSO； two?layer encoding

0 引 言

無線傳感器網絡（Wireless Sensor Network，WSN）是由多個靜態(tài)傳感器組成，通過無線介質連接，執(zhí)行物理世界的分布式感知、數據處理和決策[1]。由于傳感器經常密集部署，使得相鄰節(jié)點所采集的數據存在一定的冗余，如果直接從源節(jié)點向sink節(jié)點傳輸數據，會導致很高的通信負載。因此，在傳輸過程中需要進行數據聚合。聚合樹作為一種典型的技術廣泛應用于事件聚合中，源節(jié)點發(fā)送原始數據給中繼節(jié)點，中繼節(jié)點消除冗余數據，再將聚合結果轉發(fā)給其他中繼節(jié)點，直到到達sink節(jié)點[2]。然而，選擇哪些傳感器作為中繼節(jié)點可以抽象描述為一種NP?完全的組合優(yōu)化問題，稱為Steiner樹問題（SteinerTree Problem，STP）[3]。即在一個給定的加權圖中找出一個包含所有終端（sink和源節(jié)點）的最小權值的連通子圖。為了得到有效的聚合樹，多個性能指標被用來構建樹結構，其中，能源消耗、收斂時間、網絡壽命和通道信號干擾是常見的性能標準[4?5]。當需要考慮多個約束時，建立聚合樹就變成一個多目標約束優(yōu)化問題。為了找出有效的樹結構，文獻[6]提出了一種基于最小生成樹算法的近似算法：MST?1tRNP算法。它的目的是解決WSN中的中繼節(jié)點問題，也就是STP，但其優(yōu)化目標單一，只可以產生總鏈路成本最低的樹結構。文獻[7]提出另一種基于遺傳算法的近似算法：M?REST算法，解決多目標的中繼節(jié)點問題。然而，其模型中沒有考慮數據聚合功能，且只考慮了兩個目標。此外，在這種結構中，編碼方案效率低，需要特定的破圈法來保持解的可行性。

本文將多目標優(yōu)化和Steiner樹的組合問題稱為多目標約束優(yōu)化Steiner樹問題（Multi?constraint Optimization STP，MCSTP）。提出一種基于特定雙層編碼（Two?Layer Encoding，TE）機制和跳躍粒子群優(yōu)化（Jump Particle Swarm Optimization，JPSO）的啟發(fā)式算法（JPSO?TE），在多項式時間內找出MCSTP問題的近似最優(yōu)解。

1 問題描述和定義

為了分析MCSTP模型，本文假設網絡拓撲結構是靜態(tài)的，兩個節(jié)點之間的通信鏈路是對稱的，且每個節(jié)點的傳輸距離有限，聚合功能在生成樹的中間節(jié)點上自動執(zhí)行。

1.1 網絡模型

WSN可建模為一個無向圖，其中是傳感器的集合，并均勻或隨機地分布在監(jiān)測區(qū)域，值為，表示節(jié)點之間的連接。設定源節(jié)點的數量為，網絡中只有一個sink節(jié)點，網絡中的中繼節(jié)點可被視為Steiner節(jié)點，生成樹被定義為。此外，一些沒有源數據的傳感器節(jié)點也可以用來中繼數據。

1.2 多目標約束優(yōu)化

多目標約束優(yōu)化是一種期望多個目標函數得到平等處理的框架模型。在大部分文獻中，只考慮一個或兩個目標，其中最常見的是能耗和延遲，忽視了其他重要的目標。本文對常見的應用需求進行總結，選擇出四個最重要的目標，描述如下。

2 提出的JPSO?TE方案

2.1 JPSO?TE算法描述

跳躍粒子群優(yōu)化（JPSO）算法是離散粒子群優(yōu)化（DPSO）算法的變種。JPSO將更新方程的權重表示為概率，每個粒子在每次迭代中都會向吸引子引導的方向移動，從一個解跳躍至另一個解。

JPSO算法中每個粒子代表一種樹結構的解決方案，要解決MCSTP問題，主要的難點是設計高效的編碼方案和進化算子。對于MCSTP問題，對編碼方案有兩個要求。首先，編碼可以在不完全圖上進化。第二，Steiner樹中所涉及的節(jié)點編碼是可變的，編碼不僅可以在所有節(jié)點的完整集合上進化，而且在節(jié)點的不同子集上也可以進化。為了有效的進化，本文提出利用雙層編碼方案保證粒子在可行解空間內飛行。JPSO?TE算法如下所述：

JPSO?TE算法中，Particle_Flying（粒子飛行）是進化算子，Particle_Repair（粒子修復）用于修剪樹形結構，消除當前不合格的葉節(jié)點，確保粒子的可行性。TCR_Decoder（TCR解碼器）用來將粒子編碼轉換為樹結構。

2.2 粒子雙層編碼

無論樹結構怎樣變化，它必須遵守一個約束，即生成樹的終端必須是sink節(jié)點和源節(jié)點，所有源節(jié)點必須包含在樹中，Steiner節(jié)點作為中繼節(jié)點來中繼和聚合數據。為了產生細粒度解決方案，本文提出一種雙層編碼方案，設定節(jié)點總數為源節(jié)點數為編碼方案示例如圖1所示。

第二層是在第一層內容的基礎上形成的，并完善成可行解。本文在第二層中利用S.M. Soak提出邊窗編碼（Edge Window Decoder，EWD）方案[8]來編碼粒子代表。利用樹構建算法（Tree?construction Algorithm，TCR）對子圖直接解碼，TCR解碼器將輸入的字符串解碼成一個獨一無二的生成樹。TCR解碼過程的例子如圖2所示，編碼中的數字為節(jié)點ID，以相鄰兩個節(jié)點為邊構造樹，樹結構中的所有邊不能形成循環(huán)結構，如圖中虛線所示。若EWD編碼長度為，則能夠表示出所涉及節(jié)點（的子集，為）的所有可能Steiner樹結構，所以本文定義EWD編碼的長度為。

2.3 粒子飛行

傳統(tǒng)粒子飛行算法是利用特定的進化操作來確保粒子在可行解空間不停的飛行。這個操作可以繼承吸引子（當前最佳粒子）的部分樹狀結構，并探索最佳位置。然而，該操作是單向的，只能改善當前粒子。本文中，將兩個編碼層的代表粒度進行對比，根據對比結果以不同的方式實現進化操作。當兩編碼層代表粒度相同時，第一層保持不變，第二層開始以細粒度分級來構建結構。當兩個編碼層不相同時，進化操作在第一層執(zhí)行，同時執(zhí)行額外的操作改善對父輩樹結構的繼承性。

本文算法中，是后代，和分別為父輩的第一層和第二層，和分別為最優(yōu)解的第一層和第二層。如果第一層編碼是相同的，則在第二層執(zhí)行原始EWD進化操作，進行相鄰節(jié)點自適應交叉和突變。否則，對和進行局部OR操作產生后代的第一層，同時對和解碼獲得和在Residual選擇中，只有一個邊的兩個終端都是的Steiner節(jié)點，才能被導入邊集合Edges。為了更好地繼承父代優(yōu)良結構，根據 Intersection和Edges產生一個新的樹再將轉換成EWD編碼。最后，形成由兩層編碼組成的新的子代，其中部分樹結構從父輩繼承。

2.4 適應度函數

適應度函數用來評估解決方案在進化算法中的性能。目前，針對多目標優(yōu)化有兩個傳統(tǒng)的適應度函數：帕累托最優(yōu)度與加權和。帕累托方法只考慮帕累托支配解和非支配解之間的鑒別，沒有考慮非支配解之間的差異。加權和方法彌補了這一缺點，然而其對多個目標的權重分配是不合理的。

鑒于以上原因，本文提出一種自適應混合函數來評估解決方案，融合了兩個傳統(tǒng)適應度函數的優(yōu)點。如果是當前可行解，設定第個目標的當前適應度值為和代表第個目標的最大值和最小值。在每個進化周期后，會更新相關的適應度函數。加權和適應度函數表達式為：

3 實驗及分析

利用NS2仿真工具進行大量實驗，評估本文提出的JPSO?TE算法的高效性和可行性。傳感器節(jié)點被分布在100 m×100 m區(qū)域內，其中只有一個sink節(jié)點，傳感器節(jié)點總數和源節(jié)點數量都是可變的，每個節(jié)點的傳輸范圍為25 m。能耗參數設定為：。

圖3中描述了在一個隨機分布下，JPSO?TE方法獲得的多目標Steiner樹結構的例子，其中方節(jié)點、圓節(jié)點和三角形節(jié)點分別表示源節(jié)點、中繼節(jié)點和sink節(jié)點。

本文將混合適應度值作為衡量多目標優(yōu)化近似算法的性能指標。不同方法在不同源節(jié)點數量下的適應度值如圖4所示。圖4中，在其他參數不變的情況下，適應度值會隨著源節(jié)點數目的增加而變大，但增長率會逐漸下降。這是由于越來越多的源節(jié)點顯示為較高成本，且生成樹的尺寸不斷增大，各目標函數值增大，造成更高的適應度值。另外，在一定的限制區(qū)間內，源節(jié)點越多意味著源節(jié)點成為中繼節(jié)點的可能性增加，普通節(jié)點被選擇作為中繼節(jié)點的幾率減小，這就減緩了適應度值的增長率。與文獻[6]和文獻[7]方法相比，本文JPSO?TE方法具有最低的適應度值，表明能夠構建出更優(yōu)的樹結構。

為了獨立評估本文提出的編碼方案，將現有的兩個基于樹的編碼方案（Prufer編碼、邊集編碼）和本文雙層編碼方案進行比較。圖5所示為三種編碼方案下，解的質量的箱線圖。JPSO?TE的上四分位數、中位數和下四分位數都較小，表明解決方案接近于理論最優(yōu)解。同時，JPSO?TE的上下四分位范圍較小，意味著粒子的飛行軌跡更集中在最優(yōu)解周圍。這些結果表明了在MCSTP問題中，本文提出的雙層編碼方案具有高效性。

4 結 語

本文將WSN數據融合中尋找最優(yōu)生成樹問題定義為MCSTP。針對實際應用的要求，將四種指標作為聚合樹的最終優(yōu)化目標。提出一種基于JPSO的啟發(fā)式方法，利用自定義的編碼方案和進化操作求解MCSTP問題。仿真實驗表明，本文方法可以產生近似最優(yōu)的樹結構，且性能優(yōu)于其他方法。在今后工作中，將分布式實現JPSO來提高算法的收斂時間。此外，更多的性能指標將被導入多目標優(yōu)化框架，滿足一些特殊的實際要求。

參考文獻

[1] 楊銀堂，高翔，柴常春，等.一種WSN中的能耗優(yōu)化動態(tài)路由算法[J].西安電子科技大學學報，2010，37（5）：777?782.

[2] 郭新明，趙薔，蔡軍偉.基于覆蓋概率模型的無線傳感器網絡覆蓋算法[J].中國科技論文，2013，8（4）：316?320.

[3] 范容，潘雪增，傅建慶，等.基于Steiner樹的層次型無線傳感器網絡安全組播協(xié)議[J].傳感技術學報，2011，24（4）：601?608.

[4] YANG J， ZHANG H， LING Y， et al. Task allocation for wireless sensor network using modified binary particle swarm optimization [J]. IEEE sensors journal， 2014， 14（3）： 882?892.

[5] TAN H O， KORPEOGLU I， STOJMENOVIC I. Computing localized power?efficient data aggregation trees for sensor networks [J]. IEEE transactions on parallel and distributed systems， 2013， 22（3）： 489?500.

[6] LIOYD E L， XUE G. Relay node placement in wireless sensor networks [J]. IEEE transactions on computers， 2007， 56（1）： 134?138.

[7] PEREZ A J， LABRADOR M A， WIGHTMAN P M. A multiobjective approach to the relay placement problem in WSNs [C]// Proceedings of 2011 IEEE Wireless Communications and Networking Conference. Cancun： IEEE， 2011： 475?480.

[8] SOAK S M， CORNE D W， AHN B H. The edge?window?decoder representation for tree?based problems [J]. IEEE transactions on evolutionary computation， 2010， 10（2）： 124?144.