机会网络^[1]通过“存储-携带-转发”的方式实现间歇性连接网络的通信，这需要节点间的协作.然而，为了节省资源或安全等原因，节点存在自私行为，严重影响了机会网络性能^[2].机会网络的特性为设计基于Reputation^[3-4]和Credit^[5-6]的激励机制带来很大挑战.基于Barter的激励机制^[7]简单有效，更适合机会网络，但其严格等价交换原则降低了网络性能.

为此，笔者设计了一种基于债务的“物-物交换” (DBT, debt-based barter trade)激励机制.该机制通过引入债务关系的概念实现宽容等价交换原则，并设计基于信任的惩罚机制和基于债务的缓存策略以保证债务关系的可靠运行，从而增加了节点单次相遇时的交易数据量，提高了网络性能.

1 基本思想和假设

简单“物-物交换” (SBT, simple barter trade)激励机制^[7]的等价交换原则降低了网络性能.在SBT中，通过“你给我一个数据，我给你一个数据”的数据交换方式激励节点协作.如果在某次交换中，其中一方没收到对方的数据则终止交易，然而这可能导致节点因不能充分交换数据而降低网络性能.例如，当节点u和v相遇时，节点u转发给v的数据列表为[a, b]，节点v转发给u的数据列表为[d, e, f].在SBT机制下，节点v最多转发2个消息给节点u，浪费了机会网络中本就稀缺的通信机会，影响数据传输性能.另外，如果节点u在转发数据b时，由于无线信道的不稳定等原因，导致数据b传输失败，则节点v认为u不协作，也将终止交易，从而将进一步减少数据交易量.

SBT影响网络性能的原因在于遵循“你现在帮助我，我也现在帮助你”的一次等价交换原则，为此DBT通过引入债务关系的概念，实现了“你现在帮助我，我将来帮助你”的长期等价交换原则.如果节点间存在可信的债务关系时，节点v可以先借数据给u；或者在没收到u的数据b时，节点v也可继续转发数据给u.这样节点在相遇时能充分交换数据，提高网络性能.

然而，在完全分布式的机会网络中建立可信的债务关系很难，为防止节点赖账，设计基于信任的惩罚机制.另外，DBT建立在如下假设之上.

假设1   节点在网络中的标识是唯一的.

假设2  网络中节点都是理性的、自私的，但不存在恶意节点，节点只提供有效数据，并诚实设置债务值.

假设3   节点不清楚自身何时会离开网络.

2 DBT激励机制设计 2.1 债务关系

为打破节点交易时的一次等价交换原则，从而充分交换数据，引入债务关系的概念.

定义1  债务关系.节点u和v首次进行不等价交换时建立债权债务关系，简称债务关系.设s_u^v (s_u^v≥0)为节点u在本次交易中发送给节点v的数据量，如果s_u^v>s_v^u，则称节点u为债权方，节点u对v的债权值为c_u^v=s_u^v-s_v^u，节点v为债务方，节点v对u的债务值为d_v^u=s_v^u-s_u^v.

由于对应的债务值和债权值互为相反数，又因为节点u和v的债权或债务角色随它们之间数据交换量的改变而转变，所以为简化描述，用φ_u^v(t)表示t时刻节点u对v的债权值或债务值，简称债务，债务关系具有如下性质.

1) 对偶性：如果t时刻节点u是v的债权方，则节点v是u的债务方；如果节点u对v的债务为φ_u^v(t)，则节点v对u的债务为φ_v^u(t)=-φ_u^v(t).

2) 累加性：当节点u和v在每次相遇交易后按式(1)更新债务.

$\varphi _u^v\left( t \right) = \varphi _u^v\left( {t - 1} \right) + \left( {s_u^v - s_v^u} \right)$

(1)

3) 有界性：债务有界，设φ_max>0是债务上限值，则φ_u^v(t)∈[-φ_max, φ_max].

4) 相邻性：债务关系发生在直接相邻并通信的2个节点间.

5) 不可转移性：节点不可帮助其债权节点偿还债务.

2.2 信任值计算

设T_u^v(t)是t时刻节点u对v的信任值，T_u^v(t)∈[0, 1]，由直接信任值μ_u^v(t)和间接信任值ε_u^v(t)按式(2)合成.

$\begin{gathered} T_u^v\left( t \right) = \alpha \mu _u^v\left( t \right) + \varepsilon _u^v\left( t \right) = \hfill \\ \alpha \mu _u^v\left( t \right) + \sum\limits_{w \in \Re } {{\beta _w}T_w^v\left( t \right)} \hfill \\ \end{gathered} $

(2)

其中：$\begin{gathered} \alpha + \sum\limits_{w \in \Re } {{\beta _w}} = 1, \alpha = \frac{1}{{1 + \sum\limits_{w \in \Re } {T_u^w\left( t \right)} }}, {\beta _w} = \hfill \\ \frac{{T_u^w\left( t \right)}}{{1 + \sum\limits_{w \in \Re } {T_u^w\left( t \right)} }} \hfill \\ \end{gathered} $，$\Re $为向节点u转发节点v信任值的节点集. α和β_w用来调整节点w (w∈$\Re $∪{u})对v的信任值在信任合成时所占的比重，该比重与节点u对w的信任值成正比.直接信任值μ_u^v(t)在节点u和v每次交易后按式(3)更新.

$\mu _u^v\left( t \right) = \delta T_u^v\left( {t - 1} \right) + \left( {1 - \delta } \right)V_u^v\left( t \right)$

(3)

其中：T_u^v(0)=0.5，δ为历史信任值和当前信任值在合成时的调节系数，V_u^v(t)为t时刻节点u对v的信任评价值.令ΔV=min(s_v^u, s_u^v)-(s_v^u-s_u^v)，则V_u^v(t) (V_u^v(t)∈[0, 1])按式(4)计算.

$V_u^v = \left\{ \begin{gathered} \frac{{\Delta V}}{{{\varphi _{\max }}}}\;\;\;\Delta V \leqslant {\varphi _{\max }} \hfill \\ 1\;\;\;\;\;\;\;\;\Delta V > {\varphi _{\max }} \hfill \\ \end{gathered} \right.$

(4)

其中：min (s_v^u, s_u^v)为节点u和v的等价交换数据量，节点间等价交换将增加彼此的信任；s_v^u-s_u^v为节点v和u交换数据量的差值，交易中多付出的节点增加自己在对方的信任值，相反，提供数据少的一方将减少自己在对方的信任值.

2.3 惩罚机制

为防止债务关系失控，设计两阶段惩罚机制.第一阶段，债务分为无息债务和有息债务，当债务超出无息债务最大值时，债权方收取债务方的利息以促使债务方及时还债.设φ_umax^v为节点u对v的无息债务最大值，φ_umax^v∈[0, φ_max]，由节点u依据对v的信任值按式(5)计算.

$\varphi _{u\max }^v\left( t \right) = T_u^v\left( t \right) \times {\varphi _{\max }}$

(5)

节点u越信任v，给v的无息债务越大，所以理性节点会通过合作来增加自己在其他节点中的信任值.如果节点不及时还债，当φ_u^v(t)>φ_umax^v时，节点u对v的债务开始计算利息，每次交易后在式(1)的基础上再按式(6)进一步计算债务值，其中r为利率.

$\varphi _u^v\left( t \right) = \left( {1 + r} \right)\varphi _u^v\left( t \right)$

(6)

在惩罚期内，每次交易时债务方v先转发数据以保证s_v^u≥s_u^v，并且要求债务方在k次交易后使债务值回归到合理范围，即$\begin{gathered} \sum\limits_{i = 1}^k {{{\left( {1 + r} \right)}^{k - i + 1}}} {A_i} \geqslant {\left( {1 + r} \right)^{k + 1}}\varphi _u^v\left( {{t_0}} \right) - \varphi _{u\max }^v\left( {{t_0}} \right) \hfill \\ \left( {k \leqslant {\theta _T}, k \in {Z_ + }, {\theta _T} \in {Z_ + }} \right) \hfill \\ \end{gathered} $.其中，φ_u^v(t₀)和φ_umax^v(t₀)为进入惩罚期时节点u和v的债务和无息债务最大值，A_i为计算利息后第i次交易中s_v^u-s_u^v的值，θ_T为交易次数阈值.当k (k≤θ_T)次交易后，φ_u^v(t)≤φ_umax^v(t₀)，则节点u取消对v的利息计算，否则节点u进入对v的第二阶段惩罚.

在第二阶段惩罚中，节点u设置T_u^v(t)=0，并拒绝向v转发数据，直到v还清所有债务(含利息).如果节点v和熟悉节点都欠债过多，那么节点v将因不能从其他节点获得数据用于交换，而引发债务危机，被孤立出网络.节点v只有自己生产数据还清债务，才能重入网络.所以，理性节点会出于对得不偿失的恐惧而遵守债务关系.

2.4 缓存策略

DBT给出实用的缓存策略，使理性节点维持正常债务关系，避免债务危机.为设计实用的缓存策略，引入财富值的概念.

定义2  财富值.节点u在t时刻所有债务的和称为u的当前财富值，记为w_u(t)，w_u(t)=$\sum\limits_{v \in \pi _u^d} {\varphi _u^t\left( t \right)} $，其中π_u^d为和节点u有债务关系的节点集.

在不考虑利息的情况下，规定W_u=|π_u^d|×φ_max为u的财富值上限.设η是每次交易中缓存自己感兴趣数据和自己不感兴趣数据的比例，η∈[0, 1]，按式(7)计算.

$\eta = \left\{ \begin{gathered} \frac{{w{'_u}\left( t \right)}}{{{W_u}}},\;\;\;\;\;w{'_u}\left( t \right) \in \left( {\frac{1}{2}{W_u},{W_u}} \right] \hfill \\ 0.5,\;\;\;\;\;\;\;\;\;\;w{'_u}\left( t \right) \in \left( { - \frac{1}{2}{W_u},\frac{1}{2}{W_u}} \right] \hfill \\ 1 + \frac{{w{'_u}\left( t \right)}}{{{W_u}}},w{'_u}\left( t \right) \in \left( { - {W_u},\frac{1}{2}{W_u}} \right] \hfill \\ \end{gathered} \right.$

(7)

其中$w{'_u}\left( t \right) = \left\{ \begin{gathered} {w_u}\left( t \right)\;\;\;{w_u}\left( t \right) \leqslant {W_u} \hfill \\ {W_u}\;\;\;\;\;\;\;{w_u}\left( t \right) > {W_u} \hfill \\ \end{gathered} \right.$.当w_u(t)>$\frac{1}{2}$W_u时表明节点已经为别人提供较多的服务，有资本多考虑自身兴趣，η∈(0.5, 1]；当w_u(t) < -$\frac{1}{2}$W_u时，节点需更多为其他节点缓存数据以免出现债务危机，η∈[0, 0.5)；当-$\frac{1}{2}$W_u≤w_u(t)≤$\frac{1}{2}$W_u时，债务处于合理区间，η=0.5.

η是节点u的整体缓存策略，当节点u和具体节点v交易时，其交易量需要满足-φ_umax^v≤s_v^u-s_u^v+φ_u^v(t)≤φ_umax^v.

3 仿真实验

基于ONE^[8]设计实验，网络有10个节点，节点相遇模型服从Poisson分布，相遇时间间隔和相遇持续时间都服从参数为0.1的指数分布.系统每隔1 s生成一个数据，随机选择源节点和相异的目的节点，系统仿真时间为1 000 s.信任初始值为0.5，债务初始值为0，有息债务惩罚交易次数阈值θ_T=5.

仿真分别在合作场景和自私场景下进行.实现3种路由：ER、SBT_ER和DBT_ER，分别代表了无激励机制与基于SBT和DBT激励机制下的ER路由.比较的性能参数有投递率、迟延和网络负载.仿真结果如下.

1) 合作环境

如图 1所示，相同缓存的投递率比较结果是ER>DBT_ER>SBT_ER.因为，在现有缓存情况下ER能充分交换数据，获得较高的投递率；SBT因采取等价交换原则，在每次交易中减少了交易量，降低了投递率；DBT通过债务关系改进了SBT的等价交换，增加了节点相遇时的交易量，和SBT相比，极大提高了投递率，但是因为债务的有界性，导致不是所有时候都能充分交换数据，使投递率略低于ER.缓存为8的投递率高于缓存为2的投递率，因为缓存越大，转发机会越多，投递率越高.缓存为8时，投递率随着数据生存时间(TTL, Time To Live)增加而增大，而当缓存为2、TTL大于12 s时，投递率随着TTL增加而下降.因为TTL增加，数据转发机会增大，投递率增加，但系统数据增多，如缓存不能满足需要则溢出，从而降低投递率.

如图 2所示，相同缓存的迟延比较结果是ER>DBT_ER>SBT_ER，但是差异不大.因为SBT和DBT虽然不同程度上阻碍了数据交换，但是其投递率也下降，所以成功接收数据的平均迟延差异不大.迟延随TTL增加而增大，因为TTL增加，目的节点在更晚的时候接收数据的概率增加，导致成功接收数据的平均迟延增加.缓存为2的迟延低于缓存为8的迟延，原因是缓存越大，数据被长时间缓存而到达目的节点的概率增加，这样成功接收数据的平均迟延增加.

如图 3所示，相同缓存的网络负载比较结果是ER>DBT_ER>SBT_ER，其原因和投递率原因相似.缓存为2的网络负载低于缓存为8的网络负载，因为缓存越大，带来的转发机会越多.网络负载随TTL增加而增大，因为数据生存时间越长，其转发机会越多.但当缓存不能满足需求时溢出使数据失去转发机会而减小网络负载，因此缓存为2、TTL大于12 s时网络负载增长缓慢.

2)自私环境

自私环境下，仿真取TTL为12 s，缓存为2和8的数据进行对比，结果如图 4所示.

无激励机制的ER随自私节点增多，数据的转发次数减少，因而网络负载减小，但是也降低了投递率，增加了迟延.而在SBT和DBT激励下的ER受自私节点数影响不大，DBT_ER的投递率性能优于SBT_ER，因为DBT的债务机制增加了节点数据交换的灵活性，增加了每次相遇节点的数据交换量，提高了投递率性能.在迟延上，二者性能差异不明显，原因是SBT投递率比DBT低，成功接收数据的迟延影响不大.但是DBT_ER的网络负载高于SBT_ER，也是因为DBT的债务机制增加了数据交换量.

缓存为8时的投递率、网络负载和迟延均高于缓存为2的情况.因为缓存增加，转发机会增大，投递率提高，但网络负载也增加.同时，缓存增加使数据被更长时间缓存而到达目的节点的概率也增加，从而增加了成功接收数据的迟延.

4 结束语

通过引入债务关系增加了单次交易的数据交换量，从而提高了网络性能.为防止自私节点赖账设计了基于信任的惩罚机制，并且依据节点当前债务值设计了动态的缓存策略，以保证节点债务的合理性.实验证明DBT和SBT相比，在保证激励节点协作的情况下，提升了网络性能.笔者进一步工作将利用重复博弈理论建模分析DBT并在真实移动轨迹上测试DBT性能.