一種基于上下文和Web應用的隨機算法

吳之南，楊鑫，凌力

0 引言

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

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

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

1 相關研究

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

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

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

2 基于上下文的隨機算法

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

2.1 算法設計

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

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

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

圖1 內插算法模型

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

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

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

圖2 算法流程圖

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

2.2 算法的應用情景

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

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

圖3 應用情景模型

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

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

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

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

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

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

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

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

3 算法的性能分析

3.1 分析方法

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

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

3.2 仿真結果與分析

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

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

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

4 總結

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

[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.