基于Q 學習量子蟻群的微納衛星路由算法

張 然，高瑩雪，趙 鈺，丁元明

（1.大連大學 信息工程學院，遼寧 大連 116622；2.大連大學 通信與網絡重點實驗室，遼寧 大連 116622）

0 概述

微納衛星是指質量為1～100 kg，具有實際使用功能的衛星，其主要特點是體積小、重量輕、功耗低、隱蔽性好、機動靈活、可組網完成任務［1-2］。微納衛星網絡工作環境復雜，易遭受多種類的攻擊且承載的業務量多，所以對路由的安全性和服務質量（Quality of Service，QoS）提出更高要求，而傳統的衛星網絡路由技術由于通常只考慮了跳數的問題［3-5］，因此能同時保證數據傳輸的安全性和網絡業務QoS的路由算法成為目前研究的熱點。

文獻［6-7］分別提出了基于信任機制的安全路由算法，但這兩種算法在評估信任值時未考慮節點能量的影響。文獻［8-9］提出的信任機制可以防御常見的攻擊，但并不能均衡網絡中的負載，在計算當前信任值時也沒有考慮節點的歷史行為。文獻［10］提出一種多約束服務選擇機制蟻群路由算法，該算法根據網絡和用戶約束條件的路徑消耗指標評價路徑的好壞，但初期的收斂速度過慢，容易陷入局部最優解。文獻［11］提出的多目標蟻群路由算法減少了網絡的平均能耗，但是犧牲了算法的全局搜索能力。文獻［12-13］將量子計算與蟻群算法相結合，應用于求解QoS 路由，以量子比特編碼表示各條路徑上的信息素，并通過量子旋轉門實現對信息素的更新。

本文提出一種實現多目標優化的Q 學習量子蟻群路由算法（Q-learning Quantum Ant Colony Routing Algorithm，QQARA）。該算法綜合考慮路徑平均信任值和路徑費用兩個優化目標，同時在路徑費用函數中加入量子計算，并將蟻群算法中的信息素映射成Q 學習中的Q值，以保證數據傳輸的安全性和網絡業務服務質量。

1 相關機制及參數設計

在微納衛星網絡中，將網絡拓撲的基本模型抽象為無向圖G=｛V，E｝，其中，V表示網絡中所有微納衛星節點的集合，E={ei，j|i，j∈V}表示微納衛星網絡中的相鄰兩節點的鏈路集合，如圖1 所示。

圖1 微納衛星網絡結構Fig.1 Structure of micro-nano-satellite network

1.1 信任機制的建立

為解決微納衛星網絡中節點的惡意攻擊行為，識別異常節點，提高網絡的安全性，通過節點的直接信任值、間接信任值和能量信任值構成的整體信任值，建立節點信任機制。

1.1.1 直接信任值

直接信任值［14］是通過自身行為直接檢測計算得到的，包括攻擊行為信任值和轉發行為信任值。

攻擊行為信任值用來評估節點的惡意攻擊行為。當檢測出節點有惡意攻擊行為時，減少該節點的信任值，使節點獲得較低的信任程度，其計算公式如式（1）所示：

其中：ψ為指數衰減程度；tc、tc-1分別為當前、上一次檢測時間；為節點上一個攻擊行為的信任值；d(t)L為當前行為評估后量化的值。

其中：r(t)L為節點當前行為正常時的評估值；n(t)L為節點當前行為異常時的評估值。

轉發行為信任值用來評估微納衛星網絡中的自私攻擊行為。當節點成功轉發的數據包數量增加時，該節點的轉發行為信任值增加；當節點轉發失敗次數增加時，該節點的轉發行為信任值逐漸降低，其計算公式如式（3）所示：

其中：TS為節點成功轉發數據包的個數；TF為節點轉發失敗數據包的個數。

對節點的攻擊行為信任值和轉發行為信任值加權求和得到直接信任值TSE，如式（4）所示：

其中：ζ1、(1-ζ1)分別為轉發行為信任值和攻擊行為信任值的權重，取值范圍為［0，1］。

設定一個惡意節點門限閾值Tlower，在獲得某個節點的直接信任值后，一旦發現該節點的直接信任值低于門限閾值Tlower，則認為該節點為惡意節點，將該節點隔離，門限閾值Tlower具體大小根據具體情況取值。

1.1.2 間接信任值

間接信任值［15］是根據第三方節點的信任值得到，其計算示意圖如圖2 所示。

圖2 間接信任值計算示意圖Fig.2 Schematic diagram of indirect trust value calculation

假設節點i的鄰居節點mi連通域為YS，YS中共有n個鄰居節點存儲有節點j的直接信任值，則可得到i對j的間接信任值TRS計算公式如下：

對節點的直接信任值和間接信任值加權求和得到綜合信任值TSS：

其中：ζ2、(1-ζ2)分別為直接信任值和間接信任值的權重，取值范圍為（0，1］。

1.1.3 能量信任值

由于微納衛星的能量有限，如果不考慮節點剩余能量依舊使其頻繁工作，會導致綜合信任值較高的節點因耗能過快提前失效，退出網絡，因此在建立信任機制時還需要考慮節點的剩余能量。

節點在一次數據轉發的過程中所消耗的總能量Ecost，如式（7）所示：

其中：Eelec為節點在接收1 bit 數據所耗費的能量；N為節點收發數據分組的總比特數；Eamp為節點數據收發為滿足信噪比耗費的能量；d為兩節點之間的距離。

微納衛星節點完成傳輸后剩余能量Ecurrent，如式（8）所示：

其中：Einital為節點未參與數據傳輸時的剩余能量。

微納衛星節點當前剩余能量百分比Eper如下：

其中：Eentire為節點初始能量。

1.1.4 整體信任值

整體信任值TT是將綜合信任值和能量信任值進行加權求和得到，其計算公式如式（10）所示。計算過程如圖3 所示。

圖3 整體信任值計算過程Fig.3 Calculation process of overall trust value

1.2 QoS 度量參數

假設p為一條從源節點o到目的節點r的路徑，ei，j為路徑p上的一條鏈路，s為路徑p上的節點，則表示整個路徑QoS 的指標如下：

1）時延。路徑p處理時延delay(p)為該路徑上鏈路的傳輸時延delay(ei，j)與節點處理時延delay(si)之和：

2）出錯率。路徑p的出錯率loss(p)由該路徑上所有鏈路的出錯率loss(ei，j)共同決定：

3）跳數。路徑p的跳數hops(p)為該路徑上所有節點的數量之和：

4）帶寬。路徑p的帶寬bandwidth(p)為該路徑上所有鏈路中帶寬最小的鏈路的帶寬值：

1.3 節點負載情況

為避免網絡中部分節點出現負載過高的問題，需要考慮節點的負載情況，定義節點i的負載為Li，假設節點i的通信范圍內共有n個節點，則Lave為節點i通信范圍內的平均負載。

其中：q(x)為節點i在某時刻待發送的數據隊列長度；m為節點i處共有m組數據包等待發送。

1.4 鏈路持續時間

由于微納衛星具有一定的移動性，會出現鏈路中斷的問題，因此在選擇從源節點到目的節點的路徑時，還需要考慮路徑中鏈路的可持續時間，盡量選取鏈路持續時間長的路徑，減少因數據傳輸過程中出現鏈路中斷而造成數據丟失的現象。

在路徑p中存在相鄰的節點i和節點j，節點i的空間坐標為(xi，yi，zi)，速度向 量vi=νix，νiy，νiz，節 點j的空間坐標為(xj，yj，zj)，速度向量vj=νjx，νjy，νjz，則兩節點間距離d為：

設置節點間的最大通信范圍為R，當兩節點之間的距離d≤R時，兩節點可以正常通信；當節點間的距離d>R時，節點不在通信范圍內，兩節點之間的鏈路發生斷裂。根據兩節點之間的坐標位置和速度的移動方向，計算出路徑p中鏈路ei，j的預計可存活時間t(ei，j)：

則依據該路徑p中最先斷裂的鏈路，本次路由過程中可使用的存活時間talive為：

2 Q 學習量子蟻群路由算法

本文綜合考慮路徑平均信任值和路徑費用兩個優化目標，并將量子計算引入到蟻群算法的狀態轉移概率計算，同時將蟻群算法中的信息素映射成Q 學習中的Q值，以提高路由的整體性能。

2.1 多目標函數的建立

為能夠同時保證數據傳輸的安全性和網絡業務服務質量，把路徑的平均信任值和路徑的費用作為兩個優化目標，共同構成最優路徑的節點性能指標。

路徑的平均信任值是反映數據傳輸安全性的情況，路徑的平均信任值越大，數據傳輸安全性越高。以路徑上節點的信任值計算出路徑平均信任值作為第一個目標函數f1(p)，則具有hops 跳的路徑平均信任值如式（21）所示：

路徑的費用函數是反映所建立的路徑對于各項QoS參數的滿足情況，費用值越小，所建立路徑的QoS 指標越好。在微納衛星網絡中，多QoS 路由問題的設計目標就是找到一條或多條滿足以下約束條件的路徑，使得路徑p的費用值f(p)最小。本文以路徑的費用作為第二個目標函數f2(p)，為了保證計算時各參數單位的統一性，對各項QoS 參數進行歸一化處理。

其中：delaymax為業務可以容忍的最大時延；lossmax為業務能接受的最大出錯率；hopsmax為業務可以接受的最大跳數限制；bandwidthmin為業務可以承受的最小帶寬；delay(p)*、loss(p)*、hops(p)*分別為歸一化處理后的QoS 參數；ω1、ω2、ω3、ω4分別為時延、出錯率、跳數、帶寬的加權因子。

2.2 量子計算

量子計算［16-17］基本原理為：量子態由若干基本狀態組成，這些基本狀態可以進行疊加形成量子疊加態，當量子疊加態的相對位置和概率幅度方式變化時，就會使基本狀態的出現概率也產生相應的變化，從而使原本形成的疊加態也產生對應的形態改變。量子計算具備疊加、并行和干涉的特性［18］。

2.2.1 量子比特

量子比特［19］是量子計算中存儲信息的基本單元，使用|0>和|1>來表示微觀粒子的兩種基本狀態，記號“| >”為Dirac 記號，在量子計算中抽象為形態。與經典的比特不同，量子比特還可以形成疊加態，可以表示兩種狀態之間的中間態，即|φ>=α|0>+β|1>，其中α、β為復數，表示兩種狀態的概率幅，且滿足歸一化條件|α|2+|β|2=1，即量子態|φ>在測量時會以|α|2的概率轉換到|0>態或以|β|2的概率轉換到|1>態。

一個量子比特可以同時存儲|0>和|1>兩種狀態的概率幅，那么包含m個量子比特的個體pi能夠存儲2m種不同狀態，pi的概率幅度如式（25）所示：

2.2.2 量子旋轉門

在量子計算中使用量子旋轉門更新量子比特的概率幅，其更新方式如式（26）所示：

量子比特的旋轉角度θij如下：

其中：Δθij為旋轉角度的大小，表示量子比特從當前狀態旋轉至目標狀態所需要的步長大??；s(αij，βij)為旋轉角的方向。旋轉角的大小和方向根據旋轉角選擇策略查詢，如表1 所示［20］。在表1 中，xij=1 表示從節點i到節點j存在一條解路徑，bestij表示記錄運算過程中從節點i到節點j的最優解，f（x）為適應性函數，即建立路徑的費用函數f2(p)。

表1 旋轉角選擇策略Table 1 Rotation angle selection strategy

2.3 改進的蟻群路由算法

在傳統蟻群路由算法地基礎上，本文算法將量子計算引入到狀態轉移概率計算中，以避免陷入局部最優解，而且把蟻群算法中的信息素映射成Q 學習中的Q值，加快算法的收斂速度。

2.3.1 狀態轉移規則

設共有m只螞蟻隨機的分布在不同的節點上，表示在t時刻螞蟻k（k=1，2，…，m）從節點i移動到節點j的狀態轉移概率為：

其中：dij(t)為在t時刻節點i與節點j之間的距離；為路徑（i，j）的平均信任值。

其中：|αij|2表示從節點i到節點j的路徑上量子位的量子態坍縮到|0>的概率。

2.3.2 信息素更新規則

在全部的螞蟻完成一次循環之后，螞蟻路過某路徑時信息素濃度會發生變化，路徑的信息素濃度越高則越有可能成為最優路徑，同時信息素濃度會按照一定的系數揮發。

1）局部信息素更新規則

當每只前向螞蟻構建完一個可行路徑后，對所構建可行路徑上的各段鏈路進行各個目標的局部信息素更新，其計算如下：

其中：n為第n個目標函數（n=1，2）；1-ρ(0<ρ<1)為路徑上信息素的持久性因子，信息素通過揮發因子ρ持續揮發；Δnτij為第n個優化目標的信息素濃度增量。計算如式（34）、式（35）所示：

其中：κ為鏈路持續時間值的增強系數；talive為存活時間；f1(p)、f2(p)為目標函數；Ej-per為節點j剩余能量；Lj為節點j的負載；Lave為節點i通信范圍內的平均負載。

2）全局信息素更新規則

Q 學習是一種不基于狀態轉化模型，使用時序差分求解強化學習問題的方法［21-22］。本文引入Q 學習的思想，強化算法在動態環境中的學習能力，Q值更新規則如式（36）所示：

其中：使用Q（s，a）為動作a的累積回報值；χ∈（0，1）；δ為學習因子；rt+1為t+1 時刻根據環境狀態s選擇動作a獲得的收益。

將蟻群算法的信息素濃度映射為Q 學習的Q值，則蟻群算法中信息素更新規則為：

其中：Q為釋放的信息素濃度；Bdk為后向螞蟻走過的節點個數。

2.3.3 算法步驟

本文所提出的Q 學習量子蟻群路由算法流程如圖4 所示，具體步驟如下：

圖4 Q 學習量子蟻群路由算法流程Fig.4 Procedure of Q-learning quantum ant colony routing algorithm

步驟1初始化微納衛星網絡，設置源節點o和目的節點r，設定蟻群的螞蟻數量m，算法的最大迭代次數tmax，并設置算法中的各項參數。

步驟2設置和初始化各前向螞蟻的禁忌表，各前向螞蟻的禁忌表中用于存儲當前已經訪問過的節點ID，令前向螞蟻標記k=k+1。

步驟3各個前向螞蟻可訪問的節點范圍內，根據狀態轉移概率的計算公式選擇下一跳鄰居節點j。

步驟4判斷選擇的鄰居節點j的直接信任值是否大于惡意節點門限閾值Tlower，若節點j的直接信任值小于惡意節點門限閾值Tlower，則廣播通知其他節點將節點j從微納衛星網絡中隔離，并轉向步驟3 重新選擇鄰居節點，否則轉向步驟5。

步驟5判斷選擇下一跳節點j后所形成的鏈路是否滿足QoS 需求，若不滿足其中的某一項QoS 指標則返回步驟3，否則轉向步驟6。

步驟6前向螞蟻根據狀態轉移規則選擇下一個移動位置后，通過量子旋轉門完成自適應的更新。

步驟7前向螞蟻k根據不同的目標函數進行相應的局部信息素的更新，并把選擇的鄰居節點j放入到禁忌表中。

步驟8循環執行步驟3～步驟7，直到所有的前向螞蟻到達目的節點并轉換為后向螞蟻。

步驟9后向螞蟻進行全局的信息素更新，令迭代次數t=t+1。

步驟10判斷是否滿足結束條件t>tmax，若滿足則輸出最優解，根據算法計算出的最優路徑傳輸數據，否則轉向步驟2。

3 實驗仿真與結果分析

本文用Matlab 仿真驗證所提出QQARA 算法的性能。微納衛星的初始拓撲采用銥星星座的分布方式，即共有66 顆微納衛星，6 條軌道，并且每個軌道都均勻分布11 顆微納衛星，每顆衛星與其他4 顆衛星直接相連接，其仿真參數如表2 所示。

表2 仿真參數Table 2 Simulation parameters

為驗證QQARA 算法能否滿足網絡各種不同業務QoS 需求，在網絡中分別設置對帶寬要求敏感的大文件傳輸業務，對時延要求敏感的實時傳輸業務和對丟包率要求敏感的下載業務，各種不同業務的QoS 參數約束條件如表3 所示。

表3 不同業務的QoS 約束條件Table 3 QoS constraints for different services

本文實驗將QQARA 算法與常見的蟻群優化（Ant Colony Optimization，ACO）算法、改進的QoS（QoS aware Service Selection，QSS）算法［23］進行對比分析，分別從路徑的費用值、包投遞率、平均端到端時延、節點的平均能耗4 個性能指標驗證QQARA 算法的有效性。

1）路徑的費用值

圖5 所示為不同算法隨著迭代次數增加時的路徑費用變化趨勢。隨著迭代次數的不斷增加，3 種算法的路徑費用值f2(p)都呈現出不斷下降的狀態。由于ACO 算法只考慮了尋找最短路徑而沒有QoS 參數的問題，因此下降速度最慢且數值最高，而QSS 算法和QQARA 算法在尋找最優路徑時考慮了路徑的各項QoS 參數，因此這2 種算法路徑費用值的下降速度和最小值都明顯優于ACO 算法。由于QQARA算法結合了Q 學習的優點，因此QQARA 算法的收斂速度最快。

圖5 迭代次數與路徑費用的關系Fig.5 Relationship between iteration times and path cost

2）包投遞率

圖6 所示為在不同的節點移動速度下3 種算法的包投遞率變化情況。隨著節點移動速度的增大，3 種算法的包投遞率均出現了不同程度的下降趨勢。由于QQARA 算法加入了量子計算，能夠很好地跳出局部最優解，具有更好的路徑尋優能力，且在信息素濃度更新的過程中考慮了節點的狀態以及鏈路的持續時間，即使在節點具有一定移動速度的情況下仍能保持一定程度的包投遞率，因此，所尋找的最優路徑更加穩定。

圖6 節點移動速度與包投遞率的關系Fig.6 Relationship between node movement speed and packet delivery rate

3）平均端到端時延

圖7 所示為節點移動速度與平均端到端時延的關系。由圖7 可知，隨著節點移動速度的逐漸增加，3 種算法的平均端到端時延也呈現出了不同程度的上升趨勢。QSS 算法和QQARA 算法在選擇下一跳節點時考慮到了節點的狀態，減少了因節點失效而導致時延增加的問題。由于QQARA 算法加入了對鏈路持續時間的考慮，減少了因鏈路中斷和路由修復帶來的延遲，因此隨著節點移動速度的不斷增加，QQARA 算法的平均端到端時延明顯優于QSS 算法和ACO 算法。

圖7 節點移動速度與平均端到端時延的關系Fig.7 Relationship between node moving speed and average end-to-end delay

4）節點平均能耗

圖8 所示為節點的移動速度與節點平均能耗的關系。隨著節點移動速度的增加，3 種算法的節點平均能耗均出現上升的趨勢。由于ACO 算法和QSS 算法在選取數據傳輸路徑時沒有考慮鏈路的持續時間，在節點移動而導致鏈路斷開的情況下會產生大量的數據重傳，增大了節點的能量消耗，因此該算法的節點平均能耗隨著節點移動速度上升而大幅增加。由于QQARA算法加入了對鏈路連接持續時間的考慮，能夠有效減少因鏈路中斷而造成數據重傳產生的能耗。同時，在選擇路徑時考慮到了節點的剩余能量問題，起到了能量均衡的作用。

圖8 節點移動速度與節點平均能耗的關系Fig.8 Relationship between node moving speed and node average energy consumption

4 結束語

本文提出一種實現多目標優化的Q 學習量子蟻群路由算法。該算法考慮路徑平均信任值和路徑費用，保證數據傳輸的安全性和網絡業務服務質量，通過加入量子計算避免陷入局部最優解，將信息素映射成Q值，加快算法的收斂速度。仿真結果表明，該路由算法有效地改善了包投遞率、平均端到端時延和節點平均能耗等性能指標。下一步將在優化目標中增加影響微納衛星網絡傳輸因素，提高路由算法對不同場景的適用性。