基于投递概率SV捎带的机会网络低开销路由方法

摘要

本发明属于机会网络领域，具体涉及一种基于投递概率SV捎带的机会网络低开销路由方法，该方法由节点相遇感知、数据交互和投递概率信息更新三个阶段的操作组成，包含基于SV的投递概率捎带、精简SV交换、基于消息捎带的数据交互和自适应缓存管理4种新机制，解决现有机会网络中基于议价博弈的相关路由方法使用专门的数据结构存储和传送投递概率存在的通信开销偏大、SV消息交换过程中控制消息在数量上存在冗余、数据分组交互过程存在冗余操作以及分组删除时可能删除对方节点的请求消息导致无谓的开销和时延等问题，从而在不影响机会网络正常路由的情况下降低节点的通信开销，有利于提升网络吞吐量，节约节点能量和网络的无线带宽资源。

说明书

技术领域

本发明属于使用机会网络(opportunistic networks)技术的领域，尤其涉及在网络中采用议价博弈的方法对自私节点的合作行为进行激励和促进的场合。

背景技术

机会网络是一种不需要在源节点和目的节点之间存在完整链路，利用节点移动带来的相遇机会实现通信的时延和分裂可容忍的无线自组织网络。在军事、灾难救助以及偏远野外地区等领域有着广泛的应用。目前，机会网络的研究是基于节点具有良好的协作性。然而，由于机会网络中节点的资源有限，节点为节约自身资源会拒绝为其他节点转发消息，这种自私行为势必会严重影响机会网络正常的路由和数据转发功能，从而导致网络性能退化。因此机会网络中的节点自私性问题是一个迫切需要解决的问题。

近年来，随着基于博弈论的机会网络路由方法研究工作的逐步深入，当前很多学者已经将博弈论引入到机会网络中来，并设计了一些方法，其中比较典型的有Watchdog(参见文献：Marti S,Giuli T J,Lai K,et al.Mitigating routing misbehavior in mobilead hoc networks[C].International Conference on Mobile Computing andNetworking,Boston,USA,2000:255-265)、TFT(参见文献：Neely M J,GolubchikL.Utility optimization for dynamic peer-to-peer networks with tit-for-tatconstraints[C],2011IEEE International Conference on Computer Communications,Shanghai，China，2011:1458-1466)、IRONMAN(Incentives and Reputation forOpportunistic Networks using Social Networks，参见文献：Bigwood G,HendersonT.IRONMAN:Using social networks to add incentives and reputation toopportunistic networks[C].2011IEEE International Conference on Privacy,Security,Risk and Trust,and IEEE International Conference on SocialComputing,2011:65-72)、CRGTD(Credit-based Repeaded Game Model applied inTransfer Decision，参见文献：张程，刘慧君，陈自郁等.基于信用的重复博弈模型在节点转发中的应用[J].解放军理工大学学报，2012,13(2):152-158)、Barter(参见文献：Buttyan L,Dora L,Felegyhazi M,et al.Barter Trade Improves Message Delivery InOpportunistic Networks[J].Ad Hoc Networks,2010,8(1):1-14)和GSCP(参见文献：FanW,Tingting C,Zhong S,et al.A Game-Theoretic Approach to Stimulate Cooperationfor Probabilistic Routing in Opportunistic Networks[J].IEEE Transactions onWireless Communications,2013,12(4):1573-1583)等。

Watchdog方法的主要思路是节点把发送给下一跳节点的消息放在缓冲区中，然后利用广播信道的特性，侦听下一跳节点是否转发了该消息。若在规定的时间内下一跳无更改地转发了此消息，则说明下一跳行为良好；反之则说明下一跳出现了不合作行为，将其判定为自私节点。Watchdog在普通移动自组网中表现良好，但由于机会网络中节点的移动性，这样的判定方式没有考虑由于分组碰撞、下一跳节点脱离通信范围等情况导致的监听失败情况而容易导致误判，并且该方法只利用自身节点的观察信息，缺少与其余节点的交互。

TFT方法的主要思想是各节点都是以协作策略开始博弈，在以后的每个阶段，节点都会模仿对方节点在上一阶段的行为。基于TFT机制的路由方法采用的检测和奖励节点无私行为的思想有利于对节点行为的正面引导，但源节点计算转发路径在间断/部分连接的拓扑条件下有可能遇到困难，而目的节点广播确认消息则易使控制开销增加。而且节点间只能实现相同业务量的传输，因此该方法只适用于业务完全对等的网络。但在实际应用中，大部分业务都是非对称业务，使得该方法难以实现较好的网络性能。

IRONMAN是一种基于节点历史行为的Reputation方法，根据该方法，每个节点维护一个表征自私程度的信誉值参数，两个节点相遇后会交换相遇次数、交换的数据分组和交换历史等信息，于是，一个节点就可以根据这种信息(如是否收到了自己转发的数据分组、是否在帮其它节点转发数据分组等)来更新对方和其它节点的信誉值，从而判断它们的自私性。但由于机会网络中任意两个节点相遇的时间具有不确定性，这就使得IRONMAN方法可能因下一跳节点尚未遇到目的节点而产生误判，同时信誉值阈值的准确设置也是一个有待解决的问题。

CRGTD是一种基于信用和重复博弈的欺诈行为解决方法，通常与感染路由机制结合在一起运行，在节点相遇时进行控制信息和消息的交换。CRGTD方法引入了信用合作机制，将单次阶段博弈行为转变为网络运行时间内的重复博弈过程，并设置了惩罚措施和惩罚周期，在惩罚周期内对有欺诈行为的节点进行惩罚，拒绝转发来自或发往这类节点的消息。CRGTD方法检测节点欺诈行为的方法是预先设定节点选择交易策略的规则，如果节点按规则选择交易策略，则认为它在交易中行为诚实，否则便认为存在欺诈行为。CRGTD方法可以有效抵制节点在报告自身情况时的欺诈行为，但由于单次欺诈行为导致的博弈失败不足以判断节点为不诚信节点，因此它在不诚信节点的判定上收敛偏慢。

Barter是一种典型的基于博弈理论的机会网络路由方法，该方法在相遇的成对节点中交换信息，能够较好地适应机会网络分布式的拓扑结构，不需要对节点的自私性进行监视，在一定程度上缓解自私节点对网络性能的影响，但Barter方法遵循等量交换原则，消息交换的数量由可交换消息数量少的一方决定，进行等量交换,如果一个节点有消息需要转发，但对方节点无该节点需要的消息或者无足够消息用于交换，则会导致部分消息难以传递造成网络陷入僵局，消息等待时延增加。

GSCP是一种基于议价博弈(Bargaining Game)的节点合作激励路由方法，GSCP认为网络中消息的价值量是不同的，消息对于相同目的节点相遇概率更高的节点具有更大的价值，GSCP将节点对之间的消息交换过程建模为一次议价博弈，在该博弈中，买卖双方需要为消息的转发在价格上达成一致，并且一个消息要经过多次转发才能从源节点到达目的节点，因此它在传送的过程中要经历一系列的议价博弈，从而使得消息从价值量低的节点向价值量高的节点传输，即消息传送成功率概率随着交易的进行而越来越大，最终到达目的节点，从而促进网络性能。但是，它定义的节点两两博弈在多节点连通拓扑的情况下有可能因博弈方偏少而失去交易机会，而且集中式的信用清算中心在间断/部分连接的网络拓扑中能否及时清算也是一个需要注意的问题。

综上所述，为了在含自私节点的机会网络中激励节点协作，人们对基于博弈论的机会网络路由方法、尤其是近年来使用议价博弈的激励方法开展了持续的研究工作，并取得了一定的成果。但我们经过深入研究之后发现，现有的基于议价博弈的机会网络路由方法还存在以下四个问题：

1.使用专门的数据结构存储和传送投递概率矩阵，带来不必要的通信开销。

2.SV交换机制含有冗余的控制分组，在节点相遇后的控制消息交换过程中需要收发2个SV消息和2个Request消息，在控制消息的数量上存在冗余。

3.现有的机会网络中采用议价博弈的路由方法在消息交易过程存在分组冗余交互操作，带宽资源产生浪费。

4.节点建立连接之后,若缓存空间不足需执行缓存管理策略以接收新消息时，有可能删除缓存中对方节点请求矢量中的消息，即对方节点即将请求的消息被删除，导致无谓的开销和时延。

上述问题的存在导致机会网络的通信开销偏大，降低了网络带宽资源利用率，为了提高机会网络的吞吐量等性能，有必要提出新的路由方法对它们加以解决。本发明将针对这些问题提出切实可行的解决方案。

发明内容

为了解决上述四个问题，本发明提出一种新的、基于投递概率SV捎带的低开销路由新方法，该方法由节点相遇感知、数据交互和投递概率信息更新三个阶段的操作组成，包含“基于SV的投递概率捎带”、“精简SV交换”、“基于消息捎带的数据交互”和“自适应缓存管理”4种新机制，解决了上述单独传送投递概率矩阵开销较大、SV交换数量冗余、数据分组交互过程冗余、以及分组删除不当时增加开销四个问题，从而在不影响机会网络正常路由的情况下降低了节点的通信开销，有利于提升网络吞吐量，节约节点能量和网络的无线带宽资源。

(一)本发明提出的新机制的基本原理

以下具体介绍本发明提出的“基于SV的投递概率捎带”、“精简SV交换”、“基于消息捎带的数据交互”和“自适应缓存管理”4种新机制的基本原理。

1.基于SV的投递概率捎带

在现有基于议价博弈的机会网络路由方法中，节点主要使用专门的数据结构即投递概率矩阵来存储和传送投递概率信息，当投递概率矩阵经过数据链路层封装成帧时，不可避免的带来帧首部和帧尾部开销，通过将投递概率信息SV捎带，可有效减少单独传输投递概率矩阵带来的通信开销。

“基于SV的投递概率捎带”新机制的基本思路是：基于议价博弈的机会网络路由方法中，节点i的汇总矢量链表中的任一结构体表示该节点存储的到网络中其他目的节点j的分组的消息摘要M_n，我们简化为由消息源节点Src，消息目的节点Dest_j，分组序列号m_id表示，其存储的投递概率二维矩阵由网络中的任一节点j的节点标识Dest_j，节点i到j的投递概率P_ij表示。投递概率信息SV捎带的设计原理是：当网络中的任一节点i首次接收并存储到节点j的分组时，在汇总矢量SV中使用含4个变量的结构体<Src，Dest_j，m_id，i到j的投递概率P_ij>表示该消息摘要并捎带节点i到节点j的投递概率；当节点i再次接收到该目的节点j的分组时，使用含3个变量的结构体<Src，Dest_j，m_id>表示该消息摘要；当节点i未存储到网络中某节点k的分组时，使用含2个变量的结构体<Dest_k，i到k的投递概率P_ik>来捎带节点i到节点k的投递概率，为方便相遇节点识别截取合适长度的SV，在SV包的首部增加2个长度为16bit的标志位用以区分上述三种不同结构体的长度，该标志位的开销32bit远小于单独传输投递概率矩阵经过数据链路层封装成帧时帧首部和尾部的开销8Bytes(如使用PPP协议)，从而实现在减小开销的情况下投递概率矩阵的捎带传输。“基于SV的投递概率捎带”新机制的操作流程如说明书附图4(1)所示。

2.精简SV交换

传统的基于议价博弈的路由方法在SV消息交换过程中需要收发2个SV消息和2个Request消息,在控制消息的数量上存在冗余,为解决该问题，我们提出了“精简SV交换”的新机制，该新机制基本原理如下：

节点A、B相遇后，若A节点收到B节点的汇总矢量SV，则不再给对方发送汇总矢量信息，而是将其与自存的汇总矢量分别复制生成1个副本，从收到的B的汇总矢量副本中移出自己产生的和已存储的消息以及投递概率比自身高的消息，可得到本节点A的数据分组请求矢量；同理，A节点可得到相遇节点B的数据分组请求矢量从而可以主动向节点B发送数据分组，本发明取消一个SV消息和一个Request消息的交互，从而降低了节点的通信开销以及能量与网络带宽的消耗。“精简SV交换”新机制的操作流程如说明书附图5(1)所示。

3.基于消息捎带的数据交互

传统的基于议价博弈的路由方法中，卖方节点根据交易费用函数制定出的价格即使是博弈双方的最优价格，买方节点仍需要回复接受报价消息告知卖方节点自己同意本次交易，数据交互过程存在冗余操作，浪费网络带宽资源。

“基于消息捎带的数据交互”新机制的基本原理是：节点A、B相遇后，在消息的议价博弈过程中，若节点A需要交易某个消息时，可在请求消息中直接出价，并且由于节点A可计算得到对方节点B的数据分组请求矢量，故可根据该分组请求矢量中的请求消息进行主动要价，节点B接受上述出价和要价时就直接发送节点A的请求消息并捎带消息“接受要价”，节点A收到后可直接给B发送其需要的消息，本发明可明显减少节点之间的数据交互，有利于减少开销，降低消息传输时延以及节约网络带宽资源。“基于消息捎带的数据交互”新机制的操作流程如说明书附图6(1)所示。

4.自适应缓存管理

假设节点缓存空间不足删除消息时按照LIFO机制，即首先删除的是缓存队列尾部的消息。在传统的机会网络路由方法中，当中继节点的缓存空间不足需执行分组删除策略时有可能删除对方节点请求矢量中的消息，将会导致相遇节点重复请求而带来额外开销，为解决该问题，我们提出了“自适应缓存管理”的新机制，该新机制基本原理如下：

新消息到达时，若节点尚有足够的缓存空间，则直接接收；反之，当缓存空间不足需要丢包时，若队列尾部消息不是对方节点的请求消息，则可直接删除以接收新消息，否则，不删除缓存队列尾部消息，从该消息的下一个消息开始继续执行上述缓存管理方法。

(二)本发明的有益效果

本发明的有益效果主要是：在不影响机会网络正常路由和激励策略的前提下，降低开销，促进有效数据的交互，从而提升网络吞吐量和数据时延等性能。主要体现在以下四个方面：

1.在传统的基于议价博弈的路由方法中，节点使用专门的数据结构存储和传送投递概率矩阵，造成节点的通信开销偏大。而本发明提出的将投递概率信息存入汇总矢量的机制不需要专门的数据结构，并且在减小开销的情况下便能实现投递概率信息的存储和传输。

2.传统的基于议价博弈的路由方法在SV消息交换过程中需要收发2个SV消息和2个Request消息。而在本发明中，仅需要收1个SV消息，发1个Request消息，便可实现相同的请求矢量确定功能。在不影响消息传递的情况下，减少了控制消息的数量，从而降低了节点的通信开销以及能量的消耗。

3.在传统的基于议价博弈的路由方法中，即使卖方节点根据交易费用函数制定出的价格是博弈双方的最优价格，买方节点仍需要回复接受报价消息告知卖方节点自己同意本次交易，交互过程存在冗余造成开销偏大。而在本发明中基于消息捎带机制将节点间的数据交互过程精简，从而减少开销，降低时延。

4.传统的机会网络路由方法中，当中继节点的缓存空间不足需执行缓存管理策略时有可能删除对方节点请求矢量中的消息，而本发明所提出的自适应缓存管理机制在分组删除时首先判断该分组是否是对方节点的请求分组，从而在不增加额外开销的情况下提升吞吐量，降低时延。

附图说明

图1为本发明中基于投递概率SV捎带的低开销路由方法的组成示意图

图2为本发明中发送节点感知流程示意图

图3为本发明中接收节点感知流程示意图

图4为本发明提出的用汇总矢量捎带投递概率的方法示意图

(1)存入投递概率后的汇总矢量(2)未存储投递概率的汇总矢量

(3)投递概率矩阵示意图

图5为本发明定义的SV交换过程与原始的SV交换过程对比示意图

(1)本发明定义的SV消息交换过程(2)原始的SV消息交换过程

图6为本发明中基于消息捎带的数据交互示意图

(1)本发明定义的分组交换过程(2)原始的分组交换过程

具体实施方式

在一个包含多个物理性质相同、逻辑地位平等的节点的机会网络中，存在自私节点(不为其它节点转发数据分组的节点)，节点能够自由移动；每个节点既是业务的源节点，也是业务的目的节点，同时也能够为其它节点转发数据；节点相遇时会交换数据分组以及各自携带和作为目的节点收到的数据分组的情况(如Summary Vector，SV，汇总矢量表)，在操作上分为节点相遇感知、数据交互和投递概率更新三个阶段，如图1所示，其具体实施方式如下：

阶段1.节点相遇感知

该阶段包含以下三个步骤：

步骤1：节点周期性广播Hello消息。

当节点暂时处于静止状态时，会以一定的发送功率固定的周期重复广播Hello消息，Hello消息包含节点的标识等相关的标识信息。

步骤2：感知相遇节点。

当两个节点进入对方的通信范围之后，会启动节点发现过程，它们分别独立的在各自的物理层和网络层通过2种方式感知，并判定与对方节点的相遇：①物理层收到对方周期性广播的Hello消息；②网络层收到对方节点单播的目的地址为自己的数据包。同时满足这两个条件便符合节点的相遇条件。

步骤3：记录相遇节点信息

如果当前节点确定与其他节点相遇，则将相遇节点信息的标识存入邻居表，并进行下一阶段的操作。

图2为发送节点感知的主要流程示意图，图3为接收节点感知的主要流程示意图。

阶段2.数据交互

图6(1)为本发明中基于消息捎带的数据交互示意图，当节点经过相遇感知后，会进入下一步的数据交互的过程，该阶段包含以下两个步骤：

步骤1：节点发送SV消息。

首先，当节点收到相遇节点对Hello消息的应答后，会立即给相遇节点发送一个捎带有投递概率信息的汇总矢量消息，说明中“基于SV的投递概率捎带机制”是在本步骤中实现的，汇总矢量SV消息的包结构如图4(1)所示，SV消息中捎带的投递概率信息包括本节点与网络中其他节点接触概率的统计。当节点相遇时，会以节点保存的历史相遇概率信息P_(a,b)old为基础来更新投递概率信息，投递概率的计算由公式1来计算，

P_(a,b)＝P_(a,b)old+(1-P_(a,b)old)*P_int(1)

加入投递概率信息后，SV链表中有三种类型的结构体，结构体变量个数分别为2、3、4。当网络中的任一节点i首次接收并存储到节点j的分组时，在汇总矢量SV中使用含4个变量的结构体<Src，Dest_j，m_id，i到j的投递概率P_ij>表示该消息摘要并捎带节点i到节点j的投递概率；当节点i再次接收到该目的节点j的分组时，使用含3个变量的结构体<Src，Dest_j，m_id>表示该消息摘要；当节点i未存储到网络中某节点k的分组时，使用含2个变量的结构体<Dest_k，i到k的投递概率P_ik>来捎带节点i到节点k的投递概率，为方便相遇节点识别截取合适长度的SV，在SV包的首部增加2个长度为16bit的标志位用以区分上述三种不同结构体的长度。分别表示变量个数为4的结构体个数以及变量个数为3的结构体个数，以便接收节点截取识别合适长度的汇总矢量。

在这个阶段中，SV交换的过程精简为如图5(1)所示，说明中“精简SV交换”是在本步骤中实现的，其具体操作是节点收到对方汇总矢量后，不再给对方发送汇总矢量信息，而是将其与自存的汇总矢量分别复制生成1个副本，从收到的汇总矢量副本中移出自己产生的和已存储的消息以及投递概率比本节点高的消息，可得到本节点的数据分组请求矢量；同理，可得到相遇节点的数据分组请求矢量。得到本节点以及相遇节点的数据分组请求矢量后进行下一阶段的操作。

步骤2：数据传输。

本步骤包含以下2个子步骤：

1)发送节点发送数据

在节点A、B对消息议价博弈过程中，假设节点A需要交易某个消息时，可在请求消息中直接出价，并且由于节点A可计算得到对方节点B的数据分组请求矢量，故可根据该分组请求矢量中的请求消息进行主动要价，节点B接受上述出价和要价时就直接发送节点A的请求消息并捎带消息“接受要价”，节点A收到后可直接给B发送其需要的消息。说明中“基于消息捎带的数据交互机制”是在本步骤中实现的，其数据交互示意图如图6(1)所示。

2)接收节点执行缓存管理策略

说明中“自适应缓存管理机制”是在本步骤中实现的，其具体操作步骤为：若新消息到达时，节点尚有足够的缓存空间，则直接接收该消息；反之，当缓存空间不足需要丢包时，若队列尾部消息不是对方节点的请求消息，则可直接删除以接收新消息，否则，不删除缓存队列尾部消息，从该消息的下一个消息开始继续执行上述消息删除策略。

阶段3.投递概率更新

本阶段的投递概率更新操作分为两种情况：

1)节点a,b相遇后，以节点保存的历史相遇概率信息P_(a,b)old为基础计算新的接触概率，并更新投递概率信息，其计算公式如公式(2)所示：

P_(a,b)＝P_(a,b)old+(1-P_(a,b)old)*P_int(2)

2)投递概率具有传递性，即如果节点a,b相遇频繁，节点b,c相遇频繁，则节点a,c之间的接触概率可以利用公式(2)计算出的P_(a,b)和P_(b,c)间接计算，其计算公式如公式(3)所示，其中β表示传递性对投递概率的影响权重。

P_(a,c)＝P_(a,c)old+(1-P_(a,c)old)*P_(a,b)*P_(b,c)*β(3)。