面向网络多媒体传输服务的资源分发方法

摘要

本发明公开了一种面向网络多媒体传输服务的资源分发方法。根据网络代理服务器的个数、可用空间、多媒体资源的大小，采用初始分发方法，把中心节点上存储的所有资源分发到代理节点上；根据用户对多媒体资源的访问次数即点击率，周期动态调整多媒体资源在代理服务器上的备份数，由于存储空间有限，以点击率高文件换取点击率低文件所占的空间。该方法采用了动态规划方法，以被替换文件在未来短期内点击率可能反弹所带来的传输代价作为优化目标来选取被替换的多媒体资源，避免盲目和不切实际的调整引起网络传输带宽的消耗，提高多媒体资源在网络代理服务器上分布的合理性，和多媒体网络传输服务的质量。

主权项

1.一种面向网络多媒体传输服务的资源分发方法，由以下两个步骤组成：(1)根据网络代理服务器的个数、可用空间、多媒体资源的大小，采用初始分发方法，把中心节点上存储的所有多媒体资源分发到网络代理服务器上；(2)根据用户对多媒体资源的访问次数即点击率，周期动态调整多媒体资源在网络代理服务器上的备份数，由于存储空间有限，调整方法将以点击率高文件换取点击率低文件所占的空间；其特征在于：所述的采用初始分发方法，是根据实际网络系统中网络代理服务器的个数、可用空间和多媒体资源的大小，初始分发具体步骤如下：(1.1)计算每个多媒体资源的初始备份数：假设网络代理服务器的个数为n，每台可用空间，小于或等于剩余空间，为C₁，C₂，...，C_n；多媒体资源共有m个，其大小为S₁，S₂，...，S_m，其备份数为N₁，N₂，...，N_m；规定每个多媒体资源在一台网络代理服务器上最多只能放一份，每个多媒体资源的备份数与该多媒体资源的大小成正比：$\frac{S_1}{N_1\times {\alpha }_1}=\frac{S_2}{N_2\times {\alpha }_2}=\frac{S_3}{N_3\times {\alpha }_3}=···=\frac{S_m}{N_m\times {\alpha }_m}---\left(1\right)$其中α₁，α₂，...，α_m为各个多媒体资源备份数的调节因子；初始分发的约束条件是：$\underset{i=1}{\overset{n}{\Sigma }}{C}_i=\underset{j=1}{\overset{m}{\Sigma }}{S}_j\times N_j---\left(2\right)$从公式(1)和公式(2)可以求出每个多媒体资源初始分发的备份数为：$N_t=\frac{S_t/{\alpha }_t}{\underset{j=1}{\overset{m}{\Sigma }}({S_j}^2/{\alpha }_j)}\times \underset{i=1}{\overset{n}{\Sigma }}{C}_i,$其中1≤t≤m  (3)网络代理服务器总的可用空间和总的多媒体资源大小有如下关系：$\underset{i=1}{\overset{n}{\Sigma }}{C}_i=\underset{j=1}{\overset{m}{\Sigma }}{S}_j+X---\left(4\right)$其中X大于等于零；为了保证每个多媒体资源的备份数大于等于1，即N_t≥1，1≤t≤m，有如下关系成立：$\frac{S_t/{\alpha }_t}{\underset{j=1}{\overset{m}{\Sigma }}({S_j}^2/{\alpha }_j)}\times \underset{i=1}{\overset{n}{\Sigma }}{C}_i\ge 1$$\Rightarrow \frac{S_t/{\alpha }_t}{\underset{j=1}{\overset{m}{\Sigma }}({S_j}^2/{\alpha }_j)}\times (\underset{j=1}{\overset{m}{\Sigma }}{S}_j+X)\ge 1$$\Rightarrow X\ge \underset{j=1}{\overset{m}{\Sigma }}{S}_j(\frac{S_j/S_t}{{\alpha }_j/{\alpha }_t}-1)---\left(5\right)$令$f\left(t\right)=\underset{j=1}{\overset{m}{\Sigma }}{S}_j(\frac{S_j/S_t}{{\alpha }_j/{\alpha }_t}-1),$其中1≤t≤m，由此得到：$\underset{i=1}{\overset{n}{\Sigma }}{C}_i\ge \underset{j=1}{\overset{m}{\Sigma }}{S}_j+f{\left(t\right)}_{\max }---\left(6\right)$其中f(t)_max是f(t)最大值；由公式(1)得其中令α₁＝1，由此计算出每个多媒体资源备份数调节因子的上下界：$\frac{S_k}{S_1}·\frac{n}{1}\le {\alpha }_k\le \frac{S_k}{S_1}·n---\left(7\right)$(1.2)每个多媒体资源都有一个服务器链表，记录了存储该多媒体资源的网络代理服务器的信息；另外每个网络代理服务器上都有一个文件链表，记录了存放在该网络代理服务器上多媒体资源信息；(1.3)在初始状况下，存在两个链表：文件链表file_List_0：其中每一项为<文件名，文件大小，服务器链表，点击率，增加备份数>，由于file_List_0初始化时还没有完成文件的分发，所以file_List_0保存的是多媒体资源文件列表，按照多媒体资源的发布时间排序；所述的文件链表file_List_0中每一项的服务器链表初始化为空，每一项点击率初始化为0，每一项增加备份数初始化为0；服务器链表serve_List_0：其中每一项为<服务器容量，可用空间，最大利用率，当前利用率，文件链表>，该服务器链表server_List_0中每一项文件链表记录了该网络代理服务器所拥有的多媒体资源，初始化为空；(1.4)将文件链表file_List_0按照每个多媒体资源的发布时间排序，离当前时间最近的排前面，然后从头开始遍历，同时累加所遍历项中的文件大小，当累加值大于等于所有网络代理服务器的容量之和时，遍历终止，同时把余下的数据项删除，得到文件链表file_List_1；(1.5)如果file_List_1不空，取出file_List_1的第一项f0，然后在file_List_1中删除f0；如果file_List_1为空，则跳转到步骤(1.7)；(1.6)对于从file_List_1取出的f0，作如下处理：(1.6.1)设定每个多媒体资源的初始备份数为2，且这两个备份分别放在不同的网络代理服务器上，设置一个备份计数器Counter，备份计数器Counter初始值为0；(1.6.2)将server_List_0中每一项按照可用空间从大到小排序；(1.6.3)从server_List_0取出一项，检查该项中服务器的可用空间是否大于等于f0的大小，如果条件成立，则在多媒体资源f0的服务器链表中加入该网络代理服务器的索引号，同时在服务器链表中该网络代理服务器的文件链表中加入多媒体资源f0，重新计算该网络代理服务器当前利用率，可用空间；(1.6.4)备份计数器Counter加1，如果备份计数器Counter＝2，则把f0的文件名压入到分发成功的文件队列queue中，跳出循环，返回步骤(1.5)，否则server_List_0列表中的指针移到下一项，返回(1.6.3)步骤；(1.7)将队列queue中的所有元素弹出，得到文件链表file_List_2，就是分发成功的文件链表；所述的周期动态调整多媒体资源在网络代理服务器上备份数的方法，根据用户对多媒体资源的访问次数即点击率，以点击率高文件换取点击率低文件所占的空间，具体步骤如下：(2.1)将文件链表file_List_2根据点击率从大到小排序，然后从头开始遍历，同时累加所遍历的项中的点击率，当累加值大于等于文件链表file_List_2中所有项的点击率的总和的80％时，记录当前位置q，然后遍历终止；(2.2)复制file_List_2中的前q项，得到文件链表file_List_3，将点击率最高点β_M映射到备份数相应的最高值N，变换系数计算如下：其中K₀为调节因子，当K₀等于1时，就相当于点击率最大的多媒体资源在每台服务器上都有一个备份的情况了；(2.3)然后计算文件链表file_List_3中每个文件需要增加的备份数增加备份数＝文件的点击率×变换系数-该文件当前备份数把文件链表file_List_3各项压入队列queue1；(2.4)从queue1中删除“增加备份数”小于等于零的项，如果队列不空，取出queue1中第一项f1，同时从queue1队列中删除该项，否则跳转到步骤(2.10)；(2.5)将服务器链表server_List_0按照服务器点击率从小到大排序，服务器点击率是指该网络代理服务器上的所有文件的点击率的总和，然后从头开始遍历服务器链表server_List_0，在遍历到的项中的文件链表中查找文件f1，如果有f1，则跳过该网络代理服务器，因为说明该网络代理服务器上已经存放了文件f1；否则先判断该网络代理服务器的剩余存储空间是否足够大来存储文件f1，如果条件满足，则在该网络代理服务器的文件列表中加入f1，跳转到(2.9)；如果剩余的存储空间不满足条件，则需要在该网络代理服务器的文件链表中寻找替换文件，将它们的空间来存储文件f1，按照如下三个步骤进行查找替换文件：a)首先凡是file_List_3中的各项不予考虑；b)凡是文件备份数等于1的文件不予考虑；c)利用动态规划算法，按照点击率、文件大小和备份数选择出最优的替换文件；(2.6)如果找不到替换文件，则跳转到步骤(2.4)，不做处理；(2.7)记录文件f1的文件名在队列queue2；(2.8)并从相应的网络代理服务器上删除选择出来的替换文件，替换上文件f1；(2.9)更新文件链表file_List_0、服务器链表server_List_0的信息；文件f1的增加备份数计数器减1；如果文件f1的增加备份数等于0，则跳转步骤(2.4)；如果不等于0，则将文件f1压入队列queue1，跳转到步骤(2.4)；(2.10)根据队列queue2中的记录进行调整。