吳之南，楊鑫，凌力

0 引言

隨著通信技術(shù)的不斷發(fā)展，包括互聯(lián)網(wǎng)在內(nèi)的各種通訊網(wǎng)絡(luò)的帶寬越來越大，這一變化使網(wǎng)絡(luò)提供各種復(fù)雜與基于大數(shù)據(jù)的服務(wù)成為了可能。因此近年來，基于 Web的應(yīng)用模式一直是互聯(lián)網(wǎng)行業(yè)討論的重點，各類 Web應(yīng)用層出不窮?；谧烂鏋g覽器的 Web應(yīng)用在其中占有很大比例。瀏覽器模型的優(yōu)勢在于它可以實現(xiàn)許多原本屬于操作系統(tǒng)的功能和功能復(fù)雜的應(yīng)用。隨著網(wǎng)頁技術(shù)標準的不斷完善與改進,網(wǎng)頁技術(shù)可以像許多高級語言那樣實現(xiàn)很多復(fù)雜的需求與應(yīng)用，比如網(wǎng)頁游戲。因此許多廠商也順勢開發(fā)了以主流Web技術(shù)和標準為基礎(chǔ)的框架。

新一代的Web技術(shù)標準包括HTML5，CSS3等，結(jié)合主流的網(wǎng)頁腳本語言 Javascript，不但可以做出外觀精彩的頁面，還可以通過用戶訪問的 Web服務(wù)來獲取帶有語義的上下文信息。隨著移動終端的普及和終端上傳感器種類的增加，這類上下文信息的數(shù)據(jù)量將更大，內(nèi)容將更豐富，這使得Web應(yīng)用可以方便的提供許多個性化的服務(wù)[1]，比如基于地點的服務(wù)（LBS）。

在 Web服務(wù)中，隨機算法是必不可少的。筆者設(shè)計了一種有別于傳統(tǒng)設(shè)計的，基于上下文與 Web應(yīng)用的隨機算法，它以用戶與應(yīng)用的UI交互時所產(chǎn)生的點擊信息為隨機因子。經(jīng)過測試可知，這種算法能產(chǎn)生正態(tài)分布的隨機數(shù)并且在一類情景下有良好的用戶體驗。

1 相關(guān)研究

在 Karp的綜述文章中[2]，我們可以看到幾乎所有隨機算法核心所通用的原則，包括阻撓對手，隨機采樣，證據(jù)豐度，指紋哈希，快速馬爾科夫鏈等等。我們可以看到傳統(tǒng)的隨機算法往往是在沒有上下文的基礎(chǔ)下實現(xiàn)的。

實際上，在 Web服務(wù)中，許多上下文信息是具有隨機性的，可以利用它們設(shè)計隨機算法，這就要求 Web應(yīng)用可以方便的獲得上下文信息。Xiuguo Zhang等人提出過一種有利于利用上下文提供Web服務(wù)的網(wǎng)絡(luò)模型[3]。而在具體應(yīng)用方面，喬秀全等人提出過一種基于用戶上下文的信任度計算方法[4]。

本文所提到的隨機算法就是一種基于隨機采樣并且以隨機上下文為隨機因子的算法。

2 基于上下文的隨機算法

這部分就將介紹這種基于上下文的隨機算法。首先將說明算法如何獲取隨機因子和算法的設(shè)計，然后介紹一種可以應(yīng)用此算法的具體情景，最后給出算法的具體實現(xiàn)代碼并且對其做出分析與說明。

2.1 算法設(shè)計

由于在用戶與應(yīng)用交互的過程中，用戶發(fā)出的交互請求的時機，比如點擊UI界面的時機是隨機的，所以這是一種隨機的上下文信息。該算法就以此為隨機因子。

當(dāng)采用此算法的系統(tǒng)接收到用戶的交互請求時，或者說當(dāng)用戶點擊一個應(yīng)用程序系統(tǒng)的UI界面時，應(yīng)用程序記錄下此時的時間，以此作為點擊的上下文信息。并且將此上下文加入到一個預(yù)先定義好的隊列S。隊列S是一個記錄上下文信息并且長度固定的隊列。在加入新的上下文時，若隊列S未滿，則將此新生成的上下文信息作為序列記錄，添加到隊首，若隊列S已滿則刪除隊尾記錄，再將此新生成的上下文添加到隊首。

然后我們將根據(jù)隊列中的每條上下文記錄所記錄的時間信息為周期，生成一系列周期脈沖序列。如果隊列S的長度定義為n，那么就將有n個周期脈沖序列。如果將n個周期事件脈沖序列內(nèi)插會得到一個偽隨機的脈沖序列。以3個周期脈沖序列為例合成一個脈沖序列如圖1所示：

圖1 內(nèi)插算法模型

由圖1可見，3個周期脈沖序列的周期Tn各不相同，它們各自的第一個脈沖產(chǎn)生時間也不相同。由3個周期序列內(nèi)插后的總序列實際上是一個偽隨機序列，因為只要考察的周期足夠長，總序列仍是一個周期序列并且這個周期序列的周期取決于合成它的序列的周期與它們的第一個脈沖產(chǎn)生的時間。為了增加隨機性，可以使用盡可能多的周期脈沖序列來合成總隨機序列，也即隊列S應(yīng)該盡可能長。

在此模型中，我們使用單個脈沖來表示一個具體事件f的發(fā)生，那么一系列f就是一串事件脈沖，也就是關(guān)于時間的事件f的脈沖序列。那么算法的目標是實現(xiàn)一個時間間隔隨機的脈沖序列。這樣一來，f這一重復(fù)發(fā)生的事件的概率就是隨機的。而各個脈沖之間的間隔時間值就是該算法生成的隨機數(shù)。

該算法的流程圖如圖2所示：

圖2 算法流程圖

由圖2可見，隨著用戶與系統(tǒng)的不停交互，每次交互都會更新隊列S，所以合成總序列的周期序列總是不停地在更新。在大部分由作為用戶的人參與的交互場景中，其交互行為的發(fā)生是非周期的，即便有一個穩(wěn)定的平均交互發(fā)生頻率，比如用戶在閱讀電子書籍時，翻頁的交互行為就是頻率相對穩(wěn)定的，但各個交互行為發(fā)生的時間差往往是隨機的。當(dāng)交互發(fā)生時，系統(tǒng)利用當(dāng)前行為的發(fā)生時刻與上一個交互行為的發(fā)生時刻的差值，來決定生成的周期序列的周期Tn，這樣各個周期序列的周期與首脈沖發(fā)生時刻都是隨機的并且合成總序列的各個周期序列也是在不停更換的。本算法將用戶行為這一隨機因子加入到算法中來，并且使算法在實際應(yīng)用的層面上成為了隨機算法。

2.2 算法的應(yīng)用情景

本節(jié)介紹一種適用于此算法的具體情景。

在 Web應(yīng)用經(jīng)常有產(chǎn)生隨機視覺效果的需求，比如在模擬一個天空的場景時，要求雪花隨機的出現(xiàn)。再比如一種打鼴鼠游戲場景，這種場景要求鼴鼠隨機的出現(xiàn)在某個洞中，玩家需要及時反應(yīng)擊打鼴鼠來得分。在這些情景中，我們可以將發(fā)生的事件f抽象成：一個圖像隨機的出現(xiàn)在屏幕的一個區(qū)域中或者說一個圖片在一個位置消失然后出現(xiàn)在另一個位置。此種情景的簡單模型圖如圖3所示：

圖3 應(yīng)用情景模型

由圖3可見，一個大區(qū)域被分為四個小區(qū)域?，F(xiàn)假設(shè)要求一張圖片隨機地出現(xiàn)在四個區(qū)域的任意一個中。將f定義為“按照圖中箭頭方向移動一個區(qū)域”，比如當(dāng)此刻圖片在1區(qū)域，那么當(dāng)f發(fā)生時，圖片會從1區(qū)域消失，并在2區(qū)域出現(xiàn)。對比上一節(jié)圖 1提到的內(nèi)插算法模型，每次事件f發(fā)生，就表示產(chǎn)生了一個脈沖沖擊。

當(dāng)算法應(yīng)用于在此類情景中時，還會獲得一種額外的隨機性，下面將對此進行解釋。當(dāng)兩個f的間隔非常小時，也就是兩個事件脈沖時間間隔非常近時，人眼會觀察不到這個順序移動的過程，比如當(dāng)圖片從區(qū)域1來到區(qū)域2后，立刻又觸發(fā)了一次f，使圖片從區(qū)域2來到了區(qū)域3，由于兩次f的間隔非常短，在用戶看來，圖片是從區(qū)域1直接移動到區(qū)域3的。這樣，即便圖片在四個區(qū)域中循環(huán)移動，在用戶看來整個移動過程也是隨機的。在下文的性能分析中采用的測試環(huán)境就是基于此類情景的。

由于在這類應(yīng)用中，會忽略兩個或多個間隔較近的事件脈沖，而這種情況是很常見的，所以當(dāng)算法應(yīng)用于此類情景中時，會給本隨機算法又增加這一層額外的隨機性。

2.3 算法的具體實現(xiàn)

本節(jié)介紹如何使用前端技術(shù)具體實現(xiàn)算法并且給出相關(guān)的JS代碼。

在HTML DOM中，有一個定時器方法setInterval( )，它可按照指定的周期來反復(fù)調(diào)用預(yù)先定義好的函數(shù)或計算表達式，直到另一個方法setInterval( )被調(diào)用或瀏覽器窗口被關(guān)閉。如果將一個事件的發(fā)生看作一個具體的函數(shù)被調(diào)用，那么方法setInterval( )產(chǎn)生的就是一周期事件脈沖序列。本算法以此方法為基礎(chǔ)，利用它生成的各個周期事件脈沖序列來合成總隨機脈沖序列。需要注意的是，使用這個函數(shù)有一定的安全風(fēng)險，Russo等人在相關(guān)文章中對其安全性進行了考察[5]。

當(dāng)用戶在與系統(tǒng)的交互過程中產(chǎn)生上下文時，調(diào)用下述函數(shù)：

上述代碼中，假設(shè)隊列 的長度為10。sequence就是隊列S，adjust方法用來在周期脈沖序列周期period過小時調(diào)整它變大，因為過小的周期在上節(jié)所述的應(yīng)用情景中，人眼是辨別不出來的，只會感受到圖片在頻繁的閃爍。函數(shù)f就是所要執(zhí)行的動作也就是上節(jié)描述情景中的事件，具體來說就是圖片的位置轉(zhuǎn)移。

3 算法的性能分析

3.1 分析方法

本測試采用IE8瀏覽器作為測試環(huán)境。編寫了一個動態(tài)網(wǎng)頁，使一張圖片隨機的出現(xiàn)在網(wǎng)頁上的任何位置。在測試的過程中，要求測試者盡可能的點擊出現(xiàn)的圖片，而每次點擊成功會產(chǎn)生一個新的用戶上下文，從而能夠計算出此次點擊與上次點擊的時間差，于是便能夠更新隊列S。

與此同時，統(tǒng)計出時間間隔與樣本數(shù)量關(guān)系并且利用HTML5的繪圖功能在瀏覽器中分別做出散粒圖與柱狀圖。在測試中，樣本數(shù)量取10000個，也即事件脈沖發(fā)生10000次。

3.2 仿真結(jié)果與分析

本文提出的算法使系統(tǒng)產(chǎn)生了一種發(fā)生時間間隔呈正態(tài)分布的隨機行為，也就是產(chǎn)生了正態(tài)分布的隨機數(shù)如圖4所示：

圖4 正態(tài)分布隨即圖

由于內(nèi)插的周期脈沖序列周期有最大值，所以時間間隔分布呈正態(tài)的是很自然的。同時由散列圖可以看出樣本隨時間的取值是隨機分布的，正態(tài)概率密度是隨時間穩(wěn)定的。

4 總結(jié)

本文提出了一種基于上下文的隨機算法，該算法適用于有用戶交互的情景，它為系統(tǒng)產(chǎn)生某種隨機行為模式的需求提供了一種解決方案。本文還介紹了一種適用于此算法的具體情景。在此情景中該算法提供了一種產(chǎn)生隨機視覺效果的解決方案。經(jīng)過仿真分析可知，本算法可以產(chǎn)生一種正態(tài)分布的隨機數(shù)，為有效利用含有語義的上下文提供了一種新思路。并提出了一種有別于傳統(tǒng)隨機算法的設(shè)計思想。

[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]喬秀全 楊春 李曉峰 陳俊亮 社交網(wǎng)絡(luò)服務(wù)中一種基于上下文的信任度計算方法[J]，計算機學(xué)報，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.