基于改進(jìn)的AP和遺傳算法的能量感知分簇路由協(xié)議

胡黃水, 姚美琴, 王 亮, 韓優(yōu)佳

(1. 長(zhǎng)春工業(yè)大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院, 長(zhǎng)春, 130012； 2. 吉林建筑科技學(xué)院 計(jì)算機(jī)科學(xué)與工程學(xué)院, 長(zhǎng)春 130114)

無(wú)線傳感器網(wǎng)絡(luò)(WSN)作為物聯(lián)網(wǎng)(IoT)不可或缺的一部分, 近年來(lái)發(fā)展迅速[1-4]. 無(wú)線傳感器網(wǎng)絡(luò)是由多個(gè)節(jié)點(diǎn)聚集在一起, 將其收集的數(shù)據(jù)相互傳輸?shù)交?BS)所形成的網(wǎng)絡(luò)結(jié)構(gòu)[5-9]. 由于無(wú)線傳感器節(jié)點(diǎn)能量受限, 所以節(jié)能是延長(zhǎng)無(wú)線傳感器網(wǎng)絡(luò)壽命的關(guān)鍵因素[10]. 研究表明, 將節(jié)點(diǎn)分成不同的簇以最大限度地延長(zhǎng)無(wú)線傳感器網(wǎng)絡(luò)的使用壽命是節(jié)能和可擴(kuò)展的[11-15]. 因此, 在基于簇的協(xié)議中, 所有傳感器節(jié)點(diǎn)都根據(jù)某些特定規(guī)則劃分為不同的簇.

低能量自適應(yīng)聚類層次結(jié)構(gòu)(LEACH)[16]是最具代表性的層次成簇算法之一, 其隨機(jī)選擇一個(gè)節(jié)點(diǎn)作為簇頭(CH), 但這可能使一些剩余能量低或距離BS較遠(yuǎn)的節(jié)點(diǎn)被選為CH. LEACH-C(LEACH-centralized protocol)是一種集中式協(xié)議[17], 其中所有決策(如CH選擇、簇形成以及向網(wǎng)絡(luò)中的信息分發(fā))均由BS執(zhí)行. LEACH-C的穩(wěn)定階段與LEACH協(xié)議相同. 在穩(wěn)定階段, 最初每個(gè)傳感器節(jié)點(diǎn)都互相發(fā)送其位置(由全球定位系統(tǒng)(GPS)接收器確定)以及在每輪中向BS發(fā)送剩余能量信息. BS計(jì)算網(wǎng)絡(luò)的平均剩余能量, 當(dāng)節(jié)點(diǎn)的剩余能量小于平均剩余能量時(shí), 節(jié)點(diǎn)被禁止參與當(dāng)前回合的CH選擇過(guò)程[18-19]. 但該算法每個(gè)節(jié)點(diǎn)都需要配備GPS, 增加了成本開(kāi)銷. 文獻(xiàn)[20]提出了一種能量均衡的分簇算法, 在選取CH節(jié)點(diǎn)時(shí)引入剩余能量作為參考因素, 能均衡網(wǎng)絡(luò)能量消耗, 但其CH位置選取方式與LEACH類似, 導(dǎo)致CH分布不均勻[21]. 不合理的CH個(gè)數(shù)及初始CH位置會(huì)對(duì)成簇結(jié)果產(chǎn)生較大影響, 導(dǎo)致節(jié)點(diǎn)之間的能耗不均勻, 進(jìn)而降低網(wǎng)絡(luò)性能. 文獻(xiàn)[22]對(duì)K-means++算法進(jìn)行改進(jìn), 提出了一種無(wú)線傳感器網(wǎng)絡(luò)能量高效分簇協(xié)議KEECS, 該協(xié)議在簇的建立階段基于K-means++成簇算法進(jìn)行分簇, 并在簇首選舉過(guò)程中考慮了節(jié)點(diǎn)的剩余能量和CH的地理位置, 但基于K-means算法選舉CH時(shí)最優(yōu)簇?cái)?shù)不易確定. 因此文獻(xiàn)[23]先引入了近鄰傳播算法(AP)計(jì)算初始聚類中心, 然后采用K-medods算法對(duì)聚類結(jié)果進(jìn)行進(jìn)一步優(yōu)化, 不需事先確定最優(yōu)簇?cái)?shù), 但成簇時(shí)未考慮節(jié)點(diǎn)中心度等因素. 上述算法均未考慮路由問(wèn)題, 所以針對(duì)上述WSN成簇存在的問(wèn)題, 本文提出一種基于AP算法改進(jìn)的CH選舉算法, AP算法不需要預(yù)先給定CH數(shù)目, 選舉初始成簇中心時(shí)是存在的節(jié)點(diǎn)而不是虛擬的節(jié)點(diǎn), 且可以自動(dòng)確定CH及CH個(gè)數(shù). 結(jié)合AP算法和遺傳算法的分簇路由協(xié)議(EAPGA)基于AP算法選舉CH時(shí)考慮了節(jié)點(diǎn)的剩余能量、節(jié)點(diǎn)中心度、節(jié)點(diǎn)間距、節(jié)點(diǎn)到BS的距離, 且路由階段采用考慮CH能耗的遺傳算法作為適應(yīng)度函數(shù), 經(jīng)仿真結(jié)果驗(yàn)證, EAPGA協(xié)議選擇了更合理的CH和最優(yōu)路徑, 減少了節(jié)點(diǎn)的能量消耗, 有效延長(zhǎng)了網(wǎng)絡(luò)生命周期.

1 能量模型

當(dāng)節(jié)點(diǎn)間距離為d時(shí), 傳感器節(jié)點(diǎn)發(fā)送Lbit數(shù)據(jù)的能量消耗為

ETx(L,d)=Eelec×L+εamp×L,

(1)

其中:Eelec表示在兩個(gè)傳感器之間傳輸1 bit數(shù)據(jù)消耗的能量;εamp表示放大器的能量消耗, 計(jì)算公式為

(2)

式中εfs表示自由空間模型的能量消耗,εmp表示多徑衰落模型的能量消耗,d0為放大器的閾值, 計(jì)算公式為

(3)

傳感器接收Lbit數(shù)據(jù)時(shí)消耗的能量為

ERx(L)=Eelec×L.

(4)

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

本文提出的EAPGA協(xié)議在監(jiān)視區(qū)域中隨機(jī)部署n個(gè)傳感器節(jié)點(diǎn), 并做下列假設(shè)：

1) 所有節(jié)點(diǎn)都同構(gòu), 能量有限, 并且每個(gè)節(jié)點(diǎn)都具有唯一標(biāo)識(shí)符(ID), 但BS的能量無(wú)限；

2) 所有節(jié)點(diǎn)都可感知其剩余能量和位置；

3) 從睡眠狀態(tài)更改為工作狀態(tài)時(shí), 節(jié)點(diǎn)消耗的能量相同.

3 成簇階段

步驟1) 計(jì)算WSN中節(jié)點(diǎn)X={x1,x2,…,xn}間的相似度矩陣:

(5)

其中Enow為節(jié)點(diǎn)當(dāng)前能量,Einit為節(jié)點(diǎn)初始能量,di,k為節(jié)點(diǎn)i與節(jié)點(diǎn)k之間的距離,di,BS為節(jié)點(diǎn)i到BS的距離,s(i,k)初始化為0.

步驟2) 更新WSN中節(jié)點(diǎn)X={x1,x2,…,xn}之間的吸引力矩陣：

(6)

其中:Ci為節(jié)點(diǎn)中心度, 節(jié)點(diǎn)距離鄰居節(jié)點(diǎn)的平均最短距離越小, 節(jié)點(diǎn)中心度值越高, 說(shuō)明節(jié)點(diǎn)在該區(qū)域中越重要;Ni為節(jié)點(diǎn)i的鄰居節(jié)點(diǎn)數(shù)量;Sarea為計(jì)算的傳感區(qū)域的面積. 式(6)考慮了節(jié)點(diǎn)剩余能量和節(jié)點(diǎn)中心度. 剩余能量越少, 地理位置越偏僻的節(jié)點(diǎn)則成為CH的可能性越低,r(i,k)初始化為0.

步驟3) 更新WSN中節(jié)點(diǎn)X={x1,x2,…,xn}之間的歸屬度矩陣：

(7)

a(i,k)初始化為0.

步驟4) 通過(guò)對(duì)節(jié)點(diǎn)的吸引度信息和歸屬度信息求和, 確定節(jié)點(diǎn)選取的聚類中心:

(8)

其中, 若i=k, 則節(jié)點(diǎn)i自身是CH； 若i≠k, 則節(jié)點(diǎn)k是節(jié)點(diǎn)i的CH.

4 尋路階段

在本文網(wǎng)絡(luò)中采用改進(jìn)遺傳算法為每個(gè)信道尋找最優(yōu)的路由路徑, 傳統(tǒng)遺傳算法由于具有選擇、交叉、變異等隨機(jī)操作, 可能產(chǎn)生無(wú)效個(gè)體. 因此在EAPGA中, 為產(chǎn)生合適的基因并避免無(wú)效個(gè)體及提高收斂速度給出一個(gè)約束條件.

4.1 構(gòu)建適應(yīng)度函數(shù)

為使網(wǎng)絡(luò)壽命最大化, 必須盡可能減少每個(gè)CH的能耗. 因此, 能量消耗偏差是適應(yīng)度函數(shù)的一個(gè)影響因子. 本文構(gòu)建如下適應(yīng)度函數(shù)：

(9)

其中ECHS表示所有路由路徑中CH的能耗偏差, 計(jì)算公式為

(10)

式中hi表示第i個(gè)CH,nCH表示CH的個(gè)數(shù),Ehi表示簇頭hi的能耗. 因此, 適應(yīng)度函數(shù)的值越大, 其個(gè)體質(zhì)量越好, 越有可能傳給下一代.

4.2 初始化種群

在EAPGA中, 實(shí)數(shù)編碼用于表示群體的染色體. 染色體是指由CH的ID和BS的ID所表示基因組成的個(gè)體. 染色體的特定基因指示對(duì)應(yīng)CH的下一跳CH, 如圖1所示.

假設(shè)從有100個(gè)節(jié)點(diǎn)的網(wǎng)絡(luò)中選擇10個(gè)CH, 其ID分別為5,20,33,45,49,52,73,76,81,97. 從染色體上可見(jiàn), CH97的路由路徑為97→5→76→33→101(BS). 每個(gè)基因gi隨機(jī)產(chǎn)生, 但要滿足各自的約束條件gi∈CHhi, CHhi是簇頭hi的候選下一跳CH的集合. CHhi集合由位于hi的通信范圍內(nèi)且其下一跳距離BS更近的CH構(gòu)成. 因此可避免產(chǎn)生無(wú)效染色體, 減小迭代次數(shù). 圖2為傳統(tǒng)遺傳算法產(chǎn)生的無(wú)效染色體. 例如, CH49號(hào)基因不在CH5號(hào)基因的通信范圍內(nèi)； CH73號(hào)基因雖然在CH81號(hào)基因的通信范圍內(nèi), 但CH73號(hào)基因與BS的距離大于CH81號(hào)基因與BS的距離, 使鏈路產(chǎn)生回路20→73→81→73.

圖1 EAPGA的有效染色體Fig.1 Effective chromosome of EAPGA

圖2 EAPGA的無(wú)效染色體Fig.2 Invalid chromosome of EAPGA

4.3 產(chǎn)生下一代種群

計(jì)算初始種群中每個(gè)染色體的適應(yīng)度函數(shù)值, 并按降序排列. 適應(yīng)度函數(shù)值越大, 個(gè)體越接近最優(yōu)解. 選擇操作采用精英選擇法, 選擇最優(yōu)個(gè)體直接遺傳給下一代群體. 對(duì)于其他染色體, 每個(gè)染色體都決定其適應(yīng)度函數(shù)值是否大于隨機(jī)生成的有效個(gè)體的適應(yīng)度函數(shù)值. 如果大于, 則選擇其進(jìn)行交叉操作; 否則, 選擇隨機(jī)的進(jìn)行交叉操作, 以加速收斂, 并確保種群的多樣性.

單點(diǎn)雜交用于選定的個(gè)體產(chǎn)生新的后代. 計(jì)算每個(gè)子對(duì)象的適應(yīng)度函數(shù)值, 與父對(duì)象進(jìn)行比較. 如果其值大于其父代的值, 則選擇該值進(jìn)行變異操作. 或者使用隨機(jī)生成的個(gè)體確定其適應(yīng)度函數(shù)值是否大于父對(duì)象的適應(yīng)度函數(shù)值. 如果是, 則選擇隨機(jī)個(gè)體進(jìn)行變異操作; 否則選擇父?jìng)€(gè)體, 進(jìn)一步加快收斂速度. 將這些新個(gè)體和精英個(gè)體相結(jié)合, 產(chǎn)生下一代種群.

4.4 尋找最優(yōu)路徑

在滿足下列終止條件之一的情況下, EAPGA能找到最佳路由路徑：

1) 預(yù)先設(shè)定的迭代次數(shù)；

2) 適應(yīng)度函數(shù)值的偏差度, 用公式表示為

(11)

其中Fi表示個(gè)體i的適應(yīng)度函數(shù)值,Fmax表示最大適應(yīng)度函數(shù)值,ε為一個(gè)小正數(shù), 本文取ε=10-3. 從總體中選擇適應(yīng)度函數(shù)值最大的個(gè)體, 給出每個(gè)信道的最優(yōu)路由路徑.

5 仿真分析

本文將EAPGA和LEACH[13],LEACH-C[14]，APSA[20]協(xié)議進(jìn)行對(duì)比仿真. 模擬一個(gè)規(guī)模為100 m×100 m的無(wú)線傳感器網(wǎng)絡(luò), 節(jié)點(diǎn)總數(shù)為100, BS位于該區(qū)域的中心. 仿真參數(shù)如下： 初始能量為0.5 J,Eelec=50 nJ/bit,εfs=10 pJ/(bit·m-2),εmp=0.001 3 pJ/(bit·m-4), 數(shù)據(jù)包為1 000 bit, 控制包為25 bit, 節(jié)點(diǎn)數(shù)為100, 交叉率為0.65, 變異率為0.1, 種群數(shù)量為100.

5.1 網(wǎng)絡(luò)剩余能量

由于每個(gè)節(jié)點(diǎn)的能量有限, 網(wǎng)絡(luò)生命周期可能會(huì)由于某些節(jié)點(diǎn)的耗盡而下降. 因此, 本文考慮了節(jié)點(diǎn)的能量、位置和數(shù)據(jù)傳輸?shù)哪芰肯? 對(duì)LEACH,LEACH-C,APSA和EAPGA協(xié)議進(jìn)行了網(wǎng)絡(luò)總節(jié)點(diǎn)剩余能量的仿真分析, 結(jié)果如圖3所示. 由圖3可見(jiàn), 在相同仿真環(huán)境下, 網(wǎng)絡(luò)運(yùn)行期間EAPGA協(xié)議中節(jié)點(diǎn)的總剩余能量分別高于LEACH,LEACH-C和APSA協(xié)議. 因?yàn)镋APGA協(xié)議考慮了節(jié)點(diǎn)間的位置關(guān)系完成成簇, 可有效降低節(jié)點(diǎn)和CH傳輸?shù)哪芰肯? 并將節(jié)點(diǎn)的剩余能量作為成簇標(biāo)準(zhǔn). 避免了選擇剩余能量低、孤僻的節(jié)點(diǎn)作為CH, 并減少了節(jié)點(diǎn)的數(shù)據(jù)傳輸能量消耗.

5.2 網(wǎng)絡(luò)存活節(jié)點(diǎn)個(gè)數(shù)

為證明EAPGA協(xié)議在網(wǎng)絡(luò)生存期方面的優(yōu)越性, 本文根據(jù)存活節(jié)點(diǎn)數(shù)對(duì)其進(jìn)行評(píng)估. 圖4為不同協(xié)議網(wǎng)絡(luò)生存期與存活節(jié)點(diǎn)數(shù)的關(guān)系. 由圖4可見(jiàn), EAPGA協(xié)議的存活節(jié)點(diǎn)數(shù)在每輪都高于LEACH,LEACH-C和APSA協(xié)議, 這是因?yàn)镋APGA協(xié)議采用了基于改進(jìn)的AP算法尋找CH, 且考慮了CH能耗的適應(yīng)度函數(shù)遺傳算法, 找到了能平衡簇間能量消耗的最優(yōu)路由路徑, 從而有效地平衡了CH節(jié)點(diǎn)間的能量消耗, 降低了節(jié)點(diǎn)死亡速度, 避免了遠(yuǎn)離BS的節(jié)點(diǎn)早期大面積死亡的問(wèn)題.

圖3 不同協(xié)議的網(wǎng)絡(luò)剩余能量比較Fig.3 Comparison of residual energy of network by different protocols

圖4 不同協(xié)議的網(wǎng)絡(luò)存活節(jié)點(diǎn)數(shù)比較Fig.4 Comparison of number for surviving nodes of network by different protocols

5.3 網(wǎng)絡(luò)生命周期

為驗(yàn)證本文算法的性能, 使用網(wǎng)絡(luò)生存期準(zhǔn)則. 4種協(xié)議都采用了FND,HND和LND三個(gè)準(zhǔn)則更精確地測(cè)量網(wǎng)絡(luò)的生存期, 其中： FND表示第一個(gè)節(jié)點(diǎn)的死亡輪數(shù)； HND表示50%節(jié)點(diǎn)的死亡輪數(shù)； LND表示最后一個(gè)節(jié)點(diǎn)的死亡輪數(shù). 圖5為不同協(xié)議當(dāng)?shù)谝粋€(gè)節(jié)點(diǎn)死亡、50%的節(jié)點(diǎn)死亡和所有節(jié)點(diǎn)死亡時(shí)的網(wǎng)絡(luò)生命周期的模擬結(jié)果. 由圖5可見(jiàn), EAPGA協(xié)議第一個(gè)節(jié)點(diǎn)的死亡時(shí)間比其他協(xié)議晚. 當(dāng)死亡節(jié)點(diǎn)數(shù)達(dá)到50%時(shí), 與LEACH,LEACH-C和APSA協(xié)議相比, EAPGA協(xié)議的網(wǎng)絡(luò)生存期顯著延長(zhǎng). LEACH,LEACH-C和EAPGA協(xié)議最后一個(gè)節(jié)點(diǎn)死亡輪數(shù)分別是1 511,1 689,2 014,2 561輪, 這是因?yàn)镋APGA協(xié)議基于AP算法選舉CH時(shí)考慮了節(jié)點(diǎn)的剩余能量、節(jié)點(diǎn)中心度、節(jié)點(diǎn)間距和節(jié)點(diǎn)到BS的距離4個(gè)因素, 選擇了最合適的節(jié)點(diǎn)當(dāng)選CH, 路由階段采用了考慮能耗的適應(yīng)度函數(shù)遺傳算法, 從而顯著延長(zhǎng)了網(wǎng)絡(luò)的生存期.

5.4 CH的剩余能量偏差

分簇路由協(xié)議的成員節(jié)點(diǎn)能量消耗相似, 都是將自己的數(shù)據(jù)發(fā)送給對(duì)應(yīng)的CH, CH經(jīng)過(guò)單跳或者多跳的形式發(fā)送給BS, 所以網(wǎng)絡(luò)的主要能量消耗集中在CH. 為均衡網(wǎng)絡(luò)的能量消耗, CH的能量消耗均衡較重要. 圖6為CH經(jīng)過(guò)一輪能量消耗后, 其剩余能量的偏差程度. 由于LEACH和LEACH-C協(xié)議的數(shù)據(jù)都是CH直接傳送到BS, 導(dǎo)致了CH的能量消耗過(guò)大. 距離BS遠(yuǎn)的CH能量消耗大, 距離BS近的能量消耗小, 導(dǎo)致CH之間的能量消耗偏差較大. 而EAPGA協(xié)議采用遺傳算法構(gòu)建多跳的方式, 使數(shù)據(jù)到達(dá)BS. 遺傳算法的適應(yīng)度函數(shù)由CH的能量消耗偏差構(gòu)成, 為每個(gè)CH尋找一條最合適的路由路徑, 同時(shí)每條路由路徑的能量消耗相差最小, 從而達(dá)到均衡地消耗CH的能量, 進(jìn)而達(dá)到延長(zhǎng)網(wǎng)絡(luò)生命周期的目標(biāo).

圖5 不同協(xié)議網(wǎng)絡(luò)生命周期的比較Fig.5 Comparison of life cycle of network by different protocols

圖6 不同協(xié)議CH剩余能量偏差的比較Fig.6 Comparison of CH residual energy deviation by different protocols

綜上所述, 本文在分析LEACH協(xié)議的基礎(chǔ)上, 提出了一種能耗均衡的無(wú)線傳感器網(wǎng)絡(luò)路由協(xié)議EAPGA. 在簇建立階段, 基于AP算法, EAPGA協(xié)議考慮了節(jié)點(diǎn)的剩余能量、節(jié)點(diǎn)中心度、節(jié)點(diǎn)間距和節(jié)點(diǎn)到BS的距離選擇能量高、距離成員節(jié)點(diǎn)近的節(jié)點(diǎn)擔(dān)任CH. 在路由階段, 利用遺傳算法, 根據(jù)所有CH能量消耗偏差最小化構(gòu)造適合度函數(shù), 找到了能平衡能量消耗的最優(yōu)路由路徑, 從而有效節(jié)省了通信資源的消耗, 降低了CH的能量消耗偏差, 進(jìn)而達(dá)到延長(zhǎng)網(wǎng)絡(luò)生命周期的目標(biāo).