物聯網中基于信任的頻譜資源分配機制

魏新艷,張 琳

(南京郵電大學 計算機學院,南京 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。該機制建立基于信任的頻譜資源拍賣模型,利用屬性加密為用戶的敏感信息提供隱私保護,并采用改進的蟻群算法實現多用戶的頻譜資源分配。實驗結果表明,該機制與傳統的頻譜資源分配機制相比具有更高的社會效益,且能夠為數據提供更高精度的保護。下一步將考慮用戶反饋對競拍平臺的影響,以對物聯網中交易的隱私保護進行深入研究。