基于Merkle哈希树的机会社会网络节点协作转发机制

王 杨，黄少芬，许闪闪，赵晨曦，李 昌，赵传信

(安徽师范大学 计算机与信息学院，安徽 芜湖 241002)

1 引 言

机会网络是一种利用节点移动带来的相遇机会实现短距离无线传输的自组织网络[1].该网络不需要源节点与目标节点建立完全连接.基于机会网络特点及应用场景，人们通过使用移动无线设备相互联系，形成了机会社会网络(Opportunity Social Network)[2].机会社会网络中一个典型的例子是人们在日常生活中通过自身携带的智能手机四处游走，并且在彼此的传输范围内通过蓝牙或WIFI相互通信[3].

传统的无线网络根据当前网络拓扑信息建立路由表，并根据其变化进行路由信息的维护，同时消息的传输依赖于稳定的端到端连接，而机会社会网络在网络拓扑结构不稳定时仍可以保持消息的高效传输.其中节点的协作性机制对于机会社会网络来说至关重要.由于源节点与目标节点之间通信受到距离的限制，消息不能直接从源节点发送给目标节点，此时需要中间节点的协作来完成.而节点的自私对网络的危害较大，怎样应对网络中节点的自私行为，并且增强网络节点之间的协作是本文研究的重点.

先前的协作转发机制考虑到节点的社会属性、自身状态和节点优先级，忽视了节点的移动带来相遇位置改变及存在自私节点导致消息传输可靠性降低.针对上述问题，本文提出一种基于Merkle哈希树的节点协作转发机制，该机制根据Merkle哈希树检测网络中存在的自私节点并将其删除，其次根据节点相遇位置去计算相遇节点的距离大小，综合考虑两个因素选择合适的转发路径进行消息的传输，保证了消息的安全性及高效性.

2 相关工作

机会社会网络使用“存储-携带-转发”方式进行消息的传输，而许多节点由于自身的缓存空间、能量等因素表现自私行为，不愿意将消息转发给其他节点或者丢弃数据包，从而降低整个转发性能.为了抑制节点的自私行为，已有相关的研究成果出现.

Chen等人[4]提出基于激励的路由机制.通过激励自私节点参与消息转发，源节点与目标节点需要随时获取控制信息，并计算网络中节点的收益.Ning等人[5]提出一种基于信用的激励机制，其中的消息转发模型抽象为两参与者之间的合作博弈，采用纳什均衡找出节点间交换的内容.Zhu等人[6]提出了iTrust机制.在假定存在自私节点的前提下，引入Trust Authority(TA).TA能够基于先前的路由信息和概率路由判断节点是否存在自私行为.Zhong等人在文献[7]提出一种自私节点激励系统—SPRITE.在系统中，节点向信用清算服务(CCS)上传所收到/转发的消息报告，中继节点转发消息给其他节点时获得信用.文献[8]在邻居节点之间建立单阶段博弈模型基础上进行改进，结合重复博弈理论，提出三种激励自私节点的惩罚机制，并分析各自激励协作转发的条件.Zhang等人研究了一种基于信用的安全激励协议(SIP)，用于模拟MANET的分组协作转发[9].SIP实施信用的收费和奖励计划，在该计划中，移动自组织网络中的节点对其收到的服务进行收费或奖励.文献[10]提出了一种基于信用的集中式独立公平算法—PIFA.该算法鼓励节点通过转发其他数据包来增加积分，并使用该积分生成并转发自己的数据包，这种机制使得节点协同工作，避免自私行为.

上述基于自私节点激励机制的局限性在于：

1)当节点有足够的信用发送自己的数据时，可以决定不再合作并且丢弃数据包；

2)额外路由开销较高，网络性能不稳定；

3)某些情况下忽视了路由中的位置因素问题.因此，本文提出基于Merkle哈希树的节点协作转发(Node Cooperation Forward Based on Merkle Hash-tree，BMTCF) 机制.主要根据节点接受到消息数量利用Merkle哈希树检测是否自私节点，结合节点相遇位置距离预测模型，选择合适的转发节点，保证了节点的协作转发，从而提高了消息投递率，减少了消息传输时延.

3 系统模型及问题描述

3.1 系统模型

如图1所示为机会社会网络应用场景.当节点S与节点D不存在端到端的传输路径前提下，一个源节点S想要发送消息给目标节点D，在这种情况下，消息需要借助与网络中其他节点相遇的机会进行转发.因此，S节点将会从一组邻居节点(例如N1和N4)中选择一个中间节点，使得该消息通过多跳通信最终传输给节点D.假设S选择节点N1，N1又将消息转发给N2，因为没有其他邻居节点可转发.然而节点N2由于存储、能量等资源限制而表现出自私性，丢弃该消息而不是转发给节点D，由于资源限制导致节点表现出的自私行为很难在机会社会网络中被检测到，使得消息传递成功率降低，传输时间延长.

图1 机会社会网络应用场景Fig.1 Opportunity social network application scenario

在具体问题分析之前，首先给出系统模型的相关假设：

1)网络连通图为G=(V，E)，其中V表示网络中节点的集合，并且E={e=(u，v)|u，v∈V}表示链路的集合[11].网络G可由大小为|V|×|V|矩阵A表示，并且A的取值如下：

(1)

2)网络中节点属于理性自私节点，即节点为了获取利益最大化谎报自身信息，而不是谎报其他信息[12,13].

3)对于网络中其他节点除了目标节点之外，节点只有两种选择：转发或丢弃.

3.2 问题描述

机会社会网络节点的移动性常常导致节点的位置信息发生变化[14].为了预测节点的相遇位置，我们根据节点的距离预测和计算模型，首先计算节点移动速度与节点之间距离所成的角度，并预测节点下一时刻的移动位置并计算距离；最后利用Merkle哈希树去检测其存在自私节点，通过节点协作转发机制，选择最佳转发节点完成消息的转发.

3.2.1 相遇距离计算

(2)

(3)

图2 节点移动速度夹角的计算Fig.2 Calculation of angles of the node moving speed

1)平均速度：表示在时间ΔT内节点前一时刻位置与当前位置的距离比值.设节点C的前一时刻位置用坐标(c0x，c0y)表示，当前位置为(cx，cy)同样节点N的前一时刻位置为(n0x，n0y)，当前位置为(nx，ny)，其节点C和节点N的平均速度计算过程如公式(4)和公式(5)所示：

(4)

(5)

(6)

(7)

3.2.2 Merkle哈希树的构建

Merkle哈希树是一种二叉树[15]，它将一组节点映射到一组固定大小的字符串，如图3所示.其中每个叶子节点携带一个给定的值，内部节点包括根节点的值通过两个孩子节点哈希所得到，根据节点所携带的数据包及相遇距离构建Merkle哈希树.

图3 Merkle哈希树的实例Fig.3 An instance of the Merkle Hash tree

图3中η∈{0，…,2H-1}表示该叶子节点所存储的索引值，而H≥1表示Merkle树的高度.节点所存储的哈希值用yh[i]表示，其中h=0，…，H表示树中节点的高度(叶子节点所在高度为0，根节点所在的高度为H)，i=0，…,2H-h-1表示节点从左至右的位置计数.f：(0，1)*→(0，1)n为哈希函数，叶子节点的哈希值由函数f计算，其中表示连接运算，则Merkle树中的非叶子节点哈希值计算如公式(8)所示.

yh+1[i]=f(yh[2i]⊗yh[2i+1])

(8)

假设源节点与目标节点为合法节点，中继节点表现为自私性.Merkle哈希树通过散列消息数量创建树的第一层，散列在第一层节点的值成为叶哈希，每两个叶子哈希配对并散列创建新的哈希值，直到最后创建一个散列值，该节点成为Merkle根节点(y3[0])[20]，如图4所示.

图4 一个包含8个消息数量的Merkle树Fig.4 A perfect complete Merkle tree with 8 messages

在机会社会网络中，Merkle哈希树将用来检验在源节点与目标节点之间转发过程中是否存在消息丢失.如果有一个消息被移除，它的父节点将会改变，一旦父节点改变，将导致整个Merkle树的根哈希值改变.而源节点嵌入Merkle根在每个消息的头部，并通过中间节点发送到目标节点.如图5所示.

图5 嵌入根节点到转发节点Fig.5 Embedded root to forwarding nodes

3.2.3 自私节点检测

为了描述机会社会网络中存在自私节点问题，本文采用所提出的Merkle哈希树对其进行检测.如果目标节点接收到数据包，则通过接收到的数据包进行散列计算新的Merkle根哈希值，然后构建新的Merkle哈希树，利用计算出的新Merkle根哈希值与原始发送的Merkle根哈希值进行比较，如果相等，则表示目标节点接收到正确的数据包数量；反之，则认为在转发的过程中存在自私节点丢失了数据包或者受到攻击等.源节点将Merkle根和数据包一起发送到每个数据包的头部，目标节点接收到数据包，根据算法1来散列计算每个数据包，建立一个Merkle树，并计算一个新的Merkle树根.其步骤如算法1所示.

算法 1.CMR：ComputeMerkleRoot

Input：All node messages

Output：MerkleRoot1

1：hash[i]=creatHash(message[i])

2：For all hashes in each level

3：ifnumber of Hashes=singlethen

4： hash[i]=creatHash(hash[i]+hash[i])/*单个节点与自身节点哈希*/

5：else

6：if!lastHashthen

7： hash[i]=creatHash(hash[i]+hash[i+1])/* 散列每一层节点携带消息数量*/

8：else

9： hash[i]=creatHash(hash[i]+hash[i])

10：endif

11：iflevel=lastthen

12： rootValue=hash[i]

13：endif

14：endif

根据上述算法1计算Merkle根与先前发送的原始Merkle根进行比较，如果相互匹配，则表示目标节点收到正确的数据包；否则，认为目标节点在收到数据包的时候存在自私节点.由于在此阶段，目标节点无法识别出自私节点存在于什么位置，只是对该路径中的任何节点产生怀疑，因此本文结合节点的相遇位置预测模型，将节点的相遇距离加入其中，并结合Merkle哈希树判断并找出自私节点，从而达到消息传输的可靠性.如算法2所示.

算法2.DSP：DetectSelfishnodePath

Input：MerkleRoot，hashes[level]

Output：Selfish node path

1：ifMerkleRoot1=MerkleRootthen

2： packets are all legitimate

3：else

4：Path is selfish

5：endif

6： level=level-1

7：ifhash[level，hashLoc]= hash0[level，hashLoc]then

8：All packets that below this hash are legitimate(left side)/*左子树存在自私节点*/

9： update hashLoc()

10：endif

11：ifhash0[level，hashLoc]+hash[level，hashLoc+1]=hash[level+1，hashLoc]

12：then

13：All packets that below this hash are legitimate(right side)//右子树存在自私节点

14： update hashLoc()

15：endif

3.2.4 节点协作转发过程

机会社会网络不依赖于固定的网络基础设施，每个节点充当路由器角色，所有的节点要想正常通信，需要依赖于节点的分布式协作来完成[17,18].而非相邻的节点间通信依靠中间节点建立路由链路并转发数据，节点间的协作效果会直接影响到网络性能.

为了提高节点的消息转发效率，在自私节点的检测基础上，文中提出了一种基于Merkle哈希树的协作的转发机制(BMTCF).节点协作转发流程图如图6所示，首先根据节点的相遇距离建立路径哈希表，由建立的Merkle哈希树判断节点是否存在自私节点，如果存在自私节点，检测自私节点所在的路径，将该自私节点删除并根据相遇距离大小选择转发节点，如果当前节点为非自私节点，则遍历当前节点的邻居节点，直至将消息转发给目标节点，最后输出最佳路径.

图6 节点协作转发流程图Fig.6 Node cooperation forwarding flow chart

3.3 算法性能分析

针对上述提出的模型，对提出的算法进行性能分析，由于该算法主要针对机会社会网络中的自私节点，构建Merkle哈希树，其次对构建的Merkle哈希树的节点进行行为检测，最后根据节点的自私行为，选择合适的转发路径.其时间复杂度为O(n2).

4 仿真实验与结果分析

4.1 模拟环境设置

为了检测节点自私性对机会社会网络路由的影响，采用了ONE1.4.0(Opportunistic Network Environment)[16]仿真环境平台，通过该模拟器来评估提出的模型和算法的正确性和有效性.本文提出的算法BMTCF和先前的路由算法Epidemic、DirectDelivery进行对比.具体参数设置如表1所示.

4.2 仿真结果分析

将本文算法与对比算法在自私节点检测准确度、平均端到端时延以及消息投递率三个方面进行比较.分别介绍三个指标的定义.

表1 基本参数设置Table 1 Parameter setting

1)检测精确度(Detection Accuracy，DA)：正确检测到的自私节点总数与实际自私节点总数之比[19].如公式(9).

(9)

2)平均端到端时延(Average End-to-End Delay，AED)：它代表数据包达到目的地所花费的平均时间.其中包括所有在路由获取和中间节点缓存期间引起的时延，只有当数据包已成功到达目的地开始计数.如公式(10).

(10)

3)消息投递率(Message Delivery Ratio，MDR)：表示目标节点收到的消息总数与网络中源节点所发送消息总数之比[22].如公式(11)所示.

(11)

4.2.1 不同自私节点数量下对检测准确度的影响

在仿真场景中，假设源节点为非自私节点并且生成消息，将该消息转发给邻居节点.邻居节点可能是自私的或者合法的，但是当合法节点执行该算法时，需要区分节点是否存在自私性.图7为节点在不同时间下采用该算法检测出的自私节点精确度.

图7 不同比率的自私节点对检测精确度的影响Fig.7 Influence of selfish node DA in different ratios

从图7可看出，含有10%的自私节点，在模拟仿真1小时精确度最高达到80%，2小时精确度达到89%及3小时精确度达到95%.当邻居节点有90%自私时，仿真时间为1小时的最低精确度为58%，仿真时间为2小时的最低精确度为69%，而仿真时间为3小时的最低精确度为78%.因此，当自私节点数量越少，自私节点在检测路径上重复的机会越多，精确度也越高.相反，自私节点数量越多，并且大多数都是自私节点时，自私节点所在的路径数量增加，精确度降低.随着模拟时间的增加，采用文中所提出的算法使得拥有良好的路径机会越多，评估的精确度越高.

4.2.2 不同缓存空间对节点消息传输的影响

由于在机会社会网络中，节点所携带的消息数量受到节点缓存空间的限制，节点自身的缓存空间有限，存在消息丢失，从而导致节点存在自私行为，使得节点消息传输时延及跳数也增加.如图8(a)所示.

图8(a)表示随着节点缓存空间的增加，三种算法的消息传输时延的变化规律，由图中可以看出本文提出的算法BMTCF低于DirectDelivery，主要原因在于基于相遇位置的预测模型会带来与目标节点相遇的机会，并减少转发盲目性.同时基于提出的模型，可以选择合适的中继节点进行消息的转发.

图8 不同缓存空间大小对消息传输时延及投递率的影响Fig.8 Influence of AED & MDR different buffsizes

图8(b)表示缓存空间对于消息投递率的影响，尽管三种算法在每个缓存空间大小增加时，消息投递率都呈现上升趋势.在Epidemic算法中，由于消息存储在节点缓存区很长一段时间，当缓存区空间溢出时，导致消息无法转发[21].而在DirectDelivery算法中，由于节点缺少协作，消息又在遇到目标节点才转发，因此消息投递率会较低.而对于提出的BMTCF算法，通过利用节点协作，转发到目标节点的消息数量也增加，从而提高了消息投递率.

4.2.3 不同节点个数对节点消息传输的影响

由于网络节点存在自私行为，采取不同的节点个数进行检测，会导致消息的传输时延有所差距.

图9(a)表明，与DirectDelivery路由算法相比，随着节点数量的增加，本文提出的BMTCF算法在消息平均时延方面有所下降.原因在于随着节点数量的增加，节点之间的相遇概率也会增加，因此，节点的消息平均时延将会缩短.当节点数量少于40个时，由于网络节点密度过大，网络资源有限，消息的平均时延上升.

图9 不同节点个数下对消息传输时延及投递率的影响Fig.9 Influence of AED & MDR different node numbers

在消息投递率方面，图9(b)表示通过对比先前的两种算法，本文提出的算法明显高于Epidemic、DirectDelivery算法，但由于网络中存在自私节点，在Epidemic算法中，由于没有提出检测策略，自私节点拒绝转发，从而导致消息被丢弃.对于DirectDelivery算法，投递率最差的原因在于节点在遇到目标节点才发送消息.当节点个数增加时，BMTCF算法的消息投递率高于其他两种算法，这是因为通过节点协作机制，选择最佳节点作为转发节点，因此在仿真过程能取得较高的消息投递率.

5 结 论

本文主要针对机会社会网络中存在的自私节点进行研究，基于节点相遇位置预测模型构建Merkle哈希树，并对自私节点进行检测.通过节点位置预测模型和计算节点之间的距离选择合适的转发节点，保证节点之间的协作转发.此外，并验证了提出的模型和算法的正确性及有效性，以及仿真实验结果证明了所提出的算法(BMTCF)在消息传输时延及消息投递率两种指标下对比传统的算法有了显著的提高.