无线传感器网络中基于免疫补体优化的感知资源分配算法*

王献荣， 苏小玲

(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.