一种基于免疫克隆选择的无线传感器网络路由优化方法

摘要

本发明涉及物联网技术领域，具体涉及一种基于免疫克隆选择的无线传感器网络路由优化方法。本发明包括：在first order射频模型的基础上建立多跳通信的能量消耗模型；将源节点与所有组播节点的通信路由视为一颗组播树，在满足约束条件下，能量消耗值最小的组播树即为最优路径；将每棵组播树作为免疫系统中的一个抗体，组播树中源节点到组播节点的一条路由为抗体的一个基因；确定通信节点的最佳数量；建立组播源节点与所有组播节点之间的通达路由备选路径集。本发明根据路由优化与人工免疫系统之间的内在关联，建立路由优化问题求解与人工免疫响应五元素结构之间对应关系，提高优化速度，显著减少无线传感器网络的自愈时间。

说明书

技术领域

本发明涉及物联网技术领域，具体涉及一种基于免疫克隆选择的无线传感 器网络路由优化方法。

背景技术

无线传感器网络是由几千至几万个部署在监测区域内的传感器节点组成， 该网络是一个多跳的自组织网络系统，并通过无线通信的方式传输数据。传感 器节点之间协作的感测、收集、传递、处理监控区域内信息，并将检测到的数 据发送给基站。

无线传感器网络中的传感器节点在网络中对监控区域进行监控，并将感测 到的变化信息理由路由协议将数据信息从源传感器节点通过网络转发到目的节 点。路由协议在无线传感器网络通信中起到两方面的作用：第一，建立一条从 源节点到目的节点的路由路径；第二，将收集到得数据汇总存储到并按照已建 立的最优路径正确转发。无线传感器网络的传感器节点较特殊：节点位置随机， 不可替换，也不能更换电池，因此无线传感器网络的路由算法需要考虑能耗， 丢包率等网络性能。路由算法的目标即为建立一条能够平衡网络中节点能量的 消耗，同时提高网络中能量利用率，并能够延长网络的生命周期的路由路径。

图2是无线传感器网络基本体系结构，当传感器节点感知数据后，通过其 它节点以单跳或者多跳的方式传输给汇聚节点sink，再经互联网到达监控中心， 在监控中心对网络进行配置和管理，实现远程数据的采集与获取。

传感器节点结构如图3，它是构成网络系统的关键要素，由传感器、处理器、 射频部分组成，分别用于监测过程中的信息采集与转换、信息读取及信息交换。 按能耗从大到小的顺序来分，节点通常有发送、接收、空闲和睡眠四种工作状 态。节点通常采用干电池或者微型电池供电，其能量有限，在许多场合，由于 能耗耗尽，节点能量维护、补充难以进行，导致节点失效，难以达到预期的监 测目标，因此，在实际应用中，必须考虑能量的效率，实现网络生存期最大化。

发明内容

针对现有技术中存在的上述不足之处，本发明要解决的技术问题是提供一 种能够提高无线传感器网络系统的故障处理能力、增强健壮性与鲁棒性、具有 良好应用前景的基于人工免疫的无线传感器网络路由优化方法。

本发明为实现上述目的所采用的技术方案是：一种基于免疫克隆选择的无 线传感器网络路由优化方法，包括以下步骤：

建立能耗模型，在firstorder射频模型的基础上建立多跳通信的能量消耗模 型；

建立虚拟组播树，将源节点与所有组播节点的通信路由视为一颗组播树， 在满足约束条件下，能量消耗值最小的组播树即为最优路径；

生成抗体，将每棵组播树作为免疫系统中的一个抗体，组播树中源节点到 组播节点的一条路由为抗体的一个基因；

优化节点数量，确定通信节点的最佳数量；

生成路由算法，组播树中源节点首先广播一个路由请求信息给其邻域节点， 邻域节点收到请求信息后，记录请求包经过该节点，一方面与组播源节点建立 路由通路，另一方面继续广播该请求信息给其邻域节点，建立与之相应的路由 通路，依此类推，直至到达组播节点，通过遍历所有组播节点，建立组播源节 点与所有组播节点之间的通达路由备选路径集。

所述多跳通信的能量消耗模型为：

$\mathrm{Ab}=\underset{i=0}{\overset{N-1}{\Sigma }}{P}_i(u_i,v_i)$

其中，u_i,v_i为无线传感器网络中的通信节点，N为通信所需的跳数，Pi(u_i,v_i) 为节点u_i与v_i节点通信所消耗的能量，Ab为此多跳通信所消耗的总能量。

所述约束条件为：

(1)邻域节点的距离；

(2)邻域节点的剩余能量；

(3)到达目的节点的跳数；

其中，邻域节点的距离所代表的约束因子，F₁为：

$F_1=\frac{R-d(u,v)}{R}$

R为节点的邻域半径，为两个节点能够通信的最大距离，节点u与邻域节点 v之间的距离为d(u,v)；

在满足F₁＞0的条件下，取邻域节点的剩余能量较大且到达目的节点的跳数 较少的组播树为满足约束条件的组播树。

所述组播树中的源节点为汇聚节点，组播节点为监测区域的传感节点。

所述抗体用如下规则来表示：

Ab＝{sink→CN₁,sink→CN₁→CN₂,sink→CN₁→MN→CN₃,sink→CN₁

→MN→CN₄}

其中，sink为汇聚节点，CN_i为传感节点，MN为中转节点。

所述优化节点数量包括以下步骤：

步骤1：在抗体空间Ab中的某个传输路径上任选一个节点记为T，计算它 与其余节点的欧氏距离dist；

步骤2：将得到的欧氏距离dist与领域半径R进行比较，判断哪些是邻域 节点，哪些是非邻域节点；

步骤3：计算节点T与事件信息源及其它邻域节点和非邻域节点之间的亲 密度，将三种亲密度求和获得节点总亲密度ρ；

步骤4：在汇聚节点sink设置一个阈值V_ini，根据V_ini与ρ大小判定节点是否 被激活，设置阈值V_ini的初始值，使得网络中所有传感器节点都成为激活节点；

步骤5：通过公式$D\left(M\right)={\rho }_S^2-\frac{1}{M(1+{\rho }_S)}(2{\Sigma }_{i=1}^M{\Sigma }_{j\ne i}^M{\rho }_{\mathrm{ij}}-1)$计算事件信息源 在汇聚节点的误差，作为免疫系统的抗原；其中，ρ_S为T节点与sink节点的紧 密度，ρ_ij为T节点与通信线路上的其他节点的亲密度，M为通信线路的跳数；

步骤6：将初始阈值增加ΔV，并将新的阈值广播给网络中每个节点，观察 抗原的变化，若抗原无变化，则减少通信节点的数量；

步骤7：随着初始阈值V_ini继续增加，满足约束条件的通信节点的数量逐渐 减少，当达到抗原最大约束值时，停止增加初始阈值V_ini，并将最后的V_ini广播给 所有节点；

步骤8：将V_ini与节点亲密度进行比较，若ρ＞V_ini，则该节点被激活参与事 件信息的传递，若ρ＜V_ini，该节点不被选定参与信息的传递。

所述路由生成算法包括以下步骤：

步骤1：汇聚节点sink作为组播源节点，广播路由建立信息；

步骤2：计算汇聚节点与其它节点的欧氏距离，由邻域半径确定相应的邻 域节点集；

步骤3：判断邻域节点是否大于链路通信阈值，若是，则建立与该邻域节 点的备选路径，否则，丢弃该路径；

步骤4：按照用邻域节点取代源节点，使之成为新的源节点；

步骤5：判断当前节点是否是组播节点，再判断是否满足跳数要求，若是， 说明路由已建立，否则返回步骤2，继续寻找与其它邻域节点的路由。

本发明具有以下优点及有益效果：

(1)在分析无线传感器网络通信机理的基础上，建立组播与节点通信路由 之间的联系，给出节点通信能耗模型与最优路由评价标准，结合虚拟组播树， 提高了无线传感器网络的健壮性；

(2)利用生物免疫系统克隆选择原理进行详细分析，包括克隆选择、克隆 繁殖、免疫进化和学习记忆，应用于无线传感器网络，提高其的故障分析与处 理能力；

(3)根据路由优化与人工免疫系统之间的内在关联，建立路由优化问题求 解与人工免疫响应五元素结构之间对应关系，提高优化速度，显著减少无线传 感器网络的自愈时间。

附图说明

图1为人工免疫的无线传感器网络路由优化方法流程；

图2为无线传感器网络体系结构图；

图3为无线传感器模块结构图；

图4为无线传感器网络抗体节点模型；

图5为虚拟组播树生成图；

图6为节点免疫自适应调节算法流程图；

图7为基于邻域优先的人工克隆免疫路由算法流程图。

具体实施方式

下面结合附图及实施例对本发明做进一步的详细说明。

如图1所示，免疫克隆算法的主要思想是：以初始群体为中心，通过克隆、 变异操作，将单一群体扩展为多群体，然后从父抗体中选择品质优良的抗体作 为抗体群进行局部范围搜索，节省搜索时间，利用抑制建立群体间联系，消除 克隆变异中相似度较大的抗体，提高全局搜索范围，通过局部和全局范围的共 同搜索，寻找可能存在最优解的区域。

人工免疫克隆选择算法进行路由优化时，路由选择的约束条件用与其密切 相关的距离及剩余能量来衡量，只有在其通信范围内且有足够剩余能量的节点 才能通信。首先对抗体中的单个基因进行检测，若其中有一个为零，则包含该 基因的抗体被舍弃，同时，跳数过多的基因也被丢弃，防止因抗体种群规模过 大而浪费搜索时间。抗体规模影响并行运算速度，决定运算的复杂度，为了维 持抗体数量的稳定性，降低计算的复杂性，每次克隆抗体的总量是随其亲和度 的大小自适应确定的，这样既显示了抗体适应抗体的能力，又能扩大种群选择 范围。变异阶段，各子群体间进行局部信息交换，虽然抗体中基因的种类改变， 但并没有破坏组播树的完整性，组播树的结构随着基因变异也在不断动态变化 中，抗体的克隆与变异使得算法快速收敛于全局最优解。

为了预防最优解局部收敛，算法主要采取如下措施来产生和维持抗体种群 的多样性：

(1)人工免疫克隆选择算法采用克隆与变异的单性繁殖搜索方式，没有交 叉操作，可以避免因交叉带来对抗体的干扰和破坏，防止抗体结构的趋同；

(2)克隆是在抗体本身基础上进行了，不仅保留了抗体本来属性，而且扩 大搜索区间，维护了种群的多样性；

(3)抗体种群是与抗原作用的基本种群，强调全局寻优，而克隆选择是在 抗体种群的基础上进行局部搜索，通过各局部最优个体的比较、组合和筛选， 获得全局最优，即使单个子群出现早熟，也不会受到影响其他种群的进化；

(4)算法输出的是克隆变异后的抗体种群，代表了局部最优解的分布，反 应了抗体动态作用的过程，既保存了抗体种群的进化特征，也为向最优解搜索 提供了目标。

路由优化算法中，节点与节点之间的链路选择是通过源节点发送消息包来 建立的，只有通信距离及其能量满足要求，两节点之间的链路才认为可靠，通 过尝试搜索，直至到达组播节点，邻域优先通信算法生成备选路径集是一个动 态的搜索过程，若组播树中某个节点因能耗耗尽或者其它原因导致故障退出网 络，或者非组播树上的一个中间节点需要加入到该组播树中，算法能自适应邻 域节点的变化，寻找一棵最合适的组播树使之对应路由最优，因此，算法具有 较好的鲁棒性。

无线传感器网络路由优化算法中目标函数和约束条件、最优解与目标函数 的匹配程度分别对应于免疫系统的抗原、抗体、抗原与抗体之间的亲合度。

1建立能耗模型

与传统的无线网络相比，能耗受限是无线传感器网络的最大特点，当组播 节点与源节点进行数据通信时，传感器节点会损失能耗，由于传统的无线网络 在节点和网络方面与无线传感器网络差别较大，直接采用传统无线网络的能量 模型不能完全反映无线传感器网络的特性。为客观、正确地衡量网络路由能耗 性能，很有必要选取合适能量模型来表征通信能耗特征。基于免疫优化与无线 传感器网络实现求最优解之间的映射关系，建立无线传感器网络能耗模型。

firstorder射频模型是一种能较好反映节点通信能耗特性的模型。在距离为 d范围，传递数据包的能耗由发射机工作时电路射频损耗E_Tx(d)和接收机作时 电路射频损耗E_Rx(d)表示，它们根据射频电路基带参数确定。

传感器节点的通信模块存在发送、接收、空闲和睡眠4种状态，不同状态 的能量消耗水平差别较大。研究表明，无线传感器网络通信时能量开销要远远 大于数据计算时的能量开销，因此在进行路由设计时最需要考虑节点在发送和 接收时的能量消耗情况，而节点在空闲和睡眠时的状态能量消耗忽略不计。

根据此射频能耗模型，假设u和v为网络中的通信节点，u和v一跳通信的 能耗P(u,v)＝P_t(u,v)+P_r，其中P_t为发射电路一次发射能量消耗P_t＝E_Tx(d)·t， P_r为发射电路一次发射能量消耗P_r＝E_Rx(d)·t。t为发射与接收数据包的时间。

若u和v之间存在N个节点时，对于多跳通信的能量消耗为：

$\mathrm{Ab}=\underset{i=0}{\overset{N-1}{\Sigma }}{P}_i(u_i,v_i)$

通过上式可以看出，P(u,v)的大小与距离d及数据传递速率t有关。d和t 越大，一跳通信能耗也越大，所以，为了节省通信能耗，要尽量选择距离较近 的节点进行通信，且要减少发送和接收数据的长度。

2建立虚拟组播树

无线传感器网络中，源节点与所有组播节点的通信路由可视为一棵组播树， 如图5所示。路由问题就可以转化为：在满足约束条件下，寻找一个棵组播树， 使之对应能量消耗的值最小即为所求最优路由。

当节点之间的距离超过了节点的通信范围以及自身的能量很少时，两节点 之间的数据传输将变得很不可靠，同时，对于一条从源节点到组播节点的路由 来说，跳数也影响信息传输的可靠性，跳数过多，信息丢失的风险加大，概括 起来，组播节点与sink节点之间的可靠路由受下述三个条件约束：

(1)邻域节点的距离

(2)邻域域节点的剩余能量

(3)到达目的节点的跳数

人工免疫克隆选择算法进行路由优化时，路由选择的约束条件用与其密切 相关的距离及剩余能量来衡量，只有在其通信范围内且有足够剩余能量的节点 才能通信。首先对抗体中的单个基因进行检测，若其中有一个为零，则包含该 基因的抗体被舍弃，同时，跳数过多的基因也被丢弃，防止因抗体种群规模过 大而浪费搜索时间。抗体规模影响并行运算速度，决定运算的复杂度，为了维 持抗体数量的稳定性，降低计算的复杂性，每次克隆抗体的总量是随其亲和度 的大小自适应确定的，这样既显示了抗体适应抗体的能力，又能扩大种群选择 范围。变异阶段，各子群体间进行局部信息交换，虽然抗体中基因的种类改变， 但并没有破坏组播树的完整性，组播树的结构随着基因变异也在不断动态变化 中，抗体的克隆与变异使得算法快速收敛于全局最优解。

假设节点的邻域半径为R，节点u与邻域节点v之间的距离为d(u,v)，则 距离指标约束因子F₁为：

$F_1=\frac{R-d(u,v)}{R}$

设邻域节点v的消耗能量和初始能量分别为E_com和E_ini则剩余能量指标约束 因子F₂为：

$F_2=\frac{E_{\mathrm{ini}}-E_{\mathrm{com}}}{E_{\mathrm{ini}}}$

实际应用中F₁和剩余能量指标约束因子F₂尽可能取得较好的水平，以维持 节点单跳指标衡量值较高，可以看出，只要F₁和F₂其中一项指标值为零，不论 其余的指标值有多高，总的衡量值都将为零，该节点不能当作邻域节点，从而 可以有效避免选择那些距离很近但剩余能量很低的邻域节点作为下跳路由节点。

若源节点与一个组播节点的通信能耗为P_i，网络中共有M个组播节点，则 与所有组播节点进行通信总能耗为：

$P=\underset{i=1}{\overset{M}{\Sigma }}{P}_i$

3生成抗体

如图4所示，对于无线传感器网络将sink节点视为组播源节点，监测区域 的传感节点CN_i视为组播节点，MN为中转节点。根据虚拟组播路由中人工免疫 对应关系，每棵虚拟组播树为免疫系统中的一个抗体，虚拟树中源节点到组播 节点的一条路由为抗体的一个基因。抗体用如下规则来表示：

Ab＝{sink→CN₁,sink→CN₁→CN₂,sink→CN₁→MN→CN₃,sink→CN₁

→MN→CN₄}

以X＝{x₁,x₂,…,x_m}为无线传感器网络路由优化问题min{f(e^-1(A)):A∈I}，其中， 集合I称为抗体空间，有限长度的字符串A＝a₁a₂…a_l是抗体编码，记为A＝e(X)， X为抗体A的解码，记为X＝e^-1(A)，抗体与抗原的亲合度函数用f表示，min 表示对目标函数求最小值。

抗体种群空间表示为：

Iⁿ＝{A:A＝[A₁A₂…A_n],A_k∈I,1≤k≤n}

n为正整数，表示抗体种群规模，抗体群A＝[A₁A₂…A_n]为抗体A的n元组， 是抗体种群空间Iⁿ上的一个点。

4优化节点数量

在确定路由算法之前，可通过抗体自适应抗原刺激的免疫自适应调节算法 来确定通信节点的最佳数量，如图6所示，优化算法具体步骤为：

步骤1：在抗体空间Ab中的某个传输路径上任选一个节点记为T，计算它 与其余节点的欧氏距离dist；

步骤2：将得到的欧氏距离dist与领域半径R进行比较，判断哪些是邻域 节点，哪些是非邻域节点；

步骤3：计算节点T与事件信息源及其它邻域节点和非邻域节点之间的亲 密度，将三种亲密度求和获得节点总亲密度ρ；

步骤4：在汇聚节点sink设置一个阈值V_ini，根据V_ini与ρ大小判定节点是否 被激活，设置阈值V_ini的初始值。使得网络中所有传感器节点都成为激活节点；

步骤5：通过公式$D\left(M\right)={\rho }_S^2-\frac{1}{M(1+{\rho }_S)}(2{\Sigma }_{i=1}^M{\Sigma }_{j\ne i}^M{\rho }_{\mathrm{ij}}-1)$计算事件信息源 在汇聚节点的误差，作为免疫系统的抗原；

步骤6：将初始阈值增加ΔV(V_ini＝V_ini+ΔV)，并将新的阈值广播给网络中每 个节点，观察抗原的变化，若抗原无变化，则减少通信节点的数量，说明以当 前的抗体就能响应抗原的变化，继续增大阈值直到抗原到达约束范围；

步骤7：随着初始阈值V_ini继续增加，满足约束条件的通信节点的数量逐渐 减少，当达到抗原最大约束值时，停止增加初始阈值V_ini，并将最后的V_ini广播 给所有节点；

步骤8：将V_ini与节点亲密度进行比较，若ρ＞V_ini，则该节点被激活参与事 件信息的传递，若ρ＜V_ini，该节点不被选定参与信息的传递。

5生成路由算法

克隆选择算法的实现方式是：一方面通过抗体与抗原之间的亲和度，实现 个体间的竞争，另一方面利用抗体与抗体间亲和度调节，抑制过度竞争，保持 抗体种群的多样性，并通过个体增生为某一抗体同时采用多种变异和重组策略 提供了可能。因此，克隆选择算法的本质上利用基因操作(变异)在单一抗体 周围产生一个变异解的群体，利用局部搜索增加了抗体与抗原亲和度的可能性； 克隆选择操作通过局部寻优，实现种群的压缩，保证了抗体种群中的最优解。 克隆选择算法就是通过空间的扩张与压缩，将局部搜索与全局搜索相结合实现 问题求解的。

根据免疫抗体基因表示方法，源节点到一个组播节点的路由即为抗体的一 个基因。源节点到组播节点的路由可利用邻域优先通信算法来生成，基本思想 为：组播源节点首先广播一个路由请求信息给其邻域节点，邻域节点收到请求 信息后，记录请求包经过该节点，一方面与组播源节点建立路由通路，另一方 面继续广播该请求信息给其邻域节点，建立与之相应的路由通路，依此类推， 直至到达组播节点，通过遍历所有组播节点，建立组播源节点与所有组播节点 之间的通达路由备选路径集。

如图7所示，基于邻域优先通信的人工免疫克隆算法具体执行过程为：

步骤1汇聚节点sink作为组播源节点，广播路由建立信息；

步骤2计算汇聚节点与其它节点的欧氏距离，由邻域半径确定相应的邻 域节点集；

步骤3判断邻域节点是否大于链路通信阈值，若是，则建立与该邻域节 点的备选路径，否则，丢弃该路径；

步骤4按照用邻域节点取代源节点，使之成为新的源节点；

步骤5判断当前节点是否是组播节点，再判断是否满足跳数要求，若是， 说明路由已建立，否则返回步骤2，继续寻找与其它邻域节点的路由。