无线传感器与执行器网络是无线传感器网络的一种，由大量的异构传感节点和能够对感知到的物理信息作出响应的执行器构成. WSANs在工业进程中广泛应用，由普通低能量、性能资源的传感器节点和性能、容量远超普通节点的执行器构成^[1]. 传感节点感知数据，并周期性或自发性地将数据传输给临近的执行器节点，执行器对此作出响应，可以用于工业自动化、实时目标追踪、环境监控等应用. 由于传感节点的低花费、灵活性和可拓展性等优点，迅速取代了有线的工业设施.

工业环境恶劣、噪声的干扰给WSANs的可靠、实时传输带来巨大的挑战. 多跳通信增大了通信延时，信道状况的动态改变给路由选取带来巨大的麻烦. WSANs需要高效的通信设计. 由于传感节点通常稠密部署在感知区域来保证覆盖范围和拓扑连通性^[2]，如文献[1]、[3]、[4]所示，WSANs中存在许多实时通信的开放性问题，尤其是关于异构的网络模型、资源限制和可拓展性问题.

当前无线传感网中大多数路由协议不能很好地利用资源丰富的设备来减少普通节点的通信压力，如地理路由、AODV^[5]、DSR^[6]等. 再如考虑链路故障的路由算法^[4,7-10]，由于这些方法是针对普通传感网，它们并不适合 ${\rm WSANs}$ .

之前对于 ${\rm Kautz}$ 图的研究工作主要集中在拓展 ${\rm Kautz}$ 图在P2P网络应用层的应用^[11-13]. Zuo等^[14]提出在自组织网应用层建立 ${\rm{Kautz}}$ 图覆盖网络来提高路由性能. 由于拓扑的不一致性，该方法使用移动自组网多跳路由来实现邻居节点间的简单通信. Li等^{[11, 15]}研究最短和最长路径路由. 在 ${\rm BAKE}$ ^[11]和 ${\rm DFTR}$ ^[16]中，当节点沿最短路径传输信息故障时，它使用次最短路径进行传输. 节点需要使用路由生成算法来寻找到目标节点的不同路由，并计算它们的长度，会产生较高的能量消耗. Shen等^[17]提出使用节点 ${\rm ID}$ 的方法来进行数据传输，不需要路由表的维持，但固定了节点间的传输路径，限制了路径的多样性. 由于 ${\rm WSANs}$ 一般用于工业环境中，路由设计中应考虑链路故障.

设计容错、实时、高效、可靠的先验式路由FRER来解决以上问题. 本文的贡献如下：1）阐述了 ${\rm Kautz}$ 图在 ${\rm WSANs}$ 中满足高效、实时通信需求的能力；2）基于构建的 ${\rm Kautz}$ 图网络拓扑，提出新的高效、实时路由策略；3）考虑工业环境噪声对路由的干扰，使用基于可用性历史的多路径路由，提高网络数据传输的可靠性.

1 Kautz网络拓扑

定义 1　 ${\rm{Kautz}}$ 有向图 $K(d,n)$ 是节点度为 $d$ ，直径为 $n$ 的有向图，节点使用编号 $({u_1},\cdots,{u_n})$ 表示，其中 ${u_i} \in (0,1, \cdots ,d)$ ， ${u_i} \ne {u_{i + 1}}$ ， $K(d,n)$ 的边集 $E$ 为以顶点 ${u_1},\cdots ,{u_n}$ 为起点，连向 ${u_2}, \cdots ,{u_n}\alpha $ 的 $d$ 条有向边， $\alpha \in \{ 0,1, \cdots ,d\} $ .

在无线网络拓扑设计中，要考虑节点度和网络直径对网络性能的影响. 较高的节点度能够保证较好的容错性、较低的网络直径和传输时延，但同时会造成较大的开销和干扰. 传统的互联网络拓扑有着节点数目和不支持节点加入或离开的限制， ${\rm Kautz}$ 图与 ${\rm DeBruijn}$ 图能够解决这一问题. ${\rm Kautz}$ 图与 ${\rm DeBruijn}$ 图相似，但能够实现更好的性能，诸如最优的直径、最优的容错性和良好的负载均衡.

定理1^[18] 　对于给定的度数d和直径n，一个拓扑至多可容纳的节点数受 ${\rm Moore}$ 界 $1 + d + {d^2} + \cdots + {d^n}$ 约束， ${\rm Moore}$ 界通常情况下（除 $d = 1$ 或 $n = 1$ 的情况之外）都是不可达的. ${\rm Kautz}$ 图 $K(d,n)$ 的节点数目为 ${d^{n - 1}} + {d^n}$ ，已经非常接近 ${\rm Moore}$ 界.

证明：给定度数 $d$ 和直径 $n$ ， ${\rm Moore}$ 界是不可达的，除非平凡的情况即 $d = 1$ 或 $n = 1$ . 对于 ${\rm Kautz}$ 图 $K(d,n)$ ，根据节点编号规则可知，第一个位置有 $d + 1$ 种选择，剩余 $n - 1$ 个位置有 $d$ 种选择，所以 ${\rm Kautz}$ 图中包含 ${d^{n - 1}} + {d^n}$ 个节点，非常接近 ${\rm Moore}$ 界.

定理2^[17] 　对于给定的节点度数和节点总数为N的任意网络拓扑，根据 ${\rm Moore}$ 界可知，网络直径的下界是 $\left\lceil {{{\log }_d}(N(d - 1) + 1)} \right\rceil - 1$ ， ${\rm Kautz}$ 图的网络直径达到这一下界，因此 ${\rm Kautz}$ 图具有最优的网络直径.

证明：根据 ${\rm Moore}$ 界可知，包含 $N$ 个节点的图的直径下界为 $\left\lceil {{{\log }_d}(N(d - 1) + 1)} \right\rceil - 1$ ； ${\rm Kautz}$ 图达到下界：

$\begin{split}\left\lceil {{{\log }_d}(({d^n} + {d^{n - 1}})(d - 1) + 1)} \right\rceil - 1 = \quad\quad\quad\\\left\lceil {{{\log }_d}({d^n} + {d^{n - 1}} + 1)} \right\rceil - 1 = n + 1 - 1 = n.\end{split}$

定理1和2说明 ${\rm Kautz}$ 图是 ${\rm WSANs}$ 中合适的覆盖拓扑，能够满足能量效率和实时通信的需求. ${\rm Kautz}$ 图具有最优的容错性能， ${\rm Kautz}$ 图 $K(d,n)$ 连通度为 $d$ ， ${\rm DeBruijn}$ 图连通度为 $d - 1$ . 此外， ${\rm Kautz}$ 图较 ${\rm DeBruijn}$ 图能够实现低延时和更好的负载均衡，关于这点会在仿真中进行验证.

2 基于Kautz图的WSAN容错高效传输协议

假定 ${\rm{WSAN}}$ 传感节点密集地部署于应用区域，选取文献[17]的网络构架，如图1所示，传感节点密集地部署于应用区域. 如图1（a）所示为其中一个Kautz单元，执行器节点挑选一些传感节点构建成Kautz图的模型，资源丰富的执行器节点作为Kautz图的顶点. 整个网络由多个Kautz图单元构成，组成DHT结构.

2.1 Kautz图嵌入

每个Kautz单元包含一个单元ID(CID)，每个传感节点在每个单元包含一个节点ID(KID)，即WSAN中每个节点可以用(CID, KID)表示，其中KID={u₁, ···u_i, ···|u_i $ \ne$ (0, 1, ···, d), u_i ≠ u_i+1}是Kautz图中的Kautz ID. 在Kautz单元构造时，首先选取一个执行器节点作为初始点，选取与该执行器节点最近的执行器并与之相连构成边，任取该边的一边，通过邻居节点交换信息，从公共邻居节点中选取到该边两端点距离最短的执行器构成三角形区域，该三角区域 ID赋为1. 之后，以同样的方式继续构造Kautz单元，直至覆盖整个网络，并为每个单元赋予ID. 于是，较接近区域的ID编号较接近.

在所有Kautz单元构建完成之后，需要给每个Kautz单元中的传感节点赋予ID，即Kautz图的构建. 如图1（a）所示为图1（b）的区域5. 为了明确地表示路由，尽管节点间的通信是双向的，仍将WSAN表示为有向图 $G(d,n)$ . 为了保证邻居执行器不使用相同的KID，使用顺序顶点着色算法^[19]，每个节点分配一个不被邻居节点使用的最小的颜色号码. 由于在Kautz图 $K(d,3)$ 中只包含3个执行器节点，如图1所示，执行器节点IDs分配为（5,201）、（5,012）和（5,120），在执行器节点分配完ID之后，它们挑选信道质量最好、剩余能量最高的节点作为它们的后继节点（有向图中被指向的节点）. 对于任意的节点对 $U = {u_1}{u_2}\cdots{u_n}{\text{和}}$ $V = {v_1}{v_2}\cdots{v_n},\,$ $l = L(U,V)$ 表示U的最长后缀与V的前缀的匹配，如201和012匹配为 $L(210,012) = 1$ .

如图1所示为K(2,3)的例子，即节点的入度和出度都为2，网络的直径为3，包含12个节点. 首先是执行器间的互联，例如，对于执行器（5,012），它挑选后继（5,120）. 同时，它广播一个到（5,120）TTL（存活时间）为2的路径请求信息，保证直径 $k = 3$ . 在（5,120）接收到多个路径信息之后，它选取剩余能量高于一定水平，组合信道质量最高的路径，并给它们赋予 ${\rm IDs}$ ， ${\rm IDs}$ 的赋予遵循最接近目标的原则. 如果一个节点前驱（指向该节点的节点）的 ${\rm ID}$ 为 ${u_1}{u_2}{u_3}$ ，则该节点的 ${\rm ID}$ 为 ${u_2}{u_3}{u_k}$ ， ${u_k}$ 使得节点的ID更接近目标，即匹配长度增大. 例如，图1中，当节点（5,120）接收到多个路径信息时，它选取组合信道质量最好的路径，即图中黑色的节点，并给它们赋予IDs，挑选的路径为（5,012） $ \to $ （5,121） $ \to $ （5,212） $ \to $ （5,120）. 同理，执行器（5,120）选取到（5,201）的路径（5,120） $ \to $ （5,202） $ \to $ （5,020） $ \to $ （5,120）；执行器（5,201）选取到（5,012）的路径（5,201） $ \to $ （5,010） $ \to $ （5,101） $ \to $ （5,012）.

每个节点只能被一组执行器节点选取，当节点被选中为图1中黑色节点所在路径之后，其他执行器节点不能再选取该节点为作为到后继执行器节点的路径. 在图1中黑色节点选取完毕之后，开始选取深灰色节点. 例如执行器（5,012）的后继为（5,121），执行器（5,201）的前驱为（5,020），为了保证信息能够穿越不同的执行器对，（5,121）选取到（5,020）的路径，并给它们赋予 ${\rm IDs}$ . 将剩余节点，即图1中浅灰色的节点，按照上述规则选取满足 ${\rm Kautz}$ 图条件的最高信道质量的前驱和后继，保证节点度为2，直径为3. 最终， ${\rm Kautz}$ 图建立完毕.

2.2 能量效率拓扑维持

研究大规模的WSAN，传感节点密集部署. 如图2所示，传感节点包含3种状态：活跃、睡眠和等待. 活跃节点为Kautz节点，它们周期性地发送“Hello”数据包来更新与邻居节点的连通性状态. 当节点的能量低于某一阈值或链路质量下降到某一阈值时，规定节点能量低于20%或链路PDR连续20个时间片低于0.6，进行Kautz节点更新. 睡眠的传感节点周期性地唤醒，并与Kautz节点交换信息，检查自身能否成为Kautz节点候选. 成为Kautz节点候选需要满足3种要求：1）它必须能与一个Kautz节点通信；2）它必须有至少一个Kautz邻居节点能量低于20%或链路连续20个时间片不可用；3）它能够与该Kautz节点的其他邻居Kautz节点连通. 当一个节点检查自身时，发现自身能量或链路质量降低到某一水平，它通知邻居节点并选择满足要求的邻居节点代替自身作为Kautz节点，将自身的ID信息交给该节点，则进入睡眠状态. 为了避免出现节点未转交ID发生故障的情况，邻居Kautz节点周期性地发送“Hello”数据包检测邻居Kautz节点的状况. 若发现找不到邻居节点的情况，则通知邻居传感节点唤醒，选取链路质量最高的节点作为新的Kautz节点.

2.3 容错、可靠、高效路由

对于本文的网络构架，在网络分成多个 ${\rm Kautz}$ 单元之后，对于跨单元的数据传输，执行器使用贪婪路由的方法，将数据包发送给 ${\rm ID}$ 接近目标单元 ${\rm ID}$ 的单元. 由前面单元ID的分配可知， ${\rm ID}$ 相近的单元位置相距较近. ${\rm Kautz}$ 图在容错性和实时性及能量消耗上作了折中. 节点度为d的 ${\rm Kautz}$ 图包含d条节点不相交路径. 如图3所示为一个 $K(3,4)$ 的例子，对于任意的节点对U、V，都存在3条节点不相交路径. 假设节点0123接收到数据包或感知到事件产生数据包，并将数据包发送给节点2312. 初始时，数据包沿着最短路径0123 $ \to $ 1231 $ \to $ 2312发送；若该最短路故障，则节点0123快速地选择次最短路径，选取1232作为下一跳节点.

定理3　当节点 $U = {u_1}{u_2}\cdots{u_n}$ 使用贪婪最短路的方法向节点 $V = {v_1}{v_2}\cdots{v_n}$ 发送数据时，所选路径为最短路.

证明：根据 ${\rm Kautz}$ 节点编码方法可知， ${\rm Kautz}$ 图中任意2个节点之间的最短距离为 $n - l$ ，按照编号规则使用贪婪选取的方法选取最小编号， $U$ 节点的下一跳为 ${u_2}\cdots{u_{n - l}}\cdots{u_n}{v_{l + 1}}$ . 此时与目标节点 $V$ 之间的最短距离为 $n - l - 1$ ，继续这样下去，直到 ${u_{k - 1}}{v_2}\cdots{v_l}\cdots{v_{n - 1}}$ ，它与节点 $V$ 的编号匹配长度为n–1，即下一跳节点是V，路径总长度为 $n - l$ ，所选路径为最短路.

定理4^[17] 当节点 $U = {u_1}{u_2}\cdots{u_n}$ 转发数据给节点 $V = {v_1}{v_2}\cdots{v_n}$ 时，后继、路径长度和对应的d条节点不相交U-V路径为

$\left\{ {\begin{array}{*{20}{l}} {(1)\,{u_2}\cdots{u_n}{u_{n - l}},\quad }&{n + 2},&{\;{u_{n - l}} \ne {v_{l + 1}}} ;\\ {(2)\,{u_2}\cdots{u_{n - l}}\cdots{u_n}{v_{l + 1}}},&{n - l},&{\text{最短路径}}; \\ {(3)\,{u_2}\cdots{u_n}{v_1}, \quad \,\,\,}&n,&{{u_n} \ne {v_1}}; \\ {(4)\,{u_2}\cdots{u_n}{\alpha _i}, \quad \;\,}&{n + 1},&{\text{其他}}. \end{array}} \right.$

(1)

式中： ${\alpha _i} \ne ({v_1},{v_{l + 1}},{u_{n - l}})$ .

2.4 基于 ${\rm{ID}}$ 传输的修正

当任意节点对要发送数据时，节点通过目标节点ID，根据定理4可知，源节点能够快速、高效地找到目的节点的最短路. 任意节点对之间包含 $d$ 条节点不相交路径，当传输过程中的任意节点发生故障时，故障节点的上一跳节点不需要通知源节点，能够自发地选择次最短路径进行数据传输，保证了网络通信的容错性.

该传输方法存在一定的问题. 当 ${\rm Kautz}$ 拓扑构建完成后，节点按照ID信息进行传输时，所选取路径为有向图最短路，而非全局最短路. 例如图3中，节点U到V的最短路为0123 $ \to $ 1231 $ \to $ 2312，路径长度为2跳；当节点V向U发送数据时，由于V的后缀与U的匹配长度为0，路径长度为 $k - l = 4$ ，增大了网络的延时，且没有充分地开发网络拓扑的路径多样性.

针对这一问题的解决方法是允许节点沿 ${\rm Kautz}$ 有向边反向传输，即当节点有数据包要发送的时候，通过对比正、反向节点 ${\rm ID}$ 的匹配长度，沿着匹配长度较长的方向进行数据传输. 例如，图3中节点V要向U发送数据，它首先比较正向匹配长度和反向匹配长度，发现正向匹配长度 ${l_1} = 0$ ，反向匹配长度为 ${l_2} = 2$ ，则选择反向传输路径，在数据包中添加反向传输标记. 按照 ${\rm ID}$ 传输的反向规则进行传输，能够极大地减少网络时延.

定理5　当节点 $U = {u_1}{u_2}\cdots{u_n}$ 转发数据给节点 $V = {v_1}{v_2}\cdots{v_n}$ 时，下一跳节点选取为αu₁··· ${u_{n - 1}} $ ，以该方式使用贪婪最短路径算法，后继、路径长度和对应的d条节点不相交U-V路径为

$\left\{ {\begin{array}{*{20}{l}} {(1)\,{u_{l + 1}}{u_1}\cdots{u_{n - 1}}, }&{n + 2},&{\;{u_{l + 1}} \ne {v_{n - l}}}; \\ {(2){v_{n - l}}{u_1} \cdots {u_{n - 1}}, \;}&{n - l},&{\text{最短路径}} ;\\ {(3){v_n}{u_1}\cdots{u_{n - 1}},\quad \quad \,\,\,}&n,&{{u_1} \ne {v_n}}; \\ {(4)\,\alpha {u_1}\cdots{u_{n - 1}}, \;\,}&{n + 1},&{\text{其他}}. \end{array}} \right.$

(2)

式中： $\alpha \ne ({v_n},{v_{n - l}},{u_{l + 1}})$ .

证明：1)根据定理3证明可知，最短路径中 $U$ 的后继中编码第一位（后用 $\alpha $ 表示）为 ${v_{n - l}}$ ， $V$ 的前驱的最后一位（后用 $\beta $ 表示）为 ${u_{l + 1}}$ . 若路径为非最短路， $\alpha $ 选为 ${v_n}$ ，则 $\beta = {u_1}$ ；若 $\alpha \ne {v_n}$ ， $U$ 的后继的下一跳为 ${v_n}\alpha {u_1}\cdots{u_{n - 2}}$ ，即 $\beta = \alpha $ . 非最短路之间不会产生交错，否则与 $\beta = \alpha $ 冲突. 若 ${u_{l + 1}} = {v_{n - l}}$ ，则所有的非最短路不会与最短路产生交错；若 ${u_{l + 1}} \ne {v_{n - l}}$ ，则其中一条非最短路的后继编码中第一位为 ${u_{l + 1}}$ ，与最短路的 $\beta $ 相同，产生交错. 这条路径中 $U$ 的后继节点称为冲突节点，按照选取规则可知，冲突节点后继第一位选取为 ${v_{n - l}}$ ，此时该后继节点到 $V$ 的最短路径长度为 $n$ ，则整条路径长为 $n + 2$ ；2)同定理3可证；3)当 ${u_1} \ne {v_n}$ 时， $\alpha $ 可以选为 ${v_n}$ ，即整条路径长度为 $n$ ；4)对于其他所有情况，每个后继节点的下一跳第一位从 ${v_n}$ 开始，路径长度为 $n + 1$ .

2.5 容错传输修正

为了充分利用无线介质的广播特性，拓展路由路径的多样性，在网络节点数据传输过程中发生节点故障时，由于任意节点间存在 $d$ 条节点不相交路径，传输过程不会中断，会沿着次最优路径进行传输.

由于节点周期性地发送“ ${\rm Hello}$ ”数据包来维持邻居节点信息和状态，节点会发现一些“特殊的” ${\rm Kautz}$ 节点，这些 ${\rm Kautz}$ 节点与它之间的链路不属于 ${\rm Kautz}$ 拓扑，这些节点的 ${\rm ID}$ 信息会被记录在邻居列表中. 当传输过程中节点发生故障或链路质量下降到某一阈值时，节点比较这些特殊的 ${\rm Kautz}$ 节点与次最优下一跳节点与目的节点的正反向匹配长度. 若次最优路径匹配长度最大，则使用该次最优路径；若特殊 ${\rm Kautz}$ 节点匹配长度最大，则使用特殊的 ${\rm Kautz}$ 节点进行“绕道”，绕道时需要在数据包中添加绕道信息、标记位以及绕道节点 ${\rm ID}$ 信息.

数据包的格式如图4所示. 数据包的包头包含源节点ID、目的节点ID、数据包类型、数据包序列号及正、反向标记位和绕道标记位. 正、反向标记位为0和1两种，0表示正向传输，1表示方向传输. 绕道标记位包含2部分：标记和ID；标记为0，表示没有绕道，标记为1表示绕道，在ID位记录绕道节点ID信息. 最后的FCS位是校验位，用于检测接收数据包是否误码. 当节点通过“Hello”数据包评估邻居节点间链路质量时，要评估不存在于Kautz拓扑中的链路质量；当绕道链路质量高于原链路，绕道节点的下一跳节点有更优的匹配长度时，可以使用绕道链路.

2.6 基于可用性历史的可靠多路径路由

${\rm WSANs}$ 一般用于工业环境中，信道质量随时间发生变化，链路故障时常发生. 在考虑 ${\rm WSANs}$ 时，不仅要考虑节点由于能量问题或外界因素引起的故障，而且要考虑链路故障. 一般来讲，节点故障可以通过备用节点替换来恢复网络正常运行能力，但链路故障的出现不能通过替换节点来改善. 基于该问题，使用基于可用性历史记录的多路径传输来解决.

可用性历史表示链路可用性随时间变化的记录，将时间分为l个时间片，节点i和j之间链路第r个时间片所对应的可用性为 $a_{ij}^r$ ，链路 $(i,j)$ 某个时期的可用性可以表示为 ${{{a}}_{{{ij}}}} = \left[a_{ij}^1,a_{ij}^2, \cdots ,a_{ij}^l\right]$ . 其中，

$a_{ij}^s = \left\{ {\begin{aligned} & {\begin{array}{*{20}{l}}1,{{\;\;\;{\rm{PDR}}}_{ij}^s \geqslant {\gamma _0}}\;; \end{array}} \\ & {\begin{array}{*{20}{l}} 0,{\;\;\;\text{其他}}; \end{array}} \end{aligned}} \right.$

(3)

${\rm {PDR}}_{ij}^s$ 为链路 $(i,j)$ 在时间片s的数据包传输比率. 将 ${\rm PDR}$ 映射为数值0和1，其中0表示对应时刻链路不可用，1则相反；通过阈值 ${\gamma _0}$ 来限定链路的 ${\rm PDR}$ ，从而确定链路的可用性，本文设定 ${\gamma _0} = 0.6$ .

路径的可用性是所有该路径上链路的可用性进行逻辑位运算 ${\rm AND}$ ，长度为 $p$ 的路径 ${{{P}}_{{i}}}$ 的可用性可以表示为 ${{{A}}_{{i}}} = {a_{{i_1}}}{a_{{i_2}}} \wedge {a_{{i_2}}}{a_{{i_3}}} \wedge \cdots \wedge {a_{{i_p}}}{a_{{i_{p + 1}}}}$ ，其中 ${a_i}$ 表示路径 ${{{P}}_{{i}}}$ 上第i个节点的 ${\rm ID}$ . 多条路径的可用性表示多个路径可用性之间进行逻辑位运算 ${\rm OR}$ ，即 ${{{A}}_{ {M}}} = {{{A}}_{{1}}} \vee {{{A}}_{{2}}} \vee \cdots \vee {{{A}}_{{k}}}$ .

如图5所示，路径1包含链路1-2和2-3. 在某一时期网络的可用性如图5所示，链路1-2在第9个时间片不可用，链路2-3在第4个时间片不可用，则路径1在第4和第9个时间片不可用. 路径2与路径1有着相同的源节点和目标节点，路径2在第1和第3~5时间片可用，则它们的组合可用性只在第9个时间片不可用. 利用组合路径的方法，可以增大传输的可用性.

多路径挑选的具体流程如下. 算法总共分为2个阶段：路径预挑选阶段和贪婪多路径挑选阶段. 在路径预挑选阶段，通过上文所述的挑选最小编号下一跳节点的方法，寻找正、反向匹配的最短和次最短路径，存放于集合H中. 在贪婪多路径挑选过程中，旨在挑选组合可用性最大的k条路径用作数据传输，本文设定 $k = 2$ . 首先初始化多路径集合M为空集合，组合可用性 $\theta ({{M}})$ 为0，在集合H中挑选最大化M可用性的路径，添加到M中，直至M中包含k条路径. 通过该贪婪挑选的方法找到的可能不是最优组合，因此将集合H中可用性最大的路径选出，在剩余路径中使用贪婪的方法挑选k条路径，与最大可用性路径进行比较，在包含最大可用性路径的集合中挑选最优组合的k条路径.

3 性能评估

使用NS-2来评估FRER性能，并与REFER^[17]和DeBruijn图进行比较. 当节点发生故障时，发送广播信息来重建路径. 10个执行器节点均匀分布在500 $ \times $ 500的区域内，500个传感节点独立同分布，部署在执行器节点周围，构成 $K(3,3)$ Kautz单元；传感节点和执行器节点的传输范围分别设置为100和250 m，每过10 s，在每个Kautz单元随机选择2~7个源节点传输数据，传感节点通信使用IEEE802.11协议. 分别开展干扰环境和未受干扰下的仿真.

3.1 未受干扰的网络环境

对于未受干扰的网络环境，使用以下标准进行评估.

1）吞吐量：目标节点每秒钟成功接收的数据包的数量. 更高的吞吐量意味着更高的容错性和实时性能.

2）时延：平均端到端数据传输延时.

3）数据包传输比PDR：成功传输的数据包与总发送数据包的比值. 更高的PDR意味着更高的传输效率.

在仿真过程中，随机挑选2x个故障节点，x服从[1, 5]上的均匀分布，每过10 s，修复网络中之前的故障节点. 如图6（a）所示为吞吐量T随源目标节点对数N的变化. 可以看出，REFER和DeBruijn图的吞吐量低于本文的算法FRER，但Kautz图的吞吐量远高于DeBruijn图. 随着源目标节点对数的增长，网络吞吐量先上升后平稳下降. 这是因为最初时，随着网络中源节点数目的增多，网络吞吐量相应增长；随着源节点的增多，每个Kautz单元中重合的链路数量增多，从而影响端到端的数据传输. 从图6（a）可以看出，当每个Kautz单元中源节点的数量为4时，网络吞吐量最大. 如图6（b）所示为端到端平均传输时延随源目标节点对数的变化. 可以看出，当网络中源节点数增大时，网络端到端时延先下降；当节点对数为4时达到最小，之后增长，这是因为仿真时随机挑选源目标节点对，当节点对数较小时，所选取的可能是与REFER相同的较长路径；当节点对数增大时，FRER的路径长度小于等于REFER的路径长度，因此随着节点对数的增长，网络时延下降；随着节点对数的增加，每个Kautz单元和DeBruijn图中重合的链路增多，造成网络时延增大. 与Kautz图相比，DeBruijn图变化最明显，当本文的FRER算法在每个Kautz单元中重合的链路数量较少，时延变动较平滑. 如图6（c）所示为PDR随网络中源目标节点对数的变化. 随着源目标节点对的增多，本文算法的FRER先增长后平稳下降，当源目标节点对的数量为4时达到最高值，之后平稳下降；REFER的PDR变化不大，当网络中源目标节点对数增大时，呈现出下降趋势，整体来说，Kautz图的PDR高于DeBruijn图，本文算法的传输效率高于REFER.

3.2 受干扰的网络环境

由于WSANs一般用于工业环境，相较于REFER，本文考虑网络中链路的故障. 当链路故障时，仅通过替换节点无法解决该问题，需要使用多路径的方法来提高网络传输的可靠性.

工业环境中包含诸多噪声. 考虑其中一种高斯白噪声，对于其他噪声，可以使用本文方法降低噪声对数据传输的影响. 使用Nakagami分布来描述接收到的信号强度，Nakagami分布定义为

$f(x,m,\varOmega ) = \frac{{{m^m}{x^{m - 1}}}}{{\varGamma (m){\varOmega ^m}}}\exp \left( - \frac{{mx}}{\varOmega }\right).$

(4)

式中： $\varGamma $ 为伽马函数， $m$ 为Nakagami分布衰落参数， $\varOmega $ 为平均接收能量. 设置 $m = 1$ ，

$\varOmega (d) = \frac{{{P_{\rm t}}{G_{\rm t}}{G_{\rm r}}h_{\rm t}^2h_{\rm r}^2}}{{{d^n}L}}.$

(5)

式中： $d$ 为发送者与接受者之间的距离； ${P_{\rm t}}$ 为传输功率，本文设为2 ${\rm W}$ ； ${G_{\rm t}}$ 和 ${G_{\rm r}}$ 为天线收益； ${h_{\rm t}}$ 和 ${h_{\rm r}}$ 为天线权重； $L$ 为损耗因子； $n$ 为路径损耗指数. 设置 ${G_{\rm t}} = {G_{\rm r}} = 1$ ， ${h_{\rm t}} = {h_{\rm r}} = 1.5 \,\,{\rm m}$ ， $L = 1$ ， $n = 4$ . 假定若接收到的信号功率高于某一接收阈值（本文设为0.6），则表示数据包成功接收. 对于噪声的影响，假定产生的噪声叠加到接收信号中，只会降低接受信号强度，噪声强度设为8 dB；当接收信号强度低于0.6时，认为没有成功接收数据包.

如图7所示为在干扰情况下的网络可用性和性能情况. 在仿真过程中，将时间划分为10个时间片；每过一个时间片，可用性信息左移一位，由新的可用性信息补全最后一位. 如图7（a）所示为干扰存在下的网络端到端可用性情况. 图中，A_v为可用性，P为分布概率，垂直线表示均值，其他曲线表示累积分布. 为了与REFER算法进行对比，REFER算法和DeBruijn图按照路由选取规则挑选2条最短路进行数据传输. 从图7（a）可以看出，基于可用性历史的FRER算法与实际情况较接近，可以预测实际情况；2种基于Kautz图的可用性高于DeBruijn图，与REFER算法和DeBruijn图进行对比可知，FRER的平均可用性明显高于REFER算法和DeBruijn图，这说明利用基于可用性历史的FRER算法能够挑选出k条最优可用性的路径组合来提高网络传输的可靠性. 如图7（b）所示为干扰存在下网络端到端的数据包传输比. 图中，t为时间. 可以看出，在干扰存在的情况下，本文算法的数据包传输比明显优于REFER算法和基于DeBruijn图的算法，即网络整体传输效率高于以上2种算法.

4 结　语

本文提出的FRER算法能够利用邻居节点信息，在已存在的网络拓扑中拓展网络的路径多样性；与当前的无线传感网路由算法相比，本文的FRER算法基于Kautz图，能够以最小花费找到最短路径. 与基于Kautz图的REFER算法及基于DeBruijn图的算法相比，本文的FRER算法利用拓展路径多样性的方法，找到的路由路径长小于等于REFER算法. 本文算法考虑了REFER算法没有考虑的链路故障情况，使用可用性历史来预测未来链路的可用性，通过组合k条最优可用性组合的路径来提高网络整体传输效率. 大量的仿真实验表明，在链路故障存在的情况下，利用本文的FRER算法能够提高网络的可用性；FRER算法在提高网络可靠性、降低延时和丢包率、提高网络吞吐量方面优于REFER算法和DeBruijn图. 下一步的研究方向是考虑拥塞情况对FRER算法的影响，评估并设计拥塞避免的算法.