机会社会网络概念的提出，可以摆脱由于建立端到端通信路径以实现网络通信而产生的局限性[1]，该概念被广泛应用于野生动物追踪和车载网络等领域[2-3]．机会社会网络通常以存储-携带-转发的路由模式实现节点间的通信．该路由模式依赖于节点移动来实现，并通过节点移动产生的相遇机会实现逐跳通信[4]．机会社会网络无须提前确定下一跳转发节点，而是确定多个潜在的中继节点，选择最佳的中继节点来转发数据[5-6]．在机会社会网络中，节点由人类所携带的可移动设备组成，因此每个节点都具有大量的社会属性[7]．根据节点的社会属性可以获得节点间的社会关系，利用节点间的社会关系进行路由算法设计可以协助消息进行转发，提高网络的性能．目前大多数学者利用节点的相遇次数、交互记录和持续接触时间等指标来衡量节点间的社会关系．若两个节点接触频繁，则认为这两个节点的社会关系紧密．文献[8-9]提出利用节点的接触频率来识别节点间的社会关系，认为朋友之间有固定的互动活动，并在此基础上设计了一种基于朋友关系的转发策略．文献[10]利用地理位置和社会关系设计了几种新的地理社会指标，并使用这些指标选择与目的节点有密切关系及地理位置接近的节点作为中继节点．文献[11]提出了社会关系机会路由算法(SROR)，该算法通过节点的相遇概率和物理社会关系来评估网络中的社会关系，并以社会关系和配置文件为关键指标来选择中继节点，以优化路由性能．文献[12]提出了一种节点社会关系评价算法，通过分析节点的社会属性来量化节点的社会关系，从而选择可信的合作节点进行数据转发．该算法具有较高的传输成功率和较低的传输时延．在基于社会关系的路由机制中，关键问题是发现和量化节点间的社会关系．节点间的特征可以用作量化节点社会关系的指标，但现有的一些研究仅分析一部分特征，没有充分考虑影响社会关系量化的决策特征属性，认为社会关系是静态的，没有考虑社会关系的动态变化．本研究利用社会关系的研究成果，分析移动节点社会关系特征，提取了相似特征属性S、交互质量特征属性E、推荐特征属性R及可靠特征属性H，以研究移动节点间社会关系的动态变化．并结合信息熵和特征选择方法，提出了一种节点社会衡量算法，进而基于社会关系选择最佳的中继节点．1 节点社会关系衡量算法综合考虑影响社会关系的各种特征，定义了多种决策特征属性(如S，E，R和H)．从不同角度描述了节点社会关系的多样性、社会性、不确定性和传递性．根据节点的决策特征属性筛选可用的节点，计算出它们的社会关系值．1.1　节点的多维决策属性定义1 节点u和节点v之间的社会关系评估值A(u,v)为A(u,v)=∑i=1nqiai(u,v)(∑i=1nqi=1,0≤qi≤1;u,v∈N), (1)式中：qi为不同社会属性的权重；ai为不同类型的社会属性；n为社会属性的总数；N为网络中节点的总数．若A(u,v)=0，则节点u和节点v之间没有任何关系；若A(u,v)=1，则节点u和节点v是同一个节点．在机会社会网络中，节点间的交互模型反映了节点间的社会相似度．社会相似度可以评估节点间的相似程度，相似程度越高的节点彼此之间的联系越紧密，具有一定的社会关系．因此，相似特征属性可以协助衡量节点间的社会关系．定义2 网络中的两个节点u和v，节点u可以传递资源到节点v，在此过程中它们的邻居节点充当资源传递中的媒介．设节点u的邻居节点集为φ(u)，节点v的邻居节点集为φ(v)．则节点u和节点v之间的相似特征属性为S(u,v)=[φ(u)⋂φ(v)]/[φ(u)⋃φ(v)]，(2)式中：φ(u)⋂φ(v)为节点u和节点v共同邻居的集合；φ(u)⋃φ(v)为节点u和节点v的邻居总和．在机会社会网络中，节点的交互行为是数据产生的基础，交互质量的评价反映了这次交互行为的成败，而交互行为的成败将直接影响交互双方的社会关系．因此，交互质量属性反映了节点社会关系的动态性．定义3 设t时刻节点u对节点v的评价为Et(u,v)，则在最近的b次交互中，节点u对节点v的满意度评价为h={h1(u,v)，h2(u,v)，…，hb(u,v)}，其中，h1(u,v)∈[0,1]，t∈[1,b]，b∈[0,B]．h中的元素按交互的时间顺序排列，若h1(u,v)为最远的一次交互，则节点u对节点v的交互质量特征属性为Et(u,v)=μ∑i=1bhi(u,v)θ(t)/B-f(u,v)，(3)式中：μ为控制因子，调节历史满意度对这次交互质量评价的影响；B为最大有效历史交互次数；θ(t)为交互质量随时间变化的衰减函数，其定义为θ(t)=1    (Δt=0),1/(tnew-t)1/∂=1/Δt1/∂    (Δt≠0), (4)其中，Δt为交互对象过去的一次交互时间t和本次交互时间tnew的间隔，∂为控制因子．当节点u对节点v间的交互存在恶意欺骗时，对恶意实体进行惩罚，惩罚函数为f(u,v)=k/(γb'), (5)式中：k为节点v的恶意次数；b'≤B为节点u对节点v的所有直接交互次数；γ为调节因子，用于控制惩罚的程度．在机会社会网络中，节点的社会关系具有传递性，可以通过其他节点的推荐信息间接计算节点的社会关系值，这便是推荐过程．推荐过程根据其他节点对目标节点的推荐信息间接计算不同推荐者对目标节点的社会关系值．由于各个推荐者所在的层级不同及距离目标节点的跳数不同，因此本研究使用加权函数来计算推荐属性．定义4 设推荐者的集合为{r1,r2,⋯,rj}，A(rj,rj+1)为推荐链路上rj对直接后继rj+1的社会关系值，则节点u和节点v推荐特征属性可以表示为R(u,v)=0    (l=0) ;∑j=1n(μ(rj+1)A(rj,rj+1))/∑j=2lμ(rj)    (l≥1), (6)式中：l为推荐者的个数；μ(rj)为推荐链路衰减度函数，有μ(rj)=1    (L=0),∏i=1Lτ(ei,esuc)    (L≥1), (7)其中，τ(ei,esuc)为从源节点u到目标节点v社会关系的推荐链路上节点ei与其后继节点esuc的社会关系值，L为推荐链路中推荐者距离目标节点的跳数．如果机会社会网络中有许多自私节点，那么当自私节点充当中间节点转发数据时，它们很有可能会丢弃接收到的消息，成功传输速率将会下降．为此应该在网络中寻找可靠节点进行消息传输，这能够有效激发节点之间更多的合作意愿．为了计算节点之间的可靠性，定义可靠的三个维度(连通性、适应性和稳定性)，采用加权法来计算可靠属性．定义5 源节点和其邻居节点之间的可靠性可以根据社交功能来计算，它可以包括节点连通性、节点适应性和节点稳定性．a. 节点连通性节点连通性用来衡量一个节点连接另一个节点的能力，可以通过节点间的连接频率来计算节点连通性．节点间的连接频率越高，节点的连通性就越好．节点连通性计算公式为M(u,v)=(g+2w)/(g+2w+ω¯), (8)式中：g为节点u和节点v连接的次数；w为节点v在转发路径中作为中间节点的次数；ω¯为网络中节点的总数．b. 节点适应性节点适应性可以用来判断一个节点是否可以成为正常节点，阻止那些自私节点和恶意节点加入网络．节点适应性基于直接交互记录和转发路径，其中转发路径包括源节点与中间节点．节点适应性计算公式为F(u,v)=(q+r1+1)/(q+r1+d+r2+2), (9)式中：q为节点v转发的消息数；r1为节点v接收节点u的消息数；d为拒绝消息的数量；r2为节点v作为源节点传递的消息数．c. 节点稳定性节点稳定性表示节点之间的连接时间比例．连接时间显示两个节点可以传输消息的时间，会影响转发节点的性能．节点的连接时间越长，节点的稳定度就越好．节点稳定性计算公式为Wu,v(t)=Tu,v(t)/∑i=1nTu,i(t)，(10)式中：Tu,v(t)为节点u和节点v的连接时间；∑i=1nTu,i(t)为节点u和其邻居节点连接时间总和．使用连通性、适应性和稳定性三个维度定义节点u到其邻居节点v的可靠特征属性为G(u,v)=αM(u,v)+βF(u,v)+χWu,v(t)，(11)式中α,β,χ∈[0,1]为三个指标的权重比，且有α+β+χ=1．1.2　决策属性权重分布在衡量社会关系的过程中，权重的大小可以反映节点社会关系中每个决策属性的状态，从而决定最佳中继节点的选择，影响信息传输成功率．粗糙集理论是处理知识不确定性的工具．使用C表示待分类对象的实类，X1,X2,⋯,XT表示网络中每个节点的T个特征，Xτ(1),Xτ(2),⋯,Xτ(k)表示k个已经选择的特征．所有特征估计都是基于网络中的节点，N个节点可以表示为ξ={(x(1),c(1))，(x(2),c(2))，…，(x(N),c(N))}，其中x(t)为t个节点，xi(t)为第t个节点的第i个特征，xi为特征i在节点的值．定义6 随机变量的不确定性可以由信息熵[13]来表示，信息熵的定义为H(Xi)=-∑xi∈Xip(xi)log2 p(xi)，式中p(xi)为输出概率函数．xi的不确定性越大，信息熵也就越大．两个变量的联合概率可以表示为H(Xi,Xj)=-∑xi∈Xi,xj∈Xjp(xi,xj)log2 p(xi,xj)．定义7 交互信息和条件交互信息的估计可以通过变量的熵进行加和减来完成，交互信息定义为I(C;Xi)=H(C)+H(Xi)-H(C,Xi)，(12)式中I(C;Xi)为交互信息，即一个随机变量中关于另一个随机变量的信息量．I(C;Xi|Xj)=H(C|Xj)-H(C|Xi,Xj)=H(C,Xj)-H(Xj)-H(C,Xi,Xj)+H(Xi,Xj),式中：H(C|Xj)为已知特征Xj的条件下信息C的条件熵；H(Xi,Xj)为联合熵．对于每个选择的特征Xi，当I(C;Xi|Xj)的值都保持较大值时，特征Xi较好，说明特征Xi携带关于C的信息并且这个信息没有被其他特征携带过．如果特征Xi未携带关于C的信息或者Xi已经捕获此信息，那么I(C;Xi|Xj)保持较低值．基于前面的定义，则有：τ(1)=argmaxiI(C;Xi)；τ(K+1)=argmaxi{mina≤kI(C;Xi|Xτ(a))}⏟s(i,k)，式中τ(1),τ(2),⋯,τ(K+1)为选择的一部分特征子集．这些子集可以携带尽可能多的信息，最终目标是使选中的τ(1),τ(2),⋯,τ(K+1)最小化H(C|Xτ(1),Xτ(2),⋯,Xτ(K))．若选择的特征至少有一个与Xi相似或者Xi完全不能提供信息，则分数s(i,k)的值较低．特征Xi最大化分数s(i,k)可以确保新特征携带信息C和之前的特征相比也是完全不同的．1.3　算法步骤节点社会关系衡量算法研究社会关系的动态性，计算影响社会关系的决策特征，结合信息熵和特征选择为决策特征赋予权重，进而衡量节点的社会关系，结合概率模型计算节点的综合指标，选择综合指标高的节点作为转发节点，具体过程如下．a. 输入移动节点的相关信息，包括相似信息、交互质量信息、推荐信息和可靠信息等．b. 根据式(2)~(11)计算移动节点决策属性，即S,E,R和G．c. 根据式(12)计算每个特征的交互信息I(C;Xi)并保存在s[i]中，s[i]包含每个特征Xi的分数．在选择τ(a)个特征后，分数s[i]=mina≤kI(C;Xi|Xτ(a))代表交互信息中的最小值，分数由值I(C;Xi)来初始化．使用p[i]表示包含计算s[n]时所考虑的最后一个特征索引，初始化为0．d. 在每次迭代中，算法遍历所有候选项，选择最高分数的特征τ(a)．在当前迭代中找到的最佳候选项不是更好的情况下才更新其分数，只有更新时分数才会下降．算法遍历所有候选特征，如果该候选特征的分数高于最新的最佳分数s，那么才会更新分数p[i]，同时最小化I(C;Xi|Xτ(a))．e. 如果分数s[i]大于当前最佳分数s，那么使用s[i]来更新s．f. 重复进行迭代直至选择K个特征为止，其中每个选择的特征分数会保存在m[k]中．g. 根据特征属性的可信度值，计算各特征属性的权重．决策属性的权重分配公式为ηk=m[k]/∑k=1Km[k]    (k=1,2,⋯,K)．h. 根据式(1)计算移动节点社会关系值A，最终输出社会关系值．2 实验分析采用开源仿真工具机会网络环境(ONE)对提出的算法进行仿真．该工具可以通过控制节点的移动来获得节点的运动轨迹，进而记录信息传输过程中的各种细节．在仿真实验中，将NSRM算法与Epidemic[14]，Spray and Wait[15]以及MaxProp[16]路由算法进行比较．用于评估机会社会网络中路由算法的度量参数如下．a. 传输成功率表示传递消息时选择相关性节点的可能性．b. 路由开销表示两个节点之间传输数据的平均路由成本．c. 平均传输时延表示两个节点之间传输数据的平均延迟时间．实验使用的模拟参数详细信息为：模拟时间为1～6 h，模拟的区域面积为1 070 m×810 m，涉及的节点数为300，节点的缓存设置为5～40 Mib．节点的传输模式是一种社交模型，其中每个节点的缓存为8 Mib，每个节点可以传输的最大面积为10 m2，频率为25～35 Hz，数据包类型为随机数组．图1显示了传输成功率(Dm)和模拟时间(tm)之间的关系．Epidemic算法的增长幅度最小，该算法的每个节点都携带大量的数据，当节点的缓存较小时，会造成数据的大量丢失，影响传输成功率．Spray and Wait算法指定每份报文信息允许拷贝的最大数量，减少了信息拷贝的次数，提高了传输成功率．MaxProp算法通过存储中介节点的列表来防止数据向同一节点传播两次，避免了节点盲目复制消息而导致的资源浪费，进而提高传输成功率．NSRM算法的传输成功率最高，该算法考虑了社会关系的动态性，有助于选择最佳的中继节点转发数据，从而减少消息复制的数量，提高传输成功率．10.13245/j.hust.210212.F001图1传输成功率和模拟时间之间的关系图2显示了路由开销(Om)和模拟时间之间的关系．NSRM算法通过衡量节点的社会关系来选择最佳的中继节点传输数据，传输数据的中继节点数趋于稳定，因此路由开销可以保持稳定．Spray and Wait算法指定每份报文信息允许拷贝的最大数量，有效减少了信息拷贝次数，同时减少了路由开销．Epidemic算法的路由开销最大，该算法的每个节点都和遇到的邻居节点交换数据包，增加了网络中消息副本的数量．随着模拟时间和节点数量的增加，路由开销急剧增加，网络性能下降．10.13245/j.hust.210212.F002图2路由开销和模拟时间之间的关系图3显示了传输延迟(Lm)和模拟时间之间的关系．MaxProp算法的传输延迟最高，它根据传输成本确定数据包的优先级，每一次消息的传输都须要估算传输成本．Epidemic算法的传输延迟较高，算法中的每个节点都将和其相遇的邻居节点交换数据包，导致网络中存在大量的消息副本．Spray and Wait算法具有较低的传输延迟，它指定每份报文信息允许拷贝的最大数量，减少了消息复制的数量，降低了传输延迟．NSRM算法的传输延迟最低，它在选择中继节点时占用了网路资源，导致传输延迟，而随着时间的增加，传输延迟趋于稳定．10.13245/j.hust.210212.F003图3传输延迟与模拟时间之间的关系图4显示了传输成功率和节点缓存(Rm)之间的关系．在所有算法中，NSRM算法的传输成功率最高，它通过衡量节点的社会关系来选择最佳中继节点，缓存大小对该算法的影响不大．MaxProp算法和Spray and Wait算法类似，传输成功率随缓存的增加而提高，当缓存达到一定值后，传输成功率趋于稳定．Epidemic算法的本质是泛洪算法，节点之间交换彼此缺少的数据包，数据包占节点缓存较大，因此随着缓存的增加，可以传输的数据增加，传输成功率得到提高．10.13245/j.hust.210212.F004图4传输成功率与节点缓存之间的关系图5显示了路由开销和节点缓存之间的关系．Epidemic算法的路由开销受缓存的影响较大，随着缓存的增加，节点可以携带的数据包增加，减少了网络拥塞，从而减少了路由开销．NSRM算法和Spray and Wait算法类似，路由开销随着节点缓存的增加而减少，最后趋于稳定．NSRM算法在选择中继节点的过程中会消耗网路资源，但是总体的路由开销较低．Spry and Wait算法指定每份报文信息允许拷贝的最大数量，减少了网络中的数据传输量，因此路由开销较低．10.13245/j.hust.210212.F005图5路由开销和节点缓存之间的关系图6显示了传输延迟和节点缓存之间的关系．Epidemic算法的节点之间交换彼此缺少的数据包，当节点缓存增加时，节点可以携带的数据包增加，网络中的信息报文增加，造成传输延迟．Spray and Wait算法的传输延迟高于NSRM算法，这是由于Spray and Wait算法随机选择节点传输数据，而NSRM算法通过衡量节点的社会关系来选择最佳的中继节点传输数据，使数据一直沿着中继节点进行传输，其可达性更高．10.13245/j.hust.210212.F006图6传输延迟和节点缓存之间的关系3 结语本研究提出了一种机会社会网络中基于社会关系的传输机制，即节点社会关系衡量算法(NSRM)．该算法研究节点社会关系的动态性和可及性，从节点处获取的原始特征信息提取节点的相似特征、交互质量特征和可靠特征作为决策属性，并利用决策属性来衡量节点的社会关系．引入了信息熵和特征选择的方法，结合节点社会关系的动态性和可及性，动态地为不同属性分配权重，进而选择最佳的中继节点转发数据，一定程度上提高了数据传输效率，减少了路由开销和传输延迟．