[發明專利]用于網絡空間信息服務系統的空間信息集群緩存預取方法

有效

• 申請號: 201110242750.6
• 申請日: 2011-08-23
• 公開（公告）號: CN102355490A
• 公開（公告）日: 2012-02-15
• 發明（設計）人: 李銳;徐正全;郭銳
• 申請（專利權）人: 武漢大學
• 主分類號: H04L29/08
• 分類號: H04L29/08
• 代理公司: 武漢科皓知識產權代理事務所(特殊普通合伙) 42222
• 代理人: 張火春

1.一種用于網絡空間信息服務系統的空間信息集群緩存預取方法，其特征在于：包括以下步驟，

步驟1，選取系統中訪問次數排名前20%的瓦片作為用戶瀏覽窗口的中心點，構成中心點集合{????????????????????????????????????????????????,…,}，其中表示系統中訪問次數排名前20%的瓦片的數目；基于齊普夫分布規律，得到系統中訪問次數排名前20%的瓦片的訪問概率…，其中P_i＝C?/?，i取值為1～n，C為歸一化常數；

步驟2，為用戶瀏覽窗口的中心點建立基本Markov模型，具體實現如下，

設在地形瀏覽過程中，用戶瀏覽窗口的中心點轉移是一個Markov過程，則中心點轉移構成一個隨機變量的取值序列，且該取值序列滿足Markov性，用三元組MC?=?<X、A、λ>表示該取值序列，

其中，離散隨機變量X標識用戶瀏覽窗口的中心點集合{,…,}；初始狀態分布λ為齊普夫分布，λ={…}；轉移概率矩陣A中的每一項?表示由中心點集合內的某一中心點轉移到另一中心點的訪問轉移概率；?

A=()=????????

所述訪問轉移概率的求取方式為，定義由某瓦片轉移到與該瓦片相鄰的瓦片的訪問轉移概率為1步轉移概率，確定中心點轉移到中心點的所有轉移路徑，對所有轉移路徑經過的1步轉移概率，在條件概率下進行疊加得到訪問轉移概率；所述1步轉移概率的求取方式為，對瓦片周邊的四塊同層相鄰瓦片和上下層相鄰瓦片的訪問概率進行歸一化，獲取瓦片至周邊瓦片的1步轉移概率；

步驟3，根據步驟2所建立的基本Markov模型預測地形瀏覽過程中中心點集合{…}內各中心點的訪問轉移概率，再分別根據各中心點的訪問轉移概率預測相應用戶瀏覽窗口包含的瓦片訪問轉移概率；

步驟4，根據中心點集合{,…,}和步驟3所得瓦片訪問轉移概率，選擇訪問轉移概率高的瓦片形成緩存預取瓦片集合；

步驟5，對步驟4所得緩存預取瓦片集合中的瓦片進行集群緩存分布。

2.根據權利要求1所述用于網絡空間信息服務系統的空間信息集群緩存預取方法，其特征在于：步驟4具體實現方式如下，

首先，比較預先設定的閾值和訪問概率…，將中心點集合{,…,}內訪問概率大于閾值的中心點放入緩存預取瓦片集合T，這些中心點的瓦片大小之和記為Q1；

然后，比較預先設定的閾值和步驟3所得的瓦片訪問轉移概率，將瓦片訪問轉移概率大于閾值的瓦片存入集合Tp；

最后，對集合Tp中的瓦片按瓦片訪問轉移概率由大到小進行排列，根據網絡空間信息服務系統中的剩余緩存容量Q2，選取集合Tp中的前W個瓦片放入緩存預取瓦片集合T，其中W=剩余緩存容量/瓦片大小，剩余緩存容量Q2=Q-Q1，Q表示網絡空間信息服務系統提供的集群緩存大小。

3.根據權利要求1或2所述用于網絡空間信息服務系統的空間信息集群緩存預取方法，其特征在于：步驟5中所述進行集群緩存分布的具體方式如下，

假設網絡空間信息服務系統中的一組集群緩存服務器為S={S_i|1≤i≤L}，Sp(S_i)為集群緩存服務器Si當前的所有緩存瓦片的訪問概率和，初始值都為0，Cs(S_i)為集群緩存服務器的S_i剩余緩存大小，Min(S)為這組集群緩存服務器S中當前Sp(S_i)最小的集群緩存服務器，緩存預取瓦片集合為T={T_i|1≤i≤N}，其中瓦片T_i的大小為TS(T_i),?訪問概率為P(T_i)；

對緩存預取瓦片集合T中的每個瓦片T_i依次進行放置，放置方式為將當前的集群緩存服務器Min(S)記為集群緩存服務器s，如果此時Cs(s)>T_S(T_i)，緩存瓦片T_i到集群緩存服務器s；改變集群緩存服務器s的剩余緩存大小Cs(s)=Cs(s)-T_S(T_i)；改變集群緩存服務器s所有緩存瓦片的訪問概率和Sp(s)=Sp(s)?+?P(T_i)。