[发明专利]一种多服务器DVE系统中保持连通性的动态匹配方法

摘要

本发明公开了一种多服务器DVE系统中保持连通性的动态匹配方法，步骤包括：预先将虚拟环境的二维空间根据服务器数量划分为多个无孔的连通区域，每个区域都由具有相同大小的正方形的区块组成；将划分得到的连通区域分别指派给不同的服务器；在多服务器DVE系统运行期间，各个服务器周期性检查自身负载情况，如果负载超出预设的负载阈值，则启动动态匹配过程，根据区域连通性检查法则和区块满意度优化原则对所分配区域的备选迁移区块进行选择，并根据选择结果将相应区块发送给维护相邻区域的服务器。本发明匹配过程速度快、效果好，能够有效保证各服务器维护区域的连通性，能够保障多服务器DVE系统虚拟世界完整性要素、用户真实体验好、适用性好。

主权项

1.一种多服务器DVE系统中保持连通性的动态匹配方法，其特征在于步骤包括：1）在多服务器DVE系统运行前，预先将多服务器DVE系统的虚拟环境的二维空间根据服务器数量划分为多个无孔的连通区域，所述多服务器DVE系统是指多服务器分布式虚拟环境DVE系统，每个区域都由具有相同大小的正方形的区块组成，所述区块为负载均衡过程中不同服务器之间进行二维空间迁移的最小单位；所述连通区域指组成该区域的所有区块可组成强连通子图，对于该区域中的任何两个区块，都可以在该区域内找到一条路径连接这两个区块，且该路径只包括水平和垂直两个方向的连接线，并不包括45度角的斜线；所述无孔的连通区域是指该区域内部不包含不属于该区域的区块，描述为该连通区域的补充区域也是连通区域，所述该连通区域的补充区域是指虚拟空间中除去该连通区域的之外其他区块共同组成的区域；将划分得到的多个无孔的连通区域分别指派给不同的服务器，每个服务器负责维护所分配区域及其上运行的客户端实体；2）在多服务器DVE系统运行期间，各个服务器周期性地检查自身的负载情况，如果负载超出预设的负载阈值，则启动动态匹配过程，根据区域连通性检查法则和区块满意度优化原则对所分配区域的备选迁移区块进行选择，并根据选择结果将相应区块发送给维护相邻区域的服务器；所述步骤2）的详细步骤包括：2.1）在多服务器DVE系统运行期间，各个服务器周期性地检查自己的负载情况，判断自身的负载是否超出预设的负载阈值，如果自身的负载超出预设的负载阈值，则跳转执行步骤2.2），否则在下一个周期时跳转执行步骤2.1）；2.2）当前服务器向在多服务器DVE系统虚拟环境的二维空间中维护相邻区域的服务器发送区块迁移请求，收到区块迁移请求的服务器根据自身目前负载情况给予反馈，若目前处于低负载情况则反馈可以迁移，否则反馈无法迁移；2.3）当前服务器接收来自其他服务器的反馈，若其他服务器均反馈无法接收当前服务器的迁移请求，则本周期的动态匹配过程中止，在下一周期跳转执行步骤2.1），否则当前服务器从自身维护的区域中选择备选迁移区块准备进行动态匹配；2.4）当前服务器根据区域连通性检查法则对备选迁移区块进行筛选，保留可以保持迁出与迁入服务器的无孔连通性的区块；2.5）当前服务器根据区块满意度优化原则对备选迁移区块进行排序；2.6）当前服务器根据排序结果选择区块发送给反馈可以进行迁移的服务器实施迁移；2.7）当前服务器判断自身的负载情况是否仍然超出预设的负载阈值，如果仍然超出预设的负载阈值，则跳转执行步骤2.4）；否则迁移过程结束，在下一个周期跳转执行步骤2.1）；所述步骤2.4）的详细步骤包括：2.4.1）对备选迁移区块和待迁出区域按照区块迁出区域的无孔连通性保持原则进行检查，如果可以保持，则在可迁移区块列表中保留该区块，否则剔除该区块；2.4.2）对备选迁移区块和待迁入区域的补充区域按照区块迁出区域的无孔连通性保持原则进行检查，如果可以保持，则在可迁移区块列表中保留该区块，否则剔除该区块；所述区块迁出区域的无孔连通性保持原则包括下述规则：①如果区块与区域的交界线有一个，则该区块迁出该区域不会影响区域的无孔连通性；②如果区块与区域的交界线有两个、且交界线位于区块相对的两侧，则该区块迁出该区域会影响区域的无孔连通性；③如果区块与区域的交界线有两个、且交界线位于区块相邻的两侧，当该区块在相邻交界线的对角区块也属于该区域时，则该区块迁出该区域不会影响区域的无孔连通性，否则当该区块在相邻交界线的对角区块不属于该区域时，则该区块迁出该区域会影响区域的无孔连通性，所述相邻交界线的对角区块是指与该区块相邻的两个区块也都相邻的区块；④如果区块与区域的交界线有三个，当该区块在两组相邻交界线的对角区块都属于该区域时，则该区块迁出该区域不会影响区域的无孔连通性，否则当该区块在两组相邻交界线的对角区块不都属于该区域时，则该区块迁出该区域会影响区域的无孔连通性，所述相邻交界线的对角区块是指与该区块相邻的两组区块分别相邻的两个区块；⑤如果区块与区域的交界线有四个，则该区块迁出该区域会影响区域的无孔连通性。