一种有关网络协作时空均衡的资源访问权控制方法

本发明涉及网络技术领域，具体地说是一种有关网络协作时空均衡的资源访问权控制方法。 

资源访问权控制是交互协作系统用来对共享资源进行管理的一种技术，其核心思想最初来自Turn-Taking，即说话人与听话人交换角的过程，资源访问权是交互协作系统中对共享的多媒体资源访问、操作的临时权限。资源访问权控制的主要任务是预测、避免、解决用户之间对共享资源访问、使用所造成的冲突。资源访问权控制不同于传统的并发控制(Concurrency Control)和访问控制(Access Control)，它是以用户为中心的概念，并支持交互，其目标不仅是让用户能安全地操作共享资源。更重要的是让用户最大程度地进行协作，资源访问权控制可分为控制机制和控制策略两方面。 

控制机制是处理所有用户间的低层控制流和事件同步，反映出的是偏向系统的观点，常见的有令牌申请、令牌传递、时间戳、行为驱动等；控制策略决定了资源访问权的请求与准许、并决定资源访问权分配的顺序，策略较多的反映出用户的观点，同时也依赖于所需交互的程度，但有些策略只适用于特定的机制。 

控制策略从资源访问权分配方式来看，可以分为两类：请求方式和时间周期方式。 

请求方式有立即响应和请求队列。立即响应是指当资源访问权处于空闲状态时，所有想获得资源访问权的用户都可以向资源访问权的控制者(会议主席) 发送请求，但只有一个用户可以获得资源访问权，其他用户的请求不予保存。当获得资源访问权的用户释放了资源访问权，资源访问权再次处于空闲状态时，新一轮的请求竞争又开始了。请求队列则是指系统专门用一个队列来保存用户的请求，当一个用户释放资源访问权后，排在队列最前面的用户就可以获得资源访问权，而不需再次请求。 

时间周期方式是指每个用户从获得资源访问权到释放资源访问权的时间是系统事先定好的，用户不能超时使用，如果超过规定时间，系统会自动将资源访问权分配给下一个用户。 

从资源访问权分配顺序，我们可以把资源访问权控制策略分为单一策略和混合策略，单一策略是指采用单一的排序算法对用户的资源访问优先权进行排序，如：先来先服务，后来先服务，短任务优先，最长时间未得到服务者优先等等。每种算法都有优缺点，一旦选择一种，在系统运行过程中，就无法按照用户的要求进行改变。针对单一策略的局限，提出了一种混合策略，此策略先分别使用多种排序算法对用户进行排序，然后根据用户和交互的需求，灵活设置各个排序算法在总排序算法中的权重，并重新排序。混合策略比单一策略更合理、公平。 

从以上分析可以看出，资源访问权控制策略比较强调资源访问权的公平性，包括资源访问时间长短的公平、长短任务之间的公平，等待时间的公平等。但还没有考虑资源访问权在空间分布上的公平，因此需要一种基于空间公平的资源访问权请求排序算法，并把此算法应用到混合资源访问权控制方法中，创造一种新的基于协作时空均衡的资源访问权控制方法。 

本发明的目的针对基于位置的协作，此协作的一个显著的特点就是人们的组织活动发生在一定的地理区域内(称为协作区域)，在协作过程中，人们分散在协作区域的不同位置，并根据各自位置和协作区域的上下文进行任务分配和任务协调，这就需要协作者及时报告所在位置的上下文变化。如在消防员救火过程中，火场作为消防员的协作区域，为了安全和快速完成任务，需要火场中不同位置的消防员即时报告、交流火情变化，以便相互配合、支援。 

因此，人们在利用协作环境进行信息交互过程中，要考虑资源访问权在空间分布上的公平性，即保证协作区域中不同位置的协作者都有公平的资源访问机会，而不至于出现协作区域有些位置的协作者一直占有资源访问权，其他位置的协作者得不到资源访问的机会。因此，开展基于位置的协作，需要一种基于协作时空均衡的资源访问权控制方法。 

基于协作时空均衡的资源访问权控制方法保障了协作者在协作活动中资源访问的空间公平性，从而保证了协作区域中不同位置的上下文变化得以及时反映，让协作者及时根据最新上下文变化动态地调整协作任务的分配、方案，从而顺利完成协作任务。 

为了实现上述目的，本发明设计一种有关网络协作时空均衡的资源访问权控制方法，其特征在于该方法包括协作区域管理器、资源访问权四叉树管理器、排序策略管理器、资源访问权请求管理器和资源访问权时空分布分析器组成，所述的协作区域管理器负责定义、维护体在协作过程中所处的协作地理范围，所述的资源访问权四叉树管理器负责根据协作区域生成资源访问权四叉树，所述的排序策略管理器负责根据选择的多种资源访问权排序算法实现对协作者资源访问权优先级的排序，所述的资源访问权请求管理器负责处理用户的资源访问权申请，所述的资源访问权时空分析器负责给用户提供资源访问权控制的效 果，此方法为以下步骤： 

a、生成资源访问权四叉树，首先通过协作区域管理器定义协作区域，然后采用区域四叉树的方法，资源访问权四叉树管理器对协作区域进行分割，形成若干子区域，并记录每个子区域历史获得资源访问权的总数，形成一棵反映协作区域内资源访问权在空间分布上的历史分配情况的区域四叉树； 

b、生成资源访问指数，用户存在多个子区域中，因此判断用户资源访问空间优先权不能仅仅根据某个子区域的历史资源访问数，需要综合考虑他所在的每个子区域的历史资源访问总数；同时，资源访问的空间优先权首先要考虑大的子区域之间的空间公平性，然后再考虑小的子区域之间的空间公平性； 

1)资源访问权四叉树管理器从根节点出发，计算每个用户所在的叶子节点； 

2)资源访问权四叉树管理器计算每个用户所在叶子节点的资源访问指数； 

3)当某个用户获得资源访问权后，资源访问权四叉树管理器对他所在的叶子节点以及此叶子节点所有父节点的值加一，表示此区域申请成功的历史资源访问数目增加一次； 

4)根据用户资源访问指数进行排序，排序策略管理器根据用户所在叶子节点的资源访问指数大小对资源访问者进行排序，指数小的说明叶子节点代表的区域的历史资源访问次数是少于其他区域，在此区域申请资源访问权的申请者具有最大优先权，因此在资源访问指数小的区域 内的申请者排在队列前面； 

c、多策略综合排序，排序策略管理器综合其他资源访问权排序方法，得出最后资源访问权排序，方法如下所示 

1)系统中共有N个用户U1，U2...Un，当系统选择策略k(1≤k≤M)时，假设申请队列如下： 

$\underset{k=1}{\overset{m}{\Sigma }}{W}_k=1---\left(1\right)$

我们用 表示U_i在第k种策略队列中的位置，如 用Qseqⁱ表示用户U_i在队列中的最终排序，计算如下： 

${\mathrm{Qseq}}^i=\underset{k=1}{\overset{m}{\Sigma }}{\mathrm{Seq}}_k^i*W_i---\left(2\right)$

2)混合策略由空间公平、先来先服务、后来先服务、短任务优先5种单一策略组成，最长时间未得到服务者优先，它们的权重如下： 

W1＝0.5，W2＝0.2，W3＝0，W4＝0.1，W5＝0.2 

空间公平策略，W1＝0.5，队列如下： 

由于用户同在一个叶子节点所代表的区域里，资源访问指数一样，所以排序并列第二； 

先来先服务，W2＝0.2，队列如下： 

短任务优先，W4＝0.1，队列如下： 

最久等待优先，W5＝0.2，队列如下： 

根据公式(2)，计算如下： 

Qseq1＝3*0.5+1*0.2+4*0.1+1*0.2＝2.3 

Qseq2＝1*0.5+2*0.2+2*0.1+4*0.2＝1.9 

Qseq3＝2*0.5+3*0.2+1*0.1+5*0.2＝2.7 

Qseq4＝5*0.5+4*0.2+3*0.1+6*0.2＝4.8 

Qseq5＝2*0.5+5*0.2+6*0.1+2*0.2＝3 

Qseq6＝4*0.5+6*0.2+5*0.1+3*0.2＝4.3 

根据计算，最后的排队顺序为： 

本发明与现有技术相比，其优点在于：1)首次提出了地域分布不均的用户在协作过程中资源访问权申请的时空均衡性排序规则；2)其次把时空均衡规则与其他规则混合使用，使得各个子区域的资源访问权的获得数目相对均衡，使得在不同子区域的用户拥有相同的资源访问机会反应本子区域的情况；3)最后也降低了各个子区域获得资源访问权的最大等待时间，使得用户可以较快反应个子区域的变化。 

图1为本发明创造具体实施之前的协作区域分割示意图； 

图2为本发明创造的资源访问权四叉树示意图； 

图3为本发明创造具体实施例的测试结果示意图； 

图4为本发明创造的有关协作时空均衡的资源访问控制权方法示意图； 

参照图1，A为协作区域，B为第一次分割，C为第二次分割，D为第三次分割。 

以下结合附图，对本发明创造做近一步详细说明，这种技术对专业人士来说是清楚的。 

第一步，生成资源访问权四叉树 

采用区域四叉树的方法，对协作区域进行分割，形成若干子区域，并记录每个子区域历史获得资源访问权的总数，形成一棵反映协作区域内资源访问权在空间分布上的历史分配情况的区域四叉树，我们称为资源访问权四叉树。 

如图1所示，把协作区域进行三次分割，结果如图1所示。 

如图2所示的资源访问权四叉树：设T(depth，N)为资源访问权四叉树，其中depth为树的深度，N为节点的集合；n(index，level，Value，fn，CN)为资源访问权四叉树的节点，其中Index为节点的索引号，如10、23、330等，level为此节点深度，value为此节点代表的区域中已申请成功的资源访问请求数目；fn为此节点的父节点，CN为此节点的下级子节点集合。 

资源访问权四叉树具有以下性质： 

性质1：非叶子节点所代表的子区域包含此节点所有子节点代表的子区域。 

推论1：在节点n所代表的子区域里的用户，一定在节点n的父节点所代表的子区域里。 

推论2：在协作区域中的用户一定在depth个节点所代表的子区域里。 

性质2：非叶子节点的值等于他下一级子节点的值的总和。 

$N.\mathrm{Value}=\underset{\mathrm{cn}\in \mathrm{CN}}{\Sigma }\mathrm{cn}.\mathrm{Value}$

推论3：节点n的值大于等于他所有子节点的值。 

第二步，生成资源访问指数 

根据推论2，用户存在多个子区域中，因此判断用户资源访问空间优先权不能仅仅根据某个子区域的历史资源访问数，需要综合考虑他所在的每个子区域的历史资源访问总数；同时，资源访问的空间优先权首先要考虑大的子区域之间的空间公平性，然后再考虑小的子区域之间的空间公平性，所以我们设计了资源访问指数，资源访问指数是指能反应不同层次子区域的历史资源访问情况的指数，称为资源访问指数。 

设资源访问权四叉树T的叶子节点l，ki为l的第i层父节点的值，d为树的深度，则叶子节点l所代表的子区域的资源访问指数为： 

p＝k2(d-1)+k3(d-2)...+kd-23+kd-12+l.Value 

即： $p=\underset{i=2}{\overset{d-1}{\Sigma }}{k}_i^{(d-i+1)}+l.\mathrm{Value}$

资源访问指数越高说明在用户所在子区域申请成功的资源访问权的次数就 越多，那么从空间公平性考虑，他申请资源访问权的优先权越低。 

资源访问指数反应了父节点的值对叶子节点的资源访问指数值的影响是随着父节点的层数的增加而减小。判断两个叶子节点的资源访问指数大小只需从上至下判断他们父节点的值的大小，一旦判断出大小，这个大小关系就是资源访问指数的大小关系；反之，继续判断下去。 

第三步，根据用户资源访问指数排序 

根据用户所在叶子节点的资源访问指数大小对资源访问者进行排序，指数小的说明叶子节点代表的区域的历史资源访问次数是少于其他区域，在此区域申请资源访问权的申请者具有最大优先权，因此在资源访问指数小的区域内的申请者排在队列前面。 

例，当前有四个用户U1，U2，U3，U4申请资源访问，根据他们坐标计算出，U1在001号叶子节点，U2在033号叶子节点，U3在300号叶子节点，U4在333号叶子节点，四叶子节点的资源访问指数分别为： 

p001＝6(4-2+1)+3(4-3+1)+1＝118 

p033＝6(4-2+1)+1(4-3+1)+1＝110 

p300＝6(4-2+1)+2(4-3+1)+1＝113 

p333＝6(4-2+1)+3(4-3+1)+0＝117 

因此，对U1，U2，U3，U4的排队为 

  U 2   U 3   U 4   U 1

第四步，综合其他资源访问权排序方法，得出最后资源访问权排序 

假设系统中考虑M种排队策略，并为每一种策略设置权重Wk且权重和为1，见公式(1)系统中共有N个用户U1，U2...Un，当系统选择策略k(1≤k≤M)时，假设申请队列如下： 

$\underset{k=1}{\overset{m}{\Sigma }}{W}_k=1---\left(1\right)$

我们用 表示U_i在第k种策略队列中的位置，如 用Qseqⁱ表示用户U_i在队列中的最终排序，计算如下： 

${\mathrm{Qseq}}^i=\underset{k=1}{\overset{m}{\Sigma }}{\mathrm{Seq}}_k^i*W_i---\left(2\right)$

当系统中某种或某几种策略暂时不被考虑时，它们的权重可以设置为0。 

例如，混合策略由有5种单一策略组成，分别是空间公平、先来先服务、后来先服务、短任务优先，最长时间未得到服务者优先，它们的权重如下： 

W1＝0.5，W2＝0.2，W3＝0，W4＝0.1，W5＝0.2 

空间公平策略，W1＝0.5，队列如下： 

由于用户同在一个叶子节点所代表的区域里，资源访问指数一样，所以排序并列第二。 

先来先服务，W2＝0.2，队列如下： 

短任务优先，W4＝0.1，队列如下： 

最久等待优先，W5＝0.2，队列如下： 

根据公式2，计算如下： 

Qseq1＝3*0.5+1*0.2+4*0.1+1*0.2＝2.3 

Qseq2＝1*0.5+2*0.2+2*0.1+4*0.2＝1.9 

Qseq3＝2*0.5+3*0.2+1*0.1+5*0.2＝2.7 

Qseq4＝5*0.5+4*0.2+3*0.1+6*0.2＝4.8 

Qseq5＝2*0.5+5*0.2+6*0.1+2*0.2＝3 

Qseq6＝4*0.5+6*0.2+5*0.1+3*0.2＝4.3 

根据计算，最后的排队顺序为： 

为了对基于时空均衡的资源访问权控制方法的空间公平性进行验证，我们假设了这样一个场景，10个用户均匀分散在协作区域内开展协作活动，在活动过程中，用户的位置不断变化，我们对协作区域进行两次分割，第一次分割形成0、1、2、3四大区域，再对每个大区域进行分割，一共形成16个小区域，分别标记为00、01、02、03、......33，形成深度为3的资源访问权四叉树，最开始各个节点的值都为0，我们分别采用基于空间公平的混合策略和混合策略分别对资源访问申请进行处理，都包含了立即响应策略，即资源访问权的申请队列长度为1，系统不保存用户的申请，且系统中每个用户的优先级、任务大小都假定相同，在固定的时间内，每个用户都发出100次资源访问请求，每个用户每次资源访问申请时的位置都随机在不同叶子节点中变化，每个用户获得资源访问权后进行操作的时间也是固定的，设定为3秒，我们分别统计每个子区域成功获得资源访问权的总次数以及他们最长的等待时间，图3为测试结果示意图，通过对比数据来看，虽然用户的资源访问申请数目在空间分布上不均衡，但是利用基于空间公平的混合策略使得各个子区域的资源访问权的获得数目相对均衡，使得在不同子区域的用户拥有相同的资源访问机会反应本子区域的情况；同时也降低了各个子区域获得资源访问权的最大等待时间，使得用户可以较快反应个子区域的变化。 

此方法用于基于位置感知的协作服务平台上，其实现的功能结构如图4所示，由协作区域管理器、资源访问权四叉树管理器、排序策略管理器、资源访 问权请求管理和资源访问权时空分布分析器组成。 

使用之前必须先通过协作区域管理器定义协作区域，定义完毕后系统提交至资源访问权四叉树管理器，四叉树管理器根据协作区域的范围和资源访问权四叉树的规则动态生成资源访问权四叉树，同时根据资源访问指数规则，初始化每个协作者的资源访问指数，并进行资源访问权的优先级排序。 

在协作过程中，协作者通过资源访问权请求管理器申请资源访问权，请求管理器收到申请后转交给排序策略管理器，排序策略管理器根据当前协作者位置重新计算所在区域的资源访问指数，并对协作者当前的资源访问权优先级进行排序，同时再综合考虑其他排序规则给出最后的申请结果，批准还是拒绝。资源访问权请求管理器再把这个结果转交给用户。 

为了实时动态查看资源访问权分配的时空均衡性，用户可以通过资源访问权时空分布分析器提供的时空均衡指数、历史资源访问权分布专题地图和历史资源访问权分布报表了解。时空均衡指数反映协作区域资源访问权在历史空间分布的公平性，如果绝对公平，那么时空均衡指数的值为0，如果绝对不公平，那么时空指数就是无穷大；历史资源访问权分布专题地图是通过电子地图把协作区域中资源访问权申请数、申请成功数图形化显示出来；历史资源访问权分布报表是通过饼图等方式显示不同区域的历史资源访问权申请数、申请成功数。 

通过实际的对比分析，如果不采用此控制方法，在3小时的测试时间内，以每十分钟为单位，时空均衡指数的增长基本上成抛物线形式，3小时过后，时空均衡指数达到3023，而参与测试的人员反映有的一直可以很容易获得资源访问权，有的很少获得资源访问权；而采用此控制方法，在3小时的测试时间内， 以每十分钟为单位，时空均衡指数的增长较为平稳，3小时过后，时空均衡指数达到124，而参与测试的人员反映均有机会获得资源访问权。