论文部分内容阅读
摘要：针对移动机会网络数据转发效率低下的问题，提出了一种基于社区等量交换的路由算法。首先衡量节点对社区的贡献和从该社区获得的收益，采用等量交换的原则来决定节点的合作策略，然后采用资源分配策略对节点为社区分配的数据转发资源进行优化分配，接着进行转发数据的选择，最后对节点的贡献和收益进行更新。所提算法充分利用社区内外的节点，合理分配转发资源，从而达到提高数据转发性能的目的。仿真结果表明，与其他经典算法Direct，LABEL和ProPHET相比，该算法能够显著优化数据转发资源，提高数据转发效率，获得了更高的数据传递率、更低的转发延迟和负载。
关键词： 移动机会网络；社区；路由转发
中图分类号：TP393 文献标识码：A
文章编号：1009-3044（2019）10-0032-03
开放科学（资源服务）标识码（OSID）：
1 引言
移动机会网络（Mobile Opportunistic Network）利用移动设备在移动过程中偶然的相遇机会，采用“存储-携带-转发”的模式完成不依赖于基础设施的数据传输[1]。普遍存在的移动设备使得移动机会网络成为未来社会生活中移动应用的重要通讯模式。
近年来，社交因素对移动机会网络数据传输的影响逐渐被人们所关注，涌现了很多基于社交因素的路由算法。社区是指具有直接或间接社交联系的人组成的关系紧密的群体。社区中的成员之间，与社区外的成员相比，具有更频繁的接触和相遇机会[2]。节点间的社区特性在移动机会网络路由协议设计中具有积极的作用，能够在一定程度上提高数据传输效率。然而，在众多的移动节点中，社区外的节点的数量远远多于同社區的节点数量。而社区外的弱联系节点这一重大资源却常常被忽略。
本文提出了一种基于社区等量交换的数据路由算法（Community based Equal Exchanged Routing Algorithm， 简称CEERA），合理利用社区和弱联系节点这两种资源，考察节点与社区之间的贡献和收益平衡，采取等量交换的原则，优化转发资源，从而达到提高数据转发性能的目的。仿真结果表明，本文提出的算法能够有效地提高数据转发效率，降低网络负载。
2 算法的提出
2.1 系统模型
假设系统中有N个节点，按照一定的社交联系组成M个社区[C1，C2，...Ci，...CM]，其中i=1..M。同一社区中的节点具有较高的社交强度，从而具有更加频繁的相遇概率，常被用来指导路由转发。CEERA算法中，节点综合考虑与所有社区的社交强度和关联，从节点与社区之间的社交强度、未来相遇概率、节点对社区的贡献，以及节点从该社区的收益四个方面衡量，以实现优化分配数据转发资源，提高数据转发效率的目的。
2.2 衡量要素
节点与社区之间社交强度[ST（Ci）]。节点与社区之间的社交强度用来衡量节点与各个社区的接触程度。某节点与社区[Ci]的社交强度[ST（Ci）]采用单位时间T内遇到的该社区的节点数量来衡量，即公式（1）。
2.3 CEERA的工作流程
当两个节点如A和B进入彼此的通信范围，首先交换彼此的社区信息，更新相应的社区社交强度信息。然后，根据节点的贡献收益情况，采用等量交换的原则决定是否为对方节点转发数据（合作策略）。接着，根据数据转发策略决定转发列表，进行数据传输。如果决定不进行数据转发，转发列表为空。最后，根据本次的转发行为，更新各自的贡献收益情况（更新策略）。
3 算法的实现
3.1 合作策略的实现
移动机会网络数据传输的基础是节点之间的合作转发，即节点愿意为相遇节点转发数据。CEERA算法的合作策略采取基于社区等量交换的原则，依据节点对社区的贡献和节点从社区获得的收益两个指标来决定节点采取合作转发行为还是拒绝转发的行为。
节点一方面为各个社区转发数据做出贡献，另一方面也接受各个社区节点的转发帮助获得收益。对于节点来说，精简转发操作减少频繁替换的前提是自身得到最大的收益。假设单位时间T内，节点为各个社区做的贡献为[CON（Ci）]，则其在单位时间内总的贡献为[i=1MCON（Ci）]。假设节点从各个社区得到的收益为[BEN（Ci）]，则其在单位时间内总的贡献为[i=1MBEN（Ci）]。在节点有限的传输带宽资源下，节点要得到最大收益需要满足公式（3），即节点以最少的转发贡献获得最大的转发收益。这个问题可以转换为0-1背包问题，从而得到公式（4）。
由于每个节点都想获得最优的收益，因此，当[BEN（Ci）CON（Ci）]接近1时，可以得到接近于最优的收益，即节点对社区[Ci]的转发贡献与其从该社区得到的收益基本持平。由此可知，节点对社区采取等量交换的原则，可以最大限度地利用其转发资源，有效地减少替换操作，从而提高数据转发效率。
由于节点的贡献和收益不是同时发生的，两者之间往往存在一定的时间差，因此设立一个阈值[minSize，maxSize]来进行调节。从节点A的角度来说明具体的合作策略如下：
3.2 更新策略的实现
当数据转发成功后，要及时更新对应节点的贡献值和收益值。仍以节点A为例来说明更新策略。假设节点A为节点B转发了若干数据。则对于每个转发的数据，根据数据的源节点、目的节点与转发节点三者之间的关系，更新策略可以分为下面四种情况进行处理：
（1） A、B都是中间转发节点。这时节点A帮助节点B转发了若干数据，节点B得到了节点A的转发服务，则节点B从节点A所在社区[Ci]所得的收益值将会增加。
（2） 节点A是中间转发节点，而节点B是源节点（产生数据的节点）。这种情况的处理与（1）类似，节点A对B所在社区[Cj]的贡献将会增加，节点B从A所在社区[Ci]所得到的收益将会增加。 （3） 节点A是目的节点（数据的接收节点），而节点B是中间转发节点。这种情况下，节点A接收了所需要的数据，从节点B所在社区[Cj]中获益。因此，节点A从社区[Cj]得到的收益将会增加。而节点B因为帮助了节点A，其对社区[Ci]的贡献也将会相应增加。
（4） 节点A是目的节点，节点B是源节点。这种情况下，节点A和节点B互相为对方社区做了贡献，其贡献和收益相抵。节点A、B的贡献收益将保持不变，不做更新操作。
4 算法性能评价
4.1 仿真环境及设置
本文中使用仿真工具ONE Simulator[10]，实验数据采用INFOCOM2006实际数据集进行仿真实验。实验中，将CEERA与经典路由算法直接转发路由算法（Direct）、基于社区的转发路由算法LABEL以及ProPHET路由算法进行性能对比和分析。
4.2 仿真结果及分析
通过以上仿真比较可知，CEERA具有最高的数据交付率，较低的网络负载，最少的平均延迟，以及最多的平均跳数，获得了最优的数据转发效率。从而证明CEERA使得移动机会网络中的数据转发性能得到明显提升。
5 结语
本文中提出了基于社区等量交换的数据转发路由算法CEERA，以节点与社区之间的贡献和收益的等量交换为原则，优化分配节点的转发资源，合理分配节点的存储空间，以实现优化数据转发性能的目的。基于实际数据集INFOCOM2006的仿真实验表明，与传统经典算法相比，CEERA可以有效地提高移动机会网络中的数据转发效率。
参考文献：
[1] 马东华， 袁培燕， 赵东. 移动机会网络路由问题研究进展[J]. 软件学报， 2015， 26（3）：600-616.
[2] 姚玉坤， 杨及开， 刘文辉. 机会网络中基于社区的高效消息傳输算法[J]. 计算机应用， 2015，35（9）：2447-2452.
[3] Lindgren A， Doria A， Schelén O. Probabilistic routing in intermittently connected networks[J].Service Assurance with Partial and Intermittent Resources， ser. Lecture Notes in Computer Science，2004，3126：239-254.
[4] Ker?nen A， K?rkk?inen T， Ott J. Simulating Mobility and DTNs with the ONE[J]. Journal of Communications，2010，5（2）：92-105.
【通联编辑：王力】
关键词： 移动机会网络；社区；路由转发
中图分类号：TP393 文献标识码：A
文章编号：1009-3044（2019）10-0032-03
开放科学（资源服务）标识码（OSID）：
1 引言
移动机会网络（Mobile Opportunistic Network）利用移动设备在移动过程中偶然的相遇机会，采用“存储-携带-转发”的模式完成不依赖于基础设施的数据传输[1]。普遍存在的移动设备使得移动机会网络成为未来社会生活中移动应用的重要通讯模式。
近年来，社交因素对移动机会网络数据传输的影响逐渐被人们所关注，涌现了很多基于社交因素的路由算法。社区是指具有直接或间接社交联系的人组成的关系紧密的群体。社区中的成员之间，与社区外的成员相比，具有更频繁的接触和相遇机会[2]。节点间的社区特性在移动机会网络路由协议设计中具有积极的作用，能够在一定程度上提高数据传输效率。然而，在众多的移动节点中，社区外的节点的数量远远多于同社區的节点数量。而社区外的弱联系节点这一重大资源却常常被忽略。
本文提出了一种基于社区等量交换的数据路由算法（Community based Equal Exchanged Routing Algorithm， 简称CEERA），合理利用社区和弱联系节点这两种资源，考察节点与社区之间的贡献和收益平衡，采取等量交换的原则，优化转发资源，从而达到提高数据转发性能的目的。仿真结果表明，本文提出的算法能够有效地提高数据转发效率，降低网络负载。
2 算法的提出
2.1 系统模型
假设系统中有N个节点，按照一定的社交联系组成M个社区[C1，C2，...Ci，...CM]，其中i=1..M。同一社区中的节点具有较高的社交强度，从而具有更加频繁的相遇概率，常被用来指导路由转发。CEERA算法中，节点综合考虑与所有社区的社交强度和关联，从节点与社区之间的社交强度、未来相遇概率、节点对社区的贡献，以及节点从该社区的收益四个方面衡量，以实现优化分配数据转发资源，提高数据转发效率的目的。
2.2 衡量要素
节点与社区之间社交强度[ST（Ci）]。节点与社区之间的社交强度用来衡量节点与各个社区的接触程度。某节点与社区[Ci]的社交强度[ST（Ci）]采用单位时间T内遇到的该社区的节点数量来衡量，即公式（1）。
2.3 CEERA的工作流程
当两个节点如A和B进入彼此的通信范围，首先交换彼此的社区信息，更新相应的社区社交强度信息。然后，根据节点的贡献收益情况，采用等量交换的原则决定是否为对方节点转发数据（合作策略）。接着，根据数据转发策略决定转发列表，进行数据传输。如果决定不进行数据转发，转发列表为空。最后，根据本次的转发行为，更新各自的贡献收益情况（更新策略）。
3 算法的实现
3.1 合作策略的实现
移动机会网络数据传输的基础是节点之间的合作转发，即节点愿意为相遇节点转发数据。CEERA算法的合作策略采取基于社区等量交换的原则，依据节点对社区的贡献和节点从社区获得的收益两个指标来决定节点采取合作转发行为还是拒绝转发的行为。
节点一方面为各个社区转发数据做出贡献，另一方面也接受各个社区节点的转发帮助获得收益。对于节点来说，精简转发操作减少频繁替换的前提是自身得到最大的收益。假设单位时间T内，节点为各个社区做的贡献为[CON（Ci）]，则其在单位时间内总的贡献为[i=1MCON（Ci）]。假设节点从各个社区得到的收益为[BEN（Ci）]，则其在单位时间内总的贡献为[i=1MBEN（Ci）]。在节点有限的传输带宽资源下，节点要得到最大收益需要满足公式（3），即节点以最少的转发贡献获得最大的转发收益。这个问题可以转换为0-1背包问题，从而得到公式（4）。
由于每个节点都想获得最优的收益，因此，当[BEN（Ci）CON（Ci）]接近1时，可以得到接近于最优的收益，即节点对社区[Ci]的转发贡献与其从该社区得到的收益基本持平。由此可知，节点对社区采取等量交换的原则，可以最大限度地利用其转发资源，有效地减少替换操作，从而提高数据转发效率。
由于节点的贡献和收益不是同时发生的，两者之间往往存在一定的时间差，因此设立一个阈值[minSize，maxSize]来进行调节。从节点A的角度来说明具体的合作策略如下：
3.2 更新策略的实现
当数据转发成功后，要及时更新对应节点的贡献值和收益值。仍以节点A为例来说明更新策略。假设节点A为节点B转发了若干数据。则对于每个转发的数据，根据数据的源节点、目的节点与转发节点三者之间的关系，更新策略可以分为下面四种情况进行处理：
（1） A、B都是中间转发节点。这时节点A帮助节点B转发了若干数据，节点B得到了节点A的转发服务，则节点B从节点A所在社区[Ci]所得的收益值将会增加。
（2） 节点A是中间转发节点，而节点B是源节点（产生数据的节点）。这种情况的处理与（1）类似，节点A对B所在社区[Cj]的贡献将会增加，节点B从A所在社区[Ci]所得到的收益将会增加。 （3） 节点A是目的节点（数据的接收节点），而节点B是中间转发节点。这种情况下，节点A接收了所需要的数据，从节点B所在社区[Cj]中获益。因此，节点A从社区[Cj]得到的收益将会增加。而节点B因为帮助了节点A，其对社区[Ci]的贡献也将会相应增加。
（4） 节点A是目的节点，节点B是源节点。这种情况下，节点A和节点B互相为对方社区做了贡献，其贡献和收益相抵。节点A、B的贡献收益将保持不变，不做更新操作。
4 算法性能评价
4.1 仿真环境及设置
本文中使用仿真工具ONE Simulator[10]，实验数据采用INFOCOM2006实际数据集进行仿真实验。实验中，将CEERA与经典路由算法直接转发路由算法（Direct）、基于社区的转发路由算法LABEL以及ProPHET路由算法进行性能对比和分析。
4.2 仿真结果及分析
通过以上仿真比较可知，CEERA具有最高的数据交付率，较低的网络负载，最少的平均延迟，以及最多的平均跳数，获得了最优的数据转发效率。从而证明CEERA使得移动机会网络中的数据转发性能得到明显提升。
5 结语
本文中提出了基于社区等量交换的数据转发路由算法CEERA，以节点与社区之间的贡献和收益的等量交换为原则，优化分配节点的转发资源，合理分配节点的存储空间，以实现优化数据转发性能的目的。基于实际数据集INFOCOM2006的仿真实验表明，与传统经典算法相比，CEERA可以有效地提高移动机会网络中的数据转发效率。
参考文献：
[1] 马东华， 袁培燕， 赵东. 移动机会网络路由问题研究进展[J]. 软件学报， 2015， 26（3）：600-616.
[2] 姚玉坤， 杨及开， 刘文辉. 机会网络中基于社区的高效消息傳输算法[J]. 计算机应用， 2015，35（9）：2447-2452.
[3] Lindgren A， Doria A， Schelén O. Probabilistic routing in intermittently connected networks[J].Service Assurance with Partial and Intermittent Resources， ser. Lecture Notes in Computer Science，2004，3126：239-254.
[4] Ker?nen A， K?rkk?inen T， Ott J. Simulating Mobility and DTNs with the ONE[J]. Journal of Communications，2010，5（2）：92-105.
【通联编辑：王力】