A Distributed Protocol to Serve Dynamic Groups for Peer-to-Peer Streaming

Peer-to-peer (P2P) streaming has been widely deployed over the Internet. A streaming system usually has multiple channels, and peers may form multiple groups for content distribution. In this paper, we propose a distributed overlay framework (called SMesh) for dynamic groups where users may frequently hop from one group to another while the total pool of users remain stable. SMesh first builds a relatively stable mesh consisting of all hosts for control messaging. The mesh supports dynamic host joining and leaving, and will guide the construction of delivery trees. Using the Delaunay Triangulation (DT) protocol as an example, we show how to construct an efficient mesh with low maintenance cost. We further study various tree construction mechanisms based on the mesh, including embedded, bypass, and intermediate trees. Through simulations on Internet-like topologies, we show that SMesh achieves low delay and low link stress.     

Sharing attractions on the Net with VPark

We present a networked virtual environment (NVE) system and an attraction building system based on Windows NT that enables users to introduce their own scenario-based applications into a shared virtual environment. Our goal was to develop and integrate several modules into a system capable of animating realistic virtual humans in a real-time performance. This includes modeling and representing virtual humans with high realism and simulating human face and body movements in real time. Realism becomes quite important in NVEs, where the communication among participants is crucial for their sense of presence     

基于Qi算法的Delaunay三角网逐点插入法

Delaunay三角网在很多领域都有着广泛的应用,快速高效地生成Delaunay三角网十分重要。逐点插入法是构建Delaunay三角网中使用最广泛的方法之一。本文深入研究了使用逐点插入法构建不带约束条件Delaunay三角网的过程。在使用该方法生成Delaunay三角网中建立结点拓扑关系这一影响构网效率的关键步骤中引入了Qi算法,简化了该方法生成Delaunay三角网的复杂度。然后在向Delaunay三角网内插入约束边的过程中,再次引入Qi算法,从而提高了构网的效率。为了验证上述模型,我们在Microsoft Visual Studio 2005开发环境下,以C#为开发工具,采用底层开发模式实现了改进的逐点插入法,实验证明引入Qi算法能够提高逐点插入法Delaunay三角网构建及插入约束边的效率。     

A Weighted Delaunay Triangulation Framework for Merging Triangulations in a Connectivity Oblivious Fashion

Simplicial meshes are useful as discrete approximations of continuous spaces in numerical simulations. In some applications, however, meshes need to be modified over time. Mesh update operations are often expensive and brittle, making the simulations unstable. In this paper we propose a framework for updating simplicial meshes that undergo geometric and topological changes. Instead of explicitly maintaining connectivity information, we keep a collection of weights associated with mesh vertices, using a Weighted Delaunay Triangulation (WDT). These weights implicitly define mesh connectivity and allow direct merging of triangulations. We propose two formulations for computing the weights, and two techniques for merging triangulations, and finally illustrate our results with examples in two and three dimensions.     

Keyframe-based video summarization using Delaunay clustering

Recent advances in technology have made tremendous amounts of multimedia information available to the general population. An efficient way of dealing with this new development is to develop browsing tools that distill multimedia data as information oriented summaries. Such an approach will not only suit resource poor environments such as wireless and mobile, but also enhance browsing on the wired side for applications like digital libraries and repositories. Automatic summarization and indexing techniques will give users an opportunity to browse and select multimedia document of their choice for complete viewing later. In this paper, we present a technique by which we can automatically gather the frames of interest in a video for purposes of summarization. Our proposed technique is based on using Delaunay Triangulation for clustering the frames in videos. We represent the frame contents as multi-dimensional point data and use Delaunay Triangulation for clustering them. We propose a novel video summarization technique by using Delaunay clusters that generates good quality summaries with fewer frames and less redundancy when compared to other schemes. In contrast to many of the other clustering techniques, the Delaunay clustering algorithm is fully automatic with no user specified parameters and is well suited for batch processing. We demonstrate these and other desirable properties of the proposed algorithm by testing it on a collection of videos from Open Video Project. We provide a meaningful comparison between results of the proposed summarization technique with Open Video storyboard and K-means clustering. We evaluate the results in terms of metrics that measure the content representational value of the proposed technique.     

基于符号体积值的Delaunay逐点插入法

传统Delaunay逐点插入法需在全局范围内进行点定位操作,或涉及到面的法向量计算,效率较低。提出一种基于符号体积值的Delaunay逐点插入法。设计简要的数据结构,利用四面体带符号体积值的符号,判断新插入点所在方位,逐步搜索将该新插入点包含在其内部的中心四面体,完成局部范围的点定位;进一步利用体积值符号进行Delaunay空洞可视面测试;对多点共面或共球的退化情况,将点坐标加以细微扰动,提高算法健壮性。实验结果表明,基于符号体积值的Delaunay逐点插入法的点定位操作效率较高,计算量相对减少。     

基于移动中央服务器的P2P系统

本文在分析混杂P2P系统的基础上提出并设计了一种基于移动中央服务器的P2P系统.它是对混杂P2P系统的一种改进,可以有效地解决混杂P2P系统中的单点失效及维护代价过高的问题.     

Distributed patching for mobile wireless sensor networks

Mobile wireless sensor networks (MWSNs), the continuous movement of sensor nodes, may cause complete disconnection of the network or at best a part of it. The design of such networks should guarantee that all sensor nodes at all times have a path to the sink node(s). Prolonging the lifetimes of the MWSNs is a crucial design issue but should not be at the expense of other essential functions such as connectivity. In this paper, we propose an energy efficient distributed framework for connectivity maintenance of MWSNs. In the proposed framework, sensor nodes of the MWSNs schedule and control their radio frequency (RF) modules based on dynamic coordinated reconstruction mechanism, some senor nodes may lose their connectivity with the network due to mobility, depletion of energy and/or incurred faults. Two protocols are developed to patch up the disconnection of the MWSNs. The first protocol reestablishes the network connection consuming far less energy than state-of-the-art alternatives. However, it is capable of reestablishing the connection when no more than 20% of the MWSN backbone nodes lose connection concurrently. The second protocol extends this limit to operate when up to 35% of the MWSN backbone nodes lose connection simultaneously.     

P2P consistency support for large-scale interactive applications

Peer-to-Peer (P2P) systems have been widely used by networked interactive applications to relieve the drawback and reduce the reliance on well-provisioned servers. A core challenge is to provide consistency maintenance for a massive number of users in a P2P manner. This requires propagating updates on time by only using the uplink bandwidth from individual users instead of relying on dedicated servers. In this paper, we present a P2P system called PPAct to provide consistency maintenance for large-scale fast-interactive applications. We use massive multi-player online games as example applications to illustrate PPAct. The design can be directly applied to other interactive applications. We adopt the Area-of-Interest (AOI) filtering method, which is proposed in prior works [1], [2], to reduce bandwidth consumption of update delivery. We solve the AOI’s critical problem of bandwidth shortage in hot regions by dynamically balancing the workload of each region in a distributed way. We separate the roles of view discovery from consistency maintenance by assigning players as “region hosts” and “object holders.” A region host is responsible for tracking objects and players within a region, and an object holder is responsible for sending updates about an object to interested players. Lookup queries for view discovery are processed by region hosts, while consistency maintenance of objects is taken by object holders. Separating the roles not only alleviates the workload overflow in hot regions, but also speeds up view discovery and update delivery. Another key idea is that peers contribute spare bandwidth in a fully distributed way to forwarding updates about objects of interest. Thus popular, high-demand objects will have more peers forward updates. We also present how to select capable and reliable players for region hosts and object holders.A P2P network simulator is developed to evaluate PPAct on two major types of online games: role-playing games (RPGs) and first-person shooter (FPS) games. The results demonstrate that PPAct successfully supports 10,000 players in RPGs and 1500 players in FPS games. PPAct outperforms SimMud [2] in RPGs and Donnybrook [3] in FPS games by 40% and 30% higher successful update rates respectively.     

一种带岛屿约束数据域的三角网剖分算法研究

文中对多边形内部三角剖分算法及具有属性的带岛屿的约束数据域的D－三角剖分算法进行了研究，提出了一种适用于多边形内部的基于“最小内角优先原则“D－三角剖分算法及适用于多边形内，外部构网通用三角剖三角剖分算法，算法充分考虑到了构网数据域中存在多种不同属性块，并成功将算法应用于工程项目之中。     

针对P2P可部署性的国内网络状况调查

针对目前国内缺少公开可得的宽带用户的网络接入状况大规模统计数据的问题,实现一次针对国内居民网络接入状况的大规模普查,收集超过1 700份有效数据,通过分析,得到在P2P网络中有95.7%的概率可以在Peer之间建立可靠连接的结论,并为国内部署P2P应用提供建议,包括重视NAT路由器穿透问题以及部署带宽补充服务器等。     

On incentivizing upload capacity in P2P-VoD systems: Design,analysis and evaluation

Free riding has long been a serious problem in peer-to-peer (P2P) systems due to the selfish behavior of individual users. To conquer this problem, a key design issue of the P2P systems is to appropriately incentivize users to contribute resources. In P2P Video-on-Demand (VoD) applications, content providers need to incentivize the peers to dedicate bandwidth and upload data to one other so as to alleviate the upload workload of their content servers. In this paper, we design a simple yet practical incentive mechanism that rewards each peer based on its dedicated upload bandwidth. We use a mean field interaction model to characterize the distribution of number of peers in different video segments, based on which we characterize the content providers’ uploading cost as a function of the peers’ contribution. By using a game theoretic framework, we analyze the interaction between a content provider’s rewarding strategy and the peers’ contributing behaviors and derive a unique Stackelberg equilibrium. We further analyze the system efficiency in terms of the price of anarchy and study the long term behavior of the system under a repeated game setting. Via extensive simulations, we validate the stability and efficiency of our incentive scheme.     

一种支持MMOG的可伸缩P2P覆盖网络架构

针对网络游戏独特的伸缩性和局部性需求,提出一种支持MMOG的可伸缩P2P覆盖网络架构SPOAR( scalable P2P overlay architecture).SPOAR在结构化P2P覆盖网络方案分级设计的基础上采用基于MANET的非结构化P2P节点拓扑组织方案来维护节点在游戏世界的邻居拓扑及进行邻点发现.实验表明SPOAR覆盖网络架构在保持全局连通性的同时提高了系统的伸缩性,SPOAR的拓扑一致性算法和容错实现机制能够较好的适应MMOG的动态性.     

Delaunay三角网动态更新算法的研究进展

通过对Delaunay三角网动态更新算法进行研究,综述了Delaunay三角网中插入和删除点、约束线算法以往研究.详细介绍点定位、LOP优化、对角线交换等关键技术的研究进展,并对比各种方法的优缺点,分析已解决的问题和仍存在的问题.最后对更新算法研究不足之处进行总结,并提出若干可能的研究方向.     

一种基于Delaunay三角化的笔划分割算法

字符笔划在字符识别等领域中存在广泛的应用。针对字符图形的骨架化及笔划提取,本文提出了一种基于动态约束Delaunay三角剖分的算法。该方法首先通过对字符的轮廓多边形进行三角剖分,生成一系列具有拓扑关系的三角形,再根据三角形的三种类型生成各三角形骨架,并连接为整个字符的骨架。然后定义了骨架的平滑度函数及分支长度阈值,消除了畸变分支,并根据得到的骨架进行笔划分割。实验结果表明,该算法具有快速稳定的特点且鲁棒性较好。     

基于JXTA P2P的访问控制模型的研究与实现

访问控制技术是防止非法用户进入系统和合法用户对系统资源的非法访问。它尤其在操作系统层面上给主机提供一种安全机制,确保那些认证用户对资源的访问。在P2P(对等网络)中由于缺少集中管理使得访问控制的实现更具有挑战性。在本文中,我们将在一个P2P环境中讨论访问控制机制,并且描述其在基于JXTA的P2P框架下的实现。JXTA是一个流行的开放式的P2P技术规范。     

低维护开销的小世界P2P网络

为降低结构化P2P网络的维护开销,提高路由和查询的效率,提出了具有低维护开销的小世界P2P网络（LMCS）,并描述了网络的创建和维护方法。小世界特征使结构化P2P网络具有较高的路由和查询效率,同时利用成簇机制和扩展COU策略,有效地降低网络的维护开销。通过模拟仿真,LMCS呈现明显的小世界网络特征。与Chord相比,LMCS具有更低的维护开销和更高的查询效率。     

一种面向可用性的P2P数据分发方法

对等网络由高度动态的节点构成,节点间会话时间极端异构。对等节点频繁加入和退出导致对等网络维护开销增大,数据可用性降低。面向可用性的对等网络数据分发方法,针对热点数据和节点可用性的分析,通过增加系统中数据的副本数量,提高数据的可用性,同时减小消息扩散的范围,提高系统的效率,克服会话时间异构性。实验结果表明,该方法可以有效提高数据可用性,降低系统的维护开销。     

三维折剖面的Delaunay三角剖分算法

三维折剖面Delaunay三角剖分在三维地质建模和其他领域具有广泛应用。目前常用的方法是将其投影到二维平面三角剖分。该方法有三点不足：（1）违反Delaunay三角剖分优化准则;（2）悬三角形问题;（3）投影多值问题。通过研究分析三维折剖面的数据组织以及几何特点,提出了折剖面“展开”剖分方法,即将三维折剖面的三角剖分转化为二维平剖面的剖分。该方法具有点之间的水平距离以及原剖面数据拓扑关系不变的优点,很好地解决了折剖面投影三角剖分的不足。