張 云,鄭 嘯,黃 溯

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

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

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

1 相關工作

1.1 內容部署

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

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

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

UFL問題:解決網(wǎng)絡中進行內容部署的節(jié)點的數(shù)量問題,在網(wǎng)絡中內容部署在過多的節(jié)點上雖然可以提高網(wǎng)絡性能,但容易造成資源浪費,如果將內容部署在過少的節(jié)點上又容易造成服務質量的降低,所以適當?shù)夭渴饍热莨?jié)點的數(shù)量對網(wǎng)絡的性能及成本有直接的影響.

1.2 常用的激勵機制

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.2 算法描述

本節(jié)根據(jù)內容部署模型及分析,給出算法描述.

(1)激勵算法

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

(2)服務節(jié)點確定算法

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

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

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

(3)服務節(jié)點個數(shù)確定算法

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

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

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

3 實驗仿真分析

3.1 實驗環(huán)境與參數(shù)設置

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

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

3.2 實驗結果

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

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

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

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

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

圖3 服務節(jié)點個數(shù)對激勵方法影響

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

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

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

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

圖6 與Georgios實驗結果對比

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

圖7 與Georgios實驗結果對比

4 結語

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

1 尹浩,袁小群,林闖,等.內容網(wǎng)絡服務節(jié)點部署理論綜述.計算機學報,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 脫立恒,倪宏,李滿天,等.覆蓋網(wǎng)絡中多服務靜態(tài)部署算法.西安電子科技大學學報(自然科學版),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 曲大鵬,王興偉,黃敏.移動對等網(wǎng)絡中自私節(jié)點的檢測和激勵機制.軟件學報,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 陳國利.基于激勵的機會網(wǎng)絡協(xié)作傳輸機制[碩士學位論文].北京:北京郵電大學,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.