基于改進的AP和遺傳算法的能量感知分簇路由協議

胡黃水, 姚美琴, 王 亮, 韓優佳

(1. 長春工業大學 計算機科學與工程學院, 長春, 130012； 2. 吉林建筑科技學院 計算機科學與工程學院, 長春 130114)

無線傳感器網絡(WSN)作為物聯網(IoT)不可或缺的一部分, 近年來發展迅速[1-4]. 無線傳感器網絡是由多個節點聚集在一起, 將其收集的數據相互傳輸到基站(BS)所形成的網絡結構[5-9]. 由于無線傳感器節點能量受限, 所以節能是延長無線傳感器網絡壽命的關鍵因素[10]. 研究表明, 將節點分成不同的簇以最大限度地延長無線傳感器網絡的使用壽命是節能和可擴展的[11-15]. 因此, 在基于簇的協議中, 所有傳感器節點都根據某些特定規則劃分為不同的簇.

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

1 能量模型

當節點間距離為d時, 傳感器節點發送Lbit數據的能量消耗為

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

(1)

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

(2)

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

(3)

傳感器接收Lbit數據時消耗的能量為

ERx(L)=Eelec×L.

(4)

2 網絡模型

本文提出的EAPGA協議在監視區域中隨機部署n個傳感器節點, 并做下列假設：

1) 所有節點都同構, 能量有限, 并且每個節點都具有唯一標識符(ID), 但BS的能量無限；

2) 所有節點都可感知其剩余能量和位置；

3) 從睡眠狀態更改為工作狀態時, 節點消耗的能量相同.

3 成簇階段

步驟1) 計算WSN中節點X={x1,x2,…,xn}間的相似度矩陣:

(5)

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

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

(6)

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

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

(7)

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

步驟4) 通過對節點的吸引度信息和歸屬度信息求和, 確定節點選取的聚類中心:

(8)

其中, 若i=k, 則節點i自身是CH； 若i≠k, 則節點k是節點i的CH.

4 尋路階段

在本文網絡中采用改進遺傳算法為每個信道尋找最優的路由路徑, 傳統遺傳算法由于具有選擇、交叉、變異等隨機操作, 可能產生無效個體. 因此在EAPGA中, 為產生合適的基因并避免無效個體及提高收斂速度給出一個約束條件.

4.1 構建適應度函數

為使網絡壽命最大化, 必須盡可能減少每個CH的能耗. 因此, 能量消耗偏差是適應度函數的一個影響因子. 本文構建如下適應度函數：

(9)

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

(10)

式中hi表示第i個CH,nCH表示CH的個數,Ehi表示簇頭hi的能耗. 因此, 適應度函數的值越大, 其個體質量越好, 越有可能傳給下一代.

4.2 初始化種群

在EAPGA中, 實數編碼用于表示群體的染色體. 染色體是指由CH的ID和BS的ID所表示基因組成的個體. 染色體的特定基因指示對應CH的下一跳CH, 如圖1所示.

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

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

圖2 EAPGA的無效染色體Fig.2 Invalid chromosome of EAPGA

4.3 產生下一代種群

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

單點雜交用于選定的個體產生新的后代. 計算每個子對象的適應度函數值, 與父對象進行比較. 如果其值大于其父代的值, 則選擇該值進行變異操作. 或者使用隨機生成的個體確定其適應度函數值是否大于父對象的適應度函數值. 如果是, 則選擇隨機個體進行變異操作; 否則選擇父個體, 進一步加快收斂速度. 將這些新個體和精英個體相結合, 產生下一代種群.

4.4 尋找最優路徑

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

1) 預先設定的迭代次數；

2) 適應度函數值的偏差度, 用公式表示為

(11)

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

5 仿真分析

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

5.1 網絡剩余能量

由于每個節點的能量有限, 網絡生命周期可能會由于某些節點的耗盡而下降. 因此, 本文考慮了節點的能量、位置和數據傳輸的能量消耗. 對LEACH,LEACH-C,APSA和EAPGA協議進行了網絡總節點剩余能量的仿真分析, 結果如圖3所示. 由圖3可見, 在相同仿真環境下, 網絡運行期間EAPGA協議中節點的總剩余能量分別高于LEACH,LEACH-C和APSA協議. 因為EAPGA協議考慮了節點間的位置關系完成成簇, 可有效降低節點和CH傳輸的能量消耗, 并將節點的剩余能量作為成簇標準. 避免了選擇剩余能量低、孤僻的節點作為CH, 并減少了節點的數據傳輸能量消耗.

5.2 網絡存活節點個數

為證明EAPGA協議在網絡生存期方面的優越性, 本文根據存活節點數對其進行評估. 圖4為不同協議網絡生存期與存活節點數的關系. 由圖4可見, EAPGA協議的存活節點數在每輪都高于LEACH,LEACH-C和APSA協議, 這是因為EAPGA協議采用了基于改進的AP算法尋找CH, 且考慮了CH能耗的適應度函數遺傳算法, 找到了能平衡簇間能量消耗的最優路由路徑, 從而有效地平衡了CH節點間的能量消耗, 降低了節點死亡速度, 避免了遠離BS的節點早期大面積死亡的問題.

圖3 不同協議的網絡剩余能量比較Fig.3 Comparison of residual energy of network by different protocols

圖4 不同協議的網絡存活節點數比較Fig.4 Comparison of number for surviving nodes of network by different protocols

5.3 網絡生命周期

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

5.4 CH的剩余能量偏差

分簇路由協議的成員節點能量消耗相似, 都是將自己的數據發送給對應的CH, CH經過單跳或者多跳的形式發送給BS, 所以網絡的主要能量消耗集中在CH. 為均衡網絡的能量消耗, CH的能量消耗均衡較重要. 圖6為CH經過一輪能量消耗后, 其剩余能量的偏差程度. 由于LEACH和LEACH-C協議的數據都是CH直接傳送到BS, 導致了CH的能量消耗過大. 距離BS遠的CH能量消耗大, 距離BS近的能量消耗小, 導致CH之間的能量消耗偏差較大. 而EAPGA協議采用遺傳算法構建多跳的方式, 使數據到達BS. 遺傳算法的適應度函數由CH的能量消耗偏差構成, 為每個CH尋找一條最合適的路由路徑, 同時每條路由路徑的能量消耗相差最小, 從而達到均衡地消耗CH的能量, 進而達到延長網絡生命周期的目標.

圖5 不同協議網絡生命周期的比較Fig.5 Comparison of life cycle of network by different protocols

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

綜上所述, 本文在分析LEACH協議的基礎上, 提出了一種能耗均衡的無線傳感器網絡路由協議EAPGA. 在簇建立階段, 基于AP算法, EAPGA協議考慮了節點的剩余能量、節點中心度、節點間距和節點到BS的距離選擇能量高、距離成員節點近的節點擔任CH. 在路由階段, 利用遺傳算法, 根據所有CH能量消耗偏差最小化構造適合度函數, 找到了能平衡能量消耗的最優路由路徑, 從而有效節省了通信資源的消耗, 降低了CH的能量消耗偏差, 進而達到延長網絡生命周期的目標.