張佩云，黃 波，宮秀文

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

1 引言

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

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

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

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

2.1 基本概念

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

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

2.2 社會網(wǎng)絡可信服務覆蓋模型

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

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

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

cRate是檢驗本文方法效果的一個重要指標。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

式（4）中，χ（p）為路徑p 的服務覆蓋量，χmax（p）和χmin（p）分別表示路徑p的服務覆蓋量的最大值和最小值，其計算公式見表1。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

6. ｝ENDFOR

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

8. FOR （Gen＝0；（Gen＜ GEN＿MAX｜｜σ＜1E－5）；Gen＋＋）

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

10. ／＊設計適應度函數(shù)fitness＊／

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

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

13. 采用隨機選取斷點的兩點交叉，交叉概率Pc∈［0，1］；

14. 采用變異概率Pm∈（0，1）對個體隨機變異；

15. 把該個體放到種群中去；

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

17. ｝ENDFOR

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

19. Return the best path p；

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

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

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

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

3.2 可信服務最大覆蓋

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

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

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

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

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

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

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

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

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

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

步驟2 進行服務覆蓋。即：優(yōu)勢節(jié)點通過最優(yōu)覆蓋路徑，向該路徑上其他節(jié)點進行服務覆蓋。

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

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

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

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

BEGIN

1. CoverS←?；CoverN←?；

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

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

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

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

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

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

8. ｝ENDFOR

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

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é)點vj的服務到tempS［j］＊／

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

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

16. ｝ENDIF

17. IF（t時刻節(jié)點vj成功處理了來自節(jié)點vi所覆蓋的服務）

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；／＊設置路徑p的vi＋1節(jié)點的待覆蓋狀態(tài)為真，為后續(xù)向vj＋1的服務覆蓋做好準備＊／

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

26. ｝ENDFOR

27. Return CoverS ＆ CoverN；

28. END

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

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

4 仿真實驗

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

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

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

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

（1）可信服務覆蓋率（cRate）：見式（1）。

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

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

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

4.2 本文方法的性能測試與分析

實驗1 算法1的收斂情況如圖2所示。

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

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

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

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

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

實驗3 算法2的可信服務最大覆蓋率實驗分析如圖4所示。

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

圖4 中，橫坐標表示最優(yōu)覆蓋路徑的編號，通過對18條路徑進行統(tǒng)計可知，算法2的可信服務最大覆蓋率為84.2%～88.5%。

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

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

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

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

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

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

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

5 結(jié)束語

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

未來工作包括如下方面：（1）針對用戶偏好覆蓋滿足用戶個性化需求的服務，由于用戶偏好可能是隱性的，因此需要挖掘用戶興趣度及需求，提高用戶滿意度。（2）移動社會網(wǎng)絡是一種特殊且應用廣泛的社會網(wǎng)絡，通過分析移動社會網(wǎng)絡特征和設計可信服務覆蓋算法，加強服務覆蓋算法在移動社會網(wǎ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.

附中文參考文獻：

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

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

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

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