一种异构无线传感器网络的容错路由恢复方法

摘要

本发明涉及一种异构无线传感器网络的容错路由恢复方法，在异构无线传感器网络的簇内某条路径由于节点故障断开时，构建簇内多路径路由生成图，进行路径编码；采用多粒子群免疫协同优化算法来选择最优替代路径，进行路由恢复；采用基于该算法的协议来维护该网络系统。该多粒子群免疫协同优化算法具有全局搜索能力较强、求解精度较好、收敛速度快等特点。本发明提高了异构无线传感器网络的容错能力，通过快速构建最优替代路径以提高数据传输成功率，并延长网络的生存时间。

说明书

技术领域

本发明属无线传感器网络技术领域，特别是涉及一种异构无线传感器网络的容错路由恢复方法。

背景技术

异构无线传感器网络(heterogeneous wireless sensor networks，H-WSNs)在无线传感器网络(wireless sensor networks，WSNs)中扮演着重要角色。它一股包含两种类型的传感器节点：大量能量受限的普通节点随机分布在监测区域，少量能量富裕、可靠性高的超级节点布置在已知位置。超级节点作为周围多个普通节点的簇头，使得整个网络形成两层结构。H-WSNs相比同构WSNs可以提高数据传输成功率，减少传输过程中的能量消耗。但实际应用中，传感器故障等会导致网络链路断裂，使系统遭到破坏。因此为了提高网络的生存周期，容错路由机制，尤其是路由恢复机制对H-WSNs的网络维护十分重要，是WSNs研究热点之一。典型的H-WSNs容错路由算法包括GATC_k、EEHC、CPEQ、ICE等，这些算法很少考虑簇内的多路径路由的维护，且WSNs的路由容错问题作为一种NP完全问题，这些启发式的确定性方法往往只能得到近似的最优路径结果，易于陷入局部最优。

粒子群算法作为新型的智能算法，基本思想就是模拟生物界鸟群觅食现象，通过模拟这些群体智能行为而对问题求解空间进行全局搜索，找到全局最优解。和其他智能算法相比，粒子群算法更加容易实现，运行效率更高，因此近年来得到广泛关注。但粒子群存在早熟收敛问题，在优化初期收敛速度较快，而随着优化过程的继续，在搜索后期易陷入局部最优，收敛速度下降，精度较低。因此本发明采用主从式多群体协同进化思想来平衡粒子群的局部和全局搜索能力，采用免疫思想增加粒子(抗体)的多样性，迅速跳出局部极值解，快速收敛于全局最优解。

发明内容

本发明所要解决的技术问题是提供一种采用多粒子群免疫协同优化算法(multi-particle-swarm immune cooperative algorithm，MPSICA)对H-WSNs的路径选择，路由恢复问题进行优化，以迅速构建最优替代路径，提高H-WSNs的数据传输成功率，增加网络生存时间的异构无线传感器网络的容错路由恢复方法。

本发明解决其技术问题所采用的技术方案是：提供一种异构无线传感器网络的容错路由恢复方法，在所述的异构无线传感器网络的簇内有路径因为节点故障断开时，采用多粒子群免疫协同优化算法来选择最优路径，进行路由恢复；采用基于所述的多粒子群免疫协同优化算法的协议来维护异构无线传感器网络系统，具体包括以下步骤：

(1)构建簇内多路径路由图G(V，E)，其中V是簇内节点集合，E是簇内节点间链路集合；源节点n_s∈V，超级节点即簇头n_ch∈{V-{n_s}}，数据由n_s传输给n_ch，再由n_ch汇聚到后台；n_s到n_ch形成k条不相交路径，当一条路径断开时，可以启用其它备用路径，同时对该路径进行恢复，以便维持k路径路由；P(s，ch)是多路路径的集合，p_i(s，ch)是其中一条路径；

(2)对粒子群初始化，采用主-从粒子群模型，在一个D维空间中，初始化生成N×n个粒子，并将这些粒子分成N个群体，其中一个是主群，其余N-1个是从群，每一个粒子都有自己的位置和速度；

(3)采用簇内路径编码，在解空间和粒子表示之间建立映射关系；当某个节点发生故障时，作为簇头的n_ch根据当前获得的拓扑信息构建子图G′并从G′中计算可能的路径集合P(s，ch)；然后先将不满足条件的节点组合成的路径剔除掉，再将剩余的每条链路序列p_i(s，ch)编码为搜索空间中的一个解，用单个粒子表示一条链路序列；

(4)计算每个粒子的适应度函数，通过MPSICA算法从所有解中选出最优解空间对应的路径p_b，其适应度fitness(p_b)最优。适应度函数如下：

$\mathrm{fitness}\left(p_i\right)=\frac{\underset{n\in p_i(s,r)}{\Sigma }\mathrm{energy}\left(n\right)}{{\omega }_1{f}_1+{\omega }_2{f}_2+{\omega }_3{f}_3}$

$f_1=\frac{\underset{e\in p_i(s,r)}{\Sigma }\mathrm{energy}\left(e\right)}{\underset{e\in E}{\Sigma }\mathrm{energy}\left(e\right)}$

$f_2=\frac{\underset{e\in p_i(s,r)}{\Sigma }\mathrm{delay}\left(e\right)+\underset{n\in p_i(s,r)}{\Sigma }\mathrm{delay}\left(n\right)}{\underset{e\in E}{\Sigma }\mathrm{delay}\left(e\right)+\underset{n\in N}{\Sigma }\mathrm{delay}\left(n\right)}$

$f_3=\frac{\underset{e\in p_i(s,r)}{\Sigma }\mathrm{dist}\left(e\right)}{\underset{e\in E}{\Sigma }\mathrm{dist}\left(e\right)}$

其中f₁是某条路径所含链路总共消耗的能量在簇内所有链路可能消耗的总能量中所占的比例，f₂是该条路径所含节点及链路总的延时在簇内所有节点及链路总的延时中所占的比例，f₃是该条路径所含链路总的距离在簇内所有链路总的距离中所占的比例，ω₁、ω₂、ω₃分别为f₁、f₂、f₃对应的权值，ω₁＝0.4，ω₂＝0.2，ω₃＝0.4；

(5)采用MPSICA算法中的免疫模型对粒子进行克隆，选择和替换操作：基于抗体-抗原亲和度即适应度的比例选择，构造记忆单元，并根据亲和度的高低对粒子进行克隆、选择、变异和抑制等操作；

(6)判断是否满足终止条件，若不满足，采用MPSICA算法中的主从粒子群协同进化模型更新粒子位置和速度；每一个从群在迭代过程中执行标准粒子群算法独立进化；所有从群把发现的最好个体信息发送给主群，主群再根据这些最好个体的经验进行状态的更新；

(7)重复步骤(4)到(6)直到满足算法的终止条件(达到迭代次数或收敛到最小值)；

(8)n_ch通过MPSICA算法选择出最优路径p_b后，将路径上的节点信息通知给簇内相应的节点，以便快速建立从源节点n_s到n_ch的最新替代路径p_b，维持簇内多路径路由。

所述的MPSICA算法根据编码得到的链路集合将单个粒子表示一条链路序列，并计算适应度值。

所述的簇内多路径路由模型、路径编码及MPSICA算法在协议中，当簇内某个普通节点发生故障时，其所在路径的上下游节点将广播该信息，分别传给源节点及簇头节点，源节点重新选择新路径，并将可能被选择的接力节点发送给簇头节点，簇头节点根据当前节点拓扑信息构造子图，生成路径集，并用MPSICA算法选择最优替代路径，以便维持簇内从源节点到簇头节点的k路径路由。

有益效果

本发明能够基于H-WSNs的特点进行簇内多路径路由恢复，由于该MPSICA算法全局搜索能力较强、求解精度较好、收敛速度快，因此能在H-WSNs的路径选择和路由恢复中取得较好的效果，提高H-WSNs的路由容错能力。

附图说明

图1为本发明H-WSNs容错路由恢复的流程。

图2为本发明H-WSNs的整体架构。

图3为本发明H-WSNs簇内多路径路由生成图。

图4为本发明多粒子群协同免疫优化算法的流程。

具体实施方式

下面结合具体实施实例，进一步阐述本发明。应理解，这些实施实例仅用于说明本发明而不用于限制本发明的范围。此外应理解，在阅读了本发明讲授的内容之后，本领域技术人员可以对本发明作各种改动或修改，这些等价形式同样落于本申请所附权利要求书所限定的范围。

图1表示了H-WSNs的整体架构，包括下层普通节点和上层超级节点，其中超级节点作为周围普通节点的簇头，簇内数据通过普通节点接力传输给簇头，最后汇聚到后台节点。图2所述的是基于MPSICA算法的H-WSNs容错路由恢复流程图。具体步骤如下：

(1)图2中的簇内多路径路由图构建阶段，所构建的多路径路由图G(V，E)如图3所示，其中V是节点集合，E是节点链接集合。源节点n_s∈V，超级节点(簇头)n_ch∈{V-{n_s}}。从n_s到n_ch形成k条不相交路径，P(s，ch)是这些路径的集合，p_i(s，ch)是其中第i条路径，p_i(s，ch)∈P(s，ch)。n(n∈p_i(s，ch))代表p_i(s，ch)中的一个节点，e(e∈p_i(s，ch))代表p_i(s，ch)中某两个节点间的链接。影响p_i(s，ch)的因素包括：energy(n)，指路径上单个节点的有效能量；dist(e)，指路径上两相邻节点间有效链路的路径长度；energy(e)，指路径上两节点间通信消耗的能量；delay(e)与delay(n)，分别指路径上两节点间的传输延时及单个节点的传输延时；

(2)图2中的路径编码阶段，包含粒子群初始化和用粒子群对路径编码两部分。首先，在一个D维空间中，初始化生成N×n个粒子，并将这些粒子分成N个群体，其中一个是主群，其余N-1个是从群，每一个粒子都有自己的位置和速度，定义第i个粒子t时刻的位置是速度是代表粒子的个体极值点，p_g代表全局最优解。然后，采用簇内路径编码，当某个节点故障时，作为簇头节点的n_ch根据当前获得的拓扑信息构建子图，并从G′中计算可能的路径集合P(s，ch)。然后它先将不满足约束条件的节点组合成的路径剔除掉，再将剩余的每条链路序列p_i(s，ch)编码为搜索空间中的一个解，用单个粒子表示一条链路序列。路径约束方程为：

$\underset{e\in p_i(s,\mathrm{ch})}{\Sigma }\mathrm{delay}\left(e\right)+\underset{n\in p_i(s,\mathrm{ch})}{\Sigma }\mathrm{delay}\left(n\right)\le D$

$\underset{e\in p_i(s,\mathrm{ch})}{\Sigma }\mathrm{dist}\left(e\right)>L$

将不满足以上条件的路径视为不可达。其中，D表示延迟约束，要求n_s到n_ch的路径包含的链路与节点的延迟和不大于该值；L表示距离约束，要求n_s到n_ch的路径距离要大于该值；

(3)图2中的MPSICA算法选择路径阶段，包括目标函数设计，免疫克隆选择，多群体更新粒子群速度位置等步骤，流程图如图4所示，步骤如下：

1)计算每一个粒子的适应度值。通过MPSICA算法从所有解中选出的最优解空间对应的路径p_b，其适应度fitness(p_b)最优。适应度公式如下：

$\mathrm{fitness}\left(p_i\right)=\frac{\underset{n\in p_i(s,r)}{\Sigma }\mathrm{energy}\left(n\right)}{{\omega }_1{f}_1+{\omega }_2{f}_2+{\omega }_3{f}_3}$

$f_1=\frac{\underset{e\in p_i(s,r)}{\Sigma }\mathrm{energy}\left(e\right)}{\underset{e\in E}{\Sigma }\mathrm{energy}\left(e\right)}$

$f_2=\frac{\underset{e\in p_i(s,r)}{\Sigma }\mathrm{delay}\left(e\right)+\underset{n\in p_i(s,r)}{\Sigma }\mathrm{delay}\left(n\right)}{\underset{e\in E}{\Sigma }\mathrm{delay}\left(e\right)+\underset{n\in N}{\Sigma }\mathrm{delay}\left(n\right)}$

$f_3=\frac{\underset{e\in p_i(s,r)}{\Sigma }\mathrm{dist}\left(e\right)}{\underset{e\in E}{\Sigma }\mathrm{dist}\left(e\right)}$

其中f₁是某条路径所含链路总共消耗的能量在簇内所有链路可能消耗的总能量中所占的比例，f₂是该条路径所含节点及链路总的延时在簇内所有节点及链路总的延时中所占的比例、f₃是该条路径所含链路总的距离在簇内所有链路总的距离中所占的比例，ω₁、ω₂、ω₃分别为f₁、f₂、f₃对应的权值，ω₁＝0.4，ω₂＝0.2，ω₃＝0.4；

2)采用MPSICA算法进行路径选择。首先采用免疫思想进行粒子克隆、克隆选择和克隆抑制等操作。该免疫思想利用了免疫机制良好的多样性特征。它采用基于抗体-抗原亲和度(适应度)的比例选择，构造记忆单元，通过新旧抗体的替代，在保证收敛速度的同时又能维持抗体的多样性；

该模型将每个粒子作为一个抗体。对每个需要克隆的粒子，克隆数目与其当前适应度成正比，克隆数N_c按如下式子计算：

N_c＝αN

其中α是克隆因子，并与粒子适应度成正比，N是粒子数。变异规则根据经验设置，其公式表示为：

c_i＝x_i+βrand

其中c_i是克隆后的个体，x_i是原始抗体，β是变异因子，rand是随机变量，rand∈[0，1]。在粒子替代规则中，我们计算原始粒子和选出的克隆变异粒子对抗原的刺激程度。对于任意粒子C_t和抗体Y_t，二者欧式距离为：

$d(i,j)=\sqrt{\underset{i=1}{\overset{n}{\Sigma }}{(c_{\mathrm{it}}-y_{\mathrm{jt}})}^2}$

抗体粒子刺激度为：

A(i，j)＝1/d(i，j)

然后将各粒子的刺激度与设定的阈值进行比较，刺激度高的粒子保留，低的抑制；

3)判断是否满足终止条件(达到设定的迭代次数或收敛到最小值)，若不满足，再采用主从粒子群协同进化模型更新粒子位置和速度。该主从粒子群协同进化思想启发于自然界中的共生现象，由主-从式结构来表示共生群体之间的关系。每一个从粒子群在迭代过程中执行标准PSO算法独立进化，更新方程为：

v_id(t+1)＝wv_id(t)+c₁rand₁(p_id-x_id(t))+c₂rand₂(p_gd-x_id(t))

x_id(t+1)＝x_id(t)+v_id(t)

在所有从粒子群进行下一步更新之前，它们把目前为止发现的最好个体信息发送给某一主粒子群，此主粒子群再根据这些最好个体的经验及其它主粒子群中最好个体的经验进行状态的更新，更新方程如下：

$v_{\mathrm{id}}^M(t+1)={\mathrm{wv}}_{\mathrm{id}}^M\left(t\right)+c_1{\mathrm{rand}}_1(p_{\mathrm{id}}^M-x_{\mathrm{id}}^M\left(t\right))+c_2{\mathrm{rand}}_2(p_{\mathrm{gd}}^M-x_{\mathrm{id}}^M\left(t\right))+c_3{\mathrm{rand}}_3(p_{\mathrm{gd}}^S-x_{\mathrm{id}}^M\left(t\right))$

$x_{\mathrm{id}}^M(t+1)=x_{\mathrm{id}}^M\left(t\right)+v_{\mathrm{id}}^M\left(t\right)$

其中，M表示主粒子群，S表示除自身之外的其它共生从粒子群。p_id是个体极值点，p_gd是全局最优解。c₁，c₂，c₃是加速因子，本发明中选择c₁＝c₂＝2.05，c₃＝2。w是惯性因子，较大的w有利于群体在更大范围内进行搜索，而较小的w能够保证群体最终收敛到最优位置，因此本算法提出了一个线性差分递减策略：

$w\left(t\right)=w_{\mathrm{start}}-\frac{(w_{\mathrm{start}}-w_{\mathrm{end}})}{t_{\max }^2}\times t^2$

其中，w_start＝0.9，w_end＝0.4。在该思想中，单独个体表现出的缺陷可通过其它群体的个体交互作用得到补偿。避免了单一信息交流引起的误判，加快了算法的收敛速度。此外主——从式结构有效的平衡了算法的局部和全局搜索能力；

4)重复步骤1)到3)直到满足算法的终止条件；

(4)图2中的路由恢复阶段，由超级节点n_ch通过MPSICA算法选择出最优路径p_b后，将与路径相关的节点序列信息通知给簇内相应的节点，以便快速建立从源节点到n_ch的多跳路径p_b，恢复簇内的多路径路由；

(5)图2中的容错路由协议实现。如图3所示，源节点n_s(节点4)与簇头节点n_ch(节点40)建立了k条路径(如图3中的3条路径，分别是4-3-7-11-16-22-40，4-8-13-18-40和4-9-15-20-23-40)。协议具体步骤如下：

1)如果簇内接力节点n_fail(节点13)故障，其所在路径的下游节点n_fail-d将该信息报告给n_ch，其上游节点n_fail-u将信息报告给n_s，n_s启动替代路径选择机制；

2)n_s广播path request(PR)包，附带包含自己能量及位置的路由表。接收到PR的某个接力节点n_i根据上一节点n_i-1的信息计算两者间的dist(e)，energy(e)及delay(e)等数据，并添加进路由表，同时包括两节点的ID、energy(n)等信息。然后n_i继续接力传输该PR包，直至n_ch收到各节点传来的PR包；

3)n_ch提取PR包中的信息，并根据获得的拓扑信息构建子图G′，计算可能的路径集合P(s，ch)，通过MPSICA算法选择最优路径p_b。然后n_ch广播RP_ACK包，附带p_b中的节点序列信息(如图2中的节点序列4-8-12-17-40)；

4)若接收到RP_ACK包的接力节点n_i包含在p_b的节点序列中，则自动添加到n_s的最新替代路径中，并与上下游节点和建立连接，直至n_s接收到RP_ACK包；

5)n_s广播PR_END包，通知n_ch已建立的最新路径信息，至此n_s至n_ch的第k条路径建立完成，协议结束。