余玲飛，龔海剛

1.浙江工商大學 杭州商學院，杭州310018

2.電子科技大學 計算機科學與工程學院，成都611731

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

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

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

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

1 相關工作

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

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

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

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

2.1 節(jié)點合作度

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

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

2.2 網(wǎng)絡模型

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

圖1 網(wǎng)絡模型

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

2.3 問題描述

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

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

3 C2SR設計

3.1 節(jié)點合作度

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

當一個節(jié)點同時遇到幾個節(jié)點時，具有更高合作度的節(jié)點有更大的可能作為下一跳中繼節(jié)點。

3.2 激勵機制

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

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

3.3 節(jié)點貢獻度

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

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

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

定義TSi，TSi′如下：

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

對整個網(wǎng)絡來說節(jié)點i的服務貢獻定義為網(wǎng)絡服務指數(shù)（Network Service Index，NSI）：

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

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

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

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

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

1. begin

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

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

4. for節(jié)點i緩存的每一個數(shù)據(jù)包目標節(jié)點k

5. for節(jié)點i的每一個鄰居節(jié)點j

6. 計算CORPjk和CONji

7. if(CORPjk＞CORPik)then

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

9. end if

10. end for

11. 選擇集合φ中CORPjk/CONji最大值所對應的那個節(jié)點j

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

13. end for

14. end

4 性能評估

4.1 實驗設置

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

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

4.2 仿真結果

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

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

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

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

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

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

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

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

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

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

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

5 結論

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