無線傳感器網絡中基于免疫補體優化的感知資源分配算法*

王獻榮， 蘇小玲

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

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

0 引 言

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

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

1 無線傳感器網絡的感知資源分配模型

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

0≤pm,n≤1.

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

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

am,n∈{0,1}.

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

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

因此，本文要優化的目標函數為

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

2 基于免疫補體優化的算法求解實現

2.1 免疫補體優化算法

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

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

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

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

2.2 算法具體實現

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

1)初始化

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

2)親和度評價

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

3)終止條件判斷

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

4)克隆擴增

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

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

Nq=int(nt×EAi),

則第k代克隆產生的種群抗體個數數量記為

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

5)克隆分裂Tce

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

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

6)結合算子Tcb

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

正向結合抗體

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

逆向結合抗體

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

隨機結合抗體

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

本文采用隨機結合。

7)克隆變異Tcm

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

8)克隆選擇Tcs

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

3 仿真與結果分析

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

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

圖1 待檢測目標數與檢測出目標數示意圖

圖2 待檢測目標數與檢測率示意圖

4 結 論

無線傳感器網絡中的感知資源分配是NP難問題，智能優化方法是求解此類問題的有效方法。基于此，本文提出了一種基于免疫補體優化的無線傳感器網絡感知資源分配方法。借鑒免疫補體機制，設計了分裂、重組算子，采用了基于激勵度的克隆策略。實驗結果表明：在不同的感知

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

參考文獻:

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

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

[7]戚玉濤,劉 芳,焦李成.基于信息素模因的免疫克隆選擇函數優化[J].計算機研究與發展,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] 陳光柱,李志蜀,朱真才,等.一種免疫補體優化算法[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] 張招亮,陳海明,黃庭培,等.無線傳感器網絡中一種抗無線局域網干擾的信道分配機制[J].計算機學報,2012,31(3):215-219.