机会网络是一种不要求网络全连通、容延容断的网络^[1]。整个网络不需要发送端节点和接收端节点有完整的链路，而是通过节点的移动创造节点的相遇机会，从而实现网络通信。如今移动设备的普及使得网络中通信节点一定程度上代表了人类活动的社会性，利用社会网络有助于该类网络路由算法的设计实现，这类网络被称为社会机会网络。社会机会网络大多利用中继节点与目的节点之间接触信息、节点上下文信息（能量、移动速度、邻居变化及位置等）、节点之间社会关系、节点的社会地位^[2−4]，网络中各节点分享各自历史消息，从而预测未来与目的节点相遇机会。

由于社会机会网络是基于社会网络分析方法提出的^[5−6]，网络中节点大多代表人类活动，在实际社会活动中用户不会希望社会关系隐私信息暴露在网络中，但网络路由需要利用各用户隐私信息完成决策。本文针对此矛盾，设计了基于局部敏感哈希（locality-sensitive Hashing）计算方式^[7]加密用户隐私背景信息，保证用户隐私安全性；同时由于加密后数据相似度与原始数据相似度一致^[8−9]，从而公开各自加密信息表就可以比对任意两用户的社会背景相似度，保证了路由的正常性能。

节点社会背景信息进行转发判决的路由协议在近些年来得到极大的发展^[10−12]，研究人员根据不同的社会背景和环境条件制定不同的判决条件。Bubble rap^[13]、Simbet^[14]、Propicman^[15]等经典的社会机会网络路由中，通过收集历史社区、习惯、兴趣等信息判断节点与目的节点相似性从而预测未来的相遇机会。但社会机会网络协议的设计只考虑如何正确有效地完成路由，而忽略了用户隐私信息暴露的问题。针对社会网络隐私保护方法主要分为基于数据失真技术、基于数据限制发布技术、基于数据加密技术等方法^[16−17]。在数据失真技术方面，Parris等^[18]通过采用修改模糊朋友列表的方式保护用户的隐私，通过加入不实信息模糊隐私列表。为了完全保护隐私信息，需要在机会网络中引入加密机制，从而大量地研究提出将公钥加密（public key infrastructure，PKI）机制引入机会网络中：一种基于关键字可搜索的公钥加密研究^[19]、身份密码学（identity-based cryptography，IBC）的密钥管理方案^[20]等，该类方案通过引入身份密码学算法中陷门机制，使得交互双方可以计算加密信息的相似度。但难点在于PKI类密钥机制需要网络中存在可信第三方机构提供密钥的分配和证书的发放，显然应用在分布式的机会网络中很难实现。在之前研究基础上，Zhou^[21]提出分布式的密钥管理，网络中每个节点均平等不存在第三方机构，通过门限算法分配私钥，但这种机制有一个隐藏的前提：大多数节点之间必然存在一条路径，这显然与机会网络基础意义相背。此外更有许多自组织密钥管理体系，但是很容易受到破坏，安全隐患很大。

在PKI类加密机制很难实现的前提下，为了简化加密算法，Nguyen等^[22]在提出利用单一哈希运算加密用户的信息表格完成对用户隐私的保护。哈希算法的计算开销较小，对网络性能影响较小，但此方案中由于单一哈希运算将信息表中信息逐一加密，用户信息极容易受到字典攻击。Parris等^[23]通过引入多组真实数据集分析社会机会网络，并加入大数据集合查找算法Bloom-Filter来处理节点的朋友列表，建立可靠的隐私保护模型，但Bloom-Filter本质也是基于哈希算法的快速查找算法，列表信息逐条加密易遭受逆向攻击。

本文提出一种保护社会机会网络中节点社会关系隐私保护方案。基于目前社会机会网络隐私保护方案，并运用于SRSNs（自我报告型社会网络协议，self-reported social networks）路由协议中，解决社会机会网络中用户隐私泄露的问题。加密后的社会信息，通过比对签名数据相似性来代替原始数据相似性，从而完成路由判决，避免了公钥机制中密钥的分发困难和简单哈希运算易被字典攻击破解的问题。最后，通过隐私保护方案在社会机会网络中的应用，在真实数据集SASSY的基础上完成仿真。

1 局部敏感哈希算法

局部敏感哈希算法本身是一种对数据进行快速相似性检索算法，根据数据位置敏感特性完成哈希运算。

定义1　设距离r₂>r₁>0，p₁、p₂为Hash函数H={h|h:R^d→U}的返回概率，U为映射后的集合。若称H={h|h:R^d→U} 是（r₁，r₂，p₁，p₂）敏感的，点p，q∈R^d，则：

1）点D(q, p>r₁)，则P[h(q)=h(p)]≥p₁;

2）点D(q, p<r₂)，则P[h(q=h(p)]≤p₂。

D(q, p)为2个多维对象的相异程度，当相似性满足条件时，两对象可有较大概率放到同一个哈希桶，映射为同一Hash值；而当相似性低时，有极低的概率映射为同一Hash值。

simhash是局部敏感哈希算法实现中的一种。对比单一的Hash加密运算，simhash的主要思想是降维运算，将多维的文档信息映射成唯一的标识。并且传统的Hash加密需要保证较低的碰撞率，使得相似内容的Hash值不具有任何联系，而simhash运算利用哈希碰撞的原理，使得相似的文档会生成相似的simhash值，可以利用其安全计算数据相似度特性设计符合机会网络的安全隐私算法。simhash算法基础原理基于局部敏感哈希算法，加入了分词和权重数据处理，使得整个算法更加精确实用。

2 局部敏感哈希隐私保护实现

本文所述的隐私保护方案所应用的社会机会网络协议为Parris等所提出的社会机会网络路由协议中SRSNs(self-reported social networks)协议。并在该协议基础上，利用上文所述局部敏感哈希算法对网络中节点的朋友列表进行加密处理：对于各节点公开的朋友列表进行加密处理；对不同亲密度朋友做权值分配处理。节点在网络中公开自身朋友列表simhash值。

2.1 基于朋友列表的SRSNs路由协议

在社会机会网络协议中，若以协议采用的数据是统计数据或是真实数据，则机会网络协议类型分为DSNs(外部信息探测型社会网络协议，detected social networks)及SRSNs两类。

1）DSNs协议：根据设备记录的历史相遇信息，统计效用值，从而分析节点的社会关系，也称接触网络，例如Bubble Rap、SimBetS等。

2）SRSNs协议：由用户自主记录社交关系信息，以表明他们的社会关系。例如facebook上记录的朋友关系，主要利用朋友间比陌生节点间更有可能相遇的原理。

由于加入了用户的真实信息，SRSNs相比DSNs更能有效地在仿真中反映现实实际情况。而DSNs中由于不同协议对收集到的历史信息利用的算法不同，而达到的效果不一。我们根据SASSY数据集中各用户facebook中提供的朋友关系构建其m维朋友列表，则节点A朋友信息表可以定义为：

$ {F_A} = \left( {{a_1},{a_2}, \cdots ,{a_m}} \right), $

式中a_i∈[1,m]为整数，表示节点A的朋友空间中第i维向量的权值。在SASSY数据集下，采用SRSNs和DSNs构建的社会关系网会有所不同。相遇的节点不一定是朋友关系，DSNs根据相遇历史信息构建了更复杂的社会关系网。

本文在Parris等所提出基于SASSY数据集的SRSNs协议基础上进行进一步工作。他们在实验中只考虑了中继节点、目的节点均为源节点朋友的情况，整个网络消息的传递也仅限于朋友关系单线传递。但在大多数社会机会网络中，希望消息的传递不限于朋友，而是可以更大范围的交互传递，源节点产生的消息可以有效地传输到网络中任意节点。因此本文采用文献[23]中所用的SRSNs协议，源节点可以向网络任意节点传输消息，而消息向与目的节点相遇概率更大的节点传输。若S为一个消息源节点，假设S已知目的节点D及其朋友关系，则S产生的消息M一定要向集合C中的节点传递。

$ C\left( {S,U} \right) = \left\{ {U \in N|{\rm{sim}}\left( {U,D} \right) > {\rm{sim}}\left( {S,D} \right)} \right\} $

(1)

式中：sim(,)表示2节点之间朋友列表相似度，相似度越高则代表有更多相同的朋友，即社会关系重合度高；集合C称为理想中继节点集，原则上S节点无法预先知道该集合的具体信息，判断任意节点是否属于集合C，需要网络中节点公开朋友列表从而进行分析判决。

SRSNs协议中各节点与相遇节点分享朋友列表，分别对比与目的节点朋友列表相似度，完成是否传输消息的决策。朋友列表与目的节点朋友列表相似度越大，则与目的节点相遇概率越大。

1）节点n_i与节点n_j相遇分享各自朋友列表。

节点朋友信息表构造如图1，读取自facebook数据。

2）在社会网络规律中，朋友间接触比较频繁而陌生人间的接触偏少。因此假设目的节点朋友列表已知的前提下，在社会机会网络中节点应将消息向与目的节点社会关系更密切的节点传输，相同朋友越多则社会关系越密切。

路由决策：当节点n_i与节点n_j相遇时，若n_j为目的节点朋友，n_i为非目的节点朋友（n_i此时必为源节点），则n_i将目的节点消息传输给n_j；若节点n_i与节点n_j均为目的节点朋友，则进行社会关系值sim(n_i,D)计算。社会关系值为节点n_i与目的节点朋友列表相似度，相似性可用Jaccard系数计算：

${\rm{sim}}\left( {{n_i},D} \right) = J\left( {C\left( {{F_{{n_i}}}} \right),C\left( {{F_D}} \right)} \right) = \frac{{\left| {\left. {C\left( {{F_{{n_i}}}} \right)\mathop \cap \nolimits C({F_D}} \right)} \right|}}{{\left| {\left. {C\left( {{F_{{n_i}}}} \right)\mathop \cup \nolimits C({F_D}} \right)} \right|}}$

分别计算两相遇节点与目的节点的社会关系值，根据式（1），消息流向C(n_i,n_j)集合。

2.2 simhash算法隐私保护方案

对于SRSNs类协议中用户隐私保护方案，Parris等^[24]提出模糊型隐私保护协议(obfuscated social network routing，OSRN)及数据修改型隐私保护协议 (statisticulated social network routing，SSRN)这2种隐私保护方案。本文提出使用simhash算法的simSRN方案来处理朋友列表以达到保护用户隐私及计算朋友相似度的目的。simhash算法是更加贴近实际应用的一种局部敏感哈希加密算法^[25]，对于社会机会网络中节点的朋友列表，每个朋友的亲密关系均不相同，代表的权值也不同。运用simhash算法可以更全面反映用户的朋友关系，朋友列表中元素的顺序也将影响最终的朋友列表的签名值。simhash算法可以将信息表整体进行加密运算并且对比两信息表相似度，解决了对信息表中各元素逐一加密并检索的繁琐和易被字典攻击的问题。

社会机会网络中，节点n_i的朋友列表可根据数据集中各节点的facebook通讯录、手机通讯录收集。 ${n_m},\cdot\cdot\cdot,{n_a},\cdot\cdot\cdot,{n_x}$ 为节点n_i的通讯录联络人，即为节点n_i朋友。对于本文中朋友的权值为朋友亲密程度，基于信息表生成simhash签名步骤如下：

1）对于节点n_i的m维朋友信息表F_ni是按照朋友的关系程度顺序排列的，则依序为F_ni中的各节点取权值 $\left\{ {1,2,\cdot\cdot\cdot,m} \right\}$ 。

2）为了保护朋友列表信息隐私，对F_ni使用K维哈希函数，本文使用FNV哈希算法，Hash的位数采用64位。不同的哈希算法会产生不同位数的Hash值，位数越多最后匹配结果越精确。

3）将一个f维的向量 $ \left. {{V}({v_1},{v_2},\cdot\cdot\cdot,{v_{{f}}}} \right) $ 初始化；f位的二进制数B初始化为0；

4）将步骤2）中各元素Hash值映射到f维的向量 $\left. {{V}({v_1},{v_2},\cdot\cdot\cdot,{v_{{f}}}} \right) $ ，对每一个特征，用哈希算法对该特征产生一个f位的签名b_f。

5）对i=1~f，如果b_f的第i位为1，则 $ \left. {{V}({{v}_1},{{v}_2},\cdots,{v_{{f}}}} \right) $ 的第i个元素加上该特征的权重；否则， $\left. {V({v_1},{v_2},\cdots,{v_{{f}}}} \right)$ 的第i个元素减去该特征的权重。如果 $\left. {{V}({v_1},{v_2},\cdots,{v_{{f}}}} \right)$ 的第i个元素大于0，则S的第i位为1，否则为0；输出B作为签名。

通过上述步骤将节点n_i的通讯录生成为n位的签名值，将计算通讯录相似度问题转化为比较2个通讯录签名值的问题。

simhash算法由随机超平面算法原理演变而来，其返回概率与余弦相似度有关，即simhash属于 $\left( {{r_1},{r_2},\left( {1 - \displaystyle\frac{{{\rm{co}}{{\rm{s}}^{ - 1}}{r_1}}}{{\rm{\text π}}}} \right),\left( {1 - \displaystyle\frac{{{\rm{co}}{{\rm{s}}^{ - 1}}{r_2}}}{{\rm{\text π}}}} \right)} \right)$ 敏感LSH函数族，simhash可以定义为

$\left. {h_w^{{\rm{sim}}}\left( x \right) = {\rm{sign}}({{w}^{\rm{T}}}x} \right)$

式中w为文档向量。

本文哈希算法使用FNVhash算法，FNVhash属于非加密哈希函数，对比MD5等哈希函数保持较低的碰撞率，比较适合字符串较短的哈希场景。取初始Hash值H_hash，并设置FNV用于散列的质数F_prime。对初始Hash值H_hash进行n位的取模运算：

$ {H_{{\rm{hash}}}} = {2^n}{H_{{\rm{hash}}}}{F_{{\rm{prime}}}}/{\rm{1}}00 $

哈希函数一般适用移位和乘除法来实现，函数一般都比较精简，算法复杂度比较低。哈希函数的移位和乘除法可能会导致数据丢失，这也是哈希不可逆的原因。将朋友列表中每个分词分别生成8位数据字符串O_data，则每个分词通过FNVhash算法得到的Hash值H_value为

$ {H_{{\rm{value}}}} = {H_{{\rm{hash}}}} \oplus {O_{{\rm{data}}}} $

对于朋友列表分词处理，facebook数据中包含了朋友的联系频率。但单独以频率计算各分词的权值无法同等地表述各个节点的朋友关系，因此对于朋友的权值处理以各节点朋友列表大小为极限值，降序赋予各分词的权值

$ \left. {{\rm{weight}}\left( {{n_x}} \right) = i \Leftrightarrow {\rm{if}}({\rm{Friendslist}}.{\rm{get}}\left( i \right) = = {n_x}} \right) $

则n维的节点n_i朋友列表可由向量V = {w₁H_value(1), w₂H_value(2), ··· , w_nH_value(n)}来表示。向量V中各向量累加后可得n位的签名b_f。最终simhash的签名Hash值B由b_f各位比较获得。

社会机会网络中每个节点公开自己的simhash签名，从而代替自身朋友信息列表。此时sim(_i,j)可统计simhash签名相似度，估计i、j节点重要朋友相似度。

两节点相遇时，对比各自签名与目的节点签名的相似程度，最终消息将根据式（1）流入流向 $\left. {C({n_i},{n_j}} \right)$ 集合。此时中间节点n_i与目的节点D相似度，即中间节点与目的节点社会关系强度可以根据二进制数值汉明距d来计算：

$ {\rm{sim}}({n_i},D) = d({B_{{n_i}}},{B_D}) $

2.3 安全性分析

隐私安全方案评价一般注重在信息的损失度和隐私的保密程度。

1）算法可靠性分析

simhash算法在社会机会网络中将原始数据加密成哈希码及签名的形式，通过比对签名的汉明距离从而近似获得原始数据的相似度。

为了分析算法的可靠性，本文采用准确率来说明加密后的数据可以获得与原始数据的相同结果的程度。准确率=正确转发次数/转发总次数。由于加密后的信息进行相似度计算时会丢失一部分信息量，OSRN方案会产生失误判决(false positive)，失误率与列表信息量以及加密位数有关；simSRN将整体信息表降维处理为哈希码也会造成信息的部分丢失，从而导致一定的失误判决。本文同时分析原始数据和加密数据对同一决策的结果，若转发决策结果一致则为正确转发。仿真中使用SASSY数据集，25个节点消息，生存时间（time to live，TTL）时间取一周，仿真时间分别取7、14、21 d，分析simSRN及OSRN方案的决策成功率。隐私保护方案准确率曲线如图2所示。

OSRN方案中Bloom-filter算法中由于存在失误率导致会存在决策错误，失误率为：

$f = {\left( {1 - {{\rm{e}}^{ - kn/m}}} \right)^k} $

式中：m为数组大小；k为哈希函数个数；n为需要插入元素个数。simhash算法存在降维操作，损失了一定信息量对决策判决有所影响，在构建的余弦相似度的超平面局部敏感哈希函数中，2个信息表A，B取同一函数值的概率分布P_a,b满足：

$P\left[ {h\left( A \right) = h\left( B \right)} \right] = 1 - \frac{\theta }{{{\text{π}}}}$

式中 $\left. {\theta {\rm{ = co}}{{\rm{s}}^{ - 1}}(\left| {A\mathop \cap \nolimits B} \right|/\sqrt {\left| A \right| \cdot \left| B \right|} } \right)$ 。

2）用户信息隐私安全性分析

原始用户背景信息通过simhash算法加密得到simhash值，即指纹签名。OSRN方案中将朋友列表放入Bloom-filter中进行加密并快速查找计算列表相似度，保护了用户隐私。但由于元素的逐一加密，暴力字典破解攻击只需将字典中元素逐一在加密算法中遍历即可完成破解。而对于simhash降维加密算法，字典攻击则在每次遍历运算中需在字典中任选K维元素全排列进行破解，K为任意数，大大增加了攻击负担。对于大小为n个元素的攻击字典，假设n个元素中包含需被破解的m个朋友列表元素，若Bloom-filter失误率为f，则字典攻击产生的符合元素数为m+nf个，则攻击Bloom-filter算法加密空间时字典攻击次数 $T\left( n \right) = n + C_{m + nf}^m$ ,攻击simhash加密空间的字典攻击次数为 $T\left( n \right) = A_n^m$ 。在实际应用中，字典数n应远远大于m，且对于m数值较小时失误率f极小，可以达到0.01%以下，因此Bloom-filter算法加密空间时，字典攻击的时间复杂度为O(n)，simhash字典攻击的时间复杂度为O(n^m)。

对哈希函数加密运算采用字典碰撞运算时，对于一个n位的哈希函数进行碰撞攻击需要的时间复杂度是O(2ⁿ)，随着位数增长指数大小快速增长，对于现有的技术而言很难在实际应用中实现。

simhash算法由于利用哈希碰撞的原理，使得不同顺序或权值相似信息表序列通过simhash加密获得与隐私信息表相同的签名值，增加了字典攻击的运算负担，有效地抑制了字典攻击。

3 simSRN协议仿真与性能分析

本文在ONE仿真器下对simSRN、SSRN、OSRN及SRSN算法进行仿真和性能对比，为了考察隐私保护方案对网络性能的影响，以SRSN算法性能为基准，通过消息到达率和平均时延这2个指标来衡量网络性能。本次仿真采用SASSY数据集，该数据集是采集圣安德鲁斯大学79 d的数据，实验环境中共有25个节点，各节点为学校学生和教职工，21号至25号为学校教职工及研究生，节点间为蓝牙通信模式。本文采用和文献[21]相同的仿真环境，取数据集中其中30 d的数据，节点的朋友列表取自其各自的facebook数据。仿真参数如表1所示。

根据表1设置参数后，分别对simSRN、SSRN、OSRN及SRSN算法进行仿真。其中，SSRN算法中朋友列表采取随机插入50%节点的处理方式；OSRN方案中Bloom-filter失误率f设置为1%。朋友列表完全采用SASSY数据集中提供的各用户facebook朋友列表，数据集中朋友列表中朋友个数为4~14个，为了提高仿真效率，选取的数据集中的前30 d数据进行仿真。

图3、4中反映出社会机会网络消息的传输到达率随报文生命周期TTL变化情况。SSRN协议的报文转发到达率高于其他3种采用隐私保护方案的协议，网络中用户分享各自朋友列表信息作为辅助时，可以优化网络性能。由于simhash算法计算数据相似性时将整体信息表进行降维加密处理，损失了一定的信息量，因此simSRN算法的报文转发到达率略低于OSRN及SSRN算法，但到达率相比SRSN协议下降不到5%，基本保证了网络的正常性能。simSRN算法的平均时延随TTL的增长速度较快。

综上所述，局部敏感哈希机制运用在机会网络中可以保障网络的正常性能。同时，simSRN方案可以在加密数据后以唯一Hash值来表现原始数据的相似度，避免了其他方案中信息表元素逐一加密，易被字典攻击以及用户隐私信息暴露的问题，在损失较小的网络性能同时，可以将用户隐私信息进行加密，保护用户隐私。

4 结论

通过仿真证实了利用simhash算法进行隐私保护的可行性，并保持了良好的网络性能。

1）simhash算法将隐私信息表进行降维加密处理，与OSRN算法相比更有效的抵制字典攻击，而且敏感哈希加密后的Hash值可以计算2信息表的相似度，有效利用了加密信息。

2）由于加密后信息仍可以计算信息表相似度，可为网络提供有效的辅助信息，与不采取隐私保护方案的SRSN协议相比，消息到达率下降不到5%，保证了网络的正常性能。

本文方法能有效地加密，保护用户隐私信息，相比于OSRN算法，提高了对字典攻击的抵御能力、降低了算法复杂度，更易于应用到实际中。今后的工作应着重于对simhash算法的研究，以提高决策的成功率，提高方案的消息传输到达率。