孫海霞，雷 萌，高 屹

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

?

基于社會特征能量感知的容遲網(wǎng)組播協(xié)議

孫海霞，雷 萌，高 屹

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

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

容遲網(wǎng)絡(luò)；組播；能量；社會特征；中心度

有效的數(shù)據(jù)傳輸是容遲網(wǎng)DTN(Delay-Tolerant Network)最重要的性能要求[1-3]。然而，由于網(wǎng)絡(luò)分割頻繁、節(jié)點移動的不可預(yù)測性，給DTN的數(shù)據(jù)傳輸提出了挑戰(zhàn)。文獻(xiàn)[1]綜述了現(xiàn)有DTN中的數(shù)據(jù)傳輸方案。這些方案可分為基于泛洪和基于預(yù)測兩類，如傳染路由、先知路由。它們利用DTN節(jié)點的移動實現(xiàn)數(shù)據(jù)傳遞，共同特性在：利用節(jié)點間隨機性相遇，選擇合適的節(jié)點轉(zhuǎn)發(fā)數(shù)據(jù)。由于節(jié)點移動不可預(yù)測，節(jié)點間連接呈間歇性，而僅依賴于節(jié)點隨機相遇再選擇轉(zhuǎn)發(fā)節(jié)點，是難以保證DTN內(nèi)數(shù)據(jù)傳輸?shù)母咝缘摹?/p>

為了克服這些問題，需要設(shè)計一個有效的轉(zhuǎn)發(fā)方案，能夠選擇最優(yōu)的轉(zhuǎn)發(fā)節(jié)點。隨著社會媒體的日益發(fā)展，節(jié)點具備了依據(jù)穩(wěn)固的社會特征決策轉(zhuǎn)發(fā)的能力。為此，研究人員將社會網(wǎng)絡(luò)思想引入DTN的路由協(xié)議中。它利用社會網(wǎng)絡(luò)的關(guān)系、相似度、中心度以及社區(qū)等信息選擇轉(zhuǎn)發(fā)節(jié)點，其中，中心度常用于基于社會轉(zhuǎn)發(fā)方案[4]。文獻(xiàn)[5]提出基于中心度和社區(qū)決策轉(zhuǎn)發(fā)節(jié)點，文獻(xiàn)[6]提出了SimBet路由，它利用了兩個社會特征(中心度和相似度)選擇轉(zhuǎn)發(fā)節(jié)點。多數(shù)基于社會的數(shù)據(jù)傳輸方案均是以數(shù)據(jù)傳輸?shù)絾我坏哪康墓?jié)點為目的。然而，在真實應(yīng)用場景中，如災(zāi)難管理，數(shù)據(jù)可能需要傳輸?shù)蕉鄠€目的節(jié)點，即組播。例如，在稀疏的車聯(lián)網(wǎng)VANETs(Vehicular Ad Hoc Networks)中，車輛可能需要將實時的交通信息傳輸至后方多個車輛。戰(zhàn)場中多個移動節(jié)點可能需要共享信息。然而，由于容遲網(wǎng)絡(luò)DTN通信連接的間歇性，在DTN內(nèi)實現(xiàn)組播存在巨大的挑戰(zhàn)。

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

為此，以SDM協(xié)議為基礎(chǔ)，提出基于社會特征的能量感知的容遲網(wǎng)絡(luò)的組播SCEAM(Social Characteristics Energy-Aware based Multicast)協(xié)議。該協(xié)議可應(yīng)用于移動網(wǎng)絡(luò)、車聯(lián)網(wǎng)等無線自組織網(wǎng)絡(luò)。利用節(jié)點的中心度和能量選擇轉(zhuǎn)發(fā)節(jié)點，仿真結(jié)果表明，與SDM方案相比，組播業(yè)務(wù)提高了近27%，數(shù)據(jù)傳輸率提高了14%。

1 系統(tǒng)模型

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

圖1 13個節(jié)點的社會關(guān)系圖G

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

2 提出的SCEAM算法

2.1 建立目標(biāo)函數(shù)

SDM方案利用節(jié)點的社會特征向目的節(jié)點轉(zhuǎn)發(fā)數(shù)據(jù)。在特定的時間內(nèi)，為了滿足基本的數(shù)據(jù)傳輸率要求，SDM方案利用節(jié)點的中心度選擇轉(zhuǎn)發(fā)節(jié)點，并且盡可能最小化轉(zhuǎn)發(fā)節(jié)點數(shù)。依據(jù)文獻(xiàn)[7]，節(jié)點i的中心度定義如

(1)

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

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

因此，為了提高網(wǎng)絡(luò)性能(數(shù)據(jù)傳輸率、時延以及網(wǎng)絡(luò)壽命)，應(yīng)盡可能使中心度高的節(jié)點保持活動狀態(tài)，即讓中心度高的節(jié)點能量消耗速度緩慢，從而維持整個網(wǎng)絡(luò)壽命。在這種情況下，單一數(shù)據(jù)組播問題被轉(zhuǎn)發(fā)為：需將單一數(shù)據(jù)Data傳輸?shù)蕉鄠€目的節(jié)點，假定目的節(jié)點集為D，在特寫時間T內(nèi)，在滿足數(shù)據(jù)傳輸率p要求的條件下，如何最小化轉(zhuǎn)發(fā)節(jié)點數(shù)，又使得轉(zhuǎn)發(fā)節(jié)點的能量最高。

實際上，上述問題是兩目標(biāo)優(yōu)化問題。在滿足數(shù)據(jù)傳輸率要求的約束條件下，如何使得轉(zhuǎn)發(fā)節(jié)點數(shù)最少和轉(zhuǎn)發(fā)節(jié)點能量最高。為此，對此問題進(jìn)行形式化表述。

(2)

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

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

(3)

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

(4)

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

(5)

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

(6)

接下來，求解目標(biāo)問題的解。

2.2 貪婪算法求解

假定轉(zhuǎn)發(fā)節(jié)點集為ψ，最初為空，即ψ=φ。然后，從高概率集Rhigh內(nèi)選擇能量最高的節(jié)點作為第一轉(zhuǎn)發(fā)節(jié)點，如

(7)

(8)

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

圖2 算法流程圖

2.3 選擇轉(zhuǎn)發(fā)節(jié)點的示例

圖3 選擇轉(zhuǎn)發(fā)節(jié)點過程示意圖

3 性能分析

3.1 仿真場景

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

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

3.2 仿真結(jié)果分析

1) ANMS

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

圖4 ANMS隨數(shù)據(jù)傳輸率的變化情況

2) ANRS

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

圖5 ANRS隨數(shù)據(jù)傳輸率的變化情況

3) ANHCAS

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

圖6 ANHCAS隨數(shù)據(jù)傳輸率的變化情況

從上述仿真數(shù)據(jù)可知，SCEAM方案比SDM方案需要多一些轉(zhuǎn)發(fā)節(jié)點，能夠有效地使用高概率節(jié)點滿足DTN的數(shù)據(jù)傳輸要求。因此，SCEAM方案能夠支持更多的組播業(yè)務(wù)，拓延網(wǎng)絡(luò)壽命。

4 小結(jié)

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

[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]洪棒，俞立，張貴軍. 無線傳感網(wǎng)絡(luò)自適應(yīng)分布式聚簇路由協(xié)議[J].自動化學(xué)報，2011，37(10)：1197-1206.

[3]羅娟，肖儀，盧真，等.基于網(wǎng)絡(luò)編碼的多播車載網(wǎng)絡(luò)路由算法研究[J].計算機研究與發(fā)展，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，F(xiàn)ITZEK 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— )，女，副教授，主要研究領(lǐng)域為計算機應(yīng)用技術(shù)與網(wǎng)絡(luò)技術(shù)；

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

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

責(zé)任編輯：許 盈

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

孫海霞，雷萌，高屹. 基于社會特征能量感知的容遲網(wǎng)組播協(xié)議[J].電視技術(shù)，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

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

2016-03-10