论文部分内容阅读
如今，智能便携式移动设备在人类生活中正扮演着无法取代的角色。作为这些设备的持有者，用户本身具备社交属性且他们彼此间存在着社交关系。此外，新型无线网络技术(如5G技术)的迅速发展为移动用户之间的通信提供了强有力的支持。移动用户基于无线网络实现互联，并通过在线社交网络(Online Social Network，OSN)服务(如Facebook和微博)共享信息，构成了传统的移动社交网络(Mobile Social Network，MSN)。同时，随着短距离通信技术的发展(如蓝牙)，MSN用户能够在移动设备处于彼此通信范围内(即相遇)时进行消息转发从而实现数据共享(如多媒体文件)，进而降低网络带宽占用率并节省经济开销。此时，MSN被定义为一种由具有社交特征的移动节点组成的延迟容忍网络(Delay Tolerant Network，DTN)。
目前，MSN研究热点包括移动众包、影响最大化、社交推荐、隐私保护以及路由等。为了满足MSN用户日益增长的内容需求，数据共享需要通过移动设备之间的消息传播得以实现。这个过程必然需要路由来发挥作用，因此MSN路由研究十分关键。然而，MSN路由正面临一些严峻的挑战，比如难以获取精确的移动用户社交关系(如兴趣相似程度)、难以适应目标节点地址未知的情况(如在分布式环境中难以有效解析目标节点地址)以及消息交付延迟和交付率不理想等。由于现有的MSN范式很难解决上述问题，因此可以引入一种新的MSN系统来简化这些难题。
信息中心网络(Information Centric Networking，ICN)是一种面向内容的新型网络，它将用户的兴趣表示为内容名字，并基于这些名字进行路由。因此，路由方案可以在此基础上分析获取用户的兴趣偏好，进而准确描述用户的兴趣相似度。另外，由于ICN采用位置无关的命名方式，关注内容“是什么”而不是“在哪里”，因此其不依赖于节点地址寻找内容，从而能够适应目标节点地址未知的情况。同时，ICN支持内容的网内缓存，使兴趣请求不必依赖源内容提供者，而可以被缓存内容的邻居节点响应，从而提高消息的交付率并降低延迟。最后，由于ICN天然地支持内容移动性，因此为其与MSN的结合奠定了基础。综上所述，本文结合ICN面向内容的路由范式，提出了基于ICN的MSN路由机制，主要创新和贡献点总结如下:
(1)提出了基于ICN的MSN路由机制的基础模型，将路由过程分为兴趣包路由、数据包路由和内容的网内缓存三大模块。首先，按照ICN对内容的命名规则将用户的兴趣请求以内容名字表示，通过分析用户的历史请求内容名字得到他们的兴趣度量，并根据兴趣度量提出兴趣包路由机制，从而检索内容提供者。其次，通过分析节点之间的历史相遇信息得到它们的亲密度，基于亲密度提出数据包路由机制，从而使内容返回兴趣请求者。同时，区别于传统ICN中数据包沿着兴趣包的路径原路返回的模式，采用数据包重新路由的方式，以适应MSN的移动性本质。然后，基于亲密度和兴趣度量得出的友谊度量提出了网内缓存机制，从而保证缓存的内容能够以最大概率被返回兴趣请求者且被重新请求。再次，分析算法的时间复杂度并估计内容单位缓存时长的下界，从理论上证明所提机制的可行性和有效性。最后，通过实验结果表明提出的路由机制能够有效满足MSN用户对于内容的需求，同时相较于对比机制提高约21％的包交付率并降低约56％的交付延迟。
(2)鉴于社区发现技术能够有效改善MSN路由效率，将社区发现应用于基于ICN的MSN路由基础模型中，提出了基于ICN的社区感知型MSN路由机制。首先，根据提出的内容兴趣度量、直接兴趣朋友和间接兴趣朋友的概念进行兴趣社区划分，基于兴趣社区划分结果提出了兴趣包路由机制。其次，根据提出的相遇密度、强连接朋友和弱连接朋友的概念进行社交社区划分，基于社交社区划分结果提出了数据包路由机制。然后，基于兴趣社区和社交社区提出了内容的网内缓存机制，使内容缓存空间得到优化管理。再次，从理论上证明所提出的网内缓存机制能够实现最优化的内容缓存，令节点能够以最大概率为用户获取请求内容。最后，通过实验结果表明提出的路由机制能够有效地响应用户内容请求，同时相较于基于单一社区结构的对比机制提高约38％的包交付率并降低约41％的交付延迟。
(3)针对MSN路由中消息陷入deadend(“死胡同”)的问题，提出了基于ICN的deadend避免型MSN路由机制。首先，提出一种基于回溯的deadend避免策略，从而解决由贪婪式转发规则(即将消息转发给社交地位更高的节点)导致的消息转发陷入局部最优的问题。其次，分别根据提出的兴趣距离度量和相遇规律，结合deadend避免策略，提出了deadend避免型兴趣包路由机制和数据包路由机制，从而避免兴趣包和数据包陷入deadend。再次，基于社区兴趣偏好提出了网内缓存机制，最大程度满足社区成员的内容请求。最后，通过实验结果表明deadend避免策略能够有效改善基于ICN的MSN路由机制的性能，同时相较于没有考虑deadend的对比机制提高约51％的包交付率并降低约46％的交付延迟。
(4)面向MSN中一种重要的应用场景——车载社交网络，设计了一种基于ICN的轨道交通型车载社交网络路由机制，以满足乘坐轨道交通的乘客对于内容的需求。首先，基于真实人类社交规律，提出了一种社交型backlog(积压仓)管理机制，对存储在车辆节点backlog中的消息(包括兴趣包和数据包)进行有效管理并决定在获得转发机会时消息的转发次序。其次，考虑到节点对于消息不同的处理次序，提出了双向权衡的转发节点选择机制，使消息能够获得转发节点的优先处理进而实现快速交付。再次，结合节点之间的链路生存时间，提出了兴趣包路由机制和数据包路由机制，从而适应车辆节点移动速度较快的特点，增加数据传输成功的概率。最后，通过实验结果表明提出的路由机制能够有效满足轨道交通乘客对于内容的需求，同时相较于经典的车载社交网络路由机制提高约57％的包交付率并降低约13％的交付延迟。
本文基于ICN架构，利用社区划分技术以及贡献值、亲密度和兴趣相似度等社交度量，总共提出了四种不同的MSN路由机制。此外，分别在一些真实数据集以及合成网络拓扑上，从包交付率、平均跳数、平均延迟和网络平均开销等方面进行性能评价。研究成果具有较强的理论价值和实际意义，能够为设计有价值的MSN路由机制提供一种新思路。
目前，MSN研究热点包括移动众包、影响最大化、社交推荐、隐私保护以及路由等。为了满足MSN用户日益增长的内容需求，数据共享需要通过移动设备之间的消息传播得以实现。这个过程必然需要路由来发挥作用，因此MSN路由研究十分关键。然而，MSN路由正面临一些严峻的挑战，比如难以获取精确的移动用户社交关系(如兴趣相似程度)、难以适应目标节点地址未知的情况(如在分布式环境中难以有效解析目标节点地址)以及消息交付延迟和交付率不理想等。由于现有的MSN范式很难解决上述问题，因此可以引入一种新的MSN系统来简化这些难题。
信息中心网络(Information Centric Networking，ICN)是一种面向内容的新型网络，它将用户的兴趣表示为内容名字，并基于这些名字进行路由。因此，路由方案可以在此基础上分析获取用户的兴趣偏好，进而准确描述用户的兴趣相似度。另外，由于ICN采用位置无关的命名方式，关注内容“是什么”而不是“在哪里”，因此其不依赖于节点地址寻找内容，从而能够适应目标节点地址未知的情况。同时，ICN支持内容的网内缓存，使兴趣请求不必依赖源内容提供者，而可以被缓存内容的邻居节点响应，从而提高消息的交付率并降低延迟。最后，由于ICN天然地支持内容移动性，因此为其与MSN的结合奠定了基础。综上所述，本文结合ICN面向内容的路由范式，提出了基于ICN的MSN路由机制，主要创新和贡献点总结如下:
(1)提出了基于ICN的MSN路由机制的基础模型，将路由过程分为兴趣包路由、数据包路由和内容的网内缓存三大模块。首先，按照ICN对内容的命名规则将用户的兴趣请求以内容名字表示，通过分析用户的历史请求内容名字得到他们的兴趣度量，并根据兴趣度量提出兴趣包路由机制，从而检索内容提供者。其次，通过分析节点之间的历史相遇信息得到它们的亲密度，基于亲密度提出数据包路由机制，从而使内容返回兴趣请求者。同时，区别于传统ICN中数据包沿着兴趣包的路径原路返回的模式，采用数据包重新路由的方式，以适应MSN的移动性本质。然后，基于亲密度和兴趣度量得出的友谊度量提出了网内缓存机制，从而保证缓存的内容能够以最大概率被返回兴趣请求者且被重新请求。再次，分析算法的时间复杂度并估计内容单位缓存时长的下界，从理论上证明所提机制的可行性和有效性。最后，通过实验结果表明提出的路由机制能够有效满足MSN用户对于内容的需求，同时相较于对比机制提高约21％的包交付率并降低约56％的交付延迟。
(2)鉴于社区发现技术能够有效改善MSN路由效率，将社区发现应用于基于ICN的MSN路由基础模型中，提出了基于ICN的社区感知型MSN路由机制。首先，根据提出的内容兴趣度量、直接兴趣朋友和间接兴趣朋友的概念进行兴趣社区划分，基于兴趣社区划分结果提出了兴趣包路由机制。其次，根据提出的相遇密度、强连接朋友和弱连接朋友的概念进行社交社区划分，基于社交社区划分结果提出了数据包路由机制。然后，基于兴趣社区和社交社区提出了内容的网内缓存机制，使内容缓存空间得到优化管理。再次，从理论上证明所提出的网内缓存机制能够实现最优化的内容缓存，令节点能够以最大概率为用户获取请求内容。最后，通过实验结果表明提出的路由机制能够有效地响应用户内容请求，同时相较于基于单一社区结构的对比机制提高约38％的包交付率并降低约41％的交付延迟。
(3)针对MSN路由中消息陷入deadend(“死胡同”)的问题，提出了基于ICN的deadend避免型MSN路由机制。首先，提出一种基于回溯的deadend避免策略，从而解决由贪婪式转发规则(即将消息转发给社交地位更高的节点)导致的消息转发陷入局部最优的问题。其次，分别根据提出的兴趣距离度量和相遇规律，结合deadend避免策略，提出了deadend避免型兴趣包路由机制和数据包路由机制，从而避免兴趣包和数据包陷入deadend。再次，基于社区兴趣偏好提出了网内缓存机制，最大程度满足社区成员的内容请求。最后，通过实验结果表明deadend避免策略能够有效改善基于ICN的MSN路由机制的性能，同时相较于没有考虑deadend的对比机制提高约51％的包交付率并降低约46％的交付延迟。
(4)面向MSN中一种重要的应用场景——车载社交网络，设计了一种基于ICN的轨道交通型车载社交网络路由机制，以满足乘坐轨道交通的乘客对于内容的需求。首先，基于真实人类社交规律，提出了一种社交型backlog(积压仓)管理机制，对存储在车辆节点backlog中的消息(包括兴趣包和数据包)进行有效管理并决定在获得转发机会时消息的转发次序。其次，考虑到节点对于消息不同的处理次序，提出了双向权衡的转发节点选择机制，使消息能够获得转发节点的优先处理进而实现快速交付。再次，结合节点之间的链路生存时间，提出了兴趣包路由机制和数据包路由机制，从而适应车辆节点移动速度较快的特点，增加数据传输成功的概率。最后，通过实验结果表明提出的路由机制能够有效满足轨道交通乘客对于内容的需求，同时相较于经典的车载社交网络路由机制提高约57％的包交付率并降低约13％的交付延迟。
本文基于ICN架构，利用社区划分技术以及贡献值、亲密度和兴趣相似度等社交度量，总共提出了四种不同的MSN路由机制。此外，分别在一些真实数据集以及合成网络拓扑上，从包交付率、平均跳数、平均延迟和网络平均开销等方面进行性能评价。研究成果具有较强的理论价值和实际意义，能够为设计有价值的MSN路由机制提供一种新思路。