文章编号：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节中，我们按照树型结构的最短路径传递信息，然而路径中的父节点是由所有子节点汇聚而成的大社区，如果不加以控制，选择父节点中的任意节点作为中继节点，将不是最优选择，导致路由性能不佳。在这节，我们改进算法，将所有子节点中最活跃的节点作为父节点。具体算法如下 ： 首先，构造多层次社区群的树型结构；
然后，基于历史相遇信息（如连接次数），得出各父节点的最活跃节点，并以此替代成父节点。
最后，按照算法2进行信息转发。
三、 实验评估
（一） 实验数据
本文采用Infocom 2006数据集来评估我们提出的算法。该数据集包含两个部分：由参与者携带的iMote设备之间的联系和参与者的社会特征。在我们的模拟中，因为18个参与者的社会特征的配置文件不齐全，我们只使用其中61个参与者的数据。在337418秒时间内参与者之间共有74981次连接。我们从原始数据中提取六个社会特征：国籍、语言、单位、职务、居住城市和居住国家。
（二） 实验分析
（1） 社会特征的影响
在第一组实验中，我们评估社会特征对节点之间连接的影响。其中，连接次数、间隔时间和连接时间都采用平均数。从图1中，我们可以看出：节点之间拥有相同社会特征数目越多，节点之间连接次数越多，连接时间越长，连接越频繁。
图1 社会特征对节点之间的连接影响
（2）路由算法的比较
在第二组实验中，我们比较几种路由算法的性能。从图2-5中，我们可以看出：tree-group算法整体表现最好，拥有最高的传输成功率，在传输延迟、跳数和拷贝数量也表现较好；same-group算法次之；而tree-group算法较差是因为部分中继节点选择不够好，Spray and Wait算法则是在Wait阶段白白浪费了时间。
图1 算法比较--传输成功率 图6 算法比较--传输延迟 图7 算法比较--跳数 图8算法比较--转发数量
四、 小结
在机会网络的某些应用中，移动设备由人使用或携带，利用其稳定、可结构化的社会特征可有效改善机会网络的路由性能。本文由社会特征形成的多层次社区群，提出了多种路由算法，并通过实验进行评估。结果表明，这些算法比原有算法效果好。
