WSN路由节点优化分布设计的免疫克隆算法

江 楠， 徐 秦

(中国人民解放军92124部队， 辽宁 大连 116023)

WSN路由节点优化分布设计的免疫克隆算法

江 楠， 徐 秦

(中国人民解放军92124部队， 辽宁 大连 116023)

对于无线传感器网络(WSN)路由节点的优化分布设计，人工免疫进化算法存在几何选择区域局限，为了缓解此问题，避免系统收敛于局部最优解，提出一种基于免疫克隆算子的设计方案。根据WSN节点覆盖原理，构建WSN路由节点自适应人工免疫分布模型，用免疫平衡机理计算染色体在每个节点部署网格中的信息浓度概率，采用克隆检测算法监测WSN网络中节点冗余浓度，以使每个WSN路由节点辐射信息素最大化，突破几何选择区域的限制，实现最优节点部署和覆盖。仿真实验表明，新算法能提高网络连通性和节点利用率。

无线传感器网络；路由节点；分布；免疫算法

无线传感器网络(Wireless Sensor Network, WSN)是一种利用分布式路由节点将数据传送到决策中心，从而感知和采集节点所处环境的数据信息的网络结构。WSN的路由节点分布设计决定着其生存周期和对环境信息的感知能力，优化智能的路由节点分布设计算法不但可以使WSN能自主感知实现数据信息的传递和决策，提高网络的连通性，而且能降低节点能耗，提高WSN网络系统的可靠性和稳定性，因此研究WSN路由节点的优化部署和分布设计算法具有重要的意义。

WSN的路由节点的优化部署和分布设计算法包括空间几何设计和智能优化遗传设计两个主要方面。文献[1]采用WSN多传感器融合处理办法实现对WSN节点的定位检测，分析实现WSN网络路由节点的分布设计，其控制算法采用粒子滤波算法实现节点自动控制，导致对WSN簇头节点分布控制效能限制较大，WSN节点分布准确度有待提高；文献[2]对WSN的通信协议进行了簇内节点优化设计，有效排除了恶意节点，从而实现对WSN节点的分布设计，但算法采用多重节点反复组合的方法进行WSN路由节点分布设计，导致节点利用效率不好；文献[3]中提出了一种基于相邻节点WSN节点分布信任值提取算法，实现对WSN数据的融合和分布覆盖优化，结合自组织神经网络系统，实现WSN节点定位，但算法在低信噪比和单接收节点调制中对WSN节点准确定位困难，导致WSN网络节点冗余，增大开销[4]；文献[5]采用粒子群进化算法进行路由节点分布设计，由于粒子群在进化迭代中免疫平衡算子存在几何选择区域的局限性，系统易收敛于局部最优解[6-10]。

本文基于免疫克隆算子提出一种WSN网络路由节点优化分布设计方案，并借助仿真实验验证新算法的性能。

1 WSN网络路由节点分布设计

1.1 WSN网络路由节点分布构建原理

首先研究WSN网络路由节点优化分布设计的原理，进行无线传感器网络节点分布设计的基本构建。对于在无线传感器网络中的每一个节点，有其自身的辐射半径，在辐射半径之外而又不能被其它网络节点辐射的为辐射盲区。因此，在对进行无线传感器网络组网中，要有效利用网络节点，实现资源分配最大化，网络覆盖最优化。节点均匀分布的传感器网络节点分布模型示意图如图1所示。

图1 节点均匀分布的传感器网络节点分布模型

在图1中，无线传感器网络路由节点假设为Z，该节点的辐射或称为覆盖半径为RZ，RZ为以Z为圆心的覆盖圆的半径，在该半径圆内，为有效覆盖区，能进行有效的通信覆盖。因此，与节点Z任意相邻的节点与保证在其信息发散区域内，需保证信息的有效传输和通信，对于节点Z的邻接节点，要按照特有和一定的顺序和方式进行排列组合，确保信息最优覆盖。在传统模型中，WSN网络中节点不得不频繁收集新的网络拓扑信息、重新计算调度方案并传送给每个节点，这将会消耗大量的能量，以致传统的数据集中式算法在实际应用过程中效率很低，无法实现有效准确和实时的信息采集和拓扑分析。

1.2 WSN路由节点系统模型构建

假设WSN有N个节点，节点同步分布实现对环境条件的监测和信息特征提取，路由节点均匀的分布在监测区域Ωη，分布模型如图1表示,其中节点分布网格中每两个节点之间的最小距离为d。根据节点类型，在网络模型中，节点分为Sink节点、监测点、传感器节点和无节点等类型，该模型采用四元组结构表示，以自顶向下的方式分层构造数据聚集树，优化节点分布设计，其目的在于以数量最少的连接节点将相距两跳的支配节点连接起来，形成一棵根在Sink节点的数据聚集树DAT。具体来说，在数据聚集树的构造过程中，假设Sink节点以数量最少的连接节点将相距两跳的支配节点连接起来，形成一棵数据聚集树后，则对于数据聚集树上某一支配点，只要将与之相距两跳、尚未加入数据聚集树的支配节点加入到数据聚集树。例如，假设有相距两跳的两个支配节点u和v，如果支配节点u先将与之相距两跳、尚未加入数据聚集树的支配节点加入到数据聚集树，则对于支配节点v，只要将D2(v)-D2(u)∩D2(v)中的点加入到数据聚集树即可，这是因D2(u)∩D2(v)中的支配点已通过支配节点u加入到数据聚集树。

支配节点u加入位置为ηn∈Ωη(n=1,2,…,N)，支配节点u先将与之相距两跳覆盖，得到每一个节点与进化算子中最优子节点位置相关的数据为x(ηn)，定义节点密度来表征分布节点覆盖点集的相关性为

E[x(ηp)x(ηq)]=ρ‖ηp-ηq‖,

(1)

其中ρ∈(0,1)表示Sink节点连通性代价系数，通过节点代价系数检测已覆盖的传感器节点，得到相应的空间相关系数，对WSN的已覆盖节点进行数据融合传递，WSN网格中心节点收到的节点数据信息素为

(2)

(3)

根据构建的WSN路由节点系统模型，以下分析WSN网络路由节点优化分布设计。

2 路由节点分布算法与优化实现

2.1 自适应人工免疫节点分布算法

WSN网络路由节点分布设计，旨在按照一定的节点排列方法，以最为经济的网络节点实现最大覆盖率的辐射区域，从而完成传感器节点信号覆盖的最优化。构建评价指标体系，评价传感器节点优化覆盖的性能，对研究传感器节点优化覆盖算法具有检测和评估价值。WSN节点在寻优最优位置信息的时候，可通过模拟生物进化的人工免疫行为，实现信息位置的最佳匹配。在此给出自适应人工免疫节点分布算法。

假设融合中心有各传感器节点得到的数据y=(y1,y2,…,yN)T，采用粒子群局部搜索算法，得到目标节点信息偏差x(η)(η∈Ωη)，节点覆盖区域抗体浓度评价均方误差(Mean Squared Error， MSE)估计值为

(4)

(5)

其中

rη=E[x(η)xs],

xs=(x(η1),x(η2),…,x(ηN))T,

(6)

(7)

(8)

其中γ0表示单位区域的信噪比。

采用目标免疫的方法，对WSN节点进行目标免疫克隆节点伴随指导，可突破节点寻优过程中对空间区域的限制。

采用自适应人工免疫节点分布算法进行WSN节点分布设计的流程可描述为：首先用染色体所求的节点更新信息素解，把这些所需的解组成一个初始群体并放置在这个集合的环境中；然后计算每个个体的适应度，淘汰适应度较低的小集群，复制高适应度的个体，按照设定概率进行交叉和变异两种基因操作；最后通过以上步骤产生出的新个体就是所有样本种群的下一代。这样不停的进化，下一代比上一代更优，适应度更高，最后结果会收敛到一个最优的个体上，所需求解问题的最优解就是这个最优的个体。

具体的计算准备流程包括：(1)确定计算方案，即确定无线传感器网络节点的整个搜索空间的计算方式。(2)确定适应值的范围，即通过一个适应度函数来对小集群群体中的每个特征量的适应度进行计算。(3)确定参数和变量在控制算法的选取，即选取小集群种群的规模M、最大代数N、交叉概率Pc和变异概率Pm等参数。(4)确定算法的收敛的标准，以达到结束或者进行结果判断实现最佳搜索和信息的覆盖。

算法流程如图2所示。

图2 自适应人工免疫节点分布算法流程

根据传统的分布设计算法中，变异交叉执行算子在进化迭代中免疫平衡算子存在几何选择区域的局限性，系统易收敛于局部最优解，因此需要对算法进行改进。

2.2 算法改进与优化实现

引入免疫克隆算子，对传统的人工免疫进化WSN节点分布设计算法进行改进。

基于WSN节点覆盖原理，构建WSN网络路由节点自适应人工免疫分布模型，用免疫平衡机理计算染色体在每个节点部署网格中的信息浓度概率，表示为

(9)

采用克隆检测算法监测WSN网络中节点冗余浓度，在此引入克隆变异算子，优化节点信息素迭代更新过程，克隆变异算子为

(10)

此时每个WSN路由节点辐射信息素为

(11)

即采用最大似然估计，得到克隆检测算法估计出每个WSN路由节点辐射最大信息素。监测WSN网络中节点冗余浓度，使每个WSN路由节点辐射信息素最大化，从而可有效突破几何选择区域的限制，实现最优节点部署和覆盖，得到改进后的覆盖半径下节点密度对MSE的影响

(12)

3 仿真实验与结果分析

仿真实验以100 m × 100 m二维平面监测区域为研究对象进行，WSN网络路由节点通过免疫克隆优化迭代的实现最优节点分布，其中，仿真平面为正方形二维平面，该二维平面为无线传感器网络节点拓扑覆盖研究区域。免疫群初始的群体个数即随机分布的传感器节点个数假设为n=100, 交叉概率Pc取值为0.40～0.99，变异概率Pm一般定为0.05。仿真实验中，对克隆检测算子进行免疫平衡设计，在仿真过程中对相关数据，比如覆盖率、覆盖度、传感器节点个数进行了详细记录。根据迭代，最后确定最佳迭代次数选择为N=300。在待检测覆盖区域W中，假设需要设置Q同等性能指标的节点，各个传感节点在区域W中的坐标参数假设为(xi,yi)，各个传感节点由于性能参数相同，故而其覆盖半径是相同的，这里假设为r，设定网格大小为24，网络规模为20×20，采用改进算法和传统方法对WSN网络路由节点设计中节点密度与空间相关性以及信息素饱和度之间的关系进行仿真。在WSN网络中不同节点数量下得到节点密度对节点信息素饱和度均方根误差MSE关系如图3所示。可见，MSE随节点密度单调递减，节点密度越高，空间相关性就越强，则估计精度越高。而采用改进方法，节点分布饱和度更大，更能有效逼近最优值，网络连通性更好。

(a) 传统方法

采用改进方法仿真得到最优节点密度随节点数变化关系如图4所示。可见，采用改进方法能快速实现最优节点密度设计，收敛性好，能在最少节点下实现节点分布和信息传输最优，这说明采用改进算法进行WSN路由节点分布设计，网络连通性和节点利用率都将获得大幅度提高。

图4 最优节点密度随节点数变化关系

4 结 语

针对WSN网络路由节点分布优化设计的问题，提出一种引入免疫克隆算子的WSN网络路由节点优化分布设计方案，基于WSN节点覆盖原理，构建WSN网络路由节点自适应人工免疫分布模型，用免疫平衡机理计算染色体在每个节点部署网格中的信息浓度概率，采用克隆检测算法监测WSN网络中节点冗余浓度，使每个WSN路由节点辐射信息素最大化，研究得出，采用该算法进行WSN路由节点分布设计，节点信息素饱和度高，WSN连通性和节点信息覆盖性较好。

[1] 龚娟,段树华.PSO算法和神经网络的入侵检测系统设计[J].计算机测量与控制,2010,18(8): 1924-1927.

[2] 杨建华,王龙飞.基于FPGA的交通流量视频检测系统设计[J].计算机与数字工程,2013,41(11): 1811-1813.

[3] 董慧慧,郭亚军.一种基于节点多角度信任的无线传感器网络[J].计算机科学,2009,36(9):43-45.

[4] 赵娟,赵蔷,吴粉霞.基于自组织映射神经网络的图像检索算法[J].科技通报,2013,29(2):55-57.

[5] 杨海霞.基于改进数据过滤算法的异构数据库优化挖掘技术[J].科技通报,2013,29(6):125-127.

[6] 朱珍.基于神经网络集成分类器预处理的支持向量机分类算法[J].科技通报,2013,29(4):26-30.

[7] 吴光荣,柳书涛,章剑雄.基于ZigBee的无线传感器网络数据管理平台[J].电子科技,2009,22(2):64-67.

[8] 刘家亮,王海燕,姜喆,等.垂直线列阵结构对PTRM阵处理空间增益的影响[J].鱼雷技术,2010, 18(4):263-267.

[9] 韦然.无线传感器网络节点的设计与实现[J].电子科技,2012,25(1):31-35.

[10] 梁青,熊伟,韩昊澎.各向异性无线传感器网络DV-Hop算法性能仿真[J].西安邮电大学学报,2013,18(5):31-36.

[责任编辑:王辉]

WSN routing node distribution design based on immune clone pptimization

JIANG Nan, XU Qin

(Unit 92124 of PLA, Da lian 116023, China)

For WSN to optimize the design of the distribution of routing nodes, the artificial immune evolutionary algorithm has limitation of geometry selected area limits, thus lead system converges to local optimal solution. An improved immune clone algorithm is proposed in this paper. According to the principle of WSN node coverage, an adaptive artificial immune WSN routing nodes distribution model is built. The information probability of concentration of chromosome is calculated by the immune balance mechanism in each node deployment in the grid. WSN nodes redundant concentration in network is monitored by using the clone detection algorithm. Each WSN routing node radiation pheromones is therefore maximized to breakthrough the limitation of geometry selected area and to realize the optimal node deployment and coverage. Simulation experiments show that the new algorithm can improve the utilization rate of network connectivity and node.

wireless sensor network, routing node, distribution, immune algorithm

10.13682/j.issn.2095-6533.2014.05.015

2014-06-10

江楠(1982-)，女，硕士，助理工程师，从事通信工程研究。E-mail：66757588@qq.com 徐秦(1972-)，女，高级工程师，从事通信工程研究。E-mail:ariaxu@hotmail.com

TN 926; TP 212

A

2095-6533(2014)05-0077-05