基于社會特征能量感知的容遲網組播協議

孫海霞，雷 萌，高 屹

(西藏民族大學 信息工程學院 西藏光信息處理與可視化技術重點實驗室，陜西 咸陽 712082)

?

基于社會特征能量感知的容遲網組播協議

孫海霞，雷 萌，高 屹

(西藏民族大學 信息工程學院 西藏光信息處理與可視化技術重點實驗室，陜西 咸陽 712082)

由于容遲網DTN(Delay-Tolerant Network)節點間連接的間歇性，節點只能依據機會性相遇轉發數據。為此，提出基于社會特征的能量感知的容遲網絡的組播SCEAM(Social Characteristics Energy-Aware based Multicast) 協議。將社會網絡思想引入DTN的路由協議，進而選擇合適的轉發節點傳輸數據，這充分利用了節點的長期和較穩定的社會特征知識進行決策轉發數據。SCEAM協議就利用節點最重要的社會特征——中心度，并考慮節點能量兩項信息選擇轉發節點。仿真數據表明，提出的SCEAM協議在滿足數據傳輸率的要求下，能夠支持更多的組播業務，與SDM協議相比，組播業務提高了近27%。

容遲網絡；組播；能量；社會特征；中心度

有效的數據傳輸是容遲網DTN(Delay-Tolerant Network)最重要的性能要求[1-3]。然而，由于網絡分割頻繁、節點移動的不可預測性，給DTN的數據傳輸提出了挑戰。文獻[1]綜述了現有DTN中的數據傳輸方案。這些方案可分為基于泛洪和基于預測兩類，如傳染路由、先知路由。它們利用DTN節點的移動實現數據傳遞，共同特性在：利用節點間隨機性相遇，選擇合適的節點轉發數據。由于節點移動不可預測，節點間連接呈間歇性，而僅依賴于節點隨機相遇再選擇轉發節點，是難以保證DTN內數據傳輸的高效性的。

為了克服這些問題，需要設計一個有效的轉發方案，能夠選擇最優的轉發節點。隨著社會媒體的日益發展，節點具備了依據穩固的社會特征決策轉發的能力。為此，研究人員將社會網絡思想引入DTN的路由協議中。它利用社會網絡的關系、相似度、中心度以及社區等信息選擇轉發節點，其中，中心度常用于基于社會轉發方案[4]。文獻[5]提出基于中心度和社區決策轉發節點，文獻[6]提出了SimBet路由，它利用了兩個社會特征(中心度和相似度)選擇轉發節點。多數基于社會的數據傳輸方案均是以數據傳輸到單一的目的節點為目的。然而，在真實應用場景中，如災難管理，數據可能需要傳輸到多個目的節點，即組播。例如，在稀疏的車聯網VANETs(Vehicular Ad Hoc Networks)中，車輛可能需要將實時的交通信息傳輸至后方多個車輛。戰場中多個移動節點可能需要共享信息。然而，由于容遲網絡DTN通信連接的間歇性，在DTN內實現組播存在巨大的挑戰。

為此，研究人員將社會特征引入組播路由方案[7]。文獻[7]提出了單一數據的組播方案SDM(Single-Data Multicast) 。然而，SDM方案并沒有考慮節點的能量問題。眾所周知，能量在各類網絡中扮演了重要的角色。因為，多數節點是采用電池供電，并且給節點充電并不具有可操作性。如果節點沒有足夠的能量完成轉發任務，數據將被丟失。因此，能量在DTN是一個關鍵的參數，特別是在災難場景，節點經常安裝在無法連接于電源的地方。在這種場景下，網絡內的所有活動應考慮節點的剩余能量，這也包括轉發節點的選擇活動。由于基于社會方案最初是針對社會網絡設計的，它們并沒有考慮能量參數。盡管文獻[8]在單播路由方案考慮了能量，但是目前沒有人將能量參數引入組播路由協議中。

為此，以SDM協議為基礎，提出基于社會特征的能量感知的容遲網絡的組播SCEAM(Social Characteristics Energy-Aware based Multicast)協議。該協議可應用于移動網絡、車聯網等無線自組織網絡。利用節點的中心度和能量選擇轉發節點，仿真結果表明，與SDM方案相比，組播業務提高了近27%，數據傳輸率提高了14%。

1 系統模型

圖1顯示了13個節點的社會關系圖G。在圖1a中13個節點隨機分布，兩節點間的虛線表示這兩個節點曾經至少相遇過一次。換言之，若兩節點間沒有虛連線，就意味著這兩個節點至今沒有相遇過。例如，節點I和J曾經至少相遇過一次。通過節點間的相遇次數，建立的社會關系如圖1b所示。傳統的社會關系接觸圖是沒有權值的，本文引用權值，并將兩節點相遇次數作為權值。如圖1b所示，權值λij表示節點I和J間權值，反映了這兩個節點的相遇次數。

圖1 13個節點的社會關系圖G

此外，在社會關系圖中，將節點相遇其他節點的概率定義為中心度(Centrality)。因此，若節點具有接觸大量節點的機會，它的中心度越高，說明此節點越活躍。由于中心度高的節點能夠頻繁地接觸其他節點，將它作為傳輸消息的轉發節點是合理的選擇。從圖1b可知，節點D的中心度最高，因此，它可作為潛在的轉發節點。

2 提出的SCEAM算法

2.1 建立目標函數

SDM方案利用節點的社會特征向目的節點轉發數據。在特定的時間內，為了滿足基本的數據傳輸率要求，SDM方案利用節點的中心度選擇轉發節點，并且盡可能最小化轉發節點數。依據文獻[7]，節點i的中心度定義如

(1)

式中：N表示網絡內總的節點數；λij表示節點i與j間相遇率；T為觀察時間。從式(1)可知，節點i的中心度Ci表示在特定時間T內節點i與網絡內其他節點相遇的平均概率。

然而，SDM方案在選擇轉發節點時，僅考慮了節點的中心度，并沒有考慮節點的能量。若一個節點具有高的中心度，那么它被選擇為轉發節點的機會將很多，這就導致在每次組播時，它都可能成為轉發節點，這也必然增加了它的工作負擔。盡管高的中心度對數據轉發是非常必要的，但是也需要考慮節點的能量。一旦節點能量耗盡，它也無法完成數據的轉發，縮短了網絡壽命。如果節點能量水平低，不論它的中心度有多高，也無法完成數據傳輸的任務。

因此，為了提高網絡性能(數據傳輸率、時延以及網絡壽命)，應盡可能使中心度高的節點保持活動狀態，即讓中心度高的節點能量消耗速度緩慢，從而維持整個網絡壽命。在這種情況下，單一數據組播問題被轉發為：需將單一數據Data傳輸到多個目的節點，假定目的節點集為D，在特寫時間T內，在滿足數據傳輸率p要求的條件下，如何最小化轉發節點數，又使得轉發節點的能量最高。

實際上，上述問題是兩目標優化問題。在滿足數據傳輸率要求的約束條件下，如何使得轉發節點數最少和轉發節點能量最高。為此，對此問題進行形式化表述。

(2)

接下來，分析約束條件。首先，節點能量限制。假定Eth表示節點成為轉發節點的能量門限值，只有能量大于門限值的節點才可能成為轉發節點，如

Eixi>Eth，i=1,2，3，…,k

(3)

式(3)限制了每個轉發節點有足夠的能量轉發數據。其次，要滿足數據傳輸率的要求。假定βi表示數據攜帶節點S在時間T內不選擇鄰居節點Ri作為轉發節點的概率，定義如

(4)

將式(1)代入式(4)，可得

(5)

顯然，節點的中心度越高，概率βi可能越小。由于DTN內節點能夠相互交互它們βi和Ei的值，數據攜帶節點S知道它所接觸過的節點這兩項數據。假定數據傳輸率要達到P，對于隨機選擇的節點，如果被選擇為轉發節點的鄰居節點Ri與該隨機選擇相遇的概率低于1-P時[7]，才能保證數據傳輸率不小于P，如

(6)

接下來，求解目標問題的解。

2.2 貪婪算法求解

假定轉發節點集為ψ，最初為空，即ψ=φ。然后，從高概率集Rhigh內選擇能量最高的節點作為第一轉發節點，如

(7)

(8)

類似地，將Rl加入ψ。再判斷是否滿足式(6)，若不滿足，繼續添加轉發節點，直到滿足。最終，轉發節點集ψ內的元素為數據包攜帶節點S的轉發節點。整個貪婪算法的流程如圖2所示。

圖2 算法流程圖

2.3 選擇轉發節點的示例

圖3 選擇轉發節點過程示意圖

3 性能分析

3.1 仿真場景

利用NS2仿真軟件建立仿真平臺。將bluetooth網絡為研究對象，N=41個節點隨機分布于1 000 m×1 000 m區域。引用文獻[10]的移動節點能量消耗模型。節點接收和發送消息所消耗的能量分別為432 mW和425 mW[10]。觀察時間T=16 h。

假定數據包攜帶節點S有多個組播業務，在每個業務中，以變化的數據包傳輸率p為約束條件，數據包攜帶節點S將固定尺寸的數據傳播到多個目的節點。每個實驗獨立仿真100次，取平均數據作為最終的傳真數據。此外，考慮3項性能指標分析SCEAM算法性能，分別為：1)組播業務數量ANMS(Average Numbers of Multicast Sessions)；2)每次業務所需的轉發節點數ANRS(Average Numbers of Relays used per Sessions)；3)每次業務中處于活動狀態的高中心度節點數ANHCAS(Average Number of High-Centrality Alive per Sessions)。

3.2 仿真結果分析

1) ANMS

圖4描述ANMS隨數據包傳輸率p變化曲線。從圖4可知，ANMS隨著傳輸率p的增加而下降，原因在于：由于具有高概率節點能夠有效地傳輸數據，它們在數據傳輸中扮演著重要作用。因此，傳輸率p越高，需要的高中心度節點越多。然而，這些高概率節點受能量限制，它們中的部分節點不能夠轉發數據，因此，ANMS下降。此外，與SDM方案相比，提出的SCEAM的ANMS得到提高。這主要是因為SCEAM方案并非要求所有高概率節點參與數據轉發，存儲了更多的能量將來使用，這就使得SCEAM比SDM能夠支持更多的組播業務。從圖4可知，SCEAM比SDM的ANMS至少提高了27%。

圖4 ANMS隨數據傳輸率的變化情況

2) ANRS

ANRS隨傳輸率變化曲線如圖5所示。從圖5可知，SDM和SCEAM的ANRS均隨傳輸率p的增加而上升。然而，SCEAM方案的ANRS略高于SDM。原因在于：SCEAM方案并沒有使用所有的高概率節點轉發數據，僅在滿足傳輸率要求的條件下，使用了部分高概率節點。注意到，當p=0.3時，SCEAM方案比SDM方案的ANRS增加近2%，而當p=0.9時，增加近11%。

圖5 ANRS隨數據傳輸率的變化情況

3) ANHCAS

圖6顯示了ANHCAS隨數據傳輸率的變化情況。從圖6可知，SDM和SCEAM方案的ANHCAS隨數據傳輸率的增加而上升。這正如上述分析的，需要更多的高概率節點實現高數據傳輸率。與SDM方案相比，提出的SCEAM方案的ANHCAS得到提高，在數據傳輸率整個變化區域內，SCEAM方案的ANHCAS至少提高了14%。

圖6 ANHCAS隨數據傳輸率的變化情況

從上述仿真數據可知，SCEAM方案比SDM方案需要多一些轉發節點，能夠有效地使用高概率節點滿足DTN的數據傳輸要求。因此，SCEAM方案能夠支持更多的組播業務，拓延網絡壽命。

4 小結

針對容遲網絡DTN內的組播問題，提出基于社會特征的能量感知的容遲網絡的組播SCEAM協議。考慮到DTN網絡的通信連接率低的情況，將社會網絡引入組播協議。利用節點的長期和較穩定的社會特征知識進行決策數據轉發。首先，依據組播的性能要求，即滿足數據傳輸率要求的同時，使得轉發節點數少，且網絡能量消耗均衡。根據這個目標，建立目標函數，然后再利用貪婪算法求解。仿真結果表明，提出的SCEAM協議能夠有效地提高組播業務，比SDM提高了近27%，并且處于高概率節點的能量多于SDM。這些數據表明，通過中心度和能量選擇轉發節點能夠有效提高數據傳輸性能。

[1]GONG H，YU L. Study on routing protocols for delay tolerant mobile networks[J]. International Journal of distributed sensor networks，2013，2(3)：23-32.

[2]洪棒，俞立，張貴軍. 無線傳感網絡自適應分布式聚簇路由協議[J].自動化學報，2011，37(10)：1197-1206.

[3]羅娟，肖儀，盧真，等.基于網絡編碼的多播車載網絡路由算法研究[J].計算機研究與發展，2011，48(9)：1616-

1622.

[4]ZHU Y，XU B，SHI X，et al. A survey of social-based routing in delay tolerant networks：Positive and negative social effects[J].IEEE communications surveys and tutorials，2013，15(1)：24-32.

[5]MARSDEN P. Egocentric and sociocentric measures of network centrality[J].Social networks，2012，24(4)：407-422.

[6]DALY E，HAAHR M. Social network analysis for routing in disconnected delay-tolerant MANETs[J]. MobiHoc，2007，3(9)：34-51.

[7]GAO W，LI Q，ZHAO B，et al. Social-aware multicast in disruption-tolerant networks[J].IEEE/ACM Transactions on Networking，2012，20(5)：21-30.

[8]CHILIPIREA C，PETRE A C，DOBRE C. Energy-aware social based routing in opportunistic networks[C]//Proc. 27th International Conference on Advanced Information Networking and Applications Workshops.[S.l.]：IEEE，2013：45-50.

[9]HOSSMANN T，SPYROPOULOS T，LEGENDRE F. Know thy neighbor：towards optimal mapping of contacts to social graphs for DTN routing[C]//Proc. IEEE INFOCOM.[S.l.]：IEEE，2010：1-9.

[10]PERRUCCI G，FITZEK F，WIDMER J.Survey on energy consumption entities on the smartphone platform[C]//Proc. IEEE 73rd Vehicular Technology Conference VTC Spring.[S.l.]：IEEE，2011：1-6.

孫海霞(1972— )，女，副教授，主要研究領域為計算機應用技術與網絡技術；

雷 萌(1981— )，女，碩士，講師，主要研究領域為計算機軟件與理論、圖形圖像處理；

高 屹(1981— )，碩士，副教授，主要研究領域為數據處理與數據挖掘。

責任編輯：許 盈

Social characteristics energy-aware based multicast in delay tolerant network

SUN Haixia, LEI Meng, GAO Yi

(XizangKeyLaboratoryofOpticalInformationProcessingandVisualizationTechnology，InformationTechnologyCollege，XizangMinzuUniversity，ShanxiXianyang712082，China)

In delay-tolerant networks (DTN), nodes forward data opportunistically upon contact because of irregular connectivity and low network-denseness. Therefore, social characteristics energy-aware based Multicast (SCEAM)in delay tolerant network is proposed in this paper. Using concepts of social networks in the design of DTN routing schemes, SCEAM protocol selects appropriate relay nodes for data forwarding. This is because of its ability to make forwarding decisions based on the knowledge of long-term and more stable social characteristics of the nodes. The proposed scheme selects relays for delivering data to the destinations based on the centrality, one of the important social network characteristics, as well as on the residual energy of the DTN nodes. Simulation results show that our scheme supports higher number of multicast sessions while achieving required data delivery ratio. Compared with SDM, number of multicast sessions of SCEAM is improved by 27%.

delay-tolerant network; multicast; energy; social characteristics ; centrality

孫海霞，雷萌，高屹. 基于社會特征能量感知的容遲網組播協議[J].電視技術，2016，40(11)：64-69. SUN H X，LEI M，GAO Y. Social characteristics energy-aware based multicast in delay tolerant network [J].Video engineering，2016，40(11)：64-69.

TP393

A

10.16280/j.videoe.2016.11.014

西藏自治區自然科學基金項目(2015ZR-14-18)

2016-03-10