基于社会特征能量感知的容迟网组播协议

孙海霞，雷 萌，高 屹

(西藏民族大学 信息工程学院 西藏光信息处理与可视化技术重点实验室，陕西 咸阳 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