基于社会属性转发的容迟网络节能路由方案

摘要

本发明涉及一种基于社会属性转发的容迟网络节能路由方案，当对报文从源节点到目的节点传递时按照以下原则进行路由：首先，网络中报文的转发均采用单副本的方式；其次，对每一个新生成的报文建立一个生存周期TTL字段，其初始值为一个预设的自然数n，该报文每被转发一次TTL值就会减1，当TTL值减小到0的时候就丢弃该报文；最后，携带报文的节点当且仅当遇到比自己的社交指标SM值大amp_ratio倍的节点时才将报文转发给该节点，此外通过动态改变amp_ratio可自适应地调节携带报文节点的报文转发条件。本发明方案的实施有效降低了网络中报文的转发次数，在保证较高传递成功率前提下有效降低了容迟网络的路由能耗。

说明书

技术领域

本发明涉及容迟网络的路由方法，特别涉及一种基于社会属性转发的容迟 网络节能路由方法，属于计算机网络技术领域。

背景技术

时延容忍网络(Delay/Disruption Tolerant Networks，DTN)又称容迟网络， 它是基于存储-携带-转发的一种新型网络。它是指在一些特殊的网络环境之下 (如无线传感器网络、车辆Ad-hoc网络、星际网络)，经常出现的网络中断等 现象使得网络中端到端的连接间歇性发生变化，导致报文在端到端的传输中可 能经过很长时延。DTN可以应用于很多领域当中，比如星际网络、海底网络、 军事战略网络、车辆Ad-hoc网络、无线传感器网络以及其它一些连接受限的网 络环境中。时延容忍网络的研究和发展将对星际通信、空间探测、灾难应对、 军事战争等很多领域提供强有力的科学理论支持，它是当前国际上计算机领域 内备受关注的新兴前沿研究热点之一，其具有广阔的研究前景和应用发展前途。

传统因特网中的每台设备都有互联网服务提供商(ISP)为其提供互联网接 入服务，成功接入互联网的两台设备必然经过Internet中的若干跳路由相互连通， TCP/IP路由协议就是基于这样的假设在两台主机需要通信时为其寻找时延最小 或者跳数最少的路径。但是时延容忍网络独有的一些特性使得为传统因特网设 计的TCP/IP协议不能直接适用，这些特点包括以下几点：

1、间歇性连接：由于节点移动导致节点间的连接状态改变、节点为节约能 源暂时关闭电源等众多因素，造成容迟网络中端到端路径的间歇性连接。

2、节点资源有限：容迟网络常常分布于战场、海底、深空等恶劣环境中， 并且受节点重量、体积和成本等因素的限制，节点所携带的电能十分有限，通 常节点消耗完自身有限的电能之后将无法继续工作。

3、较长的网络延时：由于容迟网络中广泛存在的网络中断和节点间的不稳 定连接等因素导致报文在源节点到目的节点的发送过程中通常会经过较长的网 络时延。

4、低信噪比(高误码率)：容迟网络中，恶劣环境所导致的低信噪比使得 节点间信号传递的高误码率。

5、不对称数据速率。

为了在这种新型网络下取得较高的报文转发成功率，容迟网络路由策略的 设计尤为关键。基于时延容忍网络的上述独有特性，特别是端到端的间歇性连 接和较长网络延时，很多传统的路由协议在这种网络环境下不能直接适用，必 须根据容迟网络的特点为其设计专用的路由协议。近些年来，随着时延容忍网 络概念的提出及其广泛的应用领域，许多针对这种网络的路由策略被提出，这 些路由方法主要有以下几种：

(1)Epidemic路由方法。Epidemic路由方法是由Vahdat和Becker于2000 年在文献《Epidemic routing for partially connected ad hoc networks》中提出的， Epidemic路由方法主要解决了间歇性连接网络下的路由问题。它的基本思想是 当携带报文的节点遇到另外一个未携带该报文的节点时，就将自己的报文复制 并转发给这个节点。Epidemic路由算法采取洪泛式策略，模拟传染性病毒的传 播方式，将报文复制并转发给中途所遇到的所有节点，从而最大化消息转发的 成功率。但是随着整个容迟网络中报文数的增加，节点的缓存空间可能会被这 些报文的副本占满，从而导致节点在之后转发过程中出现丢包的情况。另外， 由于采取洪泛式的路由策略，网络中每个节点的能量消耗都会很大。

(2)Spray and wait路由方法。为了克服Epidemic路由方法的一些弊端， Spyropoulos等人于2005年在文献《Spray and wait:an efficient routing scheme for  intermittently connected mobile networks》中提出了Spray and wait路由算法来解 决间歇性连接网络环境下的路由问题。它通过限制网络中报文的最大副本数来 减小报文洪泛式转发时网络中节点的缓存占用。即便如此，洪泛式转发策略导 致网络中节点能耗过大这一问题仍没有被解决。

(3)基于预测的路由方法。这类路由方法通常在携带报文的节点遇到另外 一个节点时，通过历史相遇信息预测未来报文被成功转发给目的节点的可能性， 从而做出决定是否将报文转发给相遇的节点。Dubois-Ferriere等人在文献《Age  matters:efficient route discovery in mobile ad hoc networks using encounter ages》中 提出根据在移动ad hoc网络中某一节点与目的节点最近一次相遇的时间来预测 报文通过该节点传递到目的节点的可能性，并以此选择下一跳节点的Fresh路由 方法。Erramilli等人在文献《Diversity of forwarding paths in pocket switched  networks》中提出了Greedy-Total路由方法，它根据网络中某一节点与其它所有 节点的相遇频率来预测报文通过该节点传递到目的节点的可能性并做出下一跳 选择。

(4)基于社会属性转发的路由方法。随着容迟网络中越来越多的移动通信 设备被人类所携带，其行为可以很好地被其社会属性所刻画。基于社会属性转 发的路由方法就是根据节点本身的社会属性或与其它节点的社交关系来判断节 点将报文成功转发给目的节点的可能性。Daly和Haahr于2007年在文献《Social  network analysis for routing in disconnected delay-tolerant manets》中提出SimBet 路由算法。它规定当携带报文的节点遇到其它节点时，通过比较这两个节点的 核心度(betweenness centrality)以及其与目的节点的相似度(similarity)来决定 是否把报文交给遇到的节点进行转发。Hui等人在文献《How small labels create  big improvements》中提出Label路由算法，它根据节点的社会属性把其分为若 干个社区，在报文转发时首先考虑将报文转发到一个与目的节点处于相同社区 的节点。

现有的针对容迟网络的路由协议大多重点关注尽可能提高报文转发的成功 率，很少关注容迟网络中节点的能量消耗问题。然而在容迟网络中节点的能量 是十分宝贵的，一旦节点用尽自己的能量并且在没有外界为其补充能量的情况 下，它就不会继续工作，从而对整个容迟网络的路由性能造成很大影响。本发 明重点关注如何在保证报文传递成功率较高的前提下降低容迟网络中节点的能 量消耗。

发明内容

本发明针对容迟网络的特点和现有路由方法在控制节点能耗方面的不足， 提出了一种基于社会属性转发的节能路由方法EESRA(Energy Efficient  Social-based Routing Algorithm)。

本发明内容是通过以下方案实现的：

一种基于社会属性转发的容迟网络节能路由方案，包括以下步骤：

步骤1、根据节点相遇的历史信息建立社会关系图；

步骤2、根据建立好的社会关系图，计算必要的节点自身的社会属性和节点 之间的社交关系；

步骤3、对新生成的报文进行路由选择；

其特征在于，对新生成的报文从源节点到目的节点传递按照以下原则路由：

原则1：网络中报文的转发均采用单副本的方式；

原则2：对每一个新生成的报文建立一个生存周期TTL字段，其初始值为 一个预设的自然数n，该报文每被转发一次TTL字段就会减1，当TTL值减小 到0的时候节点就将该报文丢弃；

原则3：携带报文的节点当且仅当遇到比自己的社交指标SM值大amp_ratio 倍的节点时才将报文转发给该节点。

较优的，SM值的计算可以选取任何一种已有社会属性，如SimBet、social  energy，也可以是新定义的能够反应节点之间社交关系的新的度量指标。

较优的，amp_ratio值应随着TTL的减小而减小。

较优的，对每一个新生成或刚被转发的报文建立一个计数器node_counter 字段，其初始值为0，当携带报文节点每遇到一个SM值比自己大的节点但仍未 能将报文转发出去时，其值就增加1；当node_counter值大于阈值k时，就逐渐 降低amp_ratio的值来放松当前节点对于报文转发条件的限制。

一种基于社会属性转发的容迟网络节能路由方法，其特征在于，对于新生 成的报文从源节点到目的节点路由时，按以下步骤执行：

步骤1、节点v_i携带准备发往目的节点v_d的报文Msg，在某个时刻它遇到 了节点v_j并且该节点没有携带Msg；

步骤2、如果节点v_j是目的节点v_d，节点v_i将Msg转发给节点v_j，方法结 束；否则，转到步骤3；

步骤3、如果节点v_i的SM值SM(v_i)小于节点v_j的SM值SM(v_j)，转到步骤 4；否则，节点v_i继续携带Msg等待与其它节点相遇，当遇到其它节点时再从步 骤1开始进行路由选择；

步骤4、如果Msg的node_counter值大于阈值k，转到步骤5；否则，转到 步骤6；

步骤5、计算$\mathrm{amp}\_\mathrm{ratio}=1+\frac{\mathrm{ttl}}{{\mathrm{TTL}}_0}\times \theta \times \frac{1}{\mathrm{node}\_\mathrm{counter}-k+1},$转到步骤7；

步骤6、计算$\mathrm{amp}\_\mathrm{ratio}=1+\frac{\mathrm{ttl}}{{\mathrm{TTL}}_0}\times \theta ;$

步骤7、如果SM(v_j)大于SM(v_i)的amp_ratio倍，转到步骤8；否则，转到步 骤9；

步骤8、节点v_i将Msg转发给节点v_j，并且Msg的TTL字段值减1， node_counter字段值重置为0；如果Msg的TTL值为0，丢弃该报文，方法结束； 否则vj携带报文Msg等待与其它节点相遇，当遇到其它节点时再从步骤1开始 进行路由选择；

步骤9、Msg的node_counter字段的值自增1，节点vi继续携带Msg等待与 其它节点相遇，当遇到其它节点时再从步骤1开始进行路由选择。

有益效果

本发明所提出的基于社会属性转发的节能路由方法，通过利用容迟网络中 节点的社会属性进行路由选择，并且通过单副本、限制报文转发跳数、以及一 个动态的放大倍数以更好地选择下一跳节点，从而降低网络中报文的转发次数， 使得网络中的节点的平均能耗减少。

附图说明

图1为基于社会属性转发的容迟网络节能路由方法

(EESRA)的流程图。

图2～图7为EESRA容迟网络节能路由方法与其它四种容迟网络路由方法 的性能比较图。

具体实施方式

下面结合理论及附图具体说明本发明方法的内容。

在许多容迟网络的应用中，越来越多的移动通信设备由人携带和使用，其 行为可以很好地被其社会属性所刻画。本发明所提出的基于社会属性转发的节 能路由方法就是根据容迟网络中节点自身的社会属性和节点间的社交关系来选 择中继节点进行消息转发的方法。

传统基于社会属性的路由方法都是通过节点的本身的社会属性以及节点间 的社交关系计算得到节点的社交指标SM(Social Metric)，这里的社交指标既可 以是SimBet路由方法中的SimBet值，也可以是SEBAR路由方法中的social  energy等，它取决于具体的基于社会属性转发的路由方法。当携带报文的节点 与未携带该报文的节点相遇时，通过判断社交指标SM值的大小来决定是否将报 文转发给相遇的节点。本发明提出的基于社会属性转发的节能路由方法通过限 制容迟网络中报文的转发次数达到降低网络中节点能耗的目的。它通过三种措 施来限制网络中报文的转发次数。

第一，网络中报文的转发均采用单副本的方式。

第二，每一个新生成的报文都会有一个TTL(Time to Live)字段，其初始 值为一个预设的自然数n，它每被转发一次TTL字段就会减1，当TTL值减小 到0的时候节点就将该报文丢弃。

第三，规定只有携带该报文的节点遇到比自己SM值大amp_ratio倍 (amp_ratio≥0)的节点时才将报文转发给该节点。

并且当该报文的TTL字段比较大的情况下，我们希望amp_ratio的值足够大， 以此来减小报文转发到目的节点过程中可能经历的跳数；报文每被转发一次即 随着报文TTL字段的减小，携带该报文的节点遇到一个比自己SM值大很多的 节点的可能性就会变得越低，因此我们希望随着TTL字段的减小amp_ratio也能 随之减小，以此避免报文在节点中长时间等待而浪费节点的缓存。

本发明提出的EESRA容迟网络路由方法，包括以下步骤：

一、根据节点相遇的历史信息建立社会关系图(Social Graph)。

1)统计历史信息。假设整个时延容忍网络中有n个节点，节点的集合用 V＝{v₀,v₁,...,v_n-1}来表示，当网络中两个节点之间的距离小于某个值时它们就可 以相互发送和接收数据。我们统计某段时间内网络中每两个节点之间的相遇次 数将其保存在矩阵contactMatrix中。

2)建立容迟网络中节点的社会关系图。社会关系图是用来描述网络中节点 的社交关系的，图中的每个节点代表网络中的一个网络节点，图中的两个节点 之间若有边相连，则表示这两个节点有较为亲密的社会关系。社会关系图有很 多种建立方法，其中最简单的一种构造方法是根据节点在某段时间内的相遇次 数来建立，具体步骤是首先根据历史相遇信息得到节点相遇矩阵contactMatrix， 起初图中只有n个孤立节点，对于矩阵contactMatrix中每一个大于阈值t的 contactMatrix[i][j]，将节点v_i和节点v_j用一条边连接，其中t是一个事先确定好 的阈值。

二、根据建立好的社会关系图，计算必要的节点自身的社会属性和节点之 间的社交关系。

1)计算节点自身的社会属性。节点自身的社会属性是指该节点所独有的， 不依赖于其它节点的社会属性。比如节点的度指的是社会关系图中该节点邻居 的个数，节点的betweenness社会属性是指网络中的每个节点对的最短路由经过 该节点的次数。

2)计算节点之间的社交关系。节点之间的社交关系是两个节点所共有的一 种社交关系。比如节点v_i和节点v_j之间的相似度指的是社会关系图中这两个节 点的相同邻居的个数。

三、采用EESRA路由方法对新生成的报文进行路由选择。

EESRA路由方法的基本思想如下：假设节点v_i有一个报文Msg想要发给目 的节点v_d，在某个时刻它遇到了节点v_j并且该节点没有携带Msg。首先节点v_i会计算一个放大倍数amp_ratio，它的值为其中θ是一个事先确定好 的正数，我们称其为增长因子，这里的ttl是当前节点v_i所要转发的报文的TTL 字段的值，TTL₀是指该报文TTL字段的初始值。可见放大倍数amp_ratio是一 个随着报文的转发而减小的值。比较节点v_j的社交指标SM(v_j)是否大于节点v_i社交指标SM(v_i)的amp_ratio倍，如果不大于的话就由节点v_i继续携带报文Msg， 并在下一次与其它节点相遇时重新进行以上判断。这里节点的社交指标SM既可 以是节点的SimBet值，也可以是自己定义的能够反应节点之间社交关系的新的 度量指标等。

考虑到如果需要发送消息的源节点本身的社交指标SM比较大时将会使得 它很难遇到一个社交指标比它大amp_ratio倍的节点，这将对我们这套节能路由 方法的传递成功率造成较大的影响。为了解决这个问题，我们对每个报文添加 一个计数器node_counter字段，其初始值为0，并且规定每遇到一个社交指标比 自己宿主节点大的节点但仍未被转发出去时，其值就加1。当node_counter的值 大于一个事先约定好的阈值k时，就逐渐降低amp_ratio的值来放松当前持有报 文的节点对于报文转发条件的限制。具体执行步骤如下：

1)节点v_i有一个报文Msg想要发给目的节点v_d，在某个时刻它遇到了节点 v_j并且该节点没有携带Msg。如果节点v_j的社交指标SM大于节点v_i的社交指标， 那么进入下一步，否则转到第7)步。

2)如果node_counter的值大于事先约定好的阈值k，那么执行下一步，否则 执行第4)步。

3)节点v_i计算一个放大倍数amp_ratio，它的值为然后执行第5)步。

4)节点v_i计算一个放大倍数amp_ratio，它的值为然后执行下 一步。

5)比较节点v_j的社交指标SM(v_j)是否大于节点v_i社交指标SM(v_i)的 amp_ratio倍，如果不大于的话转到第7)步；否则进行下一步。

6)节点v_i将报文Msg转发给节点v_j，并且Msg的TTL字段减1， node_counter字段的值重置为0；判断TTL字段的值是否为0，如果是，丢弃该 报文；否则v_j携带报文Msg等待与其它节点相遇，当遇到其它节点时再从第1) 步开始进行以上判断。

7)Msg的node_counter字段的值自增1，节点v_i继续携带报文Msg，等到 下次与其它节点相遇时再从第一步开始进行以上判断。

8)方法结束。

为了验证本发明提出的路由策略在时延容忍网络中能达到的节能效果，接 下来的内容为在真实数据集的基础上通过仿真程序对本发明的路由策略进行模 拟，最后与时延容忍网络中其它较为常用的路由方法进行比较。

为了能在真实的延迟容忍网络中测试本发明所提出的方法，本实验利用在 Crawdad上公开发表的Infocom2006的追踪数据集。该数据集来源于参加2006 年在西班牙Barcelona举行的Infocom会议的与会人员在大会期间连续四天携带 具有蓝牙通信功能的iMotes进行交互的一些基本数据，包括每次交互双方的成 员编号以及交互的起始时间和结束时间等。本实验从中选取78名会议成员在93 小时内的相互交互信息作为模拟程序的训练与测试的数据集。

本模拟实验选取节点的SimBet值作为EESRA路由方法中节点的社交指标， 以1小时作为时间单位，把数据集中开始63小时的数据作为历史数据，用于构 建整个延时网络的社会关系图，程序中规定当两个节点之间的相遇次数大于1 时，就用一条边将这两个节点相连。随后从社会关系图中计算所需的节点自身 的社会属性和节点间的社交关系。最后用剩下30小时的数据分别对各个路由方 法进行模拟。对于每种路由方法，我们尝试了网络中所有可能的路由对，即每 一个节点尝试向网络中的其它节点发送一次报文，这样就得到了6006个源节点 到目的节点的待测节点对。本实验中除了传染病路由方法外，我们限定其余路 由方法的消息副本数都为1。

本实验将EESRA路由方法与以下四种路由方法进行对比：

1)Epidemic：当前节点将报文复制并转发给它所遇到的所有未携带该报文的 节点。

2)SimBet：当前节点v_i将报文转发给相遇的节点v_j，当且仅当节点v_j的 SimBet值比v_i的SimBet值大。

3)FRESH：当前节点v_i将报文转发给相遇的节点v_j，当且仅当在历史过程 中v_j最后一次遇到目的节点的时间比v_i最后一次遇到目的节点的时间晚。

4)Greedy-Total：当前节点v_i将报文转发给相遇的节点v_j，当且仅当在历史 过程中v_j遇到的节点数比v_i遇到的节点数多。

针对本实验模拟的所有路由方法，我们使用以下性能衡量标准来对每种路 由方法的性能进行比较：

1)传递成功率：成功将报文从源节点传送到目的节点的节点对占测试节点 对的百分比。

2)最大能耗：在一段时间内网络中消耗能量最大的节点的能耗(程序中规定 节点每发送或接收一次报文，其能耗加1)。

3)平均能耗：某段时间内网络中所有节点的平均能量消耗。

4)平均跳数：对于成功传送到目的节点的所有报文，它们从源节点到目的 节点的平均跳数。

5)平均转发次数：网络中所有报文跳数的平均值。

6)平均时延：对于成功传送到目的节点的所有报文，它们从源节点到目的 节点的时延平均数，单位是秒。

图2-图7比较了EESRA路由方法(增长因子θ为0.5)和其它四种路由方法的 各项性能指标。从图2可以看出Epidemic具有最高的报文传输成功率，EESRA 路由方法有着接近甚至略微高于SimBet路由方法的报文传递成功率。从图3和 图4中可以很明显的观察到EESRA路由方法使得网络中节点的平均能耗和最大 能耗远低于其它四种路由方法。从图5看出EESRA路由方法相对于容迟网络中 其它的三种单副本转发路由方法将报文传给目的节点的平均时延较大，这是因 为EESRA为了降低网络中节点的能耗，携带报文的节点总是等待社交指标比自 己大amp_ratio倍的节点，这就造成了较高的平均时延，但其时延仍在可接受的 范围之内。图6和图7体现出EESRA路由方法使得报文的平均跳数和平均转发 次数都远小于其它路由方法。要说明的是由于Epidemic路由方法采取多副本洪 泛式转发的路由策略，故其平均能耗最高。

综上所述，本发明所提出的基于社会属性转发的容迟网络节能路由方法能 够通过减少时延容忍网络中报文的转发次数来达到降低节点能耗的目的。另外 本发明所提出的是一个能够降低容迟网络中节点能耗的通用路由策略，由于其 中节点的社交指标SM可以选取任何一种已有社会属性也可以是新定义的能够 反应节点之间社交关系的新的度量指标等，所以本发明所提出的路由策略适用 于目前已有的任何基于社会属性转发的容迟网络路由方法。

以上所述的具体描述，对发明的目的、技术方案和有益效果进行了进一步 详细说明，所应理解的是，以上所述仅为本发明的具体实施例，用于解释本发 明，并不用于限定本发明的保护范围，凡在本发明的精神和原则之内，所做的 任何修改、等同替换、改进等，均应包含在本发明的保护范围之内。