基于多目標(biāo)效用優(yōu)化的分布式數(shù)據(jù)交易算法

黃小紅，張勇，閃德勝，錢葉魁，韓璐，李丹丹，叢群

（1.北京郵電大學(xué)計算機(jī)學(xué)院（國家示范性軟件學(xué)院），北京 100876；2.中國人民解放軍32147 部隊，陜西 寶雞 721000；3.陸軍炮兵防空兵學(xué)院鄭州校區(qū)，河南 鄭州 450052；4.北京網(wǎng)瑞達(dá)科技有限公司技術(shù)研發(fā)部，北京 100876）

1 引言

隨著物聯(lián)網(wǎng)、車聯(lián)網(wǎng)、微電網(wǎng)以及移動應(yīng)用的發(fā)展，大數(shù)據(jù)呈現(xiàn)爆炸式的增長趨勢[1-2]。預(yù)計到2026 年，數(shù)據(jù)價值將達(dá)到922 億美元[3]。目前，大部分?jǐn)?shù)據(jù)都存儲在公司或組織的數(shù)據(jù)庫中，形成一個個數(shù)據(jù)孤島，只有少部分?jǐn)?shù)據(jù)真正得到充分利用，而且在使用上也有各種限制[4]。許多App 開發(fā)者和研究人員迫切需要數(shù)據(jù)來提高產(chǎn)品和研究的質(zhì)量，并且愿意為此支付一定的經(jīng)濟(jì)成本[5-6]。因此，一些數(shù)據(jù)交易市場應(yīng)運(yùn)而生，如 Infochimps、Datacoup、Microsoft Azure Marketplace 等[7]，但這些市場仍處于起步階段，缺乏適用的交易規(guī)則。而且，從經(jīng)濟(jì)學(xué)的角度來看，市場組織者都是自私的，他們追求的是自身利益的最大化，而不是系統(tǒng)的整體效用。

因此，設(shè)計一種有效的數(shù)據(jù)交易機(jī)制成為學(xué)者的研究重點[8-9]。Niyato 等[10]描述了一種典型的數(shù)據(jù)交易市場模型，該模型由3 種實體組成：數(shù)據(jù)提供者（DP,data provider）、數(shù)據(jù)消費(fèi)者（DC,data consumer）和數(shù)據(jù)代理（DA,data agent）。Cao 等[11]考慮了數(shù)據(jù)市場中存在多個DP、DA 和DC 的情況，提出了一種迭代拍賣機(jī)制來協(xié)調(diào)交易。Jiao 等[12]考慮了大數(shù)據(jù)的“無限供給”性，提出了一種基于拍賣的大數(shù)據(jù)市場模型，通過拍賣機(jī)制得到最優(yōu)的數(shù)據(jù)交易價格和交易量。Yu 等[13]通過考慮數(shù)據(jù)質(zhì)量和數(shù)據(jù)多版本發(fā)布的策略，提出了一個雙層數(shù)學(xué)規(guī)劃模型來優(yōu)化數(shù)據(jù)交易。

當(dāng)前針對數(shù)據(jù)交易的研究主要考慮了數(shù)據(jù)量、數(shù)據(jù)質(zhì)量等數(shù)據(jù)本身的因素，忽視了數(shù)據(jù)屬性、屬性的相關(guān)性等與用戶任務(wù)相關(guān)的因素。而且，在存在多個DC 的場景下，這些因素之間是存在競爭關(guān)系的，在研究數(shù)據(jù)交易時也應(yīng)將這些競爭考慮在內(nèi)。此外，現(xiàn)有框架一般以DA 作為中介來實施數(shù)據(jù)交易，即DA 從DP 處購買數(shù)據(jù)，然后將其出售給DC。由于DA 的信任危機(jī)和數(shù)據(jù)產(chǎn)品的低復(fù)制成本，這些集中式的解決方案帶來了數(shù)據(jù)泄露方面的問題。

因此，一些學(xué)者針對如何提高數(shù)據(jù)交易的安全性和隱私性進(jìn)行了研究[14]。Niu 等[15]提出了基于同態(tài)加密和身份簽名的數(shù)據(jù)交易市場架構(gòu)來保護(hù)DP的隱私。Jung 等[16]研究了數(shù)據(jù)交易中DC 的行為，并設(shè)計了AccountTrade 來保證DC 為其不誠實的行為承擔(dān)責(zé)任。但是，這些基于密碼學(xué)的解決方案復(fù)雜性較高，在時間和空間方面代價昂貴。基于分布式對等網(wǎng)絡(luò)的區(qū)塊鏈技術(shù)具有去中心化、不可篡改、可追溯、匿名性和透明性五大特征，這些特征為數(shù)據(jù)交易的安全問題提供了很好的解決方案[17-18]。Delgado-segura 等[19]提出了一種基于比特幣的公平的分布式數(shù)據(jù)交易協(xié)議。Missier 等[20]使用區(qū)塊鏈構(gòu)建了一個分布式的、可信的、開放的物聯(lián)網(wǎng)數(shù)據(jù)交易架構(gòu)，并基于以太坊進(jìn)行了實現(xiàn)。Sabounchi 等[21]利用區(qū)塊鏈技術(shù)和契約理論設(shè)計了一種基于以太坊的P2P 數(shù)據(jù)交易機(jī)制。Gao 等[22]提出了一種安全、公平的數(shù)據(jù)交易方案，并設(shè)計了一種新型的比特幣腳本來減少交易時延。這些方案采用分布式的架構(gòu)解決了數(shù)據(jù)交易中的安全與信任問題，但是在效率方面仍存在不足，比如，比特幣的吞吐量為7 TPS（transaction per second），以太坊的吞吐量為15 TPS，與實際需求相去甚遠(yuǎn)。

基于以上研究，本文提出了基于聯(lián)盟區(qū)塊鏈的分布式數(shù)據(jù)交易框架。在此框架下，通過考慮多維因素，建立了DP 和DC 的效用函數(shù)，并構(gòu)建了雙層多目標(biāo)優(yōu)化模型對他們進(jìn)行優(yōu)化。為求解優(yōu)化模型，提出了協(xié)作式NSGAII，并通過實驗對算法的性能進(jìn)行了評估。本文的主要貢獻(xiàn)如下。

1)針對中心化交易方案容易出現(xiàn)數(shù)據(jù)泄露的問題，提出基于聯(lián)盟區(qū)塊鏈的分布式數(shù)據(jù)交易框架，實現(xiàn)了DP 與DC 的P2P 的數(shù)據(jù)交易。

2)為了提高數(shù)據(jù)交易的有效性，通過綜合考慮數(shù)據(jù)本身和用戶任務(wù)相關(guān)的因素，基于數(shù)據(jù)質(zhì)量、數(shù)據(jù)屬性、屬性的相關(guān)性、消費(fèi)者競爭等多維因素構(gòu)建雙層多目標(biāo)優(yōu)化模型，以優(yōu)化DP 和DC 的效用函數(shù)。

3)針對NSGAII 會泄露用戶隱私的問題，提出一種改進(jìn)算法——協(xié)作式NSGAII，通過DP、DC以及數(shù)據(jù)聚合器（AG,data aggregator）的協(xié)作來進(jìn)行計算。DP 和DC 的效用函數(shù)由用戶在本地進(jìn)行計算，以免泄露隱私。

4)使用北京的空氣質(zhì)量數(shù)據(jù)進(jìn)行了實驗，以評估所提算法的性能。結(jié)果表明，所提算法在DP 和DC 的效用方面可以實現(xiàn)很好的性能。

2 系統(tǒng)模型

本節(jié)描述了分布式數(shù)據(jù)交易的場景，并構(gòu)建了基于聯(lián)盟區(qū)塊鏈的分布式數(shù)據(jù)交易框架。

2.1 分布式數(shù)據(jù)交易框架

圖1 展示了基于聯(lián)盟區(qū)塊鏈的數(shù)據(jù)交易框架，為確保數(shù)據(jù)交易的安全性和效率，本節(jié)設(shè)計了基于聯(lián)盟區(qū)塊鏈的數(shù)據(jù)交易框架。聯(lián)盟區(qū)塊鏈?zhǔn)且环N特殊的區(qū)塊鏈，它建立在許多預(yù)選的共識節(jié)點上，并由這些節(jié)點執(zhí)行共識算法[23]。相比于公鏈，由于參與共識的節(jié)點較少，聯(lián)盟鏈多采用實用拜占庭容錯機(jī)制（PBFT,practical Byzantine fault tolerance）、委托拜占庭容錯機(jī)制（DBFT,delegated Byzantine fault tolerance）、Raft 等共識機(jī)制。這些機(jī)制相較于公鏈所采用的工作量證明（PoW,proof of work）、權(quán)益證明（PoS,proof of state）等機(jī)制，數(shù)據(jù)處理速度有很大提升，因此極大地提升了聯(lián)盟鏈的效率和吞吐量，對比比特幣的7 TPS 和以太坊的15 TPS，采用聯(lián)盟鏈的Fabric 可以達(dá)到500 TPS、Quorum 可以達(dá)到800 TPS[24]。

數(shù)據(jù)交易框架包含3 種實體，分別是AG、DP和DC。

1)AG 在系統(tǒng)中是數(shù)據(jù)交易組織者，負(fù)責(zé)數(shù)據(jù)交易過程中一些信息的傳遞以及對DP 數(shù)據(jù)的質(zhì)量評估。每個AG 負(fù)責(zé)某種類型數(shù)據(jù)的交易。例如，在圖1 中，AG4負(fù)責(zé)物聯(lián)網(wǎng)數(shù)據(jù)的交易，AG6負(fù)責(zé)互聯(lián)網(wǎng)數(shù)據(jù)的交易。在聯(lián)盟區(qū)塊鏈中，AG 充當(dāng)選定節(jié)點來驗證交易。

圖1 基于聯(lián)盟區(qū)塊鏈的數(shù)據(jù)交易框架

2)DP 收集從各種來源（如傳感器、移動設(shè)備、互聯(lián)網(wǎng)等）生成的數(shù)據(jù)，這些數(shù)據(jù)包含某些屬性。

3)DC 是購買數(shù)據(jù)并對數(shù)據(jù)具有某些屬性需求的最終用戶。

每個實體都有自己的賬戶和錢包。賬戶用于存儲交易記錄；錢包用于管理賬戶中的數(shù)字貨幣。交易完成后，DP 和DC 使用錢包來進(jìn)行數(shù)字貨幣的收/付款。AG 使用錢包收取數(shù)據(jù)質(zhì)量評估的費(fèi)用。借助PBFT，至少1/3 的AG 確認(rèn)交易，才能達(dá)成共識。

2.2 數(shù)據(jù)交易流程

數(shù)據(jù)交易流程如圖2 所示，其具體步驟如下。

圖2 數(shù)據(jù)交易流程

1)初始化。DP 和DC 使用有效的身份證明（例如居民身份證、企業(yè)營業(yè)執(zhí)照等）向AG 注冊成為合法實體，包括公鑰、私鑰的一對密鑰將被分配給他們。DP 和DC 使用私鑰生成錢包地址來參與數(shù)據(jù)交易。隨后，DP 和DC 根據(jù)數(shù)據(jù)的類型將交易請求發(fā)送到相應(yīng)的AG，DP 的請求包括其數(shù)據(jù)的數(shù)量和屬性信息，DC 的請求包括其屬性需求。

2)AG 廣播這些數(shù)據(jù)交易請求并進(jìn)行數(shù)據(jù)質(zhì)量評估。AG 從DP 處獲取一定比例的數(shù)據(jù)樣本，執(zhí)行質(zhì)量評估，并將評估結(jié)果記錄到區(qū)塊鏈上。

3)DP 根據(jù)DC 的屬性需求為每個DC 提供相應(yīng)的數(shù)據(jù)產(chǎn)品和單價。數(shù)據(jù)產(chǎn)品的屬性是DP 所能提供的屬性與DC 所需的屬性的交集。

4)根據(jù)DP 所提供的數(shù)據(jù)產(chǎn)品，DC 以最大化自身的效用為目標(biāo)，選擇最合適的數(shù)據(jù)產(chǎn)品，并計算購買量。DP 根據(jù)DC 的反饋，進(jìn)一步調(diào)整數(shù)據(jù)產(chǎn)品的單價。

5)經(jīng)過多輪交互，確定最終的交易方案，并由AG 將其存儲在區(qū)塊鏈上。根據(jù)數(shù)據(jù)交易方案，AG為每一筆交易創(chuàng)建相應(yīng)的智能合約，DC 將數(shù)字貨幣存儲在相應(yīng)的合約地址中。

6)DP 將相應(yīng)的數(shù)據(jù)產(chǎn)品發(fā)送給DC。

7)數(shù)據(jù)傳輸完成后，DP 對交易記錄進(jìn)行數(shù)字簽名，然后發(fā)送給AG。AG 將交易記錄發(fā)送給相應(yīng)的DC。DC 驗證交易記錄并進(jìn)行數(shù)字簽名后回傳給AG。此時，DC 保留在智能合約中的數(shù)字貨幣也將被發(fā)送到DP 的錢包地址。

8)經(jīng)過一段時間的收集后，具有排序功能的AG 將交易記錄打包成塊，然后通過PBFT 將它們存儲在區(qū)塊鏈上。

在交易過程中，AG 負(fù)責(zé)數(shù)據(jù)質(zhì)量評估、信息傳輸和共識算法執(zhí)行。交易的數(shù)據(jù)由DP 直接傳輸給DC，因此是分布式的P2P 數(shù)據(jù)交易。這種交易方法可以避免單點故障、信息泄露和其他集中式交易的安全問題。

3 雙層多目標(biāo)數(shù)據(jù)交易匹配優(yōu)化模型

本節(jié)將描述如何構(gòu)建數(shù)據(jù)交易匹配模型，以優(yōu)化DP 和DC 的效用，并給出模型的求解算法。

3.1 問題描述

在描述問題之前，給出所需參數(shù)及其含義，如表1 所示。

如圖1 所示，存在一組AG，記作A，ai∈A，1≤i≤I。一段時間內(nèi)，ai收集DP 和DC 的數(shù)據(jù)交易請求。設(shè)P和C分別表示DP 和DC 的集合，P中包含J位DP，pj∈P，1≤j≤J，pj向ai提交其數(shù)據(jù)屬性集合和數(shù)據(jù)量Nj；C中包含K位DC，ck∈C，1≤k≤K，ck向ai提交其屬性需求集合。

表1 參數(shù)及其含義

接收到AG 廣播的DC 的屬性需求后，DP 將為每個DC 提供相應(yīng)的數(shù)據(jù)產(chǎn)品，數(shù)據(jù)產(chǎn)品的屬性將是DP 可以提供的屬性與DC 的屬性需求的交集。例如，pj將為ck提供數(shù)據(jù)產(chǎn)品PCj,k，它的屬性集合為然后根據(jù)成本和效用，給出PCj,k的單價wj,k。收到數(shù)據(jù)產(chǎn)品的信息后，DC將根據(jù)其效用函數(shù)確定最合適的數(shù)據(jù)產(chǎn)品以及購買的數(shù)據(jù)量。DP 收到DC 的決定后將進(jìn)一步調(diào)整單價。通過多輪交互，確定最終的交易方案。AG 會將交易方案記錄在區(qū)塊鏈上，以解決可能發(fā)生的爭議。

在匹配過程中，需考慮2 個方面：DP 的效用函數(shù)和DC 的效用函數(shù)。

3.2 DP 的效用函數(shù)

DP 的效用函數(shù)主要考慮數(shù)據(jù)交易的收入、數(shù)據(jù)收集的成本以及數(shù)據(jù)質(zhì)量評估的成本，計算式為

其中，R(pj)表示pj的收入，L(pj)表示pj收集數(shù)據(jù)的成本，S(pj)表示ai為質(zhì)量評估收取的費(fèi)用。R(pj)的計算式為

其中，xj,k和wj,k分別表示ck從pj處購買數(shù)據(jù)的數(shù)量和單價。

對于數(shù)據(jù)收集成本，不同的屬性通常需要不同的收集設(shè)備，因此成本也有所不同。將收集第e個屬性的單位成本表示為be，，則pj的數(shù)據(jù)收集成本為

ai將對pj的數(shù)據(jù)采樣并進(jìn)行質(zhì)量評估，評估費(fèi)用與采樣數(shù)據(jù)的數(shù)量成正比。因此，質(zhì)量評估的成本為

其中，χ是單位數(shù)據(jù)評估的價格，β是采樣比例。

DC 購買數(shù)據(jù)主要是為了建立數(shù)據(jù)挖掘模型，其中分類和回歸是數(shù)據(jù)挖掘的2 個主要類別。ai考慮與客戶體驗相關(guān)的績效指標(biāo)，使用所有采樣數(shù)據(jù)和歷史數(shù)據(jù)建立模型，以評估DP 數(shù)據(jù)的質(zhì)量。對于分類問題，將分類準(zhǔn)確性（即正確預(yù)測結(jié)果的比例）作為性能指標(biāo)。對于回歸問題，使用基于絕對誤差的滿意率作為性能指標(biāo)。以pj為例，ai將使用(p1,…,pj?1,pj+1,…,pJ)的采樣數(shù)據(jù)及其自身的歷史數(shù)據(jù)訓(xùn)練模型，并將pj的屬性作為標(biāo)簽依次進(jìn)行測試。

其中，yn、和分別表示數(shù)據(jù)樣本的真實值、預(yù)測值和絕對預(yù)測誤差；τ是預(yù)設(shè)閾值，表示預(yù)測的最大容限；函數(shù)n(?)用來計算滿足條件的數(shù)據(jù)樣本數(shù)。

為了確保采樣的數(shù)據(jù)可以代表完整的數(shù)據(jù)，β的取值至關(guān)重要。為確定β的取值，首先定義欺騙。如果DP 在L條數(shù)據(jù)中包含了l條偽造數(shù)據(jù)，并且AG 從DP 處抽取了d條數(shù)據(jù)，但是這些采樣數(shù)據(jù)中不包含偽造數(shù)據(jù)，那么DP 成功欺騙了AG。DP 成功欺騙AG 的概率為

AG 的公平性對數(shù)據(jù)質(zhì)量評估有很大影響，為保證AG 能夠公平地進(jìn)行質(zhì)量評估，本文采用如下的評價方式。ck購買了pj提供的產(chǎn)品PCj,k，如果ck使用PCj,k進(jìn)行訓(xùn)練得到的模型準(zhǔn)確率rj,k與ai給出的數(shù)據(jù)質(zhì)量評估rj之間的差距超過約定的閾值σ，即rj?rj,k≥σ，則ck可以對ai進(jìn)行投訴。在一段時間內(nèi)，如果ai受到的投訴累積量大于閾值?，則ai會被認(rèn)為是不公平的，它將會被裁撤。

3.3 DC 的效用函數(shù)

DC 從DP 處購買數(shù)據(jù)，以滿足自己的需求，并為此付費(fèi)。因此，DC 的效用函數(shù)由2 個部分組成：滿意度函數(shù)和成本函數(shù)，計算式為

其中，ST(ck)表示ck的滿意度函數(shù)，參考文獻(xiàn)[17]中的構(gòu)造方式，其計算式為

ST(ck)的構(gòu)造考慮了數(shù)據(jù)購買量、數(shù)據(jù)的屬性及質(zhì)量、ck的個人偏好、DC 之間的競爭性等方面的因素。首先，ST 是數(shù)據(jù)購買量的單調(diào)遞增函數(shù)，并且隨著購買數(shù)量的增長，ST 的增長速度越來越慢，這是因為數(shù)據(jù)中所包含的信息熵增長越來越慢[25]。DP 所提供的數(shù)據(jù)具有不同的屬性和質(zhì)量，屬性越豐富，數(shù)據(jù)質(zhì)量越高，越能夠帶來有效的數(shù)據(jù)量。數(shù)據(jù)屬性的豐富程度用屬性相關(guān)性qj,k來度量，屬性越豐富，qj,k越高。數(shù)據(jù)質(zhì)量用rj來表示。此外，ck的個人偏好也會對ST(ck)產(chǎn)生影響，用λk來表示ck的個人偏好程度，λk可以根據(jù)ck的需求、習(xí)慣等來定義。例如，經(jīng)常出差的人更喜歡天氣預(yù)報服務(wù)。DC 之間的競爭性采用屬性需求的相似度來度量，2 個DC 的數(shù)據(jù)屬性需求越相似，他們之間具有競爭業(yè)務(wù)的可能性就越大，從而對DC 滿意度的負(fù)面影響也越大。利用Jaccard 相似系數(shù)，定義其他DC 對ck的影響參數(shù)ak為

計算屬性相似度實際上是計算2 個集合之間的相似度，因此采用了Jaccard 相似系數(shù)進(jìn)行計算。

消費(fèi)者ck具有屬性要求，但是在某些情況下，DP 可能無法完全滿足DC 的需求。當(dāng)屬性需求未完全滿足時，數(shù)據(jù)仍然可用，但需要更多數(shù)據(jù)才能達(dá)到相同的效果，qj,k表示pj提供的數(shù)據(jù)對ck的可用性。當(dāng)ck對數(shù)據(jù)屬性與其任務(wù)的相關(guān)性沒有一定的了解，或者認(rèn)為數(shù)據(jù)的每個屬性的相關(guān)性一致時，qj,k可以表示為

其中，θk是ck根據(jù)相關(guān)知識或經(jīng)驗設(shè)置的閾值。

在實際的數(shù)據(jù)挖掘過程中，數(shù)據(jù)屬性的相關(guān)性是不一致的。如果ck曾經(jīng)執(zhí)行過相關(guān)的數(shù)據(jù)挖掘任務(wù)，他將對數(shù)據(jù)屬性的相關(guān)性有一定的了解。設(shè)第f個屬性的相關(guān)性為δf，qj,k可更新為

上述描述定義了DP 和DC 的效用函數(shù)，在數(shù)據(jù)交易過程中他們都以最大化自身的效用為目標(biāo)。

3.4 數(shù)據(jù)交易匹配模型

在交易過程中，DP 首先提供產(chǎn)品和價格，可以看作交易的領(lǐng)導(dǎo)者，隨后，DC 根據(jù)DP 所提供的信息做出自己的購買決策，可以看作交易的跟隨者。因此，為了優(yōu)化DP 和DC 的效用函數(shù)，建立了一個涉及多個領(lǐng)導(dǎo)者（所有DP）和多個跟隨者（所有DC）的雙層優(yōu)化問題（BLPP,bi-level programming problem）。在上層，DP 根據(jù)DC 的屬性需求提供相應(yīng)的數(shù)據(jù)產(chǎn)品，并給出單價，以最大化其效用。在下層，DC 以最大化自身的效用為目標(biāo)，通過自我選擇過程做出購買決定。上述問題的模型可以表示如下。

1)上層：DP 的決策

DP 的決策變量是為每個DC 提供的數(shù)據(jù)產(chǎn)品的單價。

2)下層：DC 的決策

DC 的決策變量是從某個DP 處購買的數(shù)據(jù)量。

3.5 求解算法

BLPP 描述了現(xiàn)實世界中自然發(fā)生的層次結(jié)構(gòu)，但是很難求解，甚至最簡單的線性雙層規(guī)劃問題也被證明是NP 難的[26]。由于所提模型涉及許多變量和非線性的效用函數(shù)，且下層目標(biāo)函數(shù)是非凸的，因此很難使用經(jīng)典算法求解[27]。在下層，DC遍歷DP 的產(chǎn)品，可以得出最優(yōu)的決策。在得到DC 的決策后，BLPP 問題就退化為單個多目標(biāo)優(yōu)化問題。因此，本文提出了基于NSGAII 的BLPP求解方案。

NSGAII 算法是一種中心化的優(yōu)化算法，由一個節(jié)點來計算所有的目標(biāo)函數(shù)，需要知曉DP 和DC的完整參數(shù)（如be、、λk、qj,k等）來計算U(pj)和U(ck)。這些信息中包含了DP 和DC的隱私。因此，本文對NSGAII 進(jìn)行了改進(jìn)，提出了協(xié)作式NSGAII 算法，U(pj)和U(ck)分別由DP和DC 在本地進(jìn)行計算，以免泄露隱私。DP 負(fù)責(zé)種群的產(chǎn)生，即提供給DC 的產(chǎn)品的價格，以及種群的遺傳和變異。DC 從DP 提供的產(chǎn)品中進(jìn)行選擇，以決策從哪個DP 購買產(chǎn)品和所購買的數(shù)據(jù)量。AG負(fù)責(zé)非支配的排序，它可以避免DP 的一些自私行為產(chǎn)生的影響，例如欺詐性排序等，還可以加快算法的收斂速度。T和Genmax是需要設(shè)置的參數(shù)，T是種群中的個體數(shù)；Genmax是最大迭代次數(shù)，用來限制算法的迭代次數(shù)，當(dāng)?shù)螖?shù)達(dá)到Genmax時，算法會終止運(yùn)行，并輸出結(jié)果。協(xié)作式NSGAII 如算法1 所示。

本文所提交易匹配算法中，每次迭代內(nèi)的計算復(fù)雜度是O(JT2)，迭代進(jìn)行的最大次數(shù)是Genmax，因此匹配算法的計算復(fù)雜度是O(GenmaxJT2)。

4 安全性分析和實驗結(jié)果

4.1 安全性分析

本文所提基于聯(lián)盟區(qū)塊鏈的數(shù)據(jù)交易框架通過加密算法、數(shù)字簽名等技術(shù)，可以滿足以下與區(qū)塊鏈相關(guān)的安全要求。

1)避免不可信第三方造成的數(shù)據(jù)泄露。在基于區(qū)塊鏈的交易框架中，DP 會將數(shù)據(jù)產(chǎn)品直接傳輸給DC，避免了不可信第三方可能造成的數(shù)據(jù)泄露。

2)用戶身份隱私保護(hù)。鏈上的交易記錄中記錄的都是DP 和DC 的錢包地址，而通過錢包地址很難挖掘出用戶的真實身份。

3)數(shù)據(jù)不可篡改。聯(lián)盟區(qū)塊鏈的分散性質(zhì)與數(shù)字簽名相結(jié)合，確保了區(qū)塊鏈上的數(shù)據(jù)不會被篡改。

4)沒有雙花。數(shù)字貨幣依靠數(shù)字簽名來證明所有權(quán)以及公開的交易歷史，可以防止雙花。

同時，交易框架中一些機(jī)制的設(shè)定，也可以進(jìn)一步保證交易的安全性與公平性。

1)交易過程中，DP 僅需提供數(shù)據(jù)的屬性和數(shù)據(jù)量信息，DC 僅需提供屬性需求信息，這些信息中并不包含可能泄露用戶身份的隱私數(shù)據(jù)，這一設(shè)定有助于保護(hù)用戶的身份隱私。

2)AG 對DP 數(shù)據(jù)的質(zhì)量評估需要采樣DP 的數(shù)據(jù)，這部分?jǐn)?shù)據(jù)可能被泄露。為保證采樣數(shù)據(jù)能夠代表完整的數(shù)據(jù)，并且盡量少地泄露DP 的數(shù)據(jù)，需要設(shè)定合適的采樣比例。為此，本文計算了不同采樣比例下成功欺騙的概率。圖3 展示了不同偽造數(shù)據(jù)占比的情況下，成功欺騙的概率隨采樣比例的變化。在偽造數(shù)據(jù)占比為0.2%、1%和2%的情況下，很難通過低的采樣率來得到較低的欺騙成功率，但此時偽造數(shù)據(jù)對數(shù)據(jù)集的影響也很小。當(dāng)偽造數(shù)據(jù)的占比達(dá)到5%、采樣比例為5%時，成功欺騙的概率只有0.72%，這能夠滿足AG 的需求，而且5%的數(shù)據(jù)泄露對DP 來說也是可接受的[19]。

圖3 不同偽造數(shù)據(jù)占比的情況下，成功欺騙的概率隨采樣比例的變化

3)在執(zhí)行交易匹配算法時，由AG 進(jìn)行非支配排序，相比于選定某一個DP 或DC 進(jìn)行排序，可以保證排序的公平性，從而維護(hù)所有DP 與DC 的效用。為此設(shè)計了以下實驗，分別由AG 和隨機(jī)選取的某個DP（實驗中選取了DP1）進(jìn)行非支配排序，DP 在排序時會進(jìn)行欺詐排序，即將自己的出價排在上層，實驗結(jié)果如圖4 所示。

圖4 AG 和DP1分別進(jìn)行排序時效用函數(shù)的對比

從圖4 中可以看出，當(dāng)DP1進(jìn)行排序時，可以提高自己的效用，但會使DP 和DC 的平均效用下降，即損失了其他DP 和DC 的效用。因此，采用AG 進(jìn)行排序有助于維護(hù)所有DP 與DC 的效用。

4.2 實驗結(jié)果

實驗使用北京的空氣質(zhì)量數(shù)據(jù)來提供空氣質(zhì)量預(yù)測服務(wù)[28]。該數(shù)據(jù)集包括12 個空氣質(zhì)量監(jiān)測站點的空氣污染物數(shù)據(jù)，每個監(jiān)測站點被視為一個DP。空氣質(zhì)量數(shù)據(jù)來自北京市環(huán)境監(jiān)測中心。每個空氣質(zhì)量監(jiān)測站點的氣象數(shù)據(jù)均與最近的氣象站相匹配。時間段是從2013 年3 月1 日到2017 年2 月28 日。每個數(shù)據(jù)集都包含35 064 條數(shù)據(jù)樣本。每條樣本包含時間、PM2.5、PM10、SO2含量等17 種屬性。為了使這12 個DP 的數(shù)據(jù)產(chǎn)生顯著差異，實驗中刪除了某些DP 數(shù)據(jù)的一些屬性，并給數(shù)據(jù)集加入了不用程度的噪聲。在實驗過程中，設(shè)AG 的采樣比例為5%，即β=5%。AG 使用經(jīng)典的機(jī)器學(xué)習(xí)算法（隨機(jī)森林回歸算法）進(jìn)行數(shù)據(jù)質(zhì)量評估。實驗虛擬了100 個DC，即K=100。在DC 中，一半DC 是經(jīng)驗豐富的，具有屬性相關(guān)性的知識，利用式(12)進(jìn)行計算；另一半DC 沒有經(jīng)驗，利用式(11)進(jìn)行計算。設(shè)定1 000 條數(shù)據(jù)樣本為單位數(shù)據(jù)。

為了展示協(xié)作式NSGAII 的收斂性，圖5 和圖6分別給出了DP 和DC 的效用隨迭代次數(shù)的變化。

圖5 DP 的效用隨迭代次數(shù)的變化

圖6 DC 的效用隨迭代次數(shù)的變化

從圖5 和圖6 可以看出，隨著迭代次數(shù)的增多，DP 和DC 的效用都逐漸增長。當(dāng)達(dá)到一定的迭代次數(shù)后，DP 和DC 的效用逐漸趨于穩(wěn)定。從所有DP和DC 的平均效用來看，算法在30 次之內(nèi)可以達(dá)到收斂。就迭代次數(shù)而言，30 次是滿足用戶需求可接受的數(shù)量。

為了體現(xiàn)效用函數(shù)的靈敏性，實驗中對DP 和DC 進(jìn)行了差異化處理。針對DP，對數(shù)據(jù)的屬性和數(shù)量進(jìn)行了調(diào)整，有些DP 只能提供一部分屬性，并且在數(shù)據(jù)集中增加了不同程度的噪聲。為模擬不同DC 的需求，實驗中設(shè)定了多樣化的屬性需求、數(shù)據(jù)量需求、偏好以及對屬性相關(guān)性是否熟悉等參數(shù)。DP 和DC 的效用函數(shù)分別如圖7 和圖8 所示。

從圖7 和圖8 可以看出，實驗中對DP 和DC的差異化處理在他們的效用上得到了體現(xiàn)，這說明效用函數(shù)對DP 和DC 的參數(shù)具有靈敏性。

為了驗證協(xié)作式NSGAII 的可擴(kuò)展性，圖9 和圖10分別給出了迭代次數(shù)隨DP 和DC 數(shù)量增長的變化。

圖7 DP 的效用函數(shù)

圖8 DC 的效用函數(shù)

圖9 迭代次數(shù)隨DP 數(shù)量增長的變化

圖10 迭代次數(shù)隨DC 數(shù)量增長的變化

從圖9 可以看出，隨著DP 數(shù)量的增加，迭代次數(shù)也隨之增加，并且兩者近似成正比。從圖10可以看出，隨著DC 數(shù)量的增加，迭代次數(shù)的增長速度逐漸減慢并最終趨于穩(wěn)定。根據(jù)對數(shù)據(jù)交易市場的調(diào)研發(fā)現(xiàn)，對于特定類型的數(shù)據(jù)，數(shù)據(jù)市場基本是寡頭市場的形式，DP 的數(shù)量不會太多，因此不會導(dǎo)致迭代次數(shù)的大幅增加。而對于DC 的增加，該算法具有很好的收斂性。這表明協(xié)作式NSGAII是可擴(kuò)展的，可以應(yīng)用于大規(guī)模的用戶。

在模型的構(gòu)建中，考慮了數(shù)據(jù)屬性的影響。當(dāng)不能完全滿足DC 屬性需求或完全滿足屬性需求的數(shù)據(jù)價格過高時，DC 可以通過使用較低的價格來購買較少屬性的數(shù)據(jù)以提升自身的效用。具有較少屬性的DP 可以通過使用較低的價格將數(shù)據(jù)賣給更多的DC，從而提升效用。為了驗證這種考慮是否有助于提高DP 和DC 的效用，圖11 和圖12 分別給出了DP 和DC 的效用對比。

圖11 DP 的效用對比

圖12 DC 的效用對比

圖11 中，DP1～DP6是從12 個DP 中選取的6 個，他們在數(shù)據(jù)屬性、數(shù)據(jù)數(shù)量及添加的噪聲方面存在區(qū)別，具體參數(shù)如表2 所示。

表2 DP 的具體參數(shù)

表2 中，每單元包含1 000 條數(shù)據(jù)，增加的高斯白噪聲分別為Ⅰ、Ⅱ、Ⅲ和Ⅳ這4 個等級，對應(yīng)的噪聲量分別為0～2%、4%～6%、8%～10%和12%～14%。

圖12 中，DC1～DC6是從100 個DC 中選取的6 個，他們在屬性需求、數(shù)據(jù)量需求、個人偏好等方面存在區(qū)別，具體參數(shù)如表3 所示。

表3 DC 的具體參數(shù)

從實驗結(jié)果可以看出，協(xié)作式NSGAII 取得了很好的效果。最大屬性匹配算法是DC 將購買最能滿足其屬性需求的數(shù)據(jù)產(chǎn)品。在應(yīng)用最大屬性匹配算法的情況下，從DC 的角度來看，他們的產(chǎn)品選擇要小得多，因此他們可能無法實現(xiàn)最高的效用。從DP 的角度來看，具有豐富屬性的DP 將出售更多的數(shù)據(jù)，而具有較少屬性的DP 則難以出售數(shù)據(jù)，最終降低了總體效用。因此，考慮數(shù)據(jù)屬性在數(shù)據(jù)匹配過程中的影響，對DP 和DC 的效用函數(shù)具有一定的改善作用。

在實際的數(shù)據(jù)挖掘中，數(shù)據(jù)屬性與任務(wù)的相關(guān)性對最終的模型具有很大的影響。在某些實驗中，甚至使用PCA 等算法過濾掉一些屬性。相關(guān)性的考慮可以促使DC 選擇具有更大相關(guān)性的屬性，使用較少的屬性來獲得更好的數(shù)據(jù)挖掘結(jié)果，從而降低成本并提高效用。為了顯示這種效果，圖13 給出了是否考慮相關(guān)性的情況下DC 效用的對比。

圖13 是否考慮相關(guān)性的情況下DC 效用的對比

從圖13 可以看出，通過考慮屬性的相關(guān)性，DC 的效用得到了改善。

為了進(jìn)一步展示協(xié)作式NSGAII 的有效性，將它與其他幾種算法進(jìn)行了比較。時間匹配算法是區(qū)塊鏈系統(tǒng)中常見的基于時間戳的匹配方案。數(shù)據(jù)質(zhì)量匹配算法是Yu 等[13]提出的基于數(shù)據(jù)質(zhì)量的匹配算法。社會福利最大化是Cao 等[11]提出的一種社會福利最大化的數(shù)據(jù)交易算法。利潤最大化是Jiao 等[12]提出的一種以最大化代理利潤為目標(biāo)的匹配算法。DP 和DC 的平均效用在不同算法上的對比分別如圖14 和圖15 所示。

圖15 DC 的平均效用在不同算法上的對比

從圖14 和圖15 中可以看出，協(xié)作式NSGAII取得了最佳效果，它綜合考慮了數(shù)據(jù)質(zhì)量、數(shù)據(jù)屬性、屬性相關(guān)性以及消費(fèi)者競爭的影響，使DC 和DP能夠根據(jù)自身的情況更細(xì)粒度地執(zhí)行數(shù)據(jù)交易，從而提升了他們的效用。

為進(jìn)一步展示協(xié)作式NSGAII 的效果，將它的實驗結(jié)果與Gurobi 優(yōu)化工具箱的結(jié)果進(jìn)行了對比，結(jié)果如圖16 所示。

圖16 協(xié)作式NSGAII 與Gurobi 的對比

Gurobi 優(yōu)化工具箱是一種應(yīng)用廣泛的優(yōu)化問題求解工具箱，它的計算結(jié)果可以認(rèn)為已經(jīng)接近全局最優(yōu)解。從實驗結(jié)果可以看出，協(xié)作式NSGAII 的實驗結(jié)果與Gurobi 的結(jié)果極其相近，這在某種程度上說明了協(xié)作式NSGAII 的實驗結(jié)果很接近全局最優(yōu)解。

5 結(jié)束語

為了提高數(shù)據(jù)交易的有效性，本文提出了一種基于聯(lián)盟區(qū)塊鏈的分布式交易框架。該框架可在不依賴第三方的情況下實現(xiàn)DP和DC之間P2P的數(shù)據(jù)交易。在此框架下，本文還提出了雙層多目標(biāo)優(yōu)化模型，以優(yōu)化DP 和DC 的效用函數(shù)，模型構(gòu)建過程中考慮了數(shù)據(jù)屬性、數(shù)據(jù)質(zhì)量、屬性相關(guān)性以及消費(fèi)者競爭的影響。為求解此模型，提出了一種協(xié)作式NSGAII，通過DC、DP 和AG 的合作來得到該模型的解。最后，基于北京空氣質(zhì)量數(shù)據(jù)的實驗表明，所提算法在DP和DC 的效用函數(shù)方面可以實現(xiàn)更好的性能。