王獻(xiàn)榮， 蘇小玲

(1.河南工業(yè)大學(xué) 信息科學(xué)與工程學(xué)院,江南 鄭州 450001;

2.武漢理工大學(xué) 信息工程學(xué)院,湖北 武漢 430070)

0 引 言

無線傳感器網(wǎng)絡(luò)(wireless sensor networks,WSNs)主要由傳感器節(jié)點(diǎn)構(gòu)成，能夠?qū)崟r(shí)地監(jiān)測(cè)、感知和采集節(jié)點(diǎn)部署區(qū)里用戶感興趣的感知對(duì)象的各種信息(如光強(qiáng)、溫度、濕度、噪音等)，并對(duì)這些信息進(jìn)行處理后通過無線網(wǎng)絡(luò)的方式發(fā)送給用戶[1]。目前，無線傳感器網(wǎng)絡(luò)的應(yīng)用越來越廣泛,如軍事偵察、環(huán)境監(jiān)測(cè)、醫(yī)療護(hù)理、智能家居等。感知資源分配問題是無線傳感器網(wǎng)絡(luò)研究中的一個(gè)關(guān)鍵問題,其主要目標(biāo)在于：如何動(dòng)態(tài)調(diào)整無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)的探測(cè)目標(biāo)、通信時(shí)隙等參數(shù)并在節(jié)點(diǎn)能量有限的條件下完成對(duì)多個(gè)任務(wù)目標(biāo)的探測(cè)任務(wù)[2]。

目前，已有很多研究者提出了不同的無線傳感器網(wǎng)絡(luò)感知資源分配方案[3,4]，然而，這些方法主要存在：通信時(shí)延較大、目標(biāo)檢測(cè)成功率較低等問題。通常，感知資源分配算法需要考慮傳感器感知節(jié)點(diǎn)的能量、與探測(cè)目標(biāo)的距離、探測(cè)目標(biāo)的重要程度。因此，算法的復(fù)雜度成指數(shù)級(jí)提高，求得其最優(yōu)解是一個(gè)非確定多項(xiàng)式(NP)難問題。已有的研究表明，智能優(yōu)化算法是求解此類問題的有效方法?；诖?，本文提出了一種基于免疫補(bǔ)體優(yōu)化的無線傳感器網(wǎng)絡(luò)感知資源分配方法，提高檢測(cè)效率。仿真結(jié)果表明：本算法可以獲得更高的目標(biāo)檢測(cè)成功率。

1 無線傳感器網(wǎng)絡(luò)的感知資源分配模型

無線傳感器網(wǎng)絡(luò)的基本特點(diǎn)是：傳感器節(jié)點(diǎn)數(shù)量巨大且可用能量和探測(cè)范圍有限，因此，其感知資源分配必須考慮如何盡量節(jié)省節(jié)點(diǎn)能量，并盡量避免相鄰節(jié)點(diǎn)的通信沖突[5]。

0≤pm,n≤1.

其中，如果目標(biāo)超出傳感器節(jié)點(diǎn)的探測(cè)范圍，則其值被置為0；當(dāng)傳感器節(jié)點(diǎn)與被探測(cè)目標(biāo)的距離越近時(shí)，其值越大。根據(jù)傳感器節(jié)點(diǎn)能量的有限性，對(duì)有利程度矩陣P進(jìn)行修正，建立如下歸一化矩陣

為完成目標(biāo)探測(cè)任務(wù)，需要傳感器網(wǎng)絡(luò)中的N個(gè)節(jié)點(diǎn)去探測(cè)M個(gè)目標(biāo)，從而得到目標(biāo)分配矩陣A，如下式所示

am,n∈{0,1}.

其中，矩陣中元素am,n取1表示第n個(gè)傳感器探測(cè)第m個(gè)目標(biāo)，否則,取0。如果在特定的傳感器網(wǎng)絡(luò)中，每個(gè)節(jié)點(diǎn)每次只能探測(cè)一個(gè)任務(wù)目標(biāo)，則表示為矩陣的每列只能有一個(gè)非零元素，如下式所示

如果根據(jù)被探測(cè)目標(biāo)的重要程度和具體需求，要求至少需要dm只傳感器去探測(cè)第m只目標(biāo)，則探測(cè)目標(biāo)m所需的傳感器數(shù)目表示如下

因此，本文要優(yōu)化的目標(biāo)函數(shù)為

由于需要求得分配矩陣A(其它參數(shù)已知)，因此，本文采用矩陣編碼。本文感知資源分配算法的目標(biāo)即根據(jù)監(jiān)測(cè)范圍內(nèi)的監(jiān)測(cè)任務(wù)和空閑時(shí)隙，分配給網(wǎng)絡(luò)中的感知節(jié)點(diǎn)最優(yōu)的任務(wù)目標(biāo)。

2 基于免疫補(bǔ)體優(yōu)化的算法求解實(shí)現(xiàn)

2.1 免疫補(bǔ)體優(yōu)化算法

由于求解無線傳感器網(wǎng)絡(luò)的感知資源分配的最優(yōu)解是一個(gè)NP難問題[6]。因此，本文采用智能計(jì)算中的免疫優(yōu)化算法進(jìn)行求解。

人工免疫系統(tǒng)是一種受生物免疫原理而啟發(fā)的智能優(yōu)化系統(tǒng)。目前,人工免疫系統(tǒng)中克隆選擇原理、免疫網(wǎng)絡(luò)模型和負(fù)選擇原理等已經(jīng)在控制、圖像處理、網(wǎng)絡(luò)安全等工程應(yīng)用領(lǐng)域得到了廣泛應(yīng)用[7～10]。但這些算法和模型存在許多局限性。因此,繼續(xù)深入挖掘生物免疫系統(tǒng)的其它機(jī)理以供工程應(yīng)用是人工免疫系統(tǒng)發(fā)展的一個(gè)重要方向。

生物免疫系統(tǒng)的信息處理機(jī)制是人工免疫算法的思想來源，還有更多的機(jī)理值得借鑒。補(bǔ)體系統(tǒng)是由存在于人或脊椎動(dòng)物血清與組織液中的一組可溶液性蛋白及存在于血細(xì)胞與其它細(xì)胞表面的一組膜結(jié)合蛋白和補(bǔ)體受體所組成的,具有精密調(diào)控機(jī)制的復(fù)雜的蛋白質(zhì)反應(yīng)系統(tǒng)[11]。在補(bǔ)體系統(tǒng)中,補(bǔ)體的激活是通過補(bǔ)體激活途徑進(jìn)行的,在這個(gè)過程中,補(bǔ)體不斷地自我分裂和結(jié)合,最終形成使靶細(xì)胞溶解破壞的攻膜復(fù)合物。從信息處理角度來看,補(bǔ)體的激活過程實(shí)際上就是補(bǔ)體不斷采用分裂、結(jié)合等行為,使補(bǔ)體不斷進(jìn)行重組,篩選出更好的個(gè)體的進(jìn)化優(yōu)化過程。因此,模擬補(bǔ)體激活原理提出可行的工程應(yīng)用算法,必是一條免疫優(yōu)化算法的新思路。

基于補(bǔ)體激活的原理,并結(jié)合克隆選擇原理,本文提出了一種解決無線傳感器網(wǎng)絡(luò)資源分配的免疫補(bǔ)體優(yōu)化算法。免疫補(bǔ)體算法中，靶細(xì)胞對(duì)應(yīng)優(yōu)化問題的目標(biāo)函數(shù)和約束條件。補(bǔ)體對(duì)應(yīng)優(yōu)化問題的最優(yōu)解。本算法中包含5種操作算子，即選擇、分裂、結(jié)合、親和突變及記憶算子。

2.2 算法具體實(shí)現(xiàn)

本文設(shè)計(jì)的算法基本步驟如下

1)初始化

設(shè)進(jìn)化代數(shù)k為0，隨機(jī)初始化種群A(k)，規(guī)模為n(n=|A|)；同時(shí)設(shè)置記憶種群M(k)，規(guī)模為s(s=n·b%),初始為從A(k)中隨機(jī)選取。

2)親和度評(píng)價(jià)

根據(jù)抗體的親和度函數(shù) (即第2節(jié)的優(yōu)化目標(biāo)函數(shù))，計(jì)算抗體親和度并按降序排列，選出前s個(gè)親和度值較高的抗體更新記憶種群M(k)。

3)終止條件判斷

如果達(dá)到最大進(jìn)化代數(shù)kmax,則算法終止，同時(shí)將M(k)保存的親和度最高的抗體通過編碼映射得到最佳結(jié)果；否則，轉(zhuǎn)步驟(4)。

4)克隆擴(kuò)增

EAi=f(Ai)/ρ(Ai).

對(duì)第q個(gè)抗體Mq(k)(1≤q≤s)克隆產(chǎn)生的抗體數(shù)目為

Nq=int(nt×EAi),

則第k代克隆產(chǎn)生的種群抗體個(gè)數(shù)數(shù)量記為

其中，int(*)為向上取整，nt(nt>s)為控制參數(shù)。

5)克隆分裂Tce

分裂算子是模擬補(bǔ)體系統(tǒng)的一種操作，是指對(duì)每個(gè)分裂抗體a=(x1x2…xm)(x1,x2,…,xm表示抗體的基因)，按照一定的分裂概率pe分裂成2個(gè)子抗體a1和a2。分裂算子表示為

其中，q為分裂次數(shù)，q=int(Q×Ea/∑Ea)。一般情況下，分裂規(guī)模與克隆規(guī)模相同。

6)結(jié)合算子Tcb

設(shè)2個(gè)抗體分別為a=(x1x2…xm)和b=(y1y2…yn)，結(jié)合算子可分為3類：正向結(jié)合、逆向結(jié)合、隨機(jī)結(jié)合[12]。其中:

正向結(jié)合抗體

c=Tcpb(a,b)=(x1x2…xmy1y2…yn);

逆向結(jié)合抗體

c=Tcnb(a,b)=(y1y2…ynx1x2…xm);

隨機(jī)結(jié)合抗體

c=Tcb(a,b)=Tcpb(a,b)∨Tcnb(a,b).

本文采用隨機(jī)結(jié)合。

7)克隆變異Tcm

采用高斯變異，依據(jù)概率pm對(duì)種群Y(k)進(jìn)行變異Tcm，得到抗體種群Z(k)。

8)克隆選擇Tcs

定義為A(k+1)=Tcs(Z(k))。從Z(k)中選擇親和度值高的個(gè)體組成下一代種群A(k+1)；轉(zhuǎn)步驟(2)。

3 仿真與結(jié)果分析

為了驗(yàn)證算法結(jié)果，在網(wǎng)絡(luò)仿真軟件OPNET下進(jìn)行仿真[13,14]。設(shè)監(jiān)測(cè)范圍為500 m×500 m，待探測(cè)目標(biāo)與感知節(jié)點(diǎn)在場(chǎng)地內(nèi)隨機(jī)位置分布，感知節(jié)點(diǎn)有效感知半徑為50 m，簇半徑為120 m，每個(gè)感知節(jié)點(diǎn)只能探測(cè)一個(gè)任務(wù)目標(biāo)，探測(cè)每個(gè)任務(wù)目標(biāo)需要3個(gè)以上的感知節(jié)點(diǎn)。本文算法中，最大進(jìn)化代數(shù)kmax=1 000；種群規(guī)模n=20，記憶單元規(guī)模s=0.4n；克隆控制參數(shù)nt=20，變異概率pm=0.1。算法通過檢測(cè)率進(jìn)行衡量，并與經(jīng)典的隨機(jī)分配算法[3]、動(dòng)態(tài)規(guī)劃方法[4]作了比較。

圖1和圖2顯示了在不同感知節(jié)點(diǎn)數(shù)目下，本文算法與相關(guān)算法的對(duì)比結(jié)果。由仿真實(shí)驗(yàn)結(jié)果可以看出：隨機(jī)分配算法性能較差，成功檢測(cè)到的目標(biāo)數(shù)較少，目標(biāo)檢出率較低，主要原因在于：隨機(jī)分配容易造成一個(gè)區(qū)域內(nèi)的大多數(shù)傳感器集中探測(cè)一個(gè)目標(biāo)而忽略了其他目標(biāo)，導(dǎo)致探測(cè)區(qū)域的空白。動(dòng)態(tài)規(guī)劃算法在節(jié)點(diǎn)數(shù)較少時(shí)可以起到良好的檢測(cè)效果，但當(dāng)待探測(cè)目標(biāo)數(shù)較多時(shí)檢測(cè)率下降較快。本文算法通過設(shè)計(jì)各種免疫克隆算子，有效保證了搜索的有效性，提高了算法的性能，成功檢測(cè)到的目標(biāo)數(shù)較多，檢出率較高，達(dá)到了較好的檢測(cè)效果。

圖1 待檢測(cè)目標(biāo)數(shù)與檢測(cè)出目標(biāo)數(shù)示意圖

圖2 待檢測(cè)目標(biāo)數(shù)與檢測(cè)率示意圖

4 結(jié) 論

無線傳感器網(wǎng)絡(luò)中的感知資源分配是NP難問題，智能優(yōu)化方法是求解此類問題的有效方法。基于此，本文提出了一種基于免疫補(bǔ)體優(yōu)化的無線傳感器網(wǎng)絡(luò)感知資源分配方法。借鑒免疫補(bǔ)體機(jī)制，設(shè)計(jì)了分裂、重組算子，采用了基于激勵(lì)度的克隆策略。實(shí)驗(yàn)結(jié)果表明：在不同的感知

節(jié)點(diǎn)數(shù)目下，本文算法成功檢測(cè)的目標(biāo)數(shù)較多，目標(biāo)檢測(cè)成功率在檢測(cè)數(shù)目較少時(shí)可達(dá)92 %，具有較好的檢測(cè)結(jié)果。

參考文獻(xiàn):

[1]Akyildiz I F,Su W,Sank Y,et al.Wireless sensor networks:A survey[J].Computer Networks,2002,38(4):393-422.

[2]張曉玲,梁 煒,于海斌.無線傳感器網(wǎng)絡(luò)傳輸調(diào)度方法綜述[J].通信學(xué)報(bào),2012,33(5):143-157.

[3]Merhi Z,Elgamel M,Bayoumi M.A lightweight collaborative fault tolerant target localization system for wireless sensor network-s[J].IEEE Transactions on Mobile Computing,2009,32(8):1690-1696.

[4]Boukerche A,Samarah S.Algorithms and protocols for wireless sensor networks[J].IEEE Transactions on Parallel and Distributed Systems,2008,19(3):865-869.

[5]Yang S,Zhang C,Fang Y G.Minimum energy scheduling in multi-hop wireless networks with retransmissions[J].IEEE Transactions on Wireless Communications,2010,9(1):348-355.

[6]周 杰,劉元安,吳 帆,等.基于混沌并行遺傳算法的多目標(biāo)無線傳感器網(wǎng)絡(luò)跨層資源分配[J].物理學(xué)報(bào),2011,60(32):058803.

[7]戚玉濤,劉 芳,焦李成.基于信息素模因的免疫克隆選擇函數(shù)優(yōu)化[J].計(jì)算機(jī)研究與發(fā)展,2008,45(6):991-997.

[8]Gong Maoguo,Jiao Licheng,Liu Fang,et al.Memetic computation based on regulation between neural and immune systems:The framework and a case study[J].Science China(Information Sciences),2010,45(11):2131-2138.

[9]Gong M G,Jiao L C,Zhang L N,et al.Immune secondary response and clonal selection inspired optimizers[J].Progress in Natural Science,2009,19:237-253.

[10] Chen Jie,Xin Bin,Peng Zhihong.Statistical learning makes the hybridization of particle swarm and differential evolution more efficient—A novel hybrid optimizer[J].IEEE Transactions on Evolutionary Computation,2008,6(3):239-251.

[11] 陳光柱,李志蜀,朱真才,等.一種免疫補(bǔ)體優(yōu)化算法[J].四川大學(xué)學(xué)報(bào):工程科學(xué)版,2009,41(2):192-199.

[12] Soldti P.On cross-layer design and resource scheduling in wireless networks[D].Stockholm,Sweden:KTH,2009.

[13] Malhotra B,Nikolaidis I,Nascimento M A.Aggregation convergecast scheduling in wireless sensor networks[J].Wireless Networks,2011,17(2):319-335.

[14] 張招亮,陳海明,黃庭培,等.無線傳感器網(wǎng)絡(luò)中一種抗無線局域網(wǎng)干擾的信道分配機(jī)制[J].計(jì)算機(jī)學(xué)報(bào),2012,31(3):215-219.