[發明專利]一種空間信息網絡緩存決策方法

在審

• 申請號: 202210310851.0
• 申請日: 2022-03-28
• 公開（公告）號: CN114759970A
• 公開（公告）日: 2022-07-15
• 發明（設計）人: 蔡睿妍;錢楊;田全;魏德賓
• 申請（專利權）人: 臺州學院
• 主分類號: H04B7/185
• 分類號: H04B7/185;G06N3/00
• 代理公司: 大連智高專利事務所(特殊普通合伙) 21235
• 代理人: 蓋小靜

1.一種空間信息網絡緩存決策方法，其特征在于：包括以下步驟：

A、建立空間信息網絡緩存系統模型

ICN衛星網絡的節點維護了三種數據結構，分別是內容緩存CS、未決興趣表PIT和轉發信息表FIB，用于完成地面終端獲取星上資源的請求和數據回傳；地面用戶u請求內容f的步驟如下：設實線表示兩個節點之間存在通信鏈路，包括用戶與衛星的星地鏈路、衛星與衛星的星間鏈路，虛線則表示內容的請求路徑；當地面用戶u請求內容f時，首先將請求內容f發送到為之提供通信服務的v₁衛星；若衛星v₁緩存有該內容，則直接返回；否則將按照未決興趣表中的信息向網絡中的其他節點獲取內容，在其他節點中獲取到內容f后返回，若空間信息網絡所有節點均未緩存該內容，則向原始服務器請求，獲取到內容f后返回；

A1、設計網絡分區算法對空間信息網絡節點進行分區

由于低軌衛星運動具有周期性，因此將覆蓋某個區域的數顆衛星按照網絡分區算法劃作一個分區協作緩存內容，以減少衛星節點緩存資源浪費，分區中每顆衛星節點緩存內容均不相同，各顆衛星均存在星間鏈路，此時，既不影響用戶對內容的訪問，又降低對單顆衛星的緩存資源要求；空間信息網絡的拓撲結構實際上是一個以星間鏈路的長度為權值的無向圖，用G(V,E)來描述，V＝{v₁,v₂,...,v_N}為N顆衛星的節點集合，表示網絡中的衛星節點；E表示節點間的星間鏈路；針對衛星運動的動態性和周期性，采用劃分時間片的方法，即把一個完整的衛星運動周期T離散為足夠小的時間間隔τ，空間信息網絡節點拓撲結構在時間間隔τ內是保持穩定的，借助衛星的軌道參數計算各時間間隔τ內每個衛星的具體坐標，計算公式如下：

其中，X_i為第i顆衛星對應的直角坐標系的X軸坐標；Y_i為第i顆衛星對應的直角坐標系的Y軸坐標；Z_i為第i顆衛星對應的直角坐標系的Z軸坐標；a為衛星離地心的距離、v_i為衛星對應的近地點幅角、Ω_i為衛星對應的升交點赤經、v_oi為衛星初始的近地點幅角、Ω_oi為衛星初始的升交點赤經、i_i為軌道傾斜角、n_o為衛星公轉角速度、ω_o為地球的自轉角速度；令t₀＝0表示初始時刻，通過改變t的值，計算出各衛星在不同時間間隔內的具體坐標；

在已知各個時間間隔內衛星節點的具體坐標后，即知道節點間的星間鏈路長度，為方便分析，空間信息網絡節點拓撲結構生成采用可視即可連策略；對空間信息網絡節點拓撲進行分區，即將整個網絡拓撲劃分成多個不相交的區域，因此，對整個網絡拓撲進行分區被視為最小覆蓋成本的優化問題，其覆蓋代價profit表示為：

cost(i,j)＝d(i,j)/c+T_a (4)

其中，C＝{C₁,C₂,...,C_n}表示衛星節點的分區，n為區域的最大編號；C_n＝{c_n1,c_n2,...,c_nk}表示分區后衛星節點的集合，c_nk為第n個分區的第k個衛星節點；V＝{v₁,v₂,...,v_N}表示所有的衛星節點；d(i,j)是源節點v_i和目的節點v_j之間的歐氏距離；c為光速，T_a是為源節點v_i到目的節點v_j的處理時延；r_i,j為源節點v_i和目的v_j之間的傳輸路徑上的所有節點；

通過迪杰斯特拉即Dijkstra最短路徑算法計算出衛星節點v_i到v_j之間傳輸路徑上的所有節點，即r_i,j；通過下面的網絡分區算法得出某個時間間隔τ內的分區節點集合，優化得出對應的總覆蓋代價profit，網絡分區算法的步驟如下：

輸入：衛星節點總數N、衛星網絡拓撲結構G(V,E)

輸出：分區后的節點信息C

S1、初始化，依據可視即可連策略獲取衛星網絡拓撲結構

S2、v_i→v_j

S3、for每個時間片

根據公式(1)計算出該時間片內各衛星的位置坐標，得出對應的G(V,E)

S4、for i≤N

S5、Dijkstra(v_j,G,V)→(pfofit,v_i)

S6、C_n∪c_nk→C_n

S7、while v_j≠v_i and更新區域信息

S8、C_n\v_j→C_n

S9、Dijkstra(v_j,G,V)→(pfofit,v_i)

S10、更新區域節點信息

S11、end while

S12、end for

S13、Return C

A2、建立節點緩存模型

在空間信息網絡的內容分發中，內容的流行度反映用戶對內容的偏好；由于用戶對數據請求的時變性，網絡中內容的流行度總是不停地發生變化；由業務服從Zipf分布模型知，各內容的流行度分布由下式表示：

其中，M為內容的總量；m為內容流行度的排名，m＝1,2,...,M；q為平滑因子，用于調節內容流行度的大小，z^m表示內容集合的集中程度，取值在[0.7,1.3]之間；

在各緩存節點中，將第l個內容的緩存狀態表示為f_l，且f_l∈{0,1}，表示是否緩存了內容l；整個網絡中的緩存內容集合為為每個區域中節點集合緩存的內容，每個區域中節點的緩存集合表示為：

其中，為第c_nk個節點的緩存；

在建立節點間協作關系模型時，用協作參數來反映區域間節點緩存同一內容的概率關系；根據用戶獲取內容的路徑知，地面內容源服務器中一定是存儲了全部內容的；因此，相鄰的節點間緩存相同內容的概率具有一定的協作關系；對于內容l的緩存，當靠近用戶的節點緩存了內容l時，分區內其他節點緩存該內容的概率表示為：

其中，表示為靠近用戶的節點緩存內容l的概率；表示節點c_nk是否緩存了內容；α為兩個節點間的協作緩存程度，用內容流行度和節點的緩存容量來表示：

ω₁+ω₂＝1 (11)

其中，為節點的緩存容量；ω₁為內容流行度所占的權重；ω₂為節點緩存容量所占的權重；

A3、優化目標函數

考慮到星間鏈路通常采用高速數據鏈路，且地面站與業務供應商之間也采用寬帶連接，因此用戶u對內容l的獲取時延，由星地傳輸時延t_g,s和星間傳輸時延t_s,d組成；星間傳輸時延t_s,d由下式計算出：

其中，d(s,d)為接入節點和命中目的節點的傳輸路徑的星間鏈路長度之和；

設用戶數量為U，每次請求產生的時延為t，則優化目標為：

在內容請求過程中，假定用戶u單次請求的內容數量為1，對內容l的請求為r_u＝[0,1,0,..0]_1×M，其中“1”表明其請求的目標內容，請求概率服從上式的Zipf分布；根據空間信息網絡緩存系統中的請求傳遞路徑，用戶的請求首先到達為之提供服務的接入衛星，并在該衛星所屬區域搜索緩存中內容；設定q_l,u為空間信息網絡緩存系統對該區域的搜索結果，其表示為：

其中，c_nk表示與用戶u相連接的編號為c_nk的節點；*為Hadamard相乘；q_l,u取值為1時，表示請求內容在該區域已經獲取到，q_l,u取值為0時，表示該請求需要被發送到下一個區域進行搜索；

因此在衛星網絡中，由內容傳輸過程從產生的系統時延可分為兩種情況，分別是當前區域內衛星節點緩存了目標內容和所有衛星未緩存目標內容；若當前區域內衛星節點緩存了目標內容，則空間信息網絡緩存系統時延表示為：

q_l,up_m(t_g,s+t_s,d) (15)

若整個空間信息網絡緩存系統均未緩存目標內容，需要去源服務器獲取，此時經過兩次星地傳輸時延，則空間信息網絡緩存系統時延表示為：

(1-q_l,u)p_m(2t_g,s+t_s,d) (16)

因此式(13)重寫為：

約束條件為：

從研究問題及約束條件得出，該算法的計算過程具有較高的復雜度；為解得上述目標函數最優解，采取改進人工蜂群算法解決空間信息網絡緩存系統協作緩存問題；

B、建立基于人工蜂群的緩存決策策略

建立空間信息網絡分區模型將空間衛星網絡拓撲結構進行分區后，得到一組分區后的節點集合C＝{C₁,C₂,...,C_n}，C_n＝{c_n1,c_n2,...,c_nk}，選擇出高流行度的內容緩存在這些節點中，求解出分區節點中最優的緩存決策策略，在搜索可行解時，考慮到節點間的協作程度；具體算法包括以下步驟：

B1、初始化蜜源和算法參數

初始化階段包括初始化算法參數和初始化蜜源；使用F表示人工蜂群算法中的蜜源，每一個蜜源表示衛星網絡的緩存決策策略，蜜源初始化中，一個蜜源表示一個可行解；某個蜜源表示為其中F表示整個網絡緩存內容集合，表示第c_nk個節點中緩存內容；nPop為人工蜂群算法中蜜源的個數，在人工蜂群算法中，雇傭蜂和偵查蜂數量保持一致，nLooker為觀察蜂數量；蜜源試驗限制Limit內沒有更新蜜源，雇傭蜂轉化為偵查蜂，終止條件為達到最大迭代次數MaxIt；

B2、雇傭蜂對算法鄰域解進行搜索

雇傭蜂對初始化后的蜜源進行鄰域搜索，用貪婪選擇的策略獲取質量更好的蜜源，將記錄下的蜜源位置和適應度值傳遞給觀察蜂，引導觀察蜂進一步搜索；然后計算每個蜜源F_i的適應度值fitness_i，并將其作為評判蜜源F_i優劣的標準；公式如下:

每次迭代的過程中雇傭蜂都在蜜源附近尋找新的可行解，在尋找新解的過程中交互分區后節點間的緩存內容信息，產生新解，具體公式如下，

式中，F^β表示鄰域內的新解；表示編號為C_n區域所緩存的內容集合，計算新蜜源的適應度fitness_β，以決定是否取代舊的蜜源；

B3、觀察蜂根據解信息選擇可行解

通過雇傭蜂提供的蜜源信息，通過適應度值計算得到觀察蜂選擇可行解的概率，觀察蜂采用輪盤賭的方式選擇跟隨哪一只雇傭蜂：

適應度值越大，蜜源食物越多，觀察蜂選中該蜜源的概率也越大，觀察蜂選擇蜜源之后，再依照式(22)～(24)繼續搜索鄰域蜜源信息，通過計算新蜜源的適應度fitness_i來確定是否替換舊的蜜源；

B4、偵查蜂舍棄蜜源尋找新解

設置一個門限值Limit，當一個可行解的迭代次數超過Limit次仍未找到更好的蜜源，那么就認為解空間陷入局部最優，則舍棄該蜜源；當一個可行解F被舍棄后，其對應的雇傭蜂就會轉化成偵查蜂，并由式(22)～(24)產生一個新的蜜源代替它。