一種基於節點競爭時延代價模型的緩存部署方法與流程
2023-09-20 08:17:10
本發明屬於無線通信技術領域，具體涉及一種基於節點競爭時延代價模型的緩存部署方法。
背景技術：
隨著移動通信數據流量的飛速增長，其中視頻多媒體業務在所有業務中佔大多數，在黃金時段或者熱門事件爆發時，網絡內容資源需求量會急劇增加，可能導致網絡崩潰，將高訪問率的內容資源緩存到緩存伺服器可以拉近資源與用戶的距離，大大降低了用戶的接入時延，因此，根據不同網絡請求分布狀況確定緩存伺服器位置的緩存伺服器部署方法受到廣泛研究。
針對無線mesh網絡等多跳自組織網絡，緩存伺服器部署方法主要採用的是利用最小生成樹、斯坦納樹等經典遍歷算法將緩存內容從源伺服器分發到每個節點，再在基於節點請求狀況確定該緩存內容是否緩存。該方法在未考慮節點是否需要緩存內容的情況下，使所有節點都獲得緩存內容，再根據節點自身狀況判斷決定是否緩存，因此具有一定的盲目性，而且在節點最終沒有緩存該內容情況下可能進行了一些無用的鏈路傳輸，增加了網絡的壓力。此外，根據整體網絡請求分布狀況以及網絡拓撲結構，再確定最佳緩存伺服器部署位置，這個的過程是一個np-hard(np：non-deterministicpolynomial)問題，研究人員通常會將其轉化為經典的背包問題、推銷員旅行問題等來進行分析，由於此方法求解時間複雜度很高，所以一般用於網絡節點是否配置具有緩存能力的緩存伺服器的判決中；對於單個緩存內容而言，根據整體網絡請求分布狀況以及網絡拓撲結構，如何在較低時間複雜度情況下，制定其是否緩存於緩存伺服器的最佳緩存部署方法是一個有待解決的難題。
緩存內容部署最主要的目標是降低用戶獲得資源的傳輸時延，對於無線mesh網絡等多跳自組織網絡而言，無論是最小生成樹、斯坦納樹的確定還是np-hard問題目標代價函數的構建，其傳輸時延代價主要通過跳躍次數來表徵的；同時，通過對鏈路的競爭關係的研究，基於鏈路的競爭時延代價模型逐漸被研究人員關注，不同於基於跳躍次數的時延代價模型僅考慮節點獲得資源的鏈路跳躍次數，基於鏈路的競爭時延代價模型考慮了緩存內容傳輸過程中由於競爭網絡傳輸資源的影響，更具體的反應了網絡中節點的傳輸狀況，使得傳輸時延的表徵更合理，由此制定的緩存部署方法能更有效的優化整個網絡的傳輸時延性能。
緩存內容部署帶來的傳輸時延的降低，伴隨著的是網絡節點對緩存內容存儲的能耗和緩存空間成本的增加，如何實現傳輸時延與緩存內容存儲代價的權衡也是緩存部署方法的關鍵點。
技術實現要素：
本發明所要解決的技術問題在於針對上述現有技術中的不足，提出了一種基於節點競爭時延代價模型的緩存部署方法，解決針對單個緩存內容根據網絡請求分布以及網絡拓撲結構確定相應的緩存部署問題，該算法的時間複雜度為o(n3)，具有一定的可行性。
本發明採用以下技術方案：
一種基於節點競爭時延代價模型的緩存部署方法，在算法執行過程中確定n個節點是否是緩存節點，每次確定一個緩存伺服器時確定n個節點作為緩存伺服器時的性能，通過每次性能分析尋找到n個節點的最佳鏈路，確定基於節點競爭時延代價模型的緩存部署方法時間複雜度o(n3)。
進一步的，包括以下步驟：
s1、在網絡中只有源伺服器一個緩存伺服器的情況下，初始化網絡配置參量和初始化迭代過程變量；
s2、在已確定的緩存伺服器節點結果下，分別分析每個節點作為候選緩存伺服器時的傳輸時延代價；
s3、挑選傳輸時延代價最小的節點作為待確定緩存伺服器節點；
s4、比較待確定緩存伺服器節點部署帶來的傳輸時延收益與緩存內容存儲代價，確定是否在待確定緩存伺服器節點上部署該緩存內容；
s5、若成功添加了新的緩存伺服器節點，則更新網絡配置參量和迭代過程變量，返回步驟s2，若未添加新的緩存伺服器節點，表明已經部署的緩存伺服器節點使得整體網絡傳輸時延代價和緩存內容存儲代價最小，結束。
進一步的，步驟s1中，所述初始化網絡配置參量具體為：緩存伺服器集合節點被服務信息節點被服務鏈路路徑其中：為節點集合；o為緩存內容的源伺服器；
所述初始化迭代過程變量具體為：節點獲得緩存內容的傳輸時延代價cok＝pkdf(o,k)v，所有節點總的傳輸時延代價其中：為節點集合；o為緩存內容的源伺服器；pk為節點k對緩存內容的請求強度；v為緩存內容大小；df(o,k)為節點o服務節點k的基於節點競爭時延代價模型的傳輸時延代價。
進一步的，所述基於節點競爭時延代價模型的傳輸時延代價包括：緩存伺服器節點j到接入節點k的內容傳輸數據流的鏈路路徑f(j,k)；內容傳輸數據流的鏈路路徑上所有節點集合節點r競爭範圍內節點集合起源或者經過節點n的內容傳輸數量流內容傳輸數據流f的目標節點d(f)；節點單跳時延代價統計平均值估計值t；節點n相比其競爭範圍內其他節點的競爭權值係數wn和內容傳輸數據流的鏈路路徑f(j,k)的基於節點競爭時延代價模型的傳輸時延代價df(j,k)。
進一步的，節點n相比其競爭範圍內其他節點的競爭權值係數wn為：
其中，sf為內容傳輸數據流f在當前跳內的傳輸距離；pd(f)為內容傳輸數據流f在當前跳的目標節點內容資源請求強度；α為路徑損耗係數。
進一步的，基於節點競爭時延代價模型考慮了節點獲得緩存內容形成的鏈路路徑每跳的競爭關係對時延的影響，所述基於節點競爭時延代價模型的傳輸時延代價df(j,k)為：
進一步的，步驟s2具體包括：
s21、選取非緩存伺服器節點中未進行候選緩存伺服器分析的節點j，初始化其作為候選緩存伺服器時的傳輸時延代價costafter＝0；
s22、按照節點獲得緩存內容的傳輸時延代價從小到大的順序依次選取接入節點k，獲得其被服務的緩存伺服器節點和對應的傳輸時延代價cqk＝pkdf(q,k)v，採用迪傑斯特拉算法制定節點k從候選緩存伺服器節點j獲得緩存內容時的節點被服務鏈路路徑對應的傳輸時延代價cjk＝pkdf(j,k)v；
s23、確定節點k是否改變鏈路路徑：若cqk≥cjk，則節點k改變鏈路路徑，節點j作為候選緩存伺服器的傳輸時延代價costafter＝costafter+cjk，節點臨時被服務集合若cqk＜cjk，則節點k維持原有鏈路連接，節點被服務鏈路路徑節點j作為候選緩存伺服器的傳輸時延代價costafter＝costafter+cqk，節點臨時被服務集合
s24、若節點j作為候選緩存伺服器時各接入節點鏈路沒有分析完，跳轉至步驟s22；否則，結束。
進一步的，步驟s3具體包括以下步驟：
s31、初始化迭代循環中添加候選緩存伺服器節點時的最小傳輸時延代價costmin＝+∞；
s32、選取非緩存伺服器節點作為候選緩存伺服器時未進行傳輸時延代價比較的節點j，若costmin＞costafter，則costmin＝costafter，待確定緩存伺服器節點b＝j；否則，維持不變；
s33、若非緩存伺服器節點作為候選緩存伺服器時的傳輸時延代價沒有比較完，跳轉至步驟s32；否則，結束。
進一步的，步驟s4具體包括：
s41、提取原緩存伺服器部署方法下傳輸時延代價costbefore，提取待確定緩存伺服器節點b，提取候選緩存服務節點部署緩存伺服器之後的最小傳輸時延代價costmin；
s42、比較傳輸時延收益與緩存內容存儲代價，若則在待確定緩存伺服器節點上部署該緩存內容，也就是添加新的緩存伺服器節點；否則捨棄將節點b作為真實的緩存服務節點；
其中：λ為緩存內容存儲代價與傳輸時延代價的權值係數，一般需要根據具體場景情況量化處理，為定值；γ為單位緩存內容大小的緩存容量存儲代價，一般需要根據具體場景情況量化處理，不同緩存伺服器之間是相同的，為定值。
進一步的，步驟s5中，所述更新網絡配置參量和迭代過程變量包括：緩存伺服器集合節點被服務信息節點被服務鏈路路徑和新的所有節點的傳輸時延代價之和costbefore＝costmin。
與現有技術相比，本發明至少具有以下有益效果：
本發明基於節點競爭時延代價模型的緩存部署方法在算法執行過程中確定n個節點是否是緩存節點，每次確定一個緩存伺服器時確定n個節點作為緩存伺服器時的性能，通過每次性能分析尋找到n個節點的最佳鏈路，確定基於節點競爭時延代價模型的緩存部署方法時間複雜度o(n3)，該緩存部署方法在分發緩存內容前根據緩存內容請求分布進行了合理緩存伺服器節點確定，避免了傳統的廣播式發送再在節點處根據請求強度確定是否緩存的盲目性，極大的減少了無用的鏈路傳輸，緩解網絡壓力，基於節點競爭時延代價模型的緩存部署方法總的傳輸時延代價值更小，選擇的緩存伺服器位置更合理，使得部署相同緩存伺服器個數條件下，節點獲得緩存內容的傳輸時延更短。
進一步的，該緩存部署方法是基於節點競爭時延代價模型構建的傳輸時延代價，考慮了緩存內容傳輸過程中由於競爭網絡傳輸資源的影響，更具體的反應了網絡中節點的傳輸狀況，使得傳輸時延的表徵更合理，由此制定的緩存部署方法能更有效的優化整個網絡的傳輸時延性能；
進一步的，該基於節點競爭時延代價模型的緩存部署方法時間複雜度為o(n3)，相比於其他np-hard問題超高時間複雜度求解思路，其可以有效應用於直播等實時業務緩存伺服器部署。
綜上所述，本發明對於無線mesh網絡等多跳自組織網絡中針對節點獲得緩存內容傳輸時延和緩存內容存儲代價的權衡值進行了方法部署，減少了無用的鏈路傳輸，緩解網絡壓力，降低整個網絡的信令負荷，提高系統無線資源利用率。
下面通過附圖和實施例，對本發明的技術方案做進一步的詳細描述。
附圖說明
圖1是本發明基於節點競爭時延代價模型的緩存部署方法流程圖；
圖2是本發明待確定緩存伺服器節點判斷流程圖；
圖3是本發明算法仿真節點網格分布和緩存內容源伺服器示意圖；
圖4是本發明不同權值係數條件下緩存伺服器部署數量對比圖；
圖5是本發明不同權值係數條件下傳輸時延代價值對比圖；
圖6是本發明性能仿真節點分布與源伺服器分布示意圖；
圖7是本發明不同時延代價模型傳輸時延對比圖。
具體實施方式
本發明提供了一種基於節點競爭時延代價模型的緩存部署方法，提出的基於節點競爭時延代價模型的緩存部署方法在算法執行過程中需要對n個節點是否是緩存節點進行分析，每次確定一個緩存伺服器時需要對n個節點作為緩存伺服器時性能進行分析，每次性能分析需要尋找到n個節點的最佳鏈路，因此應用本論文提出的基於節點競爭時延代價模型的緩存部署方法的時間複雜度為o(n3)。
基於節點競爭時延代價模型的緩存部署方法目的是根據節點對緩存內容請求分布，確定網絡的緩存伺服器節點被服務信息節點被服務鏈路路徑
請參閱圖1，具體步驟如下：
s1、在網絡中只有源伺服器一個緩存伺服器的情況下，初始化網絡配置參量和初始化迭代過程變量；
初始化網絡配置參量
此時網絡中緩存伺服器只有源伺服器，因此緩存伺服器集合節點被服務信息節點被服務鏈路路徑
其中：為節點集合；o為緩存內容的源伺服器。
初始化迭代過程變量
緩存伺服器只有源伺服器一個節點，所有其他節點都從源伺服器獲得內容資源，因此節點獲得緩存內容的傳輸時延代價cok＝pkdf(o,k)v，所有節點總的傳輸時延代價
其中：為節點集合；o為緩存內容的源伺服器；pk為節點k對緩存內容的請求強度；v為緩存內容大小；df(o,k)為節點o服務節點k的基於節點競爭時延代價模型的傳輸時延代價。
所述基於節點競爭時延代價模型的傳輸時延代價包括：
緩存伺服器節點j到接入節點k的內容傳輸數據流的鏈路路徑f(j,k)；
內容傳輸數據流的鏈路路徑上所有節點集合
節點r競爭範圍內節點集合
起源或者經過節點n的內容傳輸數量流
內容傳輸數據流f的目標節點d(f)；
節點單跳時延代價統計平均值估計值t；
節點n相比其競爭範圍內其他節點的競爭權值係數wn；
內容傳輸數據流的鏈路路徑f(j,k)的基於節點競爭時延代價模型的傳輸時延代價df(j,k)。
節點n相比其競爭範圍內其他節點的競爭權值係數wn為：
其中，sf為內容傳輸數據流f在當前跳內的傳輸距離；pd(f)為內容傳輸數據流f在當前跳的目標節點內容資源請求強度；α為路徑損耗係數，一般取4。
基於節點競爭時延代價模型考慮了節點獲得緩存內容形成的鏈路路徑每跳的競爭關係對時延的影響，所述基於節點競爭時延代價模型的傳輸時延代價df(j,k)為：
其中，f(j,k)為緩存伺服器節點j到接入節點k的內容傳輸數據流的鏈路路徑；為內容傳輸數據流的鏈路路徑上所有節點集合；為節點r競爭範圍內節點集合；為起源或者經過節點n的內容傳輸數量流；d(f)為內容傳輸數據流f的目標節點；t為節點單跳時延代價統計平均值估計值；wn為節點n相比其競爭範圍內其他節點的競爭權值係數。
上述所提出的競爭時延代價模型是基於內容傳輸數據流經過的節點數以及對應競爭範圍內的節點數和起源或者經過這些競爭範圍內節點的數據流來構建的，該模型的關鍵點在於路徑選擇方法和競爭關係的關聯性對時延的增益。在靜態路由網絡中，由於介質訪問的競爭關係，內容傳輸數據流的時延代價與其經過節點所傳輸的內容數據流數量成正相關，也與其經過節點競爭範圍內節點的內容傳輸數據流數量成正相關，這些內容傳輸數據流也就是上述提到的
而在動態路由網絡中，動態路由選擇方法所確定的路徑將決定內容傳輸數據流中每個節點的競爭範圍，同時每個節點的競爭關係對該節點傳輸時延都有一定的增益，這些增益值是獨立的，換句話說，內容傳輸數據流的時延代價就是節點單跳時延代價統計平均值與總增益的乘積，而總增益也就是各單跳時延增益值統計之和。
由此不難看出，無論是在靜態路由網絡還是在動態路由網絡中，傳輸時延代價都可以看成時延代價統計平均值與時延增益的乘積，也就是本發明構造的基於節點競爭時延代價模型。
s2、在已確定的緩存伺服器節點結果下，分別分析每個節點作為候選緩存伺服器時的傳輸時延代價；
s21、選取非緩存伺服器節點中未進行候選緩存伺服器分析的節點j，初始化其作為候選緩存伺服器時的傳輸時延代價costafter＝0；
s22、按照節點獲得緩存內容的傳輸時延代價從小到大的順序依次選取接入節點k，獲得其被服務的緩存伺服器節點和對應的傳輸時延代價cqk＝pkdf(q,k)v，採用迪傑斯特拉算法制定節點k從候選緩存伺服器節點j獲得緩存內容時的節點被服務鏈路路徑對應的傳輸時延代價cjk＝pkdf(j,k)v；
s23、確定節點k是否改變鏈路路徑：若cqk≥cjk，則節點k改變鏈路路徑，節點j作為候選緩存伺服器的傳輸時延代價costafter＝costafter+cjk，節點臨時被服務集合若cqk＜cjk，則節點k維持原有鏈路連接，節點被服務鏈路路徑節點j作為候選緩存伺服器的傳輸時延代價costafter＝costafter+cqk，節點臨時被服務集合
s24、若節點j作為候選緩存伺服器時各接入節點鏈路沒有分析完，跳轉至步驟s22；否則，結束。
s3、挑選傳輸時延代價最小的節點costmin＝+∞作為待確定緩存伺服器節點，請參閱圖2，具體包括以下步驟：
s31、初始化迭代循環中添加候選緩存伺服器節點時的最小傳輸時延代價costmin＝+∞；
s32、選取非緩存伺服器節點作為候選緩存伺服器時未進行傳輸時延代價比較的節點j，若costmin＞costafter，則costmin＝costafter，待確定緩存伺服器節點b＝j；否則，維持不變；
s33、若非緩存伺服器節點作為候選緩存伺服器時的傳輸時延代價沒有比較完，跳轉至步驟s32；否則，結束。
s4、比較待確定緩存伺服器節點部署帶來的傳輸時延收益與緩存內容存儲代價，確定是否在待確定緩存伺服器節點上部署該緩存內容；
s41、提取原緩存伺服器部署方法下傳輸時延代價costbefore，提取待確定緩存伺服器節點b，提取候選緩存服務節點部署緩存伺服器之後的最小傳輸時延代價costmin；
s42、比較傳輸時延收益與緩存內容存儲代價，若則在待確定緩存伺服器節點上部署該緩存內容，也就是添加新的緩存伺服器節點；否則捨棄將節點b作為真實的緩存服務節點。
其中：λ為緩存內容存儲代價與傳輸時延代價的權值係數，一般需要根據具體場景情況量化處理，為定值；γ為單位緩存內容大小的緩存容量存儲代價，一般需要根據具體場景情況量化處理，不同緩存伺服器之間是相同的，為定值。
s5、若成功添加了新的緩存伺服器節點，則更新網絡配置參量和迭代過程變量，返回步驟s2，若未添加新的緩存伺服器節點，表明已經部署的緩存伺服器節點使得整體網絡傳輸時延代價和緩存內容存儲代價最小，結束。
所述更新網絡配置參量和迭代過程變量包括：緩存伺服器集合節點被服務信息節點被服務鏈路路徑和新的所有節點的傳輸時延代價之和costbefore＝costmin。
為驗證本發明提出的緩存部署方法能有效求解上述的np-hard問題，參考圖3所示的節點網格分布和緩存內容源伺服器示意圖，參考表1所示的算法仿真參數設置表，將本發明提出的基於節點競爭時延代價模型的緩存部署方法求得的次優解與遍歷所得的理論最優解進行對比，參考圖4，不同緩存內容存儲代價與傳輸時延代價的權值係數λ條件下，兩者求得緩存伺服器部署數量是相同的；參考圖5，不同緩存內容存儲代價與傳輸時延代價的權值係數λ條件下，本發明與理論最優解的傳輸時延代價誤差在10％以內，總體而言本發明提出的部署方法在求解上述np-hard問題具有很高的準確性。
表1算法仿真參數設置表
為驗證本發明提出的基於節點競爭時延代價模型更具體的反應了網絡中節點的傳輸狀況，使得緩存部署方法更合理，參考圖6所示的節點網格分布和緩存內容源伺服器示意圖，參考表2所示的緩存部署方法仿真參數設置表，將本發明提出的基於節點競爭時延代價模型的緩存部署方法與基於鏈路跳躍次數模型、基於鏈路競爭時延代價模型進行對比，參考圖7，基於節點競爭時延代價模型的緩存部署方法相比於另外兩種模型在部署相同緩存伺服器個數情況下，總的傳輸時延代價值更小，換句話說基於節點競爭時延代價模型選擇的緩存伺服器位置更合理，使得部署相同緩存伺服器個數條件下，節點獲得緩存內容的傳輸時延更短。
表3-4緩存部署方法仿真參數設置表
綜上所述，本發明提出了一種基於節點競爭時延代價模型的緩存部署方法，首先，該緩存部署方法在分發緩存內容前已經根據緩存內容請求分布進行了合理緩存伺服器節點確定，避免了傳統的廣播式發送再在節點處根據請求強度確定是否緩存的盲目性，極大的減少了無用的鏈路傳輸，緩解網絡壓力；其次，該緩存部署方法是基於節點競爭時延代價模型構建的傳輸時延代價，它考慮了緩存內容傳輸過程中由於競爭網絡傳輸資源的影響，更具體的反應了網絡中節點的傳輸狀況，使得傳輸時延的表徵更合理，由此制定的緩存部署方法能更有效的優化整個網絡的傳輸時延性能；最後，該基於節點競爭時延代價模型的緩存部署方法時間複雜度為o(n3)，相比於其他np-hard問題超高時間複雜度求解思路，其可以有效應用於直播等實時業務緩存伺服器部署。
以上內容僅為說明本發明的技術思想，不能以此限定本發明的保護範圍，凡是按照本發明提出的技術思想，在技術方案基礎上所做的任何改動，均落入本發明權利要求書的保護範圍之內。