一种多层无线网络中基于场强获得多条可靠通信路径的方法

技术领域

本发明涉及一种多层无线网络中基于场强获得多条可靠通信路径的方法，属于无线通 信技术领域。

背景技术

在通信技术领域多路径计算方法应用极为广泛，其优点在于提高了网络的吞吐量和可 靠性，同时多路径的应用也带来了如何获取多条最优路径的问题。KSP算法，即K条最短 路径算法，是一种解决在网络拓扑中获取指定源节点到目的节点的多条路径问题的算法， 通过该算法可以在网络拓扑中获得路径权重和由小到大顺序的K条路径。K条最短路径算 法作为一种实用的算法，被广泛应用到通信路由计算、人工智能、经济理论研究的多种领 域，具有很高的应用价值。

在节点间单链路的拓扑中，KSP算法实现的总体流程如下，包括以下内容：

调用Dijkstra算法计算第一优路径；

判断计算出的路径的数量是否满足要求，如果满足，则退出算法，停止计算；如果不 满足，继续计算；

调用KSP算法，在节点间单链路的拓扑上，计算下一优路径，进行判断。

由于需要多次嵌套使用Dijkstra算法，KSP算法普遍存在算法时间复杂度和空间复杂 度高的问题。

无线多层网络普遍应用于无线抄表、无线传感器网络等诸多领域。由于面临节点间通 信不稳定和通信环境变化等限制，需要在路由的计算过程中，提供多条优选可替代路由， 以在选定路由上通信链路失败后，提供可替换的路由以进行再次的数据传输过程。由于无 线节点要满足低功耗、低成本等需求，无线节点大都存在系统资源有限的问题，因此需要 一种时间复杂度与空间复杂度低的多条路由选择算法。

发明内容

本发明的目的是提出一种多层无线网络中基于场强获得多条可靠通信路径的方法，在 满足性能的前提下，解决计算空间复杂度过大问题。在计算过程中通过计算正反双方向最 短路径，对双方向最短路径求和后得到次优路径，并对所得路径进行试探。

本发明提出的多层无线网络中基于场强获得多条可靠通信路径的方法，包括以下各步 骤：

(1)在网络中选取源节点和目的节点，接收短程无线网络中发送端发出的射频信号， 计算各节点间通信场强，节点与其它各节点的通信场强组成场强序列记为Q_M，多个节点 场强序列组成邻居场强表，如果节点之间没有链路直接相连，则不在邻居场强表中进行记 录，计算中其场强值设为“无穷大”；

(2)通过多点最短路径算法计算源节点到其他各节点的正向最优路径集合和正向最 优路径权值集合，其中，由源节点到目的节点的计算结果为正向最优路径和正向最优路径 权值。

(3)通过多点最短路径算法计算得到目的节点到各节点的反向最优路径集合和反向 最优路径权值集合，其中，由目的节点到源节点的计算结果为反向最优路径和反向最优路 径权值；

(4)计算源节点到除目的节点外各节点的正向最优路径权值与目的节点到对应各节 点的反向最优路径权值的权值和，权值和结果最优的路径即为次优路径；

(5)通过对正向最优路径，反向最优路径和次优路径进行试探结果调整路径权值， 试探成功路径权值增大，试探失败路径权值减小，即得到按路径权值排序的多条路由。

上述多点最短路径算法，所述包含起始节点、结束节点、中间节点，其特征在于：

(1)为无线网络中的每一个节点建立一组状态记录，状态记录包括前序参数、路径权 重参数、跳数参数、标号参数；其中，前序参数表示当前节点之前的节点，路径权重参数 表示从起始节点到当前节点的路径权重，跳数参数表示从起始节点到当前节点的跳数，标 号参数表示节点的状态，每个节点的标号参数都处在“永久”或“暂时”状态，当一个节 点的标号参数为“永久”后，将不再改变；

(2)初始化所有节点的状态记录，将各节点的路径权重参数设为“无穷小”，标号参 数设为“暂时”，跳数参数设为0；

(3)将起始节点的标号参数更改为“永久”状态。

(4)更新与起始节点直接相连的所有标号参数为“暂时”的节点状态记录，读取邻 居场强表中起始节点到所有标号参数为“暂时”的节点的场强值，按照路径权重计算方法 更新路径权重参数，并更新前序参数和跳数参数；

(5)在上述标号参数为“暂时”的节点中选择距离起始节点V_S的路径权重最高的节 点。将这个节点作为新的起始节点，并重复过程(3)至(5)，当所有节点的标号参数均 为“永久”后，从结束节点开始依次提取前序参数到起始节点为止，这个节点列表便是从 起始节点到结束节点的最佳路径；结束节点的路径权重参数即为最优路径权值。

上述路径权重计算方法，其特征在于：

(1)两节点间路径权重随两节点通信场强值增大而减小；

(2)多跳情况下，每增加一跳路径权重减小；

(3)路径权重由公式确定，其中s_i为两节点通信场强值，N为路 径总跳数，c为固定常数。

本发明提出的多层无线网络中基于场强获得多条可靠通信路径的方法，具有以下优 点：

(1)本发明通过正反双方向使用多点最短路径计算方法，相对于传统KSP算法减少 了调用D算法的次数，减少了系统运算量；

(2)本发明通过使用邻居场强表，在多点最短路径计算方法中使用状态记录，减少 了内存开销，降低了算法空间复杂度；

(3)本发明通过计算多条最优路径，并进行路径探测提高了无线网络通信的可靠性；

附图说明

图1是本发明的正向最优路径计算示意图；

图2是本发明的反向最优路径计算示意图。

具体实施方式

本发明提出的多层无线网络中基于场强获得多条可靠通信路径的方法，首先由无线网 络中各节点接收其他节点发出的射频信号，得到邻居场强信息；通过多点最短路径算法计 算得到由源节点到目的节点的正向最优路径集合及正向最优路径；然后通过多点最优路径 算法计算得到由目的节点到源节点的反向最优路径集合及反向最优路径；通过正向最优路 径权值与反向最优路径权值和计算得到次优路径；通过对最优路径和次优路径进行试探确 定无线网络多条最优路径；

上述多条路由计算方法中，对网络中源节点和目的节点正反方向使用多点最短路径算 法得到多条最优路径的方法，包括以下各步骤：

(1)在网络中选取源节点V_A和目的节点V_B，接收短程无线网络中发送端发出的射 频信号，计算各节点间通信场强，节点V_M与节点V_N间通信场强记为q_MN，节点V_M与其 它各点的通信场强组成场强序列记为Q_M，多个节点场强序列组成邻居场强表，如果节点 V_M与V_N之间没有链路直接相连，则不在邻居场强表中进行记录，计算中其场强值设为“无 穷大”；

(2)通过多点最短路径算法计算源节点V_A到其他各节点V_M的正向最优路径集合和 正向最优路径权值集合P_M，其中，由源节点V_A到目的节点V_B的计算结果为正向最优路 径和正向最优路径权值为P_B。

(3)通过多点最短路径算法计算得到目的节点V_B到各节点V_M的反向最优路径集合 和反向最优路径权值集合P_M’，其中，由目的节点V_B到源节点V_A的计算结果为反向最优 路径和反向最优路径权值为P_A’；

(4)计算源节点到除目的节点外各节点的正向最优路径权值P_M与目的节点到对应各 节点的反向最优路径权值P_M’的权值和，权值和结果最优的路径即为次优路径；

(5)通过对正向最优路径，反向最优路径和次优路径进行试探结果调整路径权值， 试探成功路径权值增大，试探失败路径权值减小，即得到按路径权值排序的多条路由。

上述多点最短路径算法，所述包含起始节点、结束节点、中间节点，其特征在于：

(1)为无线网络中的每一个节点建立一组状态记录，状态记录包括前序参数、路径权 重参数、跳数参数、标号参数；其中，前序参数表示当前节点之前的节点，路径权重参数 表示从起始节点到当前节点的路径权重，跳数参数表示从起始节点到当前节点的跳数，标 号参数表示节点的状态，每个节点的标号参数都处在“永久”或“暂时”状态，当一个节 点的标号参数为“永久”后，将不再改变；

(2)初始化所有节点的状态记录，将各节点的路径权重参数设为“无穷小”，标号参 数设为“暂时”，跳数参数设为0；

(3)将起始点V_S的标号参数更改为“永久”状态。

(4)更新与起始节点V_S直接相连的所有标号参数为“暂时”的节点状态记录，读取 邻居场强表中起始节点V_S到所有标号参数为“暂时”的节点的场强值，按照路径权重计 算方法更新路径权重参数，并更新前序参数和跳数参数；

(5)在上述标号参数为“暂时”的节点中选择距离起始节点V_S的路径权重最高的节 点。将这个节点作为新的起始节点，并重复过程(3)至(5)，当所有节点的标号参数均 为“永久”后，从结束节点V₀开始依次提取前序参数到V_S为止，这个节点列表便是从起 始节点V_S到结束节点V₀的最佳路径；V₀的路径权重参数即为最优路径权值。

上述路径权重计算方法中，两节点间路径权重随两节点通信场强值增大而减小；多跳 情况下，每增加一跳路径权重减小；路径权重由公式确定，其中s_i为 两节点通信场强值，N为路径总跳数，c为固定常数。

以下详细介绍本发明的一个实施例：

本发明通过计算正反双方向多点最短路径方法，提供了一种多层无线网络中基于场强 获得多条可靠通信路径的方法。

本例的在多层无线网络中计算多条路由的方法，所面临的拓扑和场景满足以下前提：

(1)本例的研究对象为无向拓扑图；

(2)拓扑图所包含的边的个数m>＝节点的个数n；

(3)拓扑图所包含的边的权重是整数，且权重w>0；

(4)算得的任意两点间的路径不允许成环，也就是路径中不包含重复节点；

在无线网络中各节点接收周围各节点的通信场强，组成场强序列，该场强序列记为 Q_M＝[q_M1,q_M2,…,q_MN]，其中M、N表示节点序号，q_MN表示节点M与节点N通信场强。通 过无线通信各节点将场强序列传输到中心节点，中心节点接收到的多个节点场强序列组成 邻居场强表，图1和图2中已标明节点间场强值；

为网络中每个节点建立一组状态记录S₁，每个状态记录包含如下内容：

(1)PreNode，前序参数，用于记录最优路径中该节点的前序节点序号；

(2)Weight，路径权重参数，用于记录路径的权重值；

(3)JumpNum，跳数参数，用于记录路径经过跳数；

(4)StateParam，标号参数，用于标明路径“永久”或“暂时”状态；

初始化所有节点的状态记录，将各节点的路径权重参数设为“无穷小”，标号参数设 为“暂时”，跳数参数设为0；

以节点V_A为起始节点，V_B为结束节点，应用路径权重由公式其中取c＝10，按照多点最短路径算法计算得到的V_A节点状态记录中路径权重参数即为正 向最优路径权值，得到状态记录结果如下所示。

从结束节点V_B开始依次提取前序参数到起始节点V_A为止，这个节点列表A-E-C-B便 是从起始节点V_A到结束节点V_B的正向最优路径，权值为75。

为网络中每个节点建立另一组状态记录S₂，每个状态记录包含数据项与状态记录S₁中 数据项相同，以节点V_B为起始节点，V_A为结束节点，应用同样的路径权重计算公式，按 照多点最短路径算法计算得到的V_B节点状态记录中路径权重参数即为反向最优路径权值， 得到状态记录结果如下所示。

从结束节点V_A开始依次提取前序参数到V_B为止，这个节点列表B-C-E-A便是从起始 节点V_B到结束节点V_A的反向最优路径,权值为75。

在状态记录S₁中除节点V_A与节点V_B外的各节点记录中路径权重参数Weight即为各 节点的正向最优路径权值P_M，图1示出了计算得到的节点V_A到节点V_D的正向最优路径 为A-D，权值P_D＝40，节点V_A到节点V_E的正向最优路径为A-E，权值P_E＝30。在状态记 录S₂中除节点V_A与节点V_B外的各节点记录中路径权重参数Weight即为各节点的反向最 优路径权值P_M’，图2示出了计算得到的节点V_B到节点V_D的反向最优路径为D-F-B，权 值P_D’＝50，节点V_B到节点V_E的最优路径为E-C-B，权值为P_E’＝45。计算源节点到除目 的节点外各节点的正向最优路径权值P_M与目的节点到对应各节点的反向最优路径权值P_M’ 的权值和，可以得到经过节点V_D的一条较优路径为A-D-F-B，权值和为P_D+P_D’＝90，经 过节点V_E的一条较优路径为A-E-C-B，权值和为P_E+P_E’＝75，依此类推。对各权值和进行 排序，并剔除重复的路径，可得到权值和结果最优的次优路径为A-D-F-B和A-E-F-B；

通过对正向最优路径，反向最优路径和次优路径进行试探结果调整路径权值，试探成 功路径权值增大，试探失败路径权值减小，取进行试探后权值最优的多条路径即得到按路 径权值排序的多条路由。