论文部分内容阅读
【摘 要】机会网络由于不要求网络的全连通，更适合实际的自组网需求，对实现普适计算具有重大影响。然而，因拓扑结构不断变化，可能不存在端到端连接，使得机会网络的路由算法研究非常具有挑战性。本文基于真实的轨迹数据，对节点社会特征的提取、多层次社区群的形成进行了研究，并提出了新的基于社区的机会网络路由算法。实验结果表明，与已有的几种经典算法相比，我们提出的算法更有效。
【关键词】机会网络；社会特征；社区；路由算法
文章编号：ISSN1006—656X（2015）01-0073-02
引言
机会网络是一种不需要在源节点和目标节点之间存在完整路径，利用节点移动带来的相遇机会实现网络通信的、时延和分裂可容忍的自组织网络[1]。由于机会网络不要求网络的全连通，更适合实际的自组网需求，对于未来实现普适计算具有重大影响。
机会网络通常采用“存储-携带-转发”的模式工作。其中最简单的算法是直接传输（direct transmission）[2]。为了提高数据传输成功率和降低传输延迟，将传输的数据复制成多份在网络中多路径并行传输，如传染转发（epidemic forwarding）[3]。为了减少数据的拷贝数量，降低网络的开销，spray and wait算法及其改进算法binary spray and wait被提出[4]。为了选择最优的中继节点，通过历史信息进行预测，PRoPHET算法[5]和MaxProp算法[6]等由此提出。
近年来，大量低成本、具备短距离无线通信能力的智能设备的出现推动了机会网络应用的新发展。在这种应用场景中，移动设备被人使用或携带，具有交往社会性。给机会网络的路由算法带来一种新的方法：基于社会性的路由算法。
利用历史相遇数据（如：相遇次数、相遇时间、相遇频率等）来判断节点之间的关系，提出了一系列新的算法，如：基于社会中心的路由算法[7]，基于友谊的路由算法[8]，基于社区的路由算法[9]等。后来，研究发现：用节点的社会特征（如职业、国籍、性别、语言等）来判断节点之间的关系更好[10-13]。
本文主要研究了基于节点社会特征的路由算法。对节点社会特征的提取、基于社会特征的社区群的形成进行了研究，并提出了新的基于社区的路由算法。
一、 基于社会特征的社区划分
（一）社会特征
移动用户的社会特征能反映一定的社会用户在社会之间的关系。社会特征中有些相对更重要、更关键，可通过计算他们的香农熵来得到关键特征。
设网络中有个用户，每个用户有个社会特征，表示为，每个特征有个可能值，是特征值出现的概率。则特征的熵为，
其中，。社会特征的熵越大表示该特征越关键。
（二）基于社会特征的社区划分
社区，通常指相互有联系、具有某些共同特征的人群共同居住在一定的区域。研究表明：社区内节点的联系比社区之间成员节点的联系要密切得多。社区的划分是一个复杂的问题，许多学者提出了社区发现算法，经典的有：基于Laplace矩阵的谱平分法、基于贪婪算法原理的 Kernighan-Lin算法和Newman等人提出的GN算法，等等。这里，我们采用类似于Li Fan等人[10]提出的一种非常简单的基于阈值的层次划分法。
定义1. 为网络拓扑图，其中为网络中的节点集合，为定义在上的边集。节点，表示节点和之间的边，表示的大小，在此特殊定义为两个节点的相同社会特征的数目。而且
则节点的关系矩阵为（3）
基于节点社会特征的社区划分算法具体描述如下：
首先，根据定义计算出相应的关系矩阵。
然后，设置一个阈值（表示两节点的联系强度）。如果，则保留相应边，如果，则删除相应边。由此，我们得到对应t的社会特征图。采用不同值的t，就可以得到多层次的社区群。
最后，从特征图中得出社区群。
二、 基于社区的路由算法
（一）基于与目标节点同社区的路由算法
与Li Fan等人的想法相似，把与目标节点同社区的节点优先选为中继接点。描述如下：持有信息M的源节点S，想将M发送到目标节点D，中途遇到节点A。如果A就是D，或者A与D属于同一社区。转发M给A，否则不转发信息，直到遇到下一个节点，然后重复上述过程。具体算法如下：
已知：源节点S、目标节点D和相遇节点A
1： IFA是DORA与D同社区 THEN
2： 将信息M转发给A
3： ELSE
4： 不转发信息
5： END IF
（二） 基于树形结构的路由算法
上节中，我们得到了一个多层次结构的社区群，可利用树型结构表示。我们借鉴树的最短路径，让信息沿着最短路径传递，由此提出新的路由算法。
已知：源节点S、目标节点D和相遇节点A
1： IF A是D OR A与D同社区 THEN
2： 将信息M转发给A
3： ELSE
4： IFA属于S到D的路径中的社区 THEN
5： 将信息M转发给A
6： ELSE
7： 不转发信息
8： END IF
9： END IF
（三） 改进的基于树型结构的路由算法
在3.2节中，我们按照树型结构的最短路径传递信息，然而路径中的父节点是由所有子节点汇聚而成的大社区，如果不加以控制，选择父节点中的任意节点作为中继节点，将不是最优选择，导致路由性能不佳。在这节，我们改进算法，将所有子节点中最活跃的节点作为父节点。具体算法如下 ：
【关键词】机会网络；社会特征；社区；路由算法
文章编号：ISSN1006—656X（2015）01-0073-02
引言
机会网络是一种不需要在源节点和目标节点之间存在完整路径，利用节点移动带来的相遇机会实现网络通信的、时延和分裂可容忍的自组织网络[1]。由于机会网络不要求网络的全连通，更适合实际的自组网需求，对于未来实现普适计算具有重大影响。
机会网络通常采用“存储-携带-转发”的模式工作。其中最简单的算法是直接传输（direct transmission）[2]。为了提高数据传输成功率和降低传输延迟，将传输的数据复制成多份在网络中多路径并行传输，如传染转发（epidemic forwarding）[3]。为了减少数据的拷贝数量，降低网络的开销，spray and wait算法及其改进算法binary spray and wait被提出[4]。为了选择最优的中继节点，通过历史信息进行预测，PRoPHET算法[5]和MaxProp算法[6]等由此提出。
近年来，大量低成本、具备短距离无线通信能力的智能设备的出现推动了机会网络应用的新发展。在这种应用场景中，移动设备被人使用或携带，具有交往社会性。给机会网络的路由算法带来一种新的方法：基于社会性的路由算法。
利用历史相遇数据（如：相遇次数、相遇时间、相遇频率等）来判断节点之间的关系，提出了一系列新的算法，如：基于社会中心的路由算法[7]，基于友谊的路由算法[8]，基于社区的路由算法[9]等。后来，研究发现：用节点的社会特征（如职业、国籍、性别、语言等）来判断节点之间的关系更好[10-13]。
本文主要研究了基于节点社会特征的路由算法。对节点社会特征的提取、基于社会特征的社区群的形成进行了研究，并提出了新的基于社区的路由算法。
一、 基于社会特征的社区划分
（一）社会特征
移动用户的社会特征能反映一定的社会用户在社会之间的关系。社会特征中有些相对更重要、更关键，可通过计算他们的香农熵来得到关键特征。
设网络中有个用户，每个用户有个社会特征，表示为，每个特征有个可能值，是特征值出现的概率。则特征的熵为，
其中，。社会特征的熵越大表示该特征越关键。
（二）基于社会特征的社区划分
社区，通常指相互有联系、具有某些共同特征的人群共同居住在一定的区域。研究表明：社区内节点的联系比社区之间成员节点的联系要密切得多。社区的划分是一个复杂的问题，许多学者提出了社区发现算法，经典的有：基于Laplace矩阵的谱平分法、基于贪婪算法原理的 Kernighan-Lin算法和Newman等人提出的GN算法，等等。这里，我们采用类似于Li Fan等人[10]提出的一种非常简单的基于阈值的层次划分法。
定义1. 为网络拓扑图，其中为网络中的节点集合，为定义在上的边集。节点，表示节点和之间的边，表示的大小，在此特殊定义为两个节点的相同社会特征的数目。而且
则节点的关系矩阵为（3）
基于节点社会特征的社区划分算法具体描述如下：
首先，根据定义计算出相应的关系矩阵。
然后，设置一个阈值（表示两节点的联系强度）。如果，则保留相应边，如果，则删除相应边。由此，我们得到对应t的社会特征图。采用不同值的t，就可以得到多层次的社区群。
最后，从特征图中得出社区群。
二、 基于社区的路由算法
（一）基于与目标节点同社区的路由算法
与Li Fan等人的想法相似，把与目标节点同社区的节点优先选为中继接点。描述如下：持有信息M的源节点S，想将M发送到目标节点D，中途遇到节点A。如果A就是D，或者A与D属于同一社区。转发M给A，否则不转发信息，直到遇到下一个节点，然后重复上述过程。具体算法如下：
已知：源节点S、目标节点D和相遇节点A
1： IFA是DORA与D同社区 THEN
2： 将信息M转发给A
3： ELSE
4： 不转发信息
5： END IF
（二） 基于树形结构的路由算法
上节中，我们得到了一个多层次结构的社区群，可利用树型结构表示。我们借鉴树的最短路径，让信息沿着最短路径传递，由此提出新的路由算法。
已知：源节点S、目标节点D和相遇节点A
1： IF A是D OR A与D同社区 THEN
2： 将信息M转发给A
3： ELSE
4： IFA属于S到D的路径中的社区 THEN
5： 将信息M转发给A
6： ELSE
7： 不转发信息
8： END IF
9： END IF
（三） 改进的基于树型结构的路由算法
在3.2节中，我们按照树型结构的最短路径传递信息，然而路径中的父节点是由所有子节点汇聚而成的大社区，如果不加以控制，选择父节点中的任意节点作为中继节点，将不是最优选择，导致路由性能不佳。在这节，我们改进算法，将所有子节点中最活跃的节点作为父节点。具体算法如下 ：