[發明專利]一種基于遺傳算法的無線傳感網多目標優化路由方法

有效

• 申請號: 201510740359.7
• 申請日: 2015-11-03
• 公開（公告）號: CN105430707B
• 公開（公告）日: 2019-01-11
• 發明（設計）人: 曾偉;葉遠譽;范瑞祥;江峰;郝玉國;劉永光;王軍;方旭
• 申請（專利權）人: 國網江西省電力科學研究院;國家電網公司;國網江西省電力公司;河南許繼儀表有限公司
• 主分類號: H04W40/04
• 分類號: H04W40/04
• 代理公司: 南昌市平凡知識產權代理事務所 36122
• 代理人: 姚伯川

1.一種基于遺傳算法的無線傳感網多目標優化路由方法，其特征在于，包括以下步驟：

(1)隨機生成網絡拓撲，初始化參數；基站收集網絡初始信息，得到網絡的各個節點的前向鄰居矩陣A、可靠性矩陣Re、時延矩陣De、能量矩陣E、時延抖動矩陣Jit和帶寬矩陣SNR；

(2)根據前向鄰居矩陣A找源節點的代理源節點集NB和數目length_NB,初始化最優路徑解集bestPath＝Φ；初始化代理源節點i＝1；

(3)如果i≤length_NB,則執行(4),否則執行(13)；

(4)置StartN＝NN(i)，StartN為遺傳算法迭代程序名稱，NN(i)為節點集合名稱；生成父代種群father和子代種群child；置Counter＝1，初始化bestPath＝Φ；用節點ID號表示染色體中的基因，則一個染色體是由source節點到sink節點的路徑上的節點ID號序列組成；每條染色體的第一個基因為source節點ID號，最后一個基因為sink節點ID號；每相鄰的兩個基因為無線多媒體傳感器網絡WMSNs一條實際存在可相互通信的鏈路；

假設網絡的節點個數為n，source節點ID號為k＝1，sink節點ID號m＝n，則對應的染色體可表示為一個有序序列:<1…i…j…n>,1＜i,j＜n且i≠j；

(5)如果Counter<λ，則執行(6)，否則執行步驟(11)，λ為迭代次數；

(6)將種群father和child合群為farm，對farm的每個個體計算其適應度值，求Pareto最優解集，對最優解集去約束，得到本次迭代最優解集并保存在bestPath中；

(7)對本次迭代最優解集之外的個體解碼、計算其適應度值，按照個體的適應度升序排列，根據排序號計算選擇概率，計算輪盤賭選擇區域，按輪盤賭選擇方法選擇個體；多路徑多目標優化函數構造適應度函數為：

其中，del_i、rel_i、e_i、snr_i、jit_i分別表示種群中第i個個體的網絡時延、可靠性、剩余能量、傳輸速率、時延抖動大小；d_max和d_min分別表示種群中第i個個體的網絡時延的最大值和最小值；r_max和r_min分別表示種群中第i個個體的可靠性的最大值和最小值；e_max和e_min分別表示種群中第i個個體的剩余能量的最大值和最小值；s_max和s_min分別表示種群中第i個個體的傳輸速率的最大值和最小值；j_max和j_min分別表示種群中第i個個體的時延抖動大小的最大值和最小值；

根據個體是否滿足時延約束和可靠性約束的情況，對其適應度值給以適當的獎懲，時延和可靠性的獎懲函數分別構造為:

其中dc,rc分別為時延和可靠性的約束值，如果滿足約束，則qd_i和qr_i值為正，個體的適應值得到獎勵，否則qd_i和qr_i值為負，個體的適應值得到懲罰；

綜上所述，可得個體適應度計算函數Fit(i):Fit(i)＝fit_i+qd_i+qr_i；

(8)將最優解集和根據輪盤賭選擇出種群初始規模大小的個體作為新一代種群f，保存副本為父代father；采用按個體適應度輪盤賭方法和Pareto Front兩種選擇方法相結合的選擇策略；首先對每一代父種群和子種群采用Pareto Front選擇多目標最優解集，將其保存在最優解集中，并選擇其為下一代種群的部分個體；通過使用Pareto Front在父代、規模為2N的子代種群選擇出來的最優解數小于初始化種群的規模N，通過設計選擇概率函數和使用輪盤賭方法選擇個體并補充到下一代中，以保證種群規模不變；

在輪盤賭選擇法中各個個體的選擇概率和其適應度值成比例；設群體大小為n，其中個體i的適應度為Fit(i)，則個體i被選擇的概率如公式所示；

首先將種群中的個體按照個體的適應值升序排序，記錄每個個體的排序號；

然后將個體的排序號作為其適應值，即Fit(i)＝i，i為個體排序號；按照公式將選擇概率轉換為輪盤賭隨機選擇區域；

(9)種群f根據交叉概率和變異概率分別進行單點交叉和變異生成新一代種群，保存副本記為child；

(9.1)根據個體和種群的適應度設計交叉概率，用或其它表示；

其中，p_c1和p_c2為常數且0＜p_c2＜p_c1＜1，fit_i和fit_j分別為隨機選中的進行交叉的兩個個體的適應度值，fit_over為當前種群的平均適應度值，fit_max為當前種群的最大個體適應度值；

(9.2)生成新的鏈路，具體過程如下:a)隨機產生一個變異基因位i作為變異點，除了i位之外，其它的基因位保持不變，1＜i＜n；b)第i位基因變異為節點v_i-1的前向鄰居節點和節點v_i+1的后向鄰居節點的交集中的某一節點，即第i位基因變異的范圍為C＝F_i-1∩B_i+1，這里，F_i-1為節點v_i-1的前向鄰居節點集，B_i+1為節點v_i+1的后向鄰居節點集；如果C＝φ，則第i位基因不發生變異，否則按照變異概率P_m在集合C中隨機選擇某一元素進行替換；變異概率P_m表示為：

或其它；

其中，p_m1和p_m2為常數，且0＜p_m2＜p_m1＜1，fit_i、fit_over和fit_max表示的意義同(9.1)；

(10)設Counter'＝Counter+1，執行(5)；

(11)從bestPath中Pareto排序選擇一條路徑作為以當前虛擬點為起點的最優路徑，并將其保存在bestPath中，同時將該路徑上的所有節點標記為不可用；

(11.1)設source節點為v_i,置path＝<1>，置當前搜索節點v_i＝v₁；

(11.2)判斷當前搜索節點v_i，是否為sink節點，若是則執行(11.5)，否則執行(11.3)；

(11.3)依據前向鄰居矩陣A判斷當前搜索節點v_i的前向鄰居節點集合F_i是否為空集，若是則執行回退操作到步驟(11.2)，否則執行(11.4)；

(11.4)網絡的節點數為n，將F_i的成員v_j∈F_i按照其距sink節點的距離d_jn降序排列得k＝1,2,…,|F_i|為F_i按照d_jn降序排列的順序號；令d_nn＝1，1＜j＜n，對做如下變換:其中w為常數；計算F_i的成員成為下一跳轉發節點的選擇概率:

D_i為值的集合，若v_j被選為下一跳節點，將v_j加入path中:path＝<1…j>；將v_j作為當前搜索節點v_i，執行(11.2)；

(11.5)輸出path；

(12)令i＝i+1，執行(3)；

(13)輸出bestPath。