基于位置预测的无人机自组网地理信息路由方法及系统

摘要

本发明提供一种基于位置预测的无人机自组网地理信息路由方法及系统，属于无人机自组网通讯领域。本发明方法包括如下步骤：建立邻居节点表，其中，所述邻居节点表包括邻居节点ID号、及与所述邻居节点ID号对应的位置信息容器，所述位置信息容器中能够存储window个接收该邻居节点信标的时间及位置信息；根据邻居节点的位置信息容器中的信息预测邻居节点位置；根据预测的各个邻居节点位置进行路由决策。本发明的有益效果为：位置预测机制解决了由于位置信息滞后带来的路由决策错误，能够减少20%以上的无人机自组织网络通信过程中的丢包率。

说明书

技术领域

本发明涉及无人机自组网通讯领域，尤其涉及一种基于位置预测的无人机自组网地理信息路由方法，还涉及一种实现其方法的系统。

背景技术

现有的无人机自组织网络路由协议中，主要有传统基于表驱动的路由协议和基于地理信息进行决策的地理信息路由。

基于表驱动的路由主要运用与传统的有线网络或者固定节点的无线网络中。这种类型的路由要求网络中每一个节点都需要维护一张甚至多张的路由表，这张表记录着每个节点所转发的包的源节点-目的节点对在转发过程中的所有节点。每次新生成一个源节点-目的节点对之间的传输时，都会进行一次全局广播来搜寻出一条或者几条经过跳数最短的路径，然后将生成路由表。之后再在这个源节点-目的节点之间进行包转发时，只需进行查表操作就可以确定转发路径。

基于地理信息的路由则是主要运用在无线网络中，与传统路由中依托于IP地址进行节点识别的模式不同，基于地理信息的路由记录的是每个节点真实的地理位置，每个节点记录一张自己的传输范围内的临节点的表。如表1所示：

ID位置信息1(20.3,50.2)……n(x,y)

表1

ID代表每个节点的标识符，可以是IP地址，也可以是其他的编号。位置信息在表中，如果是平面坐标，则可以用一个二维向量表示，如果是立体坐标则可以用一个三维向量来表示，位置信息可以采用绝对坐标也可以采用相对坐标。

在进行包转发时，依据这张邻结点表进行路由决策。主流的路由决策依据有基于最短路径、最小负载、最短横向距离等。

基于表驱动的路由由于每一个节点都需要维护完整的源节点-目的节点之间进行转发的路由表，且该表的建立需要进行全局广播，建标开销巨大。这种类型的路由比较适合节点状态变动不大的网络，即静态网络。因为在静态网络中，只需在新建一对源节点-目的节点之间的路由时进行全局广播，而之后在此条路径上进行包的转发时，都可以确保选择的路径是经过跳数最少的。但是此类型的路由本质是将建表的开销均摊到之后的每一次转发中。每次转发产生的见表开销可以用公式

Overhead_avr＝Overhead_table/n

来描述，其中Overhead_avr表示每次转发均摊下来的开销，Overhead_table指的是建表的时候进行全局广播所产生的开销，n指的是在该条路径上进行包转发的次数。可预期的，对于静态网络，由于节点位置不产生变化，除非网络出现拥塞或者个别节点失去连接，不然理论上该条路径将一直是能够连通且最优的。n将会是一个较大的数，从而Overhead_avr将会是一个较小的值。而对于无人机自组织网络，由于无人机节点的高速移动性和网络拓扑的频繁变动，显然的，不论从可连通性还是从最优性上来说，在一对源节点-目的节点对上一直选择同一条路径是几乎不可能。用以上公式来描述的话，n将会是一个特别小的值，导致Overhead_avr将会是巨大的。即，若想在无人机自组织网络上运用传统的表驱动型路由，不可避免的在维护路由表上将产生巨大的开销，并且每次进行全局广播需要花费比较长的时间，而这期间网络拓扑可能又将产生变化，导致建立的路由表实质上是不匹配的。

基于地理信息的路由建立的假设是每个节点都能够知晓自己的地理位置信息，对于无人机自组织网络来说，本身机上的GPS模块可以提供此类支持。在地理信息路由中，路由决策是依据邻节点表信息进行的。以最经典的GPSR(Greedy Perimeter StatelessRouting,是一个典型的基于位置的路由协议，使用GPSR协议，网络节点都知道自身地理位置并被统一编址，各节点利用贪婪算法尽量沿直线转发数据)路由协议来说，每次进行转发时，节点首先会查询邻节点表，计算与目的节点的距离，并且选择距离目的节点最近的邻居节点进行转发。

为了维护邻居结点表，每个节点会定期广播自己的位置信息(以beacon(信标)包的机制)，在传输范围内的节点就会接收到此beacon包，并将此信息更新到自己的邻居节点表中。可以预期的，如果位置信息的更新频率不够高，就会导致邻居节点表中的位置信息包实时性不足，造成信息滞后，从而导致路由决策错误或者非最优。由位置信息滞后导致的路由决策错误可以通过图1进行说明。s表示源节点，d表示目的节点，n表示s的一个邻节点。黑色实心的n表示其当前的实际位置，白色空心的n’表示其在s的邻节点表上记录的位置，分表用二维数组(x_n,y_n)和(x’_n,y’_n)表示。由于beacon信息的滞后性，s会错误的判断n仍然在其传输范围内，并有可能选择其进行下一跳的转发，从而产生错误。

如果位置信息的更新频率过快，虽然此时位置信息的实时性足够了，又会导致beacon包的开销过大，影响网络负载，与数据包进行竞争，造成网络拥塞。

发明内容

为解决现有技术中的问题，本发明提供一种基于位置预测的无人机自组网地理信息路由方法，还提供一种实现位置预测的无人机自组网地理信息路由方法的系统。

本发明方法包括如下步骤：

S1：建立邻居节点表，其中，所述邻居节点表包括邻居节点ID号、及与所述邻居节点ID号对应的位置信息容器，所述位置信息容器中能够存储window个接收该邻居节点信标的时间及位置信息；

S2：根据邻居节点的位置信息容器中的信息预测邻居节点位置；

S3：根据预测的各个邻居节点位置进行路由决策。

本发明作进一步改进，信标的广播频率通过模糊控制器进行动态调节，所述位置信息容器中存储的接收该邻居节点信标的时间根据广播频率动态调节。

本发明作进一步改进，所述模糊控制器的处理方法包括如下步骤：

S101：采集步骤S2中的预测错误值及预测错误变化率，根据其对应的隶属函数，进行模糊化；

S102：根据模糊规则进行模糊推理；

S103：解模糊化，输出信标数据包的广播间隔。

本发明作进一步改进，在步骤S103中，采用的是中心加权平均值法解模糊化。

本发明作进一步改进，在步骤S1中，所述位置信息容器存储采用先进先出原则进行存储信息，当位置信息容器中的信标数量小于window时，就接着往里面填充信标，当位置信息容器里面的信标数量已经达到window个，若此时接收到新的信标广播包，则将位置信息容器里面最早接收到的信标广播包抛弃，填入新接收到的信标。

本发明作进一步改进，在步骤S2中，采用加权线性回归模型预测位置，所述加权线性回归模型生成的位置预测公式为：

x(t)＝a_xt+b_x

y(t)＝a_yt+b_y

其中，x,y分别代表二维坐标(x,y)，t代表当前时刻的时间，在上述公式中带入具体的时间即可求出该时刻的位置信息，a_x,b_x分别代表一次函数中的比例项和截距项。

本发明作进一步改进，所述位置预测公式推导过程采用最小二乘法，其处理过程包括：定义代价函数，对其求最小值的都拟合度最高的线性回归模型，然后对代价函数求偏导，再定义若干个中间变量，求解得到a_x,b_x值。

本发明还提供一种实现位置预测的无人机自组网地理信息路由方法的系统，包括邻居节点表建立模块：用于建立邻居节点表，其中，所述邻居节点表包括邻居节点ID号、及与所述邻居节点ID号对应的位置信息容器，所述位置信息容器中能够存储window个接收该邻居节点信标的时间及位置信息；邻居节点位置预测模块：用于根据邻居节点的位置信息容器中的信息预测邻居节点位置；路由决策模块：用于根据预测的各个邻居节点位置进行路由决策。

本发明作进一步改进，还包括模糊控制器，用于对信标的广播频率进行动态调节。

本发明作进一步改进，所述模糊控制器包括：模糊化单元：用于采集邻居节点位置预测模块的预测错误值及预测错误变化率，根据其对应的隶属函数，进行模糊化；模糊推理单元：用于根据模糊规则进行模糊推理；解模糊化单元：用于解模糊化，输出信标数据包的广播间隔。

与现有技术相比，本发明的有益效果是：通过引入位置预测机制和模糊控制器，形成一套能有效优化基于地理信息路由的机制，可适用于各式主流的基于地理信息路由协议。位置预测机制解决了由于位置信息滞后带来的路由决策错误，模糊控制器巧妙利用预测错误量和预测错误量的变化值作为输入，对beacon发送周期进行动态调节，有效减少了不必要的beacon资源浪费；应用于GPSR路由协议时，能够减少20％以上的无人机自组织网络通信过程中的丢包率，以及减少70％以上的beacon包的开销。

附图说明

图1为由位置信息滞后导致的路由决策错误示意图；

图2为本发明方法流程图；

图3为模糊控制器结构示意图；

图4为输入变量e各自然语义值所对应的隶属函数图像；

图5为输入变量e’各自然语义值所对应的隶属函数图像；

图6为输出变量bi各自然语义值所对应的隶属函数图像。

具体实施方式

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

如图2所示，本发明方法包括如下步骤：

S1：建立邻居节点表。

本例的邻居节点表具体结构见表2，其中，所述邻居节点表包括邻居节点ID号、及与所述邻居节点ID号对应的位置信息容器，所述位置信息容器中能够存储window个接收该邻居节点信标的时间及位置信息。

表2

与现有技术的位置信息表相比，不再仅仅只是记录邻节点的位置信息，而是维持一个叫beacon container的位置信息容器，里面存储着若干个beacon包，维持的beacon包个数用window表示；beacon包里面除了位置信息还有接收到beacon的时间。所述位置信息容器存储采用先进先出原则进行存储信息，当beacon container里面的beacon数量小于window时，就接着往里面填充beacon，当beacon container里面的beacon已经达到window个，若此时接收到新的beacon包，则将beacon container里面最早接收到的包抛弃，填入新接收到的beacon。现有技术的表中邻居节点只记录了一个以往的beacon信息，而在表2中，ID为3的表中记录的是一个存储beacon的位置信息容器，里面最多可以容纳window个beacon。这些beacon分别用beacon ID(1到window)来表示，1表示距离当前时刻最近的一次beacon信息。

S2：根据邻居节点的位置信息容器中的信息预测邻居节点位置。

在无人机自组织网络中，无人机在执行飞行任务时候，其飞行状态的变动不会产生剧烈的随机变化，而应该是有一定规律性的运动。为了降低由于位置信息的滞后性导致的路由决策错误，本发明利用了无人机自组织网络中无人机飞行状态的规律性，对其进行位置预测。位置预测的依据主要是根据邻节点表中的历史信息，采用加权线性回归的数学模型，代入时间即可求得某一时刻的位置信息。

所述加权线性回归模型生成的位置预测公式为：

x(t)＝a_xt+b_x

y(t)＝a_yt+b_y

其中，x,y分别代表二维坐标(x,y)，t代表当前时刻的时间，在上述公式中带入具体的时间即可求出该时刻的位置信息，a_x,b_x分别代表一次函数中的比例项和截距项。

所述位置预测公式推导过程采用最小二乘法，其处理过程具体为：

(1)定义代价函数J(a_x,b_x)，对其求最小值的都拟合度最高的线性回归模型。其中，

其中，w⁽ⁱ⁾表示beacon>

获得，其中t⁽ⁱ⁾代表ID为i的beacon的到达时间，t为当前时间，τ是一个调节因子，用来调节权重的变化幅度，τ的取值为非0的实数，τ越小权重变化越剧烈，一般情况下τ取[1,3]即可。

(2)对代价函数求偏导

(3)定义若干个中间变量

(4)求解得到a_x,b_x值，具体公式为：

S3：根据预测的各个邻居节点位置进行路由决策。

当某个节点需要进行转发包时它首先查看邻居节点表，若beacon container中的beacon信息数少于window，则选取最新的beacon信息作为该邻节点的位置信息(即表中beacon ID为1的包)，若beacon container中有window个beacon包，则进行加权线性回归，然后代入当前时刻的时间进行位置预测。经此过程获得了所有邻节点的位置信息之后，就可以通过这些信息进行路由决策。

在无人机自组织网络中，无人机的运动方式应该是有快有慢的，比如在追踪高速公路上的汽车时，无人机应该是高速移动的，而在进行静态的拍摄任务时，无人机应该是相对静止的或者移动缓慢的。在一次任务中，不同类型的移动方式，若采用同样的beacon广播频率，显然是不合理的。假如在高速移动的状态下，采用低频的beacon广播，就会加剧位置信息滞后性，而在低速状态下若采用高频的beacon广播，则会造成无意义的beacon开销，导致浪费。因此，相对合理的应该是beacon的广播要动态调节的进行，在移动性强的时候高频广播，移动性弱的时候低频广播。

如图3所示，本发明引入模糊控制器进行beacon广播频率的动态调节，，所述位置信息容器中存储的接收该邻居节点信标的时间根据广播频率动态调节。

具体地，所述模糊控制器的处理方法包括如下步骤：

S101：采集步骤S2中的预测错误值e将其作为第一输入变量，及预测错误变化率e’，将其作为第二输入变量，根据其对应的隶属函数，进行模糊化；

S102：根据模糊规则进行模糊推理；

S103：解模糊化，将信标数据包的广播间隔bi(即广播频率的倒数)作为输出。

在步骤S102中，本例的模糊规则见表3。

表3

其中，第一输入变量e的模糊化表见表4，第一列是e的范围，第二列是第一列的范围所对应的自然语义描述，第三列是相应的隶属函数。

表4

其中，模糊控制器的模糊化规则表4的第一列代表规则编号，第二三列代表输入变量的自然语义值，第四列代表二三列的自然语义值条件下所得到的输出变量的自然语义值。

输入变量e各自然语义值所对应的隶属函数图像如图4所示，横坐标表示e的数值，单位为米，纵坐标表示隶属与对应自然语义的程度，用[0,1]表示，0表述完全不属于，1表示完全属于。例如当e＝160时，根据图像我们大致可以判断出此时e有0.5的程度属于“低”，0.35的程度属于“中等”，完全不属于“非常低”、“高”、“非常高”。

第二输入变量e’的模糊化表见表5，第一列是e’的范围，第二列是第一列的范围所对应的自然语义描述，第三列是相应的隶属函数。

表5

输入变量e’各自然语义值所对应的隶属函数图像如图5所示，横坐标表示e’的数值，单位为米/秒，纵坐标表示隶属与对应自然语义的程度，用[0,1]表示，0表述完全不属于，1表示完全属于。例如当e’＝15时，根据图5，,大致可以判断出此时e’有0.25的程度属于“小”，0.3的程度属于“正中”，完全不属于“负大”、“负中”、“正大”。

在步骤S103中，本例采用的是中心加权平均值法解模糊化，从而确定具体的广播间隔值。其中，输出变量bi的模糊化表见表5，第一列是bi的范围，第二列是第一列的范围所对应的自然语义描述，第三列是相应的隶属函数。

表6

输出变量bi各自然语义值所对应的隶属函数图像如图6所示，横坐标表示bi的数值，单位为秒，纵坐标表示隶属与对应自然语义的程度，用[0,1]表示，0表述完全不属于，1表示完全属于。例如当bi＝7时，根据图6大致可以判断出此时bi有0.2的程度属于“中等”，0.38的程度属于“长”，完全不属于“非常短”、“短”、“非常长”。

本发明还提供一种实现位置预测的无人机自组网地理信息路由方法的系统，包括邻居节点表建立模块：用于建立邻居节点表，其中，所述邻居节点表包括邻居节点ID号、及与所述邻居节点ID号对应的位置信息容器，所述位置信息容器中能够存储window个接收该邻居节点信标的时间及位置信息；邻居节点位置预测模块：用于根据邻居节点的位置信息容器中的信息预测邻居节点位置；路由决策模块：用于根据预测的各个邻居节点位置进行路由决策。

优选地，本发明系统还包括模糊控制器，用于对信标的广播频率进行动态调节。

所述模糊控制器包括：模糊化单元：用于采集邻居节点位置预测模块的预测错误值，根据其对应的隶属函数，进行模糊化；模糊推理单元：用于采集预测错误变化率，根据其对应的隶属函数及模糊规则进行模糊推理；解模糊化单元：用于解模糊化，输出信标数据包的广播间隔。

本发明的主要创新点有：

(1)本发明对位置节点表进行改进，从而根据位置节点表的历史数据能够有效的进行位置预测，位置预测采用加权线性回归模型，具有实时性好，模型简单，有效准确的特点；

(2)本发明的模糊控制器参数及规则的选取，具有结构简单，逻辑清晰，有效的特点。

本发明具有以下突出的有益效果：

通过引入位置预测机制和模糊控制器，形成一套能有效优化基于地理信息路由的机制，可适用于各式主流的基于地理信息路由协议，如GPSR，DREAM(Distance RoutingEffect Algorithm for Mobility，移动距离效应路由)，LAR(Location Aided Routing，位置辅助路由)。位置预测机制解决了由于位置信息滞后带来的路由决策错误，模糊控制器巧妙利用预测错误量和预测错误量的变化值作为输入，对beacon发送周期进行动态调节，有效减少了不必要的beacon资源浪费；除此之外，本发明无需任何额外的硬件层面投入，仅仅进行算法层面的改进。

通过将本机制应用于GPSR协议进行实验分析，数据显示，本发明能够减少20％以上的无人机自组织网络通信过程中的丢包率，以及减少70％以上的beacon包的开销。

以上所述之具体实施方式为本发明的较佳实施方式，并非以此限定本发明的具体实施范围，本发明的范围包括并不限于本具体实施方式，凡依照本发明所作的等效变化均在本发明的保护范围内。