陈宇婷，刘广钟

(上海海事大学 信息工程学院,上海 201306)

0 引 言

无线传感器网络的分布性、独立性、移动性等特点,使得网络中的大部分功能要依靠节点间的相互协作来进行。

目前通常假设所有网络节点都具有良好的协作性,即每个节点都愿意为其他节点提供服务。但是这种假设在实际的无线传感器网络环境中并不一定成立，无线传感器网络节点由于受到自身处理能力、存储空间、电池容量等各种资源的限制[1]，自私节点会不愿意帮助其他节点转发信息,这会影响无线网络正常的路由和数据转发功能。如何激励自私节点进行合作,并且诚实地进行合作以提高网络性能,是当前无线传感器网络研究领域面临的重大挑战之一,对于无线传感器网络的发展有着重要意义。

对于该问题，目前主要有基于信誉机制和基于支付机制。基于信誉机制，文献[2]中提出了算法：检测不良行为节点，同时，由Pathrater根据路径中节点的平均信誉值选择可靠的路由，避开不良节点。但该算法只是在路由选择时避开不良节点，没有对不良节点进行限制或惩罚，不能做到激励良好节点合作，未能充分利用节点，网络的整体性能并没有得到改善[2]。

基于支付机制的算法，通过支付虚拟货币补偿节点转发的能耗，激励节点合作，例如文献[3]。文献[4]中的PFAG算法利用支付机制建立多阶段博弈拍卖模型转发路径，与LEACH相比在降低和平衡网络能耗方面效果较好，但在文中假设所有节点是完全信息博弈，在实际无线传感器网络中更多是不完全信息博弈。文中只讨论部分文献，其他有关节点合作参考文献[5-10]。

1 问题建模

文中的网络结构模型如图1所示。基站远离传感器节点，簇头节点负责控制簇内节点的协同，簇内的普通传感器节点向相应的簇头发送数据，簇头节点将收集到的数据信息进行压缩融合处理，之后发送到基站。

图1 簇头节点向基站发送数据

对于基于支付机制算法，都会有第三方收取税收，文中由簇头节点收取簇内税务，再由基站从簇头收取税务。

在无线传感器网络中，数据转发需注意能耗均衡问题，易出现部分节点过分活跃，过早死亡，网络分割。基于支付机制，文中引用付酬的多阶段拍卖模型激励节点转发；同时考虑由于在拍卖过程中是不完全信息博弈，节点会出现过度虚假报价引起的整条路径支付过高的情况。文中对竞价中的节点报价和节点自私进行讨论，结合VCG思想做出合理标价，使整条路径支付和节点收益最优；在报酬支付时，结合信誉激励使用支付部分定金，转发成功后支付报酬，激励节点提高转发成功率和诚信支付以保证路径的可靠性，以此来找到一条最优路径。

2 算法模型

能耗模型为无线通信能量消耗模型，发送比特数据到距离为d的节点或基站的能量消耗[11]，即信号发射电路与信号放大电路的能耗之和：

(1)

其中，Eelec表示信号发射电路的能量损耗;εfs和εmp表示功率放大损耗;d0=87 m为距离阈值。发送节点与接收节点距离小于阈值则采用自由空间模型；否则采用多路衰减模型[12]。

2.1 路由发现模型

无线传感器网络中，自私节点不进行自主的积极合作，拒绝作为中间节点为其他源节点转发数据，假定节点间不存在共谋。

图2中，当节点A要将采集到的数据发送给目的节点时，A看作拍卖博弈的目的节点的代理买家，向周围节点购买转发服务，A广播购买转发服务的消息给周围的邻居节点，邻居节点会为了获得收益参与竞拍，将其看作拍卖博弈卖方。按照此方法向下广播，到达最接近簇首S的节点，簇头回一个确认消息给最接近自己的节点，确定连接可建立。

从最后端v8、v7和v6、v5、v4开始考虑竞价，节点计算出各自的竞拍真实价格，分布式计算，源节点不需要一直维护整个路径，每层代理买家节点自行处理。

v6、v7、v8出价竞争，假设v7获得转发机会，v2记录v7的价格，v2计算自己报价，然后将记录的v7报价与自己报价发送给v0，v0只需处理v2和v3给出的报价，进行竞争，直到A节点将竞争出整条路径path，A节点将整条路径价格记录，同数据一起从路径发送出去。

图2 节点路由发现结构

2.2 竞拍模型

定义邻居节点i的真实报价为：

(2)

其中，w为节点信誉值，每一个节点都有一个初始信誉值w，对于式2信誉值高的节点更容易竞拍成功，增大信誉好的节点参与转发的机会；γ=ak为源节点支付给下一节点的定金，a为固定常量值且是公共信息，k为数据比特值，由源节点广播；d为到下个转发节点的距离，每个竞拍节点可根据卖方广播时的时间戳与收到广播的时间差计算得到，e'为剩余能量，eij为转发数据所需能量，d、e'、eij都是节点的私人信息即根据其计算出的真实报价也为私人信息。当e'-eij<0时即剩余能量不足以转发时，报价会低于能耗和定金的和，自私节点不会参与到竞价中，e'-eij=0时不成立则不参与报价。其他条件相同时，d越小则成功传输机率越高，能耗越低其报价越低，使易成功传输节点获得转发机会更高。

当转发能耗相同，剩余能量越高时，报价越低，使剩余能量较多的节点可以有更多的机会参加到转发，更均衡地利用节点，以期降低和平衡网络能耗。

2.3 VCG机制

(3)

(4)

一般在机制设计时，文献[13-14]将效用函数ui考虑为拟线性：

ui=pi+ηi

(5)

在文中，pi为支付函数，ηi为真实报价转发收益。

对于诚实机制，满足：

(1)节点的策略为报告自己的私有类型θi=si；

定义一个整体最优输出结果o*(s)，为节点策略选择后所得到的输出结果o(s)中总体最优。

根据上述定义，设计输出函数及支付函数满足：

(6)

此处定义支付函数为：

(7)

(8)

将公式进行处理，可得ui：

2.4 基于VCG机制思想的节点标价

对于虚假报价，做一个简化结构图(见图3)进行讨论。

图3 节点路由选择结构简化图

(10)

下面进行讨论：

2.5 报酬支付

在货币机制中一般都默认或明确提出第三方定期收取税务，簇内则由簇头定期收取税务，簇间基站为可信第三方。

源节点得到簇头的确认消息后开始发送数据，同时支付下一节点定金γ，收到定金则进行转发，否则不转发，转发成功才会拿到全部报酬，想获得最大收益的理性自私节点不会为了定金而丢弃数据包不转发。

这里的簇头节点是簇内其他条件相同时信誉值最高即付酬自私性最低的节点。

经整理每个转发节点收益为：

(11)

收到报酬的节点向下一节点发送ack传递报酬之后一次转发完成，节点自行退出路径，且考虑到节点的移动性和能耗，本次得到的路径下次可能因为中间某个节点的能量耗尽或者离开而断开，每个节点有数据转发时就开始上述过程在现有环境中再开始一次竞拍，这也使得能量多的节点有更多机会参与，能量少的节点避免过早死亡，整体范围上增加了网络节点存活量、延长了生命周期。

考虑到节点的自私性，在获得目的节点或上一节点的报酬后发送ack却少付或不付给下一节点，此时下一节点对其计数减1，并广播计数情况,正常付给报酬则不广播改变计数。

设置阈值W=1，当对其计数w小于1时，节点将其定义为骗子节点，在一个较大时间内将其排出网络，拒绝为其转发数据，使其无法收益，一定时间后将计数恢复到1。

3 仿真实验

为了对算法进行测试和分析，使用MATLAB进行仿真实验。实验是由100个传感器节点随机分布在100 m×100 m的范围内。其中Eelec=50 nJ/bit，多径衰减模型εmp=0.001 3 pJ/(bit×m4),εfs=10 pJ/(bit×m4)，每个节点的初始能量为2 J/node，w=5，节点接收单位数据的能耗和数据融合能耗为γ=5 nJ/bit。

图4为一段时间内是否使用VCG对总支付的影响，直接根据最低竞拍节点报价标价支付，则总支付高出使用VCG机制后的支付值，自私节点的虚高报价使路径支付过高，容易导致预算超支问题。这表示基于VCG思想的标价机制，能有效均衡网络总支付，降低预算超支概率。

图4 VCG机制下时间与总支付关系曲线

图5是存活节点数量时间图。部分算法中检测不良节点并避开,只同合作节点进行合作，使得部分节点过度消耗死亡，部分节点不能充分利用，剩余存活节点较少。文中算法激励合作，同时考虑节点能量、距离等因素，在竞拍时有效利用高剩余能量短发送距离节点，均衡网络节点能耗，使得节点存活数量较多。

图5 剩余节点数量时间

图6为一段时间后节点收益图，信誉都有变化，且信誉高的节点总收益明显高于信誉低的节点。这是由于节点信誉变低后，税收变高竞拍成功几率变低，参与转发获取报酬的机会减少，故此总收益会低于信誉高的节点，对于理性节点不支付下一节点报酬的行为会减少，促进节点间良好协作，少部分信誉低节点收益高，是由于上一轮不传递报酬，但大部分节点信誉等级同收益成正比。

图6 节点收益

4 结束语

提出了一种基于VCG的无线传感器网络路由算法，考虑能耗条件使用拍卖博弈激励，有效促进自私节点合作，结合支付机制与信誉机制提高了节点数据转发量。在考虑节点自私情况下，结合VCG机制思想，控制节点过高虚假报价，有效均衡路径总支付。但是文中考虑节点理性，无恶意攻击篡改等，在以后的研究中会将非理性节点恶意攻击这些情况进行完善，并设计到算法中。