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

常峰

（樂山師范學(xué)院 物理與電子工程學(xué)院，四川 樂山　614004）

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

常峰

（樂山師范學(xué)院 物理與電子工程學(xué)院，四川 樂山614004）

聚合樹是無線傳感器網(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)，具有高效性和可行性。

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

0　引　言

無線傳感器網(wǎng)絡(luò)（Wireless Sensor Network，WSN）是由多個(gè)靜態(tài)傳感器組成，通過無線介質(zhì)連接，執(zhí)行物理世界的分布式感知、數(shù)據(jù)處理和決策［1］。由于傳感器經(jīng)常密集部署，使得相鄰節(jié)點(diǎn)所采集的數(shù)據(jù)存在一定的冗余，如果直接從源節(jié)點(diǎn)向sink節(jié)點(diǎn)傳輸數(shù)據(jù)，會(huì)導(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］。即在一個(gè)給定的加權(quán)圖中找出一個(gè)包含所有終端（sink和源節(jié)點(diǎn)）的最小權(quán)值的連通子圖。為了得到有效的聚合樹，多個(gè)性能指標(biāo)被用來構(gòu)建樹結(jié)構(gòu)，其中，能源消耗、收斂時(shí)間、網(wǎng)絡(luò)壽命和通道信號(hào)干擾是常見的性能標(biāo)準(zhǔn)［4-5］。當(dāng)需要考慮多個(gè)約束時(shí)，建立聚合樹就變成一個(gè)多目標(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ù)聚合功能，且只考慮了兩個(gè)目標(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)的，兩個(gè)節(jié)點(diǎn)之間的通信鏈路是對稱的，且每個(gè)節(jié)點(diǎn)的傳輸距離有限，聚合功能在生成樹的中間節(jié)點(diǎn)上自動(dòng)執(zhí)行。

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

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

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

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

目標(biāo)1：最小化樹的總能耗?？偰茉聪闹?f1（x）為樹中所有節(jié)點(diǎn)的能耗，表達(dá)式為：

式中：Cnum表示子節(jié)點(diǎn)的數(shù)量；ETX，ERX，EDA分別表示節(jié)點(diǎn)發(fā)送、接收和數(shù)據(jù)聚合所消耗的能量。

目標(biāo)2：最大化樹的網(wǎng)絡(luò)壽命。網(wǎng)絡(luò)的生命周期是指聚合樹能夠保持正常功能的時(shí)間段，即為中繼節(jié)點(diǎn)的最小壽命。為了方便后續(xù)加權(quán)比較，定義壽命 f2（x）為真實(shí)壽命的倒數(shù)，表達(dá)式為：

目標(biāo)3：最小化樹聚合的延遲。數(shù)據(jù)聚合的延遲為從第一個(gè)源節(jié)點(diǎn)到sink節(jié)點(diǎn)傳輸數(shù)據(jù)包所需的時(shí)間，延遲時(shí)間函數(shù) f3（）x表達(dá)式為：

目標(biāo)4：最小化樹聚合的通信干擾。鏈路干擾被定義為受通信影響的節(jié)點(diǎn)數(shù)量，干擾函數(shù) f4（x）表達(dá)式為：

2　提出的JPSO-TE方案

2.1JPSO-TE算法描述

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

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

算法1：JPSO-TE算法

輸入：G（V，E）

輸出：Tree

Initialize（P1，P2，…，Pj）；

while找出最優(yōu)樹do

for每個(gè)粒子Pjdo

R=random（）；

ifC0＜R≤C0+C1then

flag =match（Pj，Bj，layer1）；

Pj=Particle_Flying（Pj，Bj，flag）；

else ifC0+C1＜Rthen

flag =match（Pj，Gs，layer1）；

Pj=Particle_Flying（Pj，Gs，flag）；

end if

Pj=Particle_Repair（Pj）；

Fitness_Evaluation（Pj）；

Individual_Best（Bj）；

end for

Global_Best（Gs）；

end while

Tree=TCR_Decoder（Gs）；

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)怎樣變化，它必須遵守一個(gè)約束，即生成樹的終端必須是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ù)為n，源節(jié)點(diǎn)數(shù)為m。編碼方案示例如圖1所示。

圖1　生成樹編碼示例

第一層，以一個(gè)二進(jìn)制字符串作為候選節(jié)點(diǎn)的Steiner標(biāo)志。圖 1中，Steiner節(jié)點(diǎn)的候選數(shù)量為n-m=17，按節(jié)點(diǎn)序號(hào)排列對其進(jìn)行二進(jìn)制編碼，1表示相應(yīng)節(jié)點(diǎn)被選為Steiner節(jié)點(diǎn)，0表示不被選擇。

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

圖2　EWD譯碼過程實(shí)例（構(gòu)建樹）

2.3粒子飛行

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

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

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

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

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

總適應(yīng)度值為各目標(biāo)函數(shù)的加權(quán)和，根據(jù)各目標(biāo)函數(shù) fi（x）的表達(dá)式可知，fi（x）值越小越好，即總適應(yīng)度值越小，整個(gè)網(wǎng)絡(luò)結(jié)構(gòu)性能越好。在加權(quán)和的同時(shí)，帕累托度函數(shù)P（x）被引入作為分段函數(shù)。如果x是非支配解，則P（x）=0否則P（x）=1。最終的混合適應(yīng)度函數(shù)是由這兩部分組成，其表達(dá)式為：

這種混合函數(shù)彌補(bǔ)了傳統(tǒng)加權(quán)函數(shù)的局限性，有助于在帕累托前沿獲得最佳解決方案。

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

利用NS2仿真工具進(jìn)行大量實(shí)驗(yàn)，評(píng)估本文提出的JPSO-TE算法的高效性和可行性。傳感器節(jié)點(diǎn)被分布在100 m×100 m區(qū)域內(nèi)，其中只有一個(gè)sink節(jié)點(diǎn)，傳感器節(jié)點(diǎn)總數(shù)和源節(jié)點(diǎn)數(shù)量都是可變的，每個(gè)節(jié)點(diǎn)的傳輸范圍為25 m。能耗參數(shù)設(shè)定為：ERX=k·50 nJ/b，ETX=k·（50+0.1d2）nJ/b，EDA=5 nJ/b，k=4 000 b。

圖3中描述了在一個(gè)隨機(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)。

圖3　多目標(biāo)Steiner樹結(jié)構(gòu)

本文將混合適應(yīng)度值作為衡量多目標(biāo)優(yōu)化近似算法的性能指標(biāo)。不同方法在不同源節(jié)點(diǎn)數(shù)量下的適應(yīng)度值如圖4所示。圖4中，在其他參數(shù)不變的情況下，適應(yīng)度值會(huì)隨著源節(jié)點(diǎn)數(shù)目的增加而變大，但增長率會(huì)逐漸下降。這是由于越來越多的源節(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)。

圖4　不同源節(jié)點(diǎn)數(shù)量下，三種方案的適應(yīng)度值

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

圖5　編碼方案的比較

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í)際要求。

［1］楊銀堂，高翔，柴常春，等.一種WSN中的能耗優(yōu)化動(dòng)態(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.

Multi-constraint Steiner tree algorithm combining two-layer encoding with JPSO in WSN

CHANG Feng
（School of Physics and Electronic Engineering，Leshan Normal University，Leshan 614004，China）

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.

WSN；multi-constraint Steiner tree；JPSO；two-layer encoding

TN911-34

A

1004-373X（2016）13-0015-04

10.16652/j.issn.1004-373x.2016.13.004

2015-10-09

國家自然科學(xué)基金民航聯(lián)合基金重點(diǎn)項(xiàng)目（U1233202/F01）

常峰（1980—），男，四川樂山人，碩士，實(shí)驗(yàn)師。主要研究方向?yàn)閭鞲衅骶W(wǎng)絡(luò)、自動(dòng)測試技術(shù)及系統(tǒng)集成。