魏新艷,張 琳

(南京郵電大學(xué) 計算機學(xué)院,南京 210023)

0 概述

隨著無線技術(shù)的快速發(fā)展,有限的頻譜資源正在被迅速消耗,傳統(tǒng)的頻譜分配方案未充分利用無線電頻譜資源,因此,頻譜再分配對于提高資源整體利用率具有重要意義。拍賣機制是提高頻譜分配公平性和分配效率的有效途徑,其包括前向頻譜拍賣、逆光譜拍賣、雙重拍賣、異種頻譜拍賣和組合拍賣。目前,對頻譜分配問題的研究大多集中在單輪拍賣[1-2],而實際上,用戶常以隨機方式到達并發(fā)出資源請求,因此,對動態(tài)頻譜拍賣機制進行研究具有現(xiàn)實意義[3],很多學(xué)者為此提出了動態(tài)頻譜資源匹配框架[4]。文獻[5]提出可信在線頻譜分配的雙重拍賣框架TODA,其消除了主要用戶和次要用戶的自我行為影響。文獻[6]假設(shè)用戶的干擾區(qū)域為一個長方形,提出了頻譜分配框架REC-TODA。文獻[7]提出在線頻譜拍賣框架PROST,其為交互時間戳、用戶地理位置提供隱私保護,同時設(shè)計了一種頻譜復(fù)用技術(shù)。

為了體現(xiàn)拍賣的真實性并提高頻譜利用率,在線拍賣機制傾向于刺激投標人對頻譜的真實價值進行投標,但是該過程可能會造成投標人個人信息的泄漏,如投標值、投標排名、地理位置等[8]。因此,亟需設(shè)計一種全面的安全框架以保證頻譜拍賣的公平開展。

目前,有研究者設(shè)計出多種頻譜拍賣機制以保護隱私。文獻[9]設(shè)計了2種信道拍賣機制：多無線電無線網(wǎng)絡(luò)中的信道拍賣機制，基于差分隱私的近似利潤最大化機制。文獻[10]提出一種保護異質(zhì)頻譜單向拍賣機制的安全方案PATH，除拍賣結(jié)果所包含的信息以外，其不泄漏任何有關(guān)買家的敏感信息給任意參與方。文獻[11]考慮投標人的投標價值和捆綁中的隱私保護問題，提出一種用于頻譜分配的隱私保護組合拍賣機制PICASSO。然而，上述機制尚未提供足夠的隱私保護，不適用于在線動態(tài)頻譜拍賣，動態(tài)的頻譜資源請求和供應(yīng)也帶來了新的安全風險。

為了解決頻譜分配過程中的多目標匹配優(yōu)化問題,研究學(xué)者提出了一系列智能算法,如蟻群算法(ACO)、遺傳算法和粒子群算法等。其中,蟻群算法通過模擬現(xiàn)實中螞蟻群體尋找最優(yōu)路徑的方式,從而合理解決頻譜資源的多目標分配問題。文獻[12]提出一種基于頻率分配的蜂群優(yōu)化算法,其求解旅行商(TSP)問題的效率明顯提高。文獻[13]通過優(yōu)化信息素更新策略,提出一種多信息素動態(tài)更新的全局優(yōu)化算法。文獻[14]借鑒多目標遺傳算法的理論,提出一種基于全局約束的多目標服務(wù)動態(tài)選擇優(yōu)化算法GODSS。文獻[15]提出一種混合蟻群遺傳算法,其通過對數(shù)值報告進行分析,證明了該算法在處理全局復(fù)雜優(yōu)化問題時的可行性。上述方法雖然在一定程度上解決了資源的多目標分配問題,但都存在各自的不足,例如,蟻群算法初期信息素積累時間較長,容易陷入局部最優(yōu),遺傳算法局部搜索能力較低,求解結(jié)果不穩(wěn)定。

本文提出一種基于信任的頻譜資源分配機制TSRA。通過信任機制對賣方和買方的信任進行評估以選出可信任用戶,使用基于密文的加密算法CP-ABE對拍賣過程中投標人的敏感數(shù)據(jù)進行加密[16]。在此基礎(chǔ)上,設(shè)計一種改進的蟻群算法,將空閑的頻譜資源分配給獲勝買方,以解決頻譜資源的多目標優(yōu)化分配問題。

1 頻譜資源拍賣機制

1.1 系統(tǒng)模型

假設(shè)有一個中心化的無線網(wǎng)絡(luò)[17],在t時刻,無線網(wǎng)絡(luò)中的m個客戶節(jié)點共享帶寬[fmin,fmax],頻譜分配網(wǎng)絡(luò)中有4個主要對象:請求資源的客戶節(jié)點(m),拍賣方,接入節(jié)點(n),資源中心。各對象具體功能如下:

1)資源中心存儲各種待分配的頻譜資源,用于協(xié)調(diào)頻譜資源的分配。

2)接入節(jié)點收集客戶節(jié)點的請求,并從資源中心獲取資源,然后分配給獲勝節(jié)點。接入節(jié)點是資源池與客戶網(wǎng)絡(luò)的接口。

3)請求資源的客戶節(jié)點以及對應(yīng)的異構(gòu)化需求組成用戶網(wǎng)絡(luò)。

4)拍賣方通過構(gòu)建客戶節(jié)點和接入節(jié)點之間的拍賣進程,根據(jù)拍賣結(jié)果確定獲勝用戶節(jié)點。

本文將客戶節(jié)點和接入節(jié)點的交互看作一個組合拍賣模型,且只關(guān)注用戶節(jié)點與接入節(jié)點之間的交互,物聯(lián)網(wǎng)頻譜資源拍賣的系統(tǒng)模型如圖1所示。

圖1 物聯(lián)網(wǎng)頻譜資源拍賣系統(tǒng)模型Fig.1 Auction system model of spectrum resources in the IoT

從圖1可以看出,在拍賣開始之前,首先計算請求頻譜資源用戶的信任值,從中選出可信用戶進入拍賣網(wǎng)絡(luò)中。然后,拍賣方根據(jù)屬性加密生成公共參數(shù)對交易數(shù)據(jù)進行加密。接著,拍賣者根據(jù)從投標人處收到的出價以及接入網(wǎng)絡(luò)的頻譜定價確定獲勝者,并將拍賣結(jié)果返回給投標人。最后,接入節(jié)點網(wǎng)絡(luò)利用優(yōu)化算法為勝利者分配頻譜資源。當拍賣進程開始時,客戶節(jié)點發(fā)出資源請求S={f1,f2,…,fm},其中,fi是頻譜間隙,并且f1≤f2≤…≤fm。在客戶網(wǎng)絡(luò)中,客戶節(jié)點i提交出價bi={Si,pi},Si=[fa,fb](a

(1)

定義1(組合拍賣) 在一個頻譜資源分配的組合拍賣模型中,每一個競拍者發(fā)送一個投標給拍賣者,該投標有一系列競拍者想要獲得的頻譜資源以及拍賣價格。

約束條件:一個競拍者只能給定一組頻譜出價,且一個競拍者只能獲得一個頻譜機會。

s.t.

(2)

1.2 信任模型

1.2.1 信任模型的影響因素

將物聯(lián)網(wǎng)中客戶節(jié)點和接入節(jié)點的集合記為S。由于在信任模型中用戶間的動態(tài)信任值隨著時間等多種因素呈動態(tài)變化,為了便于分析驗證,本文信任模型主要針對用戶間的本地信任值進行計算,同時考慮時間的動態(tài)影響因素。信任的影響因素具體如下:

1)社交互動:該因素反映了用戶間交易的熟悉度。交互次數(shù)越多,信任模型的計算就越接近現(xiàn)實,可信度越高,也越容易被人們所信任。

2)相似度:該屬性包括用戶個人相似度的基本信息、現(xiàn)實生活中2個用戶之間的興趣相似度。相似度越高,兩者越信任彼此。

3)時間衰減度:多數(shù)信任模型都是靜態(tài)的,但是實際生活中用戶間的信任會隨著時間發(fā)生變化,因此,將時間因素引入到信任的計算中更符合現(xiàn)實。

1.2.2 信任的計算

根據(jù)上文構(gòu)建的信任模型,考慮社交互動、相似度、時間衰減度3種因素,可以計算出2個用戶之間的本地信任值,最終結(jié)果由相關(guān)因素的信任值乘以對應(yīng)的權(quán)重然后求和得到,權(quán)重公式如下:

(3)

用戶dx和用戶dy間總的信任值如下:

(4)

其中,sj為可以提供的服務(wù)類型,其由物聯(lián)網(wǎng)的應(yīng)用需求決定,可以通過信任值判斷是否可以提供服務(wù)。當用戶dx和用戶dy請求服務(wù)時,由信任值的大小來判斷是否可以為其提供某種服務(wù),sj計算如下:

(5)

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

1)用戶的社交互動

用戶dx和用戶dy在某時間內(nèi)的社交互動次數(shù)對信任值產(chǎn)生一定影響,用2個用戶之間的社交活動次數(shù)除以用戶各自的社交次數(shù),可以計算出信任值,如下:

(6)

其中,ux表示用戶x的鄰居交互次數(shù),uy表示用戶y的鄰居交互次數(shù)。

2)用戶之間的相似度

Dice系數(shù)用于計算2個集合的相似度,本文引入Dice相似度以準確地計算用戶dx與用戶dy之間的信任關(guān)系,如下:

(7)

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

3)時間衰減度

在現(xiàn)實生活中可以發(fā)現(xiàn),2個非常熟悉的人,如果很久沒有互動,彼此之間沒有聯(lián)系,則他們間的信任就會降低,因此,引入合適的時間衰減函數(shù)來模擬用戶間的信任非常必要。根據(jù)牛頓冷卻定律[18],當溫度下降的速度一定時,溫度呈指數(shù)衰減。信任值的衰減過程可以看作一個自然冷卻的過程,如下所示:

(8)

其中,c為系數(shù)。對式(8)兩邊同時取積分,可以得到:

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

(9)

當衰減為離散分布時,衰減速率v可以計算如下:

衰減函數(shù)可以表示為:

(10)

R3=Time(dx,dy)=

(11)

如果2個用戶在一段時間內(nèi)沒有聯(lián)系,信任值會隨著時間的增加而減少;相反,信任值不變。

1.3 基于密文的屬性加密

為了確保頻譜資源拍賣的安全進行,本文選擇基于密文策略的屬性加密算法CP-ABE對拍賣過程中用戶的敏感數(shù)據(jù)進行加密[19],利用屬性集合來表示用戶身份。為了提高OSN的安全性能,CP-ABE算法由5個過程組成,即初始化、加密、密鑰生成、解密和密鑰傳輸,詳細過程如算法1所示,相關(guān)參數(shù)注釋如表1所示。

算法1CP-ABE算法

1.拍賣方:

3.數(shù)據(jù)加密,C=(T,x,thx,ox,d=rs)

4.將加密信息發(fā)送給接入網(wǎng)絡(luò)和客戶網(wǎng)絡(luò)(賣方和買方)

5.賣方:

7.發(fā)送信息給拍賣人

8.買方:

9.生成私鑰解密

10.發(fā)送給拍賣人

11.返回勝利者信息

表1 相關(guān)參數(shù)說明Table 1 Explanation of relevant parameters

在算法1中,首先計算網(wǎng)絡(luò)信息集合的拉格朗日系數(shù),應(yīng)用CP-ABE算法收集雙線性群g0,將拉格朗日系數(shù)引入密文的初始化過程,生成公共參數(shù)PK和明文M;然后使用訪問樹T和公共參數(shù)PK,將數(shù)據(jù)明文M轉(zhuǎn)換為密文C;最后客戶網(wǎng)絡(luò)和接入網(wǎng)絡(luò)利用明文M和網(wǎng)絡(luò)信息集S計算解密密鑰,通過解密獲得加密數(shù)據(jù),從而確保整個頻譜拍賣交易的安全進行。

2 頻譜資源分配機制

由系統(tǒng)模型可知,組合拍賣過程中確定的最終勝利者為B={bβ1,bβ2,bβ2,…,bβN}。勝利者匹配多個頻譜資源的問題屬于NP-hard問題,可以通過蟻群算法來解決組合優(yōu)化問題[20],從而尋求最佳路徑。本文利用改進的蟻群算法來解決多目標優(yōu)化問題,從而為獲勝用戶合理分配頻譜資源。

證明1勝利者匹配頻譜資源問題為NP-hard問題。

為了證明上述問題,本文引入最大獨立集(MISP)。將物聯(lián)網(wǎng)交易網(wǎng)絡(luò)看作一個無向圖G=(V,E),其中,V表示頂點集,映射為客戶節(jié)點,E表示邊集,映射為頻譜概率集合,客戶節(jié)點的每條邊表示對應(yīng)的頻譜請求。任意2個勝利者記為wa、wb,(?wa,wb∈W),對應(yīng)的分配頻譜集合為Swa,Swb,(?Swa,Swb∈S,Swa∩Swb=?),這表示W(wǎng)是圖G的一個獨立集。假設(shè)能量估值ei=1,社會效益即為W集合的大小。因為上述推理過程需要多項式時間,所以將n個頻譜資源分配給m個用戶的問題,即多目標勝利者決定問題是NP-hard問題,得證。

2.1 原有蟻群算法

(12)

其中,τij表示從路徑i到路徑j(luò)集中的信息素,ηij表示從路徑i到路徑j(luò)的路徑長度,allowedk表示第k只螞蟻允許通過的路徑集合(未被訪問路徑),?、β為控制參數(shù),取值范圍為[0,1]。

為了優(yōu)化問題的解決辦法,螞蟻在尋找最優(yōu)路徑時,信息素濃度更新策略如下:

(13)

2.2 改進蟻群算法

由于蟻群算法初期信息素積累時間較長,容易陷入局部收斂,信息素揮發(fā)僅由揮發(fā)因子決定,且未考慮不同范圍內(nèi)螞蟻的信息素影響,因此本文提出一種改進的蟻群算法,以更好地解決多目標優(yōu)化問題。

2.2.1 信息素更新方式的改進

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

(14)

其中,ξ為信息素獎懲因子,用來控制信息素濃度的更新,其計算如下:

(15)

其中,sij為t+1時刻路徑信息素的濃度。

2.2.2 信息素擴展機制

在信息素更新機制的基礎(chǔ)上,本文應(yīng)用信息素擴散模式改進蟻群算法,信息素在臨近范圍內(nèi)擴散的可能性通常大于其他區(qū)域。信息素擴展方式如下:

(16)

算法2改進蟻群算法

步驟1初始化算法參數(shù),包括螞蟻數(shù)量、信息素量、最大迭代次數(shù)、參數(shù)α和β、揮發(fā)系數(shù)等。

步驟2隨機選擇每只螞蟻的初始位置。

步驟3根據(jù)式(1)計算每個螞蟻下一狀態(tài)的轉(zhuǎn)移概率,選擇路徑。

步驟4一輪迭代結(jié)束,根據(jù)式(14)、式(15)更新每個螞蟻經(jīng)過路徑的信息素濃度,對優(yōu)路徑進行獎勵,對差路徑進行懲戒,并修改禁忌表。

步驟5根據(jù)群體的信息素擴散機制式(16),在本地更新相鄰路徑的信息素濃度。

步驟6當螞蟻找到可行路徑時,計算路徑總長度并保存。

步驟7確定路徑是否滿足要求,不滿足,則返回步驟3;否則,執(zhí)行步驟8。

步驟8輸出最佳路徑。

3 實驗結(jié)果與分析

3.1 實驗環(huán)境設(shè)置

本文在Windows 10操作系統(tǒng)中實現(xiàn)頻譜分配算法TSRA,使用2.30 GHz 4核Intel Core 的CPU處理器和8 GB RAM,Java Runtime Environment(JRE)1.7。在實驗過程中,ABES的參數(shù)和主密鑰由模擬工具自動生成,在不同的參數(shù)條件下進行實驗。屬性是事物或文件的特征,本文選取用戶屬性數(shù)量從10到60,選擇100個時隙,記為時間T。

買家隨機分布在一個方形區(qū)域,面積從256×256 m2到4 096×4 096 m2。其中,信任模型的參數(shù)設(shè)置為:w1=0.568 2,w2=0.263 1,w3=0.168 7。隨著用戶間交互次數(shù)的增多,用戶間的信任也隨之上升,設(shè)置交互次數(shù)為較大影響因素比較符合實際情況。在一個頻譜拍賣網(wǎng)絡(luò)中,普通數(shù)據(jù)集中數(shù)據(jù)相對松散,用戶間的相似度相對較弱,同時時間衰減也對用戶間的信任產(chǎn)生一定影響。每個買家的干擾范圍從50 m到100 m隨機選擇,投標值為[0,10]。本文設(shè)定賣家數(shù)的默認值為10,在時間T內(nèi)請求頻譜資源的用戶個數(shù)λ=20,分布區(qū)域為1 024 m2,蟻群中的揮發(fā)系數(shù)θ=0.85。每個實驗運行100次,取平均值作為最終結(jié)果。性能評估指標如下:

1)安全性能:為了驗證方法的有效性,本文將具有相同數(shù)量屬性的經(jīng)典聚類方法與本文方法進行比較,通過密鑰生成時間和加密精度評估方法性能。

2)社會福利:獲勝投標人總出價減去獲勝拍賣方的總要價。

3)計算和通信成本:拍賣過程消耗的總時間和傳輸?shù)目倲?shù)據(jù)量。

3.2 結(jié)果分析

本文使用基于密文的屬性加密為交易數(shù)據(jù)提供隱私保護,屬性與密鑰的對應(yīng)關(guān)系如圖2所示,每個屬性生成其對應(yīng)的子密鑰,加密密鑰是所有子密鑰的組合。由圖2可見,隨著屬性數(shù)量的增加,加密密鑰的生成數(shù)量呈線性增長。

圖2 密鑰數(shù)量與屬性數(shù)量的關(guān)系Fig.2 Relationship between key numbers andattribute numbers

3.2.1 安全性能

為了驗證基于密文的屬性加密方法的性能優(yōu)勢,在相同屬性條件下,本文對傳統(tǒng)公鑰加密算法[20]進行求解,該方法與本文方法的性能對比如圖3所示。從圖3可以看出,無論是聚類方法還是本文方法,密鑰的生成時間與屬性數(shù)量呈線性相關(guān)性,這是因為密鑰生成階段是根據(jù)各個屬性數(shù)量使用近似算法生成子密鑰,傳統(tǒng)聚類方法的平均密鑰生成時間為0.716 ms,本文方法的平均密鑰生成時間是0.583 ms,比經(jīng)典聚類方法少0.133 ms。本文基于屬性的加密方法能夠更快速地對數(shù)據(jù)進行加密,提升了加密的效率。

圖3 2種方法密鑰生成時間與屬性數(shù)量的關(guān)系Fig.3 Relationship between key generation time and attributenumbers of two methods

傳統(tǒng)聚類加密方法和本文加密方法的精度變化對比如圖4所示。從圖4可以看出,隨著加密時間的增加,2種方法的精度呈下降趨勢,因此,當方法長時間或者大范圍應(yīng)用時,其性能將會下降。傳統(tǒng)聚類方法的平均加密精度為52.4%,本文加密方法的平均加密精度為94.3%,比傳統(tǒng)方法提高了80%,因此,本文基于密文的屬性加密算法綜合性能明顯優(yōu)于傳統(tǒng)方法。

圖4 2種方法加密精度比較結(jié)果Fig.4 Comparison results of encryption precision oftwo methods

3.2.2 社會福利

為了驗證改進蟻群算法處理頻譜資源多目標組合分配問題時的優(yōu)勢,本文將TODA、REC-TODA、PROST與本文方法進行比較,4種方法求解頻譜資源分配問題時的社會福利對比如圖5所示。從圖5可以看出,社會福利隨著地理范圍的擴大而增加,當?shù)乩矸秶鷶U大時,單位時間內(nèi)獲得資源的客戶人數(shù)隨之增加,使得社會福利在一定范圍內(nèi)呈上升趨勢。當?shù)乩矸秶鷶U展到1 024×1 024 m2之后的區(qū)域內(nèi),社會福利隨之呈下降趨勢,原因是更廣泛的區(qū)域意味著更少的干擾,為了減少干擾,買家將集中在幾個群體中,從而減少了獲勝群體的數(shù)量和社會福利效益。與其他3種分配方法相比,本文方法的社會效益較高,在1 024×1 024 m2的地理范圍內(nèi),TODA、PROST、REC-TODA方法的平均社會福利分別為38.25、80.34、72.33,本文方法的平均社會福利為83.67。

圖5 4種方法社會福利效益對比結(jié)果Fig.5 Comparison results of social welfare benefits offour methods

3.2.3 計算和通信成本

為了降低資源分配的計算成本,當拍賣方完成向接入用戶的數(shù)據(jù)傳輸時,拍賣方可以同時執(zhí)行一些操作以為后續(xù)過程做準備,而非等待接入用戶的反饋結(jié)果,與順序計算相比,并發(fā)計算可以大幅降低計算成本。頻譜資源分配過程中計算和通信開銷如表2所示,由表2可見,其中主要的計算和通信開銷為加密和資源拍賣過程,隨著賣家數(shù)量和買家到達數(shù)量λ的增加,系統(tǒng)總的計算和通信成本也隨之增加。在一般情況下,當可用頻譜資源ρ為20、λ為40時,在線執(zhí)行的計算和通信成本分別為42.67 s和26.96 MB,與現(xiàn)有的頻譜資源多目標分配方法相比,上述結(jié)果可以被用戶所接受。

表2 頻譜資源分配過程中的計算和通信開銷Table 2 Computing and communication costs during spectrum resources allocation process

在頻譜資源分配過程中,各方參與者的通信開銷如圖6所示。從圖6可以看出,隨著單位時間到達用戶數(shù)λ的增加,頻譜資源分配網(wǎng)絡(luò)的計算成本呈近似平方增加,但在實際無線通信中,每個時隙即將到來的購買者的平均數(shù)量通常小于20,即λ<20。當λ=20時,買方的通信開銷為5.12 MB,拍賣方的通信開銷為10.56 MB,賣方的通信開銷為12.46 MB,拍賣與賣方的通信開銷為18.37 MB,在頻譜資源分配過程中,上述通信開銷可以被接受。

圖6 通信開銷與用戶數(shù)量的關(guān)系Fig.6 Relationship between communication costs anduser numbers

4 結(jié)束語

本文提出一種基于信任的頻譜資源分配機制TSRA。該機制建立基于信任的頻譜資源拍賣模型,利用屬性加密為用戶的敏感信息提供隱私保護,并采用改進的蟻群算法實現(xiàn)多用戶的頻譜資源分配。實驗結(jié)果表明,該機制與傳統(tǒng)的頻譜資源分配機制相比具有更高的社會效益,且能夠為數(shù)據(jù)提供更高精度的保護。下一步將考慮用戶反饋對競拍平臺的影響,以對物聯(lián)網(wǎng)中交易的隱私保護進行深入研究。