基于簇的移动多媒体客户请求调度策略*

唐瑞春,纪红英,巩存群

(中国海洋大学信息科学与工程学院,山东青岛266100)

近年来,随着无线网络技术的发展和高性能的移动设备(手机、PDA、笔记本)硬件设备技术的发展,移动多媒体的应用范围也越来越广泛,从商业到娱乐,从教育到远程控制,甚至危机应对等。

由于移动多媒体网络的异构性、动态性、共享性等特性以及多媒体数据量大、传输时间长[1]等特点,多媒体的传输需要大量的带宽和服务器资源,如果单纯的依靠部署更多的服务器和提高网络带宽性能来提升流媒体系统的服务质量成本太大。更为科学的调度和传输多媒体才是解决问题的关键。

早期移动多媒体调度方法是Agraw al P等[2]提出的C-S架构下的调度模型。该模型的调度办法是服务器存储一系列的多媒体文件,移动设备直接连接到媒体服务器上,使用客户端软件向服务器请求媒体数据;媒体服务器向客户端以等时数据流方式传输被请求到的媒体数据来响应客户端的请求。C-S调度系统中,资源寻找算法相对简单,但是可扩展性差,随着用户数量的增加,服务器面临着瓶颈拥塞,负载大,网络带宽压力大的问题。

为了缓解服务器和整个传输网络的压力,Varap rasad G等[3]提出了1种基于代理的资源调度模型PCRSS架构。在这种调度模型中,一系列的代理服务器被部署在网络中,客户端可以请求缓存在代理服务器上的全部的媒体文件或者部分媒体文件。代理服务器使用缓存技术[4]缓存多媒体数据,当客户端发出服务请求时,mediator接受客户端的请求,并利用监控技术[5],监测网络中代理服务器的负载和网络带宽,调度资源发现算法寻找合适的代理服务器来响应客户端的请求,资源调度过程使用内容分发技术[6]把缓存在代理服务器上的多媒体数据分发给客户端。这种请求调度模型系统在一定程度上缓解了服务器的瓶颈现象,也减少了网络传输媒体数据负载压力。

然而,C-S调度模型和基于代理的调度模型,用户期望源多媒体服务器和代理服务器传输高质量的媒体服务,因而服务器和代理服务器必须具备较高的处理能力,较大的媒体传输带宽上限,和较大的存储空间,而这些部署和维护提高了整个模型的运营成本。另一方面,近年来的研究和实验表明当前的网络有足够的能力支持移动流媒体的P2P传输方式[7-8]。

为了更有效的解决服务器和代理服务器所面临的传输带宽和负载的问题,文中提出1种基于簇的客户请求调度系统CCRSS(Cluster-Based Client Request Scheduler System)。CCRSS充分利用本地的性能较强的移动终端设备作为底层的服务提供者向附近的媒体请求客户提供它所缓存的多媒体数据,以减少服务器和代理服务器的负载,缓解网络传输带宽压力。

1 移动多媒体网络环境

本文所提出的基于簇的客户请求调度系统CCRSS适用于3层移动多媒体系统结构,此类系统的网络结构见图1。

移动设备层由移动设备(手机、PDA、笔记本等)组成,主要负责请求多媒体数据,向用户显示接收到的媒体数据。本层的移动设备用节点来描述。该层成员根据节点的性能分为超级节点和普通节点。缓存空间大,CPU性能高,剩余电量大的移动设备作为超级节点。相应的,性能较差的移动设备作为普通节点。超级节点通过自组织系统[9]构成的簇与Local-mediato r共同形成本地服务层。本地服务层通过CCRSS调度缓存在超级节点里的数据为移动设备层提供多媒体数据。全局服务提供层中,Yun Huang等[10]详细设计global-mediato r的各个服务模块调度缓存在Proxy server上的数据来响应客户端。

图1 3层移动多媒体网络结构图Fig.1 Three-layersmobile multimedia network structure

2 CCRSS的工作流程

CCRSS包括客户定位模块,簇节点信息管理者,簇节点选择者,簇节点判断者,簇服务提供者,代理服务器。每个组件的工作模式见图2。

CCRSS系统负责将请求的客户定位到合适的媒体服务器上。客户端发出服务请求后,CCRSS首先通过客户定位模块判定该用户所在的簇,簇信息管理者在请求者所在的簇中寻找能提供服务的簇节点,然后请求者向该节点发送服务请求,被定位的节点向客户提供服务,若不存在合适的节点,则调度代理服务器的资源为客户提供服务。最后簇判断管理者判断该请求节点能否作为簇成员节点,若符合,则更新簇信息管理者。

图2 CCRSS调度系统Fig.2 Cluster-based client request scheduler system

3 CCRSS的设计

CCRSS主要构件是客户定位模块,簇节点信息管理者,簇节点选择者,簇节点判断者,簇服务提供者,下面详细介绍这些主要模块的设计。

3.1 客户定位模块

移动设备节点发送资源请求信号,客户定位模块首先确定该节点所在的簇,从而确定资源查询的范围。为了缩小资源查找的范围从而缩短资源寻找的时间,簇节点服务层中采用簇技术[9]。由于无线设备间的通信受距离的限制,客户定位模块主要考虑距离因素的影响。

设请求节点为Ni(Ai,Bi);

Ni:第i个节点;

Ni+k:Ni附近的第k个节点;

Ai:节点Ni的经度;

Bi:节点Ni的纬度;

R:地球半径;

L:无线通信的有效距离;

D:节点间的距离。

请求节点Ni向基站发出资源请求,基站将该请求转发给Local Mediator,由Local Mediator调用客户节点定位模块,执行节点定位算法,来确定该请求节点的位置信息。

请求节点定位算法如下:

Step 1 捕获节点的位置信息数据Ni(Ai,Bi)。

Step 2 计算节点Ni与附近1-hop节点Ni+1,Ni+2,…,Ni+k,…,Ni+m之间的距离,

Step 3 判断请求节点所在的簇。

3.2 簇信息管理者

簇信息管理者负责组织和管理簇,分2步执行:管理簇的成员;管理簇成员缓存的资源。

每个簇都有1个cluster_ID作为簇的唯一标识,簇的成员node_id位于该cluster_ID下。当1个新的簇节点请求加入该簇时,更新簇信息表Cluster_number,当节点所在的簇尚不存在时,创建cluster_ID,再向cluster_ID下添加该节点作为其成员。当簇中的节点移出时,在簇信息表Cluster_number中删除该节点,若簇中所有节点都移出时,删除cluster_ID,即删除该簇信息表。簇信息管理者周期性向周围的簇节点发布查询信息,时时探测簇节点的状态,从而确保簇信息管理者信息的实时性,实现簇信息同步。

每个资源都有1个统一的标识,簇节点资源列表为cluster-resource。当1个簇节点缓存1个新资源时,则更新簇信息管理者,即向cluster-resource中的簇节点node_ID下添加1个新的resourc_ID,而当已经缓存下来的资源被删除或者其它数据覆盖时,相应的删除簇节点node_ID下所对应的resource_ID。当簇节点的资源改变时,要更新资源管理者,从而更加准确的寻找本地的资源。

3.3 簇节点选择者

为了给请求者服务较长的时间,使用簇节点选择者选出候选节点中性能较好的移动设备节点作为服务提供候选者。影响移动设备的性能因素很多,主要考虑以下几个因素:设备的在线服务时间、上传带宽、节点空闲度。

节点Ni的服务寿命表示由历史记录推测的节点“在线”服务的最长时间。在移动多媒体模式下,节点当前的服务寿命函数可用文献[11-12]给出的Pareto累计分布函数来表示,

其中:Li_current表示节点当前的服务寿命标准值;x为服务寿命;α表示预测节点未来时间服务寿命;β表示调节分布均值的调节参数;Powersurp为节点剩余电量;Pow erentire表示移动设备电量满值,k表示设备至此时为止运行的总服务的数目,A是常量,表示单位时间内电量消耗值,m量值指从上次统计至此刻设备运行的时间。Consavg是常规情况下设备消耗电量的均值,Conspre预计未来时间内设备电量消耗值。

根据目前的设备运动模式,通过数据挖掘技术预计设备未来工作情况时,使用公式(3)获得x值。

上传带宽功能定义节点Ni上传带宽,由公式(6)计算:

其中,Bi_available表示节点Ni可用的上传带宽比率,Btotal表示Ni节点能提供的上行带宽的总值;Bcurrent表示Ni节点当前已被占用的上行带宽的总值;Bj_upload表示为第j请求提供服务时所占用的上传带宽;k表示Ni节点当前提供服务的数目。

空闲度Ii_idle是Ni节点中CPU空闲百分比,其中

其中,CPUused表示每个程序使用的CPU使用率。

假定流媒体为常速率播放,播放速度为R,节点Ni所能提供的上传带宽为ri,节点“在线”时间为Ti,节点集合用{N1,N2,…,Ni}表示,搜索获得节点集合为L,算法结束返回选定资源节点集合为Sc

簇节点选择算法CNSS(Cluster Node Selection A lgorithm):

Step 1 搜索节点所在簇,得到簇节点集合L

Step 2 if(集合L不为空)

{

将L中所有簇节点按Ii_idle降序排序;

For(L中的每一个节点Ni)

If(Ni的Ii_idle>I,I为常量)

将Ni放入节点集合B;

If(集合B不为空)

{将B中所有簇节点按Bi_available降序排序;

For(B中的每一个节点Ni)

If(Ni的Bi_available>播放速度R)

将Ni放入节点集合C

Else 将Ni放入节点集合C

}

If(集合C不为空)

{

将C中所有簇节点按Li_current降序排序

For(j

If(Sc≠“)

Return Sc={N}

Else

{

Fo r(C中的每一个节点Ni)

Ni放入节点集合Sc={N1,N2,…,Ni}If(Sc≠“)

Return Sc

Else send request to globalmediator

}

}

在节点选择策略的基础上,接收者接收的同时对数据传输进行监控,如果发现一段时间内的数据传输速率下降或者有节点离开的话,将会从备选节点集合中选择替代节点,并产生新的调度表。

3.4 簇节点判断者

簇节点判断者根据节点的自身能力即节点带宽B、存储能力S,计算能力C,节点的在线时间L来判断该节点能否作为簇节点。节点能力表达公式如下:

其中:α,β,δ为调节参数,用来调节带宽,存储能力及计算能力对节点性能的影响。L是节点的在线生命时间,对节点的性能起着关键作用。α,β,δ参数值可根据媒体的质量和用户的要求作相应的设置。

4 CCRSS有效性证明

抖动率与服务器带宽压力是影响多媒体质量的重要因素,也是衡量调度系统的主要技术指标,本文就这2个技术参数对本文的CCRSS和目前流行的PCRSS调度算法做比较说明。

4.1 CCRSS调度与PCRSS调度的播放抖动率比较

播放抖动率指未按时到达的数据总量占客户端所需要总数据量的百分比[10]。设1个多媒体文件可以分为Si(1≤i≤N)片段。片段为任务调度单位,每个片段可分为n块,块为最小的资源提供单元,大小为B。为了满足播放条件,有B=kr,其中r为播放需要的带宽,k为播放速率。1个多媒体文件被缓存在kp代理服务器和kl簇节点上。每个节点提供的平均带宽为r,则每块需要时间才能传完,每个代理服务器上的某一块在时间t时刻失败概率为pp(t),每个簇节点的失败概率为pc(t)。pp(t)和pc(t)看成是时间t的离散函数,在(t～t+1)s内,代理服务器与簇节点失败概率分别为pp(t)和pc(t)。

(1)若节点以某一特定概率失败,即pp(t),pc(t)为常数时,分别为ppraxy_fail,pcluster_fail。传输媒体数据的某一片段失败即客户端在这个时间段内接收不到所需的数据。代理服务器传输失败事件与簇节点传输失败事件二者是相互独立的,簇内节点的失败也是相互独立的事件。数据片段中块与块之间的传输失败与否是无关的,即块与块传输失败事件是相互独立的,因此传输媒体数据的某一片段失败的期望数据量为:

为简化运算,令缓存该片段的代理服务器数目为1,簇节点的数目为l,则抖动率为:

(2)当pc(t)服从修改的Pareto分布[13],有:如果一个特定节点寿命为l,则l

其中α,β为参数,我们可以根据具体网络状况动态确定。故在某一时间段(t～t+1)的失败概率为

则在时间段(t～t+1)的期望传输失败次数为p(t),传输某一个数据片段时间为,故期望失败数据量为

那么传输抖动率为

说明:由表达式(10)(14)可得,簇节点的失败概率pduster_fail时,表达式(10)(14)取“=”号,即αjitter1pproxy_fail,则该系统的媒体抖动率与基于代理的客户请求调度PCRSS的抖动率相同。当簇节点的失败概率p duster_fail<1,表达式(10)(14)取“<”号,即αjitter1

当l=0时,即簇节点的数目为0,CCRSS的多媒体抖动率与PCRSS多媒体抖动率相同。当l>0时,CCRSS多媒体抖动率低于PCRSS的多媒体抖动率。由(10)～(14)式可以看出,不论节点的失败概率为一常数还是符合Pareto分布,簇节点资源提供者l越大时,客户端面临传输失败的可能性越小,播放抖动率也越小,因此选择尽量多的簇节点作为资源提供者。由此看见,CCRSS较之PCRSS能够在一定程度上减小多媒体的抖动率,由(11)式可以看出,1个节点在线时间越长,其继续在线的概率也越大,因此尽量保证所选节点的稳定性,减小播放抖动,我们优先选择满足带宽要求的在线最长的节点。

4.2 CCRSS调度与PCRSS调度的服务器带宽负载比较

针对多媒体数据大,用户请求量大的特点,主干网的带宽压力是移动多媒体发展的一个瓶颈。CCRSS可以有效地利用已经缓存在本地移动设备节点上的数据大大的减轻服务器带宽负载。

设媒体M包括{s1,s2,…sk,sk+1,sk+2,…sN}数据片段,有2个代理服务器缓存媒体M,p roxy1,p roxy2分别缓存片段{s1,s2,…,sk},{Sk+1,Sk+2,…,SN},簇节点cluster node1,cluster_node2,cluster_node3分别缓存片段{s1,s2,…,si},{sj,…sj+m,…,sj+l},{sp,…,sp+q)。其中,0≤i≤j≤p≤N,0≤m,q≤N并且j+m≤k,j+m+1≥k+1,p+q≤N。媒体m正常播放需要传输的时间为T,t1为传输{s1,s2,…sk}需要的时间,t2为传输{sk+1,sk+2,…sm}需要的时间,T=t1+t2。

CCRSS首先调度簇资源节点,充分利用本地缓存的数据,由于移动设备间无线通信,不占用有线带宽。设p roxy1,p roxy2传输数据需要的带宽分别为Band1和Band2。

p roxy1需要传输的多媒体片段为:{s1,s2,…sk}-{s1,s2,…si}-{sj,…sj+m},则band1

proxy2需要传输的多媒体片段为:

簇节点缓存媒体文件M的片段为“时,(15)和(16)的等号才能取得,即当移动设备对媒体文件没有缓存时,代理服务器的上传带宽是PCRSS情况下带宽。簇节点缓存的媒体数据越多,代理服务器需要上传的数据越少,则需要占用的上传带宽越小,压力越小,负载也就越小。当{s1,s2,…sk}∪{s1,s2…si}∪{sj…sj+l}∪{sp…sp+q}={s1,s2…sN}时,代理服务器需要上传的数据为0,该调度对代理服务器的负载为0。由此看见,CCRSS较之PCRSS能够在移动用户请求数量较多时缓解服务器带宽压力。

5 结语

本文针对目前移动多媒体系统抖动率大,带宽上限小及多媒体服务器带宽负载较大的问题,在传统的移动多媒体系统的两层架构模型的基础上,提出了移动多媒体中的CCRSS,从而充分利用性能较高的移动设备上缓存的多媒体数据来为请求者提供服务。最后用数学方法证明CCRSS较目前流行的PCRSS更能有效的减小媒体抖动、降低阻塞率,减轻服务器带宽压力。

[1] Huang Chenn-Jung,Hu Kai-Wen,Chen You-Jia,et al.QoS-aware VoD resource sharing scheme for heterogeneous networks[J].Computer Networks,2009,53(7):1087-1098.

[2] Agraw al P,Hyden E,Krzyzanow ski P,et al.SWAN:A mobile multimedia w ireless netwo rk[J].IEEE Personal Communications,1996:17-33.

[3] Varaprasad G,Wahidabanu R SD,Venkataram P.An efficient resource allocation scheme formultimedia applications in MANET[J].Journal of Network and Computer Applications,2008,31(4):577-584.

[4] Tang W K S,Wong EW M,Chan S,et al.Optimal video placement scheme for batching VOD services[J].IEEE Transactions on Broadcasting,2004,50(1):16-25.

[5] Chan C L,Huang S Y,Wang J S.Performance analysis of proxy caching for VOD services with heterogeneous clients[J].IEEE Transactionson Communications,2007,55(11):2142-2151.

[6] Ho K M,Poon W F,Lo K T.Performance study of large-scale video streaming services in highly heterogeneousenvironment[J].IEEE Transactionson Broadcasting,2007,53(4):763-773.

[7] Leung M F,Chan S H G.Broadcast-based peer-to-peer collaborative video streaming among mobiles[J].IEEE Transactions on Broadcasting,2007,53(1):350-361.

[8] Liu J C,Rao S G,Li B,et al.Opportunities and challenges of peer-to-peer Internet video broadcast[C].Hong Kong,China:Proceedingsof the IEEE,2008,96(1):11-24.

[9] 刘业,杨鹏.基于自组织聚类的结构化P2P语义路由改进算法[J].软件学报,2006,17(2):339-348.

[10] Huang Yun,Mohapatra Shivajit,Venkatasub-ramanian Nalini.An energy-efficient middle ware for supporting multimedia services in mobile grid environments,coding and computing[C].Zagreb:Croatia Proceedings of the International Conference on Information Technology,2005:220-225.

[11] Leonard D,Zhongmei Y,Rai V,et al.On lifetime based node failure and stochastic resilience of decentralized peer-to-peer networks[J].IEEE/ACMTransactions on Networking,2007,15(3):644-656.

[12] Xiao L,Zhuang Z,Liu Y.Dynamic layer management in superpeer architectures[J].IEEE Transactions on Parallel and Distributed System,2005,16(11):1078-1091.

[13] Tian Y,Wu D.Imp roving stability for peer-to-peer multicast overlays by active measurements[J].Journal of Systems A rchitecture,2008,54(1-2):305-323.