無線傳感器網(wǎng)絡中基于免疫補體優(yōu)化的感知資源分配算法*

王獻榮， 蘇小玲

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

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

0 引 言

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

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

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

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

0≤pm,n≤1.

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

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

am,n∈{0,1}.

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

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

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

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

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

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

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

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

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

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

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

本文設計的算法基本步驟如下

1)初始化

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

2)親和度評價

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

3)終止條件判斷

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

4)克隆擴增

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

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

Nq=int(nt×EAi),

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

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

5)克隆分裂Tce

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

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

6)結(jié)合算子Tcb

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

正向結(jié)合抗體

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

逆向結(jié)合抗體

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

隨機結(jié)合抗體

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

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

7)克隆變異Tcm

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

8)克隆選擇Tcs

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

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

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

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

圖1 待檢測目標數(shù)與檢測出目標數(shù)示意圖

圖2 待檢測目標數(shù)與檢測率示意圖

4 結(jié) 論

無線傳感器網(wǎng)絡中的感知資源分配是NP難問題，智能優(yōu)化方法是求解此類問題的有效方法?；诖耍疚奶岢隽艘环N基于免疫補體優(yōu)化的無線傳感器網(wǎng)絡感知資源分配方法。借鑒免疫補體機制，設計了分裂、重組算子，采用了基于激勵度的克隆策略。實驗結(jié)果表明：在不同的感知

節(jié)點數(shù)目下，本文算法成功檢測的目標數(shù)較多，目標檢測成功率在檢測數(shù)目較少時可達92 %，具有較好的檢測結(jié)果。

參考文獻:

[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)絡傳輸調(diào)度方法綜述[J].通信學報,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]周 杰,劉元安,吳 帆,等.基于混沌并行遺傳算法的多目標無線傳感器網(wǎng)絡跨層資源分配[J].物理學報,2011,60(32):058803.

[7]戚玉濤,劉 芳,焦李成.基于信息素模因的免疫克隆選擇函數(shù)優(yōu)化[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] 陳光柱,李志蜀,朱真才,等.一種免疫補體優(yōu)化算法[J].四川大學學報:工程科學版,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)絡中一種抗無線局域網(wǎng)干擾的信道分配機制[J].計算機學報,2012,31(3):215-219.