分发算法（精选3篇）
分发算法 篇1
0 引言
1992年，在M.Dorigo的博士论文中首先提出了蚁群算法[1]。该算法是一种基于蚂蚁觅食的生物行为的元启发式搜索算法。开始该算法用于在图中寻找一条最优路径。随后它被应用到了一系列的优化问题中，并且随之衍生出多个ACO的变种，比如MMAS、AS、ACS等。
在原始的蚁群算法中，蚁群中的多只蚂蚁通过协作搜索最优解。蚂蚁之间通讯是通过信息素完成。蚂蚁在觅食的路途中会留下信息素，其它蚂蚁寻路的过程中会选择信息素堆积较多的路径。在真正的蚁群算法的实现过程中，为了防止信息素堆积过快而导致产生过早收敛(又称“假收敛”，即只找到了局部的最优解，并没有获取全局的最优解即发生了收敛)的问题，又引进了信息素的挥发和启发式信息。信息素的挥发有效阻止了信息素的过早收敛，而搜索中的随机启发式信息，使得搜索路径更加发散。
本文的组织如下：第二部分对并行ACO进行扼要的介绍，对现行的相关ACO并行算法进行总结。第三部分提出了一种新的思想，基于任务分发的并行ACO。最后(第四部分)进行了相关的总结以及下一步工作的展望。
1 ACO的并行策略
1998年，Tomas Stutzle也探讨了蚁群的并行策略[3]。他提出了一种最简单的并行方法：在MIMD中，每个节点上走一个蚁群，这些蚁群独自工作，相互之间不交流信息。他在MMAS上的实验表明，这种方法有很好的性能。实际上，这是Bullnheimer等人提出的异步并行策略的一种极端情况。它最大限度地减少了处理器节点之间的通信，更加强调算法的独立运行。
Randall[4]对以上的思想进行了总结，并且在一个真正的并行环境下借助MPI库实现了ACS蚁群算法，得出的结果显示出了并行蚁群的优越性。
Chu[5]在提出了PACS，并行蚁群，他的主要思想是将一个大的蚁群分成一些小的蚁群，这些小的蚁群首先独立工作一段固定的时间或者固定的代数，然后再相互交流信息。这个系统的优点在于综合了Tomas Stutzle的思想和并行蚂蚁思想。它比并行蚂蚁有更少的通讯量，而且各个节点之间相互有所交流，因此能产生比Tomas纯粹的并行蚁群更好的解。
在Chu的基础上，陈崚教授提出了自适应的并行蚁群算法[6]。该算法的核心思想是每个处理器节点根据自身的情况选择跟哪些处理器进行交流信息。
总结以上的观点，得出的一些对本文有启发意义的观点如下：
尽量减少通信是并行ACO设计中最关键的因素;
粗粒度的并行蚁群性能要优于细粒度的蚁群;
目前主要以MIMD的体系结构为主，但是共享内存的SMP架构有利于减少通信;
性能的评价主要有是解的质量和加速比。
本文的思想是在MIMD架构的基础上，通过主控节点对各计算节点进行控制，优化通信时间与计算时间的比例，减少通信量。
2 TD的设计
Ian Foster提出[7]了四步并行算法设计方法，即划分、通信、聚集和映射。其核心思想为，减少通信，负载均衡。TD的设计也即从这一思想出发，采取了功能划分方法，避免不必要的通信，同时要加强对工人(即人工蚂蚁)的控制。
2.1 相关定义
管理者：管理者是指集中是管理中的主控线程，该线程负责算法运行中的同步、任务分发、IO以及信息素更新等信息。管理者会通过广播详细的方式通知工人节点各种信息。
工人：工人是指系统中的计算节点，该节点负责具体的计算任务，除了完成路径搜索任务与接受管理者信息之外，该节点还会同管理者进行主动通信，告知管理者任务已经完成或者发送搜索结果等。该概念对应于原始蚁群算法中的人工蚂蚁。
任务：一个任务就是一次在解空间中单独的搜索。
以下是三者之间的关系图示：
2.2 设计思路
首先，设计是基于MIMD并行系统的。虽然相对于集中式内存管理的硬件系统(SMP架构)，MIMD需要的通信量更大，但是由于目前MIMD架构成为了并行系统的趋势，因此我们仍然采用了基于MIMD的系统架构。
其次，信息素的管理采用集中式管理。所有的节点共享信息素。该信息素存储在主控节点上。每一个节点维护一个本地记录，该记录统计并且维护当前找到的最有解。由主控节点负责所有工人的同步工作。
主控节点负责的任务有：IO操作;向工人节点分发信息素矩阵以及任务;每轮任务结束后负责收集工人的劳动结果并进行统计，更新信息素矩阵。在每一轮任务开始之前，主控节点有一个任务队列，任务队列的长度或者由一个预先设定的时间决定，或者由预先设定的搜索代数决定。工作准备阶段，主控节点向每个工人发送初始任务以及信息素矩阵。虽有任务分发完毕之后，主控节点广播一个“任务结束”信息。各个工人节点收到此信息后，一旦手头工作完成，即向主控节点发送任务“完成报告”，该报告信息中包含了其搜索的结果。然后主控节点对这些信息进行统计并更新，完成后启动下一次搜索。
主控节点负责的任务有：IO操作;向工人节点分发信息素矩阵以及任务;每轮任务结束后负责收集工人的劳动结果并进行统计，更新信息素矩阵。
工人节点的任务是：在构建解的过程中，每个处理器节点完成一次搜索任务之后需要对自己节点上的相关数据进行更新。当手头任务完成之后，主动向主控节点发送任务请求信息，请求再次分配任务。在收到主控节点的结束信号之后，向管理者节点发送自己目前的搜索结果，并且等待下一轮的工作。
2.3 构建解（启发式信息的任意性）
对于MAX-MIN Ant System，在构建解的过程中，所利用的路径选择函数如下：
在构建解的过程中，为了使得各个工人节点尽量发散，在每个处理器节点上都要使用不同的启发式信息权重。这样的结果是各个处理器的搜索侧重点不同：有的更加侧重于沿着信息素信息搜索，而其他的更加侧重于随机启发式信息。在实现过程中，要求主控节点为每一个工人节点随机地产生一个β值。
在收到主控线程的任务分发完毕的信号之后，如果该进程发现自己手头仍然有多于N(N视情况而定，经验值建议设为3)个的任务，则将这些任务抛弃，即完成当前的搜索后立即上报搜索结果。
2.4 任务分发
任务分发由主控节点(管理者)完成。
初始时，管理者设定一个总任务数。该数目通常视要求而定，如果要求是减少搜索时间，则可以设定一定的时间，如果时间结束，则任务分发完毕;如果要求提高解读质量，则可以设定具体的任务数目，完成所有任务则结束该轮循环，进行相关的统计更新操作。
在工作过程中，如果某个收到某个节点的“空闲”信息，则立即为其分发一定数量工作。
管理者瓶颈的解决方法：
显然，同其他的master-slave方法一样，该方法的缺点在于，主控节点的通信量过大，而且执行任务过多，从而成为算法的瓶颈。我们尝试从以下的方面去改善之。
首先，采取任务预取方式。每一轮工作开始时，管理者为每个工人分发多个任务，而不仅仅分发一个任务。另外，当某工人空闲时，分配给该节点的任务数也要大于1。
其次，在广播相关的信息时，可以采取树状广播方式。具体广播方式如下图。
3 结论及TD的进一步探讨
基于TD(task-distribution，任务分发)模式的并行蚁群算法在设计过程中遵循了并行算法设计的两个主要原则：减少通信量与增加处理器节点的使用率。相比于串行蚁群算法，并行算法充分利用了蚂蚁在独立搜索解空间时的并行性，并且通过并行通讯交流信息素。与前文所提到的很多并行算法相比，该算法最大的优点是，在尽量减少节点之间通信的基础上，最大限度地实现了各个处理器节点之间的负载均衡。并且引入了非一致启发式信息，使得各个节点在搜索的过程中，尽量发散搜索，防止过早收敛。
参考文献
[1]Marco Dorigo,Thomas Stutzle.Ant Colony Optimization.Reading,MIT Press.
[2]Bullnheimer Bernd,Kotsis Gabriele,Strau Christine.Report Series SFB《Adaptive Information Systems and Modelling in Economics and Management Science》,Nr.8,October 1997.
[3]Thomas Stutzle.Parallelization Strategies for Ant Colony Optimization.In LNCS:722-731.
[4]A Parallel Implementation of Ant Colony Optimization.
[5]Parallel Ant Colony Systems.
[6]自适应的并行蚁群算法.
[7]Ian Foster.Designing and Building Parallel Programs:Concepts and Tools for Parallel Software Engineer.Reading,MA:Addison-Wesley,1995.
推送模式的P2P流媒体分发算法 篇2
以高质量、富媒体、互动性为特征的流媒体应用是互联网业务的趋势。面对大规模的并发流媒体直播服务,传统的C/S(Client/Server)结构性能表现不能令人满意。改进的C/S模式,例如服务器群组和CDN(ContentDistributionNetwork)网络,将服务的并发数目提高到数百至上千的级别,但是高昂的造价阻碍了这些系统的部署和应用。候选的解决方案之一的IP层多播,在节约带宽方面优于其他的解决方案,但传输的可靠性、安全性、ISP(InternetServiceProvider)的管理成本等制约了该解决方案的实施。随着骨干网和接入带宽的增加,个人终端计算机处理能力的提升,应用层多播成为具有潜力的解决方案,即将P2P(Peer-to-Peer)技术与流媒体技术相结合。P2P技术首先应用于媒体文件的共享,代表应用系统包括Napster、Gnutella、BitTorrent和eMule[1,2,3,4]等。在流媒体应用领域,P2P技术向两个方向发展:流媒体直播和点播。2000年,第一个P2P视频直播系统ESM(EndSystem Multicast)进入使用[5]。ESM系统使用Narada协议自组织地构造了覆盖网络,并在此之上构建了多播树来实现流媒体数据交换。但是,该系统的管理策略复杂,另外树的构造策略限制了同时参与的结点数目在一千左右。从2000年到2003年,更多的原型系统被开发出来,包括Peercast、P2PRadio、CoopNet、Zigzag[6,7,8,9],这一时期的研究热点仍然是集中在成员管理和树状拓扑的构造算法。结点的处理能力、接入带宽、可靠性方面都存在极大差异,这导致覆盖网和树状拓扑的高度动态变化。在大规模的应用时,树状拓扑的上层结点的崩溃导致严重的拓扑调整和重新构建,影响了流媒体回放观感。2004年,CoolStreaming[10]用于直播欧洲杯足球赛。该系统使用Gossip类型的信令协议构建网状的拓扑,使用了类似BitTorrent系统的数据块交换策略,实现了系统的高度可变性,以及对异构网络的适应性,并发服务数目达到数万。相对于树状拓扑,网状拓扑的管理策略更为简单,不存在预先指派的父结点,因而增强了覆盖网的鲁棒性。自CoolStreaming开始,PPLive、PPStreaming等系统进入商业运营,这些系统均采用了网状拓扑的覆盖网。P2P点播的发展相对较缓,基于Gnutella协议的GnuStream[11]是第一个准VOD(VideoonDemand)系统,但是没有支持快进、后退等VCR(VideoCassetteRecorder)操作。另外,P2Cast和CollectCast[12]也是面向P2P VOD协议的。
P2P流媒体直播协议划分为三类:源驱动、接收端驱动和数据驱动[13],管理覆盖网的方法各不相同。源驱动协议需要为新加入的结点指派父结点,数据从源结点开始,以接力的方式向下层的结点推送。接收端驱动协议在接收者一侧建立树状拓扑,由接收端整合和管理结点以获取流数据。数据驱动的协议一般与网状拓扑的覆盖网结合,结点发现自己需要的数据,并从邻居结点获取这些数据。
尽管网状拓扑比树状拓扑有更强的鲁棒性,但是动态的邻居关系使得前者需要更多的缓冲时间寻找媒体数据资源。上述协议的结点在为邻居提供数据时扮演下载服务器的角色,如果NAT(NetworkAddressTranslation)或者防火墙不支持内网穿透,位于内网的结点就不能为外网的结点提供数据。我们提出了推模式P2P流媒体分发算法,简称为推送算法。该算法使用网状覆盖网拓扑和推模式数据分发方法,并结合新数据块优先调度,相比目前的P2P流媒体分发算法,推送算法可以利用处于防火墙内的结点的上传带宽,加快了流媒体数据复制的速度,进而减少缓冲的时间,并保证了结点之间的准同步回放。
1相关工作
源驱动与数据驱动是P2P流媒体直播领域不同时期的研究热点。源驱动方法要求系统维护覆盖网,然后在覆盖网上建立树状的多播树,如CoopNet和Peercast使用了树状的拓扑,NICE[14]和Zigzag则使用了网状的拓扑。在多播树中需要一些担任管理任务结点。例如,Peercast系统由源结点管理多播树的信息,包括子结点的加入、离开,发现子结点的崩溃等。而Zigzag系统中,指派一些优秀的结点为簇的领导,负责簇的管理和簇之间信息的交互。数据驱动的方法通常不会显著地区分覆盖网和数据分发拓扑,例如Coolstreaming使用Gossip算法来构建覆盖网,结点之间周期性地交换他们的缓存信息,结点决定从哪个邻居结点拉拽下载哪块媒体数据。Peercast和Coolstreaming是P2P流媒体直播领域代表性的原型系统,具有参考价值。
1.1 PeerCast
新加入的结点与源结点通信,如果源结点的子结点数未达到上限,源结点接受该结点成为子结点。否则,源结点把该结点引导给它的子结点。新加入的结点重复上述的请求加入流程,直到有结点愿意接受其成为子结点。结点的离开引起拓扑的调整,而结点崩溃引起其所有下层结点的重新加入。我们的流媒体直播服务实验表明,Peercast可以满足低流量的流媒体应用,例如128kb/sMP3,而高流量的流媒体应用,例如781kb/s的WMV视频流媒体应用,其表现不能令人满意。并发数目在数百的数量级时,结点的异构性引发的拓扑的动荡现象十分严重,高层结点的离开和崩溃导致了严重的回放断续。在中国教育科研网,每个结点都具有真实IP地址,平均带宽100Mb/s,视频码率381kb/s,系统峰值并发用户数在250左右。在中国电信网中,大量不具备地址映射能力的内网结点占据了树状拓扑的顶层,从而限制了树的生长,系统退化为C/S模式。
1.2 CoolStrreaming
结点维护邻居结点列表和伙伴结点列表,称为MC(MemberCache),其中伙伴结点是发生数据和信息交换的邻居结点。新加入的结点与源结点通信,源结点随机选择一个邻居结点作为引导其加入的代理结点,代理结点是普通的结点。新加入的结点与代理结点通信,获得其MC来初始化自己的MC。新加入的结点开始在邻居结点列表中选择结点来构建伙伴关系。伙伴结点之间周期性的交换心跳信息和缓存信息(BufferMap,BM)。结点决定从哪个伙伴结点处拉拽哪个数据块。如果拉拽的请求不成功,重新选择伙伴结点。心跳信息超时,从MC中删除该伙伴结点,然后在邻居结点中选择新的伙伴结点。源结点并不知道也不需要维护整个覆盖网的拓扑信息。因此,在动态的网络环境下,其鲁棒性较高。
ThomasSilverston等,对这两种方法进行来仿真对比[13]。从以下的指标对两种方法进行比较:从加入至收到第一个分组的延时,覆盖网中结点的分布情况,结点离开导致分组丢失的程度,离开的结点的位置与导致的分组丢失之间的关系等。仿真结果显示,网状拓扑对网络动态变化具有更好的鲁棒性,网状的拓扑更适合于P2P流媒体直播。
1.3拉拽算法的不足与推送算法的优点
CoolStreaming的鲁棒性胜于PeerCast,但在网络平均上传带宽很窄的情况下,拉拽算法需要更多的交互流程来获取数据。同时,向多个结点请求下载数据并不能解决问题,因为重复的数据块传输浪费带宽,使得本来吃紧上传带宽资源更稀缺。结点扮演下载服务的角色,拉拽算法无法利用处于不能映射的内外结点的上传带宽。拉拽算法的数据调度由BM信息的交换触发,过于频繁BM交换导致通信开销(overhead)增加,太少的BM信息交换又使得数据块交换速度变慢。而推送算法的结点主动连接邻居结点之后就成为上传服务器。拥有富余资源(网络带宽资源、媒体数据资源)主动地向邻居结点请求上传数据,内网结点即使不能进行地址映射的穿透,也能为外网结点提供数据上传,使得整个覆盖网络的上传带宽资源增加。推送算法根据自己的缓存情况来调度数据交换,新接收到数据块可以更快地复制给邻居结点,降低了BM信息发布的频率。如果几个结点同时向同一结点请求推送同一个数据块,只有最先到达的请求会被接受,这样结点之间网络通信速度也被估算出来。而且,推送算法也保证了拥有数据块的结点同时拥有足够的网络带宽资源进行数据传输。推送算法系统的效率更高,缓冲时间,传输延时显著降低。
2推模式P 2P流媒体分发算法的设计
推模式P2P流媒体算法数据调度和数据块交换流程上有别于拉拽算法。
2.1结点加入
结点标志唯一标志符,nodeID<外网套接字,内外套接字>。外网套接字端口号为零时,结点是未能映射的内网结点。推送算法不区分邻居结点与伙伴结点,每个结点维护自己的伙伴列表(PartnerList,PL)。新加入的结点与数据中心(DataCenter)通信,获取相关流的详细信息。例如,接入结点(AccessPoint)的nodeID,流的缓冲策略信息等。数据中心是网络的信息中心,收集网络中正在广播的流信息,以及参与网络的结点信息等。然后,新加入的结点向接入结点发送REQ JOIN消息,请求加入网络,接入结点是普通结点。接入结点给新加入的结点指派一个伙伴作为代理结点(DeputyPoint)。最后,意图加入的结点与代理结点通信,获取其PL来初始化。PL中的一条记录包含如下信息,<nodeID,lastMsgSeq。lastUpdateTime,outByteTemp,inByteTemp,bufferMap>,其中lastMsgSeq是该伙伴最新的消息编号。lastUpdateTime记录着结点与该伙伴最后一次交换数据的时间。outByteTemp和inByteTemp则分别记录结点推送给该伙伴的通信量和该伙伴推送过来的通信量。这两个数值会被定期清空,反映最近的通信情况。bufferMap由<firstBlockNum,bufferMapVec>组成,其中firstBlockNum记录该伙伴缓存的第一个块的序号,bufferMapVec是布尔集合,表示从firstBlockNum开始的相关块的缓存信息,1表示该块存在,0表示该块缺失。
2.2缓存信息发布与校正
结点的BM信息由BUFFER MAP消息以Gossip模式发布,收到该的结点可能会转发该消息。BUFFER MAP消息带有四个域,<msgSeq,nodeID,TTL,bufferMap>。其中msgSeq是该消息的序号,nodeID是该消息的源结点的标志符,TTL是该消息的剩余转发跳数,bufferMap的结构与2.1中结构一致。我们定义结点加入网络至收到第一块数据为启动阶段。处于启动阶段的结点,每隔1s向它的伙伴广播一次BUFFER MAP消息,之后每隔5s广播一次。BUFFER MAP消息的TTL初始值为2。如果消息源结点已经是自己的伙伴,接收者更新伙伴的BM信息并转发该消息,否则执行以下算法来决策是否添加该消息的源结点为伙伴。如果添加消息的源结点为伙伴或者消息源结点为未能映射的内网结点,停止该消息的转发,否则递减TTL值,在TTL值大于零时继续转发该消息。
决策是否添加新伙伴算法:
1)如果消息的源结点是新加入的结点,则添加为伙伴,否则转到2);
2)如果结点的伙伴数目小于最大伙伴数目,添加为伙伴,否则转到3);
3)如果伙伴列表中存在长时间不活跃的结点,删除该不活跃的结点,并添加消息源结点为伙伴;否则,不添加消息源结点为伙伴。
2.3伙伴的探测与淘汰
结点周期性的发布PROBE PARTNER消息,广播其在网络中的存在,并发现其他的新伙伴。PROBE PARTNER消息与BUFFER MAP消息内容一致,处理流程也一致,不同之处是,PROBE PART-NER消息每隔10s广播一次,转发的目标伙伴个数为2,消息TTL初始值为4。PROBE PARTNER消息主要在网络的深度上传输,而BUFFER MAP消息在广度上传输。结点周期性运行统计伙伴间通信量处理流程,淘汰通信量少的伙伴。
2.4调度算法
结点bufferMap变化或者伙伴bufferMap的变化都会触发数据调度。以下的情况会导致bufferMap的变化:接收到完整的数据块,添加新伙伴,伙伴bufferMap更新,以及2.5中将提及的数据推送流程的结束。调度算法分为两步,第一步找到合适的数据块,算法尽力将资源最稀缺的数据块推送出去,越多伙伴缺少的数据块,获得分值越高。同样分值的数据块,选取较新的。第二步决策目标伙伴,随机选择一个没有该数据块的伙伴,向其发出请求。发出请求后,标记该伙伴已经拥有该数据块。
步骤1:
找出needcredit最大的并且标号最新的数据块,标记为MAX NEED BLOCK;
步骤2:
找到目标伙伴;
步骤1中新数据块优先选择算法保证了结点之间准同步回放:
如图1所示,假设结点B为新加入的结点,t1时刻结点A开始调度数据,并向B传输。新块优先的方法首先调度数据块4(图1(a)),而旧块优先的方法则调度数据块1(图1(b))。在t3时刻,A收到新的数据块,新块优先方法调度数据块5,旧块优先的方法继续调度数据块3.t4时刻,B结点缓冲完成开始播放。新数据块优先传输的方法使得A,B结点之间播放时间差为一个数据块的传输延迟。旧数据块优先传输的方法引入的播放时间差与缓冲时间和结点的上传带宽相关。
2.5推送流程
2.4的算法返回数据块号和目标伙伴的nodeID。结点向该伙伴发送REQ PUSH DATA的消息,请求推送数据块。目标伙伴收到该消息后,执行以下算法判断是否接受该数据块。
1)如果该块迟于播放时间,拒绝接收;
2)如果正在从别的伙伴处接收该数据块,拒绝接收;
3)如果自己已经缓存该数据块,拒绝接收;
4)接收该数据块。
如果目标伙伴决定接收该数据块,发送ACK PUSH DATA消息给请求结点,否则发送DENY PUSH DATA的消息来拒绝该数据块的推送。数据块传输完成,或者收到DENY PUSH DATA消息,结点重新调用2.4的算法来决策下一次传输。
3仿真与比较
我们在OMNeT++上对拉拽算法和推送算法进行仿真。仿真参数为:视频流码流381kb/s,数据块划分时间间隔1s,缓冲时间90s,最大伙伴数目为6,参与网络的结点个数1 000,接入上传带宽分为:(1)相同上传带宽,每个结点的上传带宽限制为500kb/s;(2)差异上传带宽,结点的平均上传带宽为500kb/s,其中20%的结点上传带宽为1 000kb/s,40%的结点上传带宽为500kb/s,40%的结点上传带宽为250 kb/s。上传带宽约为流码率的1.3倍。
从以下四个指标比较推送算法和拉拽算法的性能:
1)数据块复制速度:数据块从产生至分发到结点的时间关系;
2)播放缓冲延迟:结点从加入网络至回放开始的延迟时间;
3)数据块传输跳数分布:数据块传输跳数与结点数量的对应关系;
4)通信开销:构建、维护覆盖网的信令通信量占总通信量的比例。
图2给出了推送和拉拽算法在不同网络情况下的数据块复制速度。数据块复制的速度影响了P2P直播系统源端到接收端的回放延时。在相同网络带宽的情况下,推送算法需要13s覆盖所有结点,而拉拽算法则需要45s。在差异网络带宽情况下,由于推送算法可以发掘结点的上传带宽,覆盖所有结点的时间为17s,而拉拽算法由于需要多次交互才能找到合适的下载结点,不能有效地发掘结点的上传带宽,覆盖所有结点的时间需要60s。结点根据自己的BM信息和伙伴的BM信息来调度数据块的复制传输。推送算法收到数据块时立即进行数据调度,节省了数据调度的延迟,并且可以最大限度利用结点的上传带宽。而拉拽算法在BM信息更新时才能触发新一轮的数据调度,BM信息广播的频率会影响数据块复制的速度,不能有效利用结点的上传带宽。在相同BM信息广播频率的情况下,拉拽算法表现不如推送算法。
仿真中结点缓冲时间为90s,缓冲比97%时结点开始回放流媒体数据。在不同的网络情况下,推送算法均优于拉拽算法。如图3所示,在结点数量较少时(结点数目少于300),新加入的结点需要更多的时间来缓冲数据,随着网络规模的增大缓冲时间减少,相同网络规模下推送算法比拉拽算法需要的缓冲时间大约少40s。而在结点数量较大的情况下(结点数量大于400),结点缓冲的时间并不会随着网络规模的增大而减少。这是因为每个结点的伙伴个数是有限的,拥有剩余带宽的结点并不都能发现新加入的结点。缓冲时间与结点的上传带宽相关,在结点的平均上传带宽仅为码率的1.3倍时,推送算法的缓冲时间大概为40s,而拉拽算法需要多出大概20s的缓冲时间。
我们统计了数据块传输的跳数与结点数量的关系,如图4所示。相同上传带宽情况下,推送算法的传输跳数集中在8跳,拉拽算法的传输跳数集中在12跳。差异上传递带宽情况下,推送算法和拉拽算法的跳数分别集中在7跳和11跳。在不同的网络情况下,推送算法的结点分布均比拉拽算法的更为聚集。结点接收的数据块的跳数在一定程度上与数据传输延迟相关,但并非绝对,虽然差异上传带宽情况下的聚集跳数少于相同上传带宽的情况,但是后者的数据块复制速度要稍优于前者。在差异带宽条件下,因为存在一批上传带宽较大的结点,传输反而聚集在较低跳数处,窄带的结点会带入更多的传输延迟。拉拽算法的结点分布比较松散,处于高跳数的结点比例较大,当网络规模增大时,需要增加更多的缓冲时间,才能保证高跳数的结点有足够的下载结点可以选择。
在我们的仿真中,推送和拉拽算法均采用同样的相同的网络和信令参数,两种算法在最大伙伴个数为4和6情况下,通信开销均属于可以承受的范围。而推送算法在通信开销指标上略优于拉拽算法。这是因为推送算法减少了交换的次数,减少了通信开销。
4实际系统运行情况
PB算法的商业运行版本称为ShanonBox,目前该P2P流媒体直播平台正在测试中。软件启动界面及运行界面,见图6。在教育网内,100个结点播放同一个节目,计算机之间的播放延时之差小于4s。推送算法调度时,选择数据块步骤中新数据块优先调度的算法是结点准同步播放的重要保证。实际实验中发现,若使用旧数据块优先调度的算法,结点之间的播放延时差显著增加,延时差在15s左右。
5结论
推送模式的P2P流媒体分发算法有效地利用了内外上传带宽,减少了BM信息频繁交换消耗的通信带宽,以及算法本身在复制分发数据块上的有效性,在各项指标上均优于拉拽算法。而实际的系统测试中,结点的准同步回放也体现了新数据块优先调度的方法的有效性。
摘要：面对大规模的流媒体直播应用,传统的C/S(Client/Server)模式遇到了大量并发服务的巨大压力,P2P技术作为最有潜力的解决方案成为研究的热点。P2P直播技术经历了几个发展阶段,从P2P文件共享,到多播树,到多播网。目前P2P技术正在逐步进入商业运作。如何利用内网的上传带宽,加快流媒体数据的复制速度,减少结点与源结点的传输延时,保证结点之间的准同步播放,提供富媒体的业务等,仍然是P2P技术研究领域的热点问题。相比目前的P2P流媒体分发算法,提出推送模式的P2P流媒体分发算法,结合了新数据块优先调度,能够利用处于防火墙内的结点的上传带宽,加快了流媒体数据复制的速度,进而减少缓冲的时间,并保证了结点之间的准同步回放。
科学数据打包与分发技术 篇3
非常著名的安装程序制作工具, 它提供脚本编辑方式及众多应有尽有的安装选项, 堪比专业级的安装程序制作软件。Wise支持创建一个独立的可执行文件以便于在线发布程序, 也能够支持多磁盘, 并且支持网上 (HTTP和FTP方式) 分发, 支持调用外部DLL、EXE等, 灵活的脚本控制, 根据多年数据打包的经验, 较之其他类型的软件, 它具有体积小, 安装使用方便, 打包分发安全可靠。以下简称Wise902。
2 数据和软件准备
2.1 数据准备
生态数据 (ecological data) 以反映生态信息的属性为测量指标而测得的数据。生态数据是以植被数量分析为基础的各类信息, 一般包括两大类型:
一类是反映群落组成、结构关系的植物区系组成数据, 这些数据是反映群落成员特征的一些定量和定性的属性数据, 即数量数据和二元数据。
另一类是群落的环境组成数据, 包括各种环境因子的测量指标。
所以, 生态数据涉及不少类型的数据, 在本例中有遥感数据、空间地理数据、视频文件、录音文件, 调查表格和其他研究资料等。逐一将它们准备好放置在相应的计算机磁盘中备用。
2.2 工具软件
安装后的Wise902提供了Installation Expert和Script Editor两种控制打包程序的方式。推荐读者使用Installation Expert模式, 它是一种向导的模式, 以这种模式为主, 在向导模式的引领下能够更快更好完成一个复杂的数据打包任务。Script Editor模式是基于脚本, 脚本语法有点像Basic语言。可以在某些特殊的数据使用时再应用它 (例子中分发安装后执行外部程序部分有介绍) , 它左边有一个列表专门提供可以供调用的脚本语句, 需要时选择调用。
3 数据打包
数据打包即数据和应用装配过程, 这个过程在Wise902中变得相当容易。下面就来实现这类数据的打包实践。
3.1 建立工程文件和设置
启动Wise902后, 新建一个工程文件, 命名为:“科学数据.WSE.”, 并在“安装标题中”填入:“生态环境数据的打包与分发”, “默认目录”一栏填入:“生态数据”, 将“默认目录放置在‘Programming Files’的目录下”勾选。如图1所示。
3.2 添加组件和命名
Wise902提供数据打包的分组打包功能, 利用该组件功能在使用时可以将数据分不同类型进行分装, 方便将不同类型的数据源进行打包和管理。在本例中, 所有生态数据按照实际所需, 分为基础数据、专题数据、气象数据、地理空间、遥感、群落样地、群落样方、社会经济、生态计算 (外部计算程序) 以及相关的环境录像和音频数据等, 共11种数据类型。它们将通过Wise Installation的组件装配功能创建对应的数据类型名称。具体步骤如下:在方案定义部分点击“组件”按钮, 之后, 在弹出的组件对话框中再点击“添加”按钮, 在弹出的组件详情对话框中, 填入相应组件名称, 并勾选“默认安装组件 (I) ”选项即可, 如图2所示。重复此步骤, 逐一将上述11个数据类型组件添加完毕, 形成了数据包所有数据栏目, 以便稍后所有生态数据分装进来。
3.3 数据源文件加入
Wise902提供将现有磁盘中的数据文件加入到当前工程应用中来。步骤如下:在安装程序详细资料页面中选择点击“文件”, 弹出文件选择, 并加入对话框, 通过它可以按照所创建的数据分装组件一一地将已经准备好数据添加到包中来, 本例中将1号样地所涉及到11类数据文件全部按要求加到了工程里面, 如图3所示。
(需要注意的在添加目录区操作时, 新建目录和添加文件最好添加一个目录就将所要文件添加进来, 否则Wise902系统会出错, 其他版本有无问题暂不知道)
3.4 添加快捷方式
由于本例中有计算程序, 可以使用专家模式的快捷方式页来向目标电脑上的桌面和开始菜单上添加快捷方式。要在安装过程中添加快捷方式:
(1) 点击“快捷方式”, 弹出快捷方式, 填入相应的内容, 然后单击“添加”按钮, 如图4所示。
(2) 从安装对话框中选择文件, 在左边选择包含你想要与之关联的文件类型的程序文件的目录, 在右边选择要关联的快捷方式的文件。
(3) 点击“确定”, 然后在快捷方式的详细资料对话框中编辑快捷方式的详细信息。
3.5 添加注册表键和键值
作为一个专业安装包有时候需要想Windows注册表添加相应的包特征信息, 可以使用专家模式的注册表页来制定要在目标计算机上添加或编辑的注册表项。上面的两个列表框显示了本地计算机上的注册表键和键值。下面的两个列表框显示将要在目标计算机上添加的键和键值, 如图5所示。
“添加键”按钮可以复制一个完整的注册表键, “添加值”按钮可以复制键值, “新建”按钮可以通过导入一个注册表文件来创建一个新的注册表项。
要添加一个注册表项:
(1) 在下面左侧的列表框中单击选择想要添加的键值。
(2) 单击“新建”按钮然后从下拉列表中选择相应的键。
(3) 在这册表项设置对话框中配置注册表值。按F1启动帮助。
3.6 添加关联文件
生态数据中有的要用某一类程序才能打开, 在专家模式下使用关联文件页可以配置关联一个文件的应用程序用来打开这个类型的文件。要为一个文件类型配置一个关联程序:
(1) 在关联文件页, 单击“添加”按钮, 弹出文件选择对话框, 如图6所示。
(2) 从安装对话话框中选择文件, 在左侧选择包含要关联的文件类型的可执行文件的目录, 右侧为要关联的文件。
(3) 在对话框的底部, 数据3个字符的扩展名来标识关联的文件类型。
(4) 单击“确定”。
要编辑一个文件关联的设置, 双击文件关联页中的项目即可。
3.7 指定系统配置需求
通过专家模式中的“系统配置需求”页, 可以指定安装程序运行的最低软硬件需求, 同时可以设置如果目标电脑的不满足最低需求时出现的警告信息。
这里有一个例子用来制定在Windows XP下安装程序最低的操作系统需求。
(1) 在目标系统需求页, 双击“Windows NT版本”, 弹出配置对话框, 如图7所示。
(2) 在最低系统需求对话框中找到Windows版本下拉列表, 选择Windows XP。
(3) 从“类型”下拉列表中选择“建议”或者“必需”。如果选择的是“必需”, 而目标系统不满足系统, 则安装程序将终止安装。
(4) 为消息对话框输入标题和内容, 如果目标电脑低于Windows XP或更高的操作系统, 那么会弹出这个消息对话框。
(5) 单击“确定”。
3.8 选择安装对话框
通过点击在专家模式用户界面页面的“对话框”项, 选择合适的安装时出现的对话框界面, 可以指定在安装期间出现的对话框样式。要查看选择的对话框样式, 可以勾选某个对话框然后双击样式名字, 并即将打开自定义对话框编辑器。
下面是如何添加一个“自述”对话框的例子:
(1) 在对话框页, 标记“自述文件”选择框并双击。如图8所示。
(2) 在路径名称区, 输入要使用的自述文本文件的路径名称。
(3) 需要修改对话框样式可点击“编辑”按钮进行。
3.9 BDE配置
本实例中生态计算程序设计部分数据库文件的使用, 所以需要针对它们完成数据库引擎BDE的设置, 通过点击在专家模式中“BDE Runtime”页, 弹出数据库引擎配置对话框, 如图9所示。要实现BDE配置:
(1) 在BDE安装类型 (P) 处, 选择部分BDE 32安装选项。
(2) 在BDE 32子集页处, 勾选SQL, Paradox和DBASE选项。
(3) 如需要添加本机中的BDE别名, 点击“添加”按钮。
3.1 0 安装密码
从数据安全的角度, 有必要给所形成的安装包设置权限。Wise 902提供了这一功能, 在安装选项页面, 选择并点击密码弹出密码设计对话框, 如图10所示。要实现安装密码的设置:
(1) 选择在“所有安装程序使用单一密码”, 并设置所需要的密码内容。
(2) 如果需要类似专业软件安装系列号, 选择“使用个别的序列号作为密码”设置。
3.1 1 分发安装后执行外部程序
有时候当数据包安装在目标计算机后, 需要执行某个外部应用程序, 本实例中就是设计当安装包安装解压后自动执行包中的生态计算程序 (calc.exe) 。
(1) 在用户界面页面的安装对话框中, 勾选“安装选项”对话框, 使这一界面在安装过程中出现以便选择“安装完成后开始执行程序”, 一旦选择了此项, 系统将自动执行设置好的外部可执行文件, 如图11所示。
(2) 通过双击在脚本编辑器页面的“执行程序”项, 在弹出的执行程序设置的对话框界中进行程序文件浏览和选定, 可以选择任何打入包中程序文件, 同时脚本部分内容也将自行加入或更新, 即增加了新的脚本内容:
Rem在这里设定退出安装要运行的程序:
如图12所示。
至此, 数据的打包和设置已经结束, 需要将该数据包工程文件 (科学数据打包与分发.wse) 保存。
4 数据分发
数据分发与数据打包过程基本相反, 是将所装配的数据和应用程序分装到不同的介质上, 并通过安装程序将包中所有数据和程序按打包时的要求部署到目标计算机中。
4.1 分发介质
介质指存放数据包的物理设备, 在Wise 902中介质可以是多种类型的, 分发前可以进行选择。要实现安装包分发介质的选择, 通过点击在专家模式编译选项页面的“介质”项实现, 如图13所示。
(1) 单一文件安装程序:创建一个独立的磁盘文件, 该文件与工程文件同名。
(2) 基于介质的安装程序:该选项将数据包的内容分割为适合的介质类型文件, 有多个文件组成 (*.W0x, x>2) , 保证数据能够存放到相应介质中。
4.2 编译安装程序
一旦完成了创建或修改一个安装程序, 可以通过位于主窗口右下方的编译, 测试和运行按钮来进行调试。
(1) 点击“编译”, 编译所创建的安装程序, 在工程文件位置生成可执行安装包程序, 如本例的科学数据打包与分发.exe。
(2) 点击“测试”, 模拟安装过程, 但是不对系统做任何修改。
(3) 点击“运行”, 编译和实际运行所生成的安装程序。
图14是该安装包程序执行过程的两个数据分发的交互界面, 通过操作该程序文件分装过程, 可以看出Wise 902无论是数据装配, 还是分发与安装在功能和操作上都是非常专业和方便的。
5 结语
利用Wise 902和生态数据进行打包和分发全部过程已介绍完成, 读者可以体会到该工具的专业性和简便性。尤其是在应用程序数据库数据库文件, 利用它进行打包和分发, 安装部署均显得心应手, 不像其他的安装制作工具使用过程过于繁杂。经常做数据打包和分发的人会发现, 实际上有不少都是用Wise Installation System完成的, 而且数据的安全性也是有保证的。
摘要：生态的调查研究和实验过程常常会涉及到诸多数据, 这些数据往往类型多样, 数据量极大, 数据获取相当不易, 对数据管理和使用提出了更高的要求。利用Wise Install System9.02作为这类数据管理和分发的工具, 面对纷扰繁杂的各种各样数据, 能够对科学数据进行组织和管理, 打包与分发, 实现更为有效管理和安全使用。