魏新艳,张 琳

(南京邮电大学 计算机学院,南京 210023)

0 概述

随着无线技术的快速发展,有限的频谱资源正在被迅速消耗,传统的频谱分配方案未充分利用无线电频谱资源,因此,频谱再分配对于提高资源整体利用率具有重要意义。拍卖机制是提高频谱分配公平性和分配效率的有效途径,其包括前向频谱拍卖、逆光谱拍卖、双重拍卖、异种频谱拍卖和组合拍卖。目前,对频谱分配问题的研究大多集中在单轮拍卖[1-2],而实际上,用户常以随机方式到达并发出资源请求,因此,对动态频谱拍卖机制进行研究具有现实意义[3],很多学者为此提出了动态频谱资源匹配框架[4]。文献[5]提出可信在线频谱分配的双重拍卖框架TODA,其消除了主要用户和次要用户的自我行为影响。文献[6]假设用户的干扰区域为一个长方形,提出了频谱分配框架REC-TODA。文献[7]提出在线频谱拍卖框架PROST,其为交互时间戳、用户地理位置提供隐私保护,同时设计了一种频谱复用技术。

为了体现拍卖的真实性并提高频谱利用率,在线拍卖机制倾向于刺激投标人对频谱的真实价值进行投标,但是该过程可能会造成投标人个人信息的泄漏,如投标值、投标排名、地理位置等[8]。因此,亟需设计一种全面的安全框架以保证频谱拍卖的公平开展。

目前,有研究者设计出多种频谱拍卖机制以保护隐私。文献[9]设计了2种信道拍卖机制：多无线电无线网络中的信道拍卖机制，基于差分隐私的近似利润最大化机制。文献[10]提出一种保护异质频谱单向拍卖机制的安全方案PATH，除拍卖结果所包含的信息以外，其不泄漏任何有关买家的敏感信息给任意参与方。文献[11]考虑投标人的投标价值和捆绑中的隐私保护问题，提出一种用于频谱分配的隐私保护组合拍卖机制PICASSO。然而，上述机制尚未提供足够的隐私保护，不适用于在线动态频谱拍卖，动态的频谱资源请求和供应也带来了新的安全风险。

为了解决频谱分配过程中的多目标匹配优化问题,研究学者提出了一系列智能算法,如蚁群算法(ACO)、遗传算法和粒子群算法等。其中,蚁群算法通过模拟现实中蚂蚁群体寻找最优路径的方式,从而合理解决频谱资源的多目标分配问题。文献[12]提出一种基于频率分配的蜂群优化算法,其求解旅行商(TSP)问题的效率明显提高。文献[13]通过优化信息素更新策略,提出一种多信息素动态更新的全局优化算法。文献[14]借鉴多目标遗传算法的理论,提出一种基于全局约束的多目标服务动态选择优化算法GODSS。文献[15]提出一种混合蚁群遗传算法,其通过对数值报告进行分析,证明了该算法在处理全局复杂优化问题时的可行性。上述方法虽然在一定程度上解决了资源的多目标分配问题,但都存在各自的不足,例如,蚁群算法初期信息素积累时间较长,容易陷入局部最优,遗传算法局部搜索能力较低,求解结果不稳定。

本文提出一种基于信任的频谱资源分配机制TSRA。通过信任机制对卖方和买方的信任进行评估以选出可信任用户,使用基于密文的加密算法CP-ABE对拍卖过程中投标人的敏感数据进行加密[16]。在此基础上,设计一种改进的蚁群算法,将空闲的频谱资源分配给获胜买方,以解决频谱资源的多目标优化分配问题。

1 频谱资源拍卖机制

1.1 系统模型

假设有一个中心化的无线网络[17],在t时刻,无线网络中的m个客户节点共享带宽[fmin,fmax],频谱分配网络中有4个主要对象:请求资源的客户节点(m),拍卖方,接入节点(n),资源中心。各对象具体功能如下:

1)资源中心存储各种待分配的频谱资源,用于协调频谱资源的分配。

2)接入节点收集客户节点的请求,并从资源中心获取资源,然后分配给获胜节点。接入节点是资源池与客户网络的接口。

3)请求资源的客户节点以及对应的异构化需求组成用户网络。

4)拍卖方通过构建客户节点和接入节点之间的拍卖进程,根据拍卖结果确定获胜用户节点。

本文将客户节点和接入节点的交互看作一个组合拍卖模型,且只关注用户节点与接入节点之间的交互,物联网频谱资源拍卖的系统模型如图1所示。

图1 物联网频谱资源拍卖系统模型Fig.1 Auction system model of spectrum resources in the IoT

从图1可以看出,在拍卖开始之前,首先计算请求频谱资源用户的信任值,从中选出可信用户进入拍卖网络中。然后,拍卖方根据属性加密生成公共参数对交易数据进行加密。接着,拍卖者根据从投标人处收到的出价以及接入网络的频谱定价确定获胜者,并将拍卖结果返回给投标人。最后,接入节点网络利用优化算法为胜利者分配频谱资源。当拍卖进程开始时,客户节点发出资源请求S={f1,f2,…,fm},其中,fi是频谱间隙,并且f1≤f2≤…≤fm。在客户网络中,客户节点i提交出价bi={Si,pi},Si=[fa,fb](a

(1)

定义1(组合拍卖) 在一个频谱资源分配的组合拍卖模型中,每一个竞拍者发送一个投标给拍卖者,该投标有一系列竞拍者想要获得的频谱资源以及拍卖价格。

约束条件:一个竞拍者只能给定一组频谱出价,且一个竞拍者只能获得一个频谱机会。

s.t.

(2)

1.2 信任模型

1.2.1 信任模型的影响因素

将物联网中客户节点和接入节点的集合记为S。由于在信任模型中用户间的动态信任值随着时间等多种因素呈动态变化,为了便于分析验证,本文信任模型主要针对用户间的本地信任值进行计算,同时考虑时间的动态影响因素。信任的影响因素具体如下:

1)社交互动:该因素反映了用户间交易的熟悉度。交互次数越多,信任模型的计算就越接近现实,可信度越高,也越容易被人们所信任。

2)相似度:该属性包括用户个人相似度的基本信息、现实生活中2个用户之间的兴趣相似度。相似度越高,两者越信任彼此。

3)时间衰减度:多数信任模型都是静态的,但是实际生活中用户间的信任会随着时间发生变化,因此,将时间因素引入到信任的计算中更符合现实。

1.2.2 信任的计算

根据上文构建的信任模型,考虑社交互动、相似度、时间衰减度3种因素,可以计算出2个用户之间的本地信任值,最终结果由相关因素的信任值乘以对应的权重然后求和得到,权重公式如下:

(3)

用户dx和用户dy间总的信任值如下:

(4)

其中,sj为可以提供的服务类型,其由物联网的应用需求决定,可以通过信任值判断是否可以提供服务。当用户dx和用户dy请求服务时,由信任值的大小来判断是否可以为其提供某种服务,sj计算如下:

(5)

涉及信任的因素计算如下:

1)用户的社交互动

用户dx和用户dy在某时间内的社交互动次数对信任值产生一定影响,用2个用户之间的社交活动次数除以用户各自的社交次数,可以计算出信任值,如下:

(6)

其中,ux表示用户x的邻居交互次数,uy表示用户y的邻居交互次数。

2)用户之间的相似度

Dice系数用于计算2个集合的相似度,本文引入Dice相似度以准确地计算用户dx与用户dy之间的信任关系,如下:

(7)

其中,stx表示用户dx所有特征信息的集合,sty表示用户dy所有特征信息的集合,特征信息包括用户的基本信息以及兴趣爱好等。

3)时间衰减度

在现实生活中可以发现,2个非常熟悉的人,如果很久没有互动,彼此之间没有联系,则他们间的信任就会降低,因此,引入合适的时间衰减函数来模拟用户间的信任非常必要。根据牛顿冷却定律[18],当温度下降的速度一定时,温度呈指数衰减。信任值的衰减过程可以看作一个自然冷却的过程,如下所示:

(8)

其中,c为系数。对式(8)两边同时取积分,可以得到:

w(t)=w(0)×e-c×Δt

(9)

当衰减为离散分布时,衰减速率v可以计算如下:

衰减函数可以表示为:

(10)

R3=Time(dx,dy)=

(11)

如果2个用户在一段时间内没有联系,信任值会随着时间的增加而减少;相反,信任值不变。

1.3 基于密文的属性加密

为了确保频谱资源拍卖的安全进行,本文选择基于密文策略的属性加密算法CP-ABE对拍卖过程中用户的敏感数据进行加密[19],利用属性集合来表示用户身份。为了提高OSN的安全性能,CP-ABE算法由5个过程组成,即初始化、加密、密钥生成、解密和密钥传输,详细过程如算法1所示,相关参数注释如表1所示。

算法1CP-ABE算法

1.拍卖方:

3.数据加密,C=(T,x,thx,ox,d=rs)

4.将加密信息发送给接入网络和客户网络(卖方和买方)

5.卖方:

7.发送信息给拍卖人

8.买方:

9.生成私钥解密

10.发送给拍卖人

11.返回胜利者信息

表1 相关参数说明Table 1 Explanation of relevant parameters

在算法1中,首先计算网络信息集合的拉格朗日系数,应用CP-ABE算法收集双线性群g0,将拉格朗日系数引入密文的初始化过程,生成公共参数PK和明文M;然后使用访问树T和公共参数PK,将数据明文M转换为密文C;最后客户网络和接入网络利用明文M和网络信息集S计算解密密钥,通过解密获得加密数据,从而确保整个频谱拍卖交易的安全进行。

2 频谱资源分配机制

由系统模型可知,组合拍卖过程中确定的最终胜利者为B={bβ1,bβ2,bβ2,…,bβN}。胜利者匹配多个频谱资源的问题属于NP-hard问题,可以通过蚁群算法来解决组合优化问题[20],从而寻求最佳路径。本文利用改进的蚁群算法来解决多目标优化问题,从而为获胜用户合理分配频谱资源。

证明1胜利者匹配频谱资源问题为NP-hard问题。

为了证明上述问题,本文引入最大独立集(MISP)。将物联网交易网络看作一个无向图G=(V,E),其中,V表示顶点集,映射为客户节点,E表示边集,映射为频谱概率集合,客户节点的每条边表示对应的频谱请求。任意2个胜利者记为wa、wb,(∀wa,wb∈W),对应的分配频谱集合为Swa,Swb,(∀Swa,Swb∈S,Swa∩Swb=∅),这表示W是图G的一个独立集。假设能量估值ei=1,社会效益即为W集合的大小。因为上述推理过程需要多项式时间,所以将n个频谱资源分配给m个用户的问题,即多目标胜利者决定问题是NP-hard问题,得证。

2.1 原有蚁群算法

(12)

其中,τij表示从路径i到路径j集中的信息素,ηij表示从路径i到路径j的路径长度,allowedk表示第k只蚂蚁允许通过的路径集合(未被访问路径),∂、β为控制参数,取值范围为[0,1]。

为了优化问题的解决办法,蚂蚁在寻找最优路径时,信息素浓度更新策略如下:

(13)

2.2 改进蚁群算法

由于蚁群算法初期信息素积累时间较长,容易陷入局部收敛,信息素挥发仅由挥发因子决定,且未考虑不同范围内蚂蚁的信息素影响,因此本文提出一种改进的蚁群算法,以更好地解决多目标优化问题。

2.2.1 信息素更新方式的改进

信息素更新方式改进如下:

(14)

其中,ξ为信息素奖惩因子,用来控制信息素浓度的更新,其计算如下:

(15)

其中,sij为t+1时刻路径信息素的浓度。

2.2.2 信息素扩展机制

在信息素更新机制的基础上,本文应用信息素扩散模式改进蚁群算法,信息素在临近范围内扩散的可能性通常大于其他区域。信息素扩展方式如下:

(16)

算法2改进蚁群算法

步骤1初始化算法参数,包括蚂蚁数量、信息素量、最大迭代次数、参数α和β、挥发系数等。

步骤2随机选择每只蚂蚁的初始位置。

步骤3根据式(1)计算每个蚂蚁下一状态的转移概率,选择路径。

步骤4一轮迭代结束,根据式(14)、式(15)更新每个蚂蚁经过路径的信息素浓度,对优路径进行奖励,对差路径进行惩戒,并修改禁忌表。

步骤5根据群体的信息素扩散机制式(16),在本地更新相邻路径的信息素浓度。

步骤6当蚂蚁找到可行路径时,计算路径总长度并保存。

步骤7确定路径是否满足要求,不满足,则返回步骤3;否则,执行步骤8。

步骤8输出最佳路径。

3 实验结果与分析

3.1 实验环境设置

本文在Windows 10操作系统中实现频谱分配算法TSRA,使用2.30 GHz 4核Intel Core 的CPU处理器和8 GB RAM,Java Runtime Environment(JRE)1.7。在实验过程中,ABES的参数和主密钥由模拟工具自动生成,在不同的参数条件下进行实验。属性是事物或文件的特征,本文选取用户属性数量从10到60,选择100个时隙,记为时间T。

买家随机分布在一个方形区域,面积从256×256 m2到4 096×4 096 m2。其中,信任模型的参数设置为:w1=0.568 2,w2=0.263 1,w3=0.168 7。随着用户间交互次数的增多,用户间的信任也随之上升,设置交互次数为较大影响因素比较符合实际情况。在一个频谱拍卖网络中,普通数据集中数据相对松散,用户间的相似度相对较弱,同时时间衰减也对用户间的信任产生一定影响。每个买家的干扰范围从50 m到100 m随机选择,投标值为[0,10]。本文设定卖家数的默认值为10,在时间T内请求频谱资源的用户个数λ=20,分布区域为1 024 m2,蚁群中的挥发系数θ=0.85。每个实验运行100次,取平均值作为最终结果。性能评估指标如下:

1)安全性能:为了验证方法的有效性,本文将具有相同数量属性的经典聚类方法与本文方法进行比较,通过密钥生成时间和加密精度评估方法性能。

2)社会福利:获胜投标人总出价减去获胜拍卖方的总要价。

3)计算和通信成本:拍卖过程消耗的总时间和传输的总数据量。

3.2 结果分析

本文使用基于密文的属性加密为交易数据提供隐私保护,属性与密钥的对应关系如图2所示,每个属性生成其对应的子密钥,加密密钥是所有子密钥的组合。由图2可见,随着属性数量的增加,加密密钥的生成数量呈线性增长。

图2 密钥数量与属性数量的关系Fig.2 Relationship between key numbers andattribute numbers

3.2.1 安全性能

为了验证基于密文的属性加密方法的性能优势,在相同属性条件下,本文对传统公钥加密算法[20]进行求解,该方法与本文方法的性能对比如图3所示。从图3可以看出,无论是聚类方法还是本文方法,密钥的生成时间与属性数量呈线性相关性,这是因为密钥生成阶段是根据各个属性数量使用近似算法生成子密钥,传统聚类方法的平均密钥生成时间为0.716 ms,本文方法的平均密钥生成时间是0.583 ms,比经典聚类方法少0.133 ms。本文基于属性的加密方法能够更快速地对数据进行加密,提升了加密的效率。

图3 2种方法密钥生成时间与属性数量的关系Fig.3 Relationship between key generation time and attributenumbers of two methods

传统聚类加密方法和本文加密方法的精度变化对比如图4所示。从图4可以看出,随着加密时间的增加,2种方法的精度呈下降趋势,因此,当方法长时间或者大范围应用时,其性能将会下降。传统聚类方法的平均加密精度为52.4%,本文加密方法的平均加密精度为94.3%,比传统方法提高了80%,因此,本文基于密文的属性加密算法综合性能明显优于传统方法。

图4 2种方法加密精度比较结果Fig.4 Comparison results of encryption precision oftwo methods

3.2.2 社会福利

为了验证改进蚁群算法处理频谱资源多目标组合分配问题时的优势,本文将TODA、REC-TODA、PROST与本文方法进行比较,4种方法求解频谱资源分配问题时的社会福利对比如图5所示。从图5可以看出,社会福利随着地理范围的扩大而增加,当地理范围扩大时,单位时间内获得资源的客户人数随之增加,使得社会福利在一定范围内呈上升趋势。当地理范围扩展到1 024×1 024 m2之后的区域内,社会福利随之呈下降趋势,原因是更广泛的区域意味着更少的干扰,为了减少干扰,买家将集中在几个群体中,从而减少了获胜群体的数量和社会福利效益。与其他3种分配方法相比,本文方法的社会效益较高,在1 024×1 024 m2的地理范围内,TODA、PROST、REC-TODA方法的平均社会福利分别为38.25、80.34、72.33,本文方法的平均社会福利为83.67。

图5 4种方法社会福利效益对比结果Fig.5 Comparison results of social welfare benefits offour methods

3.2.3 计算和通信成本

为了降低资源分配的计算成本,当拍卖方完成向接入用户的数据传输时,拍卖方可以同时执行一些操作以为后续过程做准备,而非等待接入用户的反馈结果,与顺序计算相比,并发计算可以大幅降低计算成本。频谱资源分配过程中计算和通信开销如表2所示,由表2可见,其中主要的计算和通信开销为加密和资源拍卖过程,随着卖家数量和买家到达数量λ的增加,系统总的计算和通信成本也随之增加。在一般情况下,当可用频谱资源ρ为20、λ为40时,在线执行的计算和通信成本分别为42.67 s和26.96 MB,与现有的频谱资源多目标分配方法相比,上述结果可以被用户所接受。

表2 频谱资源分配过程中的计算和通信开销Table 2 Computing and communication costs during spectrum resources allocation process

在频谱资源分配过程中,各方参与者的通信开销如图6所示。从图6可以看出,随着单位时间到达用户数λ的增加,频谱资源分配网络的计算成本呈近似平方增加,但在实际无线通信中,每个时隙即将到来的购买者的平均数量通常小于20,即λ<20。当λ=20时,买方的通信开销为5.12 MB,拍卖方的通信开销为10.56 MB,卖方的通信开销为12.46 MB,拍卖与卖方的通信开销为18.37 MB,在频谱资源分配过程中,上述通信开销可以被接受。

图6 通信开销与用户数量的关系Fig.6 Relationship between communication costs anduser numbers

4 结束语

本文提出一种基于信任的频谱资源分配机制TSRA。该机制建立基于信任的频谱资源拍卖模型,利用属性加密为用户的敏感信息提供隐私保护,并采用改进的蚁群算法实现多用户的频谱资源分配。实验结果表明,该机制与传统的频谱资源分配机制相比具有更高的社会效益,且能够为数据提供更高精度的保护。下一步将考虑用户反馈对竞拍平台的影响,以对物联网中交易的隐私保护进行深入研究。