宮　華，盧海龍，袁　田

(沈陽理工大學 理學院，沈陽 110159)

?

基于PSO算法的無線傳感器網(wǎng)絡組網(wǎng)方法

宮華，盧海龍，袁田

(沈陽理工大學 理學院，沈陽 110159)

針對無線傳感器網(wǎng)絡中各節(jié)點能量有限的特點，設計了一種基于PSO算法的分簇組網(wǎng)方法。目標函數(shù)為最小化節(jié)點數(shù)據(jù)傳輸能耗、平衡簇頭節(jié)點的負載、協(xié)調(diào)成員節(jié)點的通信能耗和網(wǎng)絡的最優(yōu)通信結構。算法由基站發(fā)起，廣播至網(wǎng)絡中的每個節(jié)點，利用PSO算法設計了兩階段組網(wǎng)算法，將目標網(wǎng)絡劃分為若干簇，形成高效的數(shù)據(jù)傳輸網(wǎng)絡。仿真結果證明了算法能夠有效延長網(wǎng)絡的生存期和提高通信效率。

無線傳感器網(wǎng)絡；分簇；PSO算法；負載平衡

無線傳感器網(wǎng)絡(WSN)由大量體積微小的低功耗傳感器節(jié)點組成，隨機或者由人工部署在目標區(qū)域，具有能量資源和計算存儲資源受限的特點。因此在無線傳感器網(wǎng)絡中設計基于能量高效的分簇算法是一個關鍵的研究問題。

基于群智能優(yōu)化的分簇或路由算法，Iyengar等[1]探討了基于遺傳算法和基于蟻群算法的各種版本的衍生算法。Ducatelle等[2]對蟻群優(yōu)化算法在有線網(wǎng)絡和MANET中的可靠性和服務質(zhì)量路由進行了大量研究。Kuila等[3]從延長無線傳感器網(wǎng)絡生存期的角度出發(fā)，提出基于負載平衡的分簇和路由選擇模型，并設計了基于粒子群優(yōu)化算法的分簇算法。Guo等[4]針對無線傳感器網(wǎng)絡中最小能耗的分配問題提出JOPRA問題，設計出一種改進的自適應粒子群算法，將更多的網(wǎng)絡資源分配給連通條件更好的鏈路。Hamid等[5]通過多目標粒子群優(yōu)化算法提出一種多目標方案優(yōu)化分簇網(wǎng)絡中的簇頭數(shù)，降低了網(wǎng)絡能耗速率，以延長網(wǎng)絡生存期。

可以看出，現(xiàn)有研究在設計組網(wǎng)算法過程中并未充分考慮各節(jié)點的能耗均衡和數(shù)據(jù)傳輸效率，與其它智能優(yōu)化算法相比，粒子群算法具有更快的收斂速度和簡便的實現(xiàn)過程。因此，本文根據(jù)WSN內(nèi)部傳感器節(jié)點硬件資源和能量供應受限的特點，在充分考慮負載均衡、最優(yōu)能耗和數(shù)據(jù)傳輸效率的基礎上建立關于分簇方案的非線性規(guī)劃模型，并設計PSO算法求解該問題。

1　系統(tǒng)模型

1.1能量模型

無線通信的能耗模型是基于Heinzelman[6]研究成果。在模型中由通信距離決定使用自由空間或是多徑衰落信道。首先根據(jù)閾值d0，當收發(fā)距離小于給定閾值d0時，則基于自由空間建立能耗模型，否則采用多徑衰落模型。令Eelec表示節(jié)點中收發(fā)器發(fā)送一位數(shù)據(jù)的能耗，εfs、εmp分別表示處于自由空間或者多徑衰落信道的放大器發(fā)送一位數(shù)據(jù)的能耗。當距離為d時發(fā)送l-bit數(shù)據(jù)能耗為

(1)

接收l-bit能耗為

ER(l)=lEelec

(2)

式中，變量Eelec取決于多種因素比如數(shù)字編碼方案、調(diào)制、濾波和信號傳播發(fā)送;而放大器的能耗(εfs、εmp)只取決于發(fā)送距離和誤比特率。

1.2網(wǎng)絡模型

Dietrich等[7]介紹了網(wǎng)絡生存期的多種定義，本文選擇N-of-N運行期為網(wǎng)絡生存期定義，即從部署完成到第一個簇頭消亡這一時期為網(wǎng)絡生存期。網(wǎng)絡中每個成員節(jié)點只隸屬于一個簇頭。數(shù)據(jù)的收集分成若干輪次。每一輪次中，成員節(jié)點負責收集目標區(qū)域的監(jiān)測數(shù)據(jù)，并發(fā)送給對應的簇頭。簇頭節(jié)點對接收到的數(shù)據(jù)進行融合處理，把處理后的目標數(shù)據(jù)經(jīng)過多跳傳輸發(fā)送給其它簇頭，多跳通信的中繼任務由附近的簇頭承擔。兩個節(jié)點間存在無線通信鏈路的條件是它們都在對方通信范圍內(nèi)。

網(wǎng)絡部署分為三階段：引導加載階段，分簇形成階段，簇頭選擇階段。由于各節(jié)點中都配置GPS模塊，第一階段中節(jié)點根據(jù)GPS獲取各自坐標值，節(jié)點在網(wǎng)絡內(nèi)通過CSMA/CAMAC層協(xié)議廣播其坐標。因此，任一節(jié)點可以獲得通信范圍內(nèi)其它節(jié)點的位置信息，并通過多跳通信發(fā)送至基站。基站根據(jù)收集到數(shù)據(jù)執(zhí)行分簇算法，將網(wǎng)絡劃分成若干簇并選擇簇頭，為每個簇頭分配一個ID，此ID同時也表示對應簇的編號。經(jīng)過以上操作，所有節(jié)點均被安排給一個簇頭，每個簇頭記錄所轄成員信息。運行過程中，各簇頭提供一個TDMA時間表給本簇成員節(jié)點以完成簇內(nèi)通信。

2　組網(wǎng)模型

分簇的目標是最大化網(wǎng)絡生存期和提高網(wǎng)絡通信效率，在組網(wǎng)過程中不僅需考慮網(wǎng)絡的能量有效性和數(shù)據(jù)傳輸效率，也需考慮各節(jié)點能耗均衡。能耗均衡有兩層含義，首先是簇頭的負載平衡問題，當簇頭剩余能量相近時其所在分簇規(guī)模不能相差太大，避免出現(xiàn)某些簇頭管理過多的成員，而其余簇頭管理的成員過少，造成前者因能耗速率較大而很快消亡。其次最小化簇頭與本簇成員節(jié)點的距離方差，使所屬成員在與簇頭通信時的能耗不會出現(xiàn)較大的差異，有利于延長網(wǎng)絡的整體壽命。

2.1參數(shù)定義

S={s1,s2,s3,…,sN}：傳感器節(jié)點集合，N表示網(wǎng)絡內(nèi)節(jié)點總數(shù)；

ξ={g1,g2,g3,…,gM}：簇頭節(jié)點集合，M表示網(wǎng)絡中簇頭數(shù)目，等于分簇數(shù)；

dmax：傳感器節(jié)點最大通信距離；

dis(si,sj)：節(jié)點間距離；

NextHop(gi)：某簇頭通信范圍內(nèi)的其它簇頭集合；

ComCH(si)={gj|dis(si,gj)≤dmax∩gj∈ξ}：成員節(jié)點si通信范圍內(nèi)的簇頭集合；

Nmax、Nmin：每簇中成員數(shù)的上限和下限；

Nj：ID為j(1≤j≤M)的簇中成員節(jié)點數(shù)；

2.2網(wǎng)絡生存期

根據(jù)網(wǎng)絡生存期的定義，延長網(wǎng)絡的生存期可以通過延長具有最短壽命的簇頭節(jié)點生存期實現(xiàn)，即降低每一通信周期中剩余能量少的簇頭的能耗速率。簇頭能耗包括接收成員節(jié)點的感知數(shù)據(jù)，數(shù)據(jù)融合以及簇間通信。每個周期內(nèi)管理ni個成員節(jié)點的簇頭gi的能耗為

ECLUSTER(gi)=ni×ER+ni×EDA+ET(gi,NextHop(gi))

(3)

式中ER、EDA、ET分別是數(shù)據(jù)接收、數(shù)據(jù)融合、簇間通信能耗。

在一個多跳網(wǎng)絡中，除了存在簇內(nèi)信息傳輸，有時簇頭還需轉(zhuǎn)發(fā)來自于其它簇的分組。在計算簇頭作為中繼節(jié)點能耗前，首先計算gi收到的來自于其它簇的分組總數(shù)，

其他最終得出每個周期gi做為中繼節(jié)點需轉(zhuǎn)發(fā)NIN(gi)個分組，中繼能耗為

EFORWARD(gi)=NIN(gi)×ER+NIN(gi)×ET(gi,NextHop(gi))

(5)

因此，簇頭gi每個周期能耗可表示為

EG(gi)=EFORWARD(gi)+ECLISTER(gi)

=ni×ER+ni×EDA+ET(gi,NextHop(gi))+

NIN(gi)×ER+NIN(gi)×ET(gi,NextHop(gi))

(6)

令Eresidual(gi)表示gi的剩余能量，則gi的生存期可表示為

(7)

令L表示壽命最短的簇頭生存期，即L=min{L(j)|?i,1≤j≤M}，所以最大化網(wǎng)絡生存期可表示為

maxL=min{L(i)|?i,1≤i≤M}

(8)

2.3網(wǎng)絡通信效率

網(wǎng)絡運行過程中，簇頭不但對簇內(nèi)數(shù)據(jù)進行處理融合，而且負責簇間通信。本文研究的WSN網(wǎng)絡屬于Adhoc網(wǎng)絡，即網(wǎng)絡中所有節(jié)點無論簇頭還是成員節(jié)點的功能和硬件配置都是相同的，在實際運行中容易發(fā)生某個簇頭管理的成員節(jié)點過多而引起數(shù)據(jù)擁塞和通信延時的增加。因此為提高網(wǎng)絡的通信效率并且實現(xiàn)簇頭的負載平衡，對每個簇的分簇規(guī)模進行優(yōu)化。通過Var_load計算各簇的規(guī)模差異。

(9)

最大化網(wǎng)絡通信效率表示為

(10)

2.4簇內(nèi)平均距離

在分簇過程中可能出現(xiàn)為了節(jié)省簇頭能耗，某些成員節(jié)點被強制安排給較遠處的其它簇頭的情況。這樣的成員節(jié)點的通信能耗就會較大，因此在目標函數(shù)中也要考慮優(yōu)化成員節(jié)點能耗，即最小化成員節(jié)點和其簇頭的平均距離，表示為

(11)

AvegDist是成員節(jié)點和其所屬簇頭的平均距離。

結合方程(8)、(10)、(11)，得目標函數(shù)為

minObj=AvegDist×Var_load/L

(12)

s.t

(13)

(14)

Nmin≤Nj≤Nmax, j∈(0,M]

(15)

式(13)表示任意成員節(jié)點只能分配給一個簇頭。式(14)表示任意成員節(jié)點只能安排給位于其通信范圍內(nèi)的簇頭。式(15)規(guī)定每個簇的成簇規(guī)模。

3　基于粒子群算法的兩階段分簇組網(wǎng)算法

3.1初始組網(wǎng)方案

首先根據(jù)各網(wǎng)絡節(jié)點的位置坐標，將整個網(wǎng)絡區(qū)域直接按照面積劃分為M簇。網(wǎng)絡劃分成若干簇后，需要確定每個簇的簇頭。每個成員與對應簇頭通信時，根據(jù)能耗與傳輸距離成正比，為保證成員節(jié)點能耗均衡。簇頭與成員節(jié)點距離方差應最小。

(17)

式中：AvegDistj表示簇j中各成員與簇頭平均距離；Variancej表對應方差；(xj,yj)表示簇頭坐標；(xi,yi)表成員節(jié)點坐標。遍歷完本簇所有節(jié)點后選擇方差取值最小時對應的節(jié)點作為簇頭。

3.2基于PSO算法的組網(wǎng)優(yōu)化

PSO算法由一個預定義規(guī)模為(Np)的粒子群組成，每個粒子代表一個求解多維優(yōu)化問題的方案。所有粒子的維度都為D。每個粒子Pi(1≤ i≤ Np)有兩個參數(shù)，位置參數(shù)Xid(1≤ d≤ D)和速度參數(shù)Vid。種群中第i個粒子Pi用向量表示為

Pi=[Xi,1,Xi,2,Xi,3,...,Xi,D]

(18)

通過目標函數(shù)評估每個粒子對應的方案。粒子Pi根據(jù)個體最優(yōu)值(Pbesti)和種群全局最優(yōu)值(Gbest)更新自身的位置和速度。每次迭代中，粒子Pi通過以下方程更新位置參數(shù)和速度參數(shù)：

Vi,d(t)=w×Vi,d(t-1)+c1×r1×(Pbesti,d-Xi,d(t-1)+c2×r2×(Pbesti,d-Xi,d-Xi,d(t-1))

(19)

Xi,d(t)=Xi,d(t-1)+Vi,d(t)

(20)

式中：w為慣性權重；c1、c2為加速因子；r1、r2為[0,1]間的隨機數(shù)。粒子的更新過程被迭代多次，直到最終結果能夠接受或者達到預定的迭代次數(shù)。

3.2.1粒子初始化

粒子的維度等于網(wǎng)絡中傳感器節(jié)點總數(shù)N。種群的第i個粒子表示為Pi=[Yi,1,Yi,2,Yi,3,…,Yi,D]。粒子中的每維元素Yi,d(1≤ i≤ Np,1≤d≤N)表示傳感器節(jié)點sd被分配在第gk簇。初始化粒子時，首先結合3.1中所述的簇頭選擇方案并根據(jù)坐標將所有節(jié)點分成M簇，為各簇頭分配ID，取(0,1]范圍內(nèi)的隨機數(shù)初始化粒子的每一維元素。粒子Pi的元素Yi,d=Rand(0,1],l≤d≤N映射了成員節(jié)點sd從屬于哪個簇頭(假設為gk)。若sd被選做簇頭，則Yi,d等于0。映射方法為

gk=Index(ComCH(sd),n)

(21)

式中Index是索引函數(shù)，表示集合ComCH(sd)中的第n個元素被選中賦給gk。

n=Ceiling(Yi,d×|ComCH(sd)|)

(22)

3.2.2速度位置更新

通過方程(19)、(20)實現(xiàn)粒子位置和速度更新。注意到方程在迭代過程中可能會出現(xiàn)粒子中某些元素的取值非正或大于1。本文規(guī)定粒子的每個維度的元素取值范圍必須在(0,1]區(qū)間內(nèi)。因此，算法做出如下調(diào)整：

(1) 如果新的位置取值為負數(shù)或者0，則使用一個趨近于0的正數(shù)代替；

(2) 如果新的位置取值大于1，則用1代替。

每次迭代完成后，通過適應度函數(shù)Fitness評價粒子Pi，并根據(jù)最終結果決定是否更新個體最優(yōu)值Pbesti和全局最優(yōu)值Gbest。速度和位置被迭代更新直到滿足停止準則。本文的停止準則是一個預先定義的迭代次數(shù)。

4　仿真結果與分析

選定90m×50m的區(qū)域隨機拋撒無線傳感器節(jié)點，固定拋撒節(jié)點數(shù)為60，各節(jié)點坐標隨機生成。(εfs、εmp)的取值分別為10pJ/bit/m2和50nJ/bit。粒子群算法參數(shù)c1、c2取值為1.5，迭代次數(shù)為200，更新速度的最大值Vmax和最小值Vmin分別為0.1、-0.1。表1列出試驗中的網(wǎng)絡參數(shù)。

表1　網(wǎng)絡參數(shù)

圖1與圖2為拋撒節(jié)點數(shù)60，通信半徑30情況下網(wǎng)絡初始化后與經(jīng)過粒子群算法執(zhí)行200次迭代運算的組網(wǎng)效果。可以看出初始化后的組網(wǎng)結構圖，雖然簇頭節(jié)點互不相鄰，并且在目標區(qū)域分布較為均勻。但是各簇的成簇規(guī)模差異較大，衡量負載平衡的參數(shù)Var_load此處取值為5，每個通信輪次中成簇規(guī)模最大的簇頭能耗為1.7mJ。經(jīng)過優(yōu)化后的網(wǎng)絡中，參數(shù)Var_load取值為1，每個通信輪次中能耗最大的簇頭為1.2mJ，最小為0.9mJ。顯然經(jīng)過粒子群算法優(yōu)化后的組網(wǎng)方案，不僅保證了簇頭在網(wǎng)絡中均勻分布，而且各簇的成簇規(guī)模相近，較好地實現(xiàn)了簇頭的負載均衡。

圖1　初始化后的網(wǎng)絡結構圖

圖2　優(yōu)化后的網(wǎng)絡結構圖

圖3表示在拋撒節(jié)點數(shù)60，通信半徑30的情況下，算法迭代200次的收斂圖。可以看出算法迭代150次后即趨于收斂。

圖3　算法迭代200次的收斂圖

為研究算法的有效性，在不同種群規(guī)模下對運算結果進行比較。

表2　不同種群規(guī)模以及對應的目標函數(shù)值

通過以上數(shù)據(jù)可以看出，根據(jù)粒子群優(yōu)化算法的搜索結果所構造的無線傳感器網(wǎng)絡具有較好的能量有效性與通信效率。

5　結論

針對無線傳感器網(wǎng)絡中各節(jié)點具有嚴格的能量供應約束的特征，提出了一種基于PSO算法的能量有效分簇組網(wǎng)算法，根據(jù)節(jié)點能耗、負載平衡和最高通信效率等指標來選取簇頭，從而能夠顯著減少網(wǎng)絡中數(shù)據(jù)傳輸能耗，并提高通信效率，為網(wǎng)絡路由提供了合理的理論基礎。仿真結果從分簇算法的組網(wǎng)結果、算法的參數(shù)選擇、不同的網(wǎng)絡規(guī)模等方面說明了算法的有效性。

[1]S S Iyengar,H C Wu,N Balakrishnan,et al.Biologically inspired cooperative routing for wireless mobile sensor networks[J]. IEEE Systems Journal,2007,1(1):29-37.

[2]F Ducatelle,G A Di Caro,L Gambardella.Principles and applications of swarm intelligence for adaptive routing in telecommunications networks[J].Swarm Intelligence,2010,4(3):173-198.

[3]P Kuila,P K Jana.Energy efficient clustering and routing algorithms for wireless sensor networks:Particle swarm optimization approach[J].Engineering Applications of Artificial Intelligence,2014,33(8):127-140.

[4]S T Guo,C Y Dang,X F Liao.Joint opportunistic power and rate allocation for wireless ad hoc networks:An adaptive particle swarm optimization approach[J].Journal of Network and Computer Applications,2011,34(4):1353-1365.

[5]H Ali,W Shahzad,F A Khan.Energy-efficient clustering in mobile ad-hoc networks using multi-objective particle swarm optimization[J].Applied Soft Computing,2012,12(7):1913-1928.

[6]W B Heinzelman.Application specific protocol architecture for wireless microsensor networks[J].IEEE Transaction on Wireless Communications,2002,1(4):660-670.

[7]I Dietrich,F Dressler.On the Lifetime of Wireless Sensor Networks[J].ACM Transactions on Sensor Networks,2009,5(1):976-978.

(責任編輯：馬金發(fā))

Networking Method Based on PSO Algorithm in Wireless Sensor Network

GONG Hua,LU Hailong,YUAN Tian

(Shenyang Ligong University,Shenyang 110159,China)

A clustering network algorithm is proposed based on PSO algorithm for the feature with the limited power sources of wireless sensor network. The objective is to minimize transmission energy consumption,balance load among the cluster heads,tradeoff between transmission energy of the member nodes and the effective communication structure. The clustering algorithm begins with the base station,and broadcasts messages in the network. A two-stage network algorithm based on PSO algorithm can divide objective network into clusters in order to find a highly efficient communication network. The computational results show that the algorithm proposed in this paper can prolong the life time of the network and improve the efficiency of communication.

wireless sensor networks；clustering；PSO algorithm；load balancing

2015-07-14

國家自然科學基金資助項目(71101097)；遼寧省“百千萬人才工程”培養(yǎng)資助項目(2014921043)

宮華(1976—)女，教授，博士，研究方向：組合優(yōu)化、生產(chǎn)調(diào)度。

O224

A