基于合作貢獻(xiàn)的移動(dòng)社會(huì)網(wǎng)絡(luò)自私路由協(xié)議

余玲飛，龔海剛

1.浙江工商大學(xué) 杭州商學(xué)院，杭州310018

2.電子科技大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院，成都611731

隨著無(wú)線通信和集成電路技術(shù)的快速發(fā)展，智能手機(jī)等便攜式終端已廣泛流行，并具備藍(lán)牙、WiFi 或4G等無(wú)線通信能力。人們隨身攜帶這些設(shè)備，通過(guò)彼此合作，從而形成一個(gè)交換和共享數(shù)據(jù)的自組織網(wǎng)絡(luò)。而在現(xiàn)實(shí)生活中，使用設(shè)備的人們對(duì)節(jié)點(diǎn)進(jìn)行支配，因此人們的社會(huì)行為（如社會(huì)屬性、社會(huì)關(guān)系等）也往往被引入用于幫助解決數(shù)據(jù)的路由問(wèn)題，并能獲得更好的性能。Hui 等[1]將這種網(wǎng)絡(luò)定義為口袋交換網(wǎng)絡(luò)（Packet Switching Networks，PSNs）。由于這種網(wǎng)絡(luò)具有內(nèi)在的社會(huì)特性，因此也稱為移動(dòng)社會(huì)網(wǎng)絡(luò)（Mobile Social Networks，MSNs）。

一些研究試圖通過(guò)采集現(xiàn)實(shí)生活中人們隨身攜帶設(shè)備上的數(shù)據(jù)，通過(guò)分析數(shù)據(jù)得到網(wǎng)絡(luò)節(jié)點(diǎn)的社會(huì)屬性，如Reality Mining[2]、INFOCOM’05[3]、INFOCOM’06[4]。LABEL[5]、BUBBLE[6]、SimBet[7]等都是利用這種網(wǎng)絡(luò)的社會(huì)屬性來(lái)輔助消息的路由。但是這些研究工作存在一個(gè)不合理的假設(shè)，即網(wǎng)絡(luò)中所有節(jié)點(diǎn)都是無(wú)私的——每個(gè)節(jié)點(diǎn)都愿意接收和轉(zhuǎn)發(fā)其他節(jié)點(diǎn)的數(shù)據(jù)。然而現(xiàn)實(shí)中人們往往表現(xiàn)出自私的行為，從而導(dǎo)致他們所支配的設(shè)備也成為網(wǎng)絡(luò)中的自私節(jié)點(diǎn)。例如，一些節(jié)點(diǎn)很可能因?yàn)殡娏?、帶寬、?nèi)存等資源有限而不愿意為其他節(jié)點(diǎn)轉(zhuǎn)發(fā)數(shù)據(jù)。

毫無(wú)疑問(wèn)，節(jié)點(diǎn)自私性會(huì)影響節(jié)點(diǎn)的轉(zhuǎn)發(fā)行為并降低路由性能。激勵(lì)機(jī)制的研究[8-10]通過(guò)鼓勵(lì)節(jié)點(diǎn)貢獻(xiàn)自己的資源，以減少節(jié)點(diǎn)個(gè)體自私性帶來(lái)的影響。但是Li等[11]認(rèn)為節(jié)點(diǎn)的自私性由不僅僅是個(gè)體自私性，還包括社會(huì)自私性。社會(huì)自私性表現(xiàn)在節(jié)點(diǎn)更愿意為那些與它有較強(qiáng)的社會(huì)關(guān)系或社會(huì)聯(lián)系的節(jié)點(diǎn)轉(zhuǎn)發(fā)數(shù)據(jù)。他們提出一種社會(huì)自私性感知的路由協(xié)議SSAR，該協(xié)議利用節(jié)點(diǎn)之間的社會(huì)聯(lián)系量化節(jié)點(diǎn)的轉(zhuǎn)發(fā)意愿，以此作為轉(zhuǎn)發(fā)數(shù)據(jù)的能力。但是SSAR 沒(méi)有考慮節(jié)點(diǎn)的資源對(duì)用戶轉(zhuǎn)發(fā)意愿產(chǎn)生的影響。例如，一個(gè)節(jié)點(diǎn)和其他節(jié)點(diǎn)之間有很強(qiáng)的社會(huì)關(guān)系，但其節(jié)點(diǎn)資源非常稀缺（如電池能量非常低）。因此盡管它很愿意為其他節(jié)點(diǎn)轉(zhuǎn)發(fā)數(shù)據(jù)，但卻因?yàn)槿鄙儋Y源而無(wú)法提供轉(zhuǎn)發(fā)服務(wù)。

針對(duì)此現(xiàn)象，本文提出了一種基于用戶合作和貢獻(xiàn)的自私路由協(xié)議（Cooperation and Contribution based Selfish Routing protocol，C2SR）。C2SR 協(xié)議在節(jié)點(diǎn)進(jìn)行路由決策時(shí)，綜合考慮候選節(jié)點(diǎn)與目標(biāo)節(jié)點(diǎn)的合作度，以及該節(jié)點(diǎn)與候選節(jié)點(diǎn)的貢獻(xiàn)度，基于合作度和貢獻(xiàn)度決定下一跳中繼節(jié)點(diǎn)。其中節(jié)點(diǎn)合作度由社會(huì)合作度和個(gè)體合作度決定，分別反映了節(jié)點(diǎn)的社會(huì)自私性和個(gè)體自私性；而貢獻(xiàn)度則體現(xiàn)了節(jié)點(diǎn)對(duì)整個(gè)網(wǎng)絡(luò)的服務(wù)貢獻(xiàn)和對(duì)特定節(jié)點(diǎn)的相互服務(wù)貢獻(xiàn)，并且將節(jié)點(diǎn)提供的服務(wù)量作為對(duì)該節(jié)點(diǎn)的激勵(lì)。與目標(biāo)節(jié)點(diǎn)具有更高合作度并且貢獻(xiàn)度更小的候選節(jié)點(diǎn)更容易成為下一跳中繼節(jié)點(diǎn)。

1 相關(guān)工作

移動(dòng)社會(huì)網(wǎng)絡(luò)的路由協(xié)議是利用節(jié)點(diǎn)的社會(huì)屬性或社會(huì)關(guān)系輔助路由決策，如LABEL 利用社區(qū)來(lái)實(shí)現(xiàn)消息的路由[5]。LABEL 根據(jù)隸屬關(guān)系將節(jié)點(diǎn)劃入不同的社區(qū)，賦予一個(gè)體現(xiàn)其隸屬關(guān)系的標(biāo)簽。節(jié)點(diǎn)僅轉(zhuǎn)發(fā)目標(biāo)節(jié)點(diǎn)或下一跳節(jié)點(diǎn)屬于同一社區(qū)的消息。BUBBLE協(xié)議則綜合考慮了社區(qū)結(jié)構(gòu)和節(jié)點(diǎn)中心度來(lái)作出轉(zhuǎn)發(fā)策略[6]。中心度體現(xiàn)了現(xiàn)實(shí)生活中節(jié)點(diǎn)的受歡迎程度以及與其他節(jié)點(diǎn)進(jìn)行交互的頻繁程度。當(dāng)兩個(gè)節(jié)點(diǎn)相遇時(shí)，即兩個(gè)節(jié)點(diǎn)彼此的通信半徑范圍內(nèi)時(shí)，消息將轉(zhuǎn)發(fā)給具有更高中心度（更受歡迎）的節(jié)點(diǎn)。SimBet協(xié)議則根據(jù)節(jié)點(diǎn)的中心度和相似度來(lái)計(jì)算一個(gè)SimBet 效用值[7]，節(jié)點(diǎn)會(huì)選擇針對(duì)目標(biāo)節(jié)點(diǎn)具有更高SimBet效用值的節(jié)點(diǎn)作為中繼節(jié)點(diǎn)。Fabbri等[12]提出了一種基于社交能力的DTN路由協(xié)議，具有較高社交能力（頻繁遇到不同節(jié)點(diǎn)）的節(jié)點(diǎn)更適合作為中繼節(jié)點(diǎn)。

然而在上述MSN 網(wǎng)絡(luò)的路由研究工作中，都假設(shè)節(jié)點(diǎn)具有完全的轉(zhuǎn)發(fā)意愿，沒(méi)有考慮節(jié)點(diǎn)的自私行為，一旦網(wǎng)絡(luò)中存在自私節(jié)點(diǎn)，路由性能將極大地降低。為了增強(qiáng)節(jié)點(diǎn)的轉(zhuǎn)發(fā)意愿，已有許多關(guān)于激勵(lì)自私節(jié)點(diǎn)更加合作的機(jī)制研究，激勵(lì)策略可以分為三類∶基于信譽(yù)（Reputation-based）、基于積分（Credit-based）和基于TFT（TFT-based）的方法。Give2Get[8]是一種基于信譽(yù)的激勵(lì)機(jī)制，當(dāng)一個(gè)節(jié)點(diǎn)為其他節(jié)點(diǎn)提供服務(wù)時(shí)，它將得到良好的信譽(yù)。具有良好信譽(yù)的節(jié)點(diǎn)就可以接收來(lái)自其他節(jié)點(diǎn)的服務(wù)。SMART[9]則利用積分來(lái)激勵(lì)自私節(jié)點(diǎn)，節(jié)點(diǎn)通過(guò)轉(zhuǎn)發(fā)其他節(jié)點(diǎn)的數(shù)據(jù)包來(lái)賺取積分，從而調(diào)節(jié)不同節(jié)點(diǎn)之間的數(shù)據(jù)包轉(zhuǎn)發(fā)關(guān)系。對(duì)于基于TFT的機(jī)制[10]，每個(gè)節(jié)點(diǎn)都等量轉(zhuǎn)發(fā)為其服務(wù)過(guò)的鄰居節(jié)點(diǎn)的數(shù)據(jù)包。如果發(fā)現(xiàn)鄰居行為不當(dāng)，那么節(jié)點(diǎn)就會(huì)自動(dòng)降低為該鄰居提供的轉(zhuǎn)發(fā)服務(wù)量。文獻(xiàn)[13]綜合考慮了傳輸成本和相遇概率設(shè)計(jì)激勵(lì)機(jī)制，并引入博弈理論進(jìn)行路由決策。同樣，文獻(xiàn)[14]也基于博弈論對(duì)節(jié)點(diǎn)的自私行為進(jìn)行建模，在進(jìn)行路由決策時(shí)考慮了節(jié)點(diǎn)的能耗、丟包率和時(shí)延等多種因素。

激勵(lì)機(jī)制無(wú)疑能夠減少節(jié)點(diǎn)個(gè)體自私性給路由帶來(lái)的影響，但是在MSN網(wǎng)絡(luò)中節(jié)點(diǎn)除了個(gè)體自私性，還具有社會(huì)自私性。SSAR協(xié)議[11]是社會(huì)自私性感知的路由協(xié)議，將用戶的轉(zhuǎn)發(fā)意愿根據(jù)節(jié)點(diǎn)之間的社會(huì)關(guān)系進(jìn)行量化，并用于進(jìn)行路由決策。文獻(xiàn)[15]研究了DTN網(wǎng)絡(luò)中個(gè)體自私行為及社會(huì)自私行為的影響。在分析基礎(chǔ)上總結(jié)出DTN 網(wǎng)絡(luò)中社會(huì)自私行為造成的內(nèi)在威脅。HASR 協(xié)議[16]則基于人類行為的規(guī)律，提出了基于熱區(qū)的自私路由協(xié)議。沒(méi)有自私節(jié)點(diǎn)時(shí)活躍度按照節(jié)點(diǎn)訪問(wèn)的熱區(qū)的權(quán)重計(jì)算，當(dāng)存在自私節(jié)點(diǎn)時(shí)，系統(tǒng)將根據(jù)節(jié)點(diǎn)的貢獻(xiàn)指數(shù)作出路由決策。文獻(xiàn)[17]進(jìn)一步針對(duì)車載自組織網(wǎng)絡(luò)提出了基于社會(huì)貢獻(xiàn)的路由協(xié)議，轉(zhuǎn)發(fā)決策時(shí)綜合考慮了候選節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的遞交概率以及對(duì)網(wǎng)絡(luò)做出的服務(wù)貢獻(xiàn)。CAIS[18]是近年提出的一種考慮了節(jié)點(diǎn)社會(huì)關(guān)系的基于積分的激勵(lì)機(jī)制，將節(jié)點(diǎn)劃分為不同的社區(qū)，且采用了社區(qū)積分和非社區(qū)積分兩種積分，在節(jié)點(diǎn)為其他節(jié)點(diǎn)轉(zhuǎn)發(fā)數(shù)據(jù)時(shí)根據(jù)社區(qū)內(nèi)外的不同而分別給予獎(jiǎng)勵(lì)，獲得了比SSAR協(xié)議更好的性能。而ANT[19]則根據(jù)節(jié)點(diǎn)的相遇概率（遞交概率）和節(jié)點(diǎn)的合作意愿，相遇概率由歷史相遇記錄確定，合作意愿則由節(jié)點(diǎn)對(duì)之間的歷史貢獻(xiàn)和節(jié)點(diǎn)資源確定。

2 系統(tǒng)建模和問(wèn)題描述

2.1 節(jié)點(diǎn)合作度

節(jié)點(diǎn)合作度是指節(jié)點(diǎn)愿意為別的節(jié)點(diǎn)轉(zhuǎn)發(fā)數(shù)據(jù)包的意愿，與自私性是反相關(guān)的關(guān)系。節(jié)點(diǎn)自私性可以分為社會(huì)自私性和個(gè)體自私性，因此節(jié)點(diǎn)合作度包括社會(huì)合作度（Social Cooperation，SC）和個(gè)體合作度（Individual Cooperation，IC）。社會(huì)合作度依賴于彼此之間的社會(huì)關(guān)系。社會(huì)關(guān)系越強(qiáng)，它們之間的社會(huì)合作度也就越強(qiáng)，兩個(gè)節(jié)點(diǎn)為彼此轉(zhuǎn)發(fā)數(shù)據(jù)的可能性越大。但是社會(huì)合作度僅僅反映了節(jié)點(diǎn)之間的社會(huì)關(guān)系，無(wú)法反映每個(gè)個(gè)體的當(dāng)前真實(shí)意愿。

因此引入個(gè)體合作度表示節(jié)點(diǎn)的當(dāng)前真實(shí)轉(zhuǎn)發(fā)意愿，由節(jié)點(diǎn)的當(dāng)前剩余資源所決定，如剩余電量、可用帶寬或緩存或鏈路傳輸能力等。顯然節(jié)點(diǎn)當(dāng)前剩余資源越多，IC值就越大。

2.2 網(wǎng)絡(luò)模型

可以將MSN網(wǎng)絡(luò)定義為一個(gè)相遇關(guān)系的圖G=(V,E)，V為所有節(jié)點(diǎn)集合，E為節(jié)點(diǎn)之間的邊的集合。一旦兩個(gè)節(jié)點(diǎn)相遇，就在兩者之間添加一條邊，并賦予一個(gè)由用戶選擇的初始權(quán)重。這個(gè)圖反映了節(jié)點(diǎn)之間的社會(huì)關(guān)系或社會(huì)聯(lián)系。兩個(gè)節(jié)點(diǎn)接觸的越頻繁，它們互相轉(zhuǎn)發(fā)數(shù)據(jù)的意愿越強(qiáng)烈。如圖1所示，圖中每條邊都有一個(gè)權(quán)重SC，代表了兩個(gè)節(jié)點(diǎn)互相轉(zhuǎn)發(fā)數(shù)據(jù)的社會(huì)合作度，即社會(huì)關(guān)系聯(lián)系緊密的程度。SC越高，表明該邊連接的兩個(gè)節(jié)點(diǎn)更愿意為彼此轉(zhuǎn)發(fā)各自的數(shù)據(jù)。SC是[0，1]之間的實(shí)數(shù)，可以通過(guò)文獻(xiàn)[11]中提及的方法進(jìn)行計(jì)算。SC=0 表示兩個(gè)節(jié)點(diǎn)之間不存在社會(huì)關(guān)系（即從未相遇），說(shuō)明不能作為中繼節(jié)點(diǎn)；而SC 越大，說(shuō)明轉(zhuǎn)發(fā)數(shù)據(jù)的意愿越強(qiáng)烈，成為下一跳中繼節(jié)點(diǎn)的可能性就越大。例如，在圖1 中，節(jié)點(diǎn)D與節(jié)點(diǎn)J、M和E的權(quán)重分別為0.7、0.3、0.5，顯然對(duì)于節(jié)點(diǎn)D而言，它和節(jié)點(diǎn)J的社會(huì)合作度更高，更愿意為節(jié)點(diǎn)J轉(zhuǎn)發(fā)數(shù)據(jù)。

圖1 網(wǎng)絡(luò)模型

由于資源的使用隨時(shí)間變化，節(jié)點(diǎn)的當(dāng)前剩余資源也隨之變化，因此個(gè)體合作度IC 是個(gè)變量。IC 可以根據(jù)節(jié)點(diǎn)現(xiàn)存資源進(jìn)行計(jì)算。不失一般性，可以根據(jù)節(jié)點(diǎn)的當(dāng)前剩余電量與初始電量的比值來(lái)表示IC。

2.3 問(wèn)題描述

在MSN 網(wǎng)絡(luò)中，節(jié)點(diǎn)的自私行為嚴(yán)重影響數(shù)據(jù)的轉(zhuǎn)發(fā)。社會(huì)自私性和個(gè)人自私性都對(duì)路由決策產(chǎn)生影響。SSAR協(xié)議[11]允許社會(huì)自私性，通過(guò)綜合考慮用戶的意愿和接觸概率來(lái)選擇中繼節(jié)點(diǎn)從而提高網(wǎng)絡(luò)性能。然而，用戶意愿僅僅考慮了節(jié)點(diǎn)之間的社會(huì)關(guān)系，而沒(méi)有考慮用戶自身的資源限制，不能體現(xiàn)用戶的真實(shí)意愿。因?yàn)榧词箖蓚€(gè)用戶的社會(huì)關(guān)系很強(qiáng)，但是極可能由于因電量或帶寬的資源限制而無(wú)法轉(zhuǎn)發(fā)數(shù)據(jù)。而ANT 協(xié)議[19]同樣考慮了節(jié)點(diǎn)的相遇概率和用戶意愿，但是在決定用戶意愿的時(shí)候又缺乏對(duì)節(jié)點(diǎn)之間社會(huì)關(guān)系的考慮。因此，在進(jìn)行路由決策時(shí)應(yīng)該綜合考慮社會(huì)自私性和個(gè)體自私性，也即社會(huì)合作度和個(gè)體合作度。

另一方面，激勵(lì)機(jī)制是刺激自私節(jié)點(diǎn)與其他節(jié)點(diǎn)進(jìn)行合作的有效方法?；谛抛u(yù)的和基于積分的激勵(lì)機(jī)制，都需要基礎(chǔ)設(shè)施的支持，擴(kuò)展性差且部署成本高。在本機(jī)制中，當(dāng)兩個(gè)節(jié)點(diǎn)i和j相遇時(shí)，節(jié)點(diǎn)i是否為節(jié)點(diǎn)j轉(zhuǎn)發(fā)數(shù)據(jù)取決于節(jié)點(diǎn)j為它或?yàn)檎麄€(gè)網(wǎng)絡(luò)提供的貢獻(xiàn)度決定的。而貢獻(xiàn)度則由節(jié)點(diǎn)提供的數(shù)據(jù)轉(zhuǎn)發(fā)服務(wù)確定，為其他節(jié)點(diǎn)轉(zhuǎn)發(fā)的服務(wù)越多，則其貢獻(xiàn)度就越高。貢獻(xiàn)度越高的節(jié)點(diǎn)應(yīng)該更能享受到其他節(jié)點(diǎn)的轉(zhuǎn)發(fā)服務(wù)。這有點(diǎn)類似基于TFT的機(jī)制，不同之處在于節(jié)點(diǎn)貢獻(xiàn)度包含了相互貢獻(xiàn)度和社會(huì)貢獻(xiàn)度。社會(huì)貢獻(xiàn)度就是為節(jié)點(diǎn)整個(gè)網(wǎng)絡(luò)提供的轉(zhuǎn)發(fā)服務(wù)，而相互貢獻(xiàn)度則是針對(duì)兩個(gè)互相提供了轉(zhuǎn)發(fā)服務(wù)的特定節(jié)點(diǎn)對(duì)而言。傳統(tǒng)的基于TFT 的機(jī)制轉(zhuǎn)發(fā)數(shù)據(jù)時(shí)只考慮相互貢獻(xiàn)，但是這種機(jī)制對(duì)于為整個(gè)網(wǎng)絡(luò)提供了更多服務(wù)的節(jié)點(diǎn)是不公平的。例如，節(jié)點(diǎn)j為除了節(jié)點(diǎn)i之外的其他節(jié)點(diǎn)轉(zhuǎn)發(fā)了很多數(shù)據(jù)包，如果僅根據(jù)相互貢獻(xiàn)原則，那么節(jié)點(diǎn)i就會(huì)拒絕轉(zhuǎn)發(fā)節(jié)點(diǎn)j的數(shù)據(jù)。因此作出轉(zhuǎn)發(fā)決定時(shí)還應(yīng)該考慮節(jié)點(diǎn)的社會(huì)貢獻(xiàn)度。此外，傳統(tǒng)TFT中相互貢獻(xiàn)是根據(jù)兩個(gè)節(jié)點(diǎn)之間交換的總數(shù)據(jù)量來(lái)評(píng)估的。但在社會(huì)自私網(wǎng)絡(luò)中，用戶轉(zhuǎn)發(fā)數(shù)據(jù)的合作度是不一樣的。為了激勵(lì)較低合作度的節(jié)點(diǎn)參與合作，當(dāng)它為其他節(jié)點(diǎn)轉(zhuǎn)發(fā)數(shù)據(jù)時(shí)應(yīng)該獲得更多的獎(jiǎng)勵(lì)。而那些較高合作度的節(jié)點(diǎn)，特別具有較高社會(huì)合作度的，獲得的獎(jiǎng)勵(lì)可以少一些。因?yàn)樗鼈冊(cè)诰W(wǎng)絡(luò)中有更強(qiáng)的社會(huì)關(guān)系，也就具有更多服務(wù)其他節(jié)點(diǎn)的機(jī)會(huì)，并能獲得足夠的獎(jiǎng)勵(lì)。因此，應(yīng)該基于節(jié)點(diǎn)的合作度計(jì)算它們的服務(wù)量并作為對(duì)節(jié)點(diǎn)的激勵(lì)。

3 C2SR設(shè)計(jì)

3.1 節(jié)點(diǎn)合作度

在具有自私行為的MSN 網(wǎng)絡(luò)中，節(jié)點(diǎn)愿意轉(zhuǎn)發(fā)他人數(shù)據(jù)的合作度是決定路由的關(guān)鍵。合作度由社會(huì)合作度和個(gè)體合作度決定，社會(huì)合作度取決于節(jié)點(diǎn)之間的社會(huì)關(guān)系。社會(huì)合作度越強(qiáng)，意味著節(jié)點(diǎn)相遇的概率就越高，就更愿意為對(duì)方轉(zhuǎn)發(fā)數(shù)據(jù)。選擇下一跳節(jié)點(diǎn)時(shí)，與目標(biāo)節(jié)點(diǎn)之間具有更高社會(huì)合作度的候選節(jié)點(diǎn)更容易被作為下一跳中繼節(jié)點(diǎn)。數(shù)據(jù)轉(zhuǎn)發(fā)能力也受限于個(gè)體合作度。如果自私節(jié)點(diǎn)的個(gè)體合作度較低，即使與目標(biāo)節(jié)點(diǎn)具有很強(qiáng)的社會(huì)聯(lián)系，它也不情愿轉(zhuǎn)發(fā)數(shù)據(jù)。定義節(jié)點(diǎn)i愿意轉(zhuǎn)發(fā)數(shù)據(jù)到目標(biāo)節(jié)點(diǎn)j的合作度CORPij為：

當(dāng)一個(gè)節(jié)點(diǎn)同時(shí)遇到幾個(gè)節(jié)點(diǎn)時(shí)，具有更高合作度的節(jié)點(diǎn)有更大的可能作為下一跳中繼節(jié)點(diǎn)。

3.2 激勵(lì)機(jī)制

為了鼓勵(lì)自私節(jié)點(diǎn)更加無(wú)私合作，激勵(lì)機(jī)制是一種有效的方法。節(jié)點(diǎn)提供服務(wù)越多，它作出的貢獻(xiàn)也越大，得到的獎(jiǎng)勵(lì)也應(yīng)該越多。節(jié)點(diǎn)獲取的獎(jiǎng)勵(lì)是與其服務(wù)量成正比的。得到的獎(jiǎng)勵(lì)越多，意味著其他節(jié)點(diǎn)為它提供轉(zhuǎn)發(fā)服務(wù)的概率就越大。為簡(jiǎn)單起見，可以將獎(jiǎng)勵(lì)定義為節(jié)點(diǎn)所提供的服務(wù)量。當(dāng)一個(gè)節(jié)點(diǎn)轉(zhuǎn)發(fā)一個(gè)數(shù)據(jù)包到其他節(jié)點(diǎn)，可以認(rèn)為它為對(duì)方提供了1 單位服務(wù)。但對(duì)于社會(huì)關(guān)系較弱的節(jié)點(diǎn)，如果成功地轉(zhuǎn)發(fā)了數(shù)據(jù)，應(yīng)該讓它獲得更多的獎(jiǎng)勵(lì)，以刺激它更樂(lè)于參與數(shù)據(jù)轉(zhuǎn)發(fā)。定義節(jié)點(diǎn)i轉(zhuǎn)發(fā)數(shù)據(jù)包給節(jié)點(diǎn)j后的服務(wù)量Sij為：

如果節(jié)點(diǎn)i轉(zhuǎn)發(fā)數(shù)據(jù)包給節(jié)點(diǎn)j，那么節(jié)點(diǎn)i提供的是Sij個(gè)單位而不是一個(gè)單位的服務(wù)量，相應(yīng)地，它也會(huì)獲得Sij個(gè)單位的獎(jiǎng)勵(lì)。如式（2）所示，如果節(jié)點(diǎn)i和j之間的社會(huì)關(guān)系較弱（即社會(huì)合作度較低），那么節(jié)點(diǎn)將會(huì)獲得更多的獎(jiǎng)勵(lì)。類似地，如果具有較低個(gè)體合作度的節(jié)點(diǎn)為較高個(gè)體合作度的節(jié)點(diǎn)轉(zhuǎn)發(fā)數(shù)據(jù)，那么它也應(yīng)該獲得更多的獎(jiǎng)勵(lì)。顯然，節(jié)點(diǎn)i在不同的時(shí)刻為節(jié)點(diǎn)j轉(zhuǎn)發(fā)數(shù)據(jù)時(shí)，獲得的獎(jiǎng)勵(lì)Sij并不是相同的。這是因?yàn)殡S著時(shí)間的變化，兩個(gè)節(jié)點(diǎn)的合作度也在發(fā)生變化。

3.3 節(jié)點(diǎn)貢獻(xiàn)度

節(jié)點(diǎn)貢獻(xiàn)度定義為節(jié)點(diǎn)提供的數(shù)據(jù)傳輸服務(wù)能力，包括節(jié)點(diǎn)對(duì)整個(gè)網(wǎng)絡(luò)的服務(wù)貢獻(xiàn)和對(duì)特定節(jié)點(diǎn)的相互服務(wù)貢獻(xiàn)。

節(jié)點(diǎn)i為節(jié)點(diǎn)j的相互服務(wù)貢獻(xiàn)由節(jié)點(diǎn)i為節(jié)點(diǎn)j提供的服務(wù)量占這兩個(gè)節(jié)點(diǎn)對(duì)之間總服務(wù)量的比例為服務(wù)指數(shù)（Service Index，SIij）決定，即：

其中Nij為節(jié)點(diǎn)i為節(jié)點(diǎn)j提供的轉(zhuǎn)發(fā)服務(wù)次數(shù)，Nji為節(jié)點(diǎn)j為節(jié)點(diǎn)i提供的轉(zhuǎn)發(fā)服務(wù)次數(shù)。若SIij=0.5，意味著節(jié)點(diǎn)i和節(jié)點(diǎn)j互為對(duì)方提供了對(duì)等的服務(wù)量。如果SIij接近0，則表明節(jié)點(diǎn)i幾乎沒(méi)有為節(jié)點(diǎn)j提供服務(wù)?？梢钥闯觯琒Iij僅取決于兩個(gè)給定節(jié)點(diǎn)的個(gè)體合作度，而與社會(huì)合作度無(wú)關(guān)。

定義TSi，TSi′如下：

其中TSi表示節(jié)點(diǎn)i為所有其他節(jié)點(diǎn)提供的轉(zhuǎn)發(fā)服務(wù)總量，TSi′表示其他節(jié)點(diǎn)為節(jié)點(diǎn)i提供的轉(zhuǎn)發(fā)服務(wù)總量，Ψ是節(jié)點(diǎn)i提供了轉(zhuǎn)發(fā)服務(wù)的節(jié)點(diǎn)集合，Ψ′則是所有給節(jié)點(diǎn)i提供了轉(zhuǎn)發(fā)服務(wù)的節(jié)點(diǎn)集合。

對(duì)整個(gè)網(wǎng)絡(luò)來(lái)說(shuō)節(jié)點(diǎn)i的服務(wù)貢獻(xiàn)定義為網(wǎng)絡(luò)服務(wù)指數(shù)（Network Service Index，NSI）：

由式（6）可見，貢獻(xiàn)度包含兩個(gè)隱藏含義：（1）如果節(jié)點(diǎn)i和j之間的社會(huì)合作度較高，那么節(jié)點(diǎn)i的貢獻(xiàn)度主要根據(jù)節(jié)點(diǎn)i為節(jié)點(diǎn)j提供的服務(wù)量決定；（2）如果節(jié)點(diǎn)i和j之間的社會(huì)關(guān)系較弱，那么節(jié)點(diǎn)i的貢獻(xiàn)度主要根據(jù)節(jié)點(diǎn)i為整個(gè)網(wǎng)絡(luò)提供的服務(wù)量進(jìn)行評(píng)估。

3.4 數(shù)據(jù)轉(zhuǎn)發(fā)

C2SR協(xié)議中數(shù)據(jù)轉(zhuǎn)發(fā)基于中繼節(jié)點(diǎn)的合作度和貢獻(xiàn)度。與目標(biāo)節(jié)點(diǎn)具有更高合作度且貢獻(xiàn)度更小的節(jié)點(diǎn)易于被選擇作為下一跳節(jié)點(diǎn)。合作度越高，說(shuō)明候選節(jié)點(diǎn)更愿意提供數(shù)據(jù)轉(zhuǎn)發(fā)服務(wù)；貢獻(xiàn)度越小，意味著該節(jié)點(diǎn)更應(yīng)該承擔(dān)轉(zhuǎn)發(fā)服務(wù)以獲得足夠的獎(jiǎng)勵(lì)，以便能夠享受網(wǎng)絡(luò)提供的數(shù)據(jù)轉(zhuǎn)發(fā)服務(wù)。算法1 為數(shù)據(jù)轉(zhuǎn)發(fā)偽代碼。

當(dāng)節(jié)點(diǎn)i遇到幾個(gè)鄰居節(jié)點(diǎn)，它首先廣播數(shù)據(jù)包元信息（比如數(shù)據(jù)包的目標(biāo)地址）。鄰居節(jié)點(diǎn)j計(jì)算它與目標(biāo)節(jié)點(diǎn)k的合作度CORPjk，并將結(jié)果向量返回給節(jié)點(diǎn)i。該向量包括CORPjk和節(jié)點(diǎn)j的CONji。根據(jù)這個(gè)返回向量，節(jié)點(diǎn)i將具有比其自身更高CORPjk的節(jié)點(diǎn)加入候選節(jié)點(diǎn)集合φ。然后再選擇候選節(jié)點(diǎn)集合中具有最高CORPjk/CONji比例的鄰居節(jié)點(diǎn)作為下一跳節(jié)點(diǎn)。CORPjk越高，意味著候選節(jié)點(diǎn)j和目標(biāo)節(jié)點(diǎn)k的社會(huì)關(guān)系越強(qiáng)，與之相遇的可能性也就越高；CONji越低，表明節(jié)點(diǎn)j貢獻(xiàn)太小，就更有義務(wù)為網(wǎng)絡(luò)提供轉(zhuǎn)發(fā)服務(wù)以提高自己的貢獻(xiàn)度。那么在轉(zhuǎn)發(fā)數(shù)據(jù)到目標(biāo)節(jié)點(diǎn)k時(shí)，綜合考慮節(jié)點(diǎn)的合作度CORPjk和貢獻(xiàn)度CONji，選取具有最高CORPjk/CONji的節(jié)點(diǎn)j被選擇作為節(jié)點(diǎn)i的下一跳。

算法1 節(jié)點(diǎn)i的數(shù)據(jù)轉(zhuǎn)發(fā)算法

1. begin

2. 廣播緩存中數(shù)據(jù)包的目標(biāo)地址；

3. 獲得鄰居節(jié)點(diǎn)的結(jié)果向量；

4. for節(jié)點(diǎn)i緩存的每一個(gè)數(shù)據(jù)包目標(biāo)節(jié)點(diǎn)k

5. for節(jié)點(diǎn)i的每一個(gè)鄰居節(jié)點(diǎn)j

6. 計(jì)算CORPjk和CONji

7. if(CORPjk＞CORPik)then

8.φ=φj φ為節(jié)點(diǎn)i候選中繼節(jié)點(diǎn)集合

9. end if

10. end for

11. 選擇集合φ中CORPjk/CONji最大值所對(duì)應(yīng)的那個(gè)節(jié)點(diǎn)j

12. 將所有目標(biāo)為k的數(shù)據(jù)包轉(zhuǎn)發(fā)給節(jié)點(diǎn)j

13. end for

14. end

4 性能評(píng)估

4.1 實(shí)驗(yàn)設(shè)置

仿真實(shí)驗(yàn)基于INFOCOM’05[4]和INFOCOM’06[5]中的兩條真實(shí)路徑軌跡的數(shù)據(jù)集。這兩個(gè)數(shù)據(jù)集記錄了2005 年和2006 年INFOCOM 會(huì)議中，分別由41 位和78位攜帶移動(dòng)設(shè)備的參與者，在3天會(huì)議期間設(shè)備之間的相遇歷史。INFOCOM’05 數(shù)據(jù)集中包含超過(guò)2 萬(wàn)次設(shè)備之間的相遇記錄，兩個(gè)設(shè)備之間平均每天相遇4.5次；INFOCOM’06數(shù)據(jù)集則有超過(guò)19萬(wàn)次設(shè)備之間的相遇記錄，兩個(gè)設(shè)備之間平均每天相遇6.5 次。每條相遇記錄包含了兩個(gè)相遇實(shí)體ID，相遇開始時(shí)間和結(jié)束時(shí)間等信息。利用這些相遇記錄信息，可以和文獻(xiàn)[11]一樣構(gòu)建設(shè)備節(jié)點(diǎn)之間的社會(huì)關(guān)系圖，并且得到各節(jié)點(diǎn)的社會(huì)合作度SC。兩個(gè)設(shè)備節(jié)點(diǎn)相遇越頻繁，表明它們之間的社會(huì)關(guān)系越強(qiáng)，社會(huì)合作度也就越高。而節(jié)點(diǎn)的個(gè)體合作度IC則設(shè)置為節(jié)點(diǎn)的當(dāng)前剩余能量和初始能量比值。

實(shí)驗(yàn)中，每個(gè)節(jié)點(diǎn)每小時(shí)產(chǎn)生5 個(gè)數(shù)據(jù)包，并隨機(jī)選擇目標(biāo)節(jié)點(diǎn)。每個(gè)數(shù)據(jù)包都有固定的TTL，一旦TTL過(guò)期，數(shù)據(jù)包就會(huì)被丟棄。為了考察剩余能量帶來(lái)的個(gè)人轉(zhuǎn)發(fā)意愿的影響，設(shè)計(jì)了一種簡(jiǎn)單的能量消耗機(jī)制，根據(jù)文獻(xiàn)[20]的研究，典型的手持設(shè)備（如智能手機(jī)）一般正常使用情況（包括通話、短信等）下會(huì)在21 h內(nèi)用完電量。假設(shè)能量是按照每分鐘1 mA 的損失率線性遞減，每發(fā)送或接收一個(gè)數(shù)據(jù)包將消耗0.01 mA。節(jié)點(diǎn)初始能量在1 200～1 600 mA 隨機(jī)選擇，并且設(shè)置能量閾值Eth=30%。一旦節(jié)點(diǎn)的剩余能量小于閾值Eth，節(jié)點(diǎn)將表現(xiàn)出自私行為，并且將以概率IC 轉(zhuǎn)發(fā)其他節(jié)點(diǎn)的數(shù)據(jù)。

4.2 仿真結(jié)果

圖2顯示的是隨著時(shí)間的流逝，網(wǎng)絡(luò)中自私節(jié)點(diǎn)的數(shù)量在Infocom’05 和Infocom’06 數(shù)據(jù)集上的變化情形。顯然，由于設(shè)備自身的電量消耗以及轉(zhuǎn)發(fā)數(shù)據(jù)的能量消耗，使得節(jié)點(diǎn)的能量不斷減少，一旦能量低于閾值Eth，則認(rèn)為節(jié)點(diǎn)成為自私節(jié)點(diǎn)，該節(jié)點(diǎn)將表現(xiàn)出自私行為，在轉(zhuǎn)發(fā)數(shù)據(jù)時(shí)要根據(jù)概率IC進(jìn)行數(shù)據(jù)轉(zhuǎn)發(fā)。如圖2所示，對(duì)于兩個(gè)數(shù)據(jù)集的網(wǎng)絡(luò)，當(dāng)網(wǎng)絡(luò)運(yùn)行12 h左右，將出現(xiàn)自私節(jié)點(diǎn)；網(wǎng)絡(luò)運(yùn)行18 h 左右，表現(xiàn)出自私行為的節(jié)點(diǎn)比例均超過(guò)40%?？梢园l(fā)現(xiàn)，對(duì)于Infocom’05 和Infocom’06數(shù)據(jù)集，出現(xiàn)自私節(jié)點(diǎn)出現(xiàn)的情況沒(méi)有多大差別，其原因在于這兩個(gè)數(shù)據(jù)集從節(jié)點(diǎn)數(shù)量規(guī)模小，節(jié)點(diǎn)移動(dòng)受限制，因此表現(xiàn)出相似的行為。

圖2 兩個(gè)數(shù)據(jù)集上自私節(jié)點(diǎn)比例

圖3 Infocom’05數(shù)據(jù)集上數(shù)據(jù)遞交率

隨后，考察了隨著時(shí)間的流逝，網(wǎng)絡(luò)的數(shù)據(jù)遞交率的變化情況，即網(wǎng)絡(luò)在出現(xiàn)自私節(jié)點(diǎn)前后數(shù)據(jù)遞交率的變化，結(jié)果如圖3和圖4所示。由圖可以看出，所有算法的數(shù)據(jù)遞交先逐步增加，在十幾個(gè)小時(shí)的仿真時(shí)間前后一個(gè)極值，并開始下降。這主要是因?yàn)殡S著時(shí)間的增加，節(jié)點(diǎn)的能量消耗越來(lái)越多，一旦低于閾值Eth，則節(jié)點(diǎn)表現(xiàn)出自私行為，即個(gè)體合作度降低，減少了數(shù)據(jù)轉(zhuǎn)發(fā)的可能性，導(dǎo)致數(shù)據(jù)遞交率也降低。在沒(méi)有出現(xiàn)自私節(jié)點(diǎn)時(shí)，SSAR 和ANT 協(xié)議表現(xiàn)比CSR 協(xié)議稍好一些。一段時(shí)間后，它們的數(shù)據(jù)遞交率特別是SSAR協(xié)議中數(shù)據(jù)遞交率比CSR協(xié)議下降地更快。其原因是，當(dāng)節(jié)點(diǎn)能量較高的時(shí)候，SSAR中節(jié)點(diǎn)轉(zhuǎn)發(fā)數(shù)據(jù)包的概率越大，轉(zhuǎn)發(fā)的數(shù)據(jù)包就越多。隨著時(shí)間流逝，剩余能量越來(lái)越低，轉(zhuǎn)發(fā)數(shù)據(jù)包的概率也就越來(lái)越低。當(dāng)剩余能量比例低于閾值Eth，節(jié)點(diǎn)表現(xiàn)出自私行為。此時(shí)，對(duì)于SSAR協(xié)議中，計(jì)算數(shù)據(jù)包優(yōu)先級(jí)時(shí)需要乘上當(dāng)前的IC，這大大減少了節(jié)點(diǎn)的轉(zhuǎn)發(fā)行為，從而降低了數(shù)據(jù)遞交率。ANT協(xié)議由于轉(zhuǎn)發(fā)時(shí)同時(shí)考慮了節(jié)點(diǎn)的歷史相遇概率和節(jié)點(diǎn)合作意愿，因此當(dāng)節(jié)點(diǎn)合作意愿低（如剩余能量低）時(shí)仍能根據(jù)節(jié)點(diǎn)的歷史相遇概率選擇下一跳節(jié)點(diǎn)，因而仍能獲得比SSAR 協(xié)議稍高的數(shù)據(jù)遞交率。而對(duì)于C2SR協(xié)議，盡管節(jié)點(diǎn)表現(xiàn)出自私行為，當(dāng)時(shí)一方面激勵(lì)機(jī)制將會(huì)鼓勵(lì)節(jié)點(diǎn)轉(zhuǎn)發(fā)數(shù)據(jù)，另一方面選擇下一跳節(jié)點(diǎn)時(shí)還考慮了節(jié)點(diǎn)的貢獻(xiàn)度，這使得節(jié)點(diǎn)的能量消耗比ANT協(xié)議和SSAR協(xié)議中更加均衡。因此長(zhǎng)時(shí)間來(lái)看，當(dāng)網(wǎng)絡(luò)中存在自私節(jié)點(diǎn)后，C2SR 協(xié)議比ANT 協(xié)議和SSAR 協(xié)議表現(xiàn)更好。由圖3 可見，基于Infocom’05 數(shù)據(jù)集實(shí)驗(yàn)18 個(gè)小時(shí)后，C2SR 協(xié)議數(shù)據(jù)遞交率分別比ANT協(xié)議和SSAR協(xié)議各自高出9%、15%。

圖5和圖6則給出了不同數(shù)據(jù)集上各種協(xié)議的數(shù)據(jù)傳輸延遲情況。可以看出，傳輸時(shí)延的變化趨勢(shì)是相似的，在仿真初始期間傳輸時(shí)延都比較小，此后隨著仿真時(shí)間流逝，傳輸時(shí)延逐漸增大。當(dāng)網(wǎng)絡(luò)中出現(xiàn)自私節(jié)點(diǎn)后，由于自私節(jié)點(diǎn)不愿意轉(zhuǎn)發(fā)數(shù)據(jù)，導(dǎo)致傳輸時(shí)延的持續(xù)增長(zhǎng)，自私節(jié)點(diǎn)數(shù)量越多，傳輸時(shí)延就越大。而C2SR協(xié)議的傳輸時(shí)延相比于其他協(xié)議，增長(zhǎng)較為緩慢。此外，在Infocom’06 數(shù)據(jù)集中，傳輸時(shí)延要比Infocom’05數(shù)據(jù)集的結(jié)果更短，這是因?yàn)榍罢邤?shù)據(jù)集較大的緣故。

圖4 Infocom’06數(shù)據(jù)集上數(shù)據(jù)遞交率

圖5 Infocom’05數(shù)據(jù)集上的傳輸延遲

圖6 Infocom’06數(shù)據(jù)集上的傳輸延遲

圖7和圖8顯示了網(wǎng)絡(luò)中為其他節(jié)點(diǎn)提供轉(zhuǎn)發(fā)了服務(wù)的節(jié)點(diǎn)比例。顯然隨著時(shí)間的流逝，越來(lái)越多的節(jié)點(diǎn)將參與數(shù)據(jù)轉(zhuǎn)發(fā)，因此中繼節(jié)點(diǎn)比例也就越來(lái)越高。但是相比于其他協(xié)議，在C2SR協(xié)議中有更多的節(jié)點(diǎn)參與了轉(zhuǎn)發(fā)數(shù)據(jù)，這是因?yàn)镃2SR協(xié)議存在激勵(lì)機(jī)制鼓勵(lì)節(jié)點(diǎn)參與合作。對(duì)于那些貢獻(xiàn)度較低的節(jié)點(diǎn)，如果想它獲得其他節(jié)點(diǎn)的轉(zhuǎn)發(fā)服務(wù)，將不得不參與數(shù)據(jù)的轉(zhuǎn)發(fā)以提高它的貢獻(xiàn)度。而另一方面，具有較高社會(huì)合作度（SSAR 協(xié)議中指具有較強(qiáng)的社會(huì)關(guān)系，ANT 協(xié)議中是指合作意愿高的節(jié)點(diǎn)，SimBet協(xié)議中則是指具有較高中心度）的節(jié)點(diǎn)更易于被選擇作為轉(zhuǎn)發(fā)數(shù)據(jù)的下一跳；反之，具有較弱社會(huì)關(guān)系或較低中心度的節(jié)點(diǎn)不容易被作為中繼節(jié)點(diǎn)。因此，SSAR協(xié)議和SimBet協(xié)議的中繼節(jié)點(diǎn)的比例要低些。

圖7 Infocom’05數(shù)據(jù)集上參與節(jié)點(diǎn)比例

圖8 Infocom’06數(shù)據(jù)集上參與節(jié)點(diǎn)比例

5 結(jié)論

本文提出了一種基于用戶合作和貢獻(xiàn)的MSN網(wǎng)絡(luò)自私路由協(xié)議C2SR。C2SR 協(xié)議針對(duì)網(wǎng)絡(luò)中存在自私節(jié)點(diǎn)的現(xiàn)象，在進(jìn)行路由決策時(shí)同時(shí)考慮了用戶的合作度和貢獻(xiàn)度。其中合作度包括社會(huì)合作度和個(gè)體合作度，前者表明節(jié)點(diǎn)的社會(huì)關(guān)系強(qiáng)弱，后者則反映節(jié)點(diǎn)當(dāng)前的剩余資源；貢獻(xiàn)度包含網(wǎng)絡(luò)貢獻(xiàn)度和節(jié)點(diǎn)對(duì)之間的相互貢獻(xiàn)，前者表示該節(jié)點(diǎn)對(duì)整個(gè)網(wǎng)絡(luò)提供的服務(wù)量，后者表示針對(duì)特定節(jié)點(diǎn)提供的服務(wù)量。具有和目標(biāo)節(jié)點(diǎn)更高合作度，并且貢獻(xiàn)度更低的候選節(jié)點(diǎn)更適合作為下一跳節(jié)點(diǎn)轉(zhuǎn)發(fā)數(shù)據(jù)。仿真結(jié)果表明，當(dāng)網(wǎng)絡(luò)中存在自私節(jié)點(diǎn)時(shí)，C2SR 比SSAR 和ANT 等協(xié)議具有更好的性能，而激勵(lì)機(jī)制的有效性，使得C2SR 協(xié)議中節(jié)點(diǎn)的能量消耗更為均衡，有更多的節(jié)點(diǎn)參與了數(shù)據(jù)轉(zhuǎn)發(fā)工作。