一种基于消息重要程度的机会网络队列管理调度方法

摘要

本发明请求保护一种基于消息传输状态的机会网络自适应队列管理方法，涉及无线网络领域。本发明针对机会网络现有的队列管理方法中没有考虑节点活跃程度，也没有将节点特性反映到消息中的局限性，提出节点活跃程度的估计方法，该方法只需根据当前本地节点保存的信息即可估计不同节点之间的活跃程度差异，并根据节点活跃程度评估消息的传输状态以及重要程度，进而设计了一种基于消息传输状态的机会网络自适应队列管理方法，以消息传输状态为依据，合理地利用节点存储资源。本发明提出的节点活程度评估方法比较准确，同时消息重要程度感知的自适应队列管理策略能有效提高消息成功投递率，降低网络平均时延和网络负载率。

说明书

技术领域

本发明涉及无线网络领域，尤其涉及机会网络中的队列管理机制。

背景技术

大量手持智能移动设备的普及推动了无线自组织网的应用。在复杂的无线网络中，由于节点移动、信号衰减等原因，网络常常会中断。但传统的无线自组织网要求在源节点和目标节点间至少有一条确定链路，因而无法适应这样的环境。区别于传统的无线自组织网的通信模式，机会网络中的节点在转发数据之前，并不需要建立端到端路径，而是利用节点之间的相遇机会进行数据转发，直至到达目的节点。这种全新的通信方式引起了业内人士的极大兴趣，被认为是未来无线网络发展的方向之一。

机会网络以更加灵活的存储-携带-转发模式实现互连互通、移动计算。在消息转发过程中，多个节点将对需要转发的消息进行保存，显然，对于节点处理能力、存储能力等比较有限的情况下，有效的节点队列管理机制将能够直接提高存储空间利用率，进而改善网络性能。

节点活动能力越强，则该节点与其他节点相遇的机会将随之增加，进而传递和存储的消息也就越多。网络中的消息被此种类型的节点存储后，其成功投递的机会显著增加。由此易知，节点的活跃程度直接反映了其所携带消息的成功投递概率。机会网络中，节点相遇之后需要交换彼此队列中的存储状态，经过多个活跃节点携带的消息成功投递率较高，可见，过多地对其进行存储以及转发将严重浪费网络资源，也就是说，此种消息的重要程度会下降。因此，应充分考虑节点活跃程度之间的差异，以有效地管理节点队列中的消息，达到合理利用网络资源的目的。

目前，针对机会网络的队列管理方法均没有考虑节点的活跃程度，也没有将节点的活跃程度反映到消息上，可见，这些机制存在一定程度的局限性。

发明内容

本发明所要解决的技术问题是：针对机会网络中节点队列空间有限，且现有队列管理调度方法中无法高效利用存储空间的局限性，本发明设计了一种基于消息传输状态的机会网络自适应队列调度方法，节点根据与其他节点相遇情况确定各个节点之间的活跃程度差异，并根据消息转发过程中，其携带节点的活跃程度估计当前传输状态，进而，确定节点相遇之后的队列操作。所设计的消息传输状态评估方法比较准确，同时，此种自适应队列管理方法能有效提高消息成功投递率，降低网络平均时延和网络负载率。

本发明解决其技术问题所采用的技术方案是：本发明将节点间的相遇次数作为衡量节点活跃程度的关键参数，估计网络中节点相遇的总次数和各个节点相遇次数的中间值，利用节点本地保存的与其他节点相遇的历史信息，根据本节点相遇次数与各个节点相遇次数中间值之间的差值，运用均匀量化法，衡量各个节点的活跃程度差异。显然，节点活跃程度越高，则通过其将消息成功投递的概率越高，因此，消息被越多活跃节点存储、携带并转发，则表明其已经成功投递的概率越高。消息在传输过程中需要经过多个节点转发，本发明以保存过给定消息的所有节点的活跃程度为依据，估计消息已成功投递的概率，已成功投递的概率较高的消息重要程度也就随之降低，其继续在网络中存活的意义就下降。按照该原则，本发明设计了一种基于消息传输状态的自适应队列管理方法，此队列管理方法主要包括出队列操作和入队列操作两个方面，节点队列内部的消息按照当前网络状态下的重要程度排序。出队列操作中，节点相遇之后首先交换重要程度最高的消息，入队列操作中，当队列占满之后，节点需要将需要进入本地队列消息的重要程度与队列内部消息重要程度比较，使用有限的存储资源携带重要程度最高的消息。

本发明提出的消息重要程度感知的机会网络队列管理方法充分地利用节点之间随机移动的历史信息，近似地确定其与其他节点之间的活跃程度差异，并利用消息在转发过程中携带节点的活跃程度判定传输状态，进而，以消息重要程度为参数调整节点队列使用情况。与现有队列管理方法相比，本专利提出的方法能够充分地考虑节点之间活跃程度以及消息重要程度的差异，利用节点有限的存储资源，有效提高消息成功投递率，降低网络平均时延和网络负载率，提高网络性能。

附图说明

图1消息在队列中的排队方式

图2消息的接收流程图。

具体实施方式

本发明将节点间的相遇次数作为衡量节点活跃程度的关键参数，估计网络中节点相遇的总次数和各个节点相遇次数的中间值，利用节点本地保存的与其他节点相遇的历史信息，根据本节点相遇次数与各个节点相遇次数中间值之间的差值，运用均匀量化法，衡量各个节点的活跃程度差异。显然，节点活跃程度越高，则通过其将消息成功投递的概率越高，因此，消息被越多活跃节点存储、携带并转发，则表明其已经成功投递的概率越高。消息在传输过程中需要经过多个节点转发，本发明以保存过给定消息的所有节点的活跃程度为依据，估计消息已成功投递的概率，已成功投递的概率较高的消息重要程度也就随之降低，其继续在网络中存活的意义就下降。按照该原则，本发明设计了一种基于消息传输状态的自适应队列管理方法，此队列管理方法主要包括出队列操作和入队列操作两个方面，节点队列内部的消息按照当前网络状态下的重要程度排序。出队列操作中，节点相遇之后首先交换重要程度最高的消息，入队列操作中，当队列占满之后，节点需要将需要进入本地队列消息的重要程度与队列内部消息重要程度比较，使用有限的存储资源携带重要程度最高的消息。

估计节点活跃程度

计算网络中节点相遇的总次数和各个节点相遇次数的中间值，运用均匀量化法，衡量各个节点的活跃程度差异。

本发明将节点间的相遇次数作为估计节点活跃程度的关键参数。变量定义如下：给定节点与网络中其他节点的相遇次数称为该节点的相遇次数M，其大小在[M_min, M_max]内。各个节点进入其他节点通信范围的总次数定义为节点相遇总次数M_total，各个节点进入其他节点通信范围的平均次数定义为节点平均相遇次数M_avr。节点相遇间隔NM（Node Meeting Interval）表示从节点i离开某一节点的通信范围到节点i再次进入任一节点通信范围的时间间隔，节点首次相遇时间NFM（Node First Meeting Time）表示两个节点从静止开始到第一次相遇（各自进入通信范围）经过的时间。

对于广泛应用的Random Way Point移动模型来说，调用公式(1)确定NFM：

         (1)

其中RWP模型的节点运动相对速度可选择，L为节点到目标节点的距离，为L的预计平均值，在一个大小的RWP网络模型中可取，为平均停留时间，为节点的平均速度，K为节点传输范围。，表示节点在单位时间内处于运动状态的时间。

机会网络中的节点采用存储-携带-转发的方式进行通信，同一个消息可能在网络中存在多个备份。若当前网络中某个消息有L个备份，且消息的路由方式为直接投递，即节点只有遇到目标节点才转发消息。调用公式           (2)   确定消息成功传递到目的节点的延迟ED（Expected Delay）。

网络中有n个节点，若当n个节点组成的网络中有n-1个备份，则此消息到目的节点的延迟即为节点访问间隔NM，如式（3）所示：

         (3)

可见，T时间段内，节点访问间隔NM与时间的比值即为某个节点与其他节点相遇的平均次数，那么所有节点之间总相遇次数如式（4）所示：

         (4)

根据公式（5）获得节点在T时间段内与其他节点的平均相遇次数：

            (5)

令节点活跃程度的权值为X，其大小在[X_min, X_max]范围内，若令当前网络状态下，将节点平均相遇次数确定为中等活跃程度的节点相遇次数，根据公式5确定中等活跃程度的节点相遇次数为M_med，可根据M_med和给定节点的节点之间总相遇次数，获知节点活跃程度之间的差异，进而计算权重数值。可见，M_med数值的准确程度与节点活跃程度估计方法的有效性直接相关。机会网络以分布方式运行，节点无法获取整个网络范围内其他节点的状态信息，本发明采用M_avr的估计数值作为M_med的近似数值，即。

显然，若给定节点的相遇次数等于M_avr，那么此节点的权值X也是[X_min, X_max]的中间值X_med。如果某个节点的相遇次数比M_med大，那么其权值需要相应地增加，反之降低。为了更合理有效地反映相遇状态差异与权重差值之间的映射关系，如本发明可根据网络规模的大小选取X的范围[X_min, X_max]为[0, 10]，针对节点活跃程度的均匀量化计算方法如式（6）所示： 

                  (6)

其中为量化间隔，。

估计消息重要程度

消息在多次转发过程中记录携带节点活跃程度，在T时刻，存储给定消息的所有节点活跃程度权值总和A(T)：

                      (7)

网络实际运行过程中，消息被节点存储的状态动态改变，即，显然，若给定消息的A(T)为最大权值A_max，则表明此消息已成功投递。由此，可得消息已成功投递的概率P(T)，如式（8）所示：

                        (8)

其中，A(T)可由节点本地记录信息得到。

节点相遇之后比较彼此的活跃程度权值A，网络运行稳定之后，各个节点均可获得当前网络中的A_max。

利用给定消息的所有节点活跃程度权值总和A(T)为每个消息设计相应的权重，此权重反映消息在网络中继续转发的重要程度，该重要程度可表示为：

                 (9)

携带给定消息的活跃节点数量越多，其A(T)越大，表明已被成功投递的概率也随之上升，继续携带此消息的意义也相应地下降，其在网络中的重要程度也就降低，反映到（9）式就是A(T)越大，Q(T)越小。

如式（9）中所示，节点可以根据当前网络状态动态地估计A(T)和A_max数值，因此，对于网络状态时变性较强的机会网络来说，权重Q(T)能够自适应地反映消息在网络中的重要程度，根据重要程度设计队列管理策略。

基于消息传输状态的机会网络自适应队列管理方法

基于消息重要程度设计机会网络自适应队列管理策略，包括出队列操作和入队列操作两个方面。

出队列操作主要解决队列内部消息优先级问题。机会网络中两个节点相遇之后，需要彼此交换队列状态以及队列中所保存的消息。根据消息重要程度，节点将其在队列中按照权重由大到小进行排列。如附图1所示，所有消息按照其权重排列，权值最大者Message₁位于队列头部，权重最小者Message_n位于队列尾部。当节点相遇并传输消息时，队头消息获得优先发送权。

入队列操作主要解决数据携带决策问题。每个消息记录所有携带节点的活跃程度，通过各个节点的活跃程度总和，估计给定网络状态下，消息已经成功投递的概率，进而衡量其重要程度。以消息的重要程度为依据，将队列中的消息进行排列，节点在信息交换过程中，重要程度最高的消息优先发送。当消息进入队列时，判断队列中是否有足够空闲空间，若有，则接收此消息，否则，从权重最小的消息开始删除消息，为消息留出足够的空间，当队列中有足够的空间，则接收此消息，否则拒绝消息。当队列空间已经全部占用，而节点之间相遇之后需要相互交换信息，此时，将衡量需要交换的消息的重要程度，删除队列中重要程度较小的消息，直至为新消息预留出足够空间。

如图2所示，其中S表示节点的空闲存储空间，S_i表示消息i的大小，Q_i(T)表示当前网络状态下消息i的权重。当消息i要进入队列时，先判断队列中是否有足够空闲空间，若有，则接收此消息，否则，比较消息权重关系，从权重最小的消息开始执行删除操作，若删除队列中权重最小且比消息i权重小的消息后，队列中有足够的空间，则接收此消息，否则继续删除队列中权重次小且比消息i权重小的消息，直到为消息i留出足够的队列空间。若删除了所有权重比消息i权重小的消息后，还是无法留出足够空间，则拒绝此消息i。