基于合作貢獻的移動社會網絡自私路由協議

余玲飛，龔海剛

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

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

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

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

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

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

1 相關工作

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

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

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

2 系統建模和問題描述

2.1 節點合作度

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

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

2.2 網絡模型

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

圖1 網絡模型

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

2.3 問題描述

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

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

3 C2SR設計

3.1 節點合作度

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

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

3.2 激勵機制

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

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

3.3 節點貢獻度

節點貢獻度定義為節點提供的數據傳輸服務能力，包括節點對整個網絡的服務貢獻和對特定節點的相互服務貢獻。

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

其中Nij為節點i為節點j提供的轉發服務次數，Nji為節點j為節點i提供的轉發服務次數。若SIij=0.5，意味著節點i和節點j互為對方提供了對等的服務量。如果SIij接近0，則表明節點i幾乎沒有為節點j提供服務。可以看出，SIij僅取決于兩個給定節點的個體合作度，而與社會合作度無關。

定義TSi，TSi′如下：

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

對整個網絡來說節點i的服務貢獻定義為網絡服務指數（Network Service Index，NSI）：

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

3.4 數據轉發

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

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

算法1 節點i的數據轉發算法

1. begin

2. 廣播緩存中數據包的目標地址；

3. 獲得鄰居節點的結果向量；

4. for節點i緩存的每一個數據包目標節點k

5. for節點i的每一個鄰居節點j

6. 計算CORPjk和CONji

7. if(CORPjk＞CORPik)then

8.φ=φj φ為節點i候選中繼節點集合

9. end if

10. end for

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

12. 將所有目標為k的數據包轉發給節點j

13. end for

14. end

4 性能評估

4.1 實驗設置

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

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

4.2 仿真結果

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

圖2 兩個數據集上自私節點比例

圖3 Infocom’05數據集上數據遞交率

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

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

圖4 Infocom’06數據集上數據遞交率

圖5 Infocom’05數據集上的傳輸延遲

圖6 Infocom’06數據集上的傳輸延遲

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

圖7 Infocom’05數據集上參與節點比例

圖8 Infocom’06數據集上參與節點比例

5 結論

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