[發(fā)明專利]一種基于改進(jìn)粒子群算法的無線傳感網(wǎng)絡(luò)路由優(yōu)化方法

有效

• 申請?zhí)枺?/td>: 201510737551.0
• 申請日: 2015-11-03
• 公開（公告）號: CN105430706B
• 公開（公告）日: 2018-11-27
• 發(fā)明（設(shè)計）人: 曾偉;郝玉國;葉遠(yuǎn)譽(yù);江峰;范瑞祥;王軍;韓林峰
• 申請（專利權(quán)）人: 國網(wǎng)江西省電力科學(xué)研究院;國家電網(wǎng)公司;國網(wǎng)江西省電力公司;河南許繼儀表有限公司
• 主分類號: H04W40/04
• 分類號: H04W40/04;H04W40/10;H04W84/18
• 代理公司: 南昌市平凡知識產(chǎn)權(quán)代理事務(wù)所 36122
• 代理人: 姚伯川

1.一種基于改進(jìn)粒子群算法的無線傳感網(wǎng)絡(luò)路由優(yōu)化方法，其特征在于，所述方法使用一種含有整個網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)信息的關(guān)系矩陣作為粒子群算法的編碼方式，用來處理路由優(yōu)化問題；并應(yīng)用遺傳算法的交叉和變異機(jī)制實現(xiàn)全局收斂搜索；所述方法包括以下步驟：

(1)初始化參數(shù)：設(shè)定種群的規(guī)模M，網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)n，慣性權(quán)重w，以及最大的迭代次數(shù)t_max，確定路由節(jié)點(diǎn)的基本信息：有效傳輸距離、初始能量及剩余能量；

(2)初始化種群：對每個粒子i得到一個隨機(jī)的初始位置X_i以及一個隨機(jī)的初始速度V_i；粒子位置表示為其元素值為所對應(yīng)的鏈路被選擇的概率；粒子速度表示為其元素值為隨機(jī)賦值并且每次迭代后都應(yīng)當(dāng)滿足如下關(guān)系：

(3)對新位置按照路由策略計算位置的適應(yīng)值：QoS約束單播路由問題的網(wǎng)絡(luò)拓?fù)鋱D用無向連通圖G＝(V,E)表示，其中，V為網(wǎng)絡(luò)中所有網(wǎng)絡(luò)節(jié)點(diǎn)集合，E為任意兩相鄰節(jié)點(diǎn)i,j之間的鏈路邊e_ij集合，i,j＝1,2,…,n，n表示網(wǎng)絡(luò)的節(jié)點(diǎn)數(shù)；使用罰函數(shù)Q(P_st)將約束單播路由優(yōu)化問題轉(zhuǎn)化為無約束優(yōu)化問題進(jìn)行求解：其中，罰函數(shù)Q(P_st)表示為s和t分別是源節(jié)點(diǎn)和目的節(jié)點(diǎn)的編號，e_ij為相鄰節(jié)點(diǎn)i,j之間的鏈路，B_ij表示相鄰節(jié)點(diǎn)i,j間的帶寬，c_ij表示鏈路e_ij上的花費(fèi)，B_w為帶寬要求，D_ij表示相鄰節(jié)點(diǎn)i,j間的延遲，D_req為延遲要求，P_st為目標(biāo)值最優(yōu)的路徑，γ和η為罰函數(shù)系數(shù)；適應(yīng)度函數(shù)表示為

(4)尋找P_best和G_best：對于每個個體，將其適應(yīng)值與其所經(jīng)歷過的最好位置的適應(yīng)值進(jìn)行比較，若較優(yōu)，則更新最好位置；對于每個個體，將其適應(yīng)值與全局所經(jīng)歷的最好位置的適應(yīng)值進(jìn)行比較，若較好，則將其作為當(dāng)前的全局最好位置；P_best表示粒子群算法中粒子個體經(jīng)歷過的最優(yōu)位置，G_best是粒子群經(jīng)歷過的最優(yōu)位置；

(5)對于粒子群所有個體，根據(jù)關(guān)系矩陣編碼方式，計算每個粒子個體的位置和速度，對每個粒子進(jìn)行變異操作，然后在此基礎(chǔ)上對粒子進(jìn)行交叉操作；

(5.1)設(shè)網(wǎng)絡(luò)中的節(jié)點(diǎn)數(shù)是n，用具有大于或等于零的元素的二維關(guān)系矩陣來表示網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)信息，矩陣中元素x_ij的值大小表示鏈路e_ij被選中的概率，其值越大表示鏈路被選中的概率越大，若為0則表示在網(wǎng)絡(luò)中不存在此條鏈路，下標(biāo)值i表示鏈路起始節(jié)點(diǎn)，j表示鏈路的終止節(jié)點(diǎn)；

(5.2)變異操作：在每次迭代中，為了保持樣本的多樣性，根據(jù)速度更新公式計算下一代的速度；w為慣性權(quán)重系數(shù)，其中，t_max為設(shè)置的最大迭代次數(shù)，t為當(dāng)前迭代次數(shù)，w_max為最大慣性權(quán)重，w_min為最小慣性權(quán)重；P_i為粒子i所經(jīng)歷的局部最好位置，即個體最好位置；c₁,c₂為加速因子，取值為2.0；r₁,r₂為(0，1)內(nèi)隨機(jī)數(shù)；P_g為群體中所有粒子所經(jīng)歷過的局部最好位置，即全局最好位置；X_i(t)為粒子i在t時刻的位置；若在t+1時刻x_ij取1，表示其對應(yīng)的節(jié)點(diǎn)v_ij被選為路由節(jié)點(diǎn)；下腳g表示局部最好位置處的標(biāo)記；

(5.3)交叉操作：隨機(jī)選取全局最優(yōu)路由中的某個區(qū)間片段[a,b]進(jìn)行交叉；即從局部最好位置出的路由請求R_g中選擇片段R_c＝{v_a,…,v_b}插入到任意路由請求R_j中v_ij后面，并且v_ij離v_a節(jié)點(diǎn)距離最小；然后在R_j原路徑中刪除節(jié)點(diǎn)v_a,…,v_b，同時更新路由標(biāo)識向量X_j，X_j為X_i(t)的集合；

(5.4)根據(jù)位置更新公式計算下一代的位置；

(6)重新評價各粒子的適應(yīng)度值，更新各個粒子的歷史最優(yōu)解，更新種群的全局最優(yōu)解；如果新位置的適應(yīng)值比當(dāng)前局部最好解的適應(yīng)值還要小，則用新的位置更新當(dāng)前的局部最好解；假若有粒子的局部最優(yōu)解優(yōu)于當(dāng)前的全局最優(yōu)解和其他粒子的局部最優(yōu)解，則用此局部最優(yōu)解更新當(dāng)前的全局最優(yōu)解；

(7)停機(jī)條件判斷：如果當(dāng)前迭代的次數(shù)等于最大迭代次數(shù)，轉(zhuǎn)步驟(8)，否則轉(zhuǎn)步驟(5)；

(8)輸出求得的最好解路徑。

2.根據(jù)權(quán)利要求1所述的一種基于改進(jìn)粒子群算法的無線傳感網(wǎng)絡(luò)路由優(yōu)化方法，其特征在于，所述步驟(3)中，根據(jù)適應(yīng)度函數(shù)對每一個粒子i的優(yōu)劣程度進(jìn)行評價，適應(yīng)度越大，個體越好，反之，適應(yīng)度越小，個體越差；將優(yōu)化目標(biāo)函數(shù)直接定義算法的適應(yīng)度函數(shù)，其結(jié)果作為粒子i的適應(yīng)度