一種基于社會(huì)網(wǎng)絡(luò)的可信服務(wù)最大覆蓋方法＊

張佩云，黃 波，宮秀文

（1.安徽師范大學(xué)數(shù)學(xué)計(jì)算機(jī)科學(xué)學(xué)院，安徽 蕪湖241003；2.中國(guó)科學(xué)技術(shù)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，安徽 合肥230026；3.南京理工大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，江蘇 南京210094）

1 引言

隨著社會(huì)網(wǎng)絡(luò)技術(shù)的快速發(fā)展，社會(huì)網(wǎng)絡(luò)正日益成為用戶進(jìn)行服務(wù)獲取和交互的重要平臺(tái)，社會(huì)網(wǎng)絡(luò)作為一種非中心化的分布式網(wǎng)絡(luò)（起源于Mi-gram的“六度分隔理論”），其所擁有的龐大用戶群和服務(wù)為可信服務(wù)覆蓋帶來(lái)了巨大的機(jī)遇，也帶來(lái)了挑戰(zhàn)。相對(duì)于集中式機(jī)制而言，社會(huì)網(wǎng)絡(luò)為服務(wù)覆蓋提供了新的運(yùn)行環(huán)境，在社會(huì)網(wǎng)絡(luò)環(huán)境下，服務(wù)信息組織的主體、服務(wù)傳播和利用方式等發(fā)生了新變化，面對(duì)大量用戶節(jié)點(diǎn)和服務(wù)，服務(wù)覆蓋面臨著如何快速在社會(huì)網(wǎng)絡(luò)中實(shí)現(xiàn)服務(wù)最大覆蓋和可信服務(wù)覆蓋等問(wèn)題。國(guó)內(nèi)外相關(guān)研究如下。

（1）可信服務(wù)研究。在可信服務(wù)研究方面，為降低應(yīng)用服務(wù)的風(fēng)險(xiǎn)，國(guó)內(nèi)外研究者通過(guò)建立多種信任模型和方法來(lái)評(píng)估服務(wù)信任，文獻(xiàn)［1］指出社會(huì)網(wǎng)絡(luò)服務(wù)面臨著不斷增加的信任安全問(wèn)題，提出社會(huì)網(wǎng)絡(luò)動(dòng)態(tài)模型，并利用該模型分析社會(huì)網(wǎng)絡(luò)服務(wù)的惡意信任擴(kuò)張行為；文獻(xiàn)［2］提出了社會(huì)網(wǎng)絡(luò)中信任感知的傳播模型等；文獻(xiàn)［3］通過(guò)共享服務(wù)提供者與peers的經(jīng)驗(yàn)以在面向服務(wù)的環(huán)境中建立信任；文獻(xiàn)［4，5］研究了社會(huì)網(wǎng)絡(luò)中節(jié)點(diǎn)信任關(guān)系和服務(wù)的信任度計(jì)算方法。國(guó)內(nèi)外研究者在可信服務(wù)計(jì)算相關(guān)方面做了一些有益的研究工作。

（2）最大覆蓋研究。在最大覆蓋研究上，相關(guān)主要研究工作有：文獻(xiàn)［6］討論了一般最大覆蓋問(wèn)題，并給出了拉格朗日松弛算法；文獻(xiàn)［7］針對(duì)容量限制、收費(fèi)及有競(jìng)爭(zhēng)力的位置選址問(wèn)題，研究了最大覆蓋問(wèn)題的遺傳算法操作策略及應(yīng)用；文獻(xiàn)［8］認(rèn)為部分覆蓋可以采用一些啟發(fā)式算法如模擬退火算法等對(duì)這類問(wèn)題求解；文獻(xiàn)［9］討論了啟發(fā)式方法解決集合覆蓋問(wèn)題；文獻(xiàn)［10］研究了傳感器網(wǎng)絡(luò)的最大有向覆蓋問(wèn)題，通過(guò)傳感器網(wǎng)絡(luò)在地理位置上的特殊性，實(shí)現(xiàn)每個(gè)方向有限角度的覆蓋感應(yīng)。此外，在信息擴(kuò)散與傳播方面，文獻(xiàn)［11～13］研究了信息擴(kuò)散模型，文獻(xiàn)［14，15］研究了信息傳播方式等。國(guó)內(nèi)外研究者已有的研究工作對(duì)本文研究有所啟發(fā)，與以往研究不同，本文研究的是社會(huì)網(wǎng)絡(luò)環(huán)境下可信服務(wù)的最大覆蓋問(wèn)題，通過(guò)社會(huì)網(wǎng)絡(luò)、可信服務(wù)及最大覆蓋三種要素相互作用與影響，利用遺傳算法發(fā)現(xiàn)最優(yōu)覆蓋路徑，解決覆蓋中存在的NP問(wèn)題，并在指定的服務(wù)覆蓋半徑下，通過(guò)可信服務(wù)覆蓋算法，以較少的時(shí)間向其他節(jié)點(diǎn)進(jìn)行服務(wù)覆蓋，并實(shí)現(xiàn)社會(huì)網(wǎng)絡(luò)的可信服務(wù)最大覆蓋。

2 基本概念、定義與可信服務(wù)覆蓋模型

2.1 基本概念

社會(huì)網(wǎng)絡(luò)節(jié)點(diǎn)可以指具體的個(gè)人，也可指一個(gè)群體、公司或其他集體性的社會(huì)單位，其在社會(huì)網(wǎng)絡(luò)中的位置被稱為“節(jié)點(diǎn)”（node）。

社會(huì)網(wǎng)絡(luò)方便了用戶使用服務(wù)，但由于社會(huì)網(wǎng)絡(luò)中也可能存在著不可信的社會(huì)網(wǎng)絡(luò)節(jié)點(diǎn)及不可信的服務(wù)，導(dǎo)致用戶面對(duì)大量服務(wù)信息而無(wú)法判斷其可靠性，因此，基于作者前期所研究的社會(huì)網(wǎng)絡(luò)節(jié)點(diǎn)信任度及服務(wù)信任度成果［5］，選擇可信節(jié)點(diǎn)和可信服務(wù)對(duì)其他社會(huì)網(wǎng)絡(luò)節(jié)點(diǎn)進(jìn)行服務(wù)覆蓋，解決社會(huì)網(wǎng)絡(luò)的虛擬性而導(dǎo)致虛假服務(wù)覆蓋問(wèn)題。

2.2 社會(huì)網(wǎng)絡(luò)可信服務(wù)覆蓋模型

社會(huì)網(wǎng)絡(luò)節(jié)點(diǎn)存在著強(qiáng)弱不同、種類不同的區(qū)別，在服務(wù)覆蓋過(guò)程中有不同的作用效果。為提高服務(wù)覆蓋性能，提出社會(huì)網(wǎng)絡(luò)服務(wù)覆蓋模型思想：把社會(huì)網(wǎng)絡(luò)節(jié)點(diǎn)分成兩個(gè)子集，分別為優(yōu)勢(shì)節(jié)點(diǎn)子集和普通節(jié)點(diǎn)子集，通過(guò)節(jié)點(diǎn)尋優(yōu)獲取優(yōu)勢(shì)節(jié)點(diǎn)子集，并設(shè)計(jì)路徑尋優(yōu)及服務(wù)覆蓋算法，通過(guò)該子集的節(jié)點(diǎn)將可信服務(wù)覆蓋到其他社會(huì)網(wǎng)絡(luò)節(jié)點(diǎn)。基于社會(huì)網(wǎng)絡(luò)服務(wù)覆蓋模型思想。相關(guān)定義如下。

定義1 社會(huì)網(wǎng)絡(luò)可信服務(wù)最大覆蓋：對(duì)于一個(gè)給定的社會(huì)網(wǎng)絡(luò)服務(wù)信息關(guān)系圖G，V為G中節(jié)點(diǎn)集，SList為社會(huì)網(wǎng)絡(luò)節(jié)點(diǎn)的服務(wù)列表，可信服務(wù)集記為T(mén)S，TS?SList，給定優(yōu)勢(shì)節(jié)點(diǎn)集A，A?V，從A中選擇一個(gè)目標(biāo)子集Z，使得通過(guò)Z盡可能大地對(duì)V進(jìn)行可信服務(wù)覆蓋（即將可信服務(wù)信息最大范圍地傳播并覆蓋到社會(huì)網(wǎng)絡(luò)中）。要求滿足：（1）?vi∈Z且vi信任度大于節(jié)點(diǎn)信任度閾值；（2）?s∈TS且s信任度大于服務(wù)信任度閾值。用 ∪cover（vj｜vj∈V）表示通過(guò)優(yōu)勢(shì)節(jié)點(diǎn)集Z實(shí)現(xiàn)可信服務(wù)覆蓋的社會(huì)網(wǎng)絡(luò)節(jié)點(diǎn)總個(gè)數(shù)，其中cover（vj｜vj∈V）表示通過(guò)社會(huì)網(wǎng)絡(luò)節(jié)點(diǎn)vi實(shí)現(xiàn)可信服務(wù)覆蓋的社會(huì)網(wǎng)絡(luò)節(jié)點(diǎn)vj的個(gè)數(shù)。

基于定義1，可信服務(wù)覆蓋率（cRate）的計(jì)算公式如式（1）所示。

cRate是檢驗(yàn)本文方法效果的一個(gè)重要指標(biāo)。

3 社會(huì)網(wǎng)絡(luò)可信服務(wù)最大覆蓋算法

3.1 尋找最優(yōu)覆蓋路徑

最優(yōu)覆蓋路徑由子路徑組成，引入服務(wù)覆蓋子路徑，其定義如下。

定義2 服務(wù)覆蓋子路徑（記為subpath）：對(duì)于給定的覆蓋路徑R（以離散值表示），尋找以R為半徑、以v1為覆蓋源的一條服務(wù)覆蓋子路徑，表示為：“v1，v2，v3，v4，…，vR－1，vR”的一個(gè)序列，如下所示：

在subpath中，路徑長(zhǎng)度等于服務(wù)覆蓋半徑R，表示以優(yōu)勢(shì)節(jié)點(diǎn)為圓心，半徑為R的徑向社會(huì)網(wǎng)絡(luò)節(jié)點(diǎn)個(gè)數(shù)，v1為社會(huì)網(wǎng)絡(luò)優(yōu)勢(shì)節(jié)點(diǎn)層中的優(yōu)勢(shì)節(jié)點(diǎn)，v2為v1的鄰居列表（NeighborList）中的節(jié)點(diǎn)，依此類推，vR為vR－1的鄰居列表中的節(jié)點(diǎn)，從v1到vR的subpath是可達(dá)的。

定義3 覆蓋路徑的服務(wù)覆蓋量（記為χ（p））：指通過(guò)源節(jié)點(diǎn)vi將服務(wù)列表（SList）覆蓋其鄰居節(jié)點(diǎn)，且其鄰居節(jié)點(diǎn)沿著路徑p對(duì)其他節(jié)點(diǎn)進(jìn)行服務(wù)覆蓋，直到路徑的末尾，在此服務(wù)覆蓋過(guò)程中統(tǒng)計(jì)的服務(wù)覆蓋量稱為χ（p）。

定義4 覆蓋路徑的信任度（記為trust（p））：指通過(guò)源節(jié)點(diǎn)vi將服務(wù)列表（SList）覆蓋其鄰居節(jié)點(diǎn)，且其鄰居節(jié)點(diǎn)沿著路徑p對(duì)其他節(jié)點(diǎn)進(jìn)行服務(wù)覆蓋，直到路徑的末尾，在此服務(wù)覆蓋過(guò)程中統(tǒng)計(jì)的信任度稱為trust（p）。

由于不同路徑結(jié)構(gòu)對(duì)χ（p）和trust（p）的計(jì)算有不同影響，因此有必要針對(duì)不同結(jié)構(gòu)的路徑予以討論。社會(huì)網(wǎng)絡(luò)中主要存在三種基本的路徑結(jié)構(gòu)，如圖1所示。

Figure 1 Three basic path structures圖1 三種基本的路徑結(jié)構(gòu)

圖1 中，v1，…，vn＋1表示路徑上的社會(huì)網(wǎng)絡(luò)節(jié)點(diǎn)；w1，…，wn表示分支路徑上的節(jié)點(diǎn)被服務(wù)覆蓋的概率，∑wn＝1；k表示循環(huán)路徑上循環(huán)的次數(shù)?？紤]到三種不同結(jié)構(gòu)的區(qū)別及特點(diǎn)，路徑p的服務(wù)覆蓋量與路徑p的信任度計(jì)算結(jié)果如表1所示。

Table 1 Path pwith different structures and trust service coverage degree表1 不同結(jié)構(gòu)路徑p的服務(wù)覆蓋量和信任度

表1中，ψ（T）（vj）表示社會(huì)網(wǎng)絡(luò)節(jié)點(diǎn)vj在0～T時(shí)間段內(nèi)將vj的服務(wù)信息覆蓋到vj鄰居節(jié)點(diǎn)的服務(wù)信息量大小，trust（vj）表示節(jié)點(diǎn)vj的信任度，p表示服務(wù)覆蓋路徑，n表示路徑p上社會(huì)網(wǎng)絡(luò)節(jié)點(diǎn)個(gè)數(shù)。

為獲得服務(wù)最大覆蓋及最優(yōu)覆蓋路徑，采用并行遺傳算法來(lái)搜索全局最優(yōu)解。遺傳算法具有并行計(jì)算、群體尋優(yōu)的特點(diǎn)，當(dāng)搜索空間很大、復(fù)雜和難以理解時(shí)，能有效地避免僅局部最優(yōu)，達(dá)到全局最優(yōu)。遺傳算法的設(shè)計(jì)離不開(kāi)目標(biāo)函數(shù)的設(shè)計(jì)，令目標(biāo)函數(shù)為objFunc（p），該目標(biāo)函數(shù)采用路徑p上服務(wù)覆蓋量和信任度構(gòu)成遺傳算法的目標(biāo)函數(shù)（見(jiàn)式（2）），以時(shí)間耗費(fèi)小于閾值作為約束條件（見(jiàn)式（3））。

式（2）中，χ′（p）和trust′（p）分別表示歸一化處理后路徑p的服務(wù)覆蓋量和信任度；w1與w2分別是其權(quán)重，w1＋w2＝1。χ′（p）與trust′（p）的計(jì)算公式分別如下。

式（4）中，χ（p）為路徑p 的服務(wù)覆蓋量，χmax（p）和χmin（p）分別表示路徑p的服務(wù)覆蓋量的最大值和最小值，其計(jì)算公式見(jiàn)表1。

式（5）中，trust（p）表示路徑p 的信任度，trustmax（p）和trustmin（p）分別表示路徑p的信任度的最大值和最小值，其計(jì)算公式見(jiàn)表1。

式（3）為目標(biāo)函數(shù)的約束，TIME表示對(duì)路徑p進(jìn)行服務(wù)覆蓋的時(shí)間閾值。time（p）表示對(duì)路徑p進(jìn)行服務(wù)覆蓋的時(shí)間代價(jià)，timemax（p）和timemin（p）分別表示路徑p的服務(wù)覆蓋時(shí)間代價(jià)的最大值和最小值。time（p）的計(jì)算公式如式（6）所示。

式（6）中，n 表 示 路 徑p 上 節(jié) 點(diǎn) 的 個(gè) 數(shù)，tp［i］.proc、tp［i］.inbuf、tp［i］.outbuf 分 別 表 示 路 徑 p上節(jié)點(diǎn)vi的服務(wù)覆蓋處理時(shí)間、服務(wù)信息獲取時(shí)間和服務(wù)信息輸出時(shí)間。

針對(duì)可信服務(wù)最大覆蓋問(wèn)題，結(jié)合遺傳算法的求解框架，設(shè)計(jì)尋找可信服務(wù)的最優(yōu)覆蓋路徑的算法，主要思想如下：

（1）將服務(wù)覆蓋路徑編碼為一個(gè)染色體，按服務(wù)覆蓋的次序排列的染色體對(duì)應(yīng)一條服務(wù)覆蓋路徑。覆蓋路徑上的社會(huì)網(wǎng)絡(luò)節(jié)點(diǎn)表示該染色體的一個(gè)基因（用節(jié)點(diǎn)序號(hào)表示），每個(gè)基因都包含每個(gè)社會(huì)網(wǎng)絡(luò)節(jié)點(diǎn)的相關(guān)信息，包括節(jié)點(diǎn)ID、節(jié)點(diǎn)鄰居節(jié)點(diǎn)、節(jié)點(diǎn)的服務(wù)列表、與其他節(jié)點(diǎn)的歷史交易信息等。采用簡(jiǎn)單易操作的二進(jìn)制編碼方式對(duì)基因編碼。由于需要由優(yōu)勢(shì)節(jié)點(diǎn)尋找其最優(yōu)覆蓋路徑，因此規(guī)定染色體的第一個(gè)基因?yàn)閮?yōu)勢(shì)節(jié)點(diǎn)。若兩個(gè)社會(huì)網(wǎng)絡(luò)節(jié)點(diǎn)不相鄰，但在染色體中其對(duì)應(yīng)的基因相鄰時(shí)，由于此基因的適應(yīng)度值趨于0，因此在之后的遺傳過(guò)程中將被淘汰。

（2）通過(guò)染色體之間的交叉、變異和選擇操作，產(chǎn)生更符合可信服務(wù)最大覆蓋的新染色體，反復(fù)執(zhí)行該過(guò)程，以在解空間中并行全局搜索，使得目標(biāo)函數(shù)objFunc（p）最大化，同時(shí)使相應(yīng)的時(shí)間約束條件得到滿足。

（3）最終將得到符合可信服務(wù)最大覆蓋的染色體，即得到滿足可信服務(wù)最大覆蓋的具體社會(huì)網(wǎng)絡(luò)節(jié)點(diǎn)序列。

尋找最優(yōu)覆蓋路徑算法（簡(jiǎn)稱BestCover-Path）如算法1所示。

算法1 尋找最優(yōu)覆蓋路徑（BestCoverPath）

輸入：覆蓋半徑R、社會(huì)網(wǎng)絡(luò)服務(wù)信任關(guān)系圖G、目標(biāo)節(jié)點(diǎn)集Target、GEN＿M(jìn)AX 、GEN＿NEAR。／＊Target表示包含有優(yōu)勢(shì)節(jié)點(diǎn)的節(jié)點(diǎn)集，GEN＿M(jìn)AX表示最大進(jìn)化代數(shù)，GEN＿NEAR為相鄰若干代的代數(shù)，用于計(jì)算相鄰若干代的種群平均適應(yīng)值的變化＊／

輸出：最優(yōu)覆蓋路徑p。

1. int Gen；／＊Gen保存進(jìn)化代數(shù)＊／

2. int k←R；／＊k為染色體基因的位數(shù)，等于覆蓋半徑R的長(zhǎng)度＊／

3. FOR（i＝1；i＜＝｜Target｜；i＋＋）

4. ｛IF（vi.Level＝＝1）／＊表示vi是優(yōu)勢(shì)節(jié)點(diǎn)＊／

5. THEN產(chǎn)生以vi編號(hào)為首基因、長(zhǎng)度為k的染色體；

6. ｝ENDFOR

7. ／＊判斷進(jìn)化代數(shù)是否小于最大進(jìn)化代數(shù)＊／

8. FOR （Gen＝0；（Gen＜ GEN＿M(jìn)AX｜｜σ＜1E－5）；Gen＋＋）

9. ｛／＊遺傳算法的終止條件是代數(shù)超過(guò)最大進(jìn)化代數(shù)或指定的GEN＿NEAR相鄰代數(shù)的種群平均適應(yīng)值的變化值σ小于10－5＊／

10. ／＊設(shè)計(jì)適應(yīng)度函數(shù)fitness＊／

11. fitness←objFunc（p）－λ＊punish（p）；

12. 采用精英策略選擇子代，并用每代中最優(yōu)個(gè)體取代下一代中最差個(gè)體；

13. 采用隨機(jī)選取斷點(diǎn)的兩點(diǎn)交叉，交叉概率Pc∈［0，1］；

14. 采用變異概率Pm∈（0，1）對(duì)個(gè)體隨機(jī)變異；

15. 把該個(gè)體放到種群中去；

16. σ←計(jì)算指定的GEN＿NEAR相鄰代數(shù)的種群平均適應(yīng)值的變化；

17. ｝ENDFOR

18. p←最優(yōu)解對(duì)應(yīng)的路徑；／＊將最優(yōu)解對(duì)應(yīng)的路徑保存在變量p中＊／

19. Return the best path p；

算法1在構(gòu)造適應(yīng)度函數(shù)時(shí)，為懲罰不滿足約束條件（THLD）的個(gè)體，將罰函數(shù)包括到適應(yīng)度函數(shù)中，以加速遺傳算法全局收斂并防止早熟終止。適應(yīng)度函數(shù)計(jì)算公式如下：

fitness＝objFunc（p）－λ＊punish（p） （7）其中，objFunc（p）來(lái)自式（2），λ是罰函數(shù)系數(shù)（值大于0），punish（p）為罰函數(shù)，其計(jì)算如式（8）所示：

其中，n表示路徑p上社會(huì)網(wǎng)絡(luò)節(jié)點(diǎn)的個(gè)數(shù)，vi為p 上社會(huì)網(wǎng)絡(luò)節(jié)點(diǎn)。ψ（T）（vi）的含義同表1，THLD表示vi節(jié)點(diǎn)的服務(wù)覆蓋量的閾值，THLD－ψ（T）（vi）表示節(jié)點(diǎn)vi的服務(wù)覆蓋量低于閾值的量；χmax（p）和χmin（p）分別表示路徑p的服務(wù)覆蓋量的最大值和最小值。

算法1在足夠大的遺傳種群與進(jìn)化代數(shù)時(shí)，能夠搜索出可行的可信服務(wù)最大覆蓋路徑。基于算法1所獲取的最優(yōu)覆蓋路徑進(jìn)行服務(wù)覆蓋時(shí)，可實(shí)現(xiàn)可信服務(wù)的最大覆蓋。

3.2 可信服務(wù)最大覆蓋

基于最優(yōu)覆蓋路徑進(jìn)行服務(wù)覆蓋時(shí)，需要在每個(gè)社會(huì)網(wǎng)絡(luò)節(jié)點(diǎn)執(zhí)行局部計(jì)算并與路徑上的鄰居節(jié)點(diǎn)交互（發(fā)送和接收服務(wù)msg）。在實(shí)現(xiàn)可信服務(wù)覆蓋的過(guò)程中，社會(huì)網(wǎng)絡(luò)節(jié)點(diǎn)的狀態(tài)在不斷地變化，每個(gè)社會(huì)網(wǎng)絡(luò)節(jié)點(diǎn)的狀態(tài)可構(gòu)成一個(gè)狀態(tài)集，對(duì)于節(jié)點(diǎn)vi，其狀態(tài)集用Qi表示，Qi中每個(gè)狀態(tài)包括2n個(gè)狀態(tài)變量：｛ini［1］，…，ini［n］，outi［1］，…，outi［n］｝。相關(guān)符號(hào)解釋如下：

（1）ini［k］（1≤k≤n）：表示節(jié)點(diǎn)vi的鄰居節(jié)點(diǎn)vk覆蓋到vi、但尚未經(jīng)vi內(nèi)部計(jì)算處理的服務(wù)信息的狀態(tài)。ini［k］取值可為0（表示狀態(tài)為假）或?yàn)?（表示狀態(tài)為真），其初始值為0，n表示節(jié)點(diǎn)vi的鄰居節(jié)點(diǎn)的個(gè)數(shù)。其中，ini［k］＝0表示沒(méi)有由鄰居節(jié)點(diǎn)vk覆蓋到vi節(jié)點(diǎn)的服務(wù)信息；ini［k］＝1表示有由鄰居節(jié)點(diǎn)vk覆蓋到vi節(jié)點(diǎn)的服務(wù)信息，且vi尚未處理這些服務(wù)信息。注意：vk在最優(yōu)覆蓋路徑上。

（2）outi［k］（1≤k≤n）：節(jié)點(diǎn)vi有服務(wù)信息給鄰居節(jié)點(diǎn)vk但尚未覆蓋到鄰居節(jié)點(diǎn)vk時(shí)的狀態(tài)。outi［k］取值可為0或?yàn)?，其中，outi［k］＝0表示狀態(tài)為假，節(jié)點(diǎn)vi沒(méi)有服務(wù)信息準(zhǔn)備覆蓋到鄰居節(jié)點(diǎn)vk；outi［k］＝1表示狀態(tài)為真，節(jié)點(diǎn)vi有服務(wù)信息準(zhǔn)備覆蓋到鄰居節(jié)點(diǎn)。

基于狀態(tài)集用Qi可以實(shí)現(xiàn)節(jié)點(diǎn)間的異步通信。本文的可信服務(wù)覆蓋是基于優(yōu)勢(shì)節(jié)點(diǎn)進(jìn)行的，優(yōu)勢(shì)節(jié)點(diǎn)作為可信服務(wù)覆蓋的源點(diǎn)，其可信服務(wù)來(lái)源于三個(gè)部分：（1）可信的服務(wù)提供商直接提供的服務(wù)；（2）來(lái)自該節(jié)點(diǎn)可信任的鄰居節(jié)點(diǎn)；（3）來(lái)自優(yōu)勢(shì)節(jié)點(diǎn)調(diào)用過(guò)的可信服務(wù)，該服務(wù)信息直接保存在該節(jié)點(diǎn)的服務(wù)列表SList中。為向優(yōu)勢(shì)節(jié)點(diǎn)vi匯集可信服務(wù)，下面設(shè)計(jì)getServices（vi）函數(shù)，該函數(shù)的主要過(guò)程如下：

1.向節(jié)點(diǎn)vi匯聚服務(wù)提供商（ServiceProvider）提供的服務(wù)（SList），判斷服務(wù)提供商信任度是否大于閾值TRUST，如果大于TRUST，則：vi.SList←vi.SList∪ServiceProvider.SList；

2.／＊下面向vi節(jié)點(diǎn)匯聚其可信鄰居節(jié)點(diǎn)的可信服務(wù)信息＊／

3. M＝｜vi.NeighborList｜；

4. FOR（j＝1；（j＜＝ M ＆ each vj∈vi.NeighborList）；j＋＋）

5. ｛FOR （k＝1；（k＜＝｜vj.SList｜＆eachskin vj.SList）；k＋＋）

6. ｛IF（trust［vj］＞TRUST ＆tfjk＞STRUST＆sk.Tag＝＝1）

7. THEN

8. ｛vi.SList←vi.SList∪sk；outj［i］←1；

9. ｝ENDIF

10. ｝ENDFOR

11. ｝ENDFOR

12. Return vi.SList

上述過(guò)程中，語(yǔ)句6的作用是：判斷鄰居節(jié)點(diǎn)vj的信任度（trust［vj］）大于閾值TRUST 且vj對(duì)服務(wù)sk的信任度（tfjk）大于閾值STRUST且服務(wù)sk是允許向其他節(jié)點(diǎn)覆蓋的（sk.Tag＝＝1表示允許覆蓋），若判斷條件為真，則執(zhí)行語(yǔ)句8（即向節(jié)點(diǎn)vi匯聚可信服務(wù)sk）。其中，trust［vj］表示節(jié)點(diǎn)vj的信任度，tfjk表示節(jié)點(diǎn)vj對(duì)服務(wù)sk信任度。通過(guò)社會(huì)網(wǎng)絡(luò)服務(wù)sk的Tag標(biāo)志量給出的上下文信息，判斷服務(wù)是否可以向其他節(jié)點(diǎn)覆蓋，加強(qiáng)了服務(wù)覆蓋的針對(duì)性及算法的實(shí)用性。

基于算法1的最優(yōu)覆蓋路徑以及函數(shù)getServices（），設(shè)計(jì)社會(huì)網(wǎng)絡(luò)環(huán)境下可信服務(wù)最大覆蓋算法，其主要步驟如下：

步驟1 調(diào)用函數(shù)getServices（）向優(yōu)勢(shì)節(jié)點(diǎn)匯集可信服務(wù)。

步驟2 進(jìn)行服務(wù)覆蓋。即：優(yōu)勢(shì)節(jié)點(diǎn)通過(guò)最優(yōu)覆蓋路徑，向該路徑上其他節(jié)點(diǎn)進(jìn)行服務(wù)覆蓋。

社會(huì)網(wǎng)絡(luò)可信服務(wù)最大覆蓋算法（簡(jiǎn)稱MaxiCoverService）如算法2所示。

算法2 社會(huì)網(wǎng)絡(luò)可信服務(wù)最大覆蓋算法（MaxiCoverService）

輸入：社會(huì)網(wǎng)絡(luò)服務(wù)信任關(guān)系圖G、最優(yōu)覆蓋路徑p；

輸出：CoverS及CoverN。／＊CoverS為可信服務(wù)集，CoverN為被服務(wù)覆蓋的節(jié)點(diǎn)集＊／

BEGIN

1. CoverS←?；CoverN←?；

2. int l＝｜p｜；／＊l表示路徑p 上節(jié)點(diǎn)的個(gè)數(shù)＊／

3. tempS［l］←?；tempV［l］←?；／＊tempS 和tempV均為中間變量，分別暫時(shí)保存待處理的服務(wù)和節(jié)點(diǎn)信息＊／

4. BetterN←路徑p上的優(yōu)勢(shì)節(jié)點(diǎn)；／＊BetterN保存優(yōu)勢(shì)節(jié)點(diǎn)＊／

5. N←｜BetterN｜；／＊優(yōu)勢(shì)節(jié)點(diǎn)集大小為N＊／

6. FOR（i＝1；（i＜＝N ＆ each vi∈BetterN）；i＋＋）

7. ｛vi.SList←vi.SList∪getServices（vi）；／＊調(diào)用getServices（）函數(shù)向優(yōu)勢(shì)節(jié)點(diǎn)匯聚可信服務(wù)＊／

8. ｝ENDFOR

9. ／＊下面由優(yōu)勢(shì)節(jié)點(diǎn)沿著最優(yōu)覆蓋路徑p以縱向優(yōu)先策略進(jìn)行服務(wù)覆蓋＊／

10. FOR（i＝1，j＝i＋1；（i＜l ＆ each vi∈p）；i＋＋）

11. ｛IF（vjis in vi.NeighborList ＆outj［i］＝＝1＆vi.SList do not exist in vj.SList）

12. THEN

13. ｛tempS［j］←vi.SList；／＊暫存節(jié)點(diǎn)vj的服務(wù)到tempS［j］＊／

14. tempV［j］←vj；／＊暫存節(jié)點(diǎn)vj到tempV［j］＊／

15. outj［i］←0；inj［i］←1；

16. ｝ENDIF

17. IF（t時(shí)刻節(jié)點(diǎn)vj成功處理了來(lái)自節(jié)點(diǎn)vi所覆蓋的服務(wù)）

18. THEN｛δti［j］←1；

19. vj.SList←vj.SList∪tempS［j］；

20. CoverN←CoverN∪tempV［j］；

21. CoverS←CoverS∪tempS［j］；

22. inj［i］←0；／＊表示vj處理結(jié)束＊／

23. ｝ENDIF

24. outj＋1［i＋1］←1；／＊設(shè)置路徑p的vi＋1節(jié)點(diǎn)的待覆蓋狀態(tài)為真，為后續(xù)向vj＋1的服務(wù)覆蓋做好準(zhǔn)備＊／

25. 最優(yōu)覆蓋路徑p的其他子路徑同樣以縱向優(yōu)先策略進(jìn)行服務(wù)覆蓋；

26. ｝ENDFOR

27. Return CoverS ＆ CoverN；

28. END

算法2在實(shí)現(xiàn)服務(wù)覆蓋時(shí)，由于在getServices（）函數(shù)中已經(jīng)判斷是否允許服務(wù)向其他節(jié)點(diǎn)覆蓋（見(jiàn)該函數(shù)的語(yǔ)句6的sk.Tag＝＝1），因此在算法2進(jìn)行服務(wù)覆蓋時(shí)就不需再作相同的判斷。另外，由于算法1已提供了最優(yōu)覆蓋路徑及在覆蓋時(shí)間上滿足時(shí)間約束，因此基于最優(yōu)覆蓋路徑可以很便捷地實(shí)現(xiàn)可信服務(wù)最大覆蓋。

算法2對(duì)于p中的每個(gè)元素vi進(jìn)行處理，第一個(gè)節(jié)點(diǎn)是優(yōu)勢(shì)節(jié)點(diǎn)，通過(guò)該節(jié)點(diǎn)將其服務(wù)信息覆蓋到路徑的其他節(jié)點(diǎn)上。變量δti［j］記錄了t時(shí)刻服務(wù)覆蓋的結(jié)果。算法2時(shí)間復(fù)雜度：第一步（語(yǔ)句1～語(yǔ)句8）的算法復(fù)雜度為O（N＊M＊｜vj.SList｜），第二步（語(yǔ)句10～語(yǔ)句27）的算法復(fù)雜度為O（l），因此總時(shí)間復(fù)雜度為O（N3）。

4 仿真實(shí)驗(yàn)

4.1 仿真實(shí)驗(yàn)相關(guān)參數(shù)

本文仿真實(shí)驗(yàn)的硬件環(huán)境為：多臺(tái)Intel酷睿i3 2120、3 300MHz處理器、4GB 內(nèi)存的主機(jī)等；軟件環(huán)境：操作系統(tǒng)為WinXP。數(shù)據(jù)集主要來(lái)源：基于Epinions數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)，該數(shù)據(jù)集表現(xiàn)了具有信任關(guān)系的社會(huì)網(wǎng)絡(luò)節(jié)點(diǎn)與產(chǎn)品服務(wù)的關(guān)系，該數(shù)據(jù)集包括trust-data和rating＿data兩部分，trustdata是從實(shí)際的Epinions社會(huì)網(wǎng)絡(luò)中獲取的社會(huì)網(wǎng)絡(luò)節(jié)點(diǎn)及其間的信任值；設(shè)置節(jié)點(diǎn)之間的信任度取值范圍為［0，1］，節(jié)點(diǎn)對(duì)自身的信任度為1。rating＿data為社會(huì)網(wǎng)絡(luò)節(jié)點(diǎn)對(duì)產(chǎn)品服務(wù)的評(píng)價(jià)信息；服務(wù)的信任取值范圍為［0，1］。仿真實(shí)驗(yàn)相關(guān)參數(shù)的設(shè)置如表2所示。

Table 2 Parameters in simulation and algorithms表2 仿真實(shí)驗(yàn)相關(guān)參數(shù)

表2中，R和TIME的取值范圍沒(méi)有特殊的規(guī)定，TIME取值為500s，為了配合仿真實(shí)驗(yàn)需要，可令R取值在50～1 000，以步長(zhǎng)50而不斷遞增。其余參數(shù)是在多次實(shí)驗(yàn)的基礎(chǔ)上在其取值范圍內(nèi)予以取值。度量指標(biāo)如下：

（1）可信服務(wù)覆蓋率（cRate）：見(jiàn)式（1）。

（2）消耗的網(wǎng)絡(luò)資源（width）：對(duì)于給定的服務(wù)信息，在給定的覆蓋半徑的限定下，所有節(jié)點(diǎn)的接收信息的總數(shù)量反映了消耗網(wǎng)絡(luò)資源的代價(jià)。令所有節(jié)點(diǎn)的個(gè)數(shù)為N，則平均width記為width，width＝width／N，反映每個(gè)社會(huì)網(wǎng)絡(luò)節(jié)點(diǎn)平均耗費(fèi)的網(wǎng)絡(luò)資源。

（3）時(shí)間耗費(fèi)（time）：在給定的覆蓋半徑的限定下，實(shí)現(xiàn)可信服務(wù)覆蓋所需的時(shí)間，反映出服務(wù)覆蓋的時(shí)間代價(jià)。

實(shí)驗(yàn)設(shè)置每20s選擇一個(gè)優(yōu)勢(shì)節(jié)點(diǎn)向其鄰居節(jié)點(diǎn)覆蓋服務(wù)信息，在接收到鄰居節(jié)點(diǎn)發(fā)回的正反饋信息時(shí)，表示服務(wù)覆蓋成功，否則服務(wù)覆蓋失敗。每項(xiàng)測(cè)試至少包括30次實(shí)驗(yàn)，將30次實(shí)驗(yàn)結(jié)果的平均值作為一項(xiàng)測(cè)試的結(jié)果。

4.2 本文方法的性能測(cè)試與分析

實(shí)驗(yàn)1 算法1的收斂情況如圖2所示。

Figure 2 Convergence analysis of algorithm 1圖2 算法1的收斂分析

圖2 縱坐標(biāo)表示相鄰若干代的種群平均適應(yīng)值的變化偏差百分比，橫坐標(biāo)表示進(jìn)化時(shí)間，由圖2可知，當(dāng)進(jìn)化時(shí)間到第20s時(shí)，偏差百分比接近0，可見(jiàn)算法1能在較短的時(shí)間內(nèi)收斂。

實(shí)驗(yàn)2 算法1的尋找最優(yōu)覆蓋路徑的實(shí)驗(yàn)分析如圖3所示。

Figure 3 Looking for the optimal coverage path of trusted service圖3 尋找可信服務(wù)最優(yōu)覆蓋路徑

圖3 中，橫坐標(biāo)表示社會(huì)網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)，社會(huì)網(wǎng)絡(luò)的節(jié)點(diǎn)數(shù)取值在50～1 000之內(nèi)，以步長(zhǎng)50而不斷遞增。由圖3可知，算法1尋找可信服務(wù)最優(yōu)覆蓋路徑的正確率為86.5%～91.6%。

實(shí)驗(yàn)3 算法2的可信服務(wù)最大覆蓋率實(shí)驗(yàn)分析如圖4所示。

Figure 4 Different optimal coverage path maximum coverage trusted service4 不同最優(yōu)服務(wù)覆蓋路徑上可信服務(wù)最大覆蓋率

圖4 中，橫坐標(biāo)表示最優(yōu)覆蓋路徑的編號(hào)，通過(guò)對(duì)18條路徑進(jìn)行統(tǒng)計(jì)可知，算法2的可信服務(wù)最大覆蓋率為84.2%～88.5%。

實(shí)驗(yàn)4 與其他相關(guān)方法的比較分析。

將本文方法與有信任控制T-INDI方法及無(wú)信任控制的N-INDI方法進(jìn)行比較，分析三種方法的服務(wù)覆蓋率cRate。其中，T-INDI方法是加了信任判斷的方法。在指定時(shí)間段T內(nèi)、在不可信服務(wù)比例為50%左右的情況下，cRate如圖5所示。

圖5中，在運(yùn)行時(shí)間段T為（0～80s）時(shí)，本文方法的可信服務(wù)覆蓋率較快地從50%左右變化到89%左右。而T-INDI方法，在相對(duì)較長(zhǎng)的時(shí)間內(nèi)達(dá)到70%左右的可信服務(wù)最大覆蓋率并趨于穩(wěn)定。N-INDI方法的可信服務(wù)覆蓋率最小。T-INDI和N-INDI方法在非攻擊模式下（即所有網(wǎng)絡(luò)用戶和服務(wù)都是可信的），兩者服務(wù)覆蓋率基本相近（從圖5中的前20s可以看出），但由于N-INDI方法缺乏對(duì)服務(wù)信任度的判斷，不可信服務(wù)及不可信節(jié)點(diǎn)導(dǎo)致服務(wù)覆蓋逐漸趨于阻塞狀態(tài)，從而在服務(wù)覆蓋時(shí)產(chǎn)生瓶頸（在圖5中的第20s左右），其可信服務(wù)的最大覆蓋率小于26%。

Figure 5 cRate analysis of different methods圖5 不同方法的cRate分析

本文方法與其他方法的時(shí)間耗費(fèi)（單位為s）、width及width，如表3所示。

Table 3 Other performance of different methods表3 不同方法的其他性能分析

從表3可知，三種方法隨著社會(huì)網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)的增多，時(shí)間耗費(fèi)、網(wǎng)絡(luò)資源耗費(fèi)width在不斷增大，本文方法消耗網(wǎng)絡(luò)資源相對(duì)較少，并具有較好的時(shí)間性能。

5 結(jié)束語(yǔ)

研究社會(huì)網(wǎng)絡(luò)環(huán)境下可信服務(wù)最大范圍的覆蓋，對(duì)促進(jìn)服務(wù)資源的共享與利用具有重要的應(yīng)用價(jià)值，但社會(huì)網(wǎng)絡(luò)的開(kāi)放性以及服務(wù)本身的分布自治性、異構(gòu)性和動(dòng)態(tài)性等特征增加了保障可信服務(wù)最大覆蓋的難度，如何快速向社會(huì)網(wǎng)絡(luò)實(shí)現(xiàn)服務(wù)最大覆蓋和可信覆蓋是需要解決的主要問(wèn)題。本文基于優(yōu)勢(shì)節(jié)點(diǎn)與其他社會(huì)網(wǎng)絡(luò)節(jié)點(diǎn)之間的關(guān)聯(lián)關(guān)系尋找最優(yōu)覆蓋路徑，并基于最優(yōu)覆蓋路徑，通過(guò)可信服務(wù)最大覆蓋算法將服務(wù)覆蓋到社會(huì)網(wǎng)絡(luò)其他節(jié)點(diǎn)，實(shí)現(xiàn)可信服務(wù)最大覆蓋。實(shí)驗(yàn)結(jié)果表明，本文方法性能較好，達(dá)到預(yù)期設(shè)定的服務(wù)覆蓋目標(biāo)，與已有相關(guān)方法相比，本文方法可實(shí)現(xiàn)最優(yōu)化可信服務(wù)覆蓋且服務(wù)覆蓋范圍更廣。

未來(lái)工作包括如下方面：（1）針對(duì)用戶偏好覆蓋滿足用戶個(gè)性化需求的服務(wù)，由于用戶偏好可能是隱性的，因此需要挖掘用戶興趣度及需求，提高用戶滿意度。（2）移動(dòng)社會(huì)網(wǎng)絡(luò)是一種特殊且應(yīng)用廣泛的社會(huì)網(wǎng)絡(luò)，通過(guò)分析移動(dòng)社會(huì)網(wǎng)絡(luò)特征和設(shè)計(jì)可信服務(wù)覆蓋算法，加強(qiáng)服務(wù)覆蓋算法在移動(dòng)社會(huì)網(wǎng)絡(luò)中的應(yīng)用。

［1］ Kang Le，Jing Ji-wu，Wang Yue-wu.The trust expansion and control in social network service［J］.Journal of Computer Research and Development，2010，47（9）：1611-1621.（in Chinese）

［2］ Liu F M，Li X，Ding Y S.A social network-based trust-aware propagation model for P2Psystems［J］.Knowledge-Based Systems，2013，41：8-15.

［3］ Malik Z，Bouguettaya A.RATEWeb：Reputation assessment for trust establishment among web services［J］.Very Large Data Bases（VLDB），2009，18（4）：885-911.

［4］ Wang Gang，Gui Xiao-lin.Selecting and trust computing for transaction nodes in online social networks［J］.Chinese Journal of Computers，2013，36（2）：368-383.（in Chinese）

［5］ Zhang Pei-yun，Chen En-hong，Li Bo.Web services trust computing based on social network dynamic feedback［J］.PR＆AI，2013，26（4）：337-343.（in Chinese）

［6］ Berman O，Drezner Z，Krass D.Generalized coverage：New developments in covering location models［J］.Computers ＆Operations Research，2010，37（10）：1675-1687.

［7］ Jaramillo J H，Bhadury J，Batta R.On the use of genetic algorithms to solve location problems［J］.Computers ＆ Operations Research，2002，29（6）：761-779.

［8］ Karasakal O，Karasaka1EK.A maximal covering location model in the presence of partial coverage［J］.Computers ＆Operations Research，2004，31（9）：1515-1526.

［9］ Li Y，Cai Z M.Gravity-based heuristic for set covering problems and its application in fault diagnosis［J］.Journal of Systems Engineering and Electronics，2012，23（3）：391-398.

［10］ Cheng Wei-fang，Liao Xiang-ke，Shen Chang-xiang.Maximal coverage scheduling in wireless directional sensor networks［J］.Journal of Software，2009，20（4）：975-984.（in Chinese）

［11］ Osman Y，Qian D，Zhang J，et al.Conjoining speeds up information diffusion in overlaying social-physical networks［J］.IEEE Journal on Selected Areas in Communications，2013，31（6）：1038-1048.

［12］ Chamley C，Scaglione A，Lin Li.Models for the diffusion of beliefs in social networks：An overview［J］.IEEE Signal Processing Magazine，2013，30（3）：16-29.

［13］ Wang Y Q，Yang X Y，Han Y L.Rumor spreading model with trust mechanism in complex social networks［J］.Communications in Theoretical Physics，2013，59（4）：510-516.

［14］ Cheng X Q，Shen H W.Uncovering the community structure associated with the diffusion dynamics on networks［J］.Journal of Statistical Mechanics：Theory and Experiment，2010（4）：1-10.

［15］ Kimura M，Saito K，Motoda H.Blocking links to minimize contamination spread in a social network［J］.ACM Transactions on Knowledge Discovery from Data（TKDD），2009，3（2）：1-23.

附中文參考文獻(xiàn)：

［1］ 康樂(lè)，荊繼武，王躍武.社會(huì)化網(wǎng)絡(luò)服務(wù)中的信任擴(kuò)張與控制［J］.計(jì)算機(jī)研究與發(fā)展，2010，47（9）：1611-1621.

［4］ 王剛，桂小林.社會(huì)網(wǎng)絡(luò)中交易節(jié)點(diǎn)的選取及其信任關(guān)系計(jì)算方法［J］.計(jì)算機(jī)學(xué)報(bào)，2013，36（2）：368-383.

［5］ 張佩云，陳恩紅，李波.基于社會(huì)網(wǎng)絡(luò)動(dòng)態(tài)反饋的 Web服務(wù)信任度計(jì)算［J］.模式識(shí)別與人工智能，2013，26（4）：337-343.

［10］ 程衛(wèi)芳，廖湘科，沈昌祥.有向傳感器網(wǎng)絡(luò)最大覆蓋調(diào)度算法［J］.軟件學(xué)報(bào)，2009，20（4）：975-984.