[發(fā)明專利]基于二進(jìn)制粒子群算法的無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)分層調(diào)度方法

無(wú)效

• 申請(qǐng)?zhí)枺?/td>: 201310171940.2
• 申請(qǐng)日: 2013-04-25
• 公開（公告）號(hào): CN103249055A
• 公開（公告）日: 2013-08-14
• 發(fā)明（設(shè)計(jì)）人: 張軍;詹志輝
• 申請(qǐng)（專利權(quán)）人: 中山大學(xué)
• 主分類號(hào): H04W16/18
• 分類號(hào): H04W16/18;H04W72/12;H04W84/18
• 代理公司: 暫無(wú)信息
• 代理人: 暫無(wú)信息

1.一種帶變異操作的基于二進(jìn)制粒子群算法的無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)分層調(diào)度方法，其特征是通過(guò)最小化每一層的傳感器節(jié)點(diǎn)數(shù)量以達(dá)到節(jié)點(diǎn)可分層數(shù)最大化的目的，同時(shí)通過(guò)在粒子群算法中引入變異操作以增強(qiáng)算法多樣性，避免算法容易落入局部最優(yōu)的缺陷，該方法主要包括以下步驟：

(1)對(duì)于給定的網(wǎng)絡(luò)Netw，設(shè)置其最大層數(shù)K＝0，然后檢查網(wǎng)絡(luò)中的傳感器節(jié)點(diǎn)集S是否能夠?qū)W(wǎng)絡(luò)區(qū)域100％覆蓋，如果能，則進(jìn)行以下的步驟；否則輸出最大可分層數(shù)K＝0，終止程序；

(2)使用二進(jìn)制粒子群算法從網(wǎng)絡(luò)Netw的傳感器節(jié)點(diǎn)集S中找出一組能夠?qū)W(wǎng)絡(luò)區(qū)域進(jìn)行100％覆蓋的最優(yōu)節(jié)點(diǎn)子集S*，具體的流程如下：

a)隨機(jī)生成N個(gè)粒子形成粒子群算法的種群，每個(gè)粒子i的位置和速度編碼分別表示為X_i＝[x_i1，x_i2，...，x_iD]和V_i＝[v_i1，v_i2，...，v_iD]；其中D為編碼長(zhǎng)度，與網(wǎng)絡(luò)中的節(jié)點(diǎn)數(shù)目相同；位置X_i中每一維的值為1表示該節(jié)點(diǎn)被選擇到子集中，為0則表示不被選擇；速度表示位置的變化情況；評(píng)估所有粒子的適應(yīng)值，該適應(yīng)值為粒子所代表的解中被選擇的傳感器節(jié)點(diǎn)的數(shù)量，該值越小說(shuō)明解的質(zhì)量越高；同時(shí)令粒子i的歷史最優(yōu)位置P_i＝[p_i1，p_i2，...，p_iD]為當(dāng)前位置X_i，整個(gè)種群的全局最優(yōu)位置G＝[g₁，g₂，...，g_D]為所有歷史最優(yōu)位置中最好的那個(gè)；

b)對(duì)每個(gè)粒子i，借助其歷史最優(yōu)位置P_i和種群的全局最優(yōu)位置G對(duì)速度V_i進(jìn)行更新；對(duì)于V_i的每一維v_id，其中1≤d≤D，相應(yīng)的更新公式為：v_id＝v_id+c₁×r₁×(p_id-x_id)+c₂×r₂×(g_d-x_id)；其中c₁和c₂均為2.0，r₁和r₂為區(qū)間[0，1]之間的隨機(jī)數(shù)；

c)使用如下策略更新粒子i的位置X_i進(jìn)行更新：對(duì)每一維x_id，首先計(jì)算然后生成區(qū)間[0，1]之間的隨機(jī)數(shù)r，如果r≤p，則設(shè)x_id＝1，否則設(shè)x_id＝0；

d)使用變異策略對(duì)粒子i更新后的位置X_i進(jìn)行變異，增強(qiáng)算法的多樣性；

e)對(duì)粒子i更新變異后的位置X_i進(jìn)行適應(yīng)值的評(píng)估，如果新的適應(yīng)度函數(shù)值比其歷史最優(yōu)位置P_i的適應(yīng)度函數(shù)值更好，則將P_i設(shè)置為X_i，同時(shí)判斷新的P_i是否比種群的全局最優(yōu)位置G更優(yōu)，如果是，則將G替換為P_i；

f)反復(fù)執(zhí)行以上步驟b)、c)、d)和e)直到滿足終止條件，則全局最優(yōu)位置G所代表的解中值為1的那些維所對(duì)應(yīng)的傳感器節(jié)點(diǎn)表示被選擇到最優(yōu)節(jié)點(diǎn)子集S*中；

(3)將最優(yōu)節(jié)點(diǎn)子集S*中的傳感器節(jié)點(diǎn)標(biāo)記為網(wǎng)絡(luò)Netw的傳感器節(jié)點(diǎn)集S中的不可使用節(jié)點(diǎn)，剩下的傳感器節(jié)點(diǎn)組成一個(gè)新的節(jié)點(diǎn)集S＝S/S*，并形成一個(gè)新的網(wǎng)絡(luò)Netw；設(shè)置K＝K+1；

(4)檢查網(wǎng)絡(luò)中的傳感器節(jié)點(diǎn)集S是否能夠?qū)W(wǎng)絡(luò)區(qū)域100％覆蓋，如果能，則轉(zhuǎn)到步驟(2)繼續(xù)執(zhí)行；如果不能，則輸出最大可分層數(shù)K，終止程序。

2.基于權(quán)利要求1的步驟(2)-a)中所述的粒子群算法種群初始化方法，其特征在于必須保證種群中至少有一個(gè)粒子能夠滿足對(duì)整個(gè)網(wǎng)絡(luò)的100％覆蓋；具體的方法是在隨機(jī)產(chǎn)生種群之后進(jìn)行覆蓋率的判斷，如果沒(méi)有粒子能夠滿足對(duì)整個(gè)網(wǎng)絡(luò)的100％覆蓋，則需要重新產(chǎn)生種群；由于產(chǎn)生種群之前已經(jīng)檢查網(wǎng)絡(luò)能夠被所有傳感器節(jié)點(diǎn)進(jìn)行100％的覆蓋，因此可以保證這種方法的成功。