一种基于上下文和Web应用的随机算法

吴之南，杨鑫，凌力

0 引言

随着通信技术的不断发展，包括互联网在内的各种通讯网络的带宽越来越大，这一变化使网络提供各种复杂与基于大数据的服务成为了可能。因此近年来，基于 Web的应用模式一直是互联网行业讨论的重点，各类 Web应用层出不穷。基于桌面浏览器的 Web应用在其中占有很大比例。浏览器模型的优势在于它可以实现许多原本属于操作系统的功能和功能复杂的应用。随着网页技术标准的不断完善与改进,网页技术可以像许多高级语言那样实现很多复杂的需求与应用，比如网页游戏。因此许多厂商也顺势开发了以主流Web技术和标准为基础的框架。

新一代的Web技术标准包括HTML5，CSS3等，结合主流的网页脚本语言 Javascript，不但可以做出外观精彩的页面，还可以通过用户访问的 Web服务来获取带有语义的上下文信息。随着移动终端的普及和终端上传感器种类的增加，这类上下文信息的数据量将更大，内容将更丰富，这使得Web应用可以方便的提供许多个性化的服务[1]，比如基于地点的服务（LBS）。

在 Web服务中，随机算法是必不可少的。笔者设计了一种有别于传统设计的，基于上下文与 Web应用的随机算法，它以用户与应用的UI交互时所产生的点击信息为随机因子。经过测试可知，这种算法能产生正态分布的随机数并且在一类情景下有良好的用户体验。

1 相关研究

在 Karp的综述文章中[2]，我们可以看到几乎所有随机算法核心所通用的原则，包括阻挠对手，随机采样，证据丰度，指纹哈希，快速马尔科夫链等等。我们可以看到传统的随机算法往往是在没有上下文的基础下实现的。

实际上，在 Web服务中，许多上下文信息是具有随机性的，可以利用它们设计随机算法，这就要求 Web应用可以方便的获得上下文信息。Xiuguo Zhang等人提出过一种有利于利用上下文提供Web服务的网络模型[3]。而在具体应用方面，乔秀全等人提出过一种基于用户上下文的信任度计算方法[4]。

本文所提到的随机算法就是一种基于随机采样并且以随机上下文为随机因子的算法。

2 基于上下文的随机算法

这部分就将介绍这种基于上下文的随机算法。首先将说明算法如何获取随机因子和算法的设计，然后介绍一种可以应用此算法的具体情景，最后给出算法的具体实现代码并且对其做出分析与说明。

2.1 算法设计

由于在用户与应用交互的过程中，用户发出的交互请求的时机，比如点击UI界面的时机是随机的，所以这是一种随机的上下文信息。该算法就以此为随机因子。

当采用此算法的系统接收到用户的交互请求时，或者说当用户点击一个应用程序系统的UI界面时，应用程序记录下此时的时间，以此作为点击的上下文信息。并且将此上下文加入到一个预先定义好的队列S。队列S是一个记录上下文信息并且长度固定的队列。在加入新的上下文时，若队列S未满，则将此新生成的上下文信息作为序列记录，添加到队首，若队列S已满则删除队尾记录，再将此新生成的上下文添加到队首。

然后我们将根据队列中的每条上下文记录所记录的时间信息为周期，生成一系列周期脉冲序列。如果队列S的长度定义为n，那么就将有n个周期脉冲序列。如果将n个周期事件脉冲序列内插会得到一个伪随机的脉冲序列。以3个周期脉冲序列为例合成一个脉冲序列如图1所示：

图1 内插算法模型

由图1可见，3个周期脉冲序列的周期Tn各不相同，它们各自的第一个脉冲产生时间也不相同。由3个周期序列内插后的总序列实际上是一个伪随机序列，因为只要考察的周期足够长，总序列仍是一个周期序列并且这个周期序列的周期取决于合成它的序列的周期与它们的第一个脉冲产生的时间。为了增加随机性，可以使用尽可能多的周期脉冲序列来合成总随机序列，也即队列S应该尽可能长。

在此模型中，我们使用单个脉冲来表示一个具体事件f的发生，那么一系列f就是一串事件脉冲，也就是关于时间的事件f的脉冲序列。那么算法的目标是实现一个时间间隔随机的脉冲序列。这样一来，f这一重复发生的事件的概率就是随机的。而各个脉冲之间的间隔时间值就是该算法生成的随机数。

该算法的流程图如图2所示：

图2 算法流程图

由图2可见，随着用户与系统的不停交互，每次交互都会更新队列S，所以合成总序列的周期序列总是不停地在更新。在大部分由作为用户的人参与的交互场景中，其交互行为的发生是非周期的，即便有一个稳定的平均交互发生频率，比如用户在阅读电子书籍时，翻页的交互行为就是频率相对稳定的，但各个交互行为发生的时间差往往是随机的。当交互发生时，系统利用当前行为的发生时刻与上一个交互行为的发生时刻的差值，来决定生成的周期序列的周期Tn，这样各个周期序列的周期与首脉冲发生时刻都是随机的并且合成总序列的各个周期序列也是在不停更换的。本算法将用户行为这一随机因子加入到算法中来，并且使算法在实际应用的层面上成为了随机算法。

2.2 算法的应用情景

本节介绍一种适用于此算法的具体情景。

在 Web应用经常有产生随机视觉效果的需求，比如在模拟一个天空的场景时，要求雪花随机的出现。再比如一种打鼹鼠游戏场景，这种场景要求鼹鼠随机的出现在某个洞中，玩家需要及时反应击打鼹鼠来得分。在这些情景中，我们可以将发生的事件f抽象成：一个图像随机的出现在屏幕的一个区域中或者说一个图片在一个位置消失然后出现在另一个位置。此种情景的简单模型图如图3所示：

图3 应用情景模型

由图3可见，一个大区域被分为四个小区域。现假设要求一张图片随机地出现在四个区域的任意一个中。将f定义为“按照图中箭头方向移动一个区域”，比如当此刻图片在1区域，那么当f发生时，图片会从1区域消失，并在2区域出现。对比上一节图 1提到的内插算法模型，每次事件f发生，就表示产生了一个脉冲冲击。

当算法应用于在此类情景中时，还会获得一种额外的随机性，下面将对此进行解释。当两个f的间隔非常小时，也就是两个事件脉冲时间间隔非常近时，人眼会观察不到这个顺序移动的过程，比如当图片从区域1来到区域2后，立刻又触发了一次f，使图片从区域2来到了区域3，由于两次f的间隔非常短，在用户看来，图片是从区域1直接移动到区域3的。这样，即便图片在四个区域中循环移动，在用户看来整个移动过程也是随机的。在下文的性能分析中采用的测试环境就是基于此类情景的。

由于在这类应用中，会忽略两个或多个间隔较近的事件脉冲，而这种情况是很常见的，所以当算法应用于此类情景中时，会给本随机算法又增加这一层额外的随机性。

2.3 算法的具体实现

本节介绍如何使用前端技术具体实现算法并且给出相关的JS代码。

在HTML DOM中，有一个定时器方法setInterval( )，它可按照指定的周期来反复调用预先定义好的函数或计算表达式，直到另一个方法setInterval( )被调用或浏览器窗口被关闭。如果将一个事件的发生看作一个具体的函数被调用，那么方法setInterval( )产生的就是一周期事件脉冲序列。本算法以此方法为基础，利用它生成的各个周期事件脉冲序列来合成总随机脉冲序列。需要注意的是，使用这个函数有一定的安全风险，Russo等人在相关文章中对其安全性进行了考察[5]。

当用户在与系统的交互过程中产生上下文时，调用下述函数：

上述代码中，假设队列 的长度为10。sequence就是队列S，adjust方法用来在周期脉冲序列周期period过小时调整它变大，因为过小的周期在上节所述的应用情景中，人眼是辨别不出来的，只会感受到图片在频繁的闪烁。函数f就是所要执行的动作也就是上节描述情景中的事件，具体来说就是图片的位置转移。

3 算法的性能分析

3.1 分析方法

本测试采用IE8浏览器作为测试环境。编写了一个动态网页，使一张图片随机的出现在网页上的任何位置。在测试的过程中，要求测试者尽可能的点击出现的图片，而每次点击成功会产生一个新的用户上下文，从而能够计算出此次点击与上次点击的时间差，于是便能够更新队列S。

与此同时，统计出时间间隔与样本数量关系并且利用HTML5的绘图功能在浏览器中分别做出散粒图与柱状图。在测试中，样本数量取10000个，也即事件脉冲发生10000次。

3.2 仿真结果与分析

本文提出的算法使系统产生了一种发生时间间隔呈正态分布的随机行为，也就是产生了正态分布的随机数如图4所示：

图4 正态分布随即图

由于内插的周期脉冲序列周期有最大值，所以时间间隔分布呈正态的是很自然的。同时由散列图可以看出样本随时间的取值是随机分布的，正态概率密度是随时间稳定的。

4 总结

本文提出了一种基于上下文的随机算法，该算法适用于有用户交互的情景，它为系统产生某种随机行为模式的需求提供了一种解决方案。本文还介绍了一种适用于此算法的具体情景。在此情景中该算法提供了一种产生随机视觉效果的解决方案。经过仿真分析可知，本算法可以产生一种正态分布的随机数，为有效利用含有语义的上下文提供了一种新思路。并提出了一种有别于传统随机算法的设计思想。

[1]CharithPerera, Student Member, Arkady Zaslavsky,Member, Peter Christen, and DimitriosGeorgakopoulos,“Context Aware Computing for The Internet of Things A Survey”[J]IEEE Communication Surveys & Tutorials,Vol.16, No.1, 414-454, 2014.

[2]R.M.Karp, “An introduction to randomized algorithms”[C]Discrete Applied Mathematic, 34, 165-201,1991.

[3]Xiuguo Zhang, “A Novel Process Network Model for Interacting Context-Aware Web Services”[J]IEEE Services Computing, Vol.6, No.3, 344-357,2013

[4]乔秀全 杨春 李晓峰 陈俊亮 社交网络服务中一种基于上下文的信任度计算方法[J]，计算机学报，2011.34(12), 2403-2413

[5]Alejandro Russo, Andrei Sabelfeld,“Securing Timeout Instruction in Web Application”[J]IEEE Computer Security Foundations Symposium, 22, 92-105, 2009.