基于虛擬積分激勵的內容部署方法①

張 云,鄭 嘯,黃 溯

1(安徽工業大學 計算機科學與技術學院,馬鞍山 243000)2(安徽馬鋼自動化信息技術有限公司,馬鞍山 243000)

移動自組織網絡中,節點間的通信總是依賴于其他節點轉發到達目的地,若將內容部署在網絡中適合位置的節點上,則可以很大程度上增強網絡性能,提高服務效率[1].現實中節點都是理性的,一般情況下難以與其他節點分享自身資源或耗費自身資源去進行內容部署[2].在這種情形下,如果沒有一種激勵方式去鼓勵節點間的合作,節點是不愿意與其他節點合作進行內容部署的,即節點的自私特性.這些自私節點卻依靠其他合作節點來轉發自己的數據.節點的自私行為導致網絡性能下降,也可能導致多跳網絡通信失敗[3,4].為了增強網絡性能,提高服務效率,降低內容部署成本,有必要通過激勵方法鼓勵節點合作,降低節點的自私性.

本文使用了一種有效的激勵方式去鼓勵節點合作.首先,介紹了內容部署和激勵機制的相關技術;其次,闡述了基于虛擬積分激勵機制的內容部署;最后,通過仿真實驗表明本文方法的優越性.

1 相關工作

1.1 內容部署

在網絡中將內容部署在合適的節點上,可以增加網絡的靈活性,提高應用的響應時間,改善網絡的擁塞問題[1,5].目前,解決內容部署問題的主要是分布式的方法.Pandit[6]則使用了分布式算法,在復雜度為O(logn)的情形下解決了Jain等人[7]提出相同復雜度的原始-對偶方法.Oikonomou等人[8]將鄰居跳遷移部署應用于一個或者更多的內容部署中,可以解決分布式和低復雜度k-中值問題的近似解,且k＞1.Smaragdakis等人[9]就利用r-跳轉遷移部署策略有效地解決了內容部署問題,初始服務內容可以根據當前網絡的情形自適應的遷移到最佳位置,并且根據當前需求盡可能地減少進行內容部署的開銷,它可以增加或減少服務內容的數量.Stavrakakis等人[10]通過分布式的方法用一種新的啟發式方法解決內容位置的優化問題.

本文考慮的是r-跳轉遷移部署策略無容量限制的內容部署問題,主要解決內容部署中的位置UKM(uncapacitatedk-median)和數量UFL(uncapacitated facility location)兩個問題[9,11].

UKM問題:解決網絡中部署內容的節點的位置問題,盡量減少訪問用戶與能提供服務的節點之間的距離,將內容部署在網絡中的最佳位置節點上.

UFL問題:解決網絡中進行內容部署的節點的數量問題,在網絡中內容部署在過多的節點上雖然可以提高網絡性能,但容易造成資源浪費,如果將內容部署在過少的節點上又容易造成服務質量的降低,所以適當地部署內容節點的數量對網絡的性能及成本有直接的影響.

1.2 常用的激勵機制

對于內容部署的研究前提假設節點是合作的,但這在現實中節點是理性的,為了降低自私節點對內容部署過程的影響,本文在內容部署過程中引入了激勵方法.當下對激勵機制的研究主要分為四類:基于博弈論激勵[12]、虛擬積分激勵[13]、社交關系激勵[14]以及混合激勵[15].這些激勵方式都滿足參與者的某些需求而達到激勵的效果.

基于虛擬積分的激勵方法是用戶通過參與網絡中的任務而獲得虛擬積分(即一種假想的獎勵,貨幣等),當行動和獎勵不同步時,虛擬積分可以很好地調動用戶的積極性,特別在多跳無線網絡中的包轉發情形中,虛擬積分也可以用于換取其他獎勵.

Chuang等人[16]用虛擬積分補償來自其他節點的數據轉發所消耗的資源.而所獲取的虛擬積分可以用于轉發自己的數據,補償給幫忙轉發的中間節點,激勵它們幫忙轉發.而不合作的節點則不允許使用網絡,不會獲得虛擬積分.Zhong等人[17]使用虛擬積分來解決移動自組織網絡中自私節點的路由問題.在該方法中,發送方如果要發送數據,則必須使用一定的虛擬積分,以替代中間節點幫忙轉發的成本.Buttyán等人[18]介紹了一個稱為nuglet的虛擬貨幣,為了激勵節點合作而運用到移動自組織網絡中.

2 加入激勵機制的內容部署分析

本文在研究移動自組織環境下的內容部署基礎上融入了虛擬積分的激勵方法,該情形下的內容部署是基于設備選址問題又不同于傳統的設備選址問題,文中的內容是部署在網絡中合適的節點上.本文通過節點的度的值來反映節點與網絡中其他節點合作的可能性.

2.1 基于虛擬積分的激勵機制

因為節點是理性的,本文將節點分為兩種狀態:空閑狀態和忙碌狀態.在進行內容部署之前需要對節點進行訪問,當節點在空閑狀態的時候可以直接進行服務部署,但當節點為忙碌狀態的時候,需要判斷節點是否愿意配合網絡進行內容部署.

基于激勵方法的內容部署研究的主要目標是在網絡環境下激勵用戶節點積極參與內容部署活動,增強網絡性能,提高用戶使用效率.激勵機制可以用以下模型表示:

內容部署激勵機制(Incentive,I),即通過某種激勵方式(Mechanism,M)在節點集(V)中確定的服務內容數量(k),并結合服務需求(s)達到節點在進行內容部署時所消耗的服務費用成本(C)最低.

激勵機制還可以用以下模型表示:

內容部署激勵機制(Incentive,I),即通過某種激勵方式(Mechanism,M)在節點集(V)中確定服務內容數量(k),并結合服務需求(s)以及服務成本(f)達到節點在進行內容部署時所消耗的服務費用成本(C)最低.

在該情形中,節點具有自私性,但是當網絡給予節點一些虛擬積分用于彌補節點在進行內容部署時的資源消耗,節點可以從忙碌狀態轉移到空閑狀態,然后進行內容部署.本文節點所獲得的虛擬積分收益可用于后期獲取網絡資源,節點的虛擬積分值越大,享有的獲取資源的優先級就越大,可以優先于其他節點獲取資源,若節點的虛擬積分值為0,則網絡就隔離該節點,即不提供任何資源給該節點.網絡可以通過激勵函數計算給予節點vi的虛擬積分值,激勵函數為:

由于資源有限,節點會根據當前損失的利益大小判斷是否接受網絡提供的激勵值,進而決定是否從忙碌狀態轉換到空閑狀態,若當前的節點狀態滿足式(11),則節點接受當前的激勵值,允許進行內容部署:

上式中節點vi和節點vj分別表示用戶節點和服務節點,作為節點的標識位,用于該節點的數據獲取次數的記錄,p是概率值.通過式(11)計算時間內該節點的數據獲取次數與網絡中所有節點的數據獲取次數的關系,判斷當前節點在網絡中的數據獲取情況,節點依據數據獲取情況決定是否接受網絡提供的激勵值,并通過實驗對參數p進行調整.

2.2 算法描述

本節根據內容部署模型及分析,給出算法描述.

(1)激勵算法

算法1.Incentive()if iter%Δt==0 then for i=1:SizeSize do if節點i滿足部署條件then節點i從忙碌狀態切換到空閑狀態,由式(5)計算給予節點i虛擬積分值end if end for end if return節點得到的虛擬積分值

(2)服務節點確定算法

在服務節點確定過程中,所有節點隨機分布在網絡中,本文先隨機選取k個節點作為初始服務器節點,再用k-median算法確定該k個服務器節點的位置.在確定服務器節點的位置過程中,用弗洛伊德算法找到節點vi到服務器節點vj的最短路徑dij,用于計算進行內容部署的成本,選取成本較低的節點作為服務器節點.

SiteInfo表示所有節點信息;ServerInfo表示所有服務節點信息;ServerSize表示服務節點數量;SiteSize表示節點數量;iterMax表示k-median算法的最大迭代次數;t表示時間間隔.根據網絡當前的環境信息用弗洛伊德算法計算距離矩陣和路徑,并確定服務節點的位置,算法如算法2.

算法2.Choose_Serve()if iter%t= =0 then for i=1:SiteSize do for j=1:ServerSize do計算第j個服務節點到第i個節點之間的距離end for選擇距離第i個節點最近的服務節點作為該節點的獲取數據的服務節點end for for i=1:SiteSize do依據節點i的自身信息更新其服務需求end for for iter=1:iterMax do for j=1:ServerSize do for i=1:SiteSize do if 節點i到服務節點j之間存在且服務節點j不是節點i獲取數據的服務節點then把服務節點j設置為節點i的服務節點,更新SiteInfo和ServerInfo else節點i的計數器加1 end if end for Incentive();end for end for if 問題為UKM Then式(1)計算部署成本else if 問題為UFL式(2)計算部署成本end if end if return部署成本和虛擬積分值

(3)服務節點個數確定算法

在UFL情形下,不僅可以確定服務節點的位置,同時也可以確定服務節點的個數.在部署服務內容過程中,由于考慮了服務成本,過少的部署內容會達不到增強網絡性能和提高服務效率的作用;過多的部署內容就會造成部署成本的浪費,增大了服務部署開銷.確定合適的服務節點個數對增強網絡的性能、提高服務效率、降低部署成本都產生了很大的影響.在部署內容初期,部署內容的成本隨著服務節點個數的增加而減少,但是到達一個值時,部署成本就會隨著服務節點個數的增加而增加.

ServerSize表示服務節點最大數量;iterMax表示最大迭代次數;radius表示r跳值,b[n]存儲服務節點,本文取r=1,表示距離節點1-跳的用戶節點.算法如算法3.

算法3.Confirm_NumOfServe()Require:ServerSize;iterMax;radius;b[ServerSize]解決UFL問題后獲得的最優成本C=Inf,最優成本Cmin=Inf,最佳服務節點個數BestNumOfServer=-1;for i=1:ServerSize do for j=1:iterMax do遍歷當前所有服務節點radius鄰域內節點,選擇符合條件的節點與服務節點進行交換,計算最小代價C(j)if C＞C(j)then C=C(j)保留服務節點信息end if end for if Cmin＞C then Cmin=C,BestNumOfServer=i;將服務節點序號存入b[i];end if end for Choose_Serve();return最低成本Cmin,最佳服務節點個數BestNumOfServer和數組b

3 實驗仿真分析

3.1 實驗環境與參數設置

為了驗證添加本文的激勵方法對網絡的有效影響,本文分別對節點是無私的、節點是自私的以及加入激勵方法的情形做了對比實驗.實驗環境為Windows 7操作系統,使用matlab 2010b編寫算法進行仿真實驗.

本文的方法在E-R(Erd?s-Rényi)隨機圖中進行實驗仿真,E-R隨機圖中兩個節點之間存在一條邊的概率p=0.5[19].節點在網絡中移動的速度大小為1 m/s、方向隨機.節點規模分別為100、200、300和400,最大迭代次數為200代.UKM中的服務節點個數為5個,UFL中的服務節點個數根據迭代優化最終確定.

3.2 實驗結果

在E-R圖中,本文分別就UFL和UKM情形下對網絡節點數,,服務站點數進行了實驗比較,圖1 為UFL情形下對激勵方法的影響,圖2為UFL情形下節點規模對激勵方法的影響,圖3為服務節點個數對激勵方法影響,圖4為UKM情形下對激勵機制的影響,圖5為UKM情形下節點規模對激勵機制的影響,圖6和圖7為本文實驗結果與Georgios實驗結果對比.

圖1 UFL情形下對激勵方法的影響(節點個數n=200)

圖2 UFL情形下節點規模對激勵方法的影響(=10)

如圖2,在UFL的情形下,通過上述不同節點數之間的實驗對比我們可以發現,無論節點規模是100,200,300或400,它對于本文提出的激勵方法是沒有影響的,本文提出的方法依舊能有效地減少網絡成本.

如圖3,在UFL情形下,節點規模為300.通過上述實驗結果可以看出,部署內容所需成本隨著服務節點個數增加而減少,但是,當網絡所需成本減少到一定程度時,就會隨著服務節點個數增加而增加.

圖3 服務節點個數對激勵方法影響

圖4 UKM情形下對激勵機制的影響(節點個數n=200)

如圖5,在UKM的情形下,通過上述不同節點數之間的實驗對比我們可以發現,無論節點規模是100,200,300或400,它對于本文提出的激勵機制方法是沒有影響的,本文提出的方法依舊能有效地減少網絡成本.

圖5 UKM情形下節點規模對激勵機制的影響(=10)

如圖6,本文實驗中UFL情形下部署成本與文獻[9]中結果對比,通過上述實驗對比我們可以發現,本文的激勵機制方法在減少網絡成本方面具有一定效果.

圖6 與Georgios實驗結果對比

如圖7,在UKM情形下,本文的部署成本與集中式的UKM成本比率與文獻[9]中的結果對比,我們可以發現,在UKM情形下,本文的激勵機制方法能有效地減少網絡成本.

圖7 與Georgios實驗結果對比

4 結語

本文描述了一種激勵方法,并將其應用于移動自組織網絡環境下的內容部署問題中.文中分別就節點是無私的,自私的以及帶有激勵方法的情形下進行了仿真實驗對比,有效地驗證了加入激勵方法后對網絡的性能有了明顯的提高.本文存在的不足之處:雖然本文驗證了基于虛擬積分的激勵方法在E-R隨機圖中的有效性,但不確定對其他網絡模型是否有效;在考慮節點自私的情形時,沒有考慮節點的轉發能耗等問題.針對這些問題,還需要對基于激勵方法的內容部署進行更加深入的研究.

1 尹浩,袁小群,林闖,等.內容網絡服務節點部署理論綜述.計算機學報,2010,33(9):1611–1620.

2 Ciobanu RI,Dobre C,Dascalu M,et al.Collaborative selfish node detection with an incentive mechanism for opportunistic networks.Proceedings of 2013 IFIP/IEEE International Symposium on Integrated Network Management.Ghent,Belgium.2013.1161–1166.

3 Marti S,Giuli TJ,Lai K,et al.Mitigating routing misbehavior in mobile ad hoc networks.Proceedings of International Conference on Mobile Computing and Networking.Boston,MA,USA.2000.255–265.

4 Michiardi P,Molva R.Simulation-based analysis of security exposures in mobile ad hoc networks.Proceedings of European Wireless Conference.Florence,Italy.2002.15–17.

5 脫立恒,倪宏,李滿天,等.覆蓋網絡中多服務靜態部署算法.西安電子科技大學學報(自然科學版),2014,41(4):137–143.

6 Pandit S,Pemmaraju S.Return of the primal-dual:Distributed metric facilitylocation.Proceedings of the 28th ACM Symposium on Principles of Distributed Computing.Calgary,AB,Canada.2009.180–189.

7 Jain K,Vazirani VV.Approximation algorithms for metric facility location and k-median problems using the primaldual schema and Lagrangian relaxation.Journal of the ACM,2001,48(2):274–296.[doi:10.1145/375827.375845]

8 Oikonomou K,Stavrakakis I.Scalable service migration in autonomic network environments.IEEE Journal on Selected Areas in Communications,2010,28(1):84–94.[doi:10.1109/JSAC.2010.100109]

9 Smaragdakis G,Laoutaris N,Oikonomou K,et al.Distributed server migration for scalable internet service deployment.IEEE/ACM Transactions on Networking,2014,22(3):917–930.[doi:10.1109/TNET.2013.2270440]

10 Stavrakakis I.Some distributed approaches to the service facility location problem in dynamic and complex networks.Thai M,Pardalos P.Handbook of Optimization in Complex Networks.New York.Springer.2012.405–432.

11 Pantazopoulos P,Karaliopoulos M,Stavrakakis I.Distributed placement of autonomic Internet services.IEEE Transactions on Parallel &Distributed Systems,2014,25(7):1702–1712.

12 曲大鵬,王興偉,黃敏.移動對等網絡中自私節點的檢測和激勵機制.軟件學報,2013,24(4):887–899.

13 Charilas DE,Georgilakis KD,Panagopoulos AD.ICARUS:Hybrid incentive mechanism for cooperation stimulation in ad hoc networks.Ad Hoc Networks,2012,10(6):976–989.[doi:10.1016/j.adhoc.2011.12.010]

14 吳垚,曾菊儒,彭輝,等.群智感知激勵機制研究綜述.軟件學報,2016,27(8):2025–2047.[doi:10.13328/j.cnki.jos.005049]

15 陳國利.基于激勵的機會網絡協作傳輸機制[碩士學位論文].北京:北京郵電大學,2015.

16 Chuang MC.An incentive-based mechanism for fair bidirectional transmissions in wireless mesh networks.Computers &Electrical Engineering,2015,(41):342–356.

17 Zhong S,Chen J,Yang YR.Sprite:A simple,cheat-proof,credit-based system for mobile ad-hoc networks.Proceedings of the 22th Annual Joint Conference of the IEEE Computer and Communications.San Francisco,CA,USA.2003.1987–1997.

18 Buttyán L,Hubaux JP.Enforcing service availability in mobile ad-hoc WANs.Proceedings of 2000 the 1st Annual Workshop on Mobile and Ad Hoc Networking and Computing.Boston,MA,USA.2000.87–96.

19 Erd?s P,Rényi A.On random graphs I.Publicationes Mathematicae,1959,(6):290–297.