基于等级社区结构的移动社交网络数据转发方法

摘要

本发明公开了一种基于等级社区结构的移动社交网络数据转发方法，网络中节点统计其它节点与其联系的次数，并且根据朋友的定义计算自己的朋友圈；节点相遇时交换彼此的朋友圈，通过计算得到网络朋友关系图；数据包携带者根据网络朋友关系图计算目的节点所在的大小社区；根据数据包携带者的三种不同位置设计了不同的数据转发策略，具体为在目的节点所在小社区内、在目的节点所在小社区外且在目的节点所在大社区内、在目的节点所在大社区外，中继节点的数量逐渐减少。本发明可以大幅度地降低网络开销，同时接近传染病方法达到的最大传递率。

主权项

基于等级社区结构的移动社交网络数据转发方法，其特征在于，该方法具体步骤如下：(1)网络中节点统计其它节点与其联系的次数，并且根据朋友的定义计算自己的朋友圈，具体过程如下：(1.1)变量R_j表示与节点j接触过的节点集合，定义另外一个节点i对于节点j的累计接触比例为：其中c_i,j表示节点i和节点j累计接触次数，|R_j|是集合R_j的势，r_j,k是节点j的邻居集合R_j中第k个节点；CCR_i,j表示节点i对于节点j的累计接触次数平方，与节点j的邻居集合R_j中所有节点跟节点j接触次数平方和的比值；(1.2)为了标识与节点j频繁接触的节点，设定一个阈值其中n为网络中节点数目，λ是一个实数可以根据不同的应用场合而设定不同的值；(1.3)在节点j，如果另外一个节点i对于节点j的累计接触比例CCR_i,j≥CCR_thr，则称节点i属于节点的j的朋友圈；(2)节点相遇时交换彼此的朋友圈，通过计算得到网络朋友关系图，具体过程如下：(2.1)如果节点i和节点j属于彼此的朋友圈，即CCR_i,j≥CCR_thr而且CCR_j,i≥CCR_thr，则称节点i和节点j是朋友关系，当节点i和节点j是朋友关系时，定义变量f_i,j的值为1，否则它的值为0；(2.2)通过相遇的节点彼此交换朋友圈，每个节点可以得到一个网络朋友关系图，用G＝(V,E)表示；其中，V表示图中的节点集合，E表示图中边的集合；如果节点i和节点j是朋友关系，则它们之间存在一条边；(3)数据包携带者根据网络朋友关系图计算目的节点所在的大小社区，为数据转发做准备，具体过程如下：(3.1)一般情况下，一个节点的朋友们之间也有可能是朋友，因此，将彼此之间都是朋友关系的节点集合定义为一个小社区；可以根据网络朋友关系图G＝(V,E)得到目的节点所在大小社区们；(3.2)小社区是一个所有成员节点彼此都是朋友的节点集合，如果可以找到目的节点所在的小社区，就可以直接或者间接地通过这些目的节点的朋友快速有效地传递数据包到达目的节点；(3.3)接着，在小社区的基础上，定义一个由若干小社区组成的大社区，它的定义为：如果两个小社区之间存在至少K对朋友节点，称它们属于同一个大社区，根据目的节点所在的小社区之间的朋友对数目，可以得到目的节点所在的大社区们；(4)如果数据包携带者节点j位于目的节点所在小社区内，则节点j会将数据包传递给每一个属于SC_d且没有该数据包拷贝的相遇节点，从而迅速有效地传递数据包给目的节点d；其中，变量SC_d表示目的节点d所在的小社区们的节点集合；同时，限制数据包在小社区中最多经过三跳到达目的节点。(5)如果数据包携带者节点j在目的节点所在小社区外且在目的节点所在的大社区内，则分为四种情况分别处理：(5.1)如果目的节点d∈R_j，节点j直接转发数据包给目的节点d；(5.2)如果目的节点并且则选择节点i作为中继点转发数据包；(5.3)如果目的节点R_j∩SC_d＝φ，并且节点i在SC_d中至少存在一个朋友节点，则选择节点集合M_j＝{i|CCR_i,k≥CCR_thr或者CCR_k,i≥CCR_thr,k∈SC_d并且i∈R_j}中的节点作为中继点；(5.4)否则，对于集合R_j中每个节点，计算它的朋友节点数目；选择朋友节点数最多的节点N_s，即作为中继点转发数据包；其中，|R_j|是集合R_j的势，r_j,k是集合R_j第k个节点，是集合的势，是集合中第i个节点；(6)如果数据包携带者节点j在目的节点所在大社区外，则分为四种情况分别处理：(6.1)如果目的节点d∈R_j，则节点j直接转发数据包给目的节点d；并且如果则选择节点i作为中继点转发数据包；(6.2)如果目的节点并且R_j∩BC_d≠φ，其中BC_d表示目的节点d所在的大社区们的节点集合，则选择集合R_j∩BC_d中节点，而且在SC_d中朋友节点数目最多的节点M_a，即作为中继点；其中，|BC_d|是集合BC_d的势，r_j,w是集合R_j第w个节点，sc_d,k是集合SC_d第k个节点；(6.3)如果目的节点R_j∩BC_d＝φ，并且节点k存在朋友节点在集合BC_d中；如果节点k不唯一，则选择在BC_d中朋友节点数最多的节点作为中继点，记为M_b，即作为中继节点，其中，bc_d,k是集合BC_d中第k个节点；(6.4)否则，对于集合R_j中每个节点，计算它们的朋友节点数目，则选择朋友节点数目最多的那个节点，记为N_b，即作为中继节点。