一种基于日常习惯分析的节点搜寻方法

摘要

本发明提供的一种基于日常习惯分析的节点搜寻方法，其特征在于，包括以下步骤：将网络分为多个分区，每个分区设置有一个地标设备；分析节点的日常习惯，以获得包含节点的原始停留概率表的原始转移概率表；将原始停留概率表和原始转移概率表精简为简化停留概率表和简化转移概率表；将原始停留概率表和原始专利概率表分配给第一地标设备保存，并将简化停留概率表和简化转移概率表发送给第二地标设备保存；判断源节点所在的当前分区的源地标设备是否保存有目的节点的原始停留概率表和原始转移概率表，当判断为是时，源地标设备采用跟踪机制来寻找目的节点，当判断为否时，源地标设备采用机会路由机制来寻找目的节点。

说明书

技术领域

本发明涉及容迟网络系统，尤其涉及一种基于日常习惯分析的节点搜寻方法属于通信网络技术领域。

背景技术

在容迟网络中，现有的节点搜寻和数据通信方法一般分为三类：(1)基于概率的路由，该类路由一般选择具有更高概率遇见目的节点的节点作为中继节点，却忽视了一些节点虽然遇到目的节点的概率不高但是具有很高将数据带到更加靠近目的节点的能力；(2)基于社会关系的路由，该类路由通过朋友关系和相遇信息来搜寻目的节点，然而一个节点所能遇到的节点和朋友数量毕竟是有限的；(3)基于地理位置的路由，该类路由记录节点的历史移动信息来描述节点的移动模式。

然而在实际的网络通信中，由于节点的移动信息数据量庞大，上述的三种方法都无法适应实际网络的移动信息数据量大的特点，无法满足既能节省存储空间又能提高追踪效率的容迟网络通信要求。

发明内容

本发明是为了解决上述问题而进行的，目的在于提供一种基于日常习惯分析的节点搜寻方法，该搜寻方法给出了一种根据节点日常习惯分析来对节点移动模式进行准确描述的新方法，该方法在降低存储空间的前提下，提高了节点搜寻的效率，从而增加了数据传输的投递率并且降低了数据传输时延。

一种基于日常习惯分析的节点搜寻方法，从源节点所在的具有多个节点的网络中搜寻目的节点，其特征在于，包括以下步骤：

步骤一，根据节点的访问热点将网络分为多个分区，每个分区分别设置有一个地标设备和至少一个访问热点，源节点的地标设备为源地标设备；

步骤二，根据节点的日常活动习惯分析获得包含节点在不同时段、不同分区的停留概率的原始停留概率表和包含节点在不同分区之间相互转移的转移概率和转移路线的原始转移概率表；

步骤三，将步骤二中原始停留概率表和诉讼原始转移概率表精简为简化停留概率表和简化转移概率表，简化停留概率表包含原始停留概率表中停留概率高于预设值的停留信息而简化转移概率表包含简化停留概率表中包含的分区之间相互转移的转移概率信息；

步骤四，将原始停留概率表和原始转移概率表分配给第一个分区的第一地标设备保存，并将简化停留概率表和简化转移概率表发送给第二个分区的第二地标设备保存，第一地标设备位于简化停留概率表所包含的分区中，第二地标设备位于简化停留概率表所包含的分区之外；

步骤五，判断源节点所在的当前分区的源地标设备是否保存有目的节点的原始停留概率表和原始转移概率表，当判断为是时，源地标设备采用跟踪机制来寻找目的节点，当判断为否时，源地标设备采用机会路由机制来寻找目的节点。

本发明提出的的基于日常习惯分析的节点搜寻方法，还可以具有这样的特征，其特征在于：其中，原始停留概率表包括短期停留概率和长期停留概率，短期停留概率是一个节点在特定时段在某个分区内停留的概率，长期停留概率为节点从网络启动开始到当前时段在某个分区的停留概率。

本发明提出的的基于日常习惯分析的节点搜寻方法，还可以具有这样的特征，其特征在于：其中，简化停留概率表包含原始停留概率表中短期停留概率为0.8-1.0以及长期停留概率为0.08-1.0的停留信息。

本发明提出的的基于日常习惯分析的节点搜寻方法，还可以具有这样的特征，其特征在于：其中，步骤五中跟踪机制包括以下步骤：源地标设备根据节点的访问记录判断目的节点是否仍在当前分区，当判断为是时，则通过向目的节点靠近的节点与该目的节点直接通信来完成搜寻工作，否则进入下一步；根据目的节点的原始停留概率表和原始转移概率表查找目的节点在访问记录中的下一个时段的可能转移路径，并通过这些可能转移路径来追踪目的节点。

本发明提出的的基于日常习惯分析的节点搜寻方法，还可以具有这样的特征，其特征在于：其中，步骤五中机会路由机制包括以下步骤：

步骤S5-1，源地标设备根据目的节点的简化停留概率表和简化转移概率表确定一个目的节点在当前时段最可能停留的分区作为目标分区；

步骤S5-2，源地标设备根据自己所保存的停留概率表和转移概率表计算出当前时段各个分区间的节点流量，并根据各个分区之间的距离和节点流量计算出从当前分区到目的节点所在的目标分区的多条最优路径；

步骤S5-3，源地标设备根据节点的传输能力选择多个中继节点将源节点的数据携带至目标分区，传输能力与节点转移到多条最优路径上的概率相关；

步骤S5-4，当中继节点转移到最优路径上的一个分区后，该分区的地标设备运行步骤五，直至完成对目的节点的搜寻工作。

本发明提出的的基于日常习惯分析的节点搜寻方法，还可以具有这样的特征，其特征在于：其中，步骤S5-2中根据各个分区之间的距离和节点流量根据Dijistra算法计算出从当前分区到目的节点所在的目标分区的多条最优路径。

本发明提出的的基于日常习惯分析的节点搜寻方法，还可以具有这样的特征，其特征在于：其中，步骤四中将简化停留概率表和简化转移概率表发送给第二地标设备保存的方法包括：第一地标设备为节点选择与该节点移动习惯不同的节点，并将该节点的简化停留概率表和简化转移概率表发送给第二地标设备。

发明作用和效果

根据本发明所涉及一种基于日常习惯分析的节点搜寻方法，由于该方法通过分析节点的日常习惯来获取节点的原始停留概率表和原始转移概率表，这样实现了对节点的移动模式的准确描述；又由于该方法将原始停留概率表和原始转移概率表进行简化，形成简化停留概率表和简化转移概率表，并将原始信息和简化信息存储在不同的地标设备中，这样做减少存储开销，也方便了采用不同的节点搜寻机制进行目的节点的搜寻。

另一方面，由于源节点所在当前分区的源地标设备根据是否保存有目的节点的原始停留概率表和原始转移概率表的两种情况来进行区分，如果保存有则源地标设备采用跟踪机制来寻找目的节点，否则该源地标设备采用机会路由机制来寻找目的节点，根据不同情况采用不同的机制来进行搜寻跟踪，可以实现在降低存储空间的前提下提高节点搜寻效率。

附图说明

图1为本发明实施例中的基于日常习惯分析的节点搜寻方法的流程图；

图2为本发明实施例中的原始停留概率表示意图；

图3为本发明实施例中的原始转移概率表示意图；

图4为本发明实施例中的节点跟踪机制示意图；以及

图5为本发明实施例中的机会路由机制示意图。

具体实施方式

以下参照附图及实施例对本发明所涉及的一种基于日常习惯分析的节点搜寻方法作详细的描述。

实施例

图1为本发明实施例中的一种基于日常习惯分析的节点搜寻方法的流程图。

如图1所示，一种基于日常习惯分析的节点搜寻方法具有以下步骤：

步骤S1，根据节点的访问热点将网络分为多个分区，每个分区分别设置有一个地标设备和至少一个访问热点，源节点的地标设备为源地标设备。

图2为本实施例中的原始停留概率表示意图。

图3为本实施例中的原始转移概率表示意图。

步骤S2，根据节点的日常活动习惯分析获得包含节点在不同时段、不同分区的停留概率的原始停留概率表和包含节点在不同分区之间相互转移的转移概率和转移路线的原始转移概率表。

如图2所示，原始停留概率表包括短期停留概率和长期停留概率，短期停留概率是一个节点在特定时段在某分区内停留的概率，例如节点N_i在时段在分区A_m停留的平均时长为那么N_i在时段在分区的短期停留概率为计算公式为长期停留概率为节点从系统启动开始到当前时段在某分区的停留概率，节点N_i在时段在分区A_m的长期停留概率为其计算公式为：

如图3所示，原始转移概率表中包含节点的转移概率和转移路径，其中转移概率与节点在两个相邻时段的短期停留概率相关，例如节点N_i从分区A_m转移到A_h的转移概率为它等于N_i在时段在A_m的短期停留概率与N_i在时段在A_h的短期停留概率的乘积：

步骤S3，将步骤S2中原始停留概率表和诉讼原始转移概率表精简为简化停留概率表和简化转移概率表，简化停留概率表包含原始停留概率表中停留概率高于预设值的停留信息而简化转移概率表包含简化停留概率表中包含的分区之间相互转移的转移概率信息。本实施例中，简化停留概率表包含原始停留概率表中短期停留概率为0.8-1.0以及长期停留概率为0.08-1.0的停留信息。

步骤S4，将原始停留概率表和原始转移概率表分配给第一个分区的第一地标设备保存，并将简化停留概率表和简化转移概率表发送给第二个分区的第二地标设备保存，第一地标设备位于简化停留概率表所包含的分区中，第二地标设备位于简化停留概率表所包含的分区之外。将简化停留概率表和简化转移概率表发送给第二地标设备保存的方法包括：第一地标设备为节点选择与该节点移动习惯不同的节点，并将该节点的简化停留概率表和简化转移概率表发送给第二地标设备。为了说明上述的节点移动习惯，这里提出两种非相似度来评价节点之间移动习惯的差异程度。例如，对于节点N_i和N_j，分区集S_j包含N_j的简化停留概率表中的所有分区,和分别表示拥有和没有N_i的原始停留概率表的分区集，和M(S_j)分别表示和这两个分区集中分区的数量。表示和S_j的交集分区个数，那么关于N_i和N_j的两个非相似度分别为和他们的计算公式分别为：和

步骤S5，判断源节点所在的当前分区的源地标设备是否保存有目的节点的原始停留概率表和原始转移概率表，当判断为是时，源地标设备采用跟踪机制来寻找目的节点，当判断为否时，源地标设备采用机会路由机制来寻找目的节点。

跟踪机制包括以下步骤：

首先，源地标设备根据节点的访问记录判断目的节点是否仍在当前分区，当判断为是时，则通过向目的节点靠近的节点与该目的节点直接通信来完成搜寻工作，否则进入下一步。

然后，根据目的节点的原始停留概率表和原始转移概率表查找目的节点在访问记录中的下一个时段的可能转移路径，并通过这些可能转移路径来追踪目的节点。

图4为本实施例中的节点跟踪机制示意图。

下面结合图4来举例说明跟踪机制的运行过程。

如图4所示，节点N₄的当前分区为A₅，它想发送数据到节点N₅，于是它发送了一个数据发送请求给A₅的地标设备，A₅的地标设备在接到请求后，查询N₅的访问记录，发现N₅已经离开，但该地标设备拥有N₅的原始停留概率表和转移概率表，通过分析这两个表发现N₅在离开A₅以后有三条可能的转移路径，分别为A₅→A₆→A₇→A₈，A₅→A₁₀→A₁₁和A₅→A₉→A₁₃，于是A₅的地标把数据发送给接下来去往A₆,A₉和A₁₀的节点。如果A₁₀的地标设备拥有更新的N₅的访问记录，那么A₁₀的地标设备将继续追踪N₅，A₆和A₉没有更新的N₅的访问记录，则停止追踪。

机会路由机制包括以下步骤：

步骤S5-1，源地标设备根据目的节点的简化停留概率表和简化转移概率表确定一个目的节点在当前时段最可能停留的分区作为目标分区。

步骤S5-2，源地标设备根据自己所保存的停留概率表和转移概率表计算出当前时段各个分区间的节点流量，并根据各个分区之间的距离和节点流量计算出从当前分区到目的节点所在的目标分区的多条最优路径。根据各个分区之间的距离和节点流量根据Dijistra算法计算出从当前分区到目的节点所在的目标分区的多条最优路径。在步骤S5-2中，根据节点的转移概率来计算分区之间的节点流量，如果用F_n(A_m→A_h)来表示A_m去到A_h的节点流量，其计算公式为

步骤S5-3，源地标设备根据节点的传输能力选择多个中继节点将源节点的数据携带至目标分区，传输能力与节点转移到多条最优路径上的概率相关。在选择最优路径时，我们定义了一个衡量分区间的传输能力的指标，它与分区间的节点流量和分区间的距离相关，例如A_m和到A_h之间的传输能力指标为SD_n(A_m→A_h)，其计算公式为根据节点的短期停留概率来判断节点的传输能力，例如，S_Hi表示节点N_i在时段将要去向的分区集合，S_FS表示最优路径上的分区结合，那么N_i的传输能力为ND_ni，其计算公式为：

步骤S5-4，当中继节点转移到最优路径上的一个分区后，该分区的地标设备运行步骤五，直至完成对目的节点的搜寻工作。

图5为本实施例中的机会路由机制示意图。

下面结合图5来举例说明机会路由机制的运行过程。

如图5所示，节点N₆的当前分区为A₁，想发送数据到N₇，N₆发送数据发送请求给A₁的地标设备。由于A₁的地标设备只有N₇的简化停留概率表和简化转移概率表，通过分析这两个表发现N₇在当前时段最优可能停留在A₁₆，所以A₁的地标设备选择A₁₆作为目标分区，然后执行机会路由机制。根据机会路由机制在A₁和A₁₆之间发现三条最优路径，分别为，A₁→A₆→A₁₁→A₁₆，A₁→A₆→A₇→A₁₁→A₁₆和A₁→A₅→A₁₀→A₁₅→A₁₆，然后选择A₁中在当前时段最有可能转移到这三条最优路径上的节点为中继节点。

实施例的作用与效果

根据本实施例所涉及一种基于日常习惯分析的节点搜寻方法，由于该方法通过分析节点的日常习惯来获取节点的原始停留概率表和原始转移概率表，这样实现了对节点的移动模式的准确描述；又由于该方法将原始停留概率表和原始转移概率表进行简化，形成简化停留概率表和简化转移概率表，并将原始信息和简化信息存储在不同的地标设备中，这样做减少存储开销，也方便了采用不同的节点搜寻机制进行目的节点的搜寻。

另一方面，由于源节点所在当前分区的源地标设备根据是否保存有目的节点的原始停留概率表和原始转移概率表的两种情况来进行区分，如果保存有则源地标设备采用跟踪机制来寻找目的节点，否则该源地标设备采用机会路由机制来寻找目的节点，根据不同情况采用不同的机制来进行搜寻跟踪，可以实现在降低存储空间的前提下提高节点搜寻效率。