程小博，尚家澤，安葳鵬，劉雨，劉志中

(河南理工大學(xué) 計算機科學(xué)與技術(shù)學(xué)院，河南 焦作 454000)

0 引 言

隨著物聯(lián)網(wǎng)技術(shù)的發(fā)展，將ZigBee技術(shù)應(yīng)用于物聯(lián)網(wǎng)逐漸成為研究熱點。ZigBee是一種短距離、低功耗的無線通信技術(shù)協(xié)議，并具有強大的自組網(wǎng)能力，已經(jīng)廣泛用于軍事、海洋等領(lǐng)域[1-3]。

ZigBee的拓?fù)錁渎酚伤惴ㄟm用于節(jié)點少、負(fù)載低的網(wǎng)絡(luò)，現(xiàn)有的物聯(lián)網(wǎng)中數(shù)據(jù)流會對ZigBee網(wǎng)絡(luò)產(chǎn)生較大的負(fù)載，增加網(wǎng)絡(luò)能耗，造成某條線路擁塞。為了解決ZigBee在組網(wǎng)過程中出現(xiàn)的路由節(jié)點過早死亡、網(wǎng)絡(luò)能耗高等問題，優(yōu)化路由路徑算法是解決問題的關(guān)鍵。ZigBee網(wǎng)絡(luò)中AODVjr算法在路由路徑發(fā)現(xiàn)期間需要大量轉(zhuǎn)發(fā)RREQ，從而容易形成網(wǎng)絡(luò)風(fēng)暴，造成網(wǎng)絡(luò)擁塞；Cluster-Tree路由算法基于分布式地址分配，易于實現(xiàn)。當(dāng)節(jié)點深度較高時，增加能耗，當(dāng)某些節(jié)點能量耗盡，容易引發(fā)癱瘓。錢志鴻等[4]設(shè)計AODVjr+Cluster-Tree混合算法，減少了網(wǎng)絡(luò)中的冗余分組，節(jié)點深度低時選擇AODVjr算法，節(jié)點深度高時選擇Cluster-Tree算法，兩種算法的弊端仍然存在；WANG Xin等[5]采用GA-PSO算法,并提出了簇首輪換競爭機制，減少了網(wǎng)絡(luò)時延，但后期由于某些節(jié)點死亡，增大了節(jié)點間距，后期節(jié)點平均能耗增加；魏文紅等[6]采用多目標(biāo)進(jìn)化算法，把路由代價和網(wǎng)絡(luò)生存時間作為優(yōu)化目標(biāo)，提出變異，交叉和選擇策略，提高了數(shù)據(jù)包傳輸速率并降低了網(wǎng)絡(luò)能耗；M.U.Ruihui等[7]綜合考慮了路由傳輸距離和節(jié)點剩余能量2個因素，提出了網(wǎng)絡(luò)動態(tài)分簇路由協(xié)議；孫彥清等[8]為了解決路由的頻繁發(fā)現(xiàn)，提出了基于ACO和AODV的優(yōu)化算法，有效地降低了網(wǎng)絡(luò)時延，但是并沒有解決網(wǎng)絡(luò)能量均衡的問題。

本文在以上學(xué)者研究的基礎(chǔ)上，采用了分區(qū)成簇路由協(xié)議，提出了用融合差分粒子群優(yōu)化算法(DE-PSO)[9]，考慮網(wǎng)絡(luò)節(jié)點剩余能量和節(jié)點密集程度，采用簇首輪換機制并設(shè)置簇首能量最低閾值以減少節(jié)點死亡率。通信過程中，如果路由表中沒有最佳路由選擇，多目標(biāo)進(jìn)化算法對多路徑進(jìn)行搜索，由于差分進(jìn)化算法具有復(fù)雜的變異，交叉和選擇操作，尋找全局最優(yōu)解時收斂速度具有局限性，利用PSO算法的良好收斂性和高搜索精度性快速找出最優(yōu)路徑。

1 ZigBee組網(wǎng)路由簇首競選機制

在ZigBee網(wǎng)絡(luò)中實施簇首輪換機制可以有效地減少網(wǎng)絡(luò)能耗，延長網(wǎng)絡(luò)壽命，保證網(wǎng)絡(luò)結(jié)構(gòu)的完整性。在節(jié)點間的通信過程中，快速找到一條最佳路徑，提高網(wǎng)絡(luò)的整體性能。吳三柱等[10]提出新的路由算法IGPSR-2,將區(qū)域劃分為4個子區(qū)域，然后利用節(jié)點能量方差選擇路徑，提高了路徑的搜索效率，增加了網(wǎng)絡(luò)負(fù)載；LI Xiaofang等[11]利用差分進(jìn)化算法的全局搜索能力，可以彌補ADOVjr算法的不足，但因具有一定的局限性，且收斂速度較慢，增加了節(jié)點間的通信時間；G.Cavazzini等[12]利用粒子群算法加快了路徑搜尋過程中的收斂速度，但很容易陷入局部最優(yōu)。

針對以上原因，本文在ZigBee網(wǎng)絡(luò)節(jié)點通信過程中，利用融合差分粒子群優(yōu)化算法，有效降低網(wǎng)絡(luò)路徑消耗和減少節(jié)點死亡。當(dāng)網(wǎng)絡(luò)中樹簇型網(wǎng)絡(luò)結(jié)構(gòu)確定時，如果路由表中有一條最佳路徑則按照最佳路徑進(jìn)行通信，反之，則采用DE算法在全路徑中按照設(shè)置好的參數(shù)進(jìn)行搜索，然后利用PSO算法的快速收斂性，彌補差分算法時延大的缺陷，最終提高路由路徑的搜索能力。

(1)所有節(jié)點隨機分布在邊長為L的正方形區(qū)域中，節(jié)點所處位置信息未知。節(jié)點可以根據(jù)發(fā)送信號強弱(RSSI)估算節(jié)點間距。

(2)各節(jié)點均有相互獨立的ID并可成為簇首。簇首可發(fā)送信息至各節(jié)點。

1.1 簇頭競選機制算法

在ZigBee網(wǎng)絡(luò)中，隨著網(wǎng)絡(luò)深度的增加，網(wǎng)絡(luò)能量負(fù)載增大，簇首需要轉(zhuǎn)發(fā)各子節(jié)點消息，并與其他簇首進(jìn)行通信，能量消耗大，導(dǎo)致簇首過早死亡、節(jié)點分布不均，因此,應(yīng)盡量選取節(jié)點密集區(qū)域中能量較大的節(jié)點為簇首。由于距離sink節(jié)點近的節(jié)點轉(zhuǎn)發(fā)數(shù)據(jù)包數(shù)量大，距離sink節(jié)點遠(yuǎn)的節(jié)點轉(zhuǎn)發(fā)數(shù)據(jù)包數(shù)量小。為均衡網(wǎng)絡(luò)能耗并減小網(wǎng)絡(luò)開銷，本文根據(jù)節(jié)點跳數(shù)為簇首規(guī)定選舉半徑，距離sink節(jié)點越近，分配節(jié)點跳數(shù)越小，競爭半徑也越小。簇分布如圖1所示。

由于節(jié)點位置未知，節(jié)點根據(jù)發(fā)送信號強度(RSSI)作為簇首競爭半徑，簇首競爭半徑

R=RSSIr(1-1/hopmin)，

(1)

式中：RSSIr為節(jié)點通訊半徑R處的信號強度；hopmin為節(jié)點距離sink節(jié)點的最短跳數(shù)。

定義當(dāng)節(jié)點與簇首候選節(jié)點之間的信號強度大于R時，則認(rèn)定該節(jié)點位于簇首候選節(jié)點的通信半徑之內(nèi)。

文獻(xiàn)[10]提出了節(jié)點i的消耗功率Pi等于節(jié)點接收功率和發(fā)射功率之和，即

圖1 簇分布示意圖Fig.1 Cluster distribution diagram

式中：εij為節(jié)點i到j(luò)的單位數(shù)據(jù)傳輸消耗功率；k為數(shù)據(jù)包大??；fij為節(jié)點傳輸速率；ξ為無線接收器的能量消耗；ni為所有節(jié)點N中第i個節(jié)點。

為減少簇首選舉過程中能耗開銷，需要綜合考慮節(jié)點數(shù)據(jù)傳輸?shù)南墓β蔖i、競爭半徑內(nèi)鄰居節(jié)點的剩余能量Ej、競爭半徑內(nèi)節(jié)點密度ρ1等對節(jié)點存活數(shù)量與所有節(jié)點的占比，具體為

(3)

式中：W為競選簇首的權(quán)重值；Ei為當(dāng)前節(jié)點的剩余能量；α+β+γ=1；D為競爭半徑內(nèi)鄰居節(jié)點的數(shù)量；Pi為節(jié)點傳輸功率；ρ1為競爭半徑內(nèi)節(jié)點密度；ρ為節(jié)點存活數(shù)量與所有節(jié)點的占比。簇首通過比較當(dāng)前節(jié)點i的權(quán)重值選取。

2 DE-PSO算法設(shè)計

本文融合進(jìn)化算法的全局最優(yōu)搜索能力和粒子群算法的快速收斂性，設(shè)計DE-PSO算法，解決ZigBee組網(wǎng)搜索最佳路由路徑過程中所存在的問題，將2種算法的優(yōu)點運用到最佳路由的選擇過程中，采用融合差分進(jìn)化離子群優(yōu)化算法，改善網(wǎng)絡(luò)最佳路徑的搜索能力，當(dāng)網(wǎng)絡(luò)在分層結(jié)構(gòu)中，如果路由表存在最佳路由，則按照最佳路由進(jìn)行通信，反之，利用進(jìn)化算法全局最佳搜索能力在所有路徑中，按照設(shè)置參數(shù)尋找較優(yōu)路徑，然后利用粒子群算法的快速收斂性對較優(yōu)路徑進(jìn)行優(yōu)化，最后達(dá)到快速搜索最優(yōu)路徑的目的。

2.1 路徑編碼

路由路徑是由源地址到目的地址的所有路徑組成的，每條路徑代表一個元素，則所有路徑所構(gòu)成的集合就是差分算法的群，由于每條路徑的長度都是不同的，可以先對每條路徑進(jìn)行編碼，每個編碼代表一個粒子，假定編碼為xi。

2.2 基本差分進(jìn)化算法

差分進(jìn)化算法具有變異、交叉和選擇過程。首先，在父代個體間根據(jù)差分矢量生成隨機變異個體；其次，在父代個體和新生成個體間進(jìn)行交叉操作；最后，在父代個體和新生成個體間根據(jù)適應(yīng)值大小進(jìn)行選擇操作，從而得到新一代個體?？紤]端到端的能量消耗和時延，適應(yīng)值函數(shù)為

f=a/ti+b/Ei，

(4)

式中，a和b分別為適應(yīng)值函數(shù)根據(jù)時延和所需能量所設(shè)置的調(diào)整參數(shù)，滿足a+b=1。

2.2.1 變異操作

變異操作是在所有路徑當(dāng)中隨機選取某條路徑作為基向量，以另外2個不同路徑作為差分向量，變異公式為

DE/rand/1

Vi，g=xi1，g+F×(xi2，g-xi3，g)，

(5)

DE/best/2

Vi，g=xbest，g+F×(xr1，g-xr2，g),

(6)

DE/rand-to-best/3

Vi，g=xr1，g+F×(xbest，g-xr1，g)+

F×(xr2，g-xr3，g),

(7)

其中，F(xiàn)為縮放因子

F=Δf(xi)/[λ+(f(xworst)-f(xbest))]×

(Fmax-Fmin)+Fmin，

(8)

式中：xi1,g,xi2,g,xi3,g為隨機選取互不相同的3條路徑；xbest，g為當(dāng)前種群中的最優(yōu)個體；λ=10-14是防止選取路徑最優(yōu)時分母為0。

F的作用是對選出的路徑向量進(jìn)行縮放，由式(8)可得，當(dāng)選取的路徑較優(yōu)時，希望繼續(xù)利用該條路徑信息，即需要較小的F因子，此時，f(xworst)-f(xbest)=Δf(xi)→0成立，即F→Fmin，反之，f(xworst)-f(xbest)=Δf(xi)→+∞，F(xiàn)→Fmax。

2.2.2 交叉操作

此過程是在父代個體xi，j，g與變異個體Vi，j，g間進(jìn)行，其中，CR為交叉率。操作如式(9)和圖1所示。

由節(jié)點i→j的2條路徑x1和x2，其中n1,n2分別為2條路徑中的中間節(jié)點，交叉過程中，由i→n1→j和i→n2→j的2條路徑中，n1和n2進(jìn)行交叉，生成2條全新的路徑。

圖2 路徑交叉過程Fig.2 Path crossing process

2.2.3 選擇操作

選擇操作是在父代個體與子代個體間完成的選擇，選擇的過程是以適應(yīng)值為標(biāo)準(zhǔn)，公式為

(10)

式中：xi，j，g為產(chǎn)生下一代路徑中的第i條路徑；f為適應(yīng)值函數(shù)；U為實驗體的總量；V為變異產(chǎn)生的新個體；i為第i個粒子數(shù)；j為方向矢量；rand函數(shù)表示在[0，1]之間產(chǎn)生均勻分布的隨機數(shù)。

綜上所述，融合算法的步驟如下。

(1)系統(tǒng)重啟時初始化網(wǎng)絡(luò)節(jié)點并對網(wǎng)絡(luò)節(jié)點能量進(jìn)行層次劃分，如果能量小于最低能量閾值，則發(fā)送簇首競爭信息進(jìn)行簇首競爭輪換。

(2)在ZigBee網(wǎng)絡(luò)通信中，如果需要尋找由源節(jié)點到目的節(jié)點的最佳路由，則設(shè)置DE參數(shù)，初始種群為源節(jié)點到目的節(jié)點的所有路徑集合N，節(jié)點可以根據(jù)發(fā)送信息能量強弱感知目的節(jié)點深度，對路徑進(jìn)行變異、交叉和選擇操作。

(3)變異操作：差分進(jìn)化算法變異操作是按照路徑距離矢量完成的。首先，在N條路徑中隨機選擇3條路徑，分別為x1，x2，x3，對于x1，以概率p1隨機選擇路徑過程的中間節(jié)點，假設(shè)為ni；其次，沿著x2方向，從目標(biāo)節(jié)點到源節(jié)點查找相同節(jié)點ni。如果找到節(jié)點ni，則把x2中從ni到目的節(jié)點的這段路徑與x2中從ni到目的結(jié)點的路徑進(jìn)行交換；如果沒有找到中間節(jié)點ni，則重復(fù)此過程直至找到為止，經(jīng)過變異以后，x1和x2就變成了2條新的路徑。同樣以x3路徑進(jìn)行此操作，經(jīng)過2次變異，則x1，x2，x3就變成了3條全新的路徑。

(4)交叉策略：以概率p2隨機在路徑中選擇2條路徑x1,x2，然后從x1,x2中選擇2個中間節(jié)點ni和nj，為起始點交換路徑，如果在路徑x1,x2中沒有找到節(jié)點ni,nj，則持續(xù)進(jìn)行此操作。

(5)選擇操作：當(dāng)產(chǎn)生新的子代個體支配父代個體時，子代個體代替父代個體，如果父代個體支配子代個體則丟棄子代個體。如果子代和父代個體間無支配關(guān)系，則父代個體和子代個體同時存檔。引入適應(yīng)值函數(shù)，計算各條路徑的適應(yīng)值，并按照適應(yīng)值大小對較優(yōu)路徑進(jìn)行排列。

(6)設(shè)置PSO參數(shù)，從上述操作中根據(jù)適應(yīng)值大小和種群密度，選出路徑當(dāng)中前10%的路徑進(jìn)行優(yōu)化，根據(jù)PSO算法,對這些選出的粒子執(zhí)行粒子群優(yōu)化操作，選出最優(yōu)路徑。

DE-PSO融合算法具體流程如圖3所示。

圖3 DE-PSO融合算法流程圖Fig.3 DE-PSO fusion algorithm flow

步驟(3)、(4)中交叉和變異概率公式為

(12)

式中：fbig為交叉?zhèn)€體中最大適應(yīng)度；fbig為平均適應(yīng)度；fmax為最大適應(yīng)值。

考慮交叉和變異的不確定性，控制其概率為較小值，設(shè)置控制系數(shù)k1=0.8；k2=0.5；k3=0.06；k4=0.6。

在步驟(6)中，根據(jù)適應(yīng)值篩選出10%的個體數(shù)目假設(shè)為M，則此M個粒子作為粒子群算法當(dāng)中的M個個體，根據(jù)PSO算法在q維空間當(dāng)中飛行搜索，為了提高搜索精度，設(shè)定粒子初始位置Xid(0)，vid限制在(-0.1，0.1)間，具體由式(13)和(14)產(chǎn)生：

(14)

式中,r1,r2為(0，1)間的隨機數(shù)。

速度和位置的更新公式見式(15)和(16)。

(16)

(17)

式中,D(k)為種群多樣性，D(k)值越小，粒子間差異越小，多樣性也越小，根據(jù)D(k)大小選出全局最優(yōu)路徑。

3 仿真與結(jié)果分析

為合理分析傳輸時網(wǎng)絡(luò)的節(jié)點生存數(shù)量和平均剩余能量以及能耗，參照文獻(xiàn)[13]中節(jié)點參數(shù)設(shè)置，普通節(jié)點通信距離為r=30，簇首通信半徑R=2r，本文仿真設(shè)置場景參數(shù)如表1所示。

表1 仿真場景參數(shù)Tab.1 Simulation scene parameters

進(jìn)行粒子群算法時，公式(15)系數(shù)ξ∈[0，1]中的隨機數(shù)，c1=c2=1。仿真時每分鐘統(tǒng)計一次節(jié)點死亡數(shù)量和全網(wǎng)剩余平均能耗，死亡節(jié)點對比如圖4所示，剩余平均能量對比如圖5所示，端到端時延如圖6所示。

由圖4可以看出，隨著時間的增加，節(jié)點死亡量逐步遞增，DE-PSO算法節(jié)點等時死亡數(shù)量明顯低于改進(jìn)的AODVjr算法、DE算法和ACO-AODV算法，且在60 min以后更為明顯，主要原因是節(jié)點最低閾值前期保護(hù)了節(jié)點死亡，90 min后DE-PSO算法等時節(jié)點死亡數(shù)量明顯增多，主要是全網(wǎng)節(jié)點能量偏低，死亡率攀升。但在整個過程中，DE-PSO算法明顯延緩節(jié)點的死亡時間，且節(jié)點等時死亡率低于AODVjr算法、ACO-AODV算法和DE算法。這也驗證了DE-PSO算法在延緩節(jié)點死亡上有明顯的改進(jìn)效果。

圖4 不同算法死亡節(jié)點數(shù)對比Fig.4 Comparison of the number of dead nodes

圖5 不同算法剩余平均能量對比fig.5 Residual average energy comparison

圖6 不同算法端到端時延對比Fig.6 End-to-end delay comparison

圖5是4種算法節(jié)點剩余能量的平均值對比，由仿真結(jié)果可以看出，基于分簇的DE-PSO算法，節(jié)點間剩余能量等時平均值均高于AODVjr算法、DE算法和ACO-AODV算法的，且DE-PSO算法平均能量曲線下滑平緩，在實驗過程中能量均衡性高于DE算法、AODVjr算法和ACO-AODV算法，由此可以證明,DE-PSO算法在減少能量損耗和平衡節(jié)點間能量上比DE算法、AODVjr算法和ACO-AODV算法有更好的效果。

圖6可以看出，從源節(jié)點到目的節(jié)點的時間延遲方面，DE-PSO略高于ACO-AODV算法，這是由于綜合考慮了節(jié)點數(shù)據(jù)傳輸?shù)南墓β蔖i、競爭半徑內(nèi)鄰居節(jié)點的剩余能量Ej、競爭半徑內(nèi)節(jié)點密度ρ1時增加了時延，明顯低于ADOVjr算法和DE算法，在70 min以后DE算法在迭代次數(shù)增多時，種群多樣性變小，過早陷入局部最優(yōu)，導(dǎo)致時延明顯升高。仿真結(jié)果表明，端到端時延基本滿足實驗要求。

4 結(jié) 論

首先，對ZigBee節(jié)點間引入簇頭競爭機制，且在競爭過程中設(shè)置了節(jié)點競爭簇首時的競爭半徑，根據(jù)競爭半徑中鄰居節(jié)點的權(quán)重值選取簇首，在犧牲一定時延的情況下，有效地減小節(jié)點間的能量損耗，在節(jié)點能量均衡上也有很大改善。其次，在搜索最佳路徑時，通過動態(tài)調(diào)整交叉和變異概率，利用路徑交叉、變異和選擇策略篩選較優(yōu)路徑。最后，利用粒子群算法的良好收斂性，提高路徑選擇過程中的收斂速度。仿真驗證了DE-PSO算法在優(yōu)化節(jié)點死亡，減少節(jié)點能量上均有較大改進(jìn)，表明其可以滿足監(jiān)測系統(tǒng)的需求，下一步研究DE-PSO算法在網(wǎng)路節(jié)點增多和覆蓋面積增大時，是否能保持其優(yōu)勢并推廣到大型復(fù)雜環(huán)境。