[發明專利]基于改進混沌遺傳算法的WSN多跳LEACH路由協議

在審

• 申請號: 202010869415.8
• 申請日: 2020-08-26
• 公開（公告）號: CN111970742A
• 公開（公告）日: 2020-11-20
• 發明（設計）人: 胡黃水;劉清雪;王出航;王宏志;姚美琴;王婷
• 申請（專利權）人: 吉林建筑科技學院
• 主分類號: H04W40/32
• 分類號: H04W40/32;H04W40/10;H04W40/02;H04W4/38;H04W84/18;H04L12/721;G06N3/12
• 代理公司: 暫無信息
• 代理人: 暫無信息

1.基于改進混沌遺傳算法的WSN多跳LEACH路由協議，其特征在于：包括系統模型、簇頭選舉、尋找路徑和簇維護；系統模型為協議實現提供模型，具體包括網絡模型和能量模型；簇頭選舉是基于LEACH改進的閾值函數來選舉簇頭，考量了節點剩余能量、節點剩余能量與負載比和節點中心度，從而使位于簇中心、負載較小且能量多的節點成為簇頭的概率大；尋找路徑是使用混沌遺傳算法來尋找全局最優的多跳路由路徑；簇維護考量能量和負載平衡來自適應計算輪周期；

所述的簇頭選舉是通過改進LEACH的閾值函數，考量節點剩余能量、節點剩余能量與負載比和節點中心度，從而使位于簇中心、負載較小且能量多的節點成為簇頭的概率大；當節點在0和1之間分配的隨機值小于其閾值時，該節點成為CH；具體的閾值由LEACH修改后的閾值函數計算得出，如下所示：

其中E_initial表示網絡中所有節點的初始能量，表示節點i的剩余能量；Li表示節點i的負載，N_i＝{n₁，n₂，...，n_p}表示節點i的鄰居集，p是鄰居的個數；d_iBS表示節點i和BS之間的距離，可以看出，剩余能量越大、負載越均勻、越靠近鄰域中心的節點越有可能成為CH；與LEACH不同，本發明成簇是通過混沌遺傳算法來完成的，而不是CH和CM之間的消息交互；此外，該算法在BS中完成，從而得到每個簇頭最優的成員，同時尋找最優路由路徑的全局解；

所述的尋找路徑是采用混沌遺傳算法來找到從每個源簇頭到基站的路由路徑，通過混沌映射構建初始種群，并通過精英選擇、雙點交叉和位變異產生下一代種群，以能耗最小和負載最均衡為目標，構造適應度函數，并計算種群中各個體的適應度值；滿足終止條件時，適應度值最小的個體即為最優解；具體為首先構造適應度函數，考慮了能量消耗和總能量，適應度函數用于評估個體的質量，所構建的適應度函數如下：

其中

適應度函數的值越小，個體的質量越好，然后越有可能傳給下一代，直到獲得適應度函數值最小的最佳個體；接下來初始化種群，在本發明中，采用實數編碼而不是二進制編碼來表示種群的染色體，其中實數表示由節點ID表示的基因；染色體由兩部分組成，一個用于路由路徑，另一個用于CM選擇；路由路徑基因表示所選CH的下一跳CH，CM選擇基因表示相應CM的確定CH；修改后的混沌邏輯映射用于生成初始基因，因為它對初始值敏感，具有更好的隨機序列生成，表示如下：

其中，u為控制參數，當u＞3.57且z_i≠0.25，0.5，0.75時，系統進入混沌狀態；為了避免無效個體的出現，在g_i上附加了約束條件：

其中和分別表示簇頭h_i和成員m_i的下一跳CH和CH，如此則可以得到有效個體，從而產生所需的初始種群；然后計算初始種群的每個染色體的適應度函數值，適應度函數的值越小，個體越接近最佳解；遺傳選擇采用精英選擇，即種群中適應度值小的前15％精英個體直接被選為下一代；對于其它個體，確定其適應度函數值是否大于如上所述由混沌邏輯映射生成的隨機個體的適應度函數值；如果是，則選擇個體進行交叉操作，否則，選擇隨機個體進行交叉操作以加快收斂并確保種群多樣性；本發明采用兩點交叉，交叉操作后，由于父染色體的基因都滿足約束條件，因此得到的兩個子染色體必須仍然有效；然后計算子染色體的適應度函數值，與父染色體進行比較，如果子染色體的適應度函數值小于其父染色體的適應度函數值，則選擇該子染色體進行變異操作；如果沒有，則選擇隨機個體來確定其適應度函數值是否小于父染色體的適應度函數值；如果小于，則選擇隨機個體進行變異操作，否則選擇父個體進行變異操作；這樣，收斂速度進一步加快；交叉產生的個體應用混沌比特變異算子進行變異操作；選擇一個隨機突變點改變相應的基因，得到新的個體；當然，新個體也是有效的，因為新產生的基因仍然滿足約束條件；此外，計算其適應度函數值，判斷其是否優于其父染色體，并將較好的一個選擇給下一代；最后尋找最優解，一旦本發明的迭代次數滿足其中一個終止條件，就可以得到最優解，即找到所選簇頭的最優路由路徑和成員；不失一般性，迭代次數作為終止條件之一；另外，將適應度函數值的偏離度作為另一個終止條件，如下所示：

其中ω是種群中的個體數，Fitness_i是第i個個體的適應度函數值，Fitness_max是適應度函數的最大值，ε是一個預置的小正數，等于10^-5；一旦遺傳運算停止，種群中適應度值最小的個體即為最優解；

所述的簇維護是采用自適應輪周期來重新成簇，不同于采用固定輪周期來重新成簇容易導致頻繁成簇產生許多控制報文而消耗大量能量，自適應輪周期考量網絡能耗和負載均衡來自適應計算輪時長，從而降低網絡能耗；具體為網絡的負載平衡和能量平衡并分別用α和β表示；

T_newround＝2*T_round*α*β

其中

·T_round是傳統的循環時間

·α是負載平衡系數，且

·β是能量平衡系數，且

n′是存活節點的數目，而且，β標準化為

其中β_min和β_max分別為β的最小值和最大值；

在每個輪周期開始時，基站使用混沌遺傳算法根據接收到的能量信息找到每個簇頭的最佳路由路徑和包含的成員，然后將它們與計算的輪時間一起廣播到網絡；每個節點基于接收到的信息進行通信。