WSN中結(jié)合雙層編碼和JPSO的多約束Steiner樹算法

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

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

中圖分類號： TN911?34 文獻(xiàn)標(biāo)識碼： 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 引 言

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

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

1 問題描述和定義

為了分析MCSTP模型，本文假設(shè)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)是靜態(tài)的，兩個節(jié)點(diǎn)之間的通信鏈路是對稱的，且每個節(jié)點(diǎn)的傳輸距離有限，聚合功能在生成樹的中間節(jié)點(diǎn)上自動執(zhí)行。

1.1 網(wǎng)絡(luò)模型

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

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

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

2 提出的JPSO?TE方案

2.1 JPSO?TE算法描述

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

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

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

2.2 粒子雙層編碼

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

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

2.3 粒子飛行

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

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

2.4 適應(yīng)度函數(shù)

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

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

3 實(shí)驗(yàn)及分析

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

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

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

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

4 結(jié) 語

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

參考文獻(xiàn)

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

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

[3] 范容，潘雪增，傅建慶，等.基于Steiner樹的層次型無線傳感器網(wǎng)絡(luò)安全組播協(xié)議[J].傳感技術(shù)學(xué)報(bào)，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.