第 1 章 绪论
1.1 便携交换网络
传统网络要求端到端的物理链接，一旦失去如光纤等物理传输介质的保障，数据传输也就不复存在了。近年来伴随着许多具备短距离无线通讯能力的智能设备的出现，无线组网技术得到快速发展，由于这些网络最大的特点就是端到端无需物理链接，因此具有即时通信、部署简单、组网成本低、自组织能力强等特点，无线自组织网络也因此被广泛运用于山区、沙漠等复杂环境下[1]。比如在野生动物网络中通过放置在野生动物身上的传感器对野生动物群落进行监控，收集动物的迁移和活动数据[2]。但是很多实际应用场合中节点并不是静止不动的，因此节点本身的运动和节点所处的环境的不同都会对网络中的连通度产生影响；同时传统的无线多跳网络如 Ad Hoc 网络[3]在进行消息投递时都要求源节点和目的节点间至少存在一条完整的通信链路，因此没有针对链路中断情况的处理方案，这就造成了利用传统的无线自组织网络对节点在时刻运动的情况下进行组网时会出现网络性能下降，网络丢包严重，甚至是链路无法联通的情况[4]。同时由于时传统无线自组织网络所用到的节点需要即时更换电源来保证正常工作，这在一定程度上增大了网络维护的成本，并限制了网络节点的活动范围和活动时间，使得应用的场景受到限制。
传统网络要求端到端的物理链接，一旦失去如光纤等物理传输介质的保障，数据传输也就不复存在了。近年来伴随着许多具备短距离无线通讯能力的智能设备的出现，无线组网技术得到快速发展，由于这些网络最大的特点就是端到端无需物理链接，因此具有即时通信、部署简单、组网成本低、自组织能力强等特点，无线自组织网络也因此被广泛运用于山区、沙漠等复杂环境下[1]。比如在野生动物网络中通过放置在野生动物身上的传感器对野生动物群落进行监控，收集动物的迁移和活动数据[2]。但是很多实际应用场合中节点并不是静止不动的，因此节点本身的运动和节点所处的环境的不同都会对网络中的连通度产生影响；同时传统的无线多跳网络如 Ad Hoc 网络[3]在进行消息投递时都要求源节点和目的节点间至少存在一条完整的通信链路，因此没有针对链路中断情况的处理方案，这就造成了利用传统的无线自组织网络对节点在时刻运动的情况下进行组网时会出现网络性能下降，网络丢包严重，甚至是链路无法联通的情况[4]。同时由于时传统无线自组织网络所用到的节点需要即时更换电源来保证正常工作，这在一定程度上增大了网络维护的成本，并限制了网络节点的活动范围和活动时间，使得应用的场景受到限制。
另一方面由于手机等便携智能设备的使用数量爆炸性的增长，这些智能设备本身支持通过蓝牙或者 Wi-Fi 进行短距离通信，并且使用这些智能设备进行组网和消息传输时不需要额外的硬件支持，并且大多数情况下设备的使用者也会及时的对其进行充电从而保证其能正常工作，这使得人们将研究的目光转移到如何使用这些便携设备进行数据交换和传输上。剑桥大学和 Intel 研究院在2005 年提出一种利用节点携带者的移动性和局部连通性进行通信的网络-便携交换网络（PSN，pocket switched network）。
1.2 相似性指标
在众多科研领域中，如何分析系统中组成元素之间的相似性是许多重要的基础研究任务之一，也是很多研究任务的前提。例如在生物学领域的神经网络和蛋白质网络中，通过比较序列对之间是否存在相同的碱基，以及氨基酸占整个序列的比例和侧链基团的大小、电荷性、亲疏水性等方面判断两个基因序列之间是否存在相似性从而分析基因序列[9]。同样在信息检索领域，通过分析两个文档的关键字个数，主题的相关程度以及文档之间共同引用的个数等信息检索出相同的文档，一个好的相似性指标对于快速准确的检索文档起到的至关重要的作用[10]。相似性分析在实际应用中同样占据着非常重要的地位，例如社交网络和社交网络中的用户推荐系统[11]，正所谓物以类聚人以群分，Facebook 等社交网络根据比较两个用户在选择好友，兴趣爱好，和共同好友的关系等方面的相似程度，从而将和该用户相似但还未相互添加好友关系的人推荐给该用户；又比如在电子商务网站的推荐系统[12]，电子商务网站会通过分析用户的购买过的商品类型以及用户的近期搜索过得商品记录得出用户最需要的商品种类，并将与之相同和相似的商品推荐给该用户。
在众多科研领域中，如何分析系统中组成元素之间的相似性是许多重要的基础研究任务之一，也是很多研究任务的前提。例如在生物学领域的神经网络和蛋白质网络中，通过比较序列对之间是否存在相同的碱基，以及氨基酸占整个序列的比例和侧链基团的大小、电荷性、亲疏水性等方面判断两个基因序列之间是否存在相似性从而分析基因序列[9]。同样在信息检索领域，通过分析两个文档的关键字个数，主题的相关程度以及文档之间共同引用的个数等信息检索出相同的文档，一个好的相似性指标对于快速准确的检索文档起到的至关重要的作用[10]。相似性分析在实际应用中同样占据着非常重要的地位，例如社交网络和社交网络中的用户推荐系统[11]，正所谓物以类聚人以群分，Facebook 等社交网络根据比较两个用户在选择好友，兴趣爱好，和共同好友的关系等方面的相似程度，从而将和该用户相似但还未相互添加好友关系的人推荐给该用户；又比如在电子商务网站的推荐系统[12]，电子商务网站会通过分析用户的购买过的商品类型以及用户的近期搜索过得商品记录得出用户最需要的商品种类，并将与之相同和相似的商品推荐给该用户。
针对于不同的场景和不同的实际应用而言，相似性的计算方式不近相同，即是知道适用于什么样的信息进行相似性评估，如果没有一个合适的相似性指标将已有的信息进行量化也无法很好的得到样本之间的真实相似性。例如在信息检索时比较两篇文章之间的相似性最直接的方式是比较两篇文章之间相同关键词的数量，因为当人们对特定的文章主题总会用到特定的描述词汇。并且一些关键词会在两篇文章中反复出现，而这些反复出现的关键词的数量可以表示为文章本身的特征向量。同一类文章的特征向量在最能表示该文章特点的几个维度上的值会很接近；反之对于不同一类的文章而言，由于用词的不同，他们的特征向量中，值较大的维度应该没有什么交集。因此在进行文章相似性比较时会使用比较它们之间特征向量夹角的余弦值得出两篇文章是否相似。
第 2 章 相关研究
2.1 社交网络中的相似性指标研究
2.1.1 基于网络结构的相似性指标研究
最早基于网络结构相似度的链路预测大多基于静态拓扑，根据对网络结构的分析角度不同可以将基于网络结构信息的相似性指标分为基于局部信息的相似性指标、基于路径的相似性指标、基于随机游走的相似性指标。
基于局部信息的相似性指标是指通过节点局部信息，如节点的邻居信息、节点的度等计算得到的相似性指标[13]。最常用到的局部信息是节点之间的共同邻居节点，在 CN 相似性指标中节点对间共同邻居越多，这两个节点相似性越高。因此基于局部信息的相似性指标一般计算复杂度较低，但相比于全局指标而言，其预测效果较差。而基于路径的相似性指标是指通过节点间路径进行节点相似性评估，并且在指标计算时会考虑节点间存在的所有路径，从而得到节点相似性。主流的基于路径的相似性指标有 3 个，分别是局部路径
..........................
2.2 机会网络的相似性指标研究
机会网络作为一个网络拓扑在不断变化的动态网络，仅靠社交网络中常用的相似性指标，无法准确地描述出节点之间的相似性。近年来的研究学者根据机会网络的特点对相似性指标的建立做了理论模型。例如，在文献[34]就指出传统的链路预测方法没有很好的考虑机会网络中拓扑会动态变化的问题。文中提出一种基于节点在网络中的介质中心性的相似性指标 B-CN。 B-CN 在 CN 相似性指标的基础行，通过结合介质中心性与网络拓扑会根据时间变化的特性，相似性指标的定义如下：
.........................
第 3 章 PSN 网络节点行为模式 ........................... 16
3.1 PSN 网络节点行为模式 ............................... 16
3.2 PSN 网络中节点社交行为 ........................ 18
第 4 章 基于节点行为模式的相似性指标 .......................... 26
4.1 节点社交行为的相似性 ............................... 26
4.2 节点移动行为的相似性 ........................... 28
第 5 章 实验设计及结果分析 ..................................... 32
5.1 实验数据集 ...................... 32
5.2 评价指标 ................................... 33
第 5 章 实验设计及结果分析
本章最主要的工作就是对本文提出的基于节点行为模式的相似性指标进行有效性验证，主要体现在如下几个方面：实验数据集的预处理、节点社交行为相似性指标和节点移动行为相似性指标有效性验证和加权参数的确定
5.1 实验数据集
PSN 网络的节点运动往往包含着较强的社会性和一定的随机性，而 PSN 网络的这些特性往往无法很好的反应在仿真平台模拟出来的数据中。因此，为了更为真实的验证节点行为模式和相似性之间的关系，本文将使用真实数据集作为研究对象：MIT Reality 和 Dartmouth/campus。这两个数据集中不仅含有网络节点之间的连接情况，还有节点所在的区域位置变化情况，因此对于本文提出的相似性指标的研究具有较强的针对性。
表 5-1 列出了实验数据集的参考信息（关于 MIT Reality和 Dartmouth/campus数据集的详细内容请参见 CRAWDAD[60][61]）。
.........................
第 6 章 总结与展望
6.1 全文总结
本课题针对便携移动网络中节点具有社会性，节点的携带者的移动具有规律等特点，提出 PSN 网络中节点社交行为的相似性以及节点移动行为的相似性，并通过对社交相似性以及移动相似性进行线性加权的方式得出适用于 PSN 网络的基于节点行为模式的相似性指标。首先提出关系权重的概念，从节点间建立链接的次数和每次链接持续的时长对网络中节点间的关系进行计算，并进一步通过与传统相似性指标进行结合从而得到节点社交行为的相似性指标；接着，通过分析节点访问区域的规律，得出节点移动行为的相似性，并讨论了带入相似性计算时节点移动区域的个数以及实验时长对节点移动行为的影响，从而得出最合适的用于计算节点移动行为相似性的相似性区域个数；最终通过实验的方式对节点移动行为的相似性以及节点社交行为的相似性之间的加权系数进行讨论，最终通过比较与传统相似性指标在真实数据集中的预测精度从而验证本文提出的相似性指标的适用性，为 PSN 网络中的链路预测以及消息转发提供了参考。
参考文献（略）