Ad Hoc网络中基于Q学习和信任模型的路由方法

摘要

本发明公开了一种Ad Hoc网络中基于Q学习和信任模型的路由方法，主要解决了Ad Hoc网路中安全路由寻找的问题。本发明实现步骤是：(1)生成Q值表；(2)计算每个节点相邻节点的总数；(3)节点评估与其相邻的每个节点的信任值；(4)分配信任奖励；(5)获取即时奖励；(6)获取聚合奖励；(7)更新Ad Hoc网络节点的Q值表中的Q值；(8)判断路由请求包中的当前节点是否为目的节点，若是，则执行步骤(9)，否则，执行步骤(6)；(9)建立正向路由信息；(10)发送数据包。发明实现了信任模型、Q学习算法和路由技术的结合，能够根据Ad Hoc网络环境动态寻找全局最优路由，有效提高了网络的安全性和稳定性。

说明书

技术领域

本发明属于通信技术领域，更进一步涉及网络通信技术领域中的一种Ad Hoc网络中基于Q学习和信任模型的路由方法。本发明在信任模型基础上，应用Q学习对Ad Hoc网络环境中的节点作信任评估，寻找可信度最高的路由，可用于在Ad Hoc网络中寻找安全路由路径。

背景技术

移动Ad Hoc网络是由若干个相对独立的移动节点集聚在一起组成的具有自组织能力和快速部署能力的嵌入式无线网络，该网络得以高效正常运转依赖于网内所有节点具有高可信性且相互间以诚信的协作方式运行。

山东中弘信息科技有限公司在其申请的专利文献“一种基于包转发率的无线自组网可信路由协议”(申请号：201410579270.2，公开号：CN 104301222 A)中公开了一种基于包转发率的无线自组网可信路由方法。该方法采用包转发率模型计算每个节点的信任值，之后源节点发起一个路由发现过程，通过路由请求和路由应答实现，路由请求包从源节点开始寻找一跳范围内信任值最大的节点，经中间结点至目标节点，该过程每一跳均是寻找下一跳信任值最大的节点进行转发。路由请求包到达目标节点后，目标节点向源节点发送路由应答包建立路由路径。该方法存在的不足之处是：在路由寻找过程中，每次仅从一跳范围内选择信任值最大的节点进行数据传输，不能从全局考虑路由路径，容易陷入局部最优，难以获得全局最优路由路径。

青岛大学在其申请的专利文献“一种移动Ad Hoc网络中双向可信路由确定方法”(申请号：201510943519.8，公开号：CN 105471741 A)中公开了一种移动Ad Hoc网络中可信路由确定方法，该方法通过源节点发送路由请求，中间节点接收到请求报文后，计算请求报文所经路径的反向可信值，判断是否大于预设可信阈值；目的节点收到请求报文后，发送回复报文，中间节点接收到回复报文后，计算回复报文所经路径的正向可信值，判断是否大于预设可信阈值，如果是，则将回复报文返回至源节点建立路由路径。该方法存在的不足之处是：未考虑网络资源因素，面对移动Ad Hoc网络带宽较窄、能量不足、内存有限等实际，该方法在信任值计算中进行了双向两次计算和判断，占用内存大，消耗能量快，随着网络资源消耗，会使路由频繁中断丢包，影响网络传输性能。

发明内容

本发明的目的在于针对上述已有技术的不足，提供一种Ad Hoc网络中基于Q学习和信任模型的路由方法，解决寻找Ad Hoc网络全局信任度最高和能量最好的路由路径的问题，有效提高了网络的安全性和稳定性。

实现本发明目的的思路是：通过引入信任模型评估Ad Hoc网络每个节点的可信度，分配，通过动态量化网络资源消耗情况计算即时奖励，采用Q学习算法依据信任奖励和即时奖励寻找全局最优路由，使网络能够选择信任度最大和资源最好的路由路径，提高网络的安全性稳定性。

本发明的具体步骤如下：

(1)生成Q值表：

(1a)将Ad Hoc网络中每个节点对应的路由表扩展为Q值表，在该表中增加每个节点对应的Q值、信任值、学习率字段；

(1b)将Q值表中的Q值初始设置为0，信任值T初始设置为1，学习率α初始设置为0.8，路由初始设置为空；

(2)计算每个节点相邻节点的总数：

Ad Hoc网络中每个节点广播HELLO数据包，与广播节点相邻的一跳邻居节点响应HELLO数据包，累加一跳邻居的个数并记录总数；

(3)节点评估与其相邻的每个节点的信任值：

(3a)计算每个节点与其相邻的每个节点在预设交互次数后的控制分组数：

(3b)计算每个节点与其相邻的每个节点在预设交互次数后的数据分组转发率：

(3c)用每个控制分组数加数据分组转发率之和再除以2，得到该节点与其相邻的每个节点的信任值；

(4)分配信任奖励：

(4a)找出每个节点与其相邻节点信任值大于第一个阈值的节点，将该节点的相邻节点分配信任奖励1后，存入该节点的Q值表中；

(4b)找出每个节点与其相邻节点信任值小于第一个阈值且大于第二个阈值的节点，将该节点的相邻节点分配信任奖励0.5后，存入该节点的Q值表中；

(4c)找出每个节点与其相邻节点信任值小于第二个阈值的节点，将该节点的相邻节点分配信任奖励0后，存入该节点的Q值表中；

(5)获取即时奖励：

用每个节点的相邻节点的电池电量值、内存值、带宽值求和后再除以3，得到该节点与其相邻的每个节点的即时奖励；

(6)获取聚合奖励：

用每个即时奖励与0.7倍信任奖励之和再除以2，得到该节点与其相邻的每个节点的聚合奖励；

(7)按照下式，更新Ad Hoc网络节点的Q值表中的Q值：

其中，Q(s,a)表示Ad hoc网络第s个节点选择动作a的Q值，α表示取值为0.8的学习率，R表示将聚合奖励赋值给立即奖励，γ表示取值为0.8的折扣因子；

(8)判断Ad Hoc网络的路由请求包中的当前节点是否为目的节点，若是，则执行步骤(9)，否则，执行步骤(6)；

(9)建立正向路由信息：

(9a)由目的节点开始，向其邻居节点发送路由应答包；

(9b)路由应答包的每一跳选择Q值最大的相邻节点作为下一跳节点，并将路由应答包传送给下一跳节点，建立正向路由信息；

(10)发送数据包：

当路由应答包到达源节点时，从源节点到目的节点的路由路径完成建立，源节点开始按照路由表信息发送数据包。

本发明与现有技术相比具有以下优点：

第一，由于本发明采用信任模型计算Ad Hoc网络每个节点的信任值，并按信任奖励采用Q学习算法寻找路由路径，实现了从Ad Hoc网络全局评价每条路由路径可信度，克服了现有技术每次仅从一跳范围内选择信任度最大的节点进行数据传输，容易陷入局部最优的缺点，使得本发明具有在复杂网络环境下从全局考虑，建立全局最优路由路径的优点。

第二，由于本发明在获取即时奖励时量化了电池电量、带宽、内存网络资源，从AdHoc网络全局评价每条路由路径资源的大小，克服了现有技术在网络资源大量消耗后不能及时调整路由的缺点，使得本发明具有在Ad Hoc网络长时间运行时有效避免丢包和频繁中断的优点。

附图说明

图1是本发明的流程图。

具体实施方式

下面结合附图1对本发明作进一步的描述。

步骤1，生成Q值表。

将Ad Hoc网络中每个节点对应的路由表扩展为Q值表，在该表中增加每个节点的Q值、信任值、学习率字段。

将Q值表中的Q值初始设置为0，信任值T初始设置为1，学习率α初始设置为0.8，路由初始设置为空。

步骤2，计算每个节点相邻节点的总数。

Ad Hoc网络中每个节点广播HELLO数据包，与广播节点相邻的一跳邻居节点响应HELLO数据包，累加一跳邻居的个数并记录总数。

步骤3，节点评估与其相邻的每个节点的信任值。

计算每个节点与其相邻的每个节点在预设交互次数后的控制分组数。

所述的按照下式计算每个节点与其相邻的每个节点在预设交互次数后的控制分组数：

其中，C_ij(n)表示第i个节点与其相邻的第j个节点在n次交互后的控制分组数，i的取值范围为[1,t]，t表示Ad>ij(n)表示第i个节点与第j个节点在n次交互后第i个节点发送给第j个节点的路由请求包数，Y_ij(n)表示第i个节点与第j个节点在n次交互后第j个节点发送给第i个节点的路由应答包数，E_ij(n)表示第j个节点在网络中n次交互后接收的路由错误包数，H_ij(n)表示第j个节点在Ad>

计算每个节点与其相邻的每个节点在预设交互次数后的数据分组转发率。

所述的按照下式计算每个节点与其相邻的每个节点在预设交互次数后的数据分组转发率：

D_ij(n)＝F_ij(n)/G_ij(n)

其中，D_ij(n)表示第i个节点与第j个节点在n次交互后的数据分组转发率，F_ij(n)表示n次交互后第i个节点向第j个节点实际发送的数据包总数；G_ij(n)表示n次交互后第j个节点从第i个节点实际接收的数据包总数。

用每个控制分组数加数据分组转发率之和再除以2，得到该节点与其相邻的每个节点的信任值。

步骤4，分配信任奖励。

找出每个节点与其相邻节点信任值大于第一个阈值的节点，将该节点的相邻节点分配信任奖励1后，存入该节点的Q值表中。

找出每个节点与其相邻节点信任值小于第一个阈值且大于第二个阈值的节点，将该节点的相邻节点分配信任奖励0.5后，存入该节点的Q值表中。

找出每个节点与其相邻节点信任值小于第二个阈值的节点，将该节点的相邻节点分配信任奖励0后，存入该节点的Q值表中。

步骤5，获取即时奖励。

用每个节点的相邻节点的电池电量值、内存值、带宽值求和后再除以3，得到该节点与其相邻的每个节点的即时奖励。

步骤6，获取聚合奖励。

用每个即时奖励与0.7倍信任奖励之和再除以2，得到该节点与其相邻的每个节点的聚合奖励。

步骤7，按照下式，更新Ad Hoc网络节点的Q值表中的Q值。

其中，在Q学习算法中，Ad Hoc网络中每个节点表示一个状态，例如，第s个节点表示状态s，a表示该节点向相邻节点中的一个节点发送数据的动作，Q(s,a)代表该(状态，动作)对所对应的Q值，α表示取值为0.8的学习率，R表示取值聚合奖励的立即奖励，γ表示取值为0.8的折扣因子，更新Q值表的步骤如下：

第1步，检查Q值表，确定Q值初始为0；

第2步，观察当前网络状态并设为s；

第3步，根据当前状态s选择数据转发动作a；

第4步，获得立即奖励R；

第5步，观察新的网络状态s′，在该状态下选择使Q值最大的动作a′；

第6步，按公式从右至左计算迭代更新Q值；

第7步，把新状态s′赋值给s；

第8步，判断Q值表是否收敛，若是，则结束Q值表更新，否则，执行步骤5。

步骤8，判断Ad Hoc网络的路由请求包中的当前节点是否为目的节点，若是，则执行步骤9，否则，执行步骤6。

步骤9，建立正向路由信息。

由目的节点开始，向其邻居节点发送路由应答包。

路由应答包的每一跳选择Q值最大的相邻节点作为下一跳节点，并将路由应答包传送给下一跳节点，建立正向路由信息。

步骤10，发送数据包。

当路由应答包到达源节点时，从源节点到目的节点的路由路径建立完成，源节点开始按照路由表信息发送数据包。