面向海洋觀監測傳感網的計算卸載方法研究

蘇新，薛淏陽，周一青，朱金秀

（1.河海大學物聯網工程學院，江蘇 常州 231022；2.中國科學院計算技術研究所，北京 100190）

1 引言

海洋觀監測傳感網作為海洋信息網絡的重要組成部分可提供多種觀監測應用，是匯聚海洋空間、環境、資源等各類數據的重要平臺。全天候、全自動的海洋觀測和目標態勢感知、海洋信息傳輸，以及海上綜合業務服務的開展，提出了實時定位、緊急救援以及面向某些領域的低時延信息服務需求，這對海洋觀監測傳感網支持低時延高可靠的觀監測應用提出了極高的要求。進入5G/6G時代[1-2]，海洋觀監測傳感網絡終端設備（OUE,oceanic user equipment）對于低時延高可靠的應用需求隨之增加，需要全新的數據處理方式以滿足相關應用需求。

2014 年，歐洲電信標準協會提出了移動邊緣計算概念，并于 2016 年擴展為多接入邊緣計算（MAEC,multi-access edge computing）[3]。其主要思想是將云計算的部分業務下沉至網絡邊緣，在用戶邊緣分布式地部署服務與存儲，以快速地為用戶提供服務，極大減少回傳網絡帶寬[4]。在網絡邊緣就近處理數據的邊緣計算方式可實現終端用戶對低時延、高可靠的要求[5]。因此，將邊緣計算關鍵技術引入海洋觀監測傳感網以滿足低時延、高可靠的海事應用需求具有極高的研究意義和應用價值。

計算卸載技術作為邊緣計算的關鍵技術，對降低用戶執行時延，提升用戶服務質量起著重要作用[6]。現階段邊緣計算卸載技術研究主要圍繞陸地組網與車聯網，普遍根據其組網特征進行研究[7-8]。由于海洋環境復雜多變，不能簡單地將現有陸地組網中的MAEC 卸載技術應用于海洋觀監測傳感網。因此，將MAEC 卸載機制引入海洋觀監測傳感網的研究會面臨以下挑戰。

1) 海洋場景節點密度變化明顯，邊緣計算資源分布不均，調度困難，網絡節點計算與通信資源存在差異。例如，各個節點對時延和能耗的敏感度不同，網絡局部產生的大量數據會導致網絡超負荷處理，系統面臨癱瘓危險。

2) 海洋觀監測傳感網終端設備移動速度不同，網絡拓撲變化快，節點間通信范圍存在差異且有效通信時間不同，容易導致傳輸鏈路中斷。

通過參考MAEC 卸載技術在陸地組網及車聯網中的研究[7]，結合海洋觀監測傳感網中存在的挑戰，本文以滿足低時延、高可靠的海事應用需求為目標，研究了海洋觀監測傳感網中的MAEC 卸載技術，主要貢獻如下。

1) 針對節點密度差異化下的卸載問題，提出了以下2 種卸載模型：在網絡節點高密度的近岸區域，計算資源豐富，多用戶計算卸載可用多個獨立的單用戶多邊緣節點模型等效；在網絡節點低密度的遠岸區域，計算資源匱乏，多用戶計算卸載需考慮協同，提出遠岸雙跳多用戶模型。同時，闡述了一種基于海洋網絡連通概率的邊緣節點選取方法，使終端用戶可選取該區域內有利于其卸載傳輸的最佳節點。

2) 提出了節點間有效通信時間約束，并分別引入近岸和遠岸2 種卸載模型，保證了用戶數據卸載時網絡的連通效率。

3）在選取邊緣計算節點基礎上，提出了2 種計算卸載算法，在2 種卸載模型下實現了用戶卸載時的最佳決策和資源調度，解決了節點間資源差異導致的網絡成本增加的問題。

2 相關工作

計算卸載相關研究工作按照系統模型可分為單用戶設備（SUE,single user equipment）計算卸載和多用戶設備（MUE,multi-user equipment）計算卸載，本文將分別對這2 種工作進行分析與討論。

2.1 單用戶設備計算卸載

目前，針對SUE 計算卸載的研究主要分為單用戶與單個MAEC 服務器（簡稱為SUE-SMAEC）、單用戶與多個MAEC 服務器（簡稱為SUE-MMAEC）。

文獻[9]針對SUE-SMAEC，運用一維查詢算法根據UE和MAEC服務器的計算資源及其之間的信道特征找到最優的卸載策略，實現最小化執行時延的目標。然而，文獻[9]未考慮能耗約束會導致UE 能耗過高。為同時滿足UE 對時延與能耗的要求，文獻[10]提出了在滿足應用執行時延的同時最小化用戶能耗的卸載策略。優化方法引入了在線學習和離線預先計算2 種卸載方案。與全部卸載相比[9-10]，部分卸載更靈活，允許用戶將任務在本地和MAEC 服務器分別執行。文獻[11]假設UE 應用由多個子任務組成，各任務之間相互依賴，并提出了基于二元粒子群的卸載算法，使部分卸載相對于全部卸載具有顯著的節能效果。

針對車聯網下的計算卸載，文獻[4]研究了在SUE-MMAEC 中任務分配和卸載決策的問題。文獻[4]雖然考慮了節點移動性，但并未對其可能產生卸載中斷問題進行分析解決。針對車聯網中車輛快速移動導致的卸載中斷問題，文獻[12]提出了一種避免傳輸中斷的自適應卸載策略，考慮車速、傳輸速率等因素對卸載的影響，并根據這些因素動態調整卸載策略，避免卸載過程中的傳輸中斷。

目前，SUE 計算卸載的研究主要圍繞陸地組網和車聯網 2 種場景，且多數卸載方案僅考慮SUE-SMAEC 的全部卸載和部分卸載，較少考慮多MAEC 服務器協同處理的卸載方式。

2.2 多用戶設備計算卸載

通常，由于MAEC 系統中通信和計算資源有限，難以滿足過多終端用戶的計算卸載需求，且分布式計算場景之間難以達到MAEC 資源的有效利用[13]。因此，學者們開始關注MUE 場景下的卸載研究，以實現資源的合理分配。

文獻[14]將MUE 系統中資源分配表述為一個非線性問題，提出一種基于貪婪策略的資源分配方案，有效地降低了終端能耗。不同于通過貪婪策略進行資源分配，文獻[15]提出了閾值結構的資源分配策略。在時分多址MUE 系統中，通過本地計算能力和信道增益的卸載優先級函數確定用戶優先級，基站根據用戶優先級與閾值間的關系，決定用戶卸載的數據量。文獻[16]綜合考慮卸載決策、信道狀態、計算資源等影響因素，將超密集網絡下的計算卸載模型表述為一個混合整數非線性規劃問題，設計了一種結合遺傳和粒子群的優化算法，以此實現最優資源分配。

以上方案均從降低系統時延或能耗角度出發，并未從用戶對能耗和時延的敏感程度差異角度對系統時延和能耗進行綜合優化。文獻[17]在MUE-SMAEC 系統中，首先針對用戶對能耗和時延差異度，為其設置相應能耗時延優化比；再將卸載決策和資源分配的優化表述為非凸優化問題，通過鯨魚遺傳算法解決不同用戶需求；最終實現資源分配。但文獻[17]中算法的迭代速度相對較慢，增加了系統成本。針對計算資源分布不均的問題，文獻[18]在MUE-MMAEC 系統中通過主輔MAEC 服務器協同處理的方式，運用模擬退火算法進行卸載決策和資源分配的聯合優化，解決了資源分布不均導致的資源調度困難問題。

基于以上論述，現有MUE 計算卸載研究主要以減少終端能耗和任務執行時延為優化目標，對綜合考慮優化任務時延和終端能耗的研究較少，且均未考慮MUE 系統中計算卸載的可靠性。算法迭代速度都相對較慢，難以保證較小的計算卸載成本，無法滿足海洋觀監測傳感網的各類海事應用需求。

3 海洋網絡系統模型

圖1 展示了本文提出的海洋網絡系統模型，通常，距離海岸37.04 km（即20 海里）為近岸海域，海域界限向外一側的為遠岸海域[19]。海洋網絡中，不同海域節點密度差異明顯，近岸海域由于海事活動較頻繁，通常其網絡節點密度高于遠岸海域。

在海洋網絡中，網絡節點一般包含大型船舶、浮標、小型船只、水下機器人以及基站等。小型船只和浮標由于自身資源有限，一般難以獨自完成數據處理，需要傳輸至其他節點進行處理。大型船舶與基站等相比浮標等節點計算能力較強，可充當邊緣計算節點來處理終端用戶卸載的數據。通常，基站計算能力強于大型船舶，在近岸海域，可通過多個海岸基站與大型船舶協同實現用戶的計算卸載；在遠岸海域，由于海域范圍廣，大規模建設成本投入大等因素，本文考慮在遠岸海事活動頻繁的海域建設1～2 個大型海上基站保證海事應用需求，盡可能地利用現有設施滿足海事應用需求。

結合相關工作討論可知，單用戶模型一般用于解決資源豐富情況下如何實現高效卸載決策與資源調度，以滿足OUE 應用需求的問題。近岸海域計算資源豐富，某一區域內可用計算資源較多，需要考慮OUE 如何充分利用資源，以滿足自身需求。因此，結合單用戶模型特性，近岸海域本文提出單用戶多邊緣節點模型。如圖1 所示，該模型主要由集中控制單元、邊緣計算節點（包含海岸基站、大型船舶等）以及OUE（包含浮標、小型船只等）組成。OUE 可以通過多個邊緣計算節點協同處理計算任務，調度近岸豐富的計算資源以滿足自身需求。

圖1 海洋網絡系統模型

多用戶模型一般用于解決資源匱乏時如何實現資源的合理分配利用，以滿足多個用戶的卸載需求。遠岸海域計算資源匱乏，在同一區域內多個用戶同時卸載可用計算資源相對較少，需要考慮有限資源的合理分配。此外，遠岸海域范圍廣，節點離散化分布，OUE 可能遠離海上基站（OBS,offshore base station），這使遠離OBS 的OUE 需要多跳傳輸完成卸載。通常，多于兩跳的卸載由于時延與能耗開銷巨大，不符合低時延高可靠的海事應用需求。因此，如圖1 所示，本文面向遠岸海域提出了雙跳多用戶模型，主要由OBS、中繼節點（大型船舶等組成）、K個OUE 等組成。OUE 可將計算任務卸載至OBS 和各自的中繼節點，從而在滿足OUE 卸載的同時，實現資源的合理分配。

由于海洋網絡節點間資源差異明顯，OUE 計算卸載能耗與時延受到邊緣節點資源影響。如OUE 任務卸載至通信條件較好、計算能力較強的節點，卸載時延較低。需要OUE 選取合適的邊緣計算節點使OUE在計算卸載時擁有良好的卸載條件十分必要。本文結合前期研究基礎[19]提出基于海洋網絡連通概率的邊緣計算節點選取方法，該方案適用于近岸與遠岸2 種場景，包含海洋網絡連通概率預測和邊緣計算節點確定2 個步驟，具體如下。

圖2 為相鄰船舶通信示意。基于前期對海洋網絡中節點間連通概率預測研究[19]，船與船之間連通概率為

其中，ρmob表示船舶密度（艘/海里，與船舶速度有關），S(x,r)表示船A 與船B 通信范圍交集（如圖2中灰色區域所示），B表示S(x,r)內存在船舶的數量，P(B=0,S(x,r))為兩船通信范圍內沒有船舶的概率，x和r分別表示兩船間距離和船舶通信半徑，且x、r與S(x,r)存在如下關系

圖2 相鄰船舶通信示意

圖3 為船舶與基站通信示意。船舶與基站間連通概率受兩基站間距離L、基站覆蓋半徑R、船舶通信半徑r及船舶到基站的距離x影響。結合圖3給出了基站與船舶連通概率Ps[19]。

1) 當0＜L≤2R，x∈[ 0,L]時，Ps=1。

2) 當2R＜L≤2R+r，x∈(0,R) ∪(L?R,L)時，Ps=1。

3) 當2R＜L≤2R+r，x∈(R,L?R)時，

4) 當 2R+r＜L≤2R+2r，x∈(0,R)∪(L?R,L)時，Ps=1。

5) 當2R+r＜L≤2R+2r，x∈(R,L?R)時，

6) 當L＞2R+2r時，

圖3 船舶與基站通信示意

根據以上船?船、船?基站之間連通概率，可求得OUE 與該區域內各節點之間的連通概率。將連通概率大于閾值Py的節點作為連通節點，可保障良好的計算卸載通信條件。

基于海洋網絡連通概率預測模型，選擇網絡中計算能力和通信資源較好的海洋連通節點作為OUE 的邊緣計算節點。可通過式(6)計算具體OUE與第k個連通節點之間的邊緣系數Sk∈(0,1)，根據每個連通節點的邊緣系數與閾值Sy之間的關系確定邊緣計算節點。

其中，μ+η+γ+?=1。

當Sk≥Sy時，選取第k個連通節點作為OUE邊緣計算節點。式(6)中第一部分表示第k個連通節點的剩余能量占OUE 所有連通節點能量和的比重，值越大表示該節點相對OUE 的其他節點的能量優勢越大；第二部分為OUE 與第k個連通節點間的信噪比SNRoue?k在OUE 所有連通節點中的占比，值越大表示該節點與OUE 間的傳輸條件越好；第三部分表示第k個連通節點的計算能力fk在OUE 所有連通節點中的占比，值越大表示該節點相比OUE 的其他節點計算能力越強；第四部分為OUE 與第k個連通節點之間的距離doue?k占OUE 所有連通節點距離和的比重，值越小表示該節點與OUE 間的數據傳輸能耗與時延越小。

4 基于多點協同的近岸計算卸載方法

4.1 近岸海域卸載流程描述

OUE 多應用并行執行（如自動定位系統、資源探測應用、娛樂應用等）會集中產生大量需要實時處理的數據。假設數據D可被分割成N個不同數據量的計算任務，表示為N={Nloc,Noff}={τ1D,τ2D,…,τnD}，其中Nloc和Noff分別表示在本地執行或計算卸載的任務數量；τnD表示任務n需要處理的數據量，τn表示任務n數據量分配比例且

當OUE 發送卸載請求至集中控制單元，控制單元通過獲取OUE 附近節點信息，制定最佳卸載方案。控制單元將卸載方案XN={x1,x2,…,xn}（其中，xn表示任務n卸載至編號為xn的邊緣計算節點，xn=0表示本地執行）發送至OUE。OUE 按照卸載策略將任務分別在本地處理或卸載至不同的邊緣計算節點。各邊緣計算節點將執行結果回傳至OUE。

當任務n在本地執行時，需要處理的數據量為τnDbit 。設本地計算能力為foue（即每秒CPU 周期數），cn為計算1bit 數據所需的CPU 周期數，與任務復雜度有關。設Ploc為OUE 的計算功率，因此任務n在本地處理所需時間和能耗可表示為

當任務n卸載至邊緣計算節點執行時，由于海洋觀監測傳感網中各節點具有移動性且軌跡不同；OUE 在卸載時，首先需要考慮OUE 與邊緣計算節點間的有效通信時間，確保OUE 在計算卸載時不會出現通信中斷的問題。如圖4 所示，可設船A 速度為v1，船B 速度為為速度v2與i軸的夾角），當船B 進入船A 有效通信范圍時，直線A—B與i軸夾角為β。另設船B進入船A有效通信范圍后沿線路行駛，則船A與船B 有效通信時間為

圖4 相鄰兩船通信示意

在保證卸載不會中斷之后，任務n卸載時，設fmaec(xn)為邊緣節點xn的計算能力，Ptran表示OUE傳輸功率，任務n卸載所需時間為

近岸海域OUE 的總執行時間Toue受卸載決策XN和任務分配系數τ影響。由于各任務之間可并行執行，卸載部分所用時間取決于邊緣節點中執行時間的最大值。為了最小化OUE 時延，近岸區域卸載時延優化目標如式(12)所示，其中第一部分表示本地計算部分的總執行時延，第二部分表示卸載部分的總執行時延。約束a 表示任務卸載執行時延不大于任務n本地計算時延及OUE 與邊緣節點xn的通信時間；約束b 表示任務n卸載能耗不超過該任務本地計算能耗；約束c 表示各任務的數據量之和應等于OUE 需要處理的總數據量；約束d 表示每個任務只能卸載至一個邊緣節點。

4.2 近岸海域多節點協同卸載優化方法

為了解決近岸多節點協同機制下卸載優化問題，本文提出一種基于海洋多節點協同卸載的遺傳算法（MCO-GA,maritime multi-node cooperative offloading based genetic algorithm）。該算法通過對遺傳算法（GA,genetic algorithm）中編碼方式及適應度函數的優化與改進，使OUE 在尋找到最優卸載策略的同時可有效降低時延。

4.2.1遺傳算法

GA 通過模擬自然進化過程來搜索最優解，染色體編碼時每條染色體經過編碼可以看作優化問題的一種解。染色體的編碼影響后續的交叉、變異操作，很大程度上決定了GA 的進化效率。適應度函數是根據目標函數確定的用于區分種群中個體好壞的標準。在染色體種群中，個體的適應度值越大，表明該個體越適應環境。

選擇操作以一定概率從種群中選擇若干個體。選擇過程基于適應度優勝劣汰機制。通過計算，每個染色體被賦予一個適應度值，這些值與個體被選擇的概率相關。本文卸載優化策略采用輪盤賭選擇方式[20]，假設種群數量為S，A1,A2,…,Ai表示當前種群中每個可能解，個體i的適應度為fitness(Ai)，因此該個體被選中的概率為

在進行交叉操作時，本文采用單點交叉的方式且交叉概率為PJ，具體操作是在個體編碼串中隨機設定一個交叉點，實行交叉時，該點前或后2 個個體的部分結構互換，從而生成2 個新個體。在變異操作中本文采用基本位變異方式，變異概率為Pm，隨機指定一位或多位點做變異運算得到新個體，可防止算法過早收斂。

4.2.2基于海洋多節點協同卸載的遺傳算法

MCO-GA 通過對超出可行域的染色體增加懲罰值，使其適應度值減小，在選擇操作時不易被選中；把近岸約束優化問題轉化為無約束問題，最終實現在可行域內的最優計算卸載策略求解。

在對優化變量進行編碼時，由于采用固定邊緣節點與移動邊緣節點協同卸載的策略；因此需要對OUE 每個邊緣節點進行編號后，將OUE 各任務進行卸載的邊緣計算節點編號及各邊緣節點的任務分配比例采用二進制編碼的方式表示在每條染色體上。其中，任務卸載的邊緣計算節點編號及任務分配比例分別用卸載決策XN和數據量分配比例τ表示。優化變量編碼過程如圖5 所示，x1?xn，τ1?τn分別表示任務卸載決策和任務分配比例。圖5 中列舉了卸載決策變量x1的二進制表示方法，其他變量同理。

圖5 優化變量編碼過程

由于GA 面向非約束優化過程，而本文考慮了約束優化問題。因此，需要通過引入懲罰函數將約束優化問題轉化為無約束優化問題進行分析，且適應度函數可表示為

其中，penalty(Ai)為懲罰函數（通過對非可行解的個體增加懲罰值使其被選擇的概率降低），表示為

其中，l1和l2為正懲罰因子。

結合海洋船舶運動軌跡的特殊性[19]，需要考慮船舶間速度方向不同以及通信半徑差異產生的通信時間變化問題。因此，懲罰函數考慮了有效通信時間（式(9)）等因素，從而避免了OUE 計算卸載時通信中斷問題。懲罰函數通過對卸載能耗進行約束，保證了OUE 計算卸載時較低的能耗。

4.2.3基于MCO-GA 的優化策略

本文中每條染色體表示一種卸載策略Ai，其中每一種卸載策略Ai包括卸載決策XN與數據量分配比例τ。此外，卸載策略Ai交叉變異操作前后的適應度可分別用fitness(Ai)與fitnessn(Ai)表示，適應度值包括該卸載策略下 OUE 對應的執行時延Toue(Ai)及相應的懲罰值penalty(Ai)。圖6 描述了MCO-GA 的流程，具體如下。

圖6 基于MCO-GA 算法的優化策略流程

輸入邊緣計算節點計算能力fmaec(xn)、OUE計算能力foue、任務數量N、OUE 本地計算功率Ploc、OUE 傳輸功率Ptran和任務n計算復雜度cn。

輸出最優卸載決策XN、最優數據量分配比例τ、最優卸載策略對應時延。

步驟1初始化。確定迭代次數itera_num 與染色體數量S（每次迭代不同的卸載策略數目），同時設置卸載策略交叉操作與變異操作的概率分別為PJ和Pm，在可行域內隨機產生S個卸載策略。

步驟2計算適應度。根據式(14)的適應度函數計算每種卸載策略對應的適應度。

步驟3選擇操作。根據式(13)計算每種卸載策略Ai被選中的概率Pi，將本次迭代中所有可能的卸載策略按照其概率大小進行累加排序。同時均勻產生S個0～1 的隨機數Pr。若Pi＞Pr，則選擇該卸載策略進行后續操作，直至選出足夠數量的卸載策略。

步驟4交叉操作。每2 種卸載策略一組，被賦予0～1 的隨機數Pcr（該值作為是否進行交叉操作的判斷依據）。若Pcr＜PJ，則該組2 種卸載策略進行交叉操作，產生2 種新的卸載策略；否則2 種策略保持不變。

步驟5變異操作。每種卸載策略被賦予0～1的隨機數Pmr（作為是否進行變異操作的判斷依據）。若Pmr＜Pm，則隨機選取該卸載策略上3 個點位進行變異操作。

步驟6更新種群。計算交叉變異操作后卸載策略Ai對應的適應度 fitnessn(Ai)，若fitnessn(Ai) ＞fitness(Ai)，則替換交叉變異前的卸載策略Ai。

步驟7終止條件判斷。終止條件根據迭代次數itera_num 判斷。若滿足迭代次數，則選擇出適應度值最小的卸載策略并退出循環；否則繼續執行步驟3～步驟6，直至滿足條件。

步驟8輸出最優卸載策略Ai及對應時延Toue(Ai)。

5 基于容錯重傳機制的遠岸計算卸載方法

5.1 遠岸海域卸載流程描述

遠岸海域計算資源相對匱乏且海域環境復雜，節點間通信鏈路易受到惡劣環境因素的影響而導致卸載失敗。提出容錯重傳機制計算卸載方法考慮節點間可能出現的通信故障十分必要，可保證遠岸海事應用的可靠性。

設遠岸系統模型中繼節點M={m1,m2,…,mk}（mk表示第k個OUE 的中繼節點），OBS 計算能力強于中繼節點，且OBS 與每個中繼節點均可作為邊緣計算節點。另設OUE 計算任務可分割，每個OUE 只能選擇一個中繼節點連接OBS。一般情況下，K個OUE 可同時向控制單元發送卸載請求。控制單元收到請求后為OUE 制定相應卸載策略。

OUEk全部任務在本地執行時延與能耗可表示

當ak=0且OUEk子任務在mk執行時，需要處理的數據量為設中繼節點mk計算能力為，子任務卸載至mk執行時延可表示為

綜上所述，容錯機制下的計算卸載模型中，OUEk總執行能耗與時延可分別表示為

其中，twait為OUEk的等待時延，表示當OUEk在任務計劃完成時間內未收到卸載任務的執行結果，則啟動容錯機制，先將原計劃完成時間延長，若還未收到OBS 執行結果，則認為任務卸載失敗，隨后ak=0時分配給OBS 的任務做重傳處理。由于不同OUE 對于能耗和時延的敏感程度存在差異。在計算卸載時要綜合考慮OUE 對時延和能耗的要求，和IE,k分別表示OUEk在綜合優化時所要求的時延和能耗比重，可根據OUE 需求進行調整。OUEk在執行任務時總開銷（時延和能耗）為

遠岸計算資源匱乏區域可容錯機制下，K個OUE 計算卸載受制于每個OUE 正常執行與故障執行下的任務分配比，以及正常執行情況下OBS 的計算資源分配比。針對不同OUE 的實際使用需求，遠岸容錯機制下卸載開銷優化問題可由式(31)表示，其中λ={λL,λM,λB}且λL、λM、λB分別為K個OUE 在本地、中繼節點、OBS 的任務分配比例集合。λre={λLre,λOre}，λLre、λOre分別表示重傳情況下K個OUE 在本地和中繼節點的任務分配比例。約束a 表示OUEk任務執行總時延不超過節點間有效通信時間及任務全部本地執行的最小值；約束b表示OUEk任務執行能耗不大于任務全部本地執行的能耗；約束c 表示正常執行和重傳執行的任務分配比例取值范圍；約束d 表示正常執行情況下，任務分配比例的和約束；約束e 表示重傳情況下，任務分配比例的和約束；約束f 表示OBS 分配給K個OUE 計算資源不大于OBS 計算資源。

5.2 遠岸海域可容錯卸載優化方法

為解決遠岸計算卸載優化問題，本文提出基于分組交叉學習的粒子群優化（GCL-PSO,group cross learning based particle swarm optimization）算法。由于此時優化變量和問題約束條件增多，傳統群智能算法在求解問題時容易陷入局部最優。GCL-PSO 算法在傳統PSO 算法基礎上引入分組競爭學習，通過每個粒子分組交叉競爭學習，使其能夠全面地在可行域內搜索最優解。GCL-PSO 算法較一般算法收斂速度快，處理復雜問題時能夠實現快速優化。

5.2.1傳統PSO 算法

PSO 算法設置粒子總數為particle_num，包含位置與速度因素[21]。第i個粒子的位置可看作優化問題的一種潛在解Qi，第i個粒子的速度hi表示粒子i位置更新的方向與距離。尋優過程中粒子i搜索到自身最優的位置表示為pbesti，粒子群中搜索到群體最優的位置表示為gbest。粒子i位置與速度更新計算過程表示為

其中，j表示迭代次數，ω為慣性因子（值較大時全局尋優較強，值較小時局部尋優能力較強）；c1,c2為學習因子；r1和r2為0～1 的隨機數。

5.2.2基于分組交叉學習的粒子群優化算法

本文為遠岸卸載優化問題提出GCL-PSO 算法。結合傳統PSO 算法中調節參數少、收斂速度快等優點。所提算法先對每個粒子進行分組，使其在小組內先進行局部學習，再通過粒子更新式進行全局學習。下面將介紹GCL-PSO 算法的具體實現過程。

GCL-PSO 算法初始化粒子參數后，將每個粒子進行隨機分組。分組后根據適應度大小在組內排序。組內每個粒子依據排序順序在組內相互學習，學習方式采用GA 的交叉操作。組內適應度較差的粒子通過向適應度較好的粒子學習獲取新粒子，并將新粒子的適應度與交叉前的粒子適應度比較。若適應度優于交叉前的粒子，則將交叉前的粒子替換為交叉后的粒子，再將新粒子與當前個體極值與全局極值比較。若適應度優于當前個體極值或全局極值則將其替換，否則舍棄新粒子。

分組學習后將每個粒子從分組中拆分出來（下次迭代重新分組），根據分組學習后輸出的pbesti與gbest，更新式(32)和式(33)進行全局學習，通過不斷調整每個粒子位置與速度最終找到優化問題的最優解。

5.2.3基于GCL-PSO 算法的優化策略

GCL-PSO 算法相關參數與遠岸卸載優化問題相關參數間的映射關系如表1 所示。

表1 GCL-PSO 算法參數與卸載策略參數映射

輸入OUE 數量K、OUE 計算能力fk、中繼節點計算能力、基站計算能力fOBS、OUE 本地計算功率、OUE 傳輸功率、OUE 傳輸帶寬Wk、中繼節點傳輸帶寬和OUE 任務復雜度系數ck。

輸出最優卸載策略和最優策略對應系統成本。

步驟1初始化。確定迭代次數GCL_itera 與粒子數量particle_num（每次迭代產生的卸載策略數量）在可行域內設置每個粒子初始位置QiN(j)與速度hi(j)。

步驟2系統成本計算。根據式(31)所示的優化問題計算正常情況下每種卸載策略所對應的系統總成本Ci(j)。將前j次迭代中粒子i系統成本最小時所對應的卸載策略設置為粒子i當前的個體極值pbesti(j)，同時設置當前粒子群中系統成本最小的粒子所對應的卸載策略為全局最優卸載策略gbest(j)。

圖7 GCL-PSO 優化方法流程

步驟3卸載策略分組競爭學習。每3 種卸載策略為一組進行隨機分組。在組內按照每種策略所求得的系統成本Ci(j)對卸載策略進行排序，排序后系統成本值最大的策略采用交叉方式向組內次優策略學習，次優策略向成本值最小的策略學習。

步驟5粒子全局學習。根據式(32)和式(33)更新粒子i當前速度hi(j)與卸載策略每個粒子根據當前個體極值pbesti(j)與全局極值gbest(j)不斷調整自身卸載策略。

步驟6更新全局學習后參數。求解全局學習后新粒子對應的系統總成本，根據系統成本更新每個粒子的個體極值pbesti(j)和全局極值gbest(j)。

步驟7終止條件判斷。終止條件根據迭代次數進行判斷。若滿足迭代次數則退出循環，輸出正常執行時的最優的卸載策略gbest(j)以及對應系統成本C(gbest(j))。若不滿足則繼續執行步驟3～步驟6，直至滿足終止條件。

步驟8故障情況下最優策略求解。根據步驟7輸出正常情況下最優卸載策略gbest(j)，運用GCL-PSO 算法求解故障情況下的卸載策略

步驟9輸出最優卸載策略及對應的系統成本。輸出每個OUE 的卸載策略（包含正常執行與故障執行2 種情況下的策略）以及對應的系統總成本。

6 實驗仿真結果與分析討論

6.1 近岸仿真結果分析

模擬OUE 在近岸場景下同時將多個任務卸載至固定邊緣計算節點（基站）和移動邊緣計算節點（船舶）的網絡場景。實驗仿真參數設置參考文獻[4,17,19]，如表2 所示。為保證數值選取的均勻隨機性，通信半徑的設置基于文獻[19]并進行了相應的調整；船舶速度的設置也主要參考文獻[19]中的研究結果（該研究結論說明海洋網絡中船舶速度與單位區域內船舶密度呈負相關，且近岸區域網絡節點密度一般高于遠岸區域）。因此，在表2 所示仿真實驗場景下，設置近岸船舶速度大于遠岸船舶速度。此外，通過多次實驗，MCO-GA 在迭代100 次以內均可實現穩定收斂，因此設迭代次數itera_num=100，MCO-GA 中種群數量S=70，交叉概率為PJ=0.6，變異概率為Pm=0.07，懲罰函數中懲罰因子l1=2，l2=1.5，變異點數目為3。

表2 近岸實驗仿真參數

為驗證MCO-GA 在卸載方面的有效性，分析MCO-GA 在不同數據量下的收斂效果以及在降低OUE 時延方面的性能，并將MCO-GA 與以下卸載策略進行比較[4,22]。1) 基站卸載策略（簡稱為BSprocess 策略），總任務平均后卸載至多個基站處理，而不卸載至移動邊緣節點；2) 隨機卸載（簡稱為RANDOM 策略），各任務數據量與邊緣計算節點隨機分配；3) 本地執行（簡稱為LOCAL 策略），任務全部在本地執行，不進行卸載；4) 將文獻[22]中所提的蟻群優化（ACO,ant colony optimization）應用至近岸多節點協同的卸載策略，簡稱為ACO 策略。

為了驗證MCO-GA 能夠在有限的迭代次數內實現穩定收斂，本文對MCO-GA 在不同數據量下的迭代收斂效果進行了驗證。如圖8 所示，隨著迭代次數的逐漸增大，MCO-GA 在不同數據量下得到的時延解逐漸減小，在迭代約30 次時，可尋找到其對應情況下的最優解實現穩定收斂（部分情況在迭代100 次以內實現收斂，如數據量為1 000 kB 時，迭代約60 次實現收斂）。通過分析，可以看出MCO-GA 在不同數據量下均可實現有限迭代次數內的穩定收斂，且收斂速度較快，使算法的運算量相對較低。此外，MCO-GA 時間復雜度與其他群智能算法相比較低[11,17]，運行時間較短，可在卸載精度要求不嚴苛的環境下快速為OUE 找到一個可行解，具有一定的實際應用性。

圖8 MCO-GA 迭代收斂

圖9 說明5 種策略執行時延總體變化趨勢均隨著OUE 數據量的增大而增加，但MCO-GA 策略時延增加最少。這是由于MCO-GA 結合近岸海洋特色對傳統GA 進行改進，使其更加適應近岸多點協同卸載問題的尋優。而基于ACO 算法的策略由于尋優時容易陷入局部最優，其執行時延在不同數據量下均大于MCO-GA，同時證明了MCO-GA 較好的尋優效果。由于仿真設置了相同的基站與船舶數目使BSprocess 策略執行時延相對較小，若減少基站數目，BSprocess 策略執行時延會隨著數據量的增加而大幅增加。由于RANDOM 策略的隨機性，在不同數據量下的執行時延波動較大，數據量為1 200 KB 的執行時延明顯高于1 400 KB 的情況。受OUE 本地計算能力的限制，LOCAL 策略在不同數據量下執行時延最高。通過對比可以看出，MCO-GA 在降低OUE 執行時延方面具有最好性能，在不同情況下均具有穩定收斂效果。

圖9 不同數據量下各策略時延對比

當移動邊緣節點計算能力保持不變時，隨著固定邊緣節點計算能力的增加，不同邊緣節點計算能力所對應時延仿真結果如圖10 所示（以固定數據量為800 KB 為例）。可以看出，隨著固定邊緣節點計算能力的提升，4 種策略任務執行時延總體均有不同程度的降低，提高了OUE 任務執行效率。MCO-GA 在不同的計算能力下均具有最小時延。再次表明所提算法隨著固定邊緣節點計算能力的變化可以靈活地調整卸載策略以確保系統的實時性，并且具有更好的動態適應性。

圖10 不同計算能力下各策略時延對比（固定數據量為800 KB）

6.2 遠岸仿真結果分析

遠岸場景下模擬K個OUE 通過各自中繼節點與海上基站進行卸載的網絡場景，仿真參數如表3所示[4,19,23]。設置粒子數量particle_num=60，迭代次數GCL_it era=100，粒子更新速度hi取值范圍為[?0.25,0.25]，慣性因子ω=0.4，隨機數r1=0.4，r2=0.6。為驗證基于GCL-PSO 算法的卸載策略在遠岸容錯機制下卸載有效性，將GCL-PSO 與以下策略進行比較。1) PSO 策略，將傳統的PSO 算法應用于遠岸的卸載策略；2) 平均卸載策略（簡稱為AVERAGE 策略），將每個OUE 的計算任務平均分配至本地，中繼節點以及OBS，OBS 計算資源平均分配給K個OUE；3) 改進PSO 策略，將文獻[21]中的改進PSO 算法應用于遠岸卸載策略；4) 將文獻[24]所提AFSA 人工魚群算法（AFSA,artificial fish swarms algorithm）應用于遠岸的卸載策略，簡稱為AFSA 策略。

表3 遠岸實驗仿真參數

為了驗證基于GCL-PSO 算法的策略在解決遠岸卸載問題時的尋優和收斂效果，本文將GCL-PSO策略與其他策略進行對比。如圖11 所示，當OUE數量K=6且計算任務量為500～900 KB 時，基于4 種策略求得的卸載總成本隨著迭代次數的增加趨于穩定，且均可在較少的迭代次數（一般為10～20 次）內實現快速收斂，運算量小。但通過對比4 種策略的尋優效果可知，GCL-PSO 策略尋優得到的系統總成本遠小于其他3 種策略，這展示了該策略良好的尋優效果。綜上所述，本文所提基于GCL-PSO 算法的策略在解決遠岸卸載問題時可在較少的迭代次數內實現穩定收斂且尋優效果遠好于其他策略。同時，GCL-PSO 策略時間復雜度為O(mn)（m和n分別代表迭代次數與粒子數目），迭代次數少，算法運算量小，說明所需運行時間較短，可滿足實際應用需求。

圖11 算法尋優和收斂效果

本文同時對比了系統中OUE 均可正常卸載時各種算法的總成本，如圖12 所示。可以發現隨著系統中OUE 數量的增加，5 種策略的計算卸載系統總成本均隨之增加，但GCL-PSO 的總成本較其他4 種策略增幅較小。這是由于GCL-PSO 引入了分組學習使在遠岸多優化變量的復雜情況下仍能制定最優的計算卸載策略，從而降低成本。由于尋優時容易陷入局部最優，改進PSO、AFSA、PSO這3 種策略較GCL-PSO 策略相比卸載成本依次增加。隨著OUE 數量的增加AVERAGE 策略系統總成本相對增加，雖然波動較小，但未實現資源的合理調配，使系統總成本較前4 種策略更大。綜上所述，可以發現在正常卸載時，GCL-PSO 能夠實現計算卸載最佳決策，并可高效地降低系統時延與能耗。

圖12 正常情況下不同OUE 數量成本對比

設置系統中故障OUE 數量為1，本文對比了故障情況下不同OUE 數量的計算卸載總成本，如圖13 所示。從圖13 可以看出，隨著OUE 數量的增加，5 種方案整體成本逐漸增加，但本文所提方案卸載總成本相對最低。同時，可以發現，當OUE 數量大于4 時，所提方案卸載成本遠小于其他方案卸載成本，表明故障情況下所提方案在OUE 數量較多的系統中能有效地降低系統時延和能耗，可以很好地適應多OUE 系統中故障情況的計算卸載。綜上所述，隨著OUE 數量的變化，所提GCL-PSO 策略在正常與故障情況下均可實現最優卸載決策，可以很好地處理故障情況下多OUE 的計算卸載問題。

圖13 故障情況下不同OUE 數量成本對比

圖14 對正常情況下5 種方法在不同數據量下的卸載成本進行了分析，實驗設置OUE 數量為5。從圖14 可以看出，數據量的增加使5 種策略的卸載成本均有不同程度的上升，但基于GCL-PSO 策略得到的卸載成本最小，表明GCL-PSO 策略能夠很好地適應不同數據量下的卸載策略尋優。此外，當數據量為500～600 KB時，GCL-PSO策略較改進PSO策略相比成本降低了20%；當數據量為600～700 KB時，GCL-PSO 策略比改進PSO 策略降低了24%的卸載成本。上述結果表明，隨著數據量的增加，GCL-PSO策略在降低卸載成本方面的優勢較更加明顯。

圖14 正常情況下不同數據量成本對比

圖15 對比了故障情況下5 種策略的總成本。實驗假設OUE 數量為5，且其中一個OUE 在卸載時其對應中繼和OBS 傳輸出現故障，需要重傳卸載。對比5 種策略在不同數據范圍下卸載總成本，圖15說明隨著OUE 任務數據量增加，5 種策略系統總成本均增加，但GCL-PSO 能在故障情況下保持較低系統成本，且系統成本增幅較小。這是由于該策略在制定正常執行時最佳卸載策略的基礎上，分析并提前制定了故障情況下任務重傳的卸載策略。而其他4 種策略由于在正常執行時尋優能力不夠，使在此基礎上的故障重傳分析尋優結果不準確，成本較高。

圖15 故障情況下不同數量成本對比

7 結束語

本文建立了近岸與遠岸2 種符合海洋特色的卸載模型。近岸場景下提出了多節點協同的卸載策略，并針對該策略提出了MCO-GA 以進一步降低OUE 卸載時延。遠岸場景下提出了GCL-PSO 算法，使遠岸容錯卸載策略能夠找到最優的卸載策略。仿真結果表明，在近岸場景下，所提算法在不同數據量下均能實現穩定收斂，且較傳統方案能夠極大地降低OUE 時延。在遠岸場景下，GCL-PSO 算法能夠實現快速收斂，與其他算法相比更加符合遠岸容錯機制下的卸載策略。

針對PSO 算法中局部尋優能力差和尋優片面的缺陷，GCL-PSO 算法通過引入分組競爭學習思想對PSO 算法進行了改進。仿真結果表明，GCL-PSO算法較傳統PSO 算法尋優能力有較大提升。未來，將針對傳統粒子群收斂精度低等缺陷對PSO 算法中的慣性因子ω等參數進行調整，可進一步提高傳統PSO 算法的收斂精度。此外，將進一步分析海洋環境因素對卸載的影響，考慮融合通信資源分配因素的卸載，為更好地提升我國海洋觀監測能力奠定堅實的基礎。