复杂系统研究组10年9月12日学术报告会

2010-09-10 09:51:35 作者:benchong 来源: 浏览次数:0

时间:2010-9-12(星期天)晚上7:30-10:00
地点:理化大楼 17-009教室

报告人:闫小勇(进修学者),叶凡(博士后)

报告题目与摘要:

闫小勇: 人类日常出行的空间有界性
理解人类的出行行为对于规划交通设施、设计无线网络、防范疾病传播等具有重要意义。构建了一个模拟人类个体日常出行行为的模型,来解释从手机通讯记录轨迹中观察到的人类空间运动范围的有界性特征。首先,我假设个体每天的最大出行距离受限于他每天可用于出行的时间。根据这一假设,我计算出个体日常出行的范围处于以家和工作地为焦点的一个椭圆之内。进一步地,构建了一个在此有限范围之内的随机游走模型,用于分析个体出行轨迹的回转半径随时间变化的规律。仿真结果显示回转半径会很快趋近于一个稳定值,该值的大小与个体的家到工作地之间的距离存在显著的正相关关系。

叶凡:移动对等网络中基于利益的缓存放置与更新
移动点对点(MP2P)网络提供了分布式,自组织,可扩展性的特性,但是也有高延迟和由移动性带来的连接中断的问题。本文研究了在这种网络中利用缓存/复本放置和优化的高速缓存更新来减少请求响应时间的策略。已有相当多的工作提出了不同的副本放置算法来解决数据放置问题,这些问题被证明是NP难的。因此,许多启发式算法被提出以解决问题。另一方面,移动环境下合作缓存更新算法被广泛地加以研究,但是很少有文章能结合两者。本章的研究提出了一个高效且低成本的缓存放置以及缓存更新策略,它们可以很容易地以分布式的方式实现。最后,模拟试验证明了这种缓存放置策略和更新算法的有效性。
近来无线计算和无线通信技术得到了长足的发展,移动对等网络是由配备可互联的无线网卡的设备组建的分布式网络。其组成设备可以是笔记本电脑甚至是传感器网络。从低层上看,移动对等网络也就是支持多跳路由的ad hoc网络。每个节点可以支持数据包的转发,数据包的缓存等功能。本章的研究重点不是ad hoc网络的MAC层,本文的工作在于研究如何实现在应用层实现有效的数据存取和数据分享。更确切地说,研究的内容为缓存的优化放置和应付动态请求的缓存更新策略。我们还同时展示了这两种策略之间的联系,以及它们之间的相互促进作用。
研究移动对等网络上的缓存放置基于以下两个原因:第一:移动对等网络是支持多跳的在近邻节点之间分享数据的分布式网络,通过节点传输距离外的节点获取数据要使用多跳的路由算法,在中间节点上缓存数据能极大地减少传输代价。第二:移动对等网络在信道带宽和电池能量方面有很大的限制,缓存能减少通信代价,节约稀缺的带宽和电池能量资源。因此本章致力于研究无线对等网络上的合作缓存技术。
考虑一个文件共享的应用实例,假设有多个可用的文件数据(而且过大的可以被分段)被多个移动节点来共享,每个节点只能缓存一部分的数据。每个节点可以从网络中所有节点的缓存空间中获得所请求的数据。从而在哪个节点缓存何种数据就成为了关系到数据存取效率的一个很有挑战性的问题。在移动对等网络上,每个节点既可以是一个客户端,也可以是一个服务端,当作为一个客户端时,移动节点需要在限定的时间内获取所请求的数据。当作为一个服务端时,移动节点必须小心地选择数据缓存到自己有限的缓存空间里来最小化整体的存取代价。相对于移动代理基站上的缓存,这些基站静态地通过光纤或铜线连接在一起且有足够的空间,合作的移动对等网络中的设备只能暂时形成一个自组织的网络,合作分享有限的数据。移动节点上的缓存数据的启发式选择能使得在每个节点缓存适的数据,对系统效率的提高影响更大。
本文给出了一种适用于移动对等网络的高效且低成本的高速缓存放置和更新算法,它们可以很容易地以分布式的方式实施。
本文的组织方式如下:在第二节,我们回顾了有关数据复制和缓存放置的相关工作。第三节用正规化的数学模型来分析缓存放置的问题。在第四节,一系列的缓存放置算法被引入,兼顾了效率性和网络本身特点的要求。第五节讨论了缓存数据放置与缓存更新算法之间的关系以及联合放置与更新一起使用的必要性。第六节用模拟实验评估了所提出的缓存放置和更新策略的有效性。第七节对本文的内容作出了总结。

相关文章

[收藏] [打印] [关闭] [返回顶部]

最新文章