機坪感知場景下基于移動智能體的機會路由控制方法

陳維興， 孟美含， 蘇景芳

(中國民航大學電子信息與自動化學院， 天津 300300)

近年來，智慧機場已成為中國民航業(yè)發(fā)展的重要切入點，機坪作為機場運輸作業(yè)的核心區(qū)域，保障航空安全運行。其首要任務是對眾多機坪資源的全面、實時感知。

由于機坪旅客流、貨物流、資源流受航班流驅(qū)動，航班流隨機性使得感知對象、感知節(jié)點及網(wǎng)絡拓撲結(jié)構(gòu)易發(fā)生改變，從而形成許多互不連通的子域。因此，機坪環(huán)境感知網(wǎng)絡具有動態(tài)性和弱連接性。近年來，出現(xiàn)的機會網(wǎng)絡(opportunity network, OppNet)理論[1-3]采用“存儲-攜帶-轉(zhuǎn)發(fā)”的模式，可利用移動節(jié)點所帶來的相遇機會傳輸數(shù)據(jù)，解決網(wǎng)絡的間歇性問題。但基于機會的消息傳輸存在諸多不確定性，在對機坪感知數(shù)據(jù)進行采集和傳輸時面臨很大的挑戰(zhàn)[4]。

針對上述問題，中外研究人員在機會網(wǎng)絡移動模型與路由傳輸方面進行了相關(guān)研究。Talwar等[5]研究了Ad Hoc中節(jié)點流動模式對協(xié)議性能的影響。Hossen等[6]總結(jié)分析了OppNet中Epidemic、Prophet、MaxProp、SAW等經(jīng)典算法的不同移動模型性能對比，但沒有明確處理目標，環(huán)境適應性相對較弱。許炳昆等[7]在路由建立階段,通過節(jié)點間的相互運動預測鏈路的生存時間,并且將路由穩(wěn)定性與跳數(shù)之間進行均衡。李向麗等[8]考慮了消息轉(zhuǎn)發(fā)時節(jié)點的自私性并采取一種激勵策略促進節(jié)點間相互協(xié)作，但沒有考慮消息轉(zhuǎn)發(fā)時的外在環(huán)境因素。陳志剛等[9]引入節(jié)點用戶對消息內(nèi)容重要程度的設定，在提高了節(jié)點轉(zhuǎn)發(fā)消息收益和緩存利用率的同時也增加了能耗，且忽略了移動模型所產(chǎn)生的影響。劉春蕊等[10]設計了一種帶閾值的簇移動模型CMMT，增加了Ferry節(jié)點與簇節(jié)點的相遇機會，但沒有在節(jié)點相遇后進行下一跳節(jié)點的選擇。

針對機坪環(huán)境感知網(wǎng)絡的特點，合理選擇移動模型、轉(zhuǎn)發(fā)時機及下一跳節(jié)點是研究機會路由的關(guān)鍵問題。為實現(xiàn)對機坪全連通網(wǎng)絡監(jiān)控，充分考慮機坪網(wǎng)絡內(nèi)在規(guī)律性及網(wǎng)絡動態(tài)性等要素，通過引入M-Agent規(guī)劃機坪移動節(jié)點的路線模型，實現(xiàn)數(shù)據(jù)傳輸負載均衡，結(jié)合群體智能思想[11]，估計數(shù)據(jù)傳輸?shù)南乱惶?jié)點，達到改善網(wǎng)絡性能的目的。

1 機坪環(huán)境感知網(wǎng)絡系統(tǒng)

機坪環(huán)境感知系統(tǒng)包括機坪地面資源、感知節(jié)點、機坪車輛、基站(sink)、終端服務器及相關(guān)網(wǎng)絡設備等。在運行過程中，航班流驅(qū)動人員流、貨物流、資源流的變化，感知環(huán)境也隨之不同。如圖1所示，當飛機進入停機位后，各種服務車輛和保障人員開始地面保障工作，形成其感知網(wǎng)絡。由于機坪面積廣闊，依賴傳統(tǒng)無線傳感器網(wǎng)絡(wireless sensor network,WSN)很難實現(xiàn)機坪網(wǎng)絡環(huán)境連通性，特別是遠機位和航班密度較低時，會出現(xiàn)通信距離造成的非連通子域問題，形成數(shù)據(jù)中斷、子網(wǎng)邊緣存在盲區(qū)等問題。因此，以機坪特種車輛作為移動智能體(mobile agent，M-Agent)，可利用其運動的相遇機會[12]來完成數(shù)據(jù)轉(zhuǎn)發(fā)從而連接各非連通子域，實現(xiàn)機坪感知網(wǎng)絡全連通。

2 機坪感知網(wǎng)絡數(shù)據(jù)流模型設計

2.1 連續(xù)數(shù)據(jù)流模型

機坪感知過程中，助航燈柱、標志牌及高桿燈等環(huán)境感知節(jié)點上的傳感器需要周期、連續(xù)地向匯聚節(jié)點(簇頭)上傳環(huán)境數(shù)據(jù)，M-Agent節(jié)點起到移動組織者的作用，在M-Agent的移動路徑上，通過發(fā)布路由建立消息，設置約束條件，不斷沿節(jié)點(多為簇頭)轉(zhuǎn)發(fā)，形成路由樹，最后大量數(shù)據(jù)流沿路由樹向反方向向移動節(jié)點匯集。連續(xù)型數(shù)據(jù)流模型如圖2所示。

圖2 連續(xù)型數(shù)據(jù)流模型Fig.2 Continuous data flow model

2.2 事件驅(qū)動數(shù)據(jù)流模型

當航班到達后，地面保障開始作業(yè)。若機坪場景下節(jié)點均采用連續(xù)型數(shù)據(jù)流模型，多點數(shù)據(jù)連續(xù)匯聚，造成局部網(wǎng)絡資源不均衡，易導致熱點、盲點問題。考慮機坪特種車輛工作和部分感知網(wǎng)絡采集數(shù)據(jù)均受控于航班流，航班到達可視為非連續(xù)多路激勵，為達到網(wǎng)絡負載和性能優(yōu)化，除部分連續(xù)數(shù)據(jù)采集節(jié)點，部分機坪感知節(jié)點及M-Agent采用事件驅(qū)動型網(wǎng)絡模型。網(wǎng)絡模型如圖3所示。

圖3 事件驅(qū)動型數(shù)據(jù)流模型Fig.3 Event-driven data flow model

航班流有一定隨機特性(泊位位置、實際到達時間等)，機坪感知網(wǎng)絡數(shù)據(jù)流模型是共存的。

3 基于負載均衡的M-Agent網(wǎng)絡路由算法

機會網(wǎng)絡路由算法的設計和移動模型是相輔相成的，其核心思想是：基于數(shù)據(jù)流模型共存特性規(guī)劃路由，優(yōu)化M-Agent節(jié)點與分簇節(jié)點的數(shù)據(jù)交互及數(shù)據(jù)傳輸路徑，結(jié)合群體智能方法，求解M-Agent下一跳節(jié)點，保證機坪感知網(wǎng)絡的連通性和可靠性。

3.1 相關(guān)網(wǎng)絡定義

定義1 機會網(wǎng)絡模型。G=(M,V,A,E)記節(jié)點中待轉(zhuǎn)發(fā)的消息集合為M={m1,m2,…,mu}，發(fā)送消息m的簇內(nèi)節(jié)點集合為V={v1,v2,…,vn}，其中vi

定義2 M-Agent的遷移路徑模型。若M-Agent節(jié)點ai從簇內(nèi)節(jié)點vi出發(fā)，經(jīng)過鏈路E={ev1,ev2,…,evm}從第1簇節(jié)點到達第2簇繼而遍歷n簇節(jié)點。M-Agent節(jié)點ai的遷移路徑記為evm。

定義3 M-Agent負載定義。由剩余能量和消息轉(zhuǎn)發(fā)量來表示負載，負載量計算公式為

(1)

式(1)中：L(vi)為分簇節(jié)點vi的負載；q(vi)為節(jié)點vi的空閑隊列，即轉(zhuǎn)發(fā)量長度；Q(vi)為節(jié)點總隊列長度；e(vi)為節(jié)點vi的剩余能量 ；E(vi)為節(jié)點vi的總能量；δe和δq分別為能量和隊列的權(quán)重。消息在隊列中會產(chǎn)生排隊延時，所以權(quán)重由實際應用對實時性的要求確定。

3.2 SI-MA(swarm intelligence-MA)算法思想

機坪具有地域廣闊、機位分布、環(huán)境復雜、數(shù)據(jù)源分散及能源受限等特點，將機坪感知網(wǎng)絡路由分為兩部分：一是單連通子域的簇內(nèi)靜態(tài)網(wǎng)絡，多存在于近機位；二是全連通域的簇間動態(tài)連接，多存在于遠機位。

3.2.1 M-Agent節(jié)點與簇內(nèi)節(jié)點數(shù)據(jù)交互問題

簇內(nèi)節(jié)點vi向M-Agent發(fā)送數(shù)據(jù)前應先判定節(jié)點信息，機坪車輛行駛軌道和行駛速度相對固定，使車載移動節(jié)點ID、速度、遷移路徑evm、方向以及鄰居節(jié)點等狀態(tài)信息更方便預知，進而確定簇內(nèi)節(jié)點與M-Agent節(jié)點位置坐標P:{(x，y)ai,(x，y)vi}。

M-Agent移動過程中，隨網(wǎng)絡拓撲結(jié)構(gòu)的變化，其節(jié)點從不連通簇內(nèi)攜帶消息mu移動到另一簇進行數(shù)據(jù)傳輸。通常，節(jié)點傳輸跳數(shù)越小，傳輸時延和能量消耗越低。故選擇距離M-Agent更近的節(jié)點作為非連通簇內(nèi)的簇頭節(jié)點(sink)與其進行信息交互。在數(shù)據(jù)交互過程中，設定約束條件。

約束條件1：傳輸距離。設置分簇節(jié)點vi與M-Agent節(jié)點ai間的距離為

(2)

則對于任意一個M-Agent節(jié)點ai，取距離di最小的節(jié)點vj作為簇內(nèi)的sink節(jié)點繼而與M-Agent進行交互，其最小交互距離為

(3)

式(3)中：N(i)表示節(jié)點vi的鄰居節(jié)點。

約束條件2：負載量大小。由定義3可知節(jié)點的負載量化，選取低負載量簇內(nèi)節(jié)點vj作為與M-Agent交互的sink節(jié)點與其進行交互，其最小負載量為

(4)

機會網(wǎng)絡主要依靠相遇機會來傳輸消息，而節(jié)點相遇概率又可以根據(jù)約束條件等信息來估計，故設置距離和負載量作為約束條件作為下一跳與之交互的簇內(nèi)節(jié)點vj。

3.2.2 M-Agent節(jié)點路由傳輸與數(shù)據(jù)匯集問題

M-Agent數(shù)據(jù)匯集問題可視為移動目標發(fā)現(xiàn)問題，可由群體智能的思想實現(xiàn)。在機坪的數(shù)據(jù)匯集中，將M-Agent視為移動食物源，數(shù)據(jù)匯集過程視為群體覓食行為，由式(5)表示為

(5)

約束條件daj

為簡化計算，減少移動目標，采用線性加權(quán)，構(gòu)造評價函數(shù)，將其簡化為單目標數(shù)學規(guī)劃問題。針對機坪運行特點，采用距離加權(quán)求和，m個M-Agent多目標問題為

minF(X)=min[f1(X),f2(X),…，fm(X)]，

X∈R

(6)

式(6)中：X表示移動節(jié)點aj；約束條件可行點組成集合為

R={X|fai(X)≥0,(X)=0,

ai=1,2,…,m;aj=1,2,…，n}

(7)

(8)

構(gòu)造評價函數(shù)為

(9)

式(9)中：λi表示目標函數(shù)fi(X)的重要程度。

λd和λl分別表示與M-Agent節(jié)點距離的重要程度和節(jié)點負載均衡的重要程度，取值范圍及關(guān)系為

λd>0,λl≥0,λd+λl=1

(10)

式(5)評價函數(shù)求解為

(11)

式(11)中：d0為最短距離;e0為最小負載；λd和λl與機坪環(huán)境相關(guān)，根據(jù)實際情況進行調(diào)整，節(jié)點移動快、實時性要求高時，增加距離權(quán)重λd大小，節(jié)點移動慢或者能量均衡性較高時，增加負載權(quán)重λl大小使其滿足:

(12)

下一跳節(jié)點被選定后，發(fā)送反饋確認消息：機場特種車輛ID、車輛當前速度向量、當前位置坐標、是否收過該消息標識符等。通過消息中攜帶節(jié)點位置、負載量大小等信息，可精確地確定消息傳輸方向和下一跳節(jié)點，降低消息丟包率和路由開銷。

根據(jù)以上的分析，SI-MA思想可用如下偽代碼描述。

Initial: M-Agent distance from the grouping node:dvi

Packet load of grouped nodes:L(vi)

location of each node: (x，y)ai,(x，y)vi

SendDest (V,A,P,L)

Calculate the distance between node V and A

Begin to choose the cluster header

Receive (dvj,Lvj)

if (dvi

vmin=dvj,Lvj}

else {adddvj,Lvjintovmin}

UpdatePosition and load ();

SendMessage(M,V);

DataCollection(A,V,M){ }

λd,λe∈fi(X)

Return Feedback confirmation message to the M-Agent node

end for

4 仿真環(huán)境與分析

4.1 仿真環(huán)境

在機會網(wǎng)絡仿真平臺(opportunistic network environment，ONE)[13-14]下進行仿真驗證，該平臺可視為一個擔負著“存儲-攜帶-轉(zhuǎn)發(fā)”工作的路由器，能夠模擬節(jié)點的運動、節(jié)點相遇、路由以及消息傳輸?shù)恼鎸嵡闆r。采用符合機坪移動特性ClusterMovement移動模型，對M-Agent節(jié)點采用MapRouteMovement移動模型(節(jié)點在預定義的路徑上移動)連接簇間通信。由于Prophet算法利用歷史接觸時長、接觸次數(shù)等概率參數(shù)及傳遞因子使消息傳輸至概率高的中繼節(jié)點，故每次仿真結(jié)果不完全一致。因此，仿真運行5次后取平均值作為最終結(jié)果，將SI-MA算法與經(jīng)典算法Epidemic[15]、prophet[16]進行比較，具體場景參數(shù)設置如表1所示。

表1 仿真環(huán)境參數(shù)設置Table 1 Simulation environment parameter settings

4.2 不同節(jié)點數(shù)量對算法性能影響的分析

根據(jù)機坪實際工況特征，設定3個固定停機位且對應設置3簇非連通子域節(jié)點，每簇節(jié)點10～80個。考慮航班流隨機性，需要移動節(jié)點構(gòu)建機會網(wǎng)絡，根據(jù)實際情況，設置M-Agent節(jié)點為6個，且行駛軌跡具有規(guī)律性。在仿真過程中，設置所有節(jié)點緩存為25 MB，簇內(nèi)節(jié)點數(shù)量增加，但M-Agent節(jié)點不變。比較SI-MA、Prophet、Epidemic的消息投遞成功率、網(wǎng)絡開銷比率、平均消息時延。

4.2.1 消息投遞率

消息投遞率表達為

(13)

式(13)中：delivered為成功到達目的包數(shù)目；created為仿真生成的不同的數(shù)據(jù)包總數(shù)。

不同節(jié)點數(shù)量下，消息投遞成功率如圖4所示。

SI-MA算法與兩種經(jīng)典算法消息投遞率都隨簇內(nèi)節(jié)點的增加而減小，這是因為根據(jù)機坪實際網(wǎng)絡傳輸特點而設置固定M-Agent節(jié)點，只增加簇內(nèi)節(jié)點數(shù)量，隨簇內(nèi)節(jié)點數(shù)量增加，它們之間需要傳輸數(shù)據(jù)包增加，而攜帶這些數(shù)據(jù)包的M-Agent節(jié)點個數(shù)固定，故投遞率整體下降的趨勢是必然的。

由圖4可知，SI-MA算法投遞率最高，這是因為SI-MA算法在數(shù)據(jù)傳輸過程中增加傳輸距離和負載量的權(quán)重，使得數(shù)據(jù)包傳輸效率得到提高，在結(jié)點數(shù)為215個時消息投遞率最低約為0.54，這在機坪網(wǎng)絡傳輸過程中是可接受的。而Epidemic與Prophet在此節(jié)點數(shù)后投遞率均低于0.5，這是因為Epidemic消息復制沒有任何限制條件，消息副本傳輸給每個相遇節(jié)點，而Prophet算法單純依靠歷史相遇概率來選擇下一跳節(jié)點，未對節(jié)點的屬性權(quán)重做出考慮。過量消息副本必然導致緩存空間不足和能量過快消耗，因此在網(wǎng)絡中死亡節(jié)點增加，投遞成功率大幅下降。但SI-MA消息投遞率仍比Prophet和Epidemic平均提高12.85%和20.6%。

圖4 不同節(jié)點數(shù)下的消息投遞率Fig.4 Message delivery rates for different numbers of nodes

4.2.2 網(wǎng)絡開銷

網(wǎng)絡開銷比率由包轉(zhuǎn)發(fā)總數(shù)和包成功到達數(shù)二者決定，表達為

(14)

式(14)中：relayed為實際完成的總轉(zhuǎn)發(fā)數(shù)；delivered為成功到達目的地的包數(shù)目。

不同節(jié)點數(shù)下的網(wǎng)絡開銷比率如圖5所示，網(wǎng)絡開銷比率都隨節(jié)點數(shù)量增加而上升，這是網(wǎng)內(nèi)簇內(nèi)節(jié)點增多造成的必然結(jié)果。相對而言，Epidemic算法中節(jié)點隨機泛洪的轉(zhuǎn)發(fā)數(shù)據(jù)會制造大量冗余副本，增加網(wǎng)絡中分簇數(shù)據(jù)能耗，使路由開銷率提高，而SI-MA算法通過采用數(shù)據(jù)流模型共存方式并選擇最佳鄰居節(jié)點轉(zhuǎn)發(fā)數(shù)據(jù)，在節(jié)點數(shù)達到95個之后有效降低了網(wǎng)絡開銷。SI-MA網(wǎng)絡開銷比率分別比Prophet和Epidemic平均降低了20.31%和48.79%。

圖5 不同節(jié)點數(shù)下的網(wǎng)絡開銷比率Fig.5 Network overhead ratio for different number of nodes

4.2.3 消息平均時延

消息平均時延是指數(shù)據(jù)包從發(fā)送端傳輸至接收端花費的時間。不同節(jié)點數(shù)下的消息投遞成功率如圖6所示，SI-MA算法與Prophet算法的消息平均時延都隨簇內(nèi)節(jié)點的增加而快速下降，節(jié)點總數(shù)在65個后，隨節(jié)點數(shù)量的增加，SI-MA算法時延減小速度較快，這是因為隨節(jié)點數(shù)量增加，分簇節(jié)點與M-Agent節(jié)點分別采用不同的移動模型，使傳輸路徑趨于穩(wěn)定，且選擇與目的節(jié)點同方向的距離近且負載量低的中繼節(jié)點，避免了消息副本無限制傳輸導致的通信時延。SI-MA的平均消息延時分別比Prophet和Epidemic，平均降低了7.48%和12.31%。

圖6 不同節(jié)點數(shù)下的通信時延Fig.6 Communication delay with different number of nodes

由以上結(jié)果可知，節(jié)點數(shù)量一定程度上影響算法性能，在相同的網(wǎng)絡環(huán)境下，簇內(nèi)節(jié)點越多，M-Agent節(jié)點需要轉(zhuǎn)發(fā)的消息量越多，但由于移動節(jié)點的數(shù)量不變、緩存固定，使得能量消耗大，故消息投遞率降低，網(wǎng)絡開銷升高。在數(shù)據(jù)轉(zhuǎn)發(fā)過程中，若M-Agent節(jié)點始終處于工作狀態(tài)，則能量消耗過快，節(jié)點死亡較早。因此未采用數(shù)據(jù)流模型切換的Epidemic和Prophet算法性能低于SI-MA算法。該算法在節(jié)點數(shù)量較大時仍然具有較好的性能。

4.3 緩存空間對算法性能的影響

節(jié)點緩存空間大小的設置也是影響算法性能的一個重要參數(shù)。由于緩存空間的大小決定了節(jié)點存儲轉(zhuǎn)發(fā)消息量的大小。本節(jié)根據(jù)機坪的實際情況設置3簇節(jié)點內(nèi)分別為50個，移動節(jié)點6個，總結(jié)點為155個。在不同緩存空間下，研究3種算法的消息投遞成功率、網(wǎng)絡開銷比率、平均消息時延3個參數(shù)。

4.3.1 不同緩存空間下消息投遞率

不同緩存空間下的消息投遞成功率如圖7所示。投遞率隨緩存空間增加呈上升趨勢，但SI-MA算法優(yōu)于其他算法，隨緩存增大，其投遞率可達0.95以上。同時可見，當緩存增長至20 MB后，投遞率增長速度明顯下降，說明當緩存增長至一定程度后對投遞率的影響減弱，這可能是由于網(wǎng)絡內(nèi)數(shù)據(jù)分簇數(shù)量規(guī)模沒有大幅變化，進一步增長緩存對網(wǎng)絡性能影響不大。由圖7可知，SI-MA的消息投遞率分別比Prophet和Epidemic平均提高了8.07%、8.19%。

圖7 不同緩存空間下的消息投遞率Fig.7 Message delivery rate under different buffer spaces

4.3.2 不同緩存空間下網(wǎng)絡開銷比率

不同緩存空間下的網(wǎng)絡開銷比率如圖8所示，網(wǎng)絡開銷比率隨緩存增加而呈下降趨勢，Epidemic和Prophet算法網(wǎng)絡開銷比率在緩存為20 MB后趨于平緩，而SI-MA算法仍然處于下降趨勢，并且在緩存為40 MB時開銷比率降至1 000左右，這在機坪的網(wǎng)絡監(jiān)控中是可以接受的比率。SI-MA的網(wǎng)絡開銷比率分別比Prophet和Epidemic平均降低了28.11%和21.66%。

圖8 不同緩存空間下的網(wǎng)絡開銷比率Fig.8 Network overhead ratio under different cache spaces

4.3.3 不同緩存空間下平均消息延時

不同緩存空間下的平均消息時延如圖9所示。Epidemic算法平均消息時延最大且處于增長趨勢，這是由Epidemic泛洪傳輸方式使得緩存過大導致。根據(jù)信息論的原理，當投遞率增大網(wǎng)絡開銷減小時，說明網(wǎng)絡成功傳輸?shù)臄?shù)據(jù)量較大，因此SI-MA算法相對Prophet消息時延沒有明顯優(yōu)勢，但緩存增大至20 MB后，SI-MA法仍具有時延的下降，說明其具有相對優(yōu)勢。

圖9 不同緩存空間下的平均消息時延Fig.9 Average message delay in different buffer spaces

由以上結(jié)果可知，節(jié)點緩存大小也對算法性能有影響，在相同的網(wǎng)絡環(huán)境下，緩存空間越大，則節(jié)點可存儲轉(zhuǎn)發(fā)的消息量越大，因而消息投遞率越高，網(wǎng)絡開銷越低。通過以上分析可知，節(jié)點緩存設置20～30 MB時使用該算法具有較好的性能。

5 結(jié)論

通過分析機坪節(jié)點實際情況，建立網(wǎng)絡移動節(jié)點模型，對不同類型的消息采用不同數(shù)據(jù)流模型，以M-Agent觸發(fā)事件驅(qū)動模型為主，統(tǒng)籌其他節(jié)點，利用群體智能的思想限定約束條件，對節(jié)點的路由決策問題進行優(yōu)化。實驗結(jié)果表明：該算法能夠高效地將機坪工況數(shù)據(jù)傳輸至上位機，降低路由開銷與通信時延，滿足機坪數(shù)據(jù)傳輸?shù)膶崟r性和負載均衡性。但由M-Agent驅(qū)動模型來考慮最優(yōu)下一跳路由選擇屬于一種貪心策略，而機坪設備數(shù)量多且較分散，如何確保機坪網(wǎng)絡的全局優(yōu)化是未來研究方向，將對其作進一步研究。