數據緩存放置系統及數據緩存的方法

2023-09-18 23:30:10

專利名稱：數據緩存放置系統及數據緩存的方法
技術領域：
本發明涉及網絡技術，尤其涉及一種數據緩存放置系統及數據緩存的方法。
背景技術：
基於Internet 的無線自組網(Internet-based Mobile Ad Hoc Network, IMANET)能夠使移動用戶通過多跳的方式訪問到Internet上的資源，是一種非常方便的數據訪問方式。此外，無線傳感器網絡(WSN)在近幾年的應用越來越廣泛，應用領域包括環境監測、移動多媒體、物流管理、交通控制、目標跟蹤以及智能家居等軍用或民用領域。因為無線網絡中現在存在的問題，比如無線通信帶寬資源緊張，行動裝置存儲容量有限，行動網路連結不穩定，以及行動裝置自身的能量有限，因此為了提高數據訪問的效率，尋找一種能夠共享數據的方法，就顯得非常重要。通過網絡數據緩存的方法(Data Caching)的方法可以有效的提高的數據訪問效率。這種方法主要是採取數據源將數據拷貝放置在緩存結點上，其他結點可以通過訪問數據拷貝，而不是去數據源訪問數據來節省時間，節約訪問開銷。核心的問題是，如何在網絡中選擇緩存結點來放置數據拷貝。因為放置拷貝意味要求數據源能夠及時的將最新版本的數據傳輸給緩存結點，也要產生新的開銷。但是，傳統的方法都假設了每一跳的訪問延遲是一樣的，但是在實際的無線網絡中，無線信號在空氣中傳播的時候，所有結點都共享了空氣這唯一的介質，在同時傳輸數據的時候會產生競爭，目前常用的無線通信協議都有回退機制來調整這種數據傳輸。因此，在衡量緩存數據訪問開銷的時候，現有的方法沒有考慮無線信道競爭的特點，從而達不到理論分析的效果，反而會影響數據傳輸的效率。在數據緩存問題中，如何在任意網絡拓撲結構中放置緩存拷貝以達到數據更新和用戶訪問數據總開銷最小，即緩存放置問題(Cache Placement Problem),是最為關鍵的一個問題。該問題和圖論中的經典問題，設備放置問題(The Facility Location Problem)屬於等價問題。然而，緩存放置 問題(Caching Placement Problem)是緩存技術中的關鍵問題，在有線和無線網絡中已經有了較多的研究工作。在無線行動網路中現有的數據緩存工作主要是對問題本身進行了轉化，通過將緩存放置問題轉化為租用或者購買問題，然後根據貪婪算法的原理，提出了相應的算法。該技術主要存在兩個問題1)算法計算過程較為複雜，通過大量的集合轉化，對樹形結構的分解，得到最終緩存放置方案。構造過程過於複雜，比較難以實現算法；2)算法結果是通過數值分析的方法檢驗，並沒有放在無線網絡環境中進行任何實驗或者仿真。因此，針對上述問題，有必要提出一種基於數據緩衝的方法，減少緩存系統的開銷。

發明內容
有鑑於此，有必要提供一種數據緩存放置系統及數據緩存的方法。本發明提供的一種數據緩存放置系統，用於無線網絡中，其中，無線網絡中包括多個結點，所述緩存放置系統包括計算模塊、判斷模塊、選擇模塊以及繼續模塊。其中，計算模塊用於計算所述無線網絡中每個結點的對衝數據流，其中，所述對衝數據流為結點作為緩存結點時增加與減少的數據流之和；判斷模塊用於判斷一結點到某一結點的距離是否小於某一結點到最近緩存結點的距離，其中，計算模塊還用於在一結點到某一結點的距離小於某一結點到最近緩存結點的距離時增加該結點的對衝數據流，判斷模塊還用於判斷該結點的對衝數據流是否大於第一閾值；選擇模塊用於在該結點的對衝數據流大於第一閾值時將該結點選為候選結點，並將該結點加入到候選結點集合，其中，計算模塊還用於根據該候選結點的對衝數據流以及該候選結點與緩存結點之間的距離計算該候選結點在無線網絡中的競爭係數，判斷模塊還用判斷所述競爭係數是否大於第二閾值，所述選擇模塊還用於在所述競爭係數大於第二閾值時將該候選結點作為緩存結點，並將該候選結點加入到緩存結點集合。本發明還提供一種數據緩存的方法，用於無線網絡中，其中無線網絡中包括多個結點，所述方法包括以下步驟計算所述無線網絡中每個結點的對衝數據流，其中，所述對衝數據流為結點作為緩存結點時增加與減少的數據流之和；判斷一結點到某一結點的距離是否小於某一結點到最近緩存結點的距離；若一結點到某一結點的距離小於某一結點到最近緩存結點的距離，則增加該結點的對衝數據流；判斷該結點的對衝數據流是否大於第一閾值；若該結點的對衝數據流大於第一閾值，則將該結點選為候選結點，並將該結點加入到候選結點集合；根據該候選結點的對衝數據流以及該候選結點與緩存結點之間的距離計算該候選結點在無線網絡中的競爭係數；判斷所述競爭係數是否大於第二閾值；若所述競爭係數大於第二閾值，則將該候選結點作為緩存結點，並將該候選結點加入到緩存結點集合。本發明中的數據緩存放置系統及數據緩存的方法通過判斷結點的對衝數據流是否大於第一閾值來決定結點是否為候選結點，然後計算候選接結點的競爭係數並判斷競爭係數是否大於第二閾值來決定結點是否緩存結點，形成緩存結點集合，減少了對數據流的分析，以及緩存數據的訪問延遲，同時也減少了網絡中數據訪問的開銷。



圖1為本發明一實施方式中數據緩存放置系統的模塊圖；圖2為計算對衝數據流的實施例。圖3為本發明一實施方式中利用圖1所示的數據緩存放置系統進行數據緩存的方法的流程圖。
具體實施例方式下面詳細描述本發明的實施例，所述實施例的示例在附圖中示出，其中自始至終相同或類似的標號表示相同或類似的元件或具有相同或類似功能的元件。下面通過參考附圖描述的實施例是示例性的，僅用於解釋本發明，而不能理解為對本發明的限制。在本發明的描述中，術語「內」、「外」、「縱向」、「橫向」、「上」、「下」、「頂」、「底」等指示的方位或位置關係為基於附圖所示的方位或位置關係，僅是為了便於描述本發明而不是要求本發明必須以特定的方位構造和操作，因此不能理解為對本發明的限制。請參閱圖1，圖1所示為本發明一實施方式中數據緩存放置系統10的模塊圖。
在本實施方式中，數據緩存放置系統10包括計算模塊102、判斷模塊104、選擇模塊106、繼續模塊108、存儲器110以及處理器112，其中，計算模塊102、判斷模塊104、選擇模塊106以及繼續模塊108存儲在存儲器110中，處理器112用於執行存儲在存儲器110中的功能模塊。在本實施方式中，數據緩存放置系統10用於無線網絡中，其中，無線網絡中包括多個結點。在本實施方式中，存儲器110中設有緩存結點集合C、候選結點集合H、所有結點的最近緩存結點集合NC以及競爭係數集合CC。在本實施方式中，初始情況下，數據源結點屬於緩存結點集合C和最近緩存結點集合NC。在本實施方式中，計算模塊102用於計算所述無線網絡中每個結點的對衝數據流。判斷模塊104用於判斷一結點到某一結點的距離是否小於某一結點到最近緩存結點的距離。在本實施方式中，計算模塊102還用於在一結點到某一結點的距離小於某一結點到最近緩存結點的距離時增加該結點的對衝數據流。在本實施方式中，所述對衝數據流為結點作為緩存結點時增加與減少的數據流之和。在本實 施方式中，對衝數據流(Hedging Data Flow)的概念和金融行業中的對衝基金有著異曲同工的地方。緩存系統中存在的數據流的類型包括以下三種第一種類型的數據流是訪問數據流(Accessing Data Flow),簡稱為ADF,這種數據流描述了網絡中的一個結點訪問數據的請求情況；第二種是應答數據流(Reply Data Flow),簡稱為RDF,這種數據流描述了數據源結點或者緩存結點應答其他結點的數據請求的情況；第三種是更新數據流(Update Data Flow)，簡稱為UDF，這種數據流描述的是數據源更新緩存結點上的數據拷貝所產生的數據流。因此綜合上述四種數據流，若需要增加一個緩存結點，就需要盡最大可能的減少訪問數據流和應答數據流，也需要盡最大可能的減少因為增加緩存結點而引入的更新數據流。在本實施方式中，對衝數據流和其他三種數據流之間的關係HDF ⑴=Δ ADF ( ) + Δ RDF (i)-UDF (i)請結合圖2，圖2所示為計算模塊102計算對衝數據流的一實施例。在實施方式中，假設數據訪問的路徑和數據返回的路徑是一樣的，因此，可以把訪問數據流和應答數據流合併在一起，也就意味著只要有訪問數據流就有應答數據流。在圖2中的左上角的圖中，結點NI是數據源。若在圖2的右上角的圖中，計劃選擇N3為緩存結點，那麼減少的訪問數據流應該是 ΔADF(3) = (fa(4) +fa(5) +fa(6) +fa(7) +fa(8)) X (sr+sd) Xw(3, I) (I)在上面的公式(I)中，fa(4)表示結點N4訪問數據的頻率，\和8(1分別表示數據本身的大小和數據請求的大小，w(3，I)表示路徑剛從結點N3到數據源NI的權重。上面的公式(I)表示，其他結點本來要經過結點N3去數據源NI去訪問到數據，現在只要在結點N3上就可以訪問到數據了。這樣的話，對於其他結點N4到NS就可以減少兩跳(2hops)。根據同樣的道理，原來結點N3不需要從更新數據流，現在因為它充當了緩存結點，因此就增加了更新數據流，增加的數據流可以用下面的公式表示UDF(3) = fuX sdXw(l, 3) (2)在公式(2)中，fu表示數據源更新數據的頻率，4表示數據本身的大小，w(l，3)表示路徑剛從數據源NI到結點N3的權重。在本實施方式中，判斷模塊104還用於判斷該結點的對衝數據流是否大於第一閾值。選擇模塊106用於在該結點的對衝數據流大於第一閾值時將該結點選為候選結點，並將該結點加入到候選結點集合。在本實施方式中，計算模塊102還用於根據該候選結點的對衝數據流以及該候選結點與緩存結點之間的距離計算該候選結點在無線網絡中的競爭係數。在本實施方式中，結點Ni的競爭係數的定義如下
權利要求
1.一種數據緩存放置系統，用於無線網絡中，其中，無線網絡中包括多個結點，其特徵在於，所述緩存放置系統包括 計算模塊，用於計算所述無線網絡中每個結點的對衝數據流，其中，所述對衝數據流為結點作為緩存結點時增加與減少的數據流之和； 判斷模塊，用於判斷一結點到某一結點的距離是否小於某一結點到最近緩存結點的距離，其中，計算模塊還用於在一結點到某一結點的距離小於某一結點到最近緩存結點的距離時增加該結點的對衝數據流，判斷模塊還用於判斷該結點的對衝數據流是否大於第一閾值； 選擇模塊，用於在該結點的對衝數據流大於第一閾值時將該結點選為候選結點，並將該結點加入到候選結點集合，其中，計算模塊還用於根據該候選結點的對衝數據流以及該候選結點與緩存結點之間的距離計算該候選結點在無線網絡中的競爭係數，判斷模塊還用判斷所述競爭係數是否大於第二閾值，所述選擇模塊還用於在所述競爭係數大於第二閾值時將該候選結點作為緩存結點，並將該候選結點加入到緩存結點集合。
2.如權利要求1所述的數據緩存放置系統，其特徵在於，所述判斷模塊還用於在一結點到某一結點的距離大於等於某一結點到最近緩存結點的距離時判斷所述候選結點集合是否為空，且在所述候選結點集合不為空是判斷該結點是否為最後一個結點。
3.如權利要求1所述的數據緩存放置系統，其特徵在於，所述判斷模塊還用於在該結點的對衝數據流小於等於第一閾值時判斷所述候選結點集合是否為空，且在所述候選結點集合不為空是判斷該結點是否為最後一個結點。
4.如權利要求1所述的數據緩存放置系統，其特徵在於，所述判斷模塊還用於在所述競爭係數小於等於第二閾值時判斷所述候選結點集合是否為空，且在所述候選結點集合不為空是判斷該結點是否為最後一個結點。
5.如權利要求2或3或4所述的數據緩存放置系統，其特徵在於，還包括繼續模塊，用於在所述結點不是最後一個結點時繼續對下一個結點進行處理。
6.一種數據緩存的方法，用於無線網絡中，其中無線網絡中包括多個結點，其特徵在於，所述方法包括以下步驟 計算所述無線網絡中每個結點的對衝數據流其中，所述對衝數據流為結點作為緩存結點時增加與減少的數據流之和； 判斷一結點到某一結點的距離是否小於某一結點到最近緩存結點的距離； 若一結點到某一結點的距離小於某一結點到最近緩存結點的距離，則增加該結點的對衝數據流； 判斷該結點的對衝數據流是否大於第一閾值； 若該結點的對衝數據流大於第一閾值，則將該結點選為候選結點，並將該結點加入到候選結點集合； 根據該候選結點的對衝數據流以及該候選結點與緩存結點之間的距離計算該候選結點在無線網絡中的競爭係數； 判斷所述競爭係數是否大於第二閾值； 若所述競爭係數大於第二閾值，則將該候選結點作為緩存結點，並將該候選結點加入到緩存結點集合。
7.如權利要求6所述的數據緩存的方法，其特徵在於，還包括以下步驟 若一結點到某一結點的距離大於等於某一結點到最近緩存結點的距離，則判斷候所述選結點集是否為空； 若所述候選結點集不為空，則判斷該結點是否為最後一個結點。
8.如權利要求6所述的數據緩存的方法，其特徵在於，還包括以下步驟 若該結點的對衝數據流小於等於第一閾值，則判斷所述選結點集是否為空； 若所述候選結點集不為空，則判斷該結點是否為最後一個結點。
9.如權利要求6所述的數據緩存的方法，其特徵在於，還包括以下步驟 若所述競爭係數小於等於第二閾值，則判斷所述選結點集是否為空； 若所述候選結點集不為空，則判斷該結點是否為最後一個結點。
10.如權利要求7或8或9所述的數據緩存的方法，其特徵在於，還包括以下步驟 若所述結點不是最後一個結點，則繼續對下一個結點進行處理。
全文摘要
一種數據緩存放置系統，用於無線網絡中，無線網絡中包括多個結點，其特徵在於，所述緩存放置系統包括計算模塊、判斷模塊、選擇模塊以及繼續模塊，其中，計算模塊計算所述無線網絡中每個結點的對衝數據流，其中，所述對衝數據流為結點作為緩存結點時增加與減少的數據流之和；判斷模塊判斷一結點到某一結點的距離是否小於某一結點到當前最近緩存結點的距離，若是，計算模塊計算該結點的對衝數據流，判斷模塊判斷該結點的對衝數據流是否大於第一閾值；若是，選擇模塊在將該結點選為候選結點，計算模塊根據該候選結點的對衝數據流以及該候選結點與緩存結點之間的距離計算該候選結點在無線網絡中的競爭係數，判斷模塊判斷所述競爭係數是否大於第二閾值，若是，選擇模塊將該候選結點作為緩存結點。
文檔編號H04W28/14GK103052114SQ201210562480
公開日2013年4月17日 申請日期2012年12月21日 優先權日2012年12月21日
發明者範小朋, 毛海霞, 須成忠, 張帆 申請人:中國科學院深圳先進技術研究院