Fig. 1 Principle of network coding
图1 网络编码原理
张晓宇 尚 涛 刘建伟
(北京航空航天大学电子信息工程学院 北京 100191)
(zhangxiaoyubuaa@163.com)
摘 要 网络编码是数据传输领域的一项新技术.在网络编码中，节点允许在数据转发的基础上对数据进行编码处理，从而提高网络的带宽利用率和吞吐量.然而当网络中某些节点存在自私性时，这些自私节点会延迟转发数据，从而造成网络编码时延的增加，降低通信的效率，严重时会造成网络编码中断，出现通信混乱.针对该问题，提出了基于探测-支付机制的网络编码自私节点激励方案.在方案中，首先对网络节点的时延进行探测，将网络节点的时延当作网络编码的成本，然后引入经济学中的支付机制，把网络编码看作是一种源节点消费、中继节点提供服务的交易行为.在支付机制运行的过程中，源节点作为消费者需要向提供网络编码服务的中继节点支付报酬.由于中继节点在提供服务时获得收益，因此支付机制会提高中继节点配合源节点进行网络编码的积极性.方案分析表明:该激励方案能够减小网络编码的时延，有效地抑制节点的自私性，最终提高了网络编码的有效性.
关键词 网络编码；节点自私性；激励方案；时延探测；支付机制
网络编码作为一种新兴技术在提高网络传输性能上有显著的效果 [1] .Ahlswede等人 [2] 于2000年提出了网络编码概念，指出对组播网络中某些节点附加额外的编码操作能使源节点与组播成员之间达到最大流-最小割的组播速率极限，网络编码作为路由方式的扩展，在提升吞吐率、带宽利用率上有很大潜力 [3] .网络编码需要中继节点的协作，只有通过中继节点对来自不同节点的数据进行接收、编码、转发，才能够实现网络编码 [4] .但是在网络编码的过程中，由于节点自身的电池容量、计算能力、存储能力的限制，节点会延迟编码甚至直接丢弃数据包，表现出自私性 [5] .节点的自私性会使网络编码的时延大大增加，使网络编码的有效性降低.同时中继节点时延的增加也会造成网络编码混乱，影响网络编码的可靠性 [6] .
目前抑制网络节点自私性的研究主要分为2类.第1类是基于信誉的研究：Marti等人 [7] 提出的 Watchdog和pathrate机制最初是用来解决Ad hoc网络中路由错误的问题.其中，Watchdog机制用来监测具有不良行为的自私节点，pathrate机制用来避免将这些节点包含在路径中.Buchegger等人 [8] 提出的CONFIDANT机制的原理是:监测并孤立不合作的节点.第2类是基于支付的研究：利用虚拟货币来激励中继节点转发数据，即转发数据的节点会获得酬劳，而接受服务的节点需付费.Anderegg等人 [9] 提出了Ad hoc-VCG协议，把转发数据看作是价格拍卖活动，激励各中继节点给出转发所需的真实成本.Buttyán等人 [10-11] 引入了一种计数器来激励节点帮助其他节点转发数据包，当节点发送自己的数据时计数器值减小,节点发送其他节点的数据时计数器数值增加.
以上文献中提出的方案能够有效激励普通网络中的自私节点，然而针对网络编码中的自私节点的研究还很少，本文致力于研究如何激励网络编码中自私节点的问题.结合以上方案的优缺点，本文设计了一种新的方案——基于探测-支付机制的网络编码自私节点的激励方案，即Detect-Defray方案.
1 . 1 随机线性网络编码中节点的自私问题
网络编码的原理 [12] 如图1所示，在中继节点U处可以对来自源节点S 1 ，S 2 的数据进行编码，链路UV可以把编码后的数据传递到目标节点D 1 ，D 2 处，通过译码，目标节点D 1 ，D 2 就可以同时得到数据a，b.可见，网络编码通过编码的方式对数据进行压缩，从而提高了网络的吞吐量，增加了带宽的利用率.
Fig. 1 Principle of network coding
图1 网络编码原理
由网络编码的原理可知，中继节点是完成网络编码的关键节点.根据中继节点是否进行编码，本文把中继节点划分为2种类型：第1种类型如V只对数据进行接收和转发而不进行编码，这类节点本文称为Ⅰ型中继节点；第2种节点如U不仅需要对数据进行接收和转发，还需要对数据进行编码，这种节点本文称为Ⅱ型中继节点.
在网络编码中，由于节点电池容量、计算能力或者内存等因素的限制，为了节省自身的宝贵资源，网络中某些节点会出现延迟对数据包编码和转发的行为，有的节点甚至会拒绝编码或转发，这种行为称为节点的自私性行为 [13] .如图1所示，对于网络编码中的节点，节点S 1 ，S 2 是数据的发送方，是网络编码的发起者，不会表现出自私性;节点D 1 ，D 2 是数据的接收方，不存在编码和转发行为，所以也不会表现出自私性.因此网络编码中节点的自私性行为表现在中继节点上 [14] .
当Ⅰ，Ⅱ型中继节点表现出自私性行为时，这些中继节点就会拖延甚至拒绝对数据进行编码和转发，从而引起中继节点的时延增加，即网络编码节点自私性的直观表现是中继节点时延的增加.因此，如果能够采取激励措施减小中继节点的时延，就可以抑制中继节点的自私性.
1 . 2 支付机制
在经济学中存在这样一种机制：在市场中所有的参与者都会提供服务和进行消费，他们既是消费者，也是服务者.在交易的过程中，服务者会为自己的服务制定价格P，消费者会为了获得服务会支付金额P.假设在该机制执行前，所有的参与者拥有原始金额M O ,如表1所示,在系统进行交易过程中,服务者提供服务获得收益,服务者余额M S 增加.消费者支付金额，消费者余额M C 减小.当一个消费者的余额M C lt;0时，则不能再进行消费 [15] .
Table 1 Operation Mechanism of Defrayment
表1 支付机制运行
在这种机制下，所有的参与者为了能够进行消费，都需要保证自己的余额大于0,这就激励所有参与者积极地去提供服务获得收益.与此同时，在消费过程中，消费者只会选择成本较低的服务者，因此服务者为了获得利益，不得不降低自己的成本，即经济学中的竞争导致成本和价格下降.在这种情况下，所有的参与者都会积极提供服务，同时降低自己的成本.这种机制限制了某些参与者只进行消费而不提供服务的自私行为，同时降低了服务的成本.本文受到上述经济学支付模型的启发，尝试把支付模型的原理应用在网络编码中来抑制节点的自私性.
网络编码中的自私节点会造成网络编码时延的增加，降低网络编码的有效性和可靠性，因此本文设计了基于支付的网络编码自私节点的激励方案——探测-支付方案，来抑制网络编码中节点的自私性.激励方案主要分为2部分：1)网络编码中继节点的时延探测部分，主要进行中继节点的时延探测，通过对中继节点的时延探测，使源节点在进行网络编码时能够选择出时延最小的节点；2)网络编码服务的支付运算部分，基于时延探测机制，将探测出的时延信息作为各节点的成本，方案运行后，各个节点会积极地配合其他节点进行网络编码，同时各个节点也会主动减小自己的时延.
2 . 1 网络编码中继节点的时延探测
鉴于网络编码中节点存在自私性，需要对节点的自私性进行量化和统计.当节点表现出自私性时，它们的主要行为是拖延编码或转发，甚至拒绝编码或转发,即节点自私性的直观表现是节点时延的增加.同时，可以看出，节点的自私性程度与节点时延长短的成正比 [16] ，自私性较高的节点所引起的时延也比较长，而那些绝对自私的节点(拒绝编码和转发的节点)所引起的时延接近于无穷大.因此，本文以时延作为指标来量化节点的自私程度.
本文首先设计方案中的探测部分——网络编码中继节点的时延探测方案，探测方案的基本思想是源节点发送探测数据包并计时，然后等待数据包回传后停止计时，所测得的时间差就是该节点的时延.不同类型的中继节点在网络编码中的任务不同，因此本文针对Ⅰ，Ⅱ型的中继节点，设计了不同的探测方法.
1) Ⅰ型中继节点的时延探测方案
Fig. 2 Detection method of type Ⅰ intermediate node
图2 Ⅰ型中继节点探测方法
对于Ⅰ型中继节点，如图2所示，与S相邻的中继节点A，B，C，D均为Ⅰ型中继节点.Ⅰ型中继节点在网络编码中只需要对数据进行转发，因此探测方案如下：首先，源节点S通过组播的方式向相邻的节点发出探测包，同时开始计时，并等待数据包回传.当收到回传的数据包时停止计时,得到探测时间为 
其中下标i表示该节点的编号，上标Ⅰ表示节点的类型).探测后，将节点时延信息 
存储在路由信息表中，方便之后的网络编码进行路由选择.
2) Ⅱ型中继节点的时延探测方案
对于Ⅱ型中继节点，如图3所示，与S 1 ，S 2 相邻的中继节点A，B，C为Ⅱ型中继节点.Ⅱ型中继节点不仅需要接收、转发数据，同时还需要对数据进行编码.对于Ⅱ型中继节点来说，在进行网络编码时，需要有2个数据源，即源节点S 1 ，S 2 .探测方案如下：首先需要源节点S 1 ，S 2 寻找共同相邻的Ⅱ型中继节点，然后以组播的方式同时向相临的节点发送数据包.在图3中，S 1 ，S 2 同时向中继节点A，B，C发送探测数据包，并开始计时.当这些节点接收到数据后进行编码，这里采用最简单的异或编码方法.编码完成后，将数据回传，当2个源节点都收到回传数据包之后停止计时，时间为 
其中下标i表示该节点的编号，上标Ⅱ表示节点的类型).同样，把探测时间 
存储在源节点S 1 ，S 2 路由信息列表中，方便以后寻址时作出决策.
Fig. 3 Detection method of type Ⅱ intermediate node
图3 Ⅱ型中继节点探测方法
通过时延探测机制，可以达到2个目的：1)源节点在进行网络编码节点选择时，能够选择出时延最小的中继节点；2)将各中继节点的自私性通过时延的形式进行量化，这个时延信息将在支付部分(d)中作为各节本成本.同时，节点的自私性是不断变化的，可能随着整个网络编码系统采取的激励措施不同，这些节点的自私性也会发生变化 [17] .因此需要定时重新探测中继节点的时延，更新时延信息,从而使时延信息实时地反映节点的自私性 [18] .
2 . 2 网络编码服务的支付运算
在设计支付模型时，首先会介绍支付模型中的4个元素：节点的服务价格、原始资金、节点余额、支付行为.
1) 节点服务价格.通过2.1节分析可知，节点的自私性可以通过节点的时延来量化，时延越长则自私性越高，提供服务的成本也越高，则价格越高.假设在网络编码中，节点的成本和价格是一致的，本文把各个节点的时延T i 当作该节点提供服务的成本(即价格)：
P i =T i .
(1)
2) 原始资金.为了使整个通信系统在启动时各个节点有足够的本金运行，不使整个通信系统一开始就停止，因此每个节点都需要具备一定的原始资金，从公平角度出发，每个节点都有相同的原始资金，均为M O .
3) 节点余额.因为系统存在支付行为，节点的资金会发生变化，本文把节点的资金称为余额M.假设节点的编号为i，系统的时序为j，则该节点的余额为M ij ，余额信息存放在节点的路由信息表中.当余额M ij ≤0时，则该节点不能再作为源节点发起网络编码.节点余额M ij 代表该节点购买网络编码服务的能力，M ij 值越大，则购买网络编码服务的能力越强.
4) 支付行为.当整个交易系统运行后，就会出现支付行为.源节点需要向提供网络编码服务的中继节点支付费用.支付后，源节点的余额减小，中继节点的余额增加.假设支付前，网络的时隙为j，支付后时隙为j+1.支付后，源节点的余额M i(j+1) 为
M i(j+1) =M ij -P，
(2)
中继节点余额为
M i(j+1) =M ij +P，
(3)
其中:
(4)
2如图4所示，源节点S 1 ，S 2 需要分别将数据传送到目标节点D 1 ，D 2 ，在网络传输过程中进行网络编码处理.假设开始时网络编码的时序为j，网络中的节点都有基本的运算能力.
Fig. 4 Network coding applied defrayment mechanism
图4 应用支付机制的网络编码
以下是探测-支付方案在网络编码中应用的具体步骤：
Step 1. 源节点S 1 和S 2 检查自身的余额，如果M S 1 j gt;0 amp; M S 2 j gt;0，继续执行 Step 2，否则结束.
Step 2. 源节点S 1 和S 2 进行中继节点时延探测( Detect 部分)，S 1 ，S 2 向相邻的中继节点发送探测数据包，然后将探测到的时延信息存储在S 1 ，S 2 的路由信息表中.
Step 3. 源节点S 1 和S 2 需要根据路由信息表中的时延信息(也即中继节点的服务价格)选出成本最小的Ⅰ,Ⅱ中继节点.如图4所示，假设V 2 ，U 2 被选中.
Step 4. 中继节点进行网络编码.
Step 5. 编码结束后，进行支付.首先S 1 ，S 2 同时向Ⅱ型中继节点U 2 支付,其中U 2 的成本为 
分别向U 2 支付其成本的一半.支付后节点S 1 的余额为
2，
(5)
节点S 2 的余额为
2，
(6)
节点U 2 的余额变为
(7)
源节点S 1 ，S 2 向Ⅰ型中继节点V 2 进行支付，支付后，节点S 1 的余额为
2，
(8)
节点S 2 的余额为
2，
(9)
节点U 2 的余额变为
2.
(10)
网络中的节点都有基本的运算能力，节点的价格都存放在节点的路由信息列表中，因此支付运算可以直接在节点的路由信息表内进行 [19] .
以上就是探测-支付方案在网络编码中的应用步骤.随着方案的执行，网络编码中源节点和中继节点的余额都在发生变化.易知，源节点S 1 ，S 2 进行消费，余额变少，中继节点V 2 ，U 2 提供服务，余额增加.这样，源节点S 1 ，S 2 为了下次进行网络编码，就需要去作为中继节点提供服务增加收入，同时为了获得提供服务的机会，就需要主动减小自己的服务价格.
与普通网络编码相比，引入激励方案的网络编码包含探测和支付2部分.激励方案能从2个方面提高网络编码的效率，首先是对于单次网络编码时，由于引入了探测机制，源节点能够选择时延最小的中继节点.其次，从全局的角度来看，如图5所示，不同的中继节点选择构成了不同的网络编码方案，支付机制在网络编码中引入了竞争，促使每个节点都主动减小自己的时延，从而整体减小了网络编码的时延 [20] .本节讨论的网络编码的时延为网络编码的中继节点的总时延.
Fig. 5 Network coding model
图5 网络编码模型
3 . 1 单次网络编码的时延优化分析
普通网络编码在选择中继节点进行编码时，这种选择是随机，而采用激励方案后，由于激励方案中存在时延探测机制，则会选择时延最小的中继节点.假设一般网络编码所需的时间为T，如图5所示，网络编码系统中有n种网络编码选择方案，则可以得到一般网络编码中继节点时延平均值为
/ n .
(11)
假设引入时延探测机制的网络编码所需的时间为T′，则引入时延探测机制后网络编码中继节点时延为
T′= min (T 1 ,T 2 ,…,T n )，
(12)
显然，T′≤T.
采用时延探测机制后网络编码的时延可以降低的百分比为
η= 
.
(13)
由于方案的探测时间是随机分布的，这种分布符合正态分布的特点，但是存在一个下限，就是编码最小时延.假设网络编码方案中的中继节点时延符合正态分布，其方差为1，均值为3，最小时延为1，即X～N(3,1)，分布的方程为
(14)
其中，σ=1,μ=3.
概率密度分布图如图6所示，从统计意义上看，普通网络编码的时延为正态分布的均值3，而引入时延探测机制的网络编码却可以选出最小的时延方案，时延为1.
Fig. 6 Delay distribution of normal network coding
图6 普通网络编码时延分布
所以采用上述机制，网络编码的时延减少的百分比为
η= 
=66.7%.
(15)
3 . 2 全局网络编码时延的优化分析
从全局的角度来进行分析，激励方案除了在进行网络编码时能够选择最小的时延之外，还会激励中继节点减小网络编码的时延 [21] .假设采用支付机制之前，各种网络编码方案的时延为T 1 ，T 2 ，…，T n .采用支付机制之后的网络编码的时延为T 1 ，T 2 ，…，T n .这些时延都是随机分布的，符合正态分布的特点.同时，这些数据有一个理论上的最小值，显然
T 1 ≥ 
.
(16)
所以，假设所有的节点都参与了网络编码，则普通网络编码的全局时延信息为
(17)
采用激励方案后的网络编码的全局时延信息为
(18)
从全局上来看，采用上述机制后全局的网络编码时延降低的百分比为
η= 
.
(19)
当引入支付机制之后，2种网络编码的时延都会减小，假设引入支付机制后时延的均值μ 2 减小到1.5，方差仍为1，最小值为1，服从正态分布，即X～N(1.5,1)，n表示网络编码可选的方案总数，概率密度分布图如图7所示:
Fig. 7 Delay distribution of network coding applied defrayment mechanism
图7 应用支付机制的网络编码时延分布
首先计算普通网络编码的全局时延，如图6所示，正态分布的均值为μ 1 ，方案总数为n.时延存在下限1，须对图6中时延大于1的值求和.所以T global 应为均值μ 1 的n倍减去下限值1之外的时延值的和，即全局时延为
(20)
时延小于1的方案数的概率可以通过正态分布的概率P(xlt;1)得到.概率函数为
(21)
其中f(x)为正态分布,表达式为
(22)
正态分布的概率P(xlt;1)可以通过正态分布计算得到为0.022 8，所以时延小于1的方案数n′=P 1 (xlt;1)×n.
本文对小于1的时延做一个近似求解，假设这些节点的平均值 
=0.5，易知:
所以:
T global ≈n×μ 1 -P 1 (xlt;1)×n× 
.
(24)
同理，当引入支付机制的网络编码时延近似求解为
≈n×μ 2 -P 2 (xlt;1)×n× 
,
(25)
其中μ 2 =1.5， 
=0.5，P 2 (xlt;1)=0.308 5.
所以在这种情况下，采用支付机制的网络编码的时延减少的百分比为
η= = 
=
54.97%
通过图6与图7的比较，可以看出在采用激励方案后，网络编码的节点的时延均值降低，即引入激励方案的网络编码会导致整个网络编码系统的中继节点的时延减小、自私性降低.
本文运用经济学中的观点，引入了探测-支付机制，对网络编码中的自私节点进行激励.引入激励方案的网络编码与传统网络编码相比较，在以下2点优化了时延，抑制了节点的自私性：
1) 激励方案引入了时延探测机制，因此，源节点能够选择出时延最小的节点进行网络编码，而传统网络编码选择节点是随机的；
2) 激励方案将时延作为价格引入了支付，每个节点的余额需大于零才能进行网络编码，这样就促使所有的节点必须主动配合其他节点进行网络编码获取收益.同时源节点会选择价格较低的中继节点进行网络编码，因此节点会主动减小自己的时延，以获得提供服务的机会.这样各个中继节点都会主动降低自己的编码时延，从而在全局上减小网络编码的时延，抑制了节点的自私性.
参考文献
[1]Wang Wei, Yang Ming, Luo Junzhou, et al. Modeling and analysis of multicast delay in network coding-based multi-radio wireless mesh networks[J]. Journal of Computer Research and Development, 2012, 49(6): 1174-1184 (in Chinese)(王维, 杨明, 罗军舟, 等. 基于网络编码的多射频Mesh网组播时延建模与分析[J]. 计算机发展与研究, 2012, 49(6): 1174-1184)
[2] Ahlswede R, Cai Ning, Li S Y R. Network information flow[J]. IEEE Trans on Information Flow, 2000, 46(4):1204-1216
[3]Shang Tao, Fan Yong, Liu Jianwei. Throughput-delay analysis of one-to-many wireless multi-hop flow based on random linear network coding[J]. Journal of Communications and Networks, 2013, 15(4): 430-438
[4]Raymond Y. Network coding: A historical perspective[J]. Proceeding of the IEEE, 2011, 99(3): 366-371
[5]Li Xu, Lin Zhiwei, Ayong Y. Analysis and countermeasure of selfish node problem in mobile ad hoc network[C] 
Proc of Int Conf on Computer Supported Cooperative Work in Design. Piscataway, NJ: IEEE, 2006: 1027-1030
[6]Yoo Y, Agrawal D P. Why does it pay to be selfish in a MANET[J]. IEEE Wireless Communications, 2006, 13(6): 87-97
[7]Marti S, Giuli T J, Lai Kang, et al. Mitigating routing misbehavior in mobile ad hoc networks[C] Proc of the ACM IEEE Int Conf on Mobile Computing and Networking. New York: ACM, 2000: 255-265
[8]Sonja B, Le B. Performance analysis of the CONFIDANT protocol[J]. Cheminform, 2002, 38(4): 1014-1021
[9]Anderegg L, Eidenbenz S. Ad hoc -VCG: A truthful and cost-efficient routing protocol for mobile ad hoc networks with selfish agents[C] Proc of Int Conf on Mobile Computing and Networking. New York: ACM, 2003: 245-259
[10]Buttyán L, Hubaux J P. Nuglets: A virtual currency to stimulate cooperation in self-organized mobile ad hoc networks[J]. Journal of Federal Institute of Technology, 2001, 15(4): 356-361
[11]Buttyán L, Hubaux J P. Enforcing service availability in mobile ad-hoc WANs[C] Proc of the Workshop on Mobile amp; Ad Hoc NETWORKING amp; Computing. Piscataway, NJ: IEEE, 2000: 87-96
[12]Huang Jiaqing, Li Zongpeng. Network Coding Principles[M]. Beijing: National Defense Industry Press, 2012: 24-25 (in Chinese)(黄佳庆, 李宗鹏. 网络编码原理[M]. 北京: 国防工业出版社, 2012: 24-25)
[13]Das S K, Saha B J, Chatterjee P S. Selfish node detection and its behavior in WSN[J]. Journal of Engineering amp; Applied Sciences, 2014, 9(6): 231-236
[14]Yao Hong, Zhong Shao. Cheating detection for payment based incentives with application to network coding[J]. Ad Hoc amp; Sensor Wireless Networks, 2014, 24(1): 1-19
[15]Jiang Qingfeng, Men Chaoguang, Li Xiang, et al. A virtual currency-based incentive-aware low delay routing for DTNs[J]. Journal of Computer Research and Development, 2015, 52(12): 2707-2724 (in Chinese)(蒋庆丰, 门朝光, 李香, 等. 基于虚拟货币的DTNs激励感知低时延路由[J]. 计算机研究与发展, 2015, 52(12): 2707-2724)
[16]Zhao Guangsong, Chen Ming. Research of incentive-aware data dissemination in selfish opportunistic networks[J]. Journal on Communication, 2013, 34(2): 73-84 (in Chinese)(赵广松, 陈鸣. 自私性机会网络中激励感知的内容分发的研究[J]. 通信学报, 2013, 34(2): 73-84)
[17]Kasapaki E, Schoeberl M, Sørensen R B, et al. Argo: A real-time network-on-chip architecture with an efficient GALS implementation[J]. IEEE Trans on Very Large Scale Integration Systems, 2016, 24(2): 479-492
[18]Xu Hongfang. Research and analysis on selfish nodes in P2P network[J]. Software Guide, 2014, 34(2): 122-124 (in Chinese)(薛红芳. P2P网络中节点自私性分析及对策研究[J]. 软件导刊, 2014, 34(2): 122-124)
[19]Jung S G, Kang Bo, Yeoum S, et al. Trail-Using ant behavior based energy-efficient routing protocol in wireless sensor networks[J]. International Journal of Distributed Sensor Networks, 2016, 16(4): 1-9
[20]Yokoyama S, Nakane Y, Takahashi O, et al. Evaluation of the impact of selfish nodes in ad hoc networks and detection and countermeasure methods[C] Proc of Int Conf on Mobile Data Management. Piscataway, NJ: IEEE, 2006: 95
[21]Muthumalathi N, Raseen M M. Fully selfish node detection, deletion and secure replica allocation over MANET[C] Proc of Int Conf on Current Trends in Engineering and Technology. Cambridge, MA: MIT Press, 2013: 413-415
Zhang Xiaoyu , born in 1993. Master. His main research interests include network coding, information security, etc.
Shang Tao , born in 1976. PhD, associate professor, master supervisor. His main research interests include network coding, quantum cryptography, network security, etc.
Liu Jianwei , born in 1964. PhD, professor, PhD supervisor. His main research interests include cryptography, information security, network security, etc.
Zhang Xiaoyu, Shang Tao, and Liu Jianwei
(School of Electronic and Information Engineering, Beihang University, Beijing 100191)
Abstract Network coding is a new technology in the field of data transmission. In network coding, nodes are allowed to encode the data
received from different nodes so that bandwidth utilization and network throughput can be improved. Whereas, if there are some selfish nodes in the network, these selfish nodes will delay or refuse coding and forwarding. It will increase the delay of network coding and reduce the efficiency of communication. When the problem gets more serious, the network coding will break off, and communication chaos will arise. In order to solve this problem, the motivation scheme based on detect-defray mechanism for selfish nodes of network coding is proposed. In the motivation scheme, firstly, the delay of nodes for encoding and forwarding will be detected, which can be the cost of network coding. Then it operates the defrayment part, in which network coding is regarded as a kind of economic behavior, and source nodes are consumers, and intermediate nodes are providers, and remuneration will be defrayed for providers from consumers when defrayment mechanism operates. Since intermediate nodes benefit from network coding when providing services, the enthusiasm of intermediate nodes for network coding can be improved, meanwhile the delay of network coding will be reduced. Scheme analysis shows that, the motivation scheme can reduce the delay of network coding and control the nodes’ selfishness effectively. Finally, the effectiveness of network coding can be improved.
Key words network coding; selfishness of nodes; motivation scheme; delay detection; defrayment mechanism
收稿日期： 2016-10-28；
修回日期： 2017-03-21
基金项目： 国家自然科学基金项目(61571024)；国家重点研发计划项目(2016YFC1000307)
This work was supported by the National Natural Science Foundation of China (61571024) and the National Key Research and Development Program of China (2016YFC1000307).
通信作者： 尚涛(shangtao@buaa.edu.cn)
中图法分类号 TN915.08； TP309.2